罗罗编程学习记录
本页内容 展开查看

09.9.1 一致性哈希

所属:全栈开发面试题库 / 09 高阶架构:高并发与分布式 / 09.9 分布式基础算法

覆盖范围

  • 一致性哈希环原理与取模哈希的缺陷
  • 虚拟节点解决数据倾斜
  • 节点扩缩时的迁移量分析
  • 工程实现:Ketama、Redis Cluster、Dynamo 风格

高频题速览

编号 题目 难度 频率
09.9.1-001 一致性哈希解决什么问题 进阶 ★★★★★
09.9.1-002 哈希环怎么路由 进阶 ★★★★☆
09.9.1-003 虚拟节点解决什么问题 进阶 ★★★★☆
09.9.1-004 节点扩缩时迁移量是多少 进阶 ★★★★☆
09.9.1-005 一致性哈希和取模哈希的区别 基础 ★★★★☆
09.9.1-006 数据倾斜怎么处理 进阶 ★★★☆☆
09.9.1-007 Ketama 是什么 进阶 ★★★☆☆
09.9.1-008 Redis Cluster 用一致性哈希吗 进阶 ★★★★☆
09.9.1-009 一致性哈希的容错性 进阶 ★★★☆☆
09.9.1-010 一致性哈希工程实现要点 高级 ★★★☆☆

09.9.1-001 一致性哈希解决什么问题?

一句话结论

普通取模哈希(hash(key) % N)在节点数 N 变化时,几乎所有 key 都要重新映射到新节点,缓存命中率暴跌;一致性哈希把哈希空间组织成环,节点数变化时只有相邻节点的 key 迁移,迁移量约为 1/N,解决了扩缩容时的大规模缓存失效问题。

概念解释

  • 取模哈希缺陷:N 变为 N+1,约 N/(N+1) 的 key 要迁移。
  • 一致性哈希:哈希空间 0~2^32-1 组成环,节点和 key 都哈希到环上,key 顺时针找最近节点。
  • 迁移量:新增/删除一个节点,只有该节点到前一个节点之间的 key 迁移。

原理流程

取模:hash(key) % 4 → 4 节点
  加一个节点变 5 → hash(key) % 5 → 约 80% key 变节点
一致性哈希:
  环上 4 个节点,加第 5 个 → 只迁移第 5 个节点到前一个节点区间的 key
  → 迁移量约 1/5

代码或图示

环(顺时针):
  节点 A(100) → 节点 B(500) → 节点 C(900) → 节点 D(1500) → 回到 A
  key 哈希到 700 → 顺时针找最近节点 C(900)
  key 哈希到 200 → 顺时针找最近节点 B(500)

常见误区

  • 误区:一致性哈希是为了负载均衡。它主要解决扩缩容时的迁移量问题,负载均衡靠虚拟节点。
  • 误区:一致性哈希没有数据倾斜。节点少时环上分布不均,需要虚拟节点。

追问

  • 问:典型应用场景?答:分布式缓存(Memcached)、分布式存储(Dynamo)、RPC 客户端负载均衡。
  • 问:和 02.10.3 一致性哈希什么关系?答:02.10.3 从算法角度讲,这里从分布式工程视角讲迁移与容错。

09.9.1-002 哈希环怎么路由?

一句话结论

节点和 key 都用同一个哈希函数映射到 0~2^32 的整数环;key 路由时从 key 的哈希位置顺时针走,遇到的第一个节点就是归属节点;环上节点按哈希值排序,用有序数组或红黑树存储,查找用二分。

概念解释

  • 环:哈希空间首尾相接,0 和 2^32-1 相邻。
  • 顺时针:key 归属第一个哈希值大于等于它的节点。
  • 查找:节点列表有序,二分查找第一个 >= key 哈希的节点。

原理流程

1. 计算 nodeHash = hash(node),把所有节点哈希放到环上排序
2. 计算 keyHash = hash(key)
3. 在有序节点列表中二分查找第一个 >= keyHash 的节点
4. 如果没有(keyHash 大于最大节点哈希),取第一个节点(环回绕)

代码或图示

节点哈希:A=100, B=500, C=900
key 哈希:k1=300 → 顺时针第一个节点 B(500)
          k2=950 → 顺时针第一个节点 A(100,回绕)

常见误区

  • 误区:key 哈希位置逆时针找节点。是顺时针,约定一致即可,关键是所有节点用同一规则。
  • 误区:环上节点越多越精确。节点数固定时,虚拟节点增加环上的节点密度,详见 09.9.1-003。

追问

  • 问:节点列表怎么存?答:SortedSet(Redis ZSet)或 TreeMap,支持二分查找。
  • 问:哈希函数选什么?答:要均匀分布,常用 MD5、MurmurHash、Ketama,不要用 CRC32(分布不均)。

09.9.1-003 虚拟节点解决什么问题?

一句话结论

物理节点少时,环上节点分布不均导致数据倾斜(一个节点分到大量 key);虚拟节点是每个物理节点对应环上多个虚拟节点(例如 150~200 个),让数据在环上均匀分布,物理节点越多虚拟节点越多,负载越均衡。

概念解释

  • 虚拟节点:一个物理节点在环上对应多个哈希位置,例如 A-1、A-2、A-3。
  • 数据倾斜:环上节点少时,两个节点之间的弧长差异大,数据分布不均。
  • 映射:虚拟节点哈希到环上,实际归属物理节点 A。

原理流程

无虚拟节点:
  A=100, B=500 → A 管 100~500 的 key(400 弧长),B 管 500~100+2^32(巨长)
  → B 数据多
有虚拟节点:
  A-1=100, A-2=800, A-3=1500
  B-1=500, B-2=1200, B-3=2000
  → A 和 B 各管约一半 key

代码或图示

每个物理节点 150 个虚拟节点:
  node-A: A#1, A#2, ..., A#150
  node-B: B#1, B#2, ..., B#150
环上共 300 个虚拟节点位置,数据均匀分布

常见误区

  • 误区:虚拟节点越多越好。太多虚拟节点增加节点列表内存与查找开销,通常 150~200 个足够。
  • 误区:虚拟节点是为了迁移量。虚拟节点主要解决数据倾斜,迁移量改善是附带效果。

追问

  • 问:虚拟节点数怎么定?答:经验值 150~200,物理节点越多可以适当减少。
  • 问:下线一个物理节点迁移量?答:该节点所有虚拟节点负责的 key 迁移到下一个虚拟节点,总量约 1/N。

09.9.1-004 节点扩缩时迁移量是多少?

一句话结论

N 个节点的一致性哈希环,新增或删除一个节点,只有约 1/N 的 key 需要迁移(具体取决于虚拟节点位置,但期望是 1/N);对比取模哈希的接近全量迁移,一致性哈希把迁移量从 O(N) 降到 O(1)。

概念解释

  • 新增节点:新节点在环上占一段弧,这段弧上的 key 从原节点迁移到新节点。
  • 删除节点:该节点负责的 key 迁移到下一个节点。
  • 期望迁移量:1/N,与节点数成反比。

原理流程

N 个节点,环均匀分布:
  每个节点管 1/N 的 key
  新增第 N+1 个 → 从相邻节点抢 1/(N+1) 的 key
  删除第 N 个 → 该节点 1/N 的 key 迁移到下一个节点

代码或图示

4 节点,加第 5 个:
  迁移量 ≈ 1/5 = 20%
  对比取模:迁移量 ≈ 80%

常见误区

  • 误区:一致性哈希迁移量是 0。迁移量约 1/N,不是 0,只是比取模哈希小很多。
  • 误区:虚拟节点越多迁移量越大。虚拟节点让分布更均匀,迁移量更接近 1/N。

追问

  • 问:迁移期间怎么服务?答:新节点启动后,旧节点仍服务,迁移的 key 在新节点加载完成前由旧节点继续服务。
  • 问:大量节点同时扩缩怎么办?答:逐个操作,避免同时多个节点变化导致迁移量叠加。

09.9.1-005 一致性哈希和取模哈希的区别是什么?

一句话结论

取模哈希 hash(key) % N 简单,但 N 变化时几乎全量迁移;一致性哈希把 key 和节点都哈希到环上,N 变化时只迁移相邻节点的 key,迁移量从 O(N) 降到 O(1/N);代价是实现复杂(有序环、虚拟节点)。

概念解释

  • 取模:直接用节点数取模,节点数变化时映射关系完全改变。
  • 一致性哈希:节点和 key 在同一哈希空间,节点变化只影响局部。
  • 代价:需要维护有序节点列表、处理环回绕、虚拟节点映射。

原理流程

取模:key % 4 = 3 → 节点 3
  节点变 5:key % 5 = ? → 大部分 key 变节点
一致性哈希:节点和 key 在环上,节点变化只影响相邻段

代码或图示

对比:
  取模:N=4 → N=5,迁移 80%
  一致性哈希:N=4 → N=5,迁移 20%

常见误区

  • 误区:取模哈希完全不能用。节点数固定时,取模简单高效;问题在动态扩缩容。
  • 误区:一致性哈希不需要哈希函数分布均匀。如果哈希函数分布不均,环上节点和 key 分布都不均。

追问

  • 问:什么时候用取模?答:节点数固定、不扩缩的场景,取模最简单。
  • 问:什么时候用一致性哈希?答:缓存集群、分布式存储,需要动态扩缩容。

09.9.1-006 数据倾斜怎么处理?

一句话结论

数据倾斜来自环上节点分布不均和热点 key;解决方案是虚拟节点增加环上密度、用分布均匀的哈希函数、对热点 key 做多副本或本地缓存;监控各节点 key 数与内存,倾斜超阈值告警。

概念解释

  • 节点分布不均:物理节点少时,环上弧长差异大。
  • 热点 key:少数 key 被大量访问,归属节点压力大。
  • 虚拟节点:让数据均匀分布到各物理节点。

原理流程

倾斜原因:
  1. 节点少 → 弧长差异 → 虚拟节点解决
  2. 哈希函数差 → 分布不均 → 换 MurmurHash/Ketama
  3. 热点 key → 单节点压力大 → 本地缓存/多副本

代码或图示

监控:
  每个节点 key 数、内存使用率、QPS
  差异 > 20% 告警

常见误区

  • 误区:虚拟节点能解决热点 key。虚拟节点解决分布不均,热点 key 要单独处理(本地缓存、分片)。
  • 误区:数据倾斜是一致性哈希的缺陷。无虚拟节点时确实倾斜,虚拟节点后分布均匀。

追问

  • 问:热点 key 怎么发现?答:监控单节点 QPS 与 key 访问频率,热点探测详见 09.3.2.3。
  • 问:热点 key 怎么处理?答:本地缓存(Caffeine)、key 加随机后缀分片读,详见 09.3.2.4。

09.9.1-007 Ketama 是什么?

一句话结论

Ketama 是一种一致性哈希算法实现(由 Memcached 客户端使用),用 MD5 哈希把节点和 key 映射到 2^32 环,每个节点默认 160 个虚拟节点;它的特点是分布均匀、迁移量稳定,是 Memcached 客户端 libketama 的标准实现。

概念解释

  • Ketama:MD5 哈希 + 环 + 虚拟节点的具体实现。
  • 默认虚拟节点数:160。
  • 应用:Memcached 客户端、某些 RPC 框架。

原理流程

1. 节点名 + 虚拟编号 → MD5 → 4 个 uint32(MD5 输出 16 字节)
2. 每个虚拟节点贡献 4 个环上位置
3. key → MD5 → 4 个 uint32,取第一个找顺时针节点

代码或图示

Ketama 哈希:
  md5("nodeA-1") = 16 字节 → 拆成 4 个 32 位整数
  → 每个整数是环上一个位置

常见误区

  • 误区:Ketama 是一种哈希函数。它是一致性哈希算法的一种具体实现,用 MD5 做哈希。
  • 误区:Ketama 只用于 Memcached。其他 RPC 框架也用 Ketama 或类似实现。

追问

  • 问:Ketama 和普通一致性哈希区别?答:MD5 输出 16 字节拆成 4 个 uint32,每个虚拟节点贡献 4 个环位置,分布更均匀。
  • 问:用什么哈希函数?答:MD5 或 MurmurHash,关键是分布均匀,不要用 Java 的 String.hashCode(分布差)。

09.9.1-008 Redis Cluster 用一致性哈希吗?

一句话结论

Redis Cluster 不用一致性哈希,它用 16384 个哈希槽(slot):key 用 CRC16 哈希后对 16384 取模得到槽号,每个主节点负责一段槽;节点扩缩时迁移的是槽(一段 key),而不是环上的 key;本质上是取模哈希的改进版(固定槽数)。

概念解释

  • 哈希槽:固定 16384 个槽,key 归属槽,槽归属节点。
  • 槽迁移:扩缩时迁移槽(一批 key),不是逐个 key 重新哈希。
  • 为什么不用一致性哈希:Redis Cluster 的槽是固定的,节点变化时手动分配槽,迁移量可控。

原理流程

key → CRC16(key) % 16384 = slot
  → slot 映射到节点
节点 A:slot 0~5000
节点 B:slot 5001~10000
节点 C:slot 10001~16383

代码或图示

Redis Cluster 为什么 16384?
  心跳包携带槽位图(16384 bit = 2KB),太大带宽高
  16384 是工程折中值

常见误区

  • 误区:Redis Cluster 用一致性哈希。它用哈希槽,不是环;一致性哈希是自动计算归属,Redis Cluster 是手动分配槽。
  • 误区:哈希槽比一致性哈希好。各有取舍:槽迁移可控但要手动管理,一致性哈希自动但实现复杂。

追问

  • 问:为什么用 CRC16?答:CRC16 计算快且分布均匀,Redis Cluster 用它。
  • 问:节点扩缩怎么迁移槽?答:reshard,把一段槽从一个节点迁到另一个,迁移期间双写。

09.9.1-009 一致性哈希的容错性怎么样?

一句话结论

一致性哈希环上一个节点故障时,它负责的 key 自动迁移到下一个节点(环回绕),其他节点不受影响;对比取模哈希一个节点故障导致大量 key 重新映射,一致性哈希把故障影响限制在相邻节点;但单节点故障会让下一个节点负载翻倍,需要告警。

概念解释

  • 节点故障:环上该节点位置消失,它负责的 key 顺时针归到下一个节点。
  • 影响范围:只有故障节点和下一个节点受影响,其他节点 key 不变。
  • 负载翻倍:下一个节点承担故障节点的 key,负载短期翻倍。

原理流程

节点 B 故障:
  B 负责的 key → 归到下一个节点 C
  A、D 的 key 不变
  C 的负载短期增加(B 的量)

代码或图示

容错:
  环上节点故障 → key 自动归到下一个节点
  不需要重新哈希所有 key

常见误区

  • 误区:一致性哈希自动容错。它只是让 key 迁移到下一个节点,下一个节点负载会翻倍,需要告警与扩容。
  • 误区:下一个节点能扛住翻倍负载。如果故障节点负载高,下一个节点可能被压垮,需要副本与预热。

追问

  • 问:怎么缓解故障影响?答:每个 key 多副本(在环上不同节点),故障时读副本,详见 09.3.1.3。
  • 问:缓存雪崩怎么办?答:故障节点的 key 迁移到下一个节点,下一个节点缓存冷启动,可能击穿,详见 09.3.2.1。

09.9.1-010 一致性哈希工程实现要点有哪些?

一句话结论

工程实现要点:节点列表有序存储(TreeMap/跳表)、虚拟节点数 150~200、哈希函数选 MD5/MurmurHash、节点变更后客户端刷新环、key 路由用二分查找;注意环回绕、虚拟节点映射回物理节点、客户端与服务端环一致性。

概念解释

  • 有序存储:TreeMap 或 SortedSet,支持二分查找。
  • 虚拟节点:每个物理节点 150~200 个虚拟位置。
  • 环一致性:客户端和服务端用同样的节点列表与哈希函数,否则路由结果不同。

原理流程

1. 节点列表变更(上下线)→ 通知所有客户端刷新环
2. 客户端路由:keyHash → 二分找顺时针节点
3. 虚拟节点 → 映射回物理节点 IP

代码或图示

// 伪代码
TreeMap<Long, String> ring = new TreeMap<>();
for (Node node : nodes) {
    for (int i = 0; i < 160; i++) {
        long hash = hash(node.getName() + "#" + i);
        ring.put(hash, node.getName());
    }
}
public String getNode(String key) {
    long h = hash(key);
    Map.Entry<Long, String> e = ring.ceilingEntry(h);
    if (e == null) e = ring.firstEntry(); // 回绕
    return e.getValue();
}

常见误区

  • 误区:客户端和服务端用不同哈希函数。路由结果不一致,key 归属错误。
  • 误区:节点列表变更后不通知客户端。客户端用旧环,路由到已下线节点。

追问

  • 问:节点列表怎么同步?答:通过配置中心(etcd/Nacos)或 gossip,客户端订阅变更。
  • 问:性能瓶颈?答:二分查找 O(log N),虚拟节点数固定,查找很快;瓶颈在节点列表同步。

待整理清单

  • [ ] 一致性哈希 Java/Go 实现完整代码
  • [ ] Redis Cluster 槽迁移细节
  • [ ] Memcached Ketama 客户端配置