一致性哈希算法介绍
1. 一致性哈希在解决什么问题
一致性哈希（Consistent Hashing）通常用于“分布式路由/分片”：把请求或 key 路由到某个后端节点（缓存节点、分片节点、存储节点），并希望在 节点增减 时，尽量减少 key 的迁移。
最经典的对比是“取模分片”：
int idx = hash(key) % N; // N 是节点数
当节点数从 N = 3 扩容到 N = 4 时，几乎所有 key 的 hash(key) % N 都会变化，导致：
- 缓存场景：命中率瞬间下降，出现“缓存雪崩式回源”。
- 存储分片：迁移量巨大，搬迁时间长、成本高。
一致性哈希的目标就是：节点变化时，只让一小部分 key 重新映射。
2. 核心思想：把节点与 key 映射到同一个哈希环
2.1 哈希环（Hash Ring）
把哈希值空间 [0, 2^m) 看成一个首尾相接的环（常见用 m = 32 或 m = 64）。对任意输入做哈希后，落在环上的某个点。
0 -------------------------------> 2^m - 1
^ |
| v
+----------------------------------+
2.2 节点与 key 的映射
- 对每个节点（例如
10.0.0.1:6379）计算hash(nodeId)，得到它在环上的位置。 - 对每个 key 计算
hash(key)，得到它在环上的位置。
2.3 路由规则：顺时针第一个节点
一个 key 归属到“从 key 的位置开始，顺时针遇到的第一个节点”。如果顺时针走到环末尾都没遇到节点，则回到 0 继续（wrap around）。
这一规则的工程实现通常是：把所有节点位置放到一个有序结构里（排序数组或 TreeMap），对 hash(key) 做一次“后继查询”（lower_bound / ceiling）。
2.4 最小迁移性质（关键结论）
当新增一个节点 X：
- 只有落在区间
(prev(X), X]上的 key 会被迁移到X。 - 其他区间的 key 仍然映射到原来的节点，不受影响。
在节点在环上均匀分布的理想情况下，新增 1 个节点到 n 个节点的集群，期望迁移比例约为 1 / (n + 1)；删除 1 个节点的迁移比例约为 1 / n。
3. 虚拟节点：解决负载不均与支持权重
仅靠物理节点上环会有两个常见问题：
- 节点少时分布不均：某个节点可能“管辖”一段很长的环区间，导致热点倾斜。
- 节点异构：机器配置不同，希望容量大的机器承担更多 key。
3.1 虚拟节点（Virtual Node, vnode）怎么做
把一个物理节点拆成多个虚拟节点，每个虚拟节点在环上占一个位置：
- 物理节点：
10.0.0.1:6379 - 虚拟节点：
10.0.0.1:6379#0、10.0.0.1:6379#1、...、10.0.0.1:6379#k
key 先路由到某个虚拟节点，再映射回对应的物理节点。虚拟节点数量越多，环上的切分越细，负载越均匀，但元数据也越大。
3.2 权重（Weight）如何表达
权重最常见的工程做法是：按权重比例分配虚拟节点数。
- 机器 A 权重 2，机器 B 权重 1。
- 给 A 分配
2 * vnodesPerWeight个 vnode，给 B 分配1 * vnodesPerWeight个 vnode。
这样 A 在环上占据更多位置，期望分到更多 key。
4. 工程实现：数据结构、查找与一致性
4.1 数据结构选择
典型实现是“环 = 有序映射”：
- key：虚拟节点的哈希值（
long/int）。 - value：虚拟节点（或其物理节点引用）。
常见选择：
- Java：
TreeMap<Long, Node>，用ceilingEntry找后继节点。 - Go：排序数组 +
sort.Search二分查找（更省内存）。
查找复杂度通常为 O(log V)，V 是虚拟节点总数。
4.2 最小可复现代码：环查找
import java.util.NavigableMap;
import java.util.TreeMap;
public class ConsistentHashRing<T> {
private final NavigableMap<Long, T> ring = new TreeMap<>();
public void addNode(long hash, T node) {
ring.put(hash, node);
}
public T route(long keyHash) {
if (ring.isEmpty()) {
return null;
}
var entry = ring.ceilingEntry(keyHash);
if (entry == null) {
entry = ring.firstEntry(); // 注意：环回绕
}
return entry.getValue();
}
}
要点：
ceilingEntry对应“顺时针第一个节点”。null时回到firstEntry()，对应环回绕。
4.3 哈希函数的选择与一致性约束
一致性哈希最怕“不同客户端算出来的哈希不一致”，常见坑：
- 直接用语言内置
hashCode()：跨语言、跨版本或不同 JVM 参数下可能不稳定。 - 不统一字符编码：
UTF-8与其他编码会导致哈希输入字节序列不同。 - 哈希位数不足：碰撞过多会导致分布偏斜与不可解释的路由抖动。
工程建议：
- 统一哈希算法与输入编码（通常用
UTF-8）。 - 使用分布更均匀的非加密哈希（例如 MurmurHash、xxHash）。
- 使用
64位哈希值可降低碰撞概率（环空间更大）。
4.4 节点变更与并发安全
环是“路由规则的真相”，更新环时要保证读写一致：
- 典型做法：构建新 ring（copy-on-write），用原子引用一次性替换，读路径无锁。
- 或者：读写锁保护 ring，但会把锁竞争引入高频路由路径。
还要考虑节点抖动（频繁上下线）带来的反复迁移，工程上通常需要“健康检查稳定后再摘除/加入”的抖动抑制策略。
5. 与其他路由方案对比
| 方案 | 节点增减迁移量 | 是否易做权重 | 客户端是否需要全局视图 | 典型场景 |
|---|---|---|---|---|
取模分片 hash % N |
高（几乎全量） | 一般 | 是（知道 N） | 节点数固定、很少扩缩容 |
| 一致性哈希（环） | 低（局部区间） | 易（vnode 数量） | 是（知道 ring） | 客户端分片、缓存路由 |
| Rendezvous Hash（HRW） | 低（局部） | 易（带权打分） | 是（知道节点列表） | 路由决策、负载均衡 |
| Hash Slot（固定分桶） | 中（按桶迁移） | 易（桶分配） | 可选（由代理/集群协调） | Redis Cluster、Codis 类分片 |
理解上可以把“Hash Slot”看作一致性哈希的工程化变体：先把 key 映射到固定数量的桶（例如 16384 个 slot），再把桶迁移/分配到节点上，从而让迁移粒度可控、易于运维。
6. 典型应用场景与注意事项
- 客户端分片缓存：Memcached、Redis 多实例（非 Cluster）场景下，客户端用一致性哈希把 key 路由到不同实例。
- 分布式存储路由：把对象或分区路由到节点，扩容时减少搬迁。
- 负载均衡中的会话粘性：同一来源（或同一会话 key）尽量落到同一节点。
注意：Redis Cluster 本身采用的是 hash slot（CRC16(key) % 16384）而不是一致性哈希环；一致性哈希更多出现在“客户端分片”或“代理分片”方案里。
7. 常见坑与最佳实践
- 虚拟节点太少：分布不均导致热点倾斜；适当增加 vnode 数量提升平滑性。
- 热 key 问题：一致性哈希解决的是“分布与迁移”，不解决“单 key 过热”；热 key 仍需拆分、局部缓存、多副本读等手段。
- 节点故障处理：仅靠一致性哈希只是在“路由”层换了落点，数据副本与故障切换仍需额外机制。
- 迁移成本评估：新增/下线节点会触发 key 迁移（缓存回源、数据搬迁），需要结合业务峰谷做节奏控制。