分布式缓存中，如何实现一致性 Hash 算法？相比普通 Hash，它解决了什么问题？

标签：后端、系统设计、场景题、一致性Hash、分布式缓存、负载均衡

🏛 业务架构师

一致性 Hash 我按"原理 → 解决什么问题 → 业务应用 → 工程细节"答，重点放在为什么缓存场景非它不可。

普通 Hash 的问题（伸缩性灾难）

node = hash(key) % N：N 变化（加/减一台机器）时，几乎所有 key 的映射都变——缓存场景意味着瞬间全量缓存失效，请求洪峰砸穿数据库（缓存雪崩）；存储场景意味着全量数据迁移。

一致性 Hash 原理

构建 0 ~ 2^32 的哈希环，节点和 key 都 hash 到环上
key 顺时针找最近的节点归属
节点增删时，只有该节点环上相邻区段的 key 需要迁移——理论上迁移量从"全量"降到"1/N"，伸缩性质变

虚拟节点（工程必答点）

裸一致性 Hash 有数据倾斜问题：节点少时环上分布不均（某节点占 40% 区段很常见）。解法：每个物理节点映射 150~200 个虚拟节点，统计意义上分布均匀；顺带把"节点性能差异"变成权重（高性能机器多挂虚拟节点，成本结构映射到流量结构）。

nodeA → vA1, vA2 ... vA200 (均匀撒在环上)

业务应用场景

分布式缓存分片（Redis 客户端分片、Memcached Ketama）：伸缩不雪崩——这是它最大的业务价值
负载均衡的会话粘性：同一用户路由到同一节点
网关分片、分库分表路由（部分中间件）
对比：Redis Cluster 用的**哈希槽（slot）**是一致性哈希的工程变体——离散槽位比连续环实现更简单、迁移更可控

收尾：一致性 Hash 的本质是**"用最小数据移动换取集群伸缩自由"**——业务上对应的是"扩容/缩容/故障摘除时业务无感"。凡是节点会动态变化的分布式系统，路由层都应该回答"为什么不用一致性哈希"这个问题。

🏗 系统架构师

一致性 Hash 我从普通 Hash 的问题 → 算法原理 → 数据结构实现 → 虚拟节点讲透。

1. 普通 Hash 的问题server = hash(key) % N：N 变化（扩容/缩容/宕机）时，几乎全部 key 的映射关系改变。缓存场景意味着一次扩容引发全量缓存失效、请求全部穿透到 DB——缓存雪崩；存储场景意味着全量数据迁移。

2. 一致性 Hash 原理 把 hash 空间组成 0 ~ 2^32 的环：

节点 hash 后放到环上（一个点）
key hash 后顺时针找到第一个节点，就是它的归属
核心性质：节点增删时，只有该节点与前一节点之间的 key 需要迁移——平均只影响 1/N 的数据，其余 key 归属不变

3. 实现（手写要点）

java

TreeMap<Long, String> ring = new TreeMap<>();
// 节点与虚拟节点入环
for (int i = 0; i < VNODE_COUNT; i++)
    ring.put(hash(node + "#" + i), node);
// 路由：顺时针第一个
public String route(String key) {
    SortedMap<Long, String> tail = ring.tailMap(hash(key));
    long h = tail.isEmpty() ? ring.firstKey() : tail.firstKey();
    return ring.get(h);
}

TreeMap（红黑树）的 tailMap 是 O(logN) 路由；生产用 CRC32/MurmurHash 并对节点地址加扰动。

4. 虚拟节点（必讲） 物理节点少时（3 台），环上分布不均导致负载倾斜（某节点扛 60%）；且宕机时它的流量全部压给顺时针下一台。每个物理节点映射为 100~200 个虚拟节点打散在环上：负载标准差降到 10% 以内，宕机流量均匀分摊给所有节点而非一台。虚拟节点还让权重控制成为可能（性能好的机器多放虚拟节点）。

5. 工程应用：Redis 客户端分片（Jedis 的分片模式）、负载均衡会话粘性、分库分表路由中间件、CDN 边缘节点选择。带虚拟节点的一致性 hash 已是分布式路由的基础设施级算法。

💻 全栈开发专家

先说普通 hash 的问题，再给实现——一致性 hash 解决的是"节点增减时全量数据迁移"的问题。

普通 Hash 的痛点

node = hash(key) % N：N 从 3 变 4（加减节点），几乎所有 key 的映射都变了，缓存集体失效、数据全量搬迁——这在生产就是一次小型"雪崩"。

一致性 Hash 原理

把 hash 空间组成 0 ~ 2^32 的环，节点和 key 都 hash 到环上，key 顺时针找最近的节点。
节点增减只影响环上相邻一段的数据，其余不动：3 节点加 1 个，只迁移约 1/4 数据。

Java 实现（TreeMap）

java

public class ConsistentHash {
    private final TreeMap<Long, String> ring = new TreeMap<>();
    private final int VIRTUAL_NODES = 160; // 每物理节点虚拟节点数

    public void addNode(String node) {
        for (int i = 0; i < VIRTUAL_NODES; i++) {
            ring.put(hash(node + "#" + i), node); // 虚拟节点打散
        }
    }
    public String get(String key) {
        Map.Entry<Long, String> e = ring.ceilingEntry(hash(key));
        return e != null ? e.getValue() : ring.firstEntry().getValue(); // 环回绕
    }
    private long hash(String s) { return Murmur3.hash64(s); } // 分布均匀，别用 JDK hashCode
}

ceilingEntry O(logN) 找顺时针第一个节点；找完首尾要回绕到 firstEntry。

虚拟节点（必讲）

3 个节点直接上环，数据倾斜可能到 40%+。每个物理节点映射几百个虚拟节点（带权重，机器强的多放几个），统计意义上就均匀了（偏差可控制在 5% 内）。这同时解决了"异构机器负载不均"。

实际工程现状

Redis Cluster 用的是 16384 slot（预分片 + 迁移槽），比一致性 hash 更可控。
一致性 hash 仍在网关负载均衡、MQ 分区路由、分库分表扩容（等同一致性 hash 的 slot 方案）、本地缓存分片里大量使用。
坑：节点列表变化时客户端要同步刷新；用 MD5/Murmur 而不是 String.hashCode()，后者分布太差导致倾斜。

分布式缓存中，如何实现一致性 Hash 算法？相比普通 Hash，它解决了什么问题？ ​

🏛 业务架构师 ​

🏗 系统架构师 ​

💻 全栈开发专家 ​

分布式缓存中，如何实现一致性 Hash 算法？相比普通 Hash，它解决了什么问题？

🏛 业务架构师

🏗 系统架构师

💻 全栈开发专家