缓存集群从 8 台缩到 6 台，命中率从 95% 跌到 41%：一致性哈希解决的到底是谁的问题

sn: 25batch: 5round: 9topic: 一致性哈希算法与分片策略那次缩容操作现在想起来还是很典型业务低峰我们把缓存集群从 8 台缩到 6 台。缩容完成的一瞬间DB 的 QPS 涨了 9 倍命中率从 95% 掉到 41%好在压测过 DB 极限容量扛住了没挂。如果当时用的是普通取模分片掉到 41% 都算是运气好——数学上会掉到 25%。一致性哈希的经典解释通常是取模换环形空间 虚拟节点但背完概念很多人还是不明白它到底解决了什么、没解决什么。这篇从我踩过的缓存缩容事故讲起把环形哈希的数学、虚拟节点的真实作用、以及它不适合的场景一次说清。普通取模的问题变的是映射不是数据普通分片是shard hash(key) % N。N 从 8 变成 6对任何一个 keyhash % 8和hash % 6几乎必然不相等——只有 key 的 hash 恰好是 24 的倍数lcm(8,6)才落回原节点概率 1/24。也就是说约 96% 的 key 换了节点缓存里明明还有 6 台机器的数据但客户端全找错了地方。命中率掉到 4% 上下才是理论值我们实测 41% 是因为缩容后有部分自然过期回源重新填充。看清楚这个本质很重要数据还在是映射关系全变了。所以一致性哈希的目标不是数据分布更均匀而是节点数量变化时映射关系的变化最小化。环形哈希把全部重排变成局部迁移一致性哈希把哈希空间组织成一个环0 到 2^32-1节点和 key 都哈希到环上key 顺时针找到的第一个节点就是它的归属。节点的增删只影响环上相邻区间public class ConsistentHashRing { private final TreeMapLong, String ring new TreeMap(); private final HashFunction hash; public String getNode(String key) { long h hash.hash(key); // 1. 找环上第一个 h 的节点顺时针方向 Map.EntryLong, String entry ring.ceilingEntry(h); if (entry null) { // 2. 转过一圈没找到回到环头部最小 hash 的节点 entry ring.firstEntry(); } return entry.getValue(); } public void addNode(String node) { // 3. 节点加入只接管新位置到前一个节点之间的 key ring.put(hash.hash(node), node); } public void removeNode(String node) { // 4. 节点摘除它的 key 顺延给下一个节点其余 key 不动 ring.remove(hash.hash(node)); } }逐行拆第 1 行ceilingEntry是整个算法的核心操作TreeMap 的红黑树查找 O(log N)第 2 行处理环绕——哈希空间是环TreeMap 是线性的超过最大值要绕回头部第 3 行新增节点时数学上只有新节点位置到逆时针前一个节点这段区间的 key 需要迁移给它其余 key 的映射完全不变——从 96% 重排降到 8/9新增一台时分摊约 1/新总数 的流量。但朴素环形哈希有个致命缺陷节点物理位置随机落在环上8 个节点可能挤在环的一段弧里出现数据倾斜——一个节点扛 40% 的 key另一个只有 3%。我们第一次实现就栽在这3 台新机器 hash 值恰好相邻其中一台的 key 量是另外两台的 5 倍内存先打满的是它。虚拟节点解决的不是分布均匀这么简单虚拟节点的做法每个物理节点在环上放 100-200 个虚拟副本key 先映射到虚拟节点虚拟节点再映射到物理节点。大数定律开始起作用虚拟点足够多时每个物理节点分到的区间长度趋于均匀。但我要纠正一个普遍误解虚拟节点解决的不只是数据倾斜更是异构节点权重和局部迁移的稳定性。三个作用分开说其一均匀化这是最容易理解的其二异构权重——新机器内存是老机器 2 倍给新机器放 2 倍数量的虚拟节点即可权重调节变成配置问题其三也是最容易被忽略的摘掉一台物理节点时它散布在环上的 150 个虚拟点的 key 分别顺延给环上不同位置的后继节点负载被分摊到多个节点而不是集中砸给顺时针的下家——这对缩容时的热点保护非常关键。真实实现里还有一个工程细节必须处理哈希函数的质量。我们早期用String.hashCode()它的分布特性对一致性哈希来说不够随机前缀相似的 keyhash 值相关性高改用 MD5 截断或 MurmurHash 后倾斜现象明显缓解。Ketama 算法Memcached 客户端标准用的就是 MD5 取模切分。数据迁移算法之外的脏活一致性哈希只回答key 应该归谁迁移过程本身是另一摊工程。我们缩容事故后的落地清单客户端或代理层支持新旧两套环并存读取时先查新环、miss 再查旧环并回填新环类似双写读迁移写入双发新旧两套环稳定后切读、停旧写迁移期间给 DB 加一层短期限流保护防止回源风暴。整个过程灰度 2 小时完成命中率最低点 87%——对比之前 41% 的裸奔这就是预案的价值。方案节点变化时的重排比例倾斜控制适用场景hash % N接近全部~96%无节点数永远固定一致性哈希无虚拟节点1/N差随机倾斜节点少且同构一致性哈希 虚拟节点1/N分摊好可加权动态扩缩容集群有槽位预分片Redis Cluster槽位粒度迁移好官方支持运维简单最后一个观点很多场景其实用不到一致性哈希。Redis Cluster 用预分槽16384 槽扩缩容是显式的槽位迁移可控性远好于客户端一致性哈希MySQL 分库分表用基因法或查表法扩容走双写迁移。一致性哈希的最佳栖息地是无中心、客户端直接路由、节点频繁增减的缓存层。为了分库分表硬上一致性哈希后面扩容时的数据迁移会比槽位方案痛苦得多——这是我见过的选型弯路里最多的一种。加权虚拟节点与哈希函数的实现细节把虚拟节点机制写完整权重和哈希质量两个细节就能看清public class WeightedConsistentHashRing { private final TreeMapLong, PhysicalNode ring new TreeMap(); private final Hashing hashing Hashing.murmur3_128(); // 1. MurmurHash快且分布均匀 public void addNode(PhysicalNode node) { int vNodeCount 150 * node.getWeight(); // 2. 权重映射为虚拟节点数量 for (int i 0; i vNodeCount; i) { // 3. 虚拟点 key 节点名#VN序号 再哈希散布在环的不同位置 long hash hashing.hashString(node.getName() #VN i, StandardCharsets.UTF_8).asLong(); ring.put(hash, node); } } public PhysicalNode getNode(String key) { long h hashing.hashString(key, StandardCharsets.UTF_8).asLong(); Map.EntryLong, PhysicalNode entry ring.ceilingEntry(h); // 4. 环绕处理 空环防御 if (entry null) { entry ring.firstEntry(); } return entry null ? null : entry.getValue(); } }逐行拆第 1 行选 MurmurHash 而不是String.hashCode()原因在前面说过——hashCode 对相似前缀的分布质量差商品 ID 这类有规律的 key 会出现系统性倾斜第 2 行权重直接乘在虚拟点数量上8 倍内存的新机器配 weight8 就能承接近 8 倍的 key权重调节从算法问题变成配置问题第 3 行虚拟点的命名要带节点名和序号保证同一物理节点的虚拟点彼此独立散布第 4 行空环返回 null 必须处理我们见过客户端在集群整体重启时全量 getNode 返回 null 后没有降级直接 NPE 打爆日志。再看迁移期的双环读取这是算法落地的最后一公里public String getWithMigration(String key) { // 1. 先查新环绝大多数 key 在新环上直接命中 String node newRing.getNode(key); String val clientOf(node).get(key); if (val ! null) { return val; } // 2. 新环 miss查旧环缩容后被摘节点的数据还留在旧节点上 String oldNode oldRing.getNode(key); if (oldNode ! null) { val clientOf(oldNode).get(key); if (val ! null) { // 3. 回填新环后续请求直接走新环 clientOf(node).set(key, val, ttl); } } return val; }逐行说第 2 行旧环兜底的本质是迁移窗口内的过渡路由命中率损失被限制在迁移的几分钟内第 3 行回填是收敛的关键每条 miss 都让新环越来越全这个模式跑满一个 TTL 周期后旧数据全部过期或回填完毕可以安全下线旧环。对比裸切环命中率 41% 那次双环迁移的命中率最低点是 87%DB 压力曲线平滑得多的同时不需要停写。思考题带虚拟节点的一致性哈希里物理节点 A 摘除后它的 150 个虚拟节点的 key 分别顺延给各自的后继节点。如果这些后继节点里恰好有一台刚扩容进来虚拟点也很多负载会怎么变化这个交互效应会不会造成新的倾斜评论区聊聊你的分析。