环 · vnode · jump hash

一致性哈希：加一台机器要搬多少

把哈希表的槽换成机器，前七页的模型基本照搬：散列函数把 key 映到一个整数，再折算成「归哪台机器」。只有一件事变了——机器数会变，而槽数在单机表里只在扩容时变，且扩容时可以从容 rehash 全表。

集群里不行。 $N$ 台变 $N+1$ 台时，每搬一个 key 就是一次跨机网络传输。取模分片 $h \bmod N$ 的问题正在于此： $N$ 一改，几乎每个 key 的归属都变了。

1 · 取模分片的搬迁量

$h \bmod 4$ 换成 $h \bmod 5$ ，一个 key 归属不变的条件是 $h \bmod 4 = h \bmod 5$ ，这要求 $h \bmod 20$ 落在 $\{0,1,2,3\}$ ——概率 $1/5$ 。所以有 $4/5$ 的 key 要搬。

一般地， $N \to N+1$ 时约有 $1 - 1/(N+1)$ 的 key 换归属，而理论下界只需要 $1/(N+1)$ （新机器总得分到自己那一份）。实测 2 万个 key、4 台变 5 台：取模搬 79.8%，下界 20%。多搬的那 60% 是纯粹的浪费，它们从一台老机器跑到另一台老机器，什么也没改善。

2 · 环把搬迁限制在相邻一段

1997 年 Karger 等人的做法是加一层间接：不把 key 映到机器，而是把 key 与机器一并映到同一个环上（ $0$ 到 $2^{32}-1$ 首尾相接），key 归属它顺时针方向遇到的第一台机器。

图 2-1 · 4 到 5 个节点在环上的分布，弧的颜色是该段的归属。可拖动节点数与每节点的 vnode 数，也可改 key 看它落在哪一段。

关键在于：新机器插进环上某一点，只会从它顺时针方向那一段的原主人手里接走 key，其余机器之间的边界纹丝不动。删除同理。这就把搬迁量从「几乎全部」压到了「一台机器那一份」。

$N = 1$ 时它就是普通的取模； $N$ 大时，每台机器的份额是它在环上占据的弧长总和。

3 · vnode 数决定均衡程度

朴素的环有个毛病：每台机器只在环上放一个点时，弧长由随机散列决定，相邻两点的间距服从指数分布，方差极大。

补救办法是每台机器在环上放 $V$ 个点（虚拟节点 / vnode），份额变成 $V$ 段弧的和，方差按 $1/\sqrt{V}$ 收缩。

单看一组机器名的实测数字会低估这件事的随机性，所以下表换 30 组机器命名各跑一遍，取 4 台机器、2 万个 key 下「最高占比减最低占比」的分布：

每节点 vnode	极差的均值	30 组里最坏的一组
1	49.5%	82.1%
16	12.5%	21.4%
160	4.3%	10.2%
512	2.3%	5.0%

$V = 1$ 时平均极差近 50%，最坏的一组里一台机器几乎独占——集群等于没做负载均衡。收敛也确实慢： $V$ 从 1 提到 160（一百六十倍）极差均值才从 49.5% 降到 4.3%，再翻到 512 只到 2.3%。这就是 $1/\sqrt{V}$ 的形状。生产实现的 vnode 数普遍落在 100 到 200 之间——再往上，收益不足以抵偿环上二分查找的常数与内存。Dynamo 与 Cassandra 的默认值都在这个量级。

搬迁量跟着同一个方差走。同样 30 组命名、4 台加到 5 台，环的搬迁比例： $V = 1$ 时均值 14.5%、标准差 13.6、区间 $[0.3\%, 60.6\%]$ ； $V = 160$ 时均值 19.8%、标准差 1.4、区间 $[17.0\%, 22.4\%]$ 。理论下界是 20%，vnode 够多时均值贴上去了，但单次仍会偏离两三个百分点。

警示 · 环上位置的散列函数必须过一遍位混淆。本系列的引擎最初直接用 fnv1a32("node#0")、fnv1a32("node#1") 生成 vnode 位置，跑出来一台机器拿走 73.9%——把散列值打印出来才看明白：FNV-1a 的最后一个字节只经过一次乘法，#0 与 #1 的结果恒差约 0x01000193，即环周长的 $1/256$ 。同一节点的全部 vnode 于是紧挨成一小撮，等价于只放了一个点，加多少 vnode 都没用。这正是散列函数 §2 那条「一次乘法只把差异往高位搬」的直接后果。补上 fmix32 后，同样 4 节点 4 vnode 的最高占比从 73.9% 回到 31.4%，vnode 提到 160 时极差降到 4.2%。ht.test.ts 里现在锁着一条回归断言：同一节点相邻两个 vnode 在环上的间距不得小于环周长的千分之一。

4 · 不存环也能做

2014 年 Lamping 与 Veach 提出的 jump consistent hash 把整套结构去掉了，只留一个递推：

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (b + 1) * ((double)(1LL << 31) / (double)((key >> 33) + 1));
    }
    return b;
}

思路是直接模拟「桶数从 1 涨到 $N$ 的过程中，这个 key 在哪几步跳过槽」。桶数从 $b$ 加到 $b+1$ 时，每个 key 以 $1/(b+1)$ 的概率跳进新桶——用 key 作种子的伪随机数列可以算出下一次跳跃发生在哪个桶数，于是循环只需要 $O(\ln N)$ 次迭代，且不占任何内存。

图 4-1 · 取模、环、jump hash 三套方案在「加一个节点」时的搬迁比例，与理论下界 1/(N+1) 对照。下方另有 vnode 数与负载极差的关系，以及 jump hash 分十个桶的占比。

实测： $4 \to 5$ 搬 19.710%（理论 20%）， $9 \to 10$ 搬 10.265%， $99 \to 100$ 搬 1.015%。这些数字与环在 $V = 160$ 时的 19.8% 看着差不多，差别在方差：环的那个数是一个随机变量，换一组机器名就落在 $[17.0\%, 22.4\%]$ 的某处；jump hash 根本没有这个自由度，它的输入只有 key 与桶数，剩下的偏差纯粹来自有限的 key 采样。

负载均衡那一侧的对照更直白：4 个桶时 jump hash 的占比是 25.04% · 25.22% · 24.98% · 24.76%，极差 0.46%；环在 $V = 160$ 时的极差均值是 4.3%，最坏一组 10.2%。差了一个量级。均衡是 jump hash 的构造性质，不是采样结果。

代价写在它的接口里：函数签名只有 (key, num_buckets)，没有「哪些桶」这个参数。所以它只支持从尾部加减桶，中间那台机器挂了，它无能为力。环则可以摘掉任意一个节点。这道分界决定了各自的适用场景：jump hash 适合桶即分片编号、扩缩容按编号顺序进行的场景（Google 的存储系统、一致的分片路由）；环适合节点会任意上下线的场景（Dynamo、Cassandra、memcached 客户端）。

5 · Redis Cluster 选了第三条路

Redis Cluster 既没用环也没用 jump hash，而是固定 16384 个 hash slot：key 先算 CRC16(key) mod 16384 得到 slot 号，slot 再由集群配置分配给某个节点。

这实质上是把「一层间接」显式化了——环用虚拟节点做间接，Redis 用一张 slot 到节点的映射表。它的好处是搬迁的粒度与调度完全可控：管理员可以精确指定把哪几个 slot 从哪台机器搬到哪台，CLUSTER SETSLOT 逐个 slot 迁移，过程中该 slot 处于 MIGRATING / IMPORTING 状态，客户端收到 ASK 重定向。环做不到这种粒度的人工干预。

16384 这个数字有个具体的理由：节点之间的心跳消息里要带上「我负责哪些 slot」的位图，16384 位是 2KB；若取 65536 就是 8KB，而 Redis 的集群总节点数上限本就在一千左右，16384 个 slot 已经绰绰有余。这是一个被消息体大小定死的常数，不是从算法里推出来的。

6 · 参考文献

Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M., & Lewin, D. (1997). Consistent hashing and random trees. Proceedings of the 29th ACM Symposium on Theory of Computing, 654–663.
Lamping, J., & Veach, E. (2014). A fast, minimal memory, consistent hash algorithm. arXiv:1406.2294.
DeCandia, G., et al. (2007). Dynamo: Amazon's highly available key-value store. SOSP 2007, 205–220.
Thaler, D. G., & Ravishankar, C. V. (1998). Using name-based mappings to increase hit rates. IEEE/ACM Transactions on Networking, 6(1), 1–14.（rendezvous hashing）
Redis. Cluster specification：hash slot 与 CLUSTER SETSLOT 的迁移协议。