动态再平衡

集群扩容或节点故障时,数据需要从旧分布迁移到新分布。好的再平衡只迁移必要的最少数据,且不中断读写——一致性哈希的虚拟节点让这件事变得去中心化。

概述

一致性哈希和分片策略解决了"数据怎么分布到节点"。但当集群扩容(加节点)或缩容(节点故障/下线)时,数据需要从旧分布迁移到新分布⁠——这是再平衡(rebalancing)。一个糟糕的再平衡方案可能迁移远超必要的数据量,甚至在迁移期间拒绝服务。好的再平衡只迁移必要的最少数据⁠,且不中断读写⁠。

三种再平衡策略

固定分区:简单但粗糙

预创建远超节点数的分区(如每个节点 100 个分区,10 个节点共 1000 个分区),分区数不变。加节点时,从每个旧节点匀一些分区给新节点。

加节点前: Node-1: [p1..p100],  Node-2: [p101..p200], ... Node-10: [p901..p1000]
加节点后: Node-1: [p1..p90],   Node-2: [p91..p180],  ... Node-11(新): [p901..p990]

• 迁移粒度:整个分区(N 个 key 一起搬),不是逐 key。
• 缺点:⁠分区大小和节点数强绑定⁠——如果初始估算偏差(分区太大或太小),后续难调;分区数是静态的,不能随着数据量增长而分裂。

Redis Cluster 使用这个方案:16384 个固定 slot。

动态分区:分区随数据增长分裂

每个分区设一个大小上限(如 10GB),超过就分裂成两个新分区。节点数变化时,分区整体迁移到新节点——和固定分区类似,但分区数本身是动态的。

分区 p3 到达 10GB → 分裂成 p3a 和 p3b (各 ~5GB)
需要迁移时 → 整体搬 p3a 到新节点

• 优势:分区数和总数据量成正比,不会出现固定分区那种"预创建太多或太少"的问题。
• 代价:需要集中式协调者追踪分区元数据(哪个分区在哪个节点、哪个正在分裂)。HBase 用这个方案。

一致性哈希 + 虚拟节点:去中心化再平衡

一致性哈希里每个物理节点对应多个虚拟节点(vnode,如每节点 ~100 个),分布在整个哈希环上。加节点时,新节点插入环,带走它 vnode 覆盖的 token range(从相邻节点的 vnode 匀过来);删节点时,它的 vnode 对应的 range 被邻近 vnode 接管。

加节点 N11(带 vnode v1101..v1200) 到环:
  原来 token [5000, 5200] 在 N3 的 v303 上
  现在 v1101 覆盖 [5000, 5200] → 这个 range 从 N3 迁移到 N11
  只迁移 token 在新节点范围内的 key, 其他 key 不动

• 最小迁移量⁠:只迁移落在新 vnode 范围内的 key,不是整个分区。
• 去中心化⁠:每个节点通过 Gossip 协议 知道全局路由表,自己算自己该接管哪些 range,不依赖协调者。
• 代价:迁移粒度是单个 vnode 覆盖的 range,可能造成热点(某个 vnode 的 range 数据特别多)——解决办法是动态调整 vnode 数或按负载分裂 vnode(Cassandra 的 virtual node splitting)。

迁移工程:怎么在不中断的情况下搬数据

无论哪种策略,实际搬数据的过程有一些通用实践:

双写过渡

迁移期间,新旧两个节点同时接受对该 range 的写⁠:

1. 元数据更新: range [5000, 5200] 从 N3 迁移到 N11
2. 过渡期: 读写仍然发给 N3, N3 把新写的数据流式传(N11)
3. N11 收到完成信号 → 元数据更新: [5000, 5200] 现归 N11
4. 后续读写直接发 N11

双写保证迁移期间不丢写:即使新节点还没完全就绪,旧节点仍在服务。Cassandra 的 nodetool move / decommission 就是这套。

限流与优先级

数据迁移吃网络和 IO——在业务高峰期全速迁移会拖垮正常请求:

• 限流⁠:限制迁移带宽(如 Cassandra 的 stream_throughput_outbound_megabits_per_sec)。
• 低谷迁移⁠:手动触发,在低峰执行。
• 增量再同步⁠:先传全量 snapshot,再传迁移期间的新写(类似 MySQL 的 binlog 追赶)。

一致性的坑

迁移期间,一条数据的 N 个副本可能跨越新旧分布⁠——部分副本按旧路由,部分已按新路由。解法是先迁移数据,再切换路由元数据⁠(原子切换,不是逐个副本切换)。或像 Cassandra 那样,读的时候去新旧两个位置都查一下(过渡期间有短暂的双路由)。

权衡与失败模式

• 全量重分布⁠:加一个节点就把所有 key 重新 hash → 迁移量 = 全量数据/N,大量无谓迁移。永远用一致性哈希或固定分区 + 搬分区。
• 热点 vnode:某个 vnode 覆盖的 range 数据特别多,迁移时成为瓶颈 → 监控 vnode 大小,动态分裂。
• 迁移期间数据丢失⁠:先切路由再搬数据 → 始终先搬数据,再原子切路由。
• 迁移风暴⁠:一次性加大量节点,同时迁移可能压垮集群 → 逐个节点加,每次等再平衡完成再加下一个(Cassandra 推荐)。

参考

• 论文⁠: "Dynamo"(一致性哈希再平衡, 2007)

Keywords: rebalancing, 固定分区, 动态分区, hash ring, virtual node, vnode, 数据迁移, 最小迁移量, 双写过渡, 渐进迁移, 限流, atomic routing switch, hotspot vnode