📚 Java 面试知识库

主题

一致性哈希算法原理与实践 ​

传统哈希算法的局限性 ​

在分布式系统中,我们经常需要将数据分散存储到多个节点上。传统的做法是使用哈希取模算法,例如在缓存系统中,我们有8台Redis服务器,要缓存用户数据时,可以这样计算:

plain
目标服务器 = hash(user_id) % 8

这种方式在节点数量固定时运行良好。但是当我们需要扩容或缩容时,问题就出现了。

扩容场景:假设业务增长迅速,8台服务器不够用了,需要扩展到16台。此时取模的基数从8变为16,几乎所有的数据映射关系都会发生变化。原本映射到服务器3的数据,现在可能映射到服务器11。这导致大量缓存失效,引发缓存雪崩。

缩容场景:如果某台服务器故障下线,同样会导致大量数据重新映射,影响范围远超单台服务器的数据量。

mermaid
graph TB
    subgraph 传统哈希扩容问题
        Before[原有8台服务器]
        User1[用户10001<br/>hash%8=3]
        User2[用户10002<br/>hash%8=5]
        User3[用户10003<br/>hash%8=7]
        
        After[扩容至16台服务器]
        NewUser1[用户10001<br/>hash%16=11]
        NewUser2[用户10002<br/>hash%16=13]
        NewUser3[用户10003<br/>hash%16=7]
        
        Before --> User1
        Before --> User2
        Before --> User3
        
        After --> NewUser1
        After --> NewUser2
        After --> NewUser3
        
        Impact[影响:75%数据重新映射<br/>缓存大面积失效]
        
        User1 -.->|位置改变| Impact
        User2 -.->|位置改变| Impact
        User3 -.->|未变| NewUser3
    end
    
    style Before fill:#4CAF50,stroke:#2E7D32,stroke-width:2px,rx:10,ry:10
    style After fill:#2196F3,stroke:#1976D2,stroke-width:2px,rx:10,ry:10
    style Impact fill:#E57373,stroke:#C62828,stroke-width:2px,rx:10,ry:10
    style NewUser3 fill:#66BB6A,stroke:#43A047,stroke-width:2px,rx:10,ry:10

一致性哈希算法正是为了解决这个问题而诞生的,它能够在节点变化时,将数据迁移量降到最低。

一致性哈希核心原理 ​

一致性哈希算法将整个哈希值空间组织成一个虚拟的环形结构,这个环的取值范围通常是0到2^32-1。

哈希环构建 ​

mermaid
graph TB
    subgraph 哈希环结构
        Ring[一致性哈希环<br/>0 到 2^32-1]
        
        Node0[位置 0]
        Node1[位置 2^30]
        Node2[位置 2^31]
        Node3[位置 3×2^30]
        NodeMax[位置 2^32-1]
        
        Ring --> Node0
        Ring --> Node1
        Ring --> Node2
        Ring --> Node3
        Ring --> NodeMax
        
        NodeMax -.->|环形连接| Node0
    end
    
    style Ring fill:#5C6BC0,stroke:#3F51B5,stroke-width:3px,rx:10,ry:10
    style Node0 fill:#4CAF50,stroke:#2E7D32,stroke-width:2px,rx:10,ry:10
    style Node1 fill:#2196F3,stroke:#1976D2,stroke-width:2px,rx:10,ry:10
    style Node2 fill:#FF9800,stroke:#EF6C00,stroke-width:2px,rx:10,ry:10
    style Node3 fill:#9C27B0,stroke:#7B1FA2,stroke-width:2px,rx:10,ry:10

节点与数据映射 ​

第一步:服务器节点映射

假设我们有4台Redis缓存服务器,每台服务器通过哈希函数映射到环上的一个位置:

plain
hash("redis-server-A") % 2^32 = 1500000000
hash("redis-server-B") % 2^32 = 3000000000  
hash("redis-server-C") % 2^32 = 150000000
hash("redis-server-D") % 2^32 = 4200000000
mermaid
graph TB
    subgraph 服务器节点映射到哈希环
        direction TB
        ServerA[Redis-A<br/>位置:150000000]
        ServerB[Redis-B<br/>位置:1500000000]
        ServerC[Redis-C<br/>位置:3000000000]
        ServerD[Redis-D<br/>位置:4200000000]
        
        Circle([哈希环])
        
        Circle -.-> ServerA
        Circle -.-> ServerB
        Circle -.-> ServerC
        Circle -.-> ServerD
        
        ServerD -.->|顺时针方向| ServerA
    end
    
    style Circle fill:#E1BEE7,stroke:#8E24AA,stroke-width:3px,rx:10,ry:10
    style ServerA fill:#81C784,stroke:#43A047,stroke-width:2px,rx:10,ry:10
    style ServerB fill:#64B5F6,stroke:#1976D2,stroke-width:2px,rx:10,ry:10
    style ServerC fill:#FFB74D,stroke:#F57C00,stroke-width:2px,rx:10,ry:10
    style ServerD fill:#BA68C8,stroke:#7B1FA2,stroke-width:2px,rx:10,ry:10

第二步:数据键映射

当需要存储或查询数据时,对数据的键进行同样的哈希运算:

java
// 缓存用户信息示例
String cacheKey = "user:profile:888888";
long hashValue = hash(cacheKey) % (1L << 32);  // 假设结果为 2000000000

第三步:顺时针查找规则

数据映射到哈希环后,沿着顺时针方向查找,遇到的第一个服务器节点就是数据的存储位置。

mermaid
graph LR
    subgraph 数据查找过程
        Data1[数据Key1<br/>hash=200000000]
        Data2[数据Key2<br/>hash=2000000000]
        Data3[数据Key3<br/>hash=3500000000]
        
        ServerA[Redis-A<br/>150000000]
        ServerB[Redis-B<br/>1500000000]
        ServerC[Redis-C<br/>3000000000]
        ServerD[Redis-D<br/>4200000000]
        
        Data1 -->|顺时针查找| ServerB
        Data2 -->|顺时针查找| ServerC
        Data3 -->|顺时针查找| ServerD
    end
    
    style Data1 fill:#4DD0E1,stroke:#0097A7,stroke-width:2px,rx:10,ry:10
    style Data2 fill:#4DD0E1,stroke:#0097A7,stroke-width:2px,rx:10,ry:10
    style Data3 fill:#4DD0E1,stroke:#0097A7,stroke-width:2px,rx:10,ry:10
    style ServerA fill:#81C784,stroke:#43A047,stroke-width:2px,rx:10,ry:10
    style ServerB fill:#64B5F6,stroke:#1976D2,stroke-width:2px,rx:10,ry:10
    style ServerC fill:#FFB74D,stroke:#F57C00,stroke-width:2px,rx:10,ry:10
    style ServerD fill:#BA68C8,stroke:#7B1FA2,stroke-width:2px,rx:10,ry:10

节点增减时的影响 ​

增加节点场景

假设系统负载增加,需要新增一台Redis-E服务器,其哈希值为2500000000,刚好落在Redis-B和Redis-C之间。

mermaid
graph TB
    subgraph 新增节点前
        OldData[数据Key2<br/>hash=2000000000]
        OldServer[存储在Redis-C]
        OldData --> OldServer
    end
    
    subgraph 新增Redis-E后
        NewServerE[新增Redis-E<br/>位置:2500000000]
        ServerC2[Redis-C<br/>位置:3000000000]
        
        Affected[受影响数据<br/>2000000000到2500000000]
        Unaffected[不受影响数据<br/>其他区间]
        
        Affected -->|迁移到| NewServerE
        Unaffected -->|保持不变| ServerC2
    end
    
    Impact[影响范围:约25%的数据<br/>仅需迁移一个区间的数据]
    
    OldServer -.-> Affected
    
    style OldServer fill:#FFB74D,stroke:#F57C00,stroke-width:2px,rx:10,ry:10
    style NewServerE fill:#26A69A,stroke:#00897B,stroke-width:2px,rx:10,ry:10
    style ServerC2 fill:#FFB74D,stroke:#F57C00,stroke-width:2px,rx:10,ry:10
    style Impact fill:#66BB6A,stroke:#43A047,stroke-width:2px,rx:10,ry:10

相比传统哈希,影响范围从几乎100%缩减到约1/N(N为节点数)。只有落在新节点和前一个节点之间的数据需要迁移。

删除节点场景

如果Redis-B服务器故障下线,原本由它负责的数据会自动转移到下一个节点Redis-C。

mermaid
sequenceDiagram
    participant Client as 客户端
    participant HashRing as 哈希环
    participant ServerB as Redis-B(故障)
    participant ServerC as Redis-C
    
    Note over ServerB: 服务器故障
    Client->>HashRing: 查询数据(hash=2000000000)
    HashRing->>HashRing: 顺时针查找节点
    HashRing--xServerB: 跳过故障节点
    HashRing->>ServerC: 定位到下一节点
    ServerC-->>Client: 返回数据(缓存未命中需回源)

虚拟节点优化 ​

数据倾斜问题 ​

当物理节点较少时,一致性哈希可能出现数据分布不均的问题。例如4台服务器的哈希值如果集中在环的某一侧,会导致某些服务器负载过高。

mermaid
graph TB
    subgraph 数据倾斜场景
        Ring[哈希环]
        
        Node1[服务器1<br/>位置:100000]
        Node2[服务器2<br/>位置:200000]
        Node3[服务器3<br/>位置:300000]
        Node4[服务器4<br/>位置:3000000000]
        
        LargeSegment[巨大的数据区间<br/>300000 到 3000000000<br/>负载集中在服务器4]
        SmallSegment[较小的数据区间<br/>其他服务器负载轻]
        
        Ring --> Node1
        Ring --> Node2
        Ring --> Node3
        Ring --> Node4
        
        Node3 -.-> LargeSegment
        LargeSegment -.-> Node4
    end
    
    style LargeSegment fill:#E57373,stroke:#C62828,stroke-width:2px,rx:10,ry:10
    style SmallSegment fill:#81C784,stroke:#43A047,stroke-width:2px,rx:10,ry:10
    style Node4 fill:#FF6F00,stroke:#E65100,stroke-width:3px,rx:10,ry:10

虚拟节点解决方案 ​

为每个物理节点创建多个虚拟节点,使节点在环上分布更均匀。通常一个物理节点会对应100-200个虚拟节点。

java
/**
 * 缓存路由服务 - 实现一致性哈希
 */
public class CacheRouter {
    
    // 虚拟节点倍数
    private static final int VIRTUAL_NODE_COUNT = 150;
    
    // 哈希环:虚拟节点哈希值 -> 物理服务器
    private final TreeMap<Long, String> hashRing = new TreeMap<>();
    
    /**
     * 添加缓存服务器节点
     * @param serverIp 服务器IP地址
     */
    public void addServer(String serverIp) {
        // 为每个物理节点创建150个虚拟节点
        for (int i = 0; i < VIRTUAL_NODE_COUNT; i++) {
            String virtualNodeKey = serverIp + "#virtual-" + i;
            long hashValue = hash(virtualNodeKey);
            hashRing.put(hashValue, serverIp);
        }
        System.out.println("服务器 " + serverIp + " 上线,创建 " 
            + VIRTUAL_NODE_COUNT + " 个虚拟节点");
    }
    
    /**
     * 移除缓存服务器节点
     * @param serverIp 服务器IP地址
     */
    public void removeServer(String serverIp) {
        for (int i = 0; i < VIRTUAL_NODE_COUNT; i++) {
            String virtualNodeKey = serverIp + "#virtual-" + i;
            long hashValue = hash(virtualNodeKey);
            hashRing.remove(hashValue);
        }
        System.out.println("服务器 " + serverIp + " 下线");
    }
    
    /**
     * 路由缓存请求到具体服务器
     * @param cacheKey 缓存键,例如 "product:detail:12345"
     * @return 目标服务器IP
     */
    public String routeServer(String cacheKey) {
        if (hashRing.isEmpty()) {
            throw new IllegalStateException("没有可用的缓存服务器");
        }
        
        long hashValue = hash(cacheKey);
        
        // 查找顺时针方向第一个节点
        Map.Entry<Long, String> entry = hashRing.ceilingEntry(hashValue);
        
        // 如果没找到,说明已经超过最大值,取环上第一个节点
        if (entry == null) {
            entry = hashRing.firstEntry();
        }
        
        return entry.getValue();
    }
    
    /**
     * MurmurHash算法实现
     */
    private long hash(String key) {
        // 使用MurmurHash或FNV等高性能哈希算法
        // 这里简化实现
        return Math.abs(key.hashCode()) % (1L << 32);
    }
    
    /**
     * 展示当前数据分布情况
     */
    public void showDistribution() {
        Map<String, Integer> distribution = new HashMap<>();
        
        // 统计每个物理服务器对应的虚拟节点数量
        for (String server : hashRing.values()) {
            distribution.put(server, 
                distribution.getOrDefault(server, 0) + 1);
        }
        
        System.out.println("数据分布情况:");
        distribution.forEach((server, count) -> {
            System.out.println("  " + server + ": " + count + " 个虚拟节点");
        });
    }
}

应用示例 ​

java
/**
 * 商品详情缓存场景
 */
public class ProductCacheExample {
    
    public static void main(String[] args) {
        CacheRouter router = new CacheRouter();
        
        // 初始化4台缓存服务器
        router.addServer("192.168.1.101");
        router.addServer("192.168.1.102");
        router.addServer("192.168.1.103");
        router.addServer("192.168.1.104");
        
        // 路由商品缓存请求
        String product1 = router.routeServer("product:detail:10001");
        String product2 = router.routeServer("product:detail:10002");
        String product3 = router.routeServer("product:detail:10003");
        
        System.out.println("商品10001 -> " + product1);
        System.out.println("商品10002 -> " + product2);
        System.out.println("商品10003 -> " + product3);
        
        // 模拟服务器故障
        System.out.println("\n服务器192.168.1.102故障下线");
        router.removeServer("192.168.1.102");
        
        // 原本路由到102的数据会自动转移到其他服务器
        String product2New = router.routeServer("product:detail:10002");
        System.out.println("商品10002迁移至 -> " + product2New);
        
        // 扩容场景:新增一台服务器
        System.out.println("\n系统扩容,新增服务器192.168.1.105");
        router.addServer("192.168.1.105");
        
        router.showDistribution();
    }
}
mermaid
graph TB
    subgraph 虚拟节点分布效果
        Physical1[物理服务器A]
        Physical2[物理服务器B]
        
        Virtual1A[虚拟节点A-1]
        Virtual2A[虚拟节点A-2]
        Virtual3A[虚拟节点A-150]
        
        Virtual1B[虚拟节点B-1]
        Virtual2B[虚拟节点B-2]
        Virtual3B[虚拟节点B-150]
        
        Ring[哈希环<br/>均匀分布]
        
        Physical1 -.-> Virtual1A
        Physical1 -.-> Virtual2A
        Physical1 -.-> Virtual3A
        
        Physical2 -.-> Virtual1B
        Physical2 -.-> Virtual2B
        Physical2 -.-> Virtual3B
        
        Virtual1A --> Ring
        Virtual2A --> Ring
        Virtual1B --> Ring
        Virtual2B --> Ring
        Virtual3A --> Ring
        Virtual3B --> Ring
        
        Result[数据均匀分布<br/>负载均衡]
        Ring -.-> Result
    end
    
    style Physical1 fill:#4CAF50,stroke:#2E7D32,stroke-width:2px,rx:10,ry:10
    style Physical2 fill:#2196F3,stroke:#1976D2,stroke-width:2px,rx:10,ry:10
    style Ring fill:#E1BEE7,stroke:#8E24AA,stroke-width:3px,rx:10,ry:10
    style Result fill:#66BB6A,stroke:#43A047,stroke-width:2px,rx:10,ry:10

一致性哈希的优势与局限 ​

核心优势 ​

数据迁移最小化

在节点数量为N的集群中,增加或删除一个节点,平均只影响1/N的数据,而传统哈希几乎影响所有数据。这在大规模缓存系统中意味着:

  • 减少缓存失效导致的数据库压力
  • 降低数据迁移的网络开销
  • 提升系统扩展的平滑性

高扩展性

支持动态增减节点而不影响整体服务,特别适合云环境下的弹性伸缩场景。

去中心化

不需要集中式的元数据服务器,每个节点通过相同的哈希算法就能确定数据位置,降低了系统复杂度。

存在的局限 ​

哈希碰撞风险

虽然虚拟节点减轻了数据倾斜,但在节点数极少且哈希函数质量不高时,仍可能出现分布不均。

节点频繁变更

如果节点频繁上下线,虽然每次影响范围小,但累积的数据迁移量仍可能很大,需要配合缓存预热等策略。

无法处理热点数据

如果某些数据访问频率极高(如爆款商品),会导致某个节点压力过大。需要配合其他策略如数据多副本、本地缓存等。

工程实践建议 ​

选择合适的哈希算法 ​

推荐使用MurmurHash3或FNV-1a等高性能哈希算法,避免使用Java默认的hashCode(),因为其碰撞率相对较高。

虚拟节点数量配置 ​

  • 节点数少于10时,建议每个物理节点对应150-200个虚拟节点
  • 节点数在10-100时,可减少到50-100个虚拟节点
  • 节点数超过100时,甚至可以不使用虚拟节点

与其他策略结合 ​

  • 配合主从复制:每个节点配置备份节点,提升可用性
  • 数据多副本:热点数据在多个节点存储副本
  • 客户端缓存:减少对后端节点的访问压力

一致性哈希是分布式系统中的基础算法,理解其原理对于设计高可用、可扩展的系统至关重要。

更新: 2025-12-04 18:18:52
原文: https://www.yuque.com/u22210564/zoxfmt/nf24t9ks2rwdog8w

Java 后端面试知识库

内容整理自 Guide 哥系列文章