我们可以将服务器比作垃圾桶，将客户端比作球，并借鉴将球随机投入垃圾桶的过程 (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
