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 /ε2）的移动。最重要的一点是负载上界与系统中的球或箱的数量相对独立。 所以即使球或箱的数量加倍，负载的界限也不会改变。这一点增强了分配问题的可扩展性（即使扩大分配规模，也不影响一致性）。下图模拟了球或箱有更新时，移动次数（再分配）随更新的变化情况。
红色曲线显示平均移动次数，蓝色线条表示不同ε值的方差。 虚线曲线是基于理论研究建议的负载上界（通过预测实际运动次数能较好地拟合）。除此之外，对于任意值ε，谷歌研究团队知道每个箱子的负载上下界为平均负载的（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，雷锋网编译
雷峰网版权文章，未经授权禁止转载。详情见转载须知。
