一致性哈希：分布式缓存节点扩缩容的数据迁移最小化
2026/4/30大约 9 分钟
一致性哈希：分布式缓存节点扩缩容的数据迁移最小化
适读人群：做过分布式系统，或想了解中间件选型原理的Java开发 | 阅读时长：约16分钟 | 文章类型：分布式算法+Java实现
开篇故事
2020年我们给一个电商平台做技术改造，把单机Redis换成Redis Cluster，但因为业务特殊性，他们想用一致性哈希而不是Redis Cluster内置的哈希槽（16384个槽）方案。
当时负责这块的老张（就是我）...对不起，是另一个叫老王的同事，他说：扩容不就是加一台机器，然后把数据重新分配一下嘛，这很简单。
我说：你知道"重新分配"有多大代价吗？假设有3台机器，共存了3000万个key，每台1000万。加了第4台，普通取模哈希（key % 4）会导致75%的key需要迁移到新机器（因为取模结果变了）。3000万 * 75% = 2250万次迁移，期间整个缓存层半瘫痪，业务全打穿到数据库。
老王沉默了。
我说：这就是为什么要用一致性哈希——扩容时只迁移约25%的数据（新节点承担它相邻前驱节点的一部分），而不是75%。
今天我把一致性哈希从原理到Java实现说清楚，包括虚拟节点解决数据不均匀的问题。
一、普通取模哈希的问题
// 普通取模哈希
int getServer(String key, int serverCount) {
return Math.abs(key.hashCode()) % serverCount;
}
// 问题：serverCount变化时，大量key的映射结果改变
// 3台服务器时：key.hashCode() % 3
// 4台服务器时：key.hashCode() % 4
// 设 hashCode=10：10%3=1（服务器1），10%4=2（服务器2）——迁移！
// 设 hashCode=11：11%3=2（服务器2），11%4=3（服务器3）——迁移！
// 统计：4/(4-3) = 75%的key需要迁移数据迁移量对比：
| 场景 | 迁移数据量 |
|---|---|
| 普通取模：3台→4台（+1台） | 约75% |
| 一致性哈希：3台→4台（+1台） | 约25%（只有新节点承接的部分） |
| 一致性哈希：4台→3台（-1台） | 约25%（只有被删节点的数据需要迁移） |
二、一致性哈希的完整Java实现
package com.laozhang.consistent;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.*;
/**
* 一致性哈希实现（带虚拟节点）
*
* 核心思想：
* 1. 把0~2^32的哈希空间想象成一个环
* 2. 每台服务器映射到环上的一个点
* 3. 每个key按哈希值找到"顺时针方向最近的服务器"
* 4. 添加/删除服务器时，只影响"相邻区间"的key，其他key不变
*
* 虚拟节点：每台真实服务器映射为N个虚拟节点（N=150~200）
* 作用：让各节点均匀分布在哈希环上，避免数据倾斜
*/
public class ConsistentHash {
// 真实节点到虚拟节点的TreeMap（有序，便于顺时针查找）
private final TreeMap<Long, String> ring = new TreeMap<>();
// 每个物理节点对应的虚拟节点数
private final int virtualNodeCount;
// 物理节点集合
private final Set<String> physicalNodes = new HashSet<>();
/**
* @param virtualNodeCount 每个物理节点的虚拟节点数，建议150~200
* 太少：数据分布不均，可能出现"热点环段"
* 太多：内存占用增大，初始化慢
*/
public ConsistentHash(int virtualNodeCount) {
this.virtualNodeCount = virtualNodeCount;
}
/**
* 添加物理节点：把该节点的所有虚拟节点加入哈希环
* 时间复杂度：O(virtualNodeCount * log(totalVirtualNodes))
*/
public void addNode(String node) {
if (physicalNodes.contains(node)) return;
physicalNodes.add(node);
for (int i = 0; i < virtualNodeCount; i++) {
// 虚拟节点的hash：对"节点名#虚拟节点序号"做MD5
// MD5比hashCode分布更均匀，减少hash碰撞
long hash = hash(node + "#" + i);
ring.put(hash, node); // 映射到物理节点
}
}
/**
* 删除物理节点：从哈希环移除所有虚拟节点
* 该节点负责的key会自动落到顺时针方向下一个节点
*/
public void removeNode(String node) {
if (!physicalNodes.contains(node)) return;
physicalNodes.remove(node);
for (int i = 0; i < virtualNodeCount; i++) {
long hash = hash(node + "#" + i);
ring.remove(hash);
}
}
/**
* 路由：根据key找到对应的物理节点
* 时间复杂度：O(log n)，n是虚拟节点总数
*
* 核心逻辑：
* 1. 计算key的hash
* 2. 在TreeMap中找到>=key.hash的第一个虚拟节点（tailMap.firstKey()）
* 3. 如果不存在（key.hash大于所有虚拟节点），则绕环到第一个节点（ring.firstKey()）
*/
public String getNode(String key) {
if (ring.isEmpty()) return null;
long hash = hash(key);
// tailMap：返回所有key >= hash 的部分
Map.Entry<Long, String> entry = ring.ceilingEntry(hash);
if (entry == null) {
// 超过了环的最大值，绕回到第一个节点（环形）
entry = ring.firstEntry();
}
return entry.getValue();
}
/**
* 获取各物理节点的负载分布（用于监控数据均匀性）
*/
public Map<String, Long> getLoadDistribution(List<String> keys) {
Map<String, Long> distribution = new HashMap<>();
for (String node : physicalNodes) distribution.put(node, 0L);
for (String key : keys) {
String node = getNode(key);
if (node != null) distribution.merge(node, 1L, Long::sum);
}
return distribution;
}
/**
* MD5哈希：取前8字节作为long，分布比hashCode更均匀
*/
private long hash(String key) {
try {
MessageDigest md = MessageDigest.getInstance("MD5");
byte[] bytes = md.digest(key.getBytes());
// 取前4字节组成一个int（无符号），映射到0~2^32的哈希环
long h = 0;
for (int i = 0; i < 4; i++) {
h = h << 8 | (bytes[i] & 0xFF);
}
return h;
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException(e);
}
}
public int getVirtualNodeCount() { return ring.size(); }
public int getPhysicalNodeCount() { return physicalNodes.size(); }
}2.2 数据迁移量测试
package com.laozhang.consistent;
import java.util.*;
/**
* 一致性哈希 vs 普通取模哈希：数据迁移量对比
*/
public class ConsistentHashBenchmark {
/**
* 测试扩容时的数据迁移量
* 场景：3台服务器 -> 4台服务器，10万个key
*/
public static void testMigrationOnScaleOut() {
int keyCount = 100_000;
List<String> keys = new ArrayList<>();
Random rnd = new Random(42);
for (int i = 0; i < keyCount; i++) {
keys.add("key-" + rnd.nextLong());
}
// ===== 一致性哈希 =====
ConsistentHash ch = new ConsistentHash(150);
ch.addNode("server-1");
ch.addNode("server-2");
ch.addNode("server-3");
// 记录扩容前的路由
Map<String, String> beforeCH = new HashMap<>();
keys.forEach(k -> beforeCH.put(k, ch.getNode(k)));
// 扩容：添加server-4
ch.addNode("server-4");
// 统计需要迁移的key数量
long chMigrations = keys.stream()
.filter(k -> !beforeCH.get(k).equals(ch.getNode(k)))
.count();
System.out.printf("一致性哈希：迁移了 %d / %d 个key（%.1f%%）%n",
chMigrations, keyCount, 100.0 * chMigrations / keyCount);
// 据我测试：约25000个key需要迁移，约25%
// ===== 普通取模哈希 =====
long modMigrations = 0;
for (String key : keys) {
int before = Math.abs(key.hashCode()) % 3;
int after = Math.abs(key.hashCode()) % 4;
if (before != after) modMigrations++;
}
System.out.printf("普通取模哈希：迁移了 %d / %d 个key（%.1f%%）%n",
modMigrations, keyCount, 100.0 * modMigrations / keyCount);
// 据我测试：约75000个key需要迁移，约75%
}
/**
* 测试虚拟节点对数据均匀性的影响
*/
public static void testVirtualNodeBalance() {
int keyCount = 1_000_000;
List<String> keys = new ArrayList<>();
Random rnd = new Random(42);
for (int i = 0; i < keyCount; i++) keys.add("k-" + rnd.nextLong());
for (int vn : new int[]{1, 10, 50, 150}) {
ConsistentHash ch = new ConsistentHash(vn);
ch.addNode("s1"); ch.addNode("s2"); ch.addNode("s3");
Map<String, Long> dist = ch.getLoadDistribution(keys);
long min = dist.values().stream().min(Long::compareTo).orElse(0L);
long max = dist.values().stream().max(Long::compareTo).orElse(0L);
double avg = keyCount / 3.0;
System.out.printf("虚拟节点=%3d: min=%.1f%%, max=%.1f%%, 最大偏差=%.1f%%%n",
vn,
100.0 * min / avg, 100.0 * max / avg,
100.0 * (max - avg) / avg);
}
// 虚拟节点= 1: 最大偏差可能超过100%（严重不均）
// 虚拟节点=150: 最大偏差通常在5%以内（基本均匀）
}
public static void main(String[] args) {
testMigrationOnScaleOut();
System.out.println();
testVirtualNodeBalance();
}
}四、踩坑实录
坑1：虚拟节点数太少，数据严重不均匀（数据倾斜）
报错现象：部署了3台缓存服务器，但其中一台CPU使用率90%，另外两台只有20%，典型数据倾斜。
根本原因：虚拟节点太少（比如只有3个），3个点在哈希环上分布不均匀，某个节点恰好覆盖了很长一段哈希区间，导致大量key都路由到它。
具体解法：
// 虚拟节点数建议：
// 节点数<10：每个节点至少150个虚拟节点
// 节点数10-100：每个节点至少50个虚拟节点
// 节点数>100：每个节点可以降到10-20个虚拟节点
// 监控数据均匀性：定期打印各节点的负载比例
Map<String, Long> dist = ch.getLoadDistribution(sampleKeys);
dist.forEach((node, count) ->
System.out.printf("%s: %.1f%%%n", node, 100.0 * count / totalKeys));坑2：扩容后缓存穿透，数据库压力骤增
报错现象：新加了一台缓存服务器后，数据库连接数瞬间飙升，触发数据库保护机制。
根本原因：虽然只迁移了25%的key，但这25%的key对应的缓存在新节点上是空的，大量请求第一时间打到数据库（缓存穿透）。如果是热点key，数据库根本扛不住。
具体解法：
// 扩容前：预热新节点
// 方案1：灰度扩容（先把一小部分流量切到新节点，让缓存逐步预热）
// 方案2：双写期（扩容期间同时写老节点和新节点，等新节点缓存填满后再切流量）
// 方案3：限流保护（扩容期间给数据库加限流，防止瞬间打穿）
// 代码层面的保护：
public String get(String key) {
String node = consistentHash.getNode(key);
String value = cacheClients.get(node).get(key);
if (value == null) {
// 缓存未命中：加锁防止大量请求同时打数据库（缓存击穿保护）
synchronized (("lock-" + key).intern()) {
value = cacheClients.get(node).get(key); // double-check
if (value == null) {
value = loadFromDB(key);
cacheClients.get(node).set(key, value, 300); // 写入缓存
}
}
}
return value;
}坑3：物理节点哈希值相同（哈希碰撞），一个节点覆盖另一个节点
报错现象：部署了两台缓存服务器，但所有key都路由到同一台服务器，另一台完全没有流量。
根本原因：两台服务器的哈希值计算后恰好相同（或太接近），在TreeMap里后加入的覆盖了前者，或者两个虚拟节点哈希值碰撞导致只有一个生效。
具体解法：
// 使用MD5作为哈希函数（比Java的hashCode碰撞概率低得多）
// 同时验证ring的大小是否符合预期
ConsistentHash ch = new ConsistentHash(150);
ch.addNode("server-1");
ch.addNode("server-2");
// 验证：应该是 2 * 150 = 300个虚拟节点
assert ch.getVirtualNodeCount() == 300 :
"虚拟节点数异常，可能有哈希碰撞: " + ch.getVirtualNodeCount();五、总结与延伸
一致性哈希的核心价值：扩缩容时只迁移约1/n的数据（n=节点数），而不是普通取模的大量迁移。 理解了这个，就理解了为什么Memcached、Redis Cluster（在自己的一致性哈希模式下）、Cassandra等分布式系统都选择了这个方案。
虚拟节点是一致性哈希实用化的关键，没有虚拟节点的一致性哈希数据倾斜严重。 每个物理节点映射150-200个虚拟节点，让节点在哈希环上均匀分布，解决了数据不均匀问题。虚拟节点数不是越多越好，150是工程实践中的经验值。
扩容不只是算法层面的问题，还要解决"缓存预热"和"缓存穿透"的工程问题。 一致性哈希只解决了"迁移哪些数据"，但迁移期间的缓存击穿、数据库压力保护、灰度切换，都需要额外的工程设计。