3. 缓存路由原理：一致性哈希算法详解，虚拟节点与数据倾斜问题

在分布式缓存系统中，当缓存节点数量发生变化（扩缩容）时，传统取模哈希会导致大量缓存键失效，引发缓存雪崩。一致性哈希算法通过将哈希值空间组织成环形结构，将节点与数据映射到环上，从而将节点变动的影响范围控制在相邻节点之间，是实现缓存路由与一致性调优的核心基础。

3.1 一致性哈希环形空间与路由规则

一致性哈希将哈希函数的输出值域（如 SHA-1 的 0 ~ 2^160-1）首尾相连，形成一个虚拟的哈希环。缓存节点与数据键均通过相同的哈希函数映射到环上的某个位置。数据键沿环顺时针方向查找，遇到的第一个节点即为该键的归属节点。

下图展示了一个包含 4 个物理节点（Node A ~ Node D）的一致性哈希环，以及数据键 Key-1 到 Key-6 的路由归属关系。

3.2 节点增减的影响范围

一致性哈希的最大优势在于节点变动时，只有少量缓存键需要重新映射。下表对比了传统取模哈希与一致性哈希在节点增减时的失效键比例。

3.3 数据倾斜问题与虚拟节点机制

当物理节点数量较少时，哈希函数随机性不足可能导致节点在环上分布不均，造成某些节点负责的哈希区间远大于其他节点，即数据倾斜。倾斜会导致部分节点负载过高，而其他节点资源闲置，严重时引发热点故障。

虚拟节点（Virtual Node）是解决数据倾斜的标准方案。每个物理节点在环上注册多个虚拟节点（如 100~200 个），虚拟节点继承物理节点的处理能力。哈希环上的路由先定位到虚拟节点，再映射到物理节点。虚拟节点数量越多，分布越均匀，数据倾斜程度越低。

下图对比了无虚拟节点与引入虚拟节点后的环上分布情况，直观展示虚拟节点如何改善均匀性。

3.4 虚拟节点数量选择与性能权衡

虚拟节点副本数 k 的选择需要在均匀性与路由表大小之间取得平衡。下表给出了不同规模下的推荐配置。

3.5 一致性哈希的工程实现要点

在实现一致性哈希路由组件时，需关注以下关键环节：

1. 哈希函数选择： 推荐使用 SHA-256 或 MurmurHash3，避免使用 CRC32 等易碰撞的算法。哈希值空间应足够大（≥ 2^64），降低碰撞概率。
2. 虚拟节点生成策略： 采用“物理节点标识 + 序号”拼接后哈希，确保不同物理节点的虚拟节点在环上均匀交错。
3. 路由表数据结构： 使用有序映射（如 TreeMap、跳表）存储虚拟节点哈希值到物理节点的映射，支持 O(log N) 的顺时针查找。
4. 节点变更处理： 增删节点时，仅重建受影响虚拟节点的路由条目，避免全量重建。变更期间可引入读写锁或 Copy-on-Write 机制保证路由一致性。

// 一致性哈希路由核心伪代码（Java 风格）
public class ConsistentHashRouter {
    private final TreeMap<Long, String> virtualNodes = new TreeMap<>();
    private final int replicaCount;

    public ConsistentHashRouter(List<String> physicalNodes, int replicaCount) {
        this.replicaCount = replicaCount;
        for (String node : physicalNodes) {
            addNode(node);
        }
    }

    public void addNode(String node) {
        for (int i = 0; i < replicaCount; i++) {
            long hash = hash(node + "#" + i);
            virtualNodes.put(hash, node);
        }
    }

    public void removeNode(String node) {
        for (int i = 0; i < replicaCount; i++) {
            long hash = hash(node + "#" + i);
            virtualNodes.remove(hash);
        }
    }

    public String route(String key) {
        if (virtualNodes.isEmpty()) return null;
        long hash = hash(key);
        Map.Entry<Long, String> entry = virtualNodes.ceilingEntry(hash);
        if (entry == null) {
            entry = virtualNodes.firstEntry(); // 环尾回到环首
        }
        return entry.getValue();
    }

    private long hash(String key) {
        // 使用 MurmurHash3 或 SHA-256 实现
        return MurmurHash3.hash64(key);
    }
}