跳至主要內容

5. 设计一致性哈希


5. 设计一致性哈希

在实现水平扩展时,高效地将请求分配到不同服务器是非常重要的。一致性哈希(Consistent Hashing)是一种常用的方法,可以有效解决这个问题。

重哈希问题

一种简单的请求分配方式是通过以下哈希+取模公式来确定服务器:

serverIndex = hash(key) % N,其中 N 是服务器的数量

这种方法可以使请求均匀分布到所有服务器。然而,当有新服务器加入或现有服务器移除时,上述公式的结果会发生很大变化,导致大量请求被重新分配到不同的服务器。

这种现象会引起大量缓存失效,因为客户端连接到新的服务器实例,需要重新从缓存中加载用户数据。

一致性哈希的基本思想

为了解决这个问题,一致性哈希应运而生。它在 1997 年由麻省理工学院的 Karger 等人在论文 "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web" 中首次提出。

一致性哈希的核心思想是:固定哈希值的范围为 2^32,将哈希算法的所有可能键空间可视化为一个首尾相连的环,称为哈希环(Hash Ring)。

一致性哈希算法包括以下 3 步:

  1. 节点映射

通过相同的哈希函数,我们可以基于服务器的 IP 地址或名称,将服务器映射到哈希环上:

服务器哈希
服务器哈希
  1. 数据映射

类似地,客户端请求的哈希值也会映射到哈希环上的某个位置:

请求键哈希
请求键哈希
  1. 确定服务器

要确定某个请求由哪个服务器处理,我们从请求的哈希值出发,沿顺时针方向找到第一个服务器的哈希值: 要确定某个数据存放在哪个服务器上,数据将按顺时针方向定位到第一个大于或等于其哈希值的节点。例如,节点 k0 按顺时针方向映射至节点 s0。

服务器查找
服务器查找

添加服务器

当添加新服务器时,通过该方法,只有一部分请求会重新分配到新的服务器。

如图中,当新增节点 s4 时,只有顺时针方向上第一个节点 k0 的数据需要从 s0 搬移到 s4 ,而其他节点的数据映射关系保持不变。

添加服务器场景
添加服务器场景

移除服务器

同样地,当移除某个服务器时,也只有一部分请求会被重新分配到其他服务器。

如图中,当移除节点 s1 时,只有节点 k1 的数据需要从 s1 搬移到 s2 ,而其他节点的数据映射关系保持不变。

移除服务器场景
移除服务器场景

通过这种方式,一致性哈希算法显著降低了扩容或缩容时的数据迁移量。

虚拟节点的引入

尽管一致性哈希算法降低了迁移成本,但节点在哈希环上的分布可能并不均匀,导致某些节点负载过重。

  • 问题 1:使用基本方法,哈希分区可能在服务器之间分布不均;
  • 问题 2:由于哈希分区不均,可能导致请求负载也分布不均;

例如,若节点 A、B 和 C 的位置集中在哈希环的一侧,则大量请求会集中到节点 A。

为了解决上述问题,我们可以在哈希环上为每台服务器映射多个虚拟节点(Virtual Nodes),从而为每台服务器分配多个分区:

具体而言,每个真实节点对应多个虚拟节点,这些虚拟节点分布在哈希环上,并将虚拟节点映射到实际节点。例如,为每个真实节点生成 3 个虚拟节点:

  • A-01、A-02、A-03 对应节点 A;
  • B-01、B-02、B-03 对应节点 B;
  • C-01、C-02、C-03 对应节点 C。

引入虚拟节点后,原本哈希环上只有 3 个节点的情况,就会变成有 9 个虚拟节点映射到哈希环上,哈希环上的节点数量多了 3 倍。这时候,如果有访问请求寻址到「A-01」这个虚拟节点,接着再通过「A-01」虚拟节点找到真实节点 A,这样请求就能访问到真实节点 A 了。

通过虚拟节点的引入,节点在哈希环上的分布更加均匀,大大提高了系统的负载均衡能力。

虚拟节点的数量越多,请求的分布越均匀。

实验表明,创建 100-200 个虚拟节点时,标准偏差可以控制在 5-10% 的范围内。

此外,虚拟节点还提升了系统的稳定性。例如,当节点 A 被移除时,对应的虚拟节点被顺时针相邻的多个节点分担,避免了单点压力骤增。

一致性哈希的优势

  • 在重新平衡(Rebalancing)时,只有极少数的键需要重新分配。
  • 数据均匀分布,易于水平扩展。
  • 热点问题得到缓解,例如对于名人相关数据的频繁访问,由于数据的均匀分布,负载不会集中到单一服务器。

一致性哈希的实际应用

以下是一些一致性哈希的真实案例:

  • Amazon DynamoDB 的分区组件
  • Cassandra 的数据分区
  • Discord 的聊天应用程序
  • Akamai CDN
  • Maglev 网络负载均衡器