02.10.3 一致性哈希与分片
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.10 设计类与手写题
覆盖范围
- 一致性哈希环原理与虚拟节点
- 数据倾斜与扩缩容迁移量
- Jump Consistent Hash
- 普通取模与一致性哈希对比
高频题速览
| 编号 | 题目 | 难度 | 频率 |
|---|---|---|---|
| 02.10.3-001 | 一致性哈希环原理 | 基础 | ★★★★★ |
| 02.10.3-002 | 虚拟节点解决数据倾斜 | 基础 | ★★★★★ |
| 02.10.3-003 | 扩缩容时迁移量计算 | 进阶 | ★★★★ |
| 02.10.3-004 | 普通取模 vs 一致性哈希 | 基础 | ★★★★ |
| 02.10.3-005 | Jump Consistent Hash 原理 | 高级 | ★★★ |
| 02.10.3-006 | 一致性哈希缓存预热 | 进阶 | ★★★ |
| 02.10.3-007 | 数据倾斜与负载均衡 | 进阶 | ★★★★ |
| 02.10.3-008 | 分片策略怎么选 | 进阶 | ★★★★ |
02.10.3-001 一致性哈希环原理
频率 ★★★★★ | 难度 基础
一句话结论
把哈希值空间(如 0~2^32-1)组织成首尾相接的环;节点和 key 都哈希到环上,key 顺时针找到第一个节点即为归属;扩缩容只影响相邻区间的 key。
概念解释
- 环:哈希值空间首尾相接。
- 节点哈希:服务器节点也哈希到环上。
- key 归属:顺时针找第一个节点。
- 扩缩容:新增/删除节点只影响该节点与前一个节点之间的 key。
原理流程
- 把节点 A、B、C 哈希到环上。
- key k 哈希到环上某位置。
- 从 k 顺时针走,遇到的第一个节点就是 k 的归属。
- 新增节点 D,只迁移 D 与前一节点之间的 key。
代码 / 示例
class ConsistentHash {
private final TreeMap<Integer, String> ring = new TreeMap<>();
private final List<String> nodes;
ConsistentHash(List<String> nodes) {
this.nodes = nodes;
for (String n : nodes) ring.put(n.hashCode(), n);
}
String getNode(String key) {
int h = key.hashCode();
Map.Entry<Integer, String> e = ring.ceilingEntry(h);
return e == null ? ring.firstEntry().getValue() : e.getValue();
}
}
常见误区
- 误区:key 和节点用不同哈希函数;正解:同一哈希函数才能在环上比较位置。
- 误区:ceilingEntry 找不到返回 null 时返回 null;正解:环是循环的,找不到则回绕到 firstEntry。
追问 / 延伸
- Q:环大小多少合适? A:通常 2^32 或 2^160,越大分布越均匀。
- Q:为什么不用数组排序? A:TreeMap/有序集合支持 O(log n) 查找,数组二分也行但插入删除慢。
02.10.3-002 虚拟节点解决数据倾斜
频率 ★★★★★ | 难度 基础
一句话结论
一个物理节点对应环上多个虚拟节点(如 150 个),key 哈希到虚拟节点再映射到物理节点;虚拟节点越多,各物理节点在环上的分布越均匀,数据倾斜越小。
概念解释
- 真实节点:物理服务器。
- 虚拟节点:真实节点的副本,哈希到环上多个位置。
- 映射:key -> 虚拟节点 -> 真实节点。
- 倾斜:节点少时环上位置不均匀,某些节点区间大。
原理流程
- 每个真实节点拆成 N 个虚拟节点,如 node#0、node#1、...、node#N。
- 所有虚拟节点哈希到环上。
- key 顺时针找虚拟节点,再映射回真实节点。
- 虚拟节点越多,分布越均匀。
代码 / 示例
class ConsistentHashWithVNodes {
private final TreeMap<Integer, String> ring = new TreeMap<>();
private final int vnodes;
private final Map<String, List<String>> realToV = new HashMap<>();
ConsistentHashWithVNodes(List<String> realNodes, int vnodes) {
this.vnodes = vnodes;
for (String rn : realNodes) addNode(rn);
}
void addNode(String rn) {
List<String> vs = new ArrayList<>();
for (int i = 0; i < vnodes; i++) {
String vn = rn + "#" + i;
ring.put(vn.hashCode(), vn);
vs.add(vn);
}
realToV.put(rn, vs);
}
String getRealNode(String key) {
Map.Entry<Integer, String> e = ring.ceilingEntry(key.hashCode());
String vn = e == null ? ring.firstEntry().getValue() : e.getValue();
return vn.substring(0, vn.lastIndexOf('#'));
}
}
常见误区
- 误区:虚拟节点越多越好;正解:虚拟节点多内存开销大(每个虚拟节点一个 TreeMap 条目),通常 150~200 足够。
- 误区:虚拟节点哈希用相同字符串;正解:必须带后缀(#0、#1)才能哈希到不同位置。
追问 / 延伸
- Q:虚拟节点数怎么定? A:经验值 100~200,节点少时可更多。
- Q:删除真实节点怎么迁移? A:删除其所有虚拟节点,受影响的 key 重新顺时针找下一节点。
02.10.3-003 扩缩容时迁移量计算
频率 ★★★★ | 难度 进阶
一句话结论
普通取模 hash(key) % N,N 变化时几乎所有 key 都要重新映射(迁移 ~100%);一致性哈希 N 变化时只迁移 1/N 的 key(新增节点从下一节点抢 1/N,删除节点其全部 key 迁到下一节点)。
概念解释
- 取模:N 变了,hash(key) % N 几乎全变。
- 一致性哈希:新增节点 D,只从下一节点 B 抢 D 与 B 之间的 key,约 1/N。
- 删除节点:该节点所有 key 迁到下一节点,约 1/N。
原理流程
- 取模:N 台服务器,key 映射到
hash(key) % N。 - 从 N 加到 N+1:约 N/(N+1) 的 key 迁移。
- 一致性哈希:新增一台,只迁移 1/(N+1) 的 key。
- 删除一台:1/N 的 key 迁移。
代码 / 图示
取模:N=4 -> N=5
迁移量 ≈ 1 - 4/5 = 80%
一致性哈希:N=4 -> N=5
迁移量 ≈ 1/5 = 20%
常见误区
- 误区:一致性哈希扩缩容零迁移;正解:只迁移 1/N,不是零。
- 误区:删除节点迁移量和新增一样;正解:删除节点时该节点所有 key 都迁到下一节点,也是 1/N。
追问 / 延伸
- Q:为什么取模迁移量大? A:因为
hash % N和hash % (N+1)之间没有连续关系。 - Q:数据库分库分表怎么迁移? A:一致性哈希减少迁移量,但实际分库常用范围分片或哈希取模后双写迁移。
02.10.3-004 普通取模 vs 一致性哈希
频率 ★★★★ | 难度 基础
一句话结论
普通取模 hash(key) % N 实现简单但扩缩容迁移量大;一致性哈希扩缩容迁移量小(1/N),但实现复杂且有虚拟节点开销;静态场景用取模,动态扩缩容场景用一致性哈希。
概念解释
- 取模:数组下标,O(1) 查找。
- 一致性哈希:环 + 有序集合,O(log n) 查找。
- 迁移量:取模 1~N/(N+1),一致性哈希 1/N。
原理流程
- 节点数固定不变:取模足够,简单高效。
- 节点数会变化:一致性哈希减少迁移。
- 中间场景:取模 + 预分片(先分 1024 片,再映射到节点),兼顾两者。
代码 / 图示
方案 查找 迁移量 实现复杂度
取模 O(1) 高(100%) 简单
预分片 O(1) 低(1/N片) 中
一致性哈希 O(log n) 低(1/N) 复杂
常见误区
- 误区:一致性哈希一定比取模好;正解:静态场景取模 O(1) 更简单。
- 误区:预分片不是一致性哈希;正解:预分片是取模的变体,先分固定数量片,片到节点映射可变。
追问 / 延伸
- Q:Redis Cluster 用什么? A:16384 个哈希槽,类似预分片,片到节点映射在 cluster 配置中维护。
- Q:一致性哈希查找复杂度? A:TreeMap O(log n),虚拟节点多时 log n 略大。
02.10.3-005 Jump Consistent Hash 原理
频率 ★★★ | 难度 高级
一句话结论
Jump Consistent Hash 是 Google 提出的极简算法:给定 key 和节点数 n,返回 [0, n) 中的节点号;只需 O(log n) 时间,零内存,分布均匀;适合节点数已知且递增的场景。
概念解释
- 输入:key(整数)和节点数 n。
- 输出:bucket ∈ [0, n)。
- 递推:从 bucket=0 开始,不断用随机数生成新 bucket,直到 bucket >= n。
- 无内存:不需要维护环,纯函数计算。
原理流程
- 初始化 bucket = -1,j = 0。
- 当 j < n:用哈希函数生成下一个 j = floor((j+1) * (random ^ ...)),bucket = j。
- 返回 bucket。
代码 / 示例
static int jumpConsistentHash(long key, int n) {
long b = -1;
long j = 0;
while (j < n) {
b = j;
key = key * 2862933555777941757L + 1; // LCG
j = (long) ((b + 1) * (double)(1L << 31) / ((key >>> 33) + 1));
}
return (int) b;
}
常见误区
- 误区:Jump Hash 是一致性哈希;正解:Jump Hash 是哈希函数,不需要环,但节点数必须已知且递增。
- 误区:Jump Hash 支持删除节点;正解:Jump Hash 只支持节点数递增,删除节点会导致分布不均。
追问 / 延伸
- Q:Jump Hash 适合什么场景? A:节点数可预测递增的场景,如消息队列分区到消费者。
- Q:分布均匀性? A:数学上证明均匀,且扩缩容迁移量约 1/n。
02.10.3-006 一致性哈希缓存预热
频率 ★★★ | 难度 进阶
一句话结论
新节点加入后,从下一节点迁移 1/N 的 key;迁移期间这部分 key 仍在旧节点,可双写或异步迁移,迁移完成后切流量;预热是把热点 key 主动推到新节点。
概念解释
- 迁移:key 从旧节点到新节点。
- 双写:迁移期间新旧节点都写。
- 预热:主动把热点 key 加载到新节点,避免迁移后冷启动。
原理流程
- 新节点加入环,计算受影响的 key 集合。
- 异步把这些 key 从旧节点复制到新节点。
- 复制期间双写,保证一致性。
- 复制完成后,切流量到新节点。
代码 / 图示
新节点 D 加入
受影响区间:B -> D 之间的 key
异步迁移:从 B 复制 key 到 D
双写:迁移期间 B、D 都写
切流:迁移完成,key 归属 D
常见误区
- 误区:迁移完再切流;正解:迁移期间双写,迁移完成后切流,避免请求打到不存在的 key。
- 误区:预热就是迁移;正解:预热是主动加载热点,迁移是被动数据搬移。
追问 / 延伸
- Q:迁移期间旧节点还在吗? A:在,只是不再是这些 key 的归属,切流后旧节点这些 key 可删除。
- Q:迁移失败怎么办? A:双写保证数据不丢,失败可重试或回滚。
02.10.3-007 数据倾斜与负载均衡
频率 ★★★★ | 难度 进阶
一句话结论
节点少时环上位置不均匀,某些节点区间大导致数据倾斜;虚拟节点把一个节点拆成多个,均匀分布到环上;倾斜还可能由 key 分布不均引起(如热点 key),需额外处理。
概念解释
- 环倾斜:节点在环上位置集中,区间大小不均。
- key 倾斜:某些 key 访问量远高于平均。
- 虚拟节点:打散环倾斜。
- 热点 key:需要额外拆分或缓存。
原理流程
- 节点少(如 3 台):环上位置集中,区间大小差异大。
- 加虚拟节点:每个节点 150 个副本,环上位置均匀。
- key 倾斜:热点 key 单独处理(拆分 key 或本地缓存)。
代码 / 图示
3 个真实节点:
环上位置:A ----- B --- C ---- A
区间不均
加虚拟节点(每个 150 个):
环上位置均匀分布
各真实节点负责区间 ≈ 1/N
常见误区
- 误区:虚拟节点解决 key 倾斜;正解:虚拟节点解决环倾斜(节点间负载不均),不解决热点 key。
- 误区:虚拟节点越多越好;正解:通常 150~200 足够,过多增加内存和查找时间。
追问 / 延伸
- Q:热点 key 怎么处理? A:拆分 key(如 key_1、key_2)分散到不同节点,或本地缓存。
- Q:Redis Cluster 怎么处理倾斜? A:16384 个槽位均匀分布,key 按 slot 归属。
02.10.3-008 分片策略怎么选
频率 ★★★★ | 难度 进阶
一句话结论
范围分片适合顺序访问(如按时间范围查),哈希分片适合均匀分布(如用户数据),一致性哈希适合动态扩缩容;选分片策略要考虑查询模式、扩缩容频率、数据倾斜。
概念解释
- 范围分片:按 key 范围划分,适合范围查询,但可能倾斜。
- 哈希分片:按 hash(key) 划分,均匀,但范围查询要扫所有分片。
- 一致性哈希:动态扩缩容迁移量小。
原理流程
- 主要按范围查询(如按时间):范围分片。
- 主要按点查询(如用户 ID):哈希分片。
- 需要动态扩缩容:一致性哈希或预分片。
- 数据有热点:额外拆分热点 key。
代码 / 图示
策略 查询模式 扩缩容 倾斜风险
范围分片 范围友好 迁移大 高(热点区间)
哈希分片 点查友好 迁移大 低
一致性哈希 点查友好 迁移小 低(需虚拟节点)
常见误区
- 误区:范围分片一定倾斜;正解:只要 key 分布均匀,范围分片也可以均衡。
- 误区:哈希分片不能范围查询;正解:可以,但要扫所有分片,性能差。
追问 / 延伸
- Q:MySQL 分库分表用什么? A:范围分片(按时间)或哈希分片(按用户 ID),常见预分片。
- Q:MongoDB 用什么? A:范围分片(range sharding)或哈希分片(hashed sharding),由用户选择。
待整理清单
- [ ] Redis Cluster 16384 槽位设计
- [ ] 分库分表双写迁移方案
- [ ] 一致性哈希 + 虚拟节点完整代码