4.1 分片与副本：数据放在哪里

分布式存储先解决两件事：用分片扩大容量和吞吐，用副本抵抗节点或故障域失效。分片决定“谁负责这条数据”，副本决定“还要放在哪些地方”。

取模分片为何难扩容

shard = hash(key) mod N

当 N 改变时，大量 key 会重新映射。例如哈希值为 0–11，分片从 3 个扩到 4 个，只有 0、1、2 仍落在原编号分片，12 个值要搬 9 个。各路由方还必须使用同一种哈希算法、输入编码和种子，不能直接依赖会按进程随机化的语言内置哈希。问题不只是搬运字节：迁移期间新旧位置并存，读写路由、增量追赶、限速和故障恢复都需要协调。

固定数量的逻辑分片可以降低节点变化影响：先把 key 映射到大量逻辑分片，再把逻辑分片分配给物理节点。扩容时移动一部分逻辑分片，而不是改变整个 hash 函数。

Hash 与 Range 的取舍

分片	优势	代价
Hash	分布通常均匀，点查路由直接	范围查询跨分片，局部性差
Range	范围扫描和相邻数据局部性好	热区、分裂和元数据管理更复杂
复合策略	可兼顾租户与时间	路由和容量模型更难

业务 key 分布比算法名称更重要。单个超级租户、递增时间键或少数热门对象会形成热点，即使整体字节分布看起来均匀。

一致性哈希与 Rendezvous Hashing

一致性哈希把节点和 key 映射到环，key 由顺时针后继节点负责。增删节点时主要移动受影响 token 的相邻范围；一个物理节点拥有多个 token 时，会涉及环上的多段范围。虚拟节点让一个物理节点拥有多个 token，可改善均衡并支持按容量分配。

Rendezvous Hashing 则为每个 (key, node) 计算分数，选择最高分节点；选择前 k 个不同物理节点可得到候选副本集合，再按故障域约束筛选。它不需要显式环，若分数函数和已有节点身份保持不变，增加节点只会让由新节点获胜的 key 改换所有者，删除节点只影响原本由它负责的 key。朴素实现每次需给所有节点打分，节点很多时也要考虑路由计算成本。

两者都不能自动解决：

• 节点容量不同；
• rack/zone 失效相关性；
• 热 key；
• 数据迁移时的带宽和尾延迟；
• 节点列表不一致导致的路由分歧。

副本必须跨故障域

复制因子 3 若三个副本都在同一机架，机架断电时等于没有容灾。副本放置策略要认识 host、rack、zone 和 region：

partition P
  ├─ replica 1: zone-a / rack-1
  ├─ replica 2: zone-b / rack-2
  └─ replica 3: zone-c / rack-3

跨地域同步确认会把相应网络往返带入写入延迟，网络分区能否继续写取决于确认门槛及副本布局。异步复制可减少前台等待，但灾难时可能丢失尚未送达的写入。RPO 表示可接受的数据回退量（常用时间衡量），RTO 表示恢复服务所允许的时间，两者必须与故障域一起设计。

Rebalancing 是在线协议

一次安全迁移通常经历：

1. 新节点加入但暂不承担读流量；
2. 从现有副本复制快照；
3. 从与快照对应的位置捕获增量，连续追赶迁移期间写入，避免快照与增量日志之间留空档；
4. 在同一逻辑位置比较校验和、行数和业务不变量；
5. 按带版本的路由切换副本责任，旧所有者拒绝或转发过期路由的写入，避免切换后两边各自确认；
6. 保留回退窗口后删除旧副本；回退前也要追上切换后的写入，旧副本还在不等于它还新。

迁移要限速，并把恢复流量、用户流量和后台 compaction 放进同一容量模型。否则扩容可能先压垮集群。

热点不能只靠加节点

热点来源包括：

• 单个 key 请求量极高；
• 分区键基数过低；
• 时间范围集中到当前分片；
• 大分区导致单次 compaction 和恢复过重；
• 查询扇出到全部分片。

应通过 key 拆分、时间 bucket、缓存、请求合并、局部复制或业务限流处理。拆 key 会引入聚合和一致性成本，必须先定义读写语义。

设计验收

• 分片 key 是否匹配主要查询？
• 单分片大小和请求率上限是什么？
• 副本是否跨真实故障域？
• 节点增删时谁拥有路由版本？
• 迁移如何追赶并验证增量？
• 一个热点 key 如何被识别和缓解？

下一课以 leaderless 复制和 Cassandra 为例，分析 quorum 相交、冲突解决与副本修复。

参考资料

• Karger et al., Consistent Hashing and Random Trees
• Thaler, Ravishankar, Using Name-Based Mappings to Increase Hit Rates