缓存集群原来三台,某天容量不够,运维顺手加了一台,变成四台。节点都正常启动,配置也推送了,按理说容量涨了三成,命中率应该更高。结果监控上缓存命中率从九成多掉到两成出头,大量请求绕过缓存直接查数据库,数据库连接数几分钟内打满,接口开始超时。扩容动作本身没有出错,错的是 key 分到哪台机器的规则。

他们用的是最直观的取模法:把 key 哈希成一个整数,再对节点数取模,余数就是节点编号。三台变四台,节点数从 3 变成 4,绝大多数 key 的余数都变了。本机用 FNV-1a 哈希和 1 万个 key 跑了一遍,3 台扩到 4 台时,74.87% 的 key 换了节点。原来缓存里四分之三的数据直接失效,剩下的四分之一还要看原来那台机器是否被保留。

这就是这篇要讲的问题:扩缩容时,怎样让尽量少的 key 换位置。一致性哈希(consistent hashing)给出的答案是:把节点和 key 都放到同一个圆上,key 顺时针找到的第一个节点就是它的归属。这样加一台机器只影响圆上的一段,不会全量重排。

现场:加一台机器,四分之三的缓存失效

先把这个比例算清楚。对 3 取模和对 4 取模,结果是否相同,取决于这个整数在 12 的周期里落在哪一格:从 0 到 11 逐个数一遍,只有 0、1、2 这三个数同时满足「除以 3 的余数」和「除以 4 的余数」相等,其余九个都不一样。三个对十二个,就是四分之一。所以扩容之后大约 75% 的 key 会换节点,实测 74.87% 非常接近这个理论值。

换节点意味着什么?意味着这台机器上没有这个 key 的缓存,请求要回源到数据库,查完再写回新的节点。原来命中率九成,扩容后只有原来四分之一的数据还能命中,命中率大约掉到两成出头。数据库平时承接一成流量,这一刻要承接八成,连接池很快耗尽,后面的请求排队,接口超时,上游重试又把压力放大一遍。这就是常说的缓存雪崩。

更难受的是,这个操作很难「回滚」。把第四台撤掉,节点数从 4 变回 3,key 又会被重新分配一次,缓存再失效一轮。所以问题不在于「加机器」这个动作,而在于分配规则要求「节点总数」参与计算,总数一变,所有结果都跟着变。

取模法:简单,但扩缩容要全量重排

取模法的规则只有一行:节点编号等于哈希值对节点数取模。它有三个优点:实现极简、分布均匀、不需要额外元数据。只要哈希函数正常,key 会均匀落在各台机器上,查询时现算现得,不用维护一张映射表。这也是它被大量使用的原因。

function fnv1a(str) {
  let h = 2166136261;
  for (let i = 0; i < str.length; i++) {
    h ^= str.charCodeAt(i);
    h = Math.imul(h, 16777619) >>> 0;
  }
  return h;
}

function nodeByModulo(key, nodeCount) {
  return fnv1a(key) % nodeCount;
}

它的缺点也来自这一行:节点数是公式的一部分。容量规划时三台够用,扩到四台,公式里的除数从 3 变成 4,几乎所有 key 的余数都要重算。缩容也一样,四台变三台,或者某台机器宕机被摘除,剩下的 key 同样大面积搬家。搬家的代价不是一次计算,而是缓存失效、回源、网络传输、磁盘写入,以及数据库短时间内承受成倍的读流量。

有人会想,那就一次多扩几台,减少扩容次数。这只能减少「发生次数」,不能减少「每次的比例」。从 3 台扩到 6 台,仍然有大量 key 换位置;从 100 台扩到 101 台,比例看起来小了,但绝对数量仍然可观,而且集群越大,单台故障影响的 key 比例越难预测。取模法的问题不是参数没调好,而是「用总数做除数」这个设计本身不具备局部性。

还有一种缓解办法是预先分片:把哈希空间固定切成很多槽,节点负责若干槽,扩缩容只迁移整槽。它确实能把搬迁变成「按槽移动」,但槽数、槽到节点的映射仍然要维护,槽的粒度也决定了迁移的粒度。一致性哈希可以看作把这个思路做得更彻底:不预先切槽,而是让节点自己站到环上,key 按位置找主人。

哈希环:顺时针找第一个节点

哈希环(hash ring)是一个把哈希值空间首尾相接的圆。常见的哈希函数输出 32 位无符号整数,取值范围从 0 到 2 的 32 次方减一,把这个范围想象成一个圆,最大值后面接回 0。节点和 key 都用同一个哈希函数映射到这个圆上,每个节点占据圆上的一个点。

一个 key 怎样找到自己的节点
把每个节点的标识哈希成环上的位置
把 key 哈希成环上的位置
从 key 的位置顺时针找第一个节点
这个节点负责它到上一个节点之间的那段弧

注意「负责哪一段」的定义:每个节点负责从它自己的位置开始、逆时针到上一个节点之间的那段弧。换个说法,一个 key 归属于「顺时针方向第一个位置大于等于它的节点」,走到圆尾还没找到就回到圆头。这条规则让每个 key 都有唯一的主人,也让节点的增减只影响一段弧。

加一个新节点时,它只会从「顺时针方向的下一个节点」手里拿走一段:新节点到下一个节点之间的 key 改归新节点,其余 key 不受影响。按节点位置均匀分布的假设,这段弧平均占整个环的 N 加一分之一。三台加一台,平均迁移四分之一,正好是把取模法的 75% 压到了 25%。删除一个节点则相反,它负责的那段弧整体交给顺时针的下一个节点。

实现上,环通常存成一个按位置排好序的数组或一棵有序树。查找时对 key 的哈希值做二分,找到第一个大于等于它的位置;走到末尾就取第一个。插入或删除节点时,只改动环上的一个点,不需要重算所有 key。查找成本是节点数量的对数,和 key 的总数无关。

这里有一个容易被忽略的前提:所有客户端必须用同一个哈希函数、同一套节点标识、同一份环配置。任何一处不一致,同一个 key 在不同客户端眼里就会归到不同节点,缓存看起来「时有时无」。节点标识也要稳定,用 IP 加端口、主机名还是实例名,要在整个集群里统一,并且重启后不能变。

虚拟节点:把环切得更碎

只有三个节点、每个节点一个点时,环会被切成三段,但三段的长度并不相等。节点位置是哈希算出来的,随机落在圆上,完全可能出现一段占了大半个圆、另一段只有几个百分点的情况。本机用 1 万个 key、三台机器、1 个虚拟节点跑了一遍,分布是 A 2259、B 6916、C 825:B 一台就扛了近七成的 key,C 只有八个多百分点。这种偏斜在缓存场景里很致命,最忙的那台先被打满,扩容的初衷落空。

虚拟节点(virtual node)解决的就是这个问题。它的做法是给每个物理节点在环上分配多个位置,每个位置叫一个虚拟节点,key 先落到某个虚拟节点上,再映射回它所属的物理节点。一个物理节点在环上占的点越多,它负责的弧就越碎、越接近均匀。物理节点和虚拟节点之间是一对多的关系。

物理节点真正提供缓存服务的机器,负责承接请求和存储数据,数量通常不多。
虚拟节点物理节点在环上的多个投影,每个投影有自己的哈希位置,用来把负责的区间切碎。
归属规则key 先找到顺时针第一个虚拟节点,再由这个虚拟节点回到它的物理节点,多了一层间接映射。

本机继续加虚拟节点做对照。环上放 100 个虚拟节点时,三台的分布变成 C 1497、A 3056、B 5447,最重的节点从近七成降到五成多,仍然偏,但已经好转;加到 1000 个时,迁移比例降到 25.76%,接近理论值。虚拟节点数量越多,环上的点越密,单个节点能占到的弧越接近平均值,迁移和分布都更可控。

分配方案3 台扩到 4 台的迁移比例说明
取模法74.87%除数从 3 变 4,绝大多数 key 重排
一致性哈希,1 个虚拟节点62.92%环上只有三个点,弧长严重不均,新节点吃掉一大段
一致性哈希,100 个虚拟节点36.07%弧被切碎,迁移向四分之一靠拢,但仍有偏斜
一致性哈希,1000 个虚拟节点25.76%接近理论值 25%,分布也更均匀

这组数据说明两件事。第一,一致性哈希不是「一加上就均匀」:只有一个虚拟节点时,它的迁移比例甚至可能比取模法好不了太多,因为新节点落在哪段弧、那段弧有多大,全看运气。第二,虚拟节点是在用空间和查找成本换均匀,点越多越均匀,环结构和内存也越大,每次查找多一层映射。工程上常见的做法是把虚拟节点数量加到分布误差可以接受为止,再按内存和查找成本做取舍。

现象、真实原因与第一步排查

一致性哈希的故障往往不表现为「算法报错」,而是表现为缓存命中率、负载均衡和数据库压力异常。下面这些症状可以帮你快速定位。

现象真实原因第一步查什么
扩容后命中率骤降,数据库压力暴涨仍在用取模法,节点数变化导致大面积 key 重排对比扩容前后每个 key 的归属
加机器后负载仍然严重不均环上虚拟节点太少,弧长分布不均统计每台机器负责的 key 比例
缩容后请求集中到下一台被移除节点的一整段弧交给了顺时针后继看被移除节点的弧长与后继是谁
节点重启后缓存像被清空节点标识变了,环上位置改变,归属整体偏移节点哈希是否使用稳定且统一的标识
迁移期间数据库短时打满搬迁是批量进行的,新节点缓存全是冷的是否限速、预热、分批放量
不同客户端分到的节点不一致哈希函数、虚拟节点数、环配置不一致统一版本与配置,检查节点列表
单个热点 key 压垮一台机器一致性哈希只管分布,不管 key 本身有多热热点 key 是否要拆分或加多副本
环查找耗时随节点数上升虚拟节点过多,且用线性扫描而不是二分环是否有序、查找是否为对数

第一行和第三行是两代分配规则的典型差别:取模法的问题是「全量重排」,一致性哈希的问题是「一段弧整体转移」。后者把影响范围缩小了,但那一段如果恰好很大,仍会在缩容瞬间把压力集中到一台机器。第二行则提醒,虚拟节点数量不够时,一致性哈希也可能退化成「一台特别忙、两台闲着」。

边界与代价:一致性哈希不保证均匀

名字里的「一致性」指的是「节点变动时映射尽量保持」,不是「分布一定均匀」。均匀程度取决于哈希函数和虚拟节点数量,节点少、虚拟节点少时,弧长偏差会很大。它也没有解决热点:如果某一个 key 被请求得特别频繁,无论它落在哪台机器,那台机器都会忙。热点要靠拆分 key、加本地缓存或多副本分担,不能指望换一种分配算法。

迁移也不是免费的。加一台机器,理论上只搬四分之一,但这四分之一仍然可能是几百万条缓存,涉及网络传输、对端写入和旧数据清理。迁移太快会打满带宽和 CPU,太慢又会让新节点长时间空闲。常见做法是限速迁移、分批放量、让新节点先预热一部分数据,同时观察数据库压力,必要时降级或限流。

一致性哈希本身不负责副本和故障转移。节点宕机时,它负责的那段弧会交给后继节点,但数据不会自动出现在后继节点上,缓存会回源重建;如果是持久化分片,还需要副本机制来避免数据丢失。也就是说,它解决的是「key 找谁」,不解决「数据放几份」「坏了怎么办」。

还有一个和上一篇直接相关的约束:环上的哈希必须在所有节点和客户端之间保持一致。上一篇讲的每进程随机种子适合防御碰撞攻击,却不适合做分片,因为种子不同,同一个 key 在不同进程里会算出不同的环位置。分片场景要用固定哈希,或者用所有节点共享密钥的稳定哈希,既保证一致,又不让外部轻易构造热点。

最后是复杂度。环要排序、要二分、要在内存里维护节点和虚拟节点的列表;节点上下线要同步配置,配置不一致就会出现「同一个 key 两个主人」。它比取模法多了不少工程负担,所以只在「节点会经常扩缩容」或者「单台故障不能全量失效」的场景里才划算。节点数量固定、变化很少的小系统,取模法更简单也更省事。

当天能做的练习

  1. 用本文的 fnv1a 和取模法,生成 1 万个 key,模拟 3 台扩到 4 台,统计换了节点的 key 比例,确认接近 74.87%。
  2. 实现一个只有 1 个虚拟节点的一致性哈希环,打印三台机器各自负责的 key 数,观察 A、B、C 的偏斜,并记录最长和最短的弧。
  3. 把虚拟节点数改成 100 和 1000,重复第二步与第一步,记录分布和迁移比例,画出随虚拟节点数量变化的趋势。
  4. 模拟移除一台节点,统计受影响的 key 比例,确认只有该节点负责的那段弧发生迁移,其余 key 不动。
  5. 用「主机名」和「主机名加端口」两种节点标识各建一次环,重启后对比 key 归属,说明标识不稳定会带来什么后果。
环境说明:文中 1 万个 key、FNV-1a、3 台扩到 4 台的迁移比例 74.87%,以及一致性哈希 1 个、100 个、1000 个虚拟节点对应的 62.92%、36.07%、25.76%,均来自本机实际运行;三节点分布 A 2259、B 6916、C 825 与 100 个虚拟节点时的 C 1497、A 3056、B 5447 也来自同一组实验。具体数值会随节点命名、键的命名和哈希实现变化,比例的方向不变。

小结

三句话收一下:取模法把节点总数写进了公式,扩缩容时必然大面积重排;一致性哈希把节点和 key 放到同一个环上,按顺时针找主人,加一台只影响一段弧;虚拟节点把这段弧切碎,数量足够时迁移比例接近节点数加一分之一。

把这一组三篇连起来看:哈希表讲单个进程里「键怎么落到桶」,哈希退化讲「键被构造时单桶会变成一条长链」,一致性哈希讲「键怎么落到多台机器」。三者用的都是同一个哈希函数,但关注的层次不同,一个管桶内冲突,一个管攻击面,一个管节点归属。

下一步可以往两个方向走:一是副本与故障转移,看一段弧的节点挂掉之后数据怎样补齐;二是真实的缓存集群,把虚拟节点、迁移限速、预热和监控落到一套可以上线的方案里。无论走哪边,先记住今天这组数字:取模法 74.87%,一个虚拟节点 62.92%,一千个虚拟节点 25.76%。