企业官网建设流程全解析

sn: 25
batch: 5
round: 9
topic: 一致性哈希算法与分片策略

那次缩容操作现在想起来还是很典型：业务低峰，我们把缓存集群从 8 台缩到 6 台。缩容完成的一瞬间，DB 的 QPS 涨了 9 倍，命中率从 95% 掉到 41%，好在压测过 DB 极限容量，扛住了没挂。如果当时用的是普通取模分片，掉到 41% 都算是运气好——数学上会掉到 25%。

一致性哈希的经典解释通常是"取模换环形空间 + 虚拟节点"，但背完概念很多人还是不明白它到底解决了什么、没解决什么。这篇从我踩过的缓存缩容事故讲起，把环形哈希的数学、虚拟节点的真实作用、以及它不适合的场景一次说清。

普通取模的问题：变的是映射，不是数据

普通分片是shard = hash(key) % N。N 从 8 变成 6，对任何一个 key，hash % 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 TreeMap<Long, String> ring = new TreeMap<>(); private final HashFunction hash; public String getNode(String key) { long h = hash.hash(key); // 1. 找环上第一个 >= h 的节点（顺时针方向） Map.Entry<Long, 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()，它的分布特性对一致性哈希来说不够随机（前缀相似的 key，hash 值相关性高），改用 MD5 截断或 MurmurHash 后倾斜现象明显缓解。Ketama 算法（Memcached 客户端标准）用的就是 MD5 取模切分。

数据迁移：算法之外的脏活

一致性哈希只回答"key 应该归谁"，迁移过程本身是另一摊工程。我们缩容事故后的落地清单：客户端（或代理层）支持新旧两套环并存，读取时先查新环、miss 再查旧环并回填新环（类似双写读迁移）；写入双发新旧两套环，稳定后切读、停旧写；迁移期间给 DB 加一层短期限流保护，防止回源风暴。整个过程灰度 2 小时完成，命中率最低点 87%——对比之前 41% 的裸奔，这就是预案的价值。

最后一个观点：很多场景其实用不到一致性哈希。Redis Cluster 用预分槽（16384 槽），扩缩容是显式的槽位迁移，可控性远好于客户端一致性哈希；MySQL 分库分表用基因法或查表法，扩容走双写迁移。一致性哈希的最佳栖息地是无中心、客户端直接路由、节点频繁增减的缓存层。为了分库分表硬上一致性哈希，后面扩容时的数据迁移会比槽位方案痛苦得多——这是我见过的选型弯路里最多的一种。

加权虚拟节点与哈希函数的实现细节

把虚拟节点机制写完整，权重和哈希质量两个细节就能看清：

public class WeightedConsistentHashRing { private final TreeMap<Long, 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.Entry<Long, 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 倍内存的新机器配 weight=8 就能承接近 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 分别顺延给各自的后继节点。如果这些后继节点里恰好有一台刚扩容进来（虚拟点也很多），负载会怎么变化？这个交互效应会不会造成新的倾斜？评论区聊聊你的分析。