KV存储（3）：分片、路由与再均衡（hash / consistent hashing）

这一篇聚焦 KV 存储做成“多机可扩展系统”时绕不开的第一件事：数据怎么分片、请求怎么路由、扩缩容怎么再均衡。主题看起来像“hash 环”，但工程上真正决定可用性与性能的是：

• 分片粒度：一个节点承担多少个分片（token / vnode）？热点会不会被平摊？
• 路由一致性：客户端路由表与服务端实际 ownership 不一致时会发生什么？
• 迁移策略：迁移期间读写如何保证正确性？如何避免迁移把线上打爆？
• 观测与回滚：再均衡失败如何止损？如何识别“正在形成的热点”？

本文按“模型 → 机制 → 代价 → 运维指标”组织，图用 ASCII 表示。

1. 分片的目标：让系统能横向扩展且可预测

理想目标：

• 负载均衡：不同节点的 QPS、IO、空间尽量均衡
• 可扩缩容：加/减节点时只迁移一小部分数据
• 可定位：给定 key 能快速找到负责的节点集合
• 容错域可控：机架/可用区故障不会集中打到某一段 keyspace

工程上，分片方案通常必须同时满足“数据面效率”和“控制面可运维”。

2. 最简单的 hash 分片：为什么不够用

2.1 直接 node = hash(key) % N

好处：简单、路由 O(1)、无需元数据。

问题：扩缩容代价极高。

N=4: node = h(k) % 4
N=5: node = h(k) % 5

几乎所有 key 的归属都会变化 -> 全量迁移

2.2 工程结论

只要系统需要在线扩缩容、节点数量变动不可避免，就需要“增量迁移”而不是“全量重算”。

3. 一致性哈希：让迁移变成“局部变化”

3.1 hash ring 与区间归属

把 hash 空间视作 ([0, 2^m)) 的环。每个节点在环上占若干位置（token），节点负责其 token 到下一个 token 之间的区间（或反向定义）。

示意（token 简化为 0..99）：

Ring: 0 -------------------------------------- 99 (wrap)

tokens:
  A: 10, 60
  B: 25, 80
  C: 40, 90

ownership (clockwise):
  (10..25] -> B
  (25..40] -> C
  (40..60] -> A
  (60..80] -> B
  (80..90] -> C
  (90..10] -> A

路由规则（典型）：对 key 求 hash 得到点 p，找到“环上第一个 token >= p”的节点为 owner（wrap）。

3.2 为什么能“只迁移一部分”

新增节点 D 只会插入若干 token，影响的是这些 token 相邻的少数区间：

• 旧 owner 的一部分区间被切走
• 其余区间不变

迁移量近似与新增 token 覆盖的区间大小成比例，而不是全量。

4. 虚拟节点（vnode）：解决“节点不均衡”和“热点”

4.1 单 token 的问题

如果每个节点只有 1 个 token：

• 由于 token 随机，区间大小分布不均 → 负载不均
• 节点性能差异（异构硬件）无法表达
• 热点 key 落入一个大区间会拖垮单节点

4.2 vnode 的思路

每个物理节点分配很多 token（例如 256/1024 个），让区间更细粒度：

• 大数定律让区间大小更均匀
• 热点更容易被“切碎”并摊到不同节点（仍取决于 key 分布）
• 异构节点可用不同 token 数表示权重

工程提示：

• vnode 太多会增加 ring 元数据体积与查找开销
• vnode 太少会导致均衡性差

5. 路由：客户端路由 vs 服务端路由

5.1 客户端路由（client-side routing）

客户端持有 ring/token 表，直接把请求发到目标节点。

优点：

• 少一跳，延迟更低
• 节点不做转发，降低负载

缺点（关键）：

• 路由表可能过期：拓扑变化、迁移中、节点抖动
• 需要传播与一致性协议：至少保证“最终收敛”

5.2 服务端路由（server-side routing）

客户端发给任意入口（或 coordinator），由服务端转发到 owner。

优点：

• 客户端简单
• 路由表一致性由服务端承担

缺点：

• 多一跳
• coordinator 可能成为瓶颈（除非做无状态水平扩展）

5.3 常见折中：smart client + server fallback

客户端按本地路由表直连；若节点发现“请求不属于本节点”，返回重定向或进行一次转发：

Client -> NodeX (wrong owner)
  NodeX -> returns "moved to NodeY" (or forwards once)
Client updates route table

工程落点是“错误路径的成本是否可控”：如果路由频繁过期，会形成大量额外 RTT 与转发压力。

6. 扩缩容与再均衡：迁移不是“复制文件”那么简单

6.1 再均衡的三个阶段（抽象）

1) 规划：哪些 token 区间从哪些节点迁到哪些节点 2) 数据迁移：把区间内的数据复制到新 owner 3) 切换 ownership：让新路由生效，并清理旧副本

关键难点集中在阶段 2/3：迁移期间有读写并发，必须定义一致性语义。

6.2 迁移期间的读写语义（两类典型做法）

做法 A：双写 + 最终收敛

• 在迁移窗口内，写入同时写新旧 owner（或写到 quorum 覆盖两侧）
• 切换后，新 owner 一定包含最新数据

代价：写放大，且需要对失败重试、幂等做严格约束。

做法 B：单写 + 转发/重试

• ownership 切换前写旧 owner
• 切换后写新 owner
• 迁移期间若请求打到错误侧，由服务端转发或客户端重试

代价：错误路径多、尾延迟抖动，且要处理“切换瞬间的并发竞态”。

6.3 一个可落地的“切换点”模型

在控制面定义一个 epoch（配置版本）：

config_epoch = 42
ownership_map(epoch=42): token ranges -> owners

write(key, value, epoch=42):
  node rejects if local epoch < 42
  node accepts only if it is owner under epoch=42

好处：把“谁是 owner”变成可验证的条件，避免旧配置写入新 owner 或反之导致不一致。

7. 热点问题：分片解决不了“极端倾斜”

一致性哈希擅长解决“均匀随机 key”的负载均衡，但真实业务常见：

• 某些 key（或 key 前缀）超级热
• 某些租户/分区规模远大于其他

对策通常需要超出分片本身：

• key 打散：把热点 key 拆成多个子 key（需要应用语义配合）
• 分层缓存：把热点读挡在 cache
• 热点检测 + 动态复制：对热点分片临时增加副本或读副本
• 限流：保护系统稳定性

8. 运维与观测：再均衡是否安全，靠指标说话

建议最少监控：

• 节点维度：QPS、CPU、磁盘带宽、读写延迟（P50/P99/P999）、错误率
• 分片维度：每 token/分片的 key 数、数据量、读写 QPS、热点 topN
• 迁移维度：迁移速率（MB/s）、迁移 backlog、失败重试次数、切换次数
• 路由错误：重定向/转发比例，配置 epoch 不匹配次数

再均衡的常见失败模式：

• 迁移太快导致后台 IO 抢占前台（尾延迟飙升）
• 迁移太慢导致长时间双写/错误路径，整体成本过高
• 热点未被切碎，迁移后仍集中在某节点

9. 小结

分片与路由的“正确打开方式”不是画一个 hash 环，而是把它当成一套工程系统：

• vnode/权重解决均衡与异构
• 客户端/服务端路由决定错误路径成本
• 迁移与切换点（epoch）决定一致性与尾延迟
• 热点需要额外手段处理

下一篇会把“分片之后的复制与一致性”补齐：读写如何走 quorum、写入如何在副本间收敛、以及常见的故障与修复路径。