Skip to content

什么是一致性 Hash 算法?

1796字约6分钟

大数据分布式

2024-10-16

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

Hash 的不一致是指什么?

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

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

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

其中 oo 为数据对象的名称, nn 为机器的数量, mm 为计算出存储对象的机器节点编号.

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

机器编号数据
0D3,D6,D9D_3, D_6, D_9
1D1,D4,D7,D10D_1, D_4, D_7, D_{10}
2D2,D5,D8D_2, D_5, D_8

表 1

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

机器编号数据
0D4,D8D_4, D_8
1D1,D5,D9D_1, D_5, D_9
2D2,D6,D10D_2, D_6, D_{10}
3D3,D7D_3, D_7

表 2

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

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

一致性 Hash 的使用场景

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

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

算法实现

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

  1. 创建 Hash 环. 不同于一般 Hash 函数将数据映射到一个线性的空间, 我们考虑将 Hash 值空间映射成一个虚拟的环状空间. 如果整个 Hash 空间的取值为: 023210 \sim 2^{32}-1, 那么我们按照顺时针排列, 让最后一个节点 23212^{32}-1 在开始位置 0 重合.

    环状 Hash 空间
    环状 Hash 空间
  2. 将数据映射到 Hash 环上. 假设现在有 4 个数据对象 o1,o2,o3,o4o_1, o_2, o_3, o_4, 分别对其计算 Hash 值, 得到结果 m1,m2,m3,m4m_1, m_2, m_3, m_4. 将这四个结果放置到 Hash 环上.

    数据对象映射到 Hash 环上
    数据对象映射到 Hash 环上
  3. 将服务器映射到 Hash 环上. 对 3 台服务器 c1,c2,c3c_1, c_2, c_3 的 IP 地址进行 Hash 计算, 对 Hash 值进行 2322^{32} 取模, 得到一个取值在 023210 \sim 2^{32}-1 的整数 t1,t2,t3t_1, t_2, t_3. 将取模后的整数映射在 Hash 环上.

    机器节点映射到 Hash 环上
    机器节点映射到 Hash 环上
  4. 为数据选择存储的机器节点. 每个数据对象都按照顺时针方向选择离自己最近的机器进行存储.

    数据对象选取机器节点
    数据对象选取机器节点

以上我们就完成了整个一致性 Hash 算法的计算过程. 接下来我们分别看一下对于文章开始提到的两个场景: 增加机器节点 和 删减机器节点中数据和机器之间的映射会发生哪些改变.

增加机器节点

现在增加一台机器 c4c_4, Hash 值取模后得到整数 t4t_4, 将其加入 Hash 环.

增加机器节点后的 Hash 环
增加机器节点后的 Hash 环

可以看到不同于表 1 和表 2 中大量数据需要变更机器节点的情况, 现在我们只需要变更一个数据对象 o4o_4, 将其从 t3t_3 重新分配至 t4t_4.

减少机器节点

同样, 如果我们减少一台机器 c1c_1, 重新分配机器后发现, 只有对象 o2o_2 被重新分配到了 c3c_3, 而其他的数据无需变动.

减少机器节点后的 Hash 环
减少机器节点后的 Hash 环

可能遇到的问题

负载不均衡.

这是一致性 Hash 很容易遇到的一个问题. 通常来说我们希望数据均匀地分布在所有机器上, 包括增加或删除机器之后. 但是观察之前提到的增加节点的例子, 增加机器 c4c_4 之后, 仅仅分担了 c2c_2 的压力. 我们可以想象, 如果再一次增加节点 c5c_5, 不幸新的节点的 Hash 值又一次地落在了 t4t_4t2t_2 之间, 那么新增的节点分配不到任何数据. 可见新增机器节点未必一定能减轻数据负载的压力.

那么该如何解决呢?

解决方案: 虚拟节点

还是沿用上述的例子: 对于机器 c1,c2,c3c_1, c_2, c_3 来说, 除了直接映射到 Hash 环上形成三个节点外, 每个节点还额外拥有两个虚拟节点. 当虚拟节点越多, 也就意味着数据在机器上分布得越均匀.

Hash 环加入虚拟节点后
Hash 环加入虚拟节点后

你可以理解为我们又增加了一层虚拟机器节点到实际机器节点的映射.

总结

一致性 Hash 算法解决了分布式环境下机器增加或者减少时, 简单的取模运算无法获取较高命中率的问题.

通过虚拟节点的使用, 一致性 Hash 算法可以均匀分担机器的负载, 使得这一算法更具现实的意义.

变更历史

最后更新于: 查看全部变更历史
  • docs: update docs

    于 2024/12/3
  • docs: update docs

    于 2024/11/25
  • docs: update docs

    于 2024/11/19
  • 整理图片和文章

    于 2024/11/7
  • 整理tag

    于 2024/11/4
  • update

    于 2024/10/31
  • 新增文字+CRLF全部替换为LF

    于 2024/10/17
  • 更改头图

    于 2024/10/16
  • 新增文章

    于 2024/10/16

Keep It Simple