一致性哈希

当节点数变化时,如何让尽可能少的数据需要迁移?一致性哈希把节点和数据映射到同一个环上,每个 key 顺时针找最近的节点——加减节点时只影响相邻区间。虚拟节点进一步让负载更均匀,代价是路由表变大。

问题: 节点数量变化时最小化数据迁移

普通的 hash(key) % N：N 个节点 → 增删节点 → 所有 key 的映射都变了 → 全部数据要迁移。一致性哈希解决：增删节点时只有 K/N 的 key 需要迁移⁠（K 是 key 总数）。

Hash Ring + Virtual Nodes (Chord/Dynamo 方案)

算法

1. 对每个节点: 计算 hash(node_id) → 映射到 ring [0, 2^32) 上
2. 对每个 key: 计算 hash(key) → 映射到 ring 上
3. key 被分配给: 从 key 的位置顺时针走遇到的第一个 node

增删节点:
  - 加 node: 只有新 node 和它逆时针上一个 node 之间的 key 需要迁移到新 node
  - 删 node: 该 node 的 key 迁移到顺时针下一个 node

Virtual Nodes (Vnodes)

物理节点数量少时（如 5 个），ring 上节点分布不均 → 数据倾斜。Virtual nodes: 每个物理节点对应 V 个虚拟节点（通常 100-200），随机分布在 ring 上。

• 每个物理节点的 Vnodes 越多 → 负载越均匀
• Vnode 数量与物理节点无关 → 加物理节点时只需重新 assign 部分 vnodes 到新物理节点

Dynamo/Cassandra: 每个物理节点在 ring 上有 256 个 vnodes。

Jump Hash (Google 方案)

不需要存储 ring 结构，O(log N) 计算 key 属于哪个 bucket：

int jump_consistent_hash(uint64_t key, int num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        double r = random_next(key, j);  // deterministic PRNG
        j = floor((b + 1) / r);
    }
    return b;
}

性质：每个 bucket 概率相同 (1/num_buckets)。增删 bucket 时只有 1/num_buckets 的 key 需迁移。不需要 ring 数据结构。

限制：buckets 必须是连续编号 (0..N-1)，不支持任意 node_id。不支持加权（所有 bucket 权重相同）。

Google 用它做 CDN cache sharding 和 storage bucket 分配。

Rendezvous Hash (HRW: Highest Random Weight)

每个 key 对每个 node 计算 score，选最高分：

for each node N:
    score = hash(key, node_id)
assign key to: node with highest score

增删 node：只影响 score 最高的 node 改变的 key。与 jump hash 一个重要的区别：即使 nodes 数量变了，⁠只有原来被分配给该 node 的 key 会受影响⁠——其他 key 的 winner 不变。

特性：天然支持加权 (score = hash(key, node_id) / weight)。不需要任何全局状态。

应用：Apache Ignite, HAProxy (consistent balancing with balance url_param)。

对比

参考

• 论文⁠: "Consistent Hashing and Random Trees" (Karger et al, 1997)
• 论文⁠: "A Fast, Minimal Memory, Consistent Hash Algorithm" (Lamping & Veach, 2014 — jump hash)
• Dynamo: "Dynamo: Amazon's Highly Available Key-value Store" (2007, section 4.5)

Keywords: consistent hashing, hash ring, virtual nodes, vnodes, jump hash, rendezvous hash, highest random weight