网络算法 #03：Jump Consistent Hash

Jump Consistent Hash 用 5 行代码实现 O(1) 空间、O(ln N) 时间的一致性哈希，扩容时只迁移 1/(N+1) 的 key，被 Google 分布式存储和负载均衡系统广泛采用。

相关文章：轮询与加权轮询 · 最小连接数 · Rendezvous Hashing

目录

问题背景

取模哈希的缺陷

最简单的分片方案是取模哈希：bucket = key % N。当桶数量从 N 变为 N+1 时，几乎所有 key 的映射结果都会发生变化，导致大规模数据迁移。

示例：10 个 key，桶数从 3 扩到 4：

key=0: 0%3=0 → 0%4=0  (不变)
key=1: 1%3=1 → 1%4=1  (不变)
key=2: 2%3=2 → 2%4=2  (不变)
key=3: 3%3=0 → 3%4=3  (迁移)
key=4: 4%3=1 → 4%4=0  (迁移)
key=5: 5%3=2 → 5%4=1  (迁移)
key=6: 6%3=0 → 6%4=2  (迁移)
key=7: 7%3=1 → 7%4=3  (迁移)
...

约 75% 的 key 需要迁移，对生产系统是灾难性的。

一致性哈希的不足

传统一致性哈希（Karger et al. 1997）通过虚拟节点环解决了大规模迁移问题，但：

• 空间复杂度高：需要维护 O(N) 个虚拟节点的哈希环，内存占用随节点数线性增长。
• 实现复杂：需要有序数据结构（如红黑树）维护虚拟节点，查找时需要二分搜索。
• 虚拟节点数量：为保证负载均匀，每个物理节点通常需要 100-200 个虚拟节点。

Jump Consistent Hash 的定位

Google 2014 年发表的论文提出 Jump Consistent Hash，目标是：

• O(1) 空间：不需要存储任何哈希环或虚拟节点。
• O(ln N) 时间：迭代次数随桶数增长缓慢（100 个桶约迭代 7 次）。
• 最优迁移代价：扩容时恰好只有 1/(N+1) 的 key 迁移到新桶。
• 代码极简：核心实现仅 5 行。

核心算法

核心数据结构

算法只需两个局部变量，无任何外部状态：

完整伪代码

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;
}

关键常数说明

核心公式解读

j = (b + 1) * (2^31 / ((key >> 33) + 1))

设 r = (key >> 33 + 1) / 2^31，则 r 是 (0, 1] 之间的伪随机数，公式等价于：

j = floor((b + 1) / r)

这意味着：以概率 1/(b+2) 跳到桶 b+1，以更小概率跳到更远的桶。

算法原理推导

核心问题

给定 key，桶数从 N 扩到 N+1 时，哪些 key 应该跳到新桶 N？

答案：恰好 1/(N+1) 比例的 key 应该跳到新桶，且每个 key 跳到新桶的概率相等（均为 1/(N+1)）。这是负载均衡的最优解。

概率递推

设 ch(key, n) 为 key 在 n 个桶时的分配桶号。当桶数从 n 扩到 n+1 时：

• key 留在原桶的概率：n/(n+1)
• key 跳到新桶 n 的概率：1/(n+1)

因此，ch(key, n+1) 的值：

• 若随机数 r > n/(n+1)，则 ch(key, n+1) = n（跳到新桶）
• 否则，ch(key, n+1) = ch(key, n)（保持不变）

从递推到迭代

直接递推需要 O(N) 步。关键优化是跳跃：对于给定 key，在某个桶号 b 处，直接计算下一次「发生跳跃」的桶号 j。

设当前在桶 b，下一次跳跃发生在桶 j（即 key 在 b+1..j-1 这些桶都「选择留下」，在桶 j 选择「跳到新桶」）。

j 的期望公式：给定伪随机数 r ∈ (0,1]，令 j = floor((b+1)/r)，使得 j > b 且跳跃位置服从正确的概率分布。

线性同余生成器

每次迭代用 key = key * M + 1 更新 key 作为伪随机源，保证：

• 确定性：相同的 key 每次产生相同的随机序列
• 均匀性：高位 31 位（key >> 33）的分布接近均匀
• 效率：单条乘法指令，硬件原生支持

执行追踪

输入：key = 12345678，num_buckets = 5

初始状态：b = -1，j = 0

迭代 1（j=0 < 5，继续）：

b = 0
key = 12345678 * 2862933555777941757 + 1
    = 12345678 * 0x27BB2EE687B0B0FD + 1
    = 9647097690860584595  (mod 2^64)
key >> 33 = 9647097690860584595 >> 33 = 1125557...  ≈ 1125557899
r = (1125557899 + 1) / 2^31 ≈ 0.5239
j = floor((0 + 1) / 0.5239) = floor(1.909) = 1

状态：b=0, j=1

迭代 2（j=1 < 5，继续）：

b = 1
key = 9647097690860584595 * 2862933555777941757 + 1
    = 3421679987654321001  (mod 2^64，示意值)
key >> 33 ≈ 399123456
r = (399123456 + 1) / 2^31 ≈ 0.1858
j = floor((1 + 1) / 0.1858) = floor(10.76) = 10

状态：b=1, j=10

迭代 3（j=10 >= 5，退出循环）：

while (10 < 5) → false，退出
return b = 1

结果：key=12345678 被分配到桶 1。

追踪说明：算法在 j 第一次超出 num_buckets 时停止，b 保存的是最后一次合法的桶号。迭代次数为 O(ln N)：5 个桶约迭代 2-3 次，1000 个桶约迭代 7 次。

迁移代价证明

结论

当桶数从 N 扩到 N+1 时，恰好有 1/(N+1) 比例的 key 迁移到新桶 N，其余 N/(N+1) 的 key 保持不变。

直觉证明

设有 K 个 key 均匀分布在 N 个桶中，每个桶平均有 K/N 个 key。

扩容后有 N+1 个桶，为了保持均匀，每个桶平均有 K/(N+1) 个 key。

新桶 N 需要接收 K/(N+1) 个 key，占总量的 1/(N+1)。

这 K/(N+1) 个 key 来自原来的 N 个桶，每个桶贡献 (K/N) - (K/(N+1)) = K/(N(N+1)) 个 key，即每个桶迁移比例为：

(K/(N(N+1))) / (K/N) = 1/(N+1)

每个桶迁移相同比例，负载均衡最优。

算法实现的保证

Jump Consistent Hash 通过线性同余生成器产生的伪随机序列，保证对于任意 key：

• 在桶数为 n 时，key 被分配到每个桶的概率均为 1/n
• 扩容到 n+1 时，key 跳到新桶的概率恰好为 1/(n+1)

这个概率由 j = floor((b+1)/r) 公式精确控制。

异常与边界场景

场景 1：num_buckets = 0

JumpConsistentHash(key, 0)

分析：初始 j = 0，循环条件 j < 0 为 false，直接退出。返回 b = -1。

处理：调用方必须检查返回值是否为 -1，并抛出异常或返回错误。不能直接将 -1 作为桶号使用。

int bucket = JumpConsistentHash(key, numBuckets);
if (bucket < 0) throw new IllegalArgumentException("num_buckets must be >= 1");

场景 2：num_buckets = 1

JumpConsistentHash(key, 1)

分析：初始 j = 0，进入循环，b = 0，然后计算新 j。由于任何正数 floor((0+1)/r) >= 1，新 j >= 1，循环退出。

结果：所有 key 都返回 0，符合预期——只有一个桶时所有请求都分配到同一桶。

场景 3：key 分布不均匀（哈希质量差）

问题：Jump Consistent Hash 假设输入 key 的低位具有足够随机性。如果 key 本身分布不均（如全为偶数、递增整数），可能导致负载不均。

分析：算法内部使用 key >> 33（高位），但初始 key 的低位偏斜仍会通过线性同余传播到后续迭代，影响均匀性。

解决：在调用前先对 key 做一次哈希预处理：

// 使用 MurmurHash3 或 xxHash 预处理 key
long hashedKey = MurmurHash3.hash64(originalKey);
int bucket = JumpConsistentHash(hashedKey, numBuckets);

场景 4：节点缩容（不连续编号）

问题：Jump Consistent Hash 要求桶编号连续（0..N-1）。如果删除的不是最后一个节点（如删除中间节点 5），节点编号出现空洞，算法无法直接处理。

解决方案：

1. 重映射表：维护逻辑桶号到物理节点的映射，缩容时只删除最后一个逻辑桶并更新映射表。
2. 只缩减末尾节点：业务上约定只允许删除编号最大的节点，维持连续性。
3. 切换算法：需要频繁不规则增删节点时，改用传统一致性哈希。

与一致性哈希对比

选择建议

• 选 Jump Consistent Hash：存储分片（节点只增不删）、CDN 节点（机器有序扩容）、批量计算任务分发。
• 选传统一致性哈希：服务发现（节点随时上下线）、缓存代理（任意节点故障转移）。

实际应用

Google 内部负载均衡

Jump Consistent Hash 出自 Google 论文，在 Google 内部用于：

• Bigtable：分片到 tablet server，节点数量稳定增长。
• Guice/gRPC 负载均衡：客户端将请求按 key 路由到特定后端分片。

分布式存储分片

适用于分片数量单调递增的存储系统：

// 示例：按 userId 路由到存储分片
public int getShardId(long userId, int totalShards) {
    return JumpConsistentHash.hash(userId, totalShards);
}

扩容时（totalShards 从 N 增到 N+1），只有 1/(N+1) 的用户数据需要从旧分片迁移到新分片，迁移脚本逻辑简单且数据量可控。

CDN 节点选择

对于内容 CDN，将内容 ID 哈希到边缘节点：

node = JumpConsistentHash(contentId, edgeNodeCount)

新增边缘节点时，只有少量内容需要从其他节点迁移，大部分内容缓存仍然有效（缓存命中率不会骤降）。

数据库水平分表

-- 逻辑：将 user_id 映射到分表编号
table_index = JumpConsistentHash(user_id, table_count)
-- 查询表：user_{table_index}

扩表时（table_count++），只有 1/(table_count) 的数据需要迁移，可以在业务低峰期逐步完成。

参考资料

1. 原始论文：Lamping, J., & Veach, E. (2014). A Fast, Minimal Memory, Consistent Hash Algorithm. arXiv:1406.2294. https://arxiv.org/abs/1406.2294
2. Knuth 乘法因子：Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Section 3.2.1, Linear Congruential Method.
3. 一致性哈希原始论文：Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M., & Lewin, D. (1997). Consistent Hashing and Random Trees. STOC 1997.
4. Java 实现参考：Google Guava Hashing.consistentHash(). https://guava.dev/releases/snapshot/api/docs/com/google/common/hash/Hashing.html#consistentHash(com.google.common.hash.HashCode,int)
5. Go 实现：stathat/consistent 与 dgryski/go-jump. https://github.com/dgryski/go-jump