📚 课程目录第3章哈希分区（上）

3、哈希分区（上）：一致性哈希原理、虚拟节点技术、环状空间与数据映射

哈希分区，说白了就是给每个数据算个「身份证号」，然后按号分配节点。但这里有个坑——节点数量一变，所有数据的身份证号都得重算。我在早期做缓存集群时就吃过这个亏，扩容一次，缓存雪崩一次，数据库差点被打挂。

那怎么办？一致性哈希就是来救场的。它不直接对节点数量取模，而是把哈希值空间组织成一个环。你想想看，这样一来，节点增减只影响环上的一小段数据，而不是全局洗牌。

环状空间：把哈希值首尾相连

先看一个常规哈希：hash(key) % N。N 是节点数。N 一变，结果全变。一致性哈希的做法是——把哈希函数的输出范围（比如 0 到 2^32-1）想象成一个首尾相接的环。

每个节点用自己的标识（比如 IP 或名称）算哈希，落在环上的某个位置。每个数据 key 也算哈希，落在环上。然后数据归谁管？顺时针找到的第一个节点。

我画个图你就明白了。

你看这个环。key1 顺时针遇到的第一个节点是 B，所以它归 B 管。key2 顺时针找到 C，key3 找到 D。这个映射关系一旦确定，只要节点不增不减，就不会变。

节点增减的影响范围

这才是核心优势。假设节点 C 挂了，环上少了 C。原来归 C 的数据，顺时针找下一个节点——也就是 D。只有 C 和 D 之间的数据需要迁移。A、B 的数据纹丝不动。

关键结论：一致性哈希把节点增减的影响范围，从「全局」缩小到了「相邻区间」。节点数越多，影响比例越小。

反过来，新增一个节点 E，它落在环上某处。只有 E 和它逆时针方向上一个节点之间的数据需要重新分配。其他节点完全不受影响。

我在项目中遇到过一个问题：节点太少的时候，环上的分布很不均匀。比如只有 3 个节点，它们可能扎堆在环的一侧，导致某个节点管了一大片数据，其他节点却很闲。这就是「数据倾斜」。

虚拟节点技术：解决倾斜的利器

怎么解决？虚拟节点。每个物理节点在环上不是只占一个位置，而是占多个位置。每个位置对应一个「虚拟节点」。物理节点 A 可以虚拟出 A-1、A-2、A-3……一直到 A-N，每个虚拟节点都算一次哈希，散落在环上。

这样一来，环上的节点数量从几个变成了几百上千个。分布自然就均匀了。

对比项	无虚拟节点	有虚拟节点
环上节点数	物理节点数（通常 3~10）	物理节点 × 虚拟因子（通常 100~1000）
数据分布均匀性	差，容易倾斜	好，接近均匀
节点增减影响	相邻区间数据迁移	多个虚拟节点分担迁移量
实现复杂度	低	中等（需维护虚拟→物理映射）

虚拟因子的选择有讲究。我个人的习惯是：物理节点少于 10 个时，虚拟因子设 200~500；节点数超过 50 时，虚拟因子降到 50~100 就够了。太多了反而增加内存开销和查找延迟。

经验之谈：虚拟节点的哈希计算要保证「同一物理节点的不同虚拟节点」哈希值尽量分散。我见过有人用 hash(ip + ":" + index)，效果不错。别用简单的递增数字，容易扎堆。

数据映射的完整流程

来，走一遍完整流程。假设我们有 3 个物理节点，每个配 100 个虚拟节点。

初始化环：对每个虚拟节点计算哈希，按值排序，存入一个有序列表（比如红黑树或跳表）。
数据写入：计算 key 的哈希，在有序列表中做二分查找，找到第一个大于等于该哈希值的虚拟节点。
映射到物理节点：通过虚拟节点 ID 找到对应的物理节点，写入数据。
数据读取：同样的流程，找到虚拟节点，再找到物理节点，读取数据。
节点扩容：新节点加入，生成它的虚拟节点，插入有序列表。只有落在新节点逆时针方向上一个虚拟节点之间的数据需要迁移。
节点缩容：节点下线，移除它的所有虚拟节点。这些虚拟节点负责的数据，顺时针交给下一个虚拟节点。

这里有个细节：二分查找的时间复杂度是 O(log N)，N 是虚拟节点总数。1000 个虚拟节点，查找只要 10 次比较。性能完全不是问题。

注意：虚拟节点列表必须支持高效的插入和删除。我建议用平衡树结构（TreeMap 或类似实现），不要用数组。数组插入和删除是 O(N)，节点频繁变动时会成为瓶颈。

一个简单的代码示意

我用伪代码展示核心逻辑，方便你理解数据结构的组织方式。

// 虚拟节点映射表：虚拟节点哈希值 → 物理节点 ID
TreeMap<Integer, String> virtualNodes = new TreeMap<>();

// 初始化：为每个物理节点创建虚拟节点
for (String physicalNode : physicalNodes) {
    for (int i = 0; i < VIRTUAL_COUNT; i++) {
        String vnodeKey = physicalNode + ":" + i;
        int hash = hash(vnodeKey);
        virtualNodes.put(hash, physicalNode);
    }
}

// 查找数据归属
String findNode(String dataKey) {
    int hash = hash(dataKey);
    // 找到第一个大于等于 hash 的虚拟节点
    Map.Entry<Integer, String> entry = virtualNodes.ceilingEntry(hash);
    if (entry == null) {
        // 如果超出环尾，回到环头
        entry = virtualNodes.firstEntry();
    }
    return entry.getValue();
}

这段代码虽然简单，但已经能跑通核心流程了。实际生产环境要考虑的事情更多——比如虚拟节点列表的持久化、数据迁移的并发控制、以及节点故障时的快速检测。这些后面章节会展开。

一致性哈希的局限

没有银弹。一致性哈希也有它的短板。

数据迁移粒度粗：虽然只影响相邻区间，但迁移的单位是整个虚拟节点负责的数据段。如果某个虚拟节点恰好管了热点数据，迁移量可能很大。
负载不均衡的极端情况：虚拟节点再多，也做不到完全均匀。某些物理节点可能因为哈希碰撞而多管几个虚拟节点。
不支持权重：所有物理节点默认平等。如果机器配置不同（比如一台 128G 内存，另一台 32G），没法让高配机器多管数据。

针对最后一点，我后来在项目中用了「带权虚拟节点」——高配机器的虚拟因子设大一些，低配的设小一些。效果不错，但需要手动调参。有没有更优雅的方案？有的，后面讲「负载感知分区」时会提到。

嗯，一致性哈希的原理和虚拟节点技术就先说到这。你想想看，它本质上是用「空间换稳定」——多维护一个环状结构和虚拟节点映射，换来节点变动时的小范围数据迁移。这个 trade-off，在大多数分布式系统中是值得的。