分布式缓存 / 一致性Hash算法 002 — CONSISTENT HASH

一致性 Hash 算法
从原理到分布式缓存的
工程实践。

在分布式缓存集群扩容、缩容场景中，普通取模 Hash 算法存在致命缺陷：节点数量变更时，hash(key) % N 映射关系大面积失效，绝大多数缓存 Key 路由到新节点，引发大规模缓存失效、缓存雪崩。一致性 Hash 正是为解决该痛点诞生——保证集群增减节点时，仅少量缓存 Key 发生迁移。

迁移率
<1%
Hash 空间
2³²
虚拟节点
256/NODE
章节
8CHAPTERS
CHAPTER 01
01/08

传统取模 Hash 的 致命缺陷

传统分布式缓存路由方案：nodeIndex = hash(key) % N。当集群节点数量 N 变更时，几乎所有 Key 的取模结果都会改变，引发大规模缓存失效与雪崩。

TRADITIONAL HASH ROUTING
nodeIndex = hash(key) % N ;   // N = 节点数量
FAILURE SCENARIO
N=3 扩容至 N=4 时发生了什么

假设集群拥有 3 台缓存节点 N=3，当扩容至 4 台节点 N=4，几乎所有 Key 的取模结果都会改变。下方为两种方案在节点变更后的缓存失效率对比：

TRADITIONAL MOD HASH
普通取模 90%+ 失效
92% Cache Miss Rate
CONSISTENT HASH
一致性 Hash 仅 ~25% 迁移
25% Key Migration Rate
STEP 01
90%+
缓存路由错乱
扩容后绝大多数 Key 取模结果改变，缓存全部失效。
→
STEP 02
DB
请求击穿缓存
大量请求直达数据库，缓存层完全失去保护作用。
→
STEP 03
CRASH
缓存雪崩宕机
高并发场景直接触发雪崩，数据库宕机，系统不可用。
CONCLUSION 传统取模 Hash 无法适应集群动态扩缩容，分布式缓存场景不再适用。一致性 Hash 正是为解决此痛点诞生。
CHAPTER 02
02/08

一致性 Hash 核心原理

一致性 Hash 将 Hash 值空间设定为 0 ~ 2³²-1，把值域首尾相连形成环形结构。节点和 Key 都映射到环上，Key 顺时针遇到的第一个节点即为归属节点。

2.1 / HASH RING
Hash 环（哈希圆环）

对缓存节点 IP/名称进行 Hash 运算，映射到圆环上对应的位置；对缓存 Key 进行 Hash 运算，定位到圆环上的坐标；沿着 Hash 环顺时针查找，遇到的第一个节点即为当前 Key 归属节点。

HASH RING 0 ~ 2³² - 1
物理节点 Real Node
实际缓存服务器，Hash 后映射到环上
虚拟节点 Virtual Node
物理节点的副本，打散分布以均衡流量
缓存 Key
Hash 后定位到环上某坐标
顺时针路由
Key 沿环顺时针查找，遇到的第一个物理节点为归属
2.2 / NODE CHANGE
节点增减的数据迁移规则

对比普通取模 Hash：一致性 Hash 扩缩容，只有一小部分缓存数据需要迁移，极大降低缓存失效范围。

  • 新增节点：仅会分割相邻原有节点的数据，只有部分 Key 迁移至新节点；
  • 下线节点：失效节点的数据，顺延分配给顺时针下一个节点，仅影响该部分数据。
MIGRATION RATIO 集群从 N 台扩至 N+1 台，平均仅 1/(N+1) 的 Key 需要迁移，其余 Key 归属不变。
CASE — ADD NODE
新增节点场景

在 Node-A 与 Node-B 之间插入 Node-E，原本归属 Node-B 的部分 Key（落在新节点逆时针方向）会被分割给 Node-E。其余节点上的 Key 完全不受影响。

IMPACT RANGE 仅 Node-B 的部分数据被分割，Node-A / Node-C / Node-D 零迁移。
CASE — REMOVE NODE
下线节点场景

Node-B 宕机下线，原本归属 Node-B 的所有 Key，顺延至顺时针下一个节点（Node-C）。其余节点上的 Key 完全不受影响。

IMPACT RANGE 仅 Node-B 的数据迁移至 Node-C，其余节点零迁移。
2.3 / DATA SKEW
原生一致性 Hash 的短板：数据倾斜

直接将物理节点映射到 Hash 环存在严重问题：节点数量较少时，物理节点在环上分布不均匀，大量缓存 Key 集中落在少数节点，出现数据倾斜，节点负载不均衡。例如 3 台服务器，大量流量集中到其中一台节点，节点资源耗尽，其余节点闲置。

WITHOUT VIRTUAL NODE
3 物理节点直映射 倾斜
Node-A: 62% Keys
Node-B: 23% Keys
Node-C: 15% Keys
WITH 256 VIRTUAL NODES
3 × 256 虚拟节点 均匀
Node-A: 33.4% Keys
Node-B: 33.3% Keys
Node-C: 33.3% Keys
CHAPTER 03
03/08

虚拟节点 最优优化方案

为解决数据倾斜，引入虚拟节点（Virtual Node）。不再直接把物理节点放入 Hash 环，而是为每一台真实物理节点生成数百 / 上千个虚拟副本。

VIRTUAL NODE FLOW
虚拟节点工作流程
  1. 不再直接把物理节点放入 Hash 环；
  2. 为每一台真实物理节点生成数百 / 上千个虚拟副本；
  3. 将虚拟节点计算 Hash 放置到 Hash 环；
  4. 路由找到虚拟节点后，映射回真实物理节点。
BENEFIT 01
均衡数据分布
大量虚拟节点打散在圆环，缓存 Key 均匀分配至所有物理节点，解决倾斜。
BENEFIT 02
平滑扩容缩容
下线一台物理节点，它对应的所有虚拟节点失效，数据分散转移至其他多个物理节点，避免单节点瞬间流量暴涨。
ENGINEERING NOTE 线上一般设置每台物理节点虚拟节点数量 128 ~ 512，兼顾均衡性与内存开销。
CHAPTER 04
04/08

Java 简易 一致性 Hash 实现

含虚拟节点。使用 TreeMap 的 SortedMap 作为 Hash 环底层结构，tailMap 顺时针查找最近节点，MD5 作为 Hash 函数保证均匀分布。

ConsistentHash.java — with virtual nodes
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.*; import java.security.MessageDigest; public class ConsistentHash { // 虚拟节点数量 private static final int VIRTUAL_NUM = 256; // Hash环：hash值 -> 虚拟节点名称 private final SortedMap<Long, String> circle = new TreeMap<>(); // 真实节点集合 private final Set<String> realNodes = new HashSet<>(); public ConsistentHash(List<String> nodes) { for (String node : nodes) { addNode(node); } } // 添加物理节点 public void addNode(String realNode) { realNodes.add(realNode); for (int i = 0; i < VIRTUAL_NUM; i++) { String virtualNode = realNode + "v" + i; long hash = hash(virtualNode); circle.put(hash, realNode); } } // 删除物理节点 public void removeNode(String realNode) { if (!realNodes.contains(realNode)) return; realNodes.remove(realNode); for (int i = 0; i < VIRTUAL_NUM; i++) { String virtualNode = realNode + "v" + i; long hash = hash(virtualNode); circle.remove(hash); } } // 根据key寻找节点 public String getNode(String key) { if (circle.isEmpty()) return null; long hash = hash(key); // 顺时针查找 SortedMap<Long, String> tailMap = circle.tailMap(hash); Long targetHash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey(); return circle.get(targetHash); } // MD5计算hash private long hash(String str) { try { MessageDigest md5 = MessageDigest.getInstance("MD5"); byte[] bytes = md5.digest(str.getBytes()); long res = ((long) bytes[3] << 24) | ((long) bytes[2] << 16) | ((long) bytes[1] << 8) | bytes[0]; return res & 0xFFFFFFFFL; } catch (Exception e) { throw new RuntimeException(e); } } }
CHAPTER 05
05/08

分布式缓存场景 落地辨析

一致性 Hash 在 Memcached 客户端是经典应用，但 Redis Cluster 走的是另一条路。很多人存在误区，把两者混为一谈。

5.1 / MEMCACHED
Memcached 客户端一致性 Hash
Spymemcached · Xmemcached
架构
服务端无集群协议，集群能力完全依靠客户端实现
路由
成熟客户端内置一致性 Hash 算法，默认开启虚拟节点
扩缩容
仅影响少量 Key，客户端完成路由，服务端无感知
定位
一致性 Hash 最经典应用场景
5.2 / REDIS CLUSTER
Redis Cluster 不使用一致性 Hash！
16384 Hash Slots · CRC16
架构
Redis 集群划分 16384 个固定槽位
路由
CRC16(key) % 16384 计算槽，槽预先分配给各 Master
扩缩容
手动迁移部分槽至新节点，以槽为单位批量迁移
建议
优先使用官方槽方案，不要自行实现一致性 Hash
CONTRAST Hash 槽：槽位总量固定，迁移以槽为单位，批量迁移 Key；一致性 Hash：动态圆环，逐个 Key 迁移。
CHAPTER 06
06/08

线上经典问题 与解决方案

四类高频踩坑场景，每一类都对应过真实的线上故障。规避成本远低于复盘成本。

01
缓存雪崩
节点下线，大量 key 集中迁移
CAUSE 单台节点宕机，大量缓存 Key 迁移至下一个节点，瞬间大量缓存未命中，冲击数据库。 SOLUTION 1. 开启虚拟节点，流量分散到多个节点；
2. 缓存数据增加随机过期时间，避免集中失效；
3. 增加熔断、限流保护数据库。
02
缓存穿透
查询不存在的数据
CAUSE 缓存不存在的数据，持续查询直接访问数据库。 SOLUTION 通用方案：缓存空值、布隆过滤器拦截非法查询。
03
Hash 算法选择
分布不均的隐患
CAUSE 不要使用简单的 hashCode，分布不均匀，导致 Key 在环上聚集。 SOLUTION 推荐 MD5 / SHA1 衍生长 Hash，保证 Key 在圆环均匀分布。
04
客户端版本不一致
多实例配置漂移
CAUSE 微服务多实例场景，如果部分客户端虚拟节点数量配置不同，同一个 Key 会路由至不同节点，缓存出现多份数据，引发数据不一致。 SOLUTION 强制规范：所有服务实例保持完全相同的一致性 Hash 配置（虚拟节点数、Hash 函数、节点列表）。
CHAPTER 07
07/08

适用场景 与不适用场景

一致性 Hash 不是万能分片方案。下方为线上选型时的明确判断标准。

✓
适合场景
  • Memcached 客户端集群分片
  • 负载均衡、服务路由（如 Dubbo / gRPC 节点选择）
  • 需要平滑扩缩容、尽量减少缓存迁移的分布式缓存架构
  • 节点数量适中、变动频率低的分布式存储
✕
不适合场景
  • Redis Cluster 原生集群（官方槽方案更稳定）
  • 需要强一致性分片存储
  • 频繁上下线大量节点（虚拟节点维护成本高）
  • 小规模固定集群（取模 Hash 已足够）
CHAPTER 08 / 结语

掌握一致性 Hash，
是设计 高可用分布式缓存架构
的基础能力。

一致性 Hash 是分布式分片领域经典算法，核心价值就是最小化节点变动带来的数据迁移代价。在实际开发中，不能只停留在理论层面，必须理解虚拟节点解决倾斜的原理，同时区分 Memcached 客户端集群与 Redis Cluster 两种不同分片方案，避免技术选型踩坑。

算法的优雅不在于复杂，而在于用最小的代价解决最痛的问题——这正是一致性 Hash 成为分布式缓存基石的原因。