一篇读懂一致性哈希：扩容为什么不用搬光数据

设想一个最常见的缓存集群：三台 Memcached，客户端用最朴素的方式分片——hash(key) % 3。业务涨了，运维挑个凌晨加第四台。理论上是容量多了三分之一，实际发生的事情是：几乎全部缓存在同一瞬间失效，命中率像跳崖一样归零，数据库像被全公司同事同时 @ 的值班人，当场休克。

这不是夸张，是取模分片的数学必然。而一致性哈希这个 1997 年就发明、至今仍在无数系统里服役的算法，要解决的正是这件事：让「加减一台机器」只影响它自己附近的一小片数据，而不是全世界。

取模分片的死穴：模数一变，全员搬家

server = hash(key) % N 这行代码的隐含前提是：N 是个恒定不变的常量。扩容时它变了，于是公式对每一个 key 同时失效。

举两个具体例子。某 key 的哈希值是 10：3 台时 10 % 3 = 1，落在 1 号机；扩成 4 台，10 % 4 = 2，搬家。另一个 key 哈希值是 12：12 % 3 = 0、12 % 4 = 0，侥幸不动。什么样的数能保住原位？必须让模 3 和模 4 得到同一个余数，也就是 12 的倍数这一档。粗算下来，10000 个 key 里只有约四分之一能留下，其余四分之三全部换主。

一般化：从 N 台扩到 N + 1 台，key 保住原位的概率只有约 1/(N + 1)。规模越大越讽刺——10 台扩到 11 台，搬家比例反而超过九成。你越成功，扩容越痛。

缓存场景下，这个现象有个如雷贯耳的名字：缓存雪崩。海量 key 同时失效，等于把整条读流量在一瞬间砸回数据库，DB 连接池打满，超时连锁反应拖着应用一起倒。存储场景下更痛：分库分表的数据是要真搬的，逐行导出导入，一晚上搬不完就得停写。

根因只有一句话：取模把机器数量织进了每一个 key 的映射公式里。N 一动，天下皆动。想要扩容便宜，就得把「谁的变化影响谁」局部化——这就是一致性哈希的全部动机。

哈希环：把除法换成排队

Karger 等人 1997 年在分布式缓存论文里提出的方案，一句话就能说清：别算除法了，把节点和 key 都摆到一个首尾相接的圆环上排队。

具体三步：

• 把哈希空间看成一个环，比如 0 到 2^32 - 1，最大值绕回 0；
• 每个节点算一个哈希值，作为自己站上环的位置；
• 每个 key 也算一个哈希值，从自己的位置顺时针走，遇到的第一个节点就是主人。

flowchart LR
  subgraph R["哈希环：0 到 2^32 - 1，首尾相接"]
    A["cache-a（哈希 0x25f0）"] -->|"顺时针"| B["cache-b（0x7c31）"]
    B --> C["cache-c（0xc9a2）"]
    C --> A
  end
  K["key K1（哈希 0x88d4）"] -.->|"顺时针第一个：cache-c"| C

现在再看扩容发生了什么。cache-d 加入，环上多了一个点。只有「cache-d 到它前驱之间」那段弧上的 key，顺时针看到的第一个人从别人变成了 cache-d；其余所有弧段的 key，望过去的主人一个都没变。四台机器，新节点平均接管四分之一的环，就只搬四分之一的数据。摘节点同理：cache-c 下线，它那段弧上的 key 顺时针挪交给下家，其他人原地不动。

顺带澄清一个容易望文生义的点：这里的「一致性」不是分布式一致性协议里那个 consistency，而是映射规则的稳定性——同一个 key，不管哪个客户端、在哪个时刻算，只要节点集合相同，得到的归属就相同；节点集合变化时，受影响的范围被限制在局部。

虚拟节点：往环上撒一把芝麻

朴素环有一个马上会翻车的问题：节点少的时候，随机落点极不均匀。

环上掷点本质是随机事件。只掷四个点，弧长的方差可以大到离谱——有人分到一大片沃土，有人挤在一条缝里。我实测了一下：四台机器各放 1 个环点、10000 个 key，最忙的机器分到 3940 个 key，最闲的只有 1077 个，差 3.7 倍。四分之一的算力在裸奔，四分之一在划水。

虚拟节点是解药：一台物理机不再对应环上的一个点，而是同时扮演几百个虚拟点。Dynamo 论文里叫 tokens；Memcached 世界的 ketama 约定每台机器放 160 个点。效果立竿见影，同样四台机器、1 万 key 的实测：

• 每台 1 个点：最大/最小负载比 3.66；
• 每台 10 个点：2.15；
• 每台 160 个点：1.18，基本均匀。

原理是大数定律：每台机器撒的点多了，分到的弧段总长趋于相等，个别点掷偏了会被同机器的其他点摊薄。

Dynamo 论文把虚拟节点的收益总结为三条，值得原样记住：节点宕机时，它的负载均匀散给所有幸存节点，而不是全压给环上下家；新节点上线时，从每台机器各接走大致相等的负载；机器性能参差时，按容量配不同数量的虚拟节点。论文 6.2 节还诚实记录了后续演进：纯随机 token 方案在数据恢复速度和元数据量上都不理想，最终改成「等分区间 + 随机挑选」的策略，元数据规模降了三个数量级。工程上没有一劳永逸的环，只有不断被现实修正的环。

代码走查：亲眼看见 1/N

口说无凭，下面这份 javascript 不到六十行，把取模与哈希环放进同一个实验里对照（node consistent-hash.mjs 即可运行）：

// 一致性哈希对照实验：取模分片 vs 哈希环 + 虚拟节点（ketama 风格，MD5）
// 运行：node consistent-hash.mjs
import { createHash } from 'node:crypto'
const md5 = (s) => createHash('md5').update(s).digest()

const KEYS = Array.from({ length: 10000 }, (_, i) => `user:${i}:profile`)

// 方案一：普通哈希取模——槽位数一变，几乎全部 key 换主
function byModulo(servers) {
  const map = new Map()
  for (const k of KEYS) map.set(k, servers[md5(k).readUInt32BE(0) % servers.length])
  return map
}

// 方案二：一致性哈希环，每个物理节点撒 160 个虚拟点
function buildRing(servers, vnodes = 160) {
  const ring = []
  for (const s of servers)
    for (let i = 0; i < vnodes; i++)
      ring.push([md5(`${s}-${i}`).readUInt32BE(0), s])
  return ring.sort((a, b) => a[0] - b[0])
}

function byRing(ring) {
  const map = new Map()
  for (const k of KEYS) {
    const h = md5(k).readUInt32BE(0)
    let lo = 0, hi = ring.length          // 上界开区间：lower bound
    while (lo < hi) {                     // 二分找第一个 hash >= h 的点
      const mid = (lo + hi) >> 1
      ring[mid][0] < h ? (lo = mid + 1) : (hi = mid)
    }
    map.set(k, ring[lo % ring.length][1]) // lo === length 时回绕到环头
  }
  return map
}

const moved = (a, b) => [...a].filter(([k, v]) => b.get(k) !== v).length

const m3 = byModulo(['cache-a', 'cache-b', 'cache-c'])
const m4 = byModulo(['cache-a', 'cache-b', 'cache-c', 'cache-d'])
console.log(`取模    3 台扩到 4 台：迁移 ${moved(m3, m4) / 100}% 的 key`)

const r3 = byRing(buildRing(['cache-a', 'cache-b', 'cache-c']))
const r4 = byRing(buildRing(['cache-a', 'cache-b', 'cache-c', 'cache-d']))
console.log(`哈希环  3 台扩到 4 台：迁移 ${moved(r3, r4) / 100}% 的 key`)

const r4b = byRing(buildRing(['cache-a', 'cache-b', 'cache-c', 'cache-d']))
const r3b = byRing(buildRing(['cache-a', 'cache-b', 'cache-d']))
console.log(`哈希环  4 台摘掉 cache-c：迁移 ${moved(r4b, r3b) / 100}% 的 key`)

// 数据倾斜：虚拟节点越多，各台负载越均匀
for (const v of [1, 10, 160]) {
  const ring = buildRing(['cache-a', 'cache-b', 'cache-c', 'cache-d'], v)
  const m = byRing(ring)
  const load = { 'cache-a': 0, 'cache-b': 0, 'cache-c': 0, 'cache-d': 0 }
  for (const k of KEYS) load[m.get(k)]++
  const c = Object.values(load)
  console.log(`虚拟节点 ${String(v).padStart(3)} 个：[${c.join(', ')}]，最大/最小 = ${(Math.max(...c) / Math.min(...c)).toFixed(2)}`)
}

我本机跑出来的数字：

取模    3 台扩到 4 台：迁移 75.21% 的 key
哈希环  3 台扩到 4 台：迁移 24.12% 的 key
哈希环  4 台摘掉 cache-c：迁移 27.46% 的 key
虚拟节点   1 个：[1436, 1077, 3547, 3940]，最大/最小 = 3.66
虚拟节点  10 个：[2588, 1449, 3121, 2842]，最大/最小 = 2.15
虚拟节点 160 个：[2322, 2520, 2746, 2412]，最大/最小 = 1.18

几个走查要点：

• buildRing 把所有虚拟点的哈希值算出来排序——环在内存里就是一个有序数组，没有比这更神秘的实现；
• 查找是标准二分（lower bound）：找第一个大于等于 key 哈希值的点，复杂度 O(log V)，V 是虚拟点总数，640 个点只要约 10 次比较；
• lo % ring.length 是个小心思：二分的上界用开区间，当 key 的哈希比环上所有点都大时，lo 正好等于数组长度，取模后回绕到环头——顺时针走到头，就回到起点；
• 摘掉 cache-c 的迁移率是 27.46%，比四分之一略高，因为它掷到的弧段略大。环的迁移率从来不是精确的 1/N，而是「新节点弧长的占比」，方差随虚拟点增多而收窄。

真实系统怎么用

Memcached 客户端：Ketama 立下的约定

2007 年 Flickr 的缓存池扩容之痛催生了 ketama——它不在服务器上，而是客户端里的一个约定：服务器列表、每台 160 个虚拟点、MD5 哈希，全套固定下来，libmemcached、spymemcached 以及各路 Ruby、Python 客户端都照此实现。约定必须跨语言一致的原因很直接：不同服务要能共享同一个缓存池，就必须对「这个 key 归谁」算出同一个答案。有了它，往池里加机器只丢约 1/N 的缓存条目，其余全部继续命中。

Dynamo：把环写进教科书的系统

同年发布的 Dynamo 论文（后来 DynamoDB 的学术前身）用整节的篇幅固定了「一致性哈希 + 虚拟节点」的组合，三条收益在前文已经引过。它还带起了一整脉系统：Cassandra 的 tokens、Riak 的 ring，都是这一思想的直系后代。可以说，2007 年之后，「一致性哈希」不再是论文术语，而是分布式存储的出厂配置。

Redis Cluster：不走环，改用槽位

有意思的是，Redis Cluster 明确选择了不做一致性哈希。官方文档原话是：它用的是 a different form of sharding where every key is conceptually part of what we call a hash slot。具体做法：把键空间切成 16384 个槽，slot = CRC16(key) mod 16384，每个节点负责一段槽位（例如 0 到 5500、5501 到 11000）。扩容就是把一部分槽连同其中的 key 迁给新节点，缩容是挪空再退场，全程不宕机；客户端把请求发到了不归对方管的槽，会收到 MOVED 重定向，随后把槽位映射缓存下来直连正确的节点。

为什么放着现成的环不用？槽位方案换来的是可运维性：

• 谁管哪些槽是一张显式的表，一眼可查、可手动调整；环的归属靠哈希推导，出了倾斜只能整体增减虚拟点，粒度粗；
• 心跳包可以携带本节点负责槽位的位图，16384 个比特正好 2 KB，gossip 协议塞得下——这也是槽位总数定在 16384 而不是 65536 的直接原因，毕竟官方建议的集群规模在约 1000 个节点以内；
• 多 key 操作靠 hash tag 获得确定性：{user1000}.following 与 {user1000}.followers 强制落进同一个槽，同槽即可事务与脚本操作。

两种方案摆在一起看：

维度	一致性哈希环	Redis Cluster 槽位
映射方式	key 顺时针找第一个虚拟点	CRC16(key) mod 16384 查表
扩缩容	环上增删点，弧段自动易主	显式迁移指定槽位
归属可见性	靠计算推导	槽位表显式可查
元数据开销	每个客户端各存一张环	心跳携带约 2 KB 位图
多 key 操作	无原生约定	hash tag 同槽
代表系统	Ketama、Dynamo、Cassandra	Redis Cluster

一句话总结分歧：环把路由「算」出来，槽位把路由「管」起来。前者适合无中心的客户端分片，后者适合需要精细运维的集群。

边界与坑

• 虚拟节点治不了热点 key。环保证的是 key 数量均匀，不是访问量均匀。全站都在读同一个明星用户的资料，它落在哪台机器，哪台就被压穿。热点要靠应用层拆 key、本地缓存或多级副本解决，环帮不上忙。
• 环是数据结构，不是魔法。增删节点要重建有序数组，并让所有客户端看到同一张环。几千个点的重建只是微秒级开销，但别把它放进请求热路径现算；客户端之间环短暂不一致时，会出现两台机器都认自己是主人的窗口，要靠约定的更新顺序或中心化配置兜底。
• 副本与环会打架。Dynamo 要求 N 个副本沿环顺时针取接下来的 N 个位置，但虚拟节点可能让其中两个落回同一台物理机——论文的解法是构建 preference list 时跳过重复的物理节点。
• 迁移期的一致性要自己管。环只回答「数据该在哪」，不回答「正在搬的数据读谁」。缓存场景天然可容忍（miss 回源即可），存储场景则要双写双读或按弧段灰度切换——Redis Cluster 用 MIGRATE 原子搬 key、用 ASK 重定向过渡，补的就是这块。
• 哈希函数要稳，约定要死。同一个 key 在所有客户端必须算出同一个哈希值。ketama 能跨语言共享缓存池，靠的是「服务器字符串拼接 + 160 点 + MD5 取前 4 字节」逐字一致。改任何一处，等于换了一个缓存池。

参考资料

• Dynamo: Amazon's Highly Available Key-value Store——一致性哈希与虚拟节点的原始出处，三条收益与 6.2 节的策略演进都在论文里。
• Scale with Redis Cluster（Redis 官方文档）——槽位模型、hash tag 与 MOVED 重定向的权威说明。
• Redis Cluster Specification（Redis 官方规范）——CRC16 mod 16384 的精确定义、心跳位图与槽位迁移协议。
• libketama: consistent hashing for memcached clients——每台 160 点、MD5 的客户端环约定，跨语言兼容的事实标准。
• Hash Slot vs. Consistent Hashing in Redis（Severalnines）——antirez 关于 16384 个槽与 2 KB 心跳位图的取舍分析。