外观
28 - 一致性哈希:节点扩缩容时如何减少缓存迁移
摘要
缓存扩容后,请求为什么可能更多地落到数据库?如果大量 Key(缓存键,例如 user:1)被分配到新的节点,而这些节点还没有对应数据,请求就会缓存未命中,再回源查询数据库或其他原始存储。本文讨论的节点是实际存放缓存数据的服务实例,路由是根据 Key 选择节点的过程。
一致性哈希把节点和 Key 映射到同一哈希环,使节点增删只改变部分 Key 的归属。它减少的是路由重映射的范围;缓存数据是否已经搬过去、迁移期间怎样读写,仍需额外安排。下面先解释取模与哈希环,再看 Java 实现及发布边界。
1. 普通取模的问题
text
nodeIndex = hash(key) % nodeCount这里的 hash(key) 是哈希函数计算出的值,nodeCount 是节点数,余数对应节点列表中的下标。假设节点下标保持原有对应关系,哈希值为 7 时,7 % 4 = 3,而 7 % 5 = 2:Key 没变,目标节点却变了。
当节点数从 4 变成 5,在哈希值分布均匀的前提下,多数 Key 的余数都会变化。原缓存数据可能仍在旧节点,新路由却不再访问它;如果没有预热或过渡读取,这会形成大面积冷缓存,即新目标节点缺少可命中的数据,进而增加回源压力。
2. 哈希环
哈希空间是哈希值所有可能取值组成的范围。把这些位置按数值从小到大排列,并约定越过最大值后回到最小值,就得到哈希环;“顺时针”表示沿这个顺序前进,不需要真的绘制或存储一个圆。
先假设每个真实节点在环上只有一个位置:
- 用节点名称计算哈希值,确定节点位置;
- 用 Key 计算哈希值,确定 Key 位置;
- 从 Key 位置顺时针找第一个节点;若 Key 恰好与节点同位置,就选该节点。
因此,一个节点负责从它的前驱(环上前一个节点)之后,到自身位置为止的区间。新增节点时,原有节点位置不变,新节点只接管它与前驱之间的 Key;删除节点时,它负责的区间交给顺时针下一个节点。变化来自局部区间被切分或合并,而不是重新用节点数对所有 Key 取模。
实际实现通常为一个真实节点放置多个虚拟节点。虚拟节点只是环上的路由位置,不是额外的缓存进程;找到它之后,仍返回对应的真实节点。这样一个真实节点负责的是多个分散区间,增删它时也会影响多个局部区间。第 5 节再讨论这样做如何改善分布。
3. Java 最小实现
下面是没有运行入口的教学片段,只展示建环和定位。TreeMap 按位置排序,NavigableMap 提供查找不小于指定位置的条目等操作。node + "#" + i 为同一个真实节点生成不同的虚拟节点名称;映射的值仍是 node。
调用方需传入有效节点名、正整数 virtualNodes 和非 null 的 Key。片段没有完整参数校验,同名节点重复添加也没有清理旧位置。
java
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.util.NavigableMap;
import java.util.TreeMap;
class ConsistentHash {
private final NavigableMap<Long, String> ring = new TreeMap<>();
void addNode(String node, int virtualNodes) {
for (int i = 0; i < virtualNodes; i++) {
ring.put(hash(node + "#" + i), node);
}
}
String locate(String key) {
if (ring.isEmpty()) throw new IllegalStateException("empty ring");
var entry = ring.ceilingEntry(hash(key));
return entry != null ? entry.getValue() : ring.firstEntry().getValue();
}
private long hash(String value) {
try {
byte[] digest = MessageDigest.getInstance("SHA-256").digest(
value.getBytes(StandardCharsets.UTF_8)
);
return java.nio.ByteBuffer.wrap(digest).getLong() & Long.MAX_VALUE;
} catch (java.security.NoSuchAlgorithmException e) {
throw new IllegalStateException(e);
}
}
}示例没有实现删除、并发安全和碰撞处理,不应直接用于生产。哈希碰撞指不同输入得到同一个位置;此处 ring.put 会覆盖该位置的旧映射。locate 在空环上抛出异常,超过环尾时返回首位置对应的真实节点。
4. 完整可运行示例:节点增删与路由
下面是完整入口类 ConsistentHashDemo,源文件应命名为 ConsistentHashDemo.java,仅使用 JDK 标准库。代码使用了 var、List.of 和 String.isBlank,需要支持这些特性的 JDK。
ring 保存“虚拟位置 → 真实节点”,positions 反向记录每个真实节点占用的位置,便于删除。add 会先移除同名节点的旧位置;remove 对不存在的节点不做处理;locate 要求环非空且 Key 非 null。这个示例仍没有并发保护,也没有搬运任何缓存数据。
java
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.util.*;
/**
* 可运行示例:一致性哈希:节点扩缩容时如何减少缓存迁移。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class ConsistentHashDemo {
static class Ring {
final NavigableMap<Long, String> ring = new TreeMap<>();
final Map<String, List<Long>> positions = new HashMap<>();
void add(String node, int virtualNodes) {
if (node == null || node.isBlank() || virtualNodes <= 0) {
throw new IllegalArgumentException(
"invalid node or virtual node count"
);
}
// 同名节点重加时先清除旧位置,避免不同虚拟节点数量残留脏数据。
remove(node);
List<Long> list = new ArrayList<>();
for (int i = 0; i < virtualNodes; i++) {
// 固定命名规则是路由协议的一部分,所有客户端必须完全一致。
long p = hash(node + "#" + i);
// 极少数 Hash 碰撞通过顺延位置解决,保证虚拟节点不被覆盖。
while (ring.containsKey(p)) p = (p + 1) & Long.MAX_VALUE;
// 环保存虚拟位置到真实节点的映射。
ring.put(p, node);
// 反向记录位置,使删除节点无需扫描整张环。
list.add(p);
}
positions.put(node, list);
}
void remove(String node) {
List<Long> list = positions.remove(node);
if (list != null) {
for (long p : list) {
ring.remove(p);
}
}
}
String locate(String key) {
if (ring.isEmpty()) throw new IllegalStateException("empty ring");
// 顺时针寻找第一个节点;越过环尾时回到首节点。
var e = ring.ceilingEntry(hash(key));
return (e != null ? e : ring.firstEntry()).getValue();
}
long hash(String value) {
try {
// SHA-256 在示例中用于获得稳定分布;生产还需评估吞吐和跨语言协议。
byte[] d = MessageDigest.getInstance("SHA-256").digest(
value.getBytes(StandardCharsets.UTF_8)
);
// 取摘要前 64 位并清除符号位,把位置映射到 [0, 2^63-1]。
return java.nio.ByteBuffer.wrap(d).getLong() & Long.MAX_VALUE;
} catch (Exception e) {
throw new IllegalStateException(e);
}
}
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
Ring ring = new Ring();
ring.add("node-a", 100);
ring.add("node-b", 100);
for (String key : List.of("user:1", "user:2", "user:3"))
System.out.println(key + " -> " + ring.locate(key));
ring.add("node-c", 100);
System.out.println("after scale out: " + ring.locate("user:1"));
ring.remove("node-b");
}
}4.1 扩容时哪些 Key 会移动
入口先添加两个各有 100 个虚拟节点的真实节点,打印三个 Key 的归属;再加入 node-c,只打印 user:1 的新归属,最后删除 node-b。删除之后没有输出,示例也没有统计迁移率。因此,不能从这几个 Key 推断整体分布或扩缩容效果。
假设 A、B 是环上相邻的两个位置,新位置 C 插入它们之间。原先 (A,B] 区间的 Key 都路由到 B;加入 C 后,只有 (A,C] 改为路由到 C,其他区间保持不变。括号 ( 表示不含 A,方括号 ] 表示包含右端点。使用虚拟节点时,对新增的每个位置分别应用这个规则。
理想均匀分布下,从 N 个等权真实节点扩到 N+1 个节点,新节点期望接管约 1/(N+1) 的 Key;这些 Key 原先属于旧节点,因此这也是期望的重映射比例,而普通取模通常会改变大多数 Key 的映射。这里的“迁移”首先指路由归属变化,不表示代码已经复制数据。
这里的比例是均匀 Hash 和足够虚拟节点下的期望,不是对任意小样本的硬保证。应以真实 Key 做分布与迁移率测试。
4.2 路由不变量
路由不变量是每次建环或更新后都应保持的规则:TreeMap.ceilingEntry(keyHash) 找到位置不小于 Key 哈希值的第一个虚拟节点;若不存在,就回绕到 firstEntry()。所有参与者需要使用相同的节点集合、虚拟节点命名、哈希函数、字节编码和碰撞规则,才能复现同一个环和同一个 Key 的路由。
还要注意示例的碰撞顺延依赖添加顺序:两个虚拟节点争用同一位置时,先添加者占据原位置,后添加者顺延。因此,在发生碰撞时,仅有相同成员集合和规则还不够,构建顺序也必须一致。这里是按代码做的静态推导,未执行碰撞测试。
4.3 复杂度、发布与测试
- 环包含
V个虚拟节点时,定位、添加一个位置和删除一个位置均为O(log V);路由表空间为O(V)。 - 若一个真实节点有
v个虚拟位置,添加或删除它需要处理这些位置,常规成本约为O(v log V)。该估算未计入碰撞顺延的额外探测;重新添加同名节点还需先删除旧位置。 - 更新路由表应构建不可变新快照后原子替换,避免请求读到“只更新一半”的环。
- 数据迁移应限速并预热,必要时短期双读或回源;一致性哈希只减少迁移量,不负责迁移过程的一致性。
- 建议测试:空环、单节点、增删同名节点、哈希碰撞与不同构建顺序、环尾回绕、不同节点数下的负载标准差、扩缩容迁移率及跨语言一致性向量。标准差描述各节点负载的离散程度;一致性向量是一组固定输入及其预期哈希值、路由结果,用于比较不同语言实现。
5. 虚拟节点
真实节点少时,即使哈希函数分布良好,少量节点位置也可能相距很不均匀:负责长区间的节点通常会接收更多 Key。为每个真实节点创建多个虚拟节点,让它承担多个分散区间,可以降低单个过长区间对整体负载的影响。
不同容量节点还可以分配不同数量的虚拟节点表达权重,即期望承担的负载份额。容量更大的节点获得更多位置,通常也会接收更多 Key,但 Key 数量均衡不等于请求量或数据字节量均衡。
虚拟节点越多,分布通常越平滑,但路由表内存和变更成本也会增加,数量应通过真实 Key 分布验证。
6. 成员视图与发布协议
成员视图是某个版本下参与路由的节点集合及其权重等配置。一致性哈希要求所有路由参与者使用相同的成员视图、虚拟节点规则、哈希函数和编码,以及一致的碰撞处理与构建规则。若客户端在发布期间使用不同版本的环,同一个 Key 可能同时被路由到不同节点:旧客户端访问旧归属,新客户端访问新归属。
下面是发布流程的组织方式,具体过渡读写协议仍需按业务设计:
- 为成员视图分配单调递增版本;
- 构建并校验不可变新环;
- 先准备目标节点和数据迁移能力;
- 原子切换路由快照;
- 在过渡期按业务一致性要求执行双读、回源或副本读取;
- 监控迁移率、命中率和节点负载后再清理旧数据。
原子切换表示单个参与者将完整的新路由快照一次替换旧快照,并不意味着所有客户端在同一时刻切换。双读是过渡期按协议读取新旧位置;回源是查询原始存储;副本读取是访问其他数据副本。它们能否满足业务一致性要求,取决于写入、版本判断和清理规则。
一致性哈希不提供成员发现(获知哪些节点可用)、共识(就共同状态达成一致)或数据复制协议,这些机制需要单独设计。
7. 与 Rendezvous Hashing 的对比
Rendezvous Hashing(最高随机权重哈希)对 Key 与每个节点的组合计算稳定得分,并选择得分最高的节点。它不需要显式哈希环,成员较少时实现直观;朴素定位需要遍历节点,节点很多时可再做优化。
两者都能在成员变化时减少重映射,但权重表达、查找成本、实现复杂度和跨语言一致性不同。不能只凭算法名称决定选型,应使用真实 Key 与成员变更序列测量分布和迁移率。
8. 一致性哈希不保证什么
- 不保证热点 Key 被拆散;热点 Key 指访问频率特别高的键,同一个热门 Key 仍路由到一个节点。
- 不自动复制数据或提供高可用。
- 不保证节点间绝对均衡。
- 客户端路由表不一致时,仍可能访问不同节点。
- 不保证迁移期间读写一致;旧节点、新节点和副本的切换需要额外协议。
9. 排障证据
- 各客户端成员视图版本与更新时间;
- 同一组测试 Key 的跨语言路由结果;
- 每个真实节点的 Key 数、请求量、字节量和虚拟节点数;
- 扩缩容前后的迁移比例、缓存命中率和回源 QPS(每秒回源请求数);
- 热 Key 是否集中在单节点,以及副本读取是否符合一致性要求。
扩容后数据库压力升高时,先用上述证据区分原因:路由变化集中在预期区间且命中率下降,可检查预热和迁移进度;同一 Key 在不同客户端的归属不同,应核对成员版本及构建规则;少量 Key 集中贡献大量请求,则要检查热点。只增加虚拟节点数量,无法同时解决这些问题。
10. 容易踩的坑
- 使用分布不佳或跨语言结果不一致的哈希函数。
- 改变虚拟节点命名规则,使原有位置整体变化,可能引发大范围乃至全量重映射。
- 节点列表更新不原子,不同线程看到不同环。
- 只做路由不做副本,节点故障后该节点上的数据可能无法读取;若是缓存,仍需评估集中回源的压力。
- 扩容时忽略回源和数据预热压力。
- 成员列表版本不一致,却把同 Key 路由漂移误判为 Hash 碰撞。
11. 总结
一致性哈希通过稳定的环形映射,把节点变化的影响限制在局部区间。
- 普通取模对节点数敏感,扩缩容会重映射大量 Key。
- 虚拟节点改善分布,也可以表达节点权重。
- 一致性哈希只解决路由迁移问题,热点、副本和一致性仍需单独设计。
专栏主线至此覆盖:复杂度 → 数据结构 → 查找与排序 → 树与图 → 动态规划 → 工程算法。