网络算法 #07：经典一致性哈希（虚拟节点）

经典一致性哈希将哈希空间映射为环，节点和 key 均匀散布其上，扩缩容时只迁移 1/(N+1) 的数据；虚拟节点进一步解决物理节点数量少时的负载不均问题，是 Cassandra、Memcached、Amazon Dynamo 的核心分片机制。

相关文章：Jump Consistent Hash · Rendezvous Hashing

目录

问题背景

最简单的分片方案是取模哈希：bucket = hash(key) % N。

当节点数从 N 扩容到 N+1 时，绝大多数 key 的目标节点都会改变——对 10 个节点扩到 11 个的场景，约 91% 的 key 需要迁移，对生产系统是灾难性的。

一致性哈希的目标：

扩缩容时，只让受影响的最少数量的 key 发生迁移。

理论下界是 1/(N+1)（N 为扩容后节点数），经典一致性哈希正好达到这个下界。

哈希环模型

核心思想

将哈希空间 [0, 2³²) 首尾相连，弯成一个逻辑上的环。

1. 节点映射：对每个物理节点计算 hash(node_id)，将其放置到环上对应位置。
2. key 映射：对 key 计算 hash(key)，顺时针找到第一个节点，该节点即为 key 的归属节点。

环位置示意（简化为 0~100）：

  节点A @ 10      节点B @ 40      节点C @ 70
    |               |               |
────●───────────────●───────────────●────▶ 环（首尾相连）
    0              40              70   100/0

key=25 → 顺时针 → 节点B（@ 40）
key=80 → 顺时针 → 节点A（@ 10，绕过 100/0 边界）

取模哈希 vs 一致性哈希

虚拟节点

问题：物理节点少时负载不均

若只有 3 个物理节点，它们在环上的位置取决于 hash(node_id)。哈希函数的随机性无法保证 3 个点均匀分布，可能出现某个节点负责 60% 的 key 而另一个节点只负责 10% 的极端情况。

解决方案：每个物理节点映射多个虚拟节点

将每个物理节点 N 拆分为 K 个虚拟节点（vN_1, vN_2, ..., vN_K），分散放置到环上的 K 个位置。

物理节点 A → 虚拟节点 vA1 @ hash("A#1")
             虚拟节点 vA2 @ hash("A#2")
             虚拟节点 vA3 @ hash("A#3")

效果：K 越大，各物理节点负责的 key 比例越接近 1/N（大数定律）。实践中 K 取 100～200 即可达到良好均匀性。

均匀性与 K 的关系

核心操作

数据结构

用有序 Map（TreeMap）维护 虚拟节点哈希值 → 物理节点 的映射：

TreeMap<Long, Node> ring:
  10  → 节点A（vA3）
  25  → 节点C（vC2）
  40  → 节点B（vB1）
  55  → 节点A（vA1）
  ...

查找（O(log N)）

1. hash(key) → 哈希值 h
2. ring.ceilingEntry(h)  ← 找 ≥ h 的最小键
3. 若不存在（h 超过最大虚拟节点）→ ring.firstEntry()  ← 绕环
4. 返回对应的物理节点

添加节点

1. 为新节点生成 K 个虚拟节点：hash("newNode#1") ... hash("newNode#K")
2. 将 K 个虚拟节点插入 TreeMap
3. 对每个新虚拟节点 vN：
   原来负责 vN 所在区间的节点 → 将该区间的 key 迁移给 vN

迁移量：约 K / (原虚拟节点总数 + K) ≈ 1/(N+1)

删除节点

1. 找到该节点的所有 K 个虚拟节点
2. 从 TreeMap 中删除这 K 项
3. 受影响的 key（原归属这 K 个虚拟节点的）→ 顺时针迁移到下一个节点

迁移代价证明

设环上有 N 个物理节点，每节点 K 个虚拟节点，共 NK 个虚拟节点均匀分布。

新增 1 个节点（K 个新虚拟节点）后，总虚拟节点数变为 (N+1)K。

每个新虚拟节点 vNew_i 插入环后，只"抢走"其前驱到自身这段弧上的 key，来自原本负责这段区间的旧节点。

$$ \text{迁移比例} = \frac{K}{(N+1)K} = \frac{1}{N+1} $$

这正是理论最优值——不可能做到更少，因为新节点必须承担 1/(N+1) 的总负载。

Java 实现

import java.security.MessageDigest;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHash<T> {

    private final int virtualNodes;           // 每个物理节点的虚拟节点数
    private final TreeMap<Long, T> ring = new TreeMap<>();

    public ConsistentHash(int virtualNodes) {
        this.virtualNodes = virtualNodes;
    }

    /** 添加物理节点 */
    public void addNode(T node) {
        for (int i = 0; i < virtualNodes; i++) {
            long hash = hash(node.toString() + "#" + i);
            ring.put(hash, node);
        }
    }

    /** 删除物理节点 */
    public void removeNode(T node) {
        for (int i = 0; i < virtualNodes; i++) {
            long hash = hash(node.toString() + "#" + i);
            ring.remove(hash);
        }
    }

    /** 查找 key 归属的物理节点 */
    public T getNode(String key) {
        if (ring.isEmpty()) return null;
        long h = hash(key);
        // ceilingKey：找 >= h 的最小虚拟节点
        Long target = ring.ceilingKey(h);
        if (target == null) {
            target = ring.firstKey(); // 绕环
        }
        return ring.get(target);
    }

    /** MD5 取低 32 位作为哈希值 */
    private long hash(String key) {
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            byte[] digest = md.digest(key.getBytes("UTF-8"));
            // 取前 4 字节组成 unsigned int
            return ((long)(digest[3] & 0xFF) << 24)
                 | ((long)(digest[2] & 0xFF) << 16)
                 | ((long)(digest[1] & 0xFF) <<  8)
                 |  (long)(digest[0] & 0xFF);
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }
}

使用示例：

ConsistentHash<String> ch = new ConsistentHash<>(150); // 每节点 150 个虚拟节点
ch.addNode("server-1");
ch.addNode("server-2");
ch.addNode("server-3");

String node = ch.getNode("user:12345"); // → "server-2"（示例）

复杂度：

与 Jump CH / Rendezvous 对比

选型建议：节点可以任意增删、需要权重差异 → 经典一致性哈希；节点只增不删、追求极简实现 → Jump CH；需要副本选择或 CDN 边缘调度 → Rendezvous。

实际应用

Apache Cassandra

Cassandra 使用一致性哈希对数据行进行分区：

• 每行的 partition key 经过 Murmur3 哈希后映射到环上的 token
• 每个节点负责一段 token 范围（token range）
• 虚拟节点（vnodes）默认每物理节点 256 个，保证自动负载均衡
• 新节点加入时，自动从相邻节点接收部分 token 范围，无需手动迁移

Memcached（libmemcached）

libmemcached 客户端实现了一致性哈希模式（--enable-consistent-hashing）：

• 默认每节点 160 个虚拟节点
• 使用 ketama 算法（MD5 哈希）
• 服务端节点增删时，只有对应区间的 key 失效，不会全量 miss

Amazon Dynamo

Amazon Dynamo（DynamoDB 前身）论文（2007）中描述了一致性哈希的工业化实践：

• 将哈希环划分为等大小的 Q 个区间（Q >> N × S，N 为节点数，S 为每节点虚拟节点数）
• 每个节点随机负责多个不连续区间，天然容灾
• 采用向量时钟（Vector Clock）处理并发写冲突

参考资料

参考资料

• Apache Cassandra Architecture — Dynamo
• Amazon Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007)
• Karger et al., Consistent Hashing and Random Trees (STOC 1997) — 奠基论文，ACM DL 收录
• Jump Consistent Hash（改进方案：O(1) 空间，但不支持任意删除）
• Rendezvous Hashing（改进方案：天然支持副本选择）