PZY

Enjoy software architecture and programming

08 Sep 2022

具有负载边界的一致性哈希[译文]

运行大规模 Web 服务(如内容托管),必然需要负载均衡 —— 将大量客户端(流量)均匀地分发到众多服务器上,以避免出现某台服务器过载。此外,在客户端和服务器都可以随时添加或删除的动态环境中,期望仍能找到一种不随时间波动很大的负载分配策略。换句话说,我们需要将服务器的得到的客户端(流量)分配,随着时间的推移保持一致性。

背景

虽然过去已经演变出一致性哈希的概念来处理动态环境中的负载均衡,但所有先前开发的方案的一个根本问题是,在某些场景下,它们也许会导致许多服务器上的负载均衡不理想。

此外,客户端和服务器都可能会定期添加或删除,并且通过此类更改,我们不希望移动太多客户端。 因此,尽管动态分配算法必须始终确保适当的负载均衡,但它还应该旨在最大限度地减少每次更改系统后移动的客户端数量。 当我们面临对每台服务器容量的硬性限制时,这种分配问题变得更加具有挑战性 —— 也就是说,每台服务器都有一个负载不得超限的容量。 通常情况下,我们希望容量接近平均负载。

换句话说,我们期望同时实现结果分配的统一性和一致性。 在服务器集群是固定的,只有客户端集群被更新的较简单的情况下,有大量的文献介绍了解决方案,但在本文中,我们讨论的解决方案,是在客户端和服务器都可以被添加和删除的完全动态场景下。

算法

我们可以把服务器看成是桶,把客户端看成是球,类似于经过充分研究的 balls-to-bins 随机过程中的符号。均匀性目标是追求所有桶的负载大致等于平均负载(球的数量除以桶的数量)。对于某个参数 ε,我们设置每个桶的容量为平均加载时间(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+ε)倍的硬性容量限制,其余负载则具有衰减分布。

在提供内容托管服务时,必须准备好面对各种具有不同特征的实例。这种一致的哈希方案是这种情况的理想选择,因为它即使在最坏的情况下也表现良好。

虽然我们的内部结果令人振奋,但我们更高兴的是,更广泛的社区发现我们的解决方案足够有用,可以开放源代码,允许任何人使用该算法。 如果您对这项研究的更多细节感兴趣,请参阅 ArXiv 上的论文,并请继续关注 算法与优化团队的更多研究!

本文摘译自:Consistent Hashing with Bounded Loads