几天前举行了一次九头蛇会议 。 JUG.ru集团的成员邀请了梦想中的演讲者（莱斯莉·兰普波特！克里夫·喀特！马丁·克莱普曼！），并花了两天时间致力于分布式系统和计算。 Contour是三个会议合作伙伴之一。 我们在展台上交谈，谈论了我们的分布式存储设施，玩了宾果游戏，解决了问题。
这是一篇文章，作者分析了Contour展位上的任务。 谁在Hydra上是您回想令人愉快的印象的原因，而谁却不是-可以使您的大脑大张O标记的机会。
甚至有参与者将活动挂图分解成幻灯片以记录他们的决定。 我不是在开玩笑-他们交出了这张纸以供检查：
总共有三项任务：
- 选择用于权重的副本以实现负载平衡
- 有关将查询结果排序到内存数据库的信息
- 环形拓扑的分布式系统中的状态转移
任务1. ClusterClient
有必要提出一种从分布式系统的N个加权副本中有效选择K的算法：
您的团队的任务是为大型分布式N节点集群开发客户端库。 库将跟踪与节点关联的各种元数据（例如，它们的延迟，4xx / 5xx响应率等），并为它们分配浮点权重W 1 ..W N。 为了支持并发执行策略，库应该能够随机选择K个N个节点-被选择的机会应与节点的权重成正比。
提出一种有效选择节点的算法。 使用大O表示法估算其计算复杂度。
为什么一切都是英文的？因为以这种形式，会议的参加者与他们抗争，并且因为英语是九头蛇的官方语言。 任务如下所示：
带上纸和笔，想一想，不要着急立即打开扰流板:)
汇报（视频）从5:53开始，仅需4分钟：
那些拿着活动挂图的家伙如何提出他们的决定：
决策分析（文本）从表面上看，有一个解决方案：对所有副本的权重求和，生成一个从0到所有权重之和的随机数，然后选择一个i副本，以使从0到第（i-1）的副本权重之和小于随机数，并且副本权重之和从0到第i-大于它。 结果是选择一个副本，然后选择下一个副本，您需要重复整个过程而不考虑所选副本。 使用这种算法，选择一个副本的复杂度为O（N），选择K个副本的复杂度为O（N·K）〜O（N 2 ）。
二次复杂度不好，但是可以改善。 为此，为权重之和构建一个分段树 。 这将产生一棵深度为N的树，在树的叶子中将有复制权重，而在其余节点中，将是部分和，直至树根中所有权重的和。 接下来，我们生成一个从0到所有权重之和的随机数，找到第i个副本，将其从树中删除，然后重复该过程以搜索剩余的副本。 使用这种算法，构造树的复杂度为O（N），找到第i个副本并将其从树中删除的复杂度为O（log N），选择K个副本的复杂度为O（N + K log N）〜O（N log N） 。
线性对数复杂度比二次复杂度好，尤其是对于大K而言。
该算法在Vostok项目的ClusterClient库的代码中实现 。
任务2.斑马
有必要提出一种算法，用于通过任意非索引字段对内存中的文档进行有效排序：
您的团队的任务是开发内存中的分片文档数据库。 常见的工作是从大小为M（通常N <100 << M）的集合中选择按任意（非索引）数字字段排序的前N个文档。 较少的常见工作量是在跳过前S个文档（S〜N）之后选择前N个。
提出一种算法来有效执行此类查询。 在平均情况和最坏情况下，使用大O表示法估算其计算复杂度。
决策分析（文本）解决方案是表面上的：对所有文档进行排序 （例如，使用quicksort ），然后获取N + S个文档。 在这种情况下，平均排序的复杂度为O（M lg M），最差的情况为-O（M 2 ）。
显然，对所有M个文档进行排序以仅获取其中的一小部分效率低下。 为了不对所有文档进行排序，使用quickselect算法是合适的 ，该算法选择N + S个必需的文档（它们可以通过任何算法进行排序）。 在这种情况下，复杂度平均降低到O（M），最坏的情况保持不变。
但是，您可以更加有效地进行操作-使用二进制堆流算法。 在这种情况下，将前N + S个文档添加到最小或最大堆中（取决于排序方向），然后将每个后续文档与树的根进行比较，该树的根包含当前的最小或最大文档，并在必要时添加到树中。 在这种情况下，最坏情况下的复杂度是必须不断重建树-O（M lg（N + S）），与快速选择一样，平均复杂度为O（M）。
但是，由于实际上在与根元素进行一次比较之后，实际上可以丢弃大多数文档而无需重建堆，因此堆流更为有效。 这种分类是在电路中开发和使用的Zebra文档内存数据库中实现的。
任务3.状态交换
有必要提出一种最有效的状态转移算法：
您的团队的任务是为N个节点的分布式集群开发一种幻想状态交换机制。 第i个节点的状态应传输到第（i + 1）个节点，第N个节点的状态应传输到第一个节点。 当两个节点原子交换其状态时，唯一支持的操作是状态交换。 已知状态交换需要M毫秒。 每个节点都可以在任何给定时刻参与单个状态交换。
转移集群中所有节点的状态需要多长时间？
决策分析（文本）表面上的解决方案：交换第一个和第二个元素的状态，然后交换第一个和第三个元素的状态，然后交换第一个和第四个元素的状态，依此类推。 每次交换后，一个元素的状态将处于所需位置。 您必须进行O（N）个排列并花费O（N·M）时间。
线性时间很长，因此您可以成对交换元素的状态：第一个与第二个交换，第三个与第四个交换，依此类推。 每次交换后，每个第二元素的状态将处于所需位置。 我们将不得不进行O（对数N）的排列，并花费O（对数N N）的时间。
但是，您可以使转换更加有效-不是线性的，而是恒定的时间。 为此，在第一步中，您需要将第一个元素的状态与最后一个交换，将第二个元素的倒数第二个交换，依此类推。 最后一个元素的状态将处于所需位置。 现在，您需要与第二个元素交换第二个元素的状态，与倒数第二个交换第三个元素的状态，依此类推。 经过这一轮的交换，所有元素的状态将处于正确的位置。 总共将进行O（2M）〜O（1）个排列。
这样的解决方案不会令数学家感到惊讶，他仍然记得旋转是两个轴向对称的组合。 顺便说一句，一般来说，它不移位1，而是移位K <N个位置。 （在注释中确切写出方法。）
你喜欢拼图吗？ 您知道其他解决方案吗？ 分享评论。
最后是一些有用的链接：