一致性哈希算法

一、问题

普通取模：

hash(key) % N

N 变了，所有 key 都要重新映射。

二、一致性哈希

把 hash 值空间组织成环（0 ~ 2³²-1）。

节点

服务器 hash 后放到环上。

路由

key 顺时针找到第一个节点。

增减节点

• 加节点：只影响一段。
• 减节点：那段迁移到下一个。

三、数据倾斜

节点少，分布不均。

虚拟节点

每个节点对应多个虚拟节点，放到环上。

一个真实节点 → 100 个虚拟节点。

四、Java 实现

TreeMap<Integer, String> ring = new TreeMap<>();

void addNode(String node) {
    ring.put(hash(node), node);
}

String getNode(String key) {
    int h = hash(key);
    Map.Entry<Integer, String> e = ring.ceilingEntry(h);
    return e == null ? ring.firstEntry().getValue() : e.getValue();
}

五、应用

• 分布式缓存。
• 分布式存储。
• 负载均衡。

一句话

一致性哈希 = 环 + 虚拟节点，加节点只迁移一部分数据。