什么是一致性 Hash 算法？

约 1754 字大约 6 分钟

2024-10-16

"一致性 Hash" 似乎是一个具有迷惑性的名字，因为 Hash 函数的结果不管在哪里计算都应该是一样的，为什么会存在一致性的问题？其实我们提出一致性 Hash 这个概念是为了解决分布式存储中的问题。在分布式存储中不同的机器会存储不同的对象的数据，我们使用 Hash 函数来建立数据到服务器之间的映射关系。那么为什么会存在 "不一致" 呢？

Hash 的不一致是指什么？

我们考虑这样一个分布式存储的场景：

现在需要将 10 个数据 $D_1, D_2, \dots, D_{10}$ 存放到 3 个机器节点( $M_0, M_1, M_2$ )上。我们当然可以使用一个映射表来维护数据和机器之间的映射关系，但是那样意味着我们需要额外存储一个表，而且必须不断维护它。甚至这个表可能会随着数据的增加会存储不下。那么我们自然会想到使用一个 Hash 函数来计算数据和机器节点之间的映射，于是我们有了以下这个公式：

m = hash(o) \ \ mod \ \ n

其中 $o$ 为数据对象的名称， $n$ 为机器的数量， $m$ 为计算出存储对象的机器节点编号。

根据这个公式我们很容易得到以下映射：

机器编号	数据
0	$D_3, D_6, D_9$
1	$D_1, D_4, D_7, D_{10}$
2	$D_2, D_5, D_8$

表 1

如果我们此时增加一个机器， $n = 4$ 后，可以重新计算得出映射：

机器编号	数据
0	$D_4, D_8$
1	$D_1, D_5, D_9$
2	$D_2, D_6, D_{10}$
3	$D_3, D_7$

表 2

很显然，除了 $D_1, D_2$ 没有改变机器节点以外，其他所有的数据都变更了存储机器。这意味着当存储集群中增加一个机器节点时会造成大量的数据迁移，这无疑给网络和磁盘增加了许多压力，严重情况下也可能导致数据库的宕机。

所以 Hash 的一致性并不是指 Hash 函数重复计算之后结果不一致，而是这种计算导致了数据的迁移。那么我们有没有可能减少这种数据的迁移呢？可以的，一致性 Hash 算法可以保证当机器节点增加或者减少时，节点之间的数据迁移只限于两个节点之间，而不会造成全局的网络问题。

一致性 Hash 的使用场景

一致性 Hash 算法是分布式系统中非常重要的算法，主要运用在：

负载均衡。
缓存数据分区。
分布式关系型数据库节点映射。
RPC 框架 Duddo 用来选择服务提供者。

算法实现

整个算法主要是将 Hash 值空间转移到一个环状的虚拟空间上，然后再对机器节点和数据进行映射。我们就根据前文提到的数据与机器节点映射的例子具体来看一下实现的过程：

创建 Hash 环。不同于一般 Hash 函数将数据映射到一个线性的空间，我们考虑将 Hash 值空间映射成一个虚拟的环状空间。如果整个 Hash 空间的取值为： $0 \sim 2^{32}-1$ ，那么我们按照顺时针排列，让最后一个节点 $2^{32}-1$ 在开始位置 0 重合。
环状 Hash 空间
将数据映射到 Hash 环上。假设现在有 4 个数据对象 $o_1, o_2, o_3, o_4$ ，分别对其计算 Hash 值，得到结果 $m_1, m_2, m_3, m_4$ 。将这四个结果放置到 Hash 环上。
数据对象映射到 Hash 环上
将服务器映射到 Hash 环上。对 3 台服务器 $c_1, c_2, c_3$ 的 IP 地址进行 Hash 计算，对 Hash 值进行 $2^{32}$ 取模，得到一个取值在 $0 \sim 2^{32}-1$ 的整数 $t_1, t_2, t_3$ 。将取模后的整数映射在 Hash 环上。
机器节点映射到 Hash 环上
为数据选择存储的机器节点。每个数据对象都按照顺时针方向选择离自己最近的机器进行存储。
数据对象选取机器节点