一致性哈希

定义

一致性哈希(Consistent Hashing)是一种特殊的哈希算法,由 David Karger 等人于 1997 年在 MIT 提出,最初用于解决分布式缓存的热点问题。它的核心目标是:当集群中节点数量变化时,只有少部分键需要重新映射,而传统的取模哈希(hash mod N)在节点变动时几乎所有键都会失效。

原理

算法将整个哈希值空间组织成一个首尾相接的环(通常为 0 到 2^32-1)。节点和数据键都通过哈希函数映射到环上的某个位置,每个键沿顺时针方向找到的第一个节点即为其归属节点。当新增或移除一个节点时,只影响环上相邻区段的数据,其余键的映射保持不变。

为避免节点在环上分布不均导致负载倾斜,实际实现中通常引入虚拟节点:每个物理节点映射为环上的多个虚拟位置,使数据分布更均匀,也便于按机器性能分配不同权重。

应用场景

• 分布式缓存:Memcached 客户端分片、Redis 集群方案
• 分布式存储:Amazon Dynamo、Cassandra 等采用其变体做数据分区
• 负载均衡:将同一用户的请求稳定路由到同一后端

优缺点

优点是扩缩容代价小、无需中心化的映射表;缺点是原始形态存在负载不均问题(需虚拟节点缓解),且相比范围分片,难以支持高效的范围查询。