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 步:
- 节点映射
通过相同的哈希函数,我们可以基于服务器的 IP 地址或名称,将服务器映射到哈希环上:
- 数据映射
类似地,客户端请求的哈希值也会映射到哈希环上的某个位置:
- 确定服务器
要确定某个请求由哪个服务器处理,我们从请求的哈希值出发,沿顺时针方向找到第一个服务器的哈希值: 要确定某个数据存放在哪个服务器上,数据将按顺时针方向定位到第一个大于或等于其哈希值的节点。例如,节点 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 网络负载均衡器