Google研究 | 使用一致的哈希算法分配临界负载

文 | NYC 算法团队首席科学家 Vahab Mirrokni 和研究员 Morteza Zadimoghaddam

运行大规模网络服务（例如内容托管）离不开负载平衡，也就是将客户端均匀地分配到多个服务器上，使得每个服务器都不至于过载。此外，在随时可以添加或移除客户端和服务器的动态环境中，较为理想的做法是找到一种不会随时间而大幅改变的分配方案。换而言之，我们需要在一段时间内一致地将客户端分配到服务器。

通过与哥本哈根大学客座研究员 Mikkel Thorup 合作，我们开发了一种全新而有效的分配算法来解决这一问题，能够严格保证每台服务器的最大负载，并从理论和实践上研究了这一算法。随后，我们与我们的云团队合作，在 Google Cloud Pub/Sub 这一可扩展的事件流服务中实现了该算法，我们发现，在符合一致性和稳定性目标的同时，还显著改善了负载分配的均匀性（以服务器分配到的最大负载来衡量）。2016 年 8 月，我们在“使用一致的哈希算法分配临界负载”(Consistent Hashing with Bounded Loads) 论文中介绍了我们的算法，并在 ArXiv 中分享了这一算法，以供更广泛的研究社区使用。

三个月以后，来自 Vimeo 的 Andrew Rodland 通知我们，他发现了该论文，随后在 haproxy（一段广泛使用的开放源代码软件）中实现了该算法并将其用于 Vimeo 的负载平衡项目。结果非常引人注目：应用这些算法帮助他们几乎将缓存带宽降低到原来的 1/8，从而消除了扩展瓶颈。他最近在一篇博文中概述了这一案例，详细介绍了他的用例。毋庸赘言，我们非常兴奋地了解到，我们的理论研究成果不仅被投入应用，还体现出使用价值，并且还开放源代码。

背景

尽管过去已经研发出一致的哈希算法理念来解决动态环境中的负载平衡问题，但所有之前开发的方案都存在一个根本性的问题：在特定的场景下，它们可能导致许多服务器上的负载平衡不能达到最佳状态。

此外，由于可能随时添加或移除客户端和服务器，在做出此类改动时，我们不希望移动太多的客户端。因此，动态分配算法不仅必须始终确保正确的负载平衡，还应尽量减少每次对系统做出改动之后所移动的客户端数量。当每台服务器的容量存在严格的限制时，也就是说，每台服务器都有严格的容量限制，负载不得超过此限制之时，此类分配问题会变得更为严峻。通常，我们希望容量接近于平均负载。

换而言之，我们希望在最终的分配中同时实现均匀性和一致性这两大目标。对于服务器集固定不变、只有客户端集会更新这种简单很多的情形，有大量的文献介绍了相关的解决方案，但在本文中，我们讨论的解决方案针对的是客户端和服务器均可随时添加和移除的完全动态的情形。

算法

我们可以将服务器比作垃圾桶，将客户端比作球，并借鉴将球随机投入垃圾桶的过程 (balls-to-bins stochastic processes) 这一经过深入研究的模型，采用与之类似的抽象方法。均匀性目标要求所有垃圾桶所装的球数量大致等于平均密度（球数除以箱子数）。对于参数 ε，我们将每个垃圾桶的容量设置为平均负载的最低或最高倍数 (1+ε)。这一额外的容量让我们可以设计出一种能够同时满足均匀性目标和一致性目标的分配算法。

设想给定范围的一组数字，将其分布到一个圆圈上。我们对球应用一个哈希函数，对垃圾桶应用另一个不同的哈希函数，以获取该范围内、与该圆圈上不同位置对应的数字。随后，我们开始按特定的顺序分配球，此顺序与其哈希值无关（假设基于其 ID）。然后，按顺时针移动每个球并将其分配到第一个有空闲容量的垃圾桶。

我们分析一下上面的例子，我们使用两种不同的哈希函数，将 6 个球和 3 个垃圾桶随机分配到圆圈上的不同位置。对于本例，我们假设每个垃圾桶的容量设置为 2。我们开始按 ID 值的升序分配球。1 号球按顺时针移动，进入垃圾桶 C。2 号球进入垃圾桶 A。3 号和 4 号球进入垃圾桶 B。5 号球进入垃圾桶 C。6 号球顺时针移动，首先命中垃圾桶 B。然而，垃圾桶 B 的容量为 2，而其中已经装有 3 号和 4 号球。因此，6 号球继续向前移动，直至到达垃圾桶 C，但该垃圾桶也已满。最后，6 号球进入仍有空余位置的垃圾桶 A。

如对系统进行任何更新（插入/删除球或垃圾桶），则会重新计算分配，以保持均匀性目标。分析表明小幅更新（插入和删除少量的球或垃圾桶）会导致分配状态的小幅改变，因此，可满足一致性目标。在我们的论文中，我们展示了在该系统中，每插入或移除一个球将会导致其他球进行 O(1/ε2) 次运动。最重要的是，此上限与系统中球或垃圾桶的总数无关。因此，如果球或垃圾桶的数量加倍，此上限不会改变。上限与球或垃圾桶的数量无关，为可伸缩性带来了巨大的空间，因为我们将其搬到更大的实例中，仍然可以满足一致性目标。下面显示了更新某个垃圾桶/服务器时，每次更新所导致的移动（重新分配）次数模拟结果。

红色曲线代表移动的平均次数，蓝色柱线代表不同 ε 值（X 轴）的方差。虚线代表我们的理论结果所建议的上限，其非常适合用于预测实际的移动次数。此外，对于任何 ε 值，我们知道，每个垃圾桶的负载至多是平均负载的 (1+ε) 倍。下面，我们看到不同值 ε=0.1、ε=0.3 和 ε=0.9 条件下垃圾桶的负载分布情况。

▲ 不同 ε 值下的负载分布。对于所有范围的负载（从 0 到 (1+ε) 倍于平均负载），负载分布均接近均匀，许多垃圾桶的负载等于平均负载的 (1+ε) 倍。    

我们可以看到，这里需要折中考虑，较低的 ε 值有利于确保均匀性，但不利于确保一致性，而较大的 ε 值则有利于确保一致性。较低的 ε 值可确保许多负载等于平均负载的 (1+ε) 倍这一硬性容量限制，而其他负载则为递减分布。

在提供内容托管服务时，必须做好应对许多不同特性的实例的准备。这种一致的哈希方案非常适合此类情形，因为即便是最糟糕的情形下，它也能有不错的表现。

我们的内部研究结果激动人心，我们更欣慰的是，更广大的社区发现我们的解决方案非常有用，足以列入开放源代码，让任何人都可以使用该算法：

https://github.com/arodland/haproxy

如果您有兴趣进一步了解本研究的详细情况，请在 ArXiv 上查阅此论文，并请务必关注，NYC 算法团队将公布更多的研究成果：

https://arxiv.org/abs/1608.01350

致谢：

我们想感谢来自 Google Cloud Pub/Sub 团队的 Alex Totok、Matt Gruskin、Sergey Kondratyev 和 Haakon Ringberg，当然还要感谢 Mikkel Thorup 对此论文做出的宝贵贡献。

了解更多细节，查看文内所有链接，请点击文末“阅读原文”。

scrolling="no" frameborder="0" class="vote_iframe js_editor_vote_card" data-display-style="height: 172px;" data-display-src="/cgi-bin/readtemplate?t=vote/vote-new_tmpl&__biz=MzAwODY4OTk2Mg==&supervoteid=449718494&token=1233282222&lang=zh_CN" data-src="/mp/newappmsgvote?action=show&__biz=MzAwODY4OTk2Mg==&supervoteid=449718494#wechat_redirect" data-supervoteid="449718494" allowfullscreen>

点击「阅读原文」，查看文内链接