谷歌推出有界负载的一致性哈希算法，解决服务器负载均衡问题

studyinsweden

雷锋网AI科技评论按：运行大型Web服务需要负载平衡，例如内容托管。通常做法是在多个服务器之间均匀分发客户端，以免任何服务器超负荷运行。此外，谷歌的研究者们期望找到一种分发方式，使得在客户端和服务器可以随时增加或删除的动态环境中，分发也不会随时间波动产生太大变化。

谷歌与哥本哈根大学访问研究员Mikkel Thorup合作，开发了一种新的高效分配算法来解决这个问题：即严格控制每个服务器的最大负载，并从理论和经验上进行了研究。紧接着，谷歌研究院与云团队合作，在Google Cloud Pub / Sub（一种可扩展的事件流媒体服务）中实现算法，并在保证一致性和稳定性的同时，对负载分配（分配给服务器的最大负载）的均匀性进行了实质性改进。在2016年8月，谷歌纽约研究院的 Vahab Mirrokni、Mikkel Thorup 及Mikkel Thorup发表了论文“Consistent Hashing with Bounded Loads”，并在论文中描述了算法，并分享在ArXiv上，方便更广泛的研究用途。

三个月后，Vimeo的Andrew Rodland告诉我们，他发现了这篇论文并在haproxy（一个广泛使用的开源软件）中实现此算法，将其用于Vimeo的负载平衡项目。结果非常惊人：这种算法帮助他们将缓存带宽降低了近8倍，解决了扩大规模的一个瓶颈。他最近在一篇博客文章中详细介绍了此应用。这证明了谷歌研究院的理论研究不仅能应用到实践中，也兼具开源及有效的优点。

以下为雷锋网编译的论文部分内容，未经许可不得转载。

背景

尽管一致性哈希算法早以被应用到动态环境中的负载平衡问题上，但是普遍存在的一个基本问题是，在某些情况下，它们可能导致许多服务器上的负载平衡次优化。

此外，客户端和服务器可能会定期添加或删除，但谷歌研究团队不希望因此导致客户端的大量移动。因此，动态分配算法不仅要始终确保适当的负载均衡，还要最小化每次变化后被移动的客户端数量。此外，服务器容量的严格限制使得这种分配问题更具挑战性，也就是， 每台服务器都有一个最大负载容量限制，我们希望容量能接近于平均负载。

换句话说，我们希望同时实现分配的均匀性和一致性。有大量的文献讨论了简单场景，即服务器集群是固定的，只有客户端被更新。但在这篇文章中，谷歌研究团队讨论了完全动态的场景，即客户端和服务器可以随时被添加和删除。

算法

谷歌研究团队把每个客户端想象成一个球，将服务器想象成进球箱，仔细研究进球的随机过程。为了实现进球箱的均匀性，期望所有箱子的负载尽量接近平均负载（球的数量除以箱子数量）。对于参数ε，谷歌研究团队将每个箱子的容量上下界设置为平均负载的上下（1 +ε）倍。这种容量范围允许设计一个同时满足一致性和均匀性的分配算法。

想象一下，在一个圆上覆盖了给定范围的数字。谷歌研究团队对球和进球箱分别应用不同的哈希函数，以获得与该圆上的位置对应范围内的数字。然后，我们开始以特定的顺序（假设根据它们的ID）分配球，而不考虑它们的哈希值。然后每个球顺时针移动，并分配到还有剩余容量的第一个箱子。

想象一下有6个球和3个箱子，使用2个哈希函数来随机循环地分配球进箱。设每个箱子的容量是2，然后按球的升序依次分配球（根据它们的ID），顺时针移动，1号球进入箱子C，2号球进入箱子A，3号球和4号球进入箱子B，5号球进入箱子C，然后6号球顺时针移动尝试进入箱子B，然而箱子B容量已达限制（箱子容量为2，箱子B已经装了3号球和4号球），所以6号球继续顺时针移动尝试进入箱子C，但是箱子C也已达容量，最后6号球进入了箱子A。

系统有任何更新（球或箱增加/删除）时，算法需要重新进行计算分配以保证均匀性。算法中巧妙的一点在于，确保小范围的更新（少量球或箱增加/删除）只引起细微的分配变化，以满足一致性。 在论文中，谷歌研究团队表明了增加和删除一个球引起其他球O（1 /ε²）的移动。最重要的一点是负载上界与系统中的球或箱的数量相对独立。 所以即使球或箱的数量加倍，负载的界限也不会改变。这一点增强了分配问题的可扩展性（即使扩大分配规模，也不影响一致性）。下图模拟了球或箱有更新时，移动次数（再分配）随更新的变化情况。

红色曲线显示平均移动次数，蓝色线条表示不同ε值的方差。 虚线曲线是基于理论研究建议的负载上界（通过预测实际运动次数能较好地拟合）。除此之外，对于任意值ε，谷歌研究团队知道每个箱子的负载上下界为平均负载的（1 +ε）倍。 下图表示不同值ε（ 0.1，0.3，0.9）对应的箱子的负载分布。

不同ε值的负载分布。 负载分布几乎均匀，覆盖了从0到（1 +ε）倍的平均负载，还有许多箱子的负载等于（1 +ε）倍的平均负载

从图中可以看出均匀性和一致性的一个折衷 - 较小的ε值增强了均匀性，降低了一致性；而较大的ε值增加了一致性而降低了均匀性。较低的ε值能确保许多箱子的负载等于（1 +ε）倍的平均负载，其余箱子的负载依次衰减。

提供内容托管服务可能会遇到差异很大的各种场景，在这种情况下，谷歌研究院提供的这种一致性哈希算法将是理想的解决方案，即使是面对最坏的情况。

作者们对于内部试验的结果感到兴奋，但更加高兴的是，外界发现该算法很有效果且兼具开源特性，允许任何人使用此算法。

致谢：感谢Google Cloud Pub / Sub团队的Alex Totok，Matt Gruskin，Sergey Kondratyev和Haakon Ringberg，以及Mikkel Thorup对本文的宝贵贡献。

原文链接：https://research.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html，雷锋网编译