运行大型网络服务（如内容托管）离不开负载均衡，即将客户端均匀分配到多台服务器上，使每台服务器不至于过载。此外，在可以随时添加或删除客户端和服务器的动态环境中，找到一个不会随时间发生剧烈变化的分配是理想的。换句话说，我们需要随着时间的推移一致地将客户端分配给服务器。背景虽然过去已经发展了一致性哈希算法思想来解决动态环境下的负载均衡问题，但是之前发展的所有方案都存在一个根本问题：在某些场景下，它们会导致负载均衡在许多服务器上无法达到平衡在一个完美的状态。此外，由于可以随时添加或删除客户端和服务器，我们不想在进行这些更改时移动太多客户端。因此，动态分配算法不仅必须始终确保正确的负载平衡，而且还要尽量减少每次对系统进行更改时移动的客户端数量。当对每台服务器的容量有硬限制时，这种分配问题会加剧，也就是说，每台服务器都有一个硬容量限制，负载不得超过该限制。通常，我们希望容量接近平均负载。换句话说，我们希望在最终的分配上同时做到统一和一致。对于更简单的服务器集合固定，只更新客户端集合的情况，有大量文献描述相关解决方案，但在本文中，我们讨论的是客户端和服务器可以更新的解决方案任何时候。添加和删??除的完全动态情况。算法我们可以将服务器比作垃圾桶，将客户端比作球，并借用经过充分研究的球到垃圾桶随机过程模型，使用类似于方法的抽象。均匀性目标要求所有箱子包含的球大致等于平均密度（球除以箱子）。对于参数ε，我们将每个垃圾箱的容量设置为最大或平均负载的最大倍数（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的不同值时bin的负载分布。▲不同ε值的载荷分布。对于所有负载范围（从0到(1+ε)倍的平均负载），负载分布几乎是均匀的，许多箱子的负载等于(1+ε)倍的平均负载。我们可以看到这里有个权衡，较小的ε值有利于均匀性但不利于一致性，较大的ε值有利于一致性。较小的ε值可确保许多负载等于(1+ε)乘以平均负载的硬容量限制，而其他负载则按降序分布。在提供内容托管服务时，必须准备好处理许多不同特征的实例。这种一致性哈希方案非常适合这种情况，因为即使在最坏的情况下它也能表现良好。我们内部研究的结果令人兴奋，更令我们高兴的是，更广泛的社区发现我们的解决方案足够有用，可以包含在开源中，从而使任何人都可以使用该算法：https://github.com/arodland/haproxy【本文为栏目组织“GoogleDevelopers”原创稿件，转载请联系原作者（微信公众号：Google_Developers）】点此查看更多本作者好文
