五、设计一致哈希

为了实现水平扩展，在服务器之间高效、均匀地分配请求/数据非常重要。一致哈希是实现这一目标的常用技术。但首先，让我们深入研究一下这个问题。

老调重弹问题

如果你有 n 个缓存服务器，平衡负载的一个常用方法是使用下面的哈希方法:

server index = hash(key)% N，其中 N 是服务器池的大小。

让我们用一个例子来说明它是如何工作的。如表 5-1 所示，我们有 4 台服务器和 8 个带哈希的字符串键。

A screenshot of a cell phone Description automatically generated

为了获取存储密钥的服务器，我们执行模块化操作 f(key) % 4 。例如， hash(key0) % 4 = 1 表示客户端必须联系服务器 1 来获取缓存的数据。图 5-1 显示了基于表 5-1 的键的分布。

A close up of text on a white background Description automatically generated

当服务器池的大小固定且数据分布均匀时，这种方法非常有效。然而，当添加新的服务器或者移除现有的服务器时，问题出现。例如，如果服务器 1 脱机，服务器池的大小将变为 3。使用相同的哈希函数，我们得到一个键的相同哈希值。但是应用模运算给了我们不同的服务器索引，因为服务器的数量减少了 1。我们应用 hash % 3 : 得到如表 5-2 所示的结果

A screenshot of a cell phone Description automatically generated

图 5-2 显示了基于表 5-2 的新的密钥分布。

A screenshot of a cell phone Description automatically generated

如图 5-2 所示，大部分的键都是重新分配的，而不仅仅是原来存储在离线服务器(服务器 1)中的那些。这意味着当服务器 1 离线时，大多数缓存客户端将连接到错误的服务器来获取数据。这导致了高速缓存未命中的风暴。一致哈希是缓解这一问题的有效技术。

一致哈希

引自维基百科:“一致哈希是一种特殊的哈希，当哈希表重新调整大小并使用一致哈希时，平均只有k/n个键需要重新映射，其中 k 是键的数量，n 是槽的数量。相反，在大多数传统哈希表中，数组槽数量的变化会导致几乎所有的键被重新映射[1]”。

哈希空间和哈希环

现在我们了解了一致性哈希的定义，让我们看看它是如何工作的。假设 SHA-1 作为哈希函数 f，哈希函数的输出范围为 : x0，x1，x2，x3，…，xn 。在密码学中，SHA-1 的哈希空间从 0 到 2^160 - 1。这意味着 x0 对应于 0， xn 对应于 2^160 - 1，中间的所有其他哈希值落在 0 和 2^160-1 之间。图 5-3 显示了哈希空间。

A close up of a logo Description automatically generated

通过连接两端，我们得到一个哈希环如图图 5-4 :

A close up of a lamp Description automatically generated

哈希服务器

使用相同的哈希函数 f ，我们基于服务器 IP 或名称将服务器映射到环上。图 5-5 显示了 4 个服务器被映射到哈希环上。

A necklace on a table Description automatically generated

哈希键

值得一提的是，这里使用的 hash 函数与“重哈希问题”中的不同，没有模运算。如图 5-6 所示，4 个缓存键(key0、key1、key2 和 key3)被哈希到哈希环上

A close up of a necklace Description automatically generated

服务器查找

为了确定一个密钥存储在哪个服务器上，我们从环上的密钥位置开始顺时针旋转，直到找到一个服务器。图 5-7 解释了这个过程。顺时针转动，键 0 存储在服务器 0 上； key1 存储在服务器 1 上； key2 存储在服务器 2 和 key3 存储在服务器 3 。

A necklace hanging on a wall Description automatically generated

添加服务器

使用上述逻辑，添加新的服务器将只需要重新分发一小部分密钥。

在图 5-8 中，增加了一个新的服务器 4 后，只有 key0 需要重新分配。 k1、k2、和 k3 保持在相同的服务器上。让我们仔细看看其中的逻辑。在添加服务器 4 之前， key0 存储在服务器 0 上。现在， key0 将被存储在 server 4 上，因为 server 4 是它从 key0 在环上的位置顺时针方向遇到的第一个服务器。其他密钥不会基于一致的哈希算法进行重新分配。

A picture containing necklace Description automatically generated

移除一个服务器

当服务器被移除时，只有一小部分密钥需要用一致的哈希法重新分配。在图 5-9 中，当服务器 1 被移除后，只有 key1 必须重新映射到服务器 2 。其余的键不受影响。

A picture containing necklace Description automatically generated

两个问题的基本处理方法

一致性哈希算法是由 Karger 等人在麻省理工学院提出的[1]。基本步骤是:

使用均匀分布的哈希函数将服务器和密钥映射到环上。

要找出一个密钥映射到哪个服务器，从密钥位置开始顺时针方向走，直到找到环上的第一个服务器。

这种方法发现了两个问题。首先，考虑到可以添加或移除服务器，不可能为环上的所有服务器保持相同大小的分区。分区是相邻服务器之间的哈希空间。分配给每个服务器的环上的分区的大小可能非常小或相当大。在图 5-10 中，如果去掉 s1 ， s2 的分区(用双向箭头突出显示)是 s0 和 s3 的分区的两倍。

A close up of a necklace Description automatically generated

第二，环上可能有不均匀的密钥分布。例如，如果服务器被映射到图 5-11 中列出的位置，那么大部分密钥都存储在服务器 2 上。但是服务器 1服务器 3 没有数据。

A necklace with a piece of paper Description automatically generated

一种叫做虚拟节点或副本的技术被用来解决这些问题。

虚拟节点

虚拟节点是指真实节点，每个服务器由环上的多个虚拟节点表示。在图 5-12 中，服务器 0 和服务器 1 都有 3 个虚拟节点。3 是任意选择的；而在现实世界的系统中，虚拟节点的数量要大得多。我们没有用 s0 ，而是用 s0_0，s0_1 ，s0_2 来代表环上的服务器 0 。同样， s1_0，s1_1 ，和 s1_2 代表环上的服务器 1。对于虚拟节点，每台服务器负责多个分区。标签为 s0 的分区(边缘)由服务器 0 管理。另一方面，标签为 s1 的分区由服务器 1 管理。

A necklace looking at the camera Description automatically generated

为了找到一个密钥存储在哪个服务器上，我们从密钥的位置开始顺时针方向，找到环上遇到的第一个虚拟节点。在图 5-13 中，为了找出 k0 存储在哪个服务器上，我们从 k0 的位置顺时针方向，找到虚拟节点 s1_1 ，它指的是服务器 1 。

A picture containing accessory, necklace, table, phone Description automatically generated

随着虚拟节点数量的增加，键的分布变得更加均衡。这是因为虚拟节点越多，标准偏差就越小，从而导致平衡的数据分布。标准差衡量数据是如何分布的。online research [2]进行的实验结果显示，对于一个或两百个虚拟节点，标准偏差在平均值的 5% (200 个虚拟节点)和 10% (100 个虚拟节点)之间。当我们增加虚拟节点的数量时，标准偏差会更小。然而，需要更多的空间来存储关于虚拟节点的数据。这是一种权衡，我们可以调整虚拟节点的数量来适应我们的系统需求。