一致性哈希：一个环 + 顺时针找主人
一、技术产生的背景
1997 年，MIT 的研究者 David Karger 等人提出了这个算法，最初是为了解决互联网的"热点问题"——早期的 P2P 网络（如 Chord）和分布式缓存系统需要把海量数据分散到多台机器上。最直觉的做法是：hash(key) % N（N 是机器数量）。
但这有个致命缺陷：只要增减一台机器，N 就变了，几乎所有 key 的归属都变了。
Amazon 的 Dynamo 论文发表后，一致性哈希成了分布式存储的标配，Cassandra、Memcached 客户端（如 ketama）、Redis Cluster（哈希槽是其变种思路）等都在用。
二、想解决的核心问题
分布式系统中机器增减是常态：扩容、宕机、日常运维。如果不解决"取模失效"问题，一台缓存服务器下线就会导致全量缓存失效——所有请求瞬间砸向后端数据库，引发"缓存雪崩"，甚至整个系统连环崩溃。
所以核心诉求是：节点变化时，只影响那一小部分数据，其余数据原地不动。
三、具体实现方案
哈希环
把哈希值空间想象成一个 0 ~ 2³² 的圆环，首尾相接。每台服务器按 IP/名称算哈希，落在环上某个位置；每个 key 也算哈希落在环上。规则很简单：key 顺时针走，遇到的第一个服务器就是它的归属。
类比：环就像一个圆形的餐桌，服务器是坐下的客人，key 是端上来的菜——菜端给顺时针方向第一位客人。
为什么只影响局部（单调性）
新增一台服务器，只"抢走"它和前一台之间那一段环上的 key；删除一台，它的数据顺延给下一个邻居。集群从 N 台变 N+1 台，理论上只有 1/(N+1) 的数据需要迁移，其余全部稳定。
这就是"一致性"的含义——前后一贯。Karger 论文将其形式化为两个性质：
- 平衡性（Balance）：key 尽可能均匀分布到所有节点
- 单调性（Monotonicity）：新增节点时，已有 key 只会迁移到新节点，而不会在旧节点之间搬家
一个常见误区：一致性哈希的重点是 consistent（稳定）而非均衡——% N 取模的均衡性其实很好，差的是稳定性。
虚拟节点
机器少的时候，哈希位置在环上可能很不均匀，某台机器分到大半环导致数据倾斜。更糟的是，节点下线后其负载全部顺延给下一个邻居，特定的下线顺序可能让某台服务器的环段越滚越长。
解决办法是给每台机器起几百个别名（如 node1-1、node1-2……），别名算哈希散布到环上，各自代表真实机器：
- 节点多了，环就均匀了：某台机器下线，它散布在环各处的虚拟节点分别由不同邻居接管，负载被"摊薄"而不是砸给一个倒霉蛋
- 顺带还能按机器性能设权重——性能强的多给几个虚拟节点（如 A:B:C = 5:3:2 的分布）
- 代价极低，只是一个虚拟节点 → 真实节点的映射表
一个需要澄清的细节：真正提供均匀性的是哈希函数（如 MurmurHash），虚拟节点主要改善的是节点变动时的负载再分布——真实节点越少，虚拟节点的作用越关键。
工程细节
- 哈希函数：常用 MurmurHash（分布均匀、速度快、与 Java 原生 hashCode 无关），Cassandra、Jedis 都用它；C 实现中 FNV 也常见
- 查找：有序环 + 二分查找，O(log N) 定位（如 Java 的
TreeMap.tailMap()） - 副本机制：沿环继续走下去，遇到的前几个不同真实节点各存一份（跳过同一物理机的虚拟节点）
- 虚拟节点数量：经验值每节点 100~200 个（Dynamo 论文为 150），过多会拖慢查找
四、后续演进
裸哈希环并非终点。蒙特卡洛模拟显示，5 节点的裸哈希环不均衡比可达 3.67 倍，因此出现了更精细的方案：
- Jump Consistent Hash（Google, 2014）：无内存占用、O(log N)，只把 1/(n+1) 数据移到新桶，超千节点时性能比经典方案快一到两个数量级；缺点是只支持桶编号有序增减
- Rendezvous Hash（HRW）：无需虚拟节点即可做到近乎完美均衡，适合节点数中等、拓扑多变的场景（如分布式缓存选节点）
- Maglev Hash（Google, 2016）：为负载均衡器设计，查找 O(1)、扰动最小，Google 的网络负载均衡就在用
- Redis Cluster 的哈希槽：4096→16384 个固定槽位，本质是把"环"换成"槽"，节点只负责槽的迁移，简化了实现
总结
一致性哈希用"一个环 + 顺时针找主人"的简单设计，把分布式系统最头疼的节点变更从"全量抖动"降到"局部微调"，是 Dynamo、Cassandra 等海量存储系统得以横向扩展的基石。理解它，就理解了几乎所有分布式存储的数据分片起点。
参考资料