发生在几天前 。 JUG.ru 集团的人员邀请了梦想演讲者（Leslie Lamport！Cliff Click！Martin Kleppmann！），并花了两天时间讨论分布式系统和计算。 Kontur 是本次会议的三位合作伙伴之一。 我们在展位上交谈，谈论我们的分布式存储，玩宾果游戏，解决谜题。
这是一篇文章，作者对 Kontur 展台的任务进行了分析。 谁在九头蛇号上 - 这是您记住这次愉快经历的原因，谁不在 - 这是一个锻炼大脑的机会 大O-符号。
甚至还有参与者将活动挂图拆成幻灯片来写下他们的决定。 我不是开玩笑——他们把这一叠纸交给了我们核实：
总共有三项任务：
- 关于按权重选择副本以进行负载平衡
- 关于根据内存数据库对查询结果进行排序
- 环形拓扑分布式系统中的状态转移
任务 1. ClusterClient
有必要提出一种从分布式系统的 N 个加权副本中有效选择 K 的算法：
您的团队的任务是为 N 个节点的大规模分布式集群开发客户端库。 该库将跟踪与节点相关的各种元数据（例如，它们的延迟、4xx/5xx 响应率等）并向它们分配浮点权重 W1..WN。 为了支持并发执行策略，库应该能够随机选择 N 个节点中的 K 个——被选择的机会应该与节点的权重成正比。
提出一种有效选择节点的算法。 使用大 O 表示法估计其计算复杂度。
为什么全部都是英文？
因为在这种形式下，会议参与者与他们战斗，并且因为英语是九头蛇的官方语言。 任务看起来像这样：
拿起纸和笔，想一想，不要急于立即打开剧透🙂
解决方案分析（视频）
5点53分开始，仅4分钟：
下面是那些拿着挂图的人如何提出他们的解决方案：
解决方案分析（文字）
表面上的解决方案是：将所有副本的权重相加，生成一个从 0 到所有权重之和的随机数，然后选择一个 i-副本，使得副本权重之和从 0 到第 (i-1)th小于随机数，并且从 0 到第 i 个副本权重的总和 - 大于该随机数。 因此，您可以选择一个副本，并选择下一个副本，您需要重复整个过程，而不考虑所选的副本。 采用这样的算法，选择一个副本的复杂度为 O(N)，选择 K 个副本的复杂度为 O(N K) ~ O(N2)。
二次复杂度不好，但可以改进。 为此，我们将构建 为权重总和。 将获得深度为 lg N 的树，在其叶子中将有副本权重，在其余节点中将有部分和，直到树根处的所有权重之和。 接下来，我们生成一个从 0 到所有权重之和的随机数，找到第 i 个副本，将其从树中删除，然后重复该过程以找到剩余的副本。 使用该算法，构建树的复杂度为 O(N)，找到第 i 个副本并将其从树中删除的复杂度为 O(lg N)，选择 K 个副本的复杂度为 O(N + K lg N) ~ O(N lg N) 。
线性对数复杂度比二次复杂度更好，尤其是对于较大的 K。
就是这个算法 项目中的 ClusterClient 库“”。 （其中，树的构建时间为 O(N lg N)，但这并不影响算法的最终复杂度。）
任务 2. 斑马
有必要提出一种算法，通过任意非索引字段对内存中的文档进行有效排序：
您的团队的任务是开发分片内存文档数据库。 常见的工作负载是从大小为 M（通常 N < 100 << M）的集合中选择按任意（非索引）数字字段排序的前 N 个文档。 稍微不太常见的工作负载是在跳过前 S 个文档（S ~ N）后选择前 N 个。
提出一种算法来有效地执行此类查询。 在平均情况和最坏情况下使用大 O 表示法估计其计算复杂度。
解决方案分析（视频）
34:50开始，仅6分钟：
解决方案分析（文字）
表面解决方案：对所有文档进行排序（例如 ），然后取N+S个文档。 在这种情况下，排序的复杂度平均为 O(M lg M)，最坏为 O(M2)。
显然，对所有 M 个文档进行排序，然后只取出其中的一小部分是低效的。 为了不对所有文档进行排序，适合使用一种算法 ，这将选择 N + S 个所需文档（它们可以通过任何算法排序）。 在这种情况下，平均复杂度将降低到 O(M)，而最坏情况将保持不变。
但是，您可以更有效地做到这一点 - 使用算法 。 在这种情况下，前 N+S 个文档被添加到最小堆或最大堆（取决于排序方向），然后将每个下一个文档与包含当前最小或最大文档的树的根进行比较，并在必要时添加到树中。 在这种情况下，最坏情况下的复杂度（当您必须不断重建树时）为 O(M lg M)，平均复杂度为 O(M)，与快速选择一样。
然而，堆流式传输被证明更有效，因为实际上，在与其根元素进行一次比较后，大多数文档都可以被丢弃，而无需重建堆。 这种排序是在 Kontur 开发和使用的 Zebra 内存文档数据库中实现的。
任务 3. 状态交换
有必要提出最有效的状态转换算法：
您的团队的任务是为 N 个节点的分布式集群开发一种奇特的状态交换机制。 第 i 个节点的状态应转移到第 (i+1) 个节点，第 N 个节点的状态应转移到第一个节点。 唯一支持的操作是两个节点原子交换状态时的状态交换。 已知状态交换需要 M 毫秒。 每个节点都可以在任何给定时刻参与单个状态交换。
集群中所有节点的状态转移需要多长时间？
解决方案分析（文字）
表面解：交换第一个和第二个元素的状态，然后交换第一个和第三个元素的状态，然后交换第一个和第四个元素的状态，依此类推。 每次交换后，一个元素的状态将处于所需的位置。 您必须进行 O(N) 排列并花费 O(N M) 时间。
线性时间很长，因此您可以成对交换元素的状态：第一个与第二个，第三个与第四个，依此类推。 每次状态交换后，每隔一个元素都会处于正确的位置。 您必须进行 O(lg N) 排列并花费 O(M lg N) 时间。
然而，有可能使这种转变更加有效——不是线性的，而是恒定的时间。 为此，第一步需要交换第一个元素与最后一个元素的状态，第二个元素与倒数第二个元素的状态，依此类推。 最后一个元素的状态将处于正确的位置。 现在我们需要交换第二个元素与最后一个元素的状态，第三个元素与倒数第二个元素的状态，依此类推。 经过这一轮的交流，所有元素的状态都会回到正确的位置。 总共会有 O(2M) ~ O(1) 次排列。
对于仍然记得旋转是两个轴对称的组合的数学家来说，这样的解决方案根本不会感到惊讶。 顺便说一句，它通常被推广为移位不是一位，而是 K < N 个位置。 （具体写在评论里。）
你喜欢拼图吗？ 您知道其他解决方案吗？ 在评论中分享。
最后是一些有用的链接：
- 学习更多关于 轮廓上
- 查看内部记录 关于分布式系统
- 观看系列视频讲座»
- 订阅我们的
来源： habr.com