---
title: 一致性哈希
url: https://doc.liz6.com/distributed-systems/04-partitioning-and-routing/01-consistent-hashing
locale: zh
area: distributed-systems
tags:
- distributed-systems
- 分区与路由
date: 2026-06-30
modified: 2026-06-30
description: 当节点数变化时,如何让尽可能少的数据需要迁移?一致性哈希把节点和数据映射到同一个环上,每个 key 顺时针找最近的节点——加减节点时只影响相邻区间。虚拟节点进一步让负载更均匀,代价是路由表变大。
---

# 一致性哈希

> 当节点数变化时,如何让尽可能少的数据需要迁移?一致性哈希把节点和数据映射到同一个环上,每个 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`)。

## 对比

| | Hash Ring + Vnodes | Jump Hash | Rendezvous |
|---|---|---|---|
| 内存 | O(V * N) | O(1) | O(1) per node，O(N) to compute |
| 查询 | O(log(V*N)) + binary search on ring | O(log N) | O(N) per key |
| 迁移 | ~1/N keys | ~1/N keys | ~1/N keys |
| 加权 | 可 (vnode count) | 不可 | 天然 |
| 适用 | N 不常变, 需要任意 node_id | N 常变, 内存紧张 | N 不大 (< 1000) |

## 参考

- **论文**: "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*