一致性哈希：分布式缓存里的数据分配算法

我对“一致性哈希：分布式缓存里的数据分配算法”的理解经历过一个从会背到会用的过程。其中最明显的一点是：我最初做缓存分片只想到对节点数取模，节点一扩缩容，大量键同时迁移的问题很快就暴露出来。后来每次看到结论，我都会追问它省掉了哪一步、又付出了什么代价，这也是这篇文章的主线。

一致性哈希常用于分布式缓存、分布式存储和负载分配。它解决的问题是：当节点增加或减少时，如何尽量少迁移数据。

它从哪里来

一致性哈希由 David Karger 等人在 1997 年提出，用于分布式缓存等节点会变化的系统。普通取模在节点数量变化后会让大量键重新映射；哈希环和虚拟节点则把迁移限制在局部范围。

普通取模的问题

最简单的分片方式是：

nodeIndex = hash(key) % nodeCount;

如果有 3 个节点，这个方法看起来很自然。但一旦节点数从 3 变成 4，大量 key 的取模结果都会变化，缓存会大面积失效。

一致性哈希环

图：key 顺时针找到第一个节点；节点变化时只影响局部区间

一致性哈希把哈希空间看成一个环：

把服务器节点 hash 到环上。
把数据 key 也 hash 到环上。
key 顺时针找到的第一个节点，就是负责它的节点。

当新增一个节点时，只会接管它逆时针方向到前一个节点之间的数据；当删除一个节点时，也只需要把它负责的数据交给下一个节点。

虚拟节点

如果真实节点数量少，节点在环上分布可能不均匀，导致某些机器压力很大。虚拟节点可以缓解这个问题。

做法是：给每台真实机器创建多个虚拟节点。

node-A#1, node-A#2, node-A#3
node-B#1, node-B#2, node-B#3
node-C#1, node-C#2, node-C#3

每个虚拟节点都 hash 到环上，最终再映射回真实节点。

简化实现

class ConsistentHash {
    private final TreeMap<Integer, String> ring = new TreeMap<>();
    private final int replicas;

    ConsistentHash(int replicas) {
        this.replicas = replicas;
    }

    void addNode(String node) {
        for (int i = 0; i < replicas; i++) {
            ring.put(hash(node + "#" + i), node);
        }
    }

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

TreeMap 用来找到大于等于当前 hash 的第一个节点。如果找不到，就回到环的起点。

工程注意点

一致性哈希不是分布式系统的全部答案。真实落地还要考虑：

节点权重：大机器应该承载更多虚拟节点。
故障探测：节点挂了要及时摘除。
数据迁移：新增节点后是否主动预热。
热点 key：单个 key 太热时，一致性哈希也救不了。
副本策略：缓存或存储通常需要多个副本提高可靠性。

我的分析

一致性哈希的核心价值是“降低变化成本”。它不是让数据永远不迁移，而是让节点变化时只迁移局部数据。

我会把它放在数据结构与算法专题里，是因为它很好地连接了哈希、环形空间、有序查找和工程分布式问题。学完它以后，再看缓存集群、网关负载、分布式存储，会更容易理解。

面试题

普通 hash(key) % n 在扩容时有什么问题？
一致性哈希为什么能减少数据迁移？
虚拟节点解决什么问题？
一致性哈希能否解决热点 key？
一致性哈希和 Redis Cluster 槽位思想有什么相似和不同？