一、什么是一致性哈希

一致性哈希算法（Consistent Hashing）是一种特殊的哈希算法，在移除或添加服务器时，能够尽可能小地改变已存在的键值映射关系。主要应用于分布式缓存系统中，解决节点动态增减时的数据重新分配问题。

传统哈希的问题

假设有 3 台缓存服务器，使用传统取模方式分配数据：

int serverIndex = hash(key) % serverCount;

当服务器数量变化时：

  • 增加节点：serverCount 从 3 变为 4，大部分数据的映射关系都会改变
  • 删除节点：serverCount 从 3 变为 2，同样导致大量数据重新分配

这会导致缓存大面积失效，引发缓存雪崩。

二、一致性哈希原理

2.1 哈希环

一致性哈希将整个哈希值空间组织成一个虚拟的圆环（Hash Ring），范围为 0 ~ 2^32-1：

  1. 服务器节点映射：对每台服务器的 IP 或主机名进行哈希，映射到环上的某个位置
  2. 数据映射：对数据的 key 进行哈希，映射到环上的某个位置
  3. 查找规则：从数据位置开始顺时针查找，遇到的第一个服务器节点即为存储位置

2.2 节点增减的影响

删除节点：

  • 只影响该节点到其前一个节点之间的数据
  • 这些数据会迁移到下一个节点

添加节点：

  • 只影响新节点到其前一个节点之间的数据
  • 部分数据从下一个节点迁移到新节点

相比传统方式，数据迁移量大幅减少。

三、虚拟节点

3.1 数据倾斜问题

当服务器节点较少时，可能出现数据分布不均的情况。例如 3 台服务器在环上的位置可能很接近，导致某台服务器承载了大部分数据。

3.2 虚拟节点解决方案

为每台物理服务器创建多个虚拟节点（Virtual Node），均匀分布在哈希环上：

// 为每台服务器创建 150 个虚拟节点
for (int i = 0; i < 150; i++) {
    String virtualNodeName = "Server1#" + i;
    int hash = getHash(virtualNodeName);
    virtualNodes.put(hash, "Server1");
}

优势：

  • 虚拟节点越多，数据分布越均匀
  • 一般 100-200 个虚拟节点即可达到良好效果

四、Java 实现

public class ConsistentHash<T> {
    // 虚拟节点数量
    private final int virtualNodeCount;
    // 哈希环
    private final SortedMap<Integer, T> ring = new TreeMap<>();
    
    public ConsistentHash(int virtualNodeCount) {
        this.virtualNodeCount = virtualNodeCount;
    }
    
    /**
     * 添加服务器节点
     */
    public void addNode(T node) {
        for (int i = 0; i < virtualNodeCount; i++) {
            String virtualNodeName = node.toString() + "#" + i;
            int hash = getHash(virtualNodeName);
            ring.put(hash, node);
        }
    }
    
    /**
     * 删除服务器节点
     */
    public void removeNode(T node) {
        for (int i = 0; i < virtualNodeCount; i++) {
            String virtualNodeName = node.toString() + "#" + i;
            int hash = getHash(virtualNodeName);
            ring.remove(hash);
        }
    }
    
    /**
     * 获取数据应该存储的节点
     */
    public T getNode(String key) {
        if (ring.isEmpty()) {
            return null;
        }
        
        int hash = getHash(key);
        // 顺时针查找第一个节点
        SortedMap<Integer, T> tailMap = ring.tailMap(hash);
        
        // 如果没有找到，返回第一个节点（形成环）
        int nodeHash = tailMap.isEmpty() ? ring.firstKey() : tailMap.firstKey();
        return ring.get(nodeHash);
    }
    
    /**
     * FNV1_32_HASH 算法
     */
    private int getHash(String str) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < str.length(); i++) {
            hash = (hash ^ str.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return Math.abs(hash);
    }
}

使用示例

// 创建一致性哈希，每个节点 150 个虚拟节点
ConsistentHash<String> consistentHash = new ConsistentHash<>(150);

// 添加服务器节点
consistentHash.addNode("192.168.1.1:8080");
consistentHash.addNode("192.168.1.2:8080");
consistentHash.addNode("192.168.1.3:8080");

// 查找数据应该存储的节点
String server = consistentHash.getNode("user:1001");
System.out.println("数据应该存储在: " + server);

// 添加新节点
consistentHash.addNode("192.168.1.4:8080");

// 删除节点
consistentHash.removeNode("192.168.1.2:8080");

五、应用场景

5.1 分布式缓存

  • Memcached 客户端：使用一致性哈希分配缓存数据
  • Redis Cluster：使用哈希槽（Hash Slot）的变种实现

5.2 负载均衡

  • Nginx：consistent hash 模块实现会话粘滞
  • Dubbo：ConsistentHashLoadBalance 负载均衡策略

5.3 分布式存储

  • Cassandra：使用一致性哈希分配数据到不同节点
  • DynamoDB：基于一致性哈希的分区策略

六、优缺点分析

优点

  1. 单调性：节点增减时，已有映射关系不会改变，只会增加新映射
  2. 分散性：数据均匀分布在各个节点上
  3. 平衡性：通过虚拟节点避免数据倾斜
  4. 可扩展性：方便动态增减节点

缺点

  1. 数据倾斜：节点较少时可能分布不均（虚拟节点可解决）
  2. 实现复杂：相比简单取模方式，实现和维护成本较高
  3. 虚拟节点开销：需要维护大量虚拟节点

七、总结

一致性哈希算法通过引入哈希环和虚拟节点的概念，有效解决了分布式系统中节点动态增减导致的数据大规模迁移问题。在分布式缓存、负载均衡、分布式存储等场景中有广泛应用。

核心要点：

  • 哈希环将数据和节点映射到同一空间
  • 顺时针查找规则确定数据存储位置
  • 虚拟节点保证数据分布均匀
  • 节点变化时只影响相邻节点的数据