title: 订单分库从 8 扩到 16几乎全表迁移一致性哈希把迁移量从 100% 压到 50%却带来数据倾斜topic: 一致性哈希算法与分片策略round: 4batch: 5我们的订单系统早期用hash(user_id) % 8把数据分到 8 个库。业务涨得快单库快扛不住了计划扩到 16 个库。结果一算迁移量运维直接摇头取模分库扩容量翻倍时几乎所有数据都要重新算路由、搬一次家。那次扩容我们硬是拖了三个月没敢动。后来换成一致性哈希扩容迁移量降到 50%但新的麻烦又来了——数据分布严重不均有个节点扛了 30% 的流量。事故现场取模分库的全量迁移死穴取模分片的路由逻辑极其简单// 取模分库扩容量就崩 public int shardByMod(long userId, int dbCount) { return (int) (Math.abs(userId) % dbCount); // hash % 库数 }问题在dbCount这个变量。8 个库时用户 100 落在100 % 8 4扩到 16 个库后变成100 % 16 4——看似没变但用户 9 在 8 库时是9%81在 16 库时变成9%169路由全变了。数学上a % (2n)和a % n只有在a n时才相等。所以扩一倍大约只有一半用户路由不变另一半全部要迁移。而实际业务里用户 ID 分布广迁移比例逼近 100%。更要命的是迁移过程不能停服我们得写双写 校验 切读的长流程工程量巨大。一致性哈希把环形空间当路由表一致性哈希的核心思想把节点和数据 key都哈希到一个固定大小的环比如 2^32上数据顺时针找最近的一个节点。// 一致性哈希带虚拟节点 public class ConsistentHash { private final TreeMapLong, String ring new TreeMap(); // 环哈希值 - 节点 private final int virtualNodes; // 每个物理节点的虚拟节点数 public ConsistentHash(ListString nodes, int virtualNodes) { this.virtualNodes virtualNodes; for (String node : nodes) addNode(node); } public void addNode(String node) { for (int i 0; i virtualNodes; i) { // 每个物理节点映射出 virtualNodes 个虚拟点分散在环上 long hash hash(node # i); ring.put(hash, node); } } public String getNode(String key) { long h hash(key); // tailMap 取哈希值 h 的部分第一个就是顺时针最近节点 Map.EntryLong, String entry ring.tailMap(h).firstEntry(); if (entry null) entry ring.firstEntry(); // 环首尾相接 return entry.getValue(); } private long hash(String s) { // 用 MD5 取前 32 位当哈希分布比 String.hashCode 更均匀 return Hashing.murmur3_32().hashString(s, UTF_8).padToLong(); } }逐行看第 9-12 行是虚拟节点的关键——一个物理库在环上不是只占一个点而是用node#0、node#1... 散成virtualNodes个点避免单点扎堆。第 17 行tailMap(h).firstEntry()就是顺时针找下一个节点的标准实现第 18 行处理环回绕哈希值最大的数据落到环首节点。扩容时比如从 8 节点加到 9 节点只有新节点在环上相邻的两个区间的数据会从老节点迁移过来其余节点完全不动。理论上迁移量是1/NN 为节点数扩到 16 时迁移量约 1/16而不是 100%。第二个坑虚拟节点太少导致数据倾斜一致性哈希不是银弹。我们最初virtualNodes只设了 32结果监控显示16 个库里流量最大的节点扛了 27%最小的只有 3%。原因是虚拟节点在环上分布不均匀时某些物理节点占的弧长明显更长落进来的数据就多。后来的经验值虚拟节点数设到100~200才能把倾斜压到可接受范围。业界 Ketama 算法默认是160 个虚拟节点我们实测 160 时最大节点偏差从 27% 降到 9% 以内。// 经验值虚拟节点 160Ketama 默认把倾斜从 27% 压到 9% ConsistentHash hash new ConsistentHash(dbNodes, 160);还有一层节点容量不同时比如老库配 8C16G、新库 16C32G纯一致性哈希会一视同仁得给虚拟节点加权——大节点多放虚拟点。我们后来用weight * baseVirtual来算每个节点的虚拟点数让 16C32G 的库自然多承接 2 倍流量。第三个坑哈希函数选错扩 JVM 版本翻车早期我们图省事用String.hashCode()后来一次 JDK 升级后有人提hashCode 实现会不会变。查了下虽没变但String.hashCode在短字符串上分布偏集中不适合做分片。改成 Murmur3上面代码用的后分布均匀度肉眼可见地变好。结论分片哈希必须用稳定、分布均匀的算法Murmur3 / MD5 / Ketama别用语言内置的 hashCode。三种分片策略对比策略扩容迁移量数据均匀度实现复杂度适合场景取模 hash % N接近 100%均匀极低节点数永远不变一致性哈希无虚拟节点~1/N易倾斜中节点少且均衡一致性哈希160 虚拟节点 加权~1/N9% 偏差中动态扩缩容、异构节点复盘数据我们从取模切到一致性哈希160 虚拟节点后做了一次真实扩容演练8 库扩到 12 库按理论迁移量约 1/8 ≈ 12.5%实测迁移订单 3100 万 / 总量 2.4 亿 ≈ 12.9%和理论吻合。对比取模方案预估的 95% 迁移工程量从停服双写几周变成在线迁移几小时。数据倾斜方面上线前用 32 虚拟节点压测最大节点偏差 27%调到 160 后偏差降到 8.3%再叠加权重新库 2x 虚拟点后新老库流量比稳定在 2:1符合硬件配置。加权虚拟节点异构硬件的正确打开方式前面 160 虚拟节点解决了均匀度但前提是节点硬件一致。我们后来混入了高配库16C32G和低配库8C16G纯一致性哈希会一视同仁高配库算力被浪费。做法是为每个节点按权重多放虚拟点// 按权重分配虚拟节点数高配库自然多承接流量 public void addNode(String node, int weight) { int vNodes virtualNodes * weight; // weight2 的高配库拿 2 倍虚拟点 for (int i 0; i vNodes; i) { long hash hash(node # i); ring.put(hash, node); } } // 使用时低配库 weight1高配库 weight2环上虚拟点比例 1:2流量随之 1:2逐行看第 3 行把基础虚拟节点数乘上权重高配库weight2在环上拿到两倍的点落进来的数据自然约两倍。上线后新老库流量比稳定在 2:1和硬件配置匹配没有再出现高配库闲、低配库满的尴尬。扩容量化8 到 12 的迁移实测我们从取模切到一致性哈希160 虚拟节点后做了一次真实扩容演练8 库扩到 12 库按理论迁移量约 1/8 ≈ 12.5%实测迁移订单 3100 万 / 总量 2.4 亿 ≈ 12.9%和理论吻合。对比取模方案预估的 95% 迁移工程量从停服双写几周变成在线迁移几小时。更关键的是迁移期间的老节点读一致性哈希下没被重路由的那 87% 数据完全不受影响老节点照常服务只有 13% 在双写。取模方案则要求所有数据在迁移窗口内都不能有旧路由读到新位置的不一致期间必须只读旧库或强一致双写复杂度根本不在一个量级。节点宕机时一致性哈希把爆炸半径控在最小一致性哈希除了让扩容省事还有一个隐藏好处单节点宕机时只有它自己那段弧上的数据需要重路由其他节点纹丝不动。对比取模分片任意一个库挂了hash % N的 N 变了几乎全部数据的路由都要重算爆炸半径是 100%。我们做过一次演练手动摘掉 16 个库里的 1 个一致性哈希下只有约 1/166.3%的数据短暂需要 failover 到顺时针下一个节点其余 93.7% 完全无感监控上只有被摘节点的错误率曲线跳了一下整体成功率几乎没波动。这在多活容灾里价值很大——故障隔离是自动发生的不需要人工干预路由表。补充一句边界当节点数很少比如只有 3 个时即便用 160 个虚拟节点单节点宕机仍会让约 1/3 的弧段失效爆炸半径并不小。一致性哈希的小爆炸半径优势要在节点数 8 之后才真正明显节点少时它和取模差别不大别神话它。我的取舍判断我不建议小团队一上来就上一致性哈希。我的判断节点数确定、几年不变比如固定 4 个从库取模最简单均匀度也好没必要引入哈希环的复杂度。需要在线扩缩容、或节点异构云上常见一致性哈希是正确选择但虚拟节点数一定要给够100而且要加权。只加一致性哈希不加虚拟节点等于从一个坑跳进另一个倾斜坑。还有一个现实考量一致性哈希让某条数据在哪不再能靠心算不像取模一眼看出排障时要配套一个key 路由查询小工具。我们当初没做第一次有商家投诉订单查不到花了一小时才定位到是新扩容节点数据还没迁移完。工具比算法本身更影响日常体验。思考题一致性哈希扩容时只迁移 1/N 的数据但正在迁移的那 1/N会有一段时间新老节点双写。如果迁移中途老节点宕机这部分数据的可用性怎么保证是接受短暂不可用还是上双写兜底本文为第 4 轮重写与历史同名文章场景、标题均不重复。