分片把不同键交给不同服务组。扩容时，计算一个新映射并不困难；困难在于旧组还有请求、新组正在接收数据、控制器可能随时停止，而客户端缓存的地址不会同时更新。迁移协议必须说明每个阶段谁能接受业务请求，以及失败后凭什么继续。

分布式系统（23）：Dynamo风格复制、Quorum与冲突版本

前篇讨论 Dynamo 风格副本选择与冲突版本。本篇切换到每个分片最多一个有效服务归属的模型：每个组可以在内部使用复制状态机，跨组迁移则把源撤权、状态传输和目标授权串成有序步骤。允许迁移窗口暂时没有可用服务者，但不允许两个组各自成功修改同一分片。

映射函数不能代替迁移协议

范围分片按排序后的键空间划分区间。相邻键通常在少量分片中，范围扫描容易定位；若新写集中在尾部区间，负载也可能集中在那里。Bigtable 的 tablet 就以行键范围为分布单元，这个组织方式服务于排序与范围访问，而不是所有场景下的负载均衡保证。Bigtable，OSDI 2006，§2

哈希分片先把键映射到散列空间，再分配给节点或逻辑分片。它可以打散具有相近前缀的键，但范围查询可能需要访问多个分片。若直接使用 hash(key) mod n，改变 n 会改变许多键的归属。一致性哈希改用环上的位置及节点标记，在其随机分布和映射前提下限制成员变化带来的重映射量；“consistent”在这里不表示线性一致性。Karger 等，STOC 1997，§4

flowchart TD
  K[键集合] --> R[范围分片：按键排序后切区间]
  K --> H[哈希分片：先映射散列空间]
  H --> M[取模：节点数变化可能广泛重映射]
  H --> C[一致性哈希：环上位置与节点标记]
  R --> O[计算期望归属]
  M --> O
  C --> O
  O --> T[仍需迁移数据并切换服务权限]

对象数量分布均匀，不等于字节数量均匀，更不等于请求负载均匀。一个键可以远大于其他键，也可以独占大部分请求。虚拟节点把可重新分配的范围切得更细，有利于调整多个范围的放置，但不会自动把一个热键拆成多个独立写单元。

flowchart TD
  Q[大量请求都访问同一个键 k] --> P[k 映射到分片 s]
  P --> G[s 当前由组 A 服务]
  V[增加更多虚拟节点] --> B[更细地分配其他键或范围]
  B -.-> P
  G --> H[热键仍集中于一个服务归属]
  H --> D[需要按业务拆键、聚合或其他专门策略]

是否能拆键取决于业务操作。如果所有请求都要求对同一个计数器执行严格串行的条件更新，改变映射算法不能消除这个串行约束。迁移热分片可以改变承载机器，却不一定提高该分片本身的可并行度。本篇实验不提供负载或吞吐数据，只验证归属迁移的安全边界。

分片归属变化与 Raft 成员变化是两件事

设组 A 和组 B 各自有固定成员、独立日志和 quorum。把分片 s 从 A 交给 B，改变的是谁存储和服务这部分业务状态。它没有把 A 的 Raft peer 列表替换成 B，也没有合并两条日志。

flowchart TD
  subgraph GA[固定成员组 A]
    RA[A 自己的复制日志与 quorum] --> SA[分片 s 与 t]
  end
  subgraph GB[固定成员组 B]
    RB[B 自己的复制日志与 quorum] --> SB[接收分片 s]
  end
  SA -->|跨组迁移 s 的状态与权限| SB
  C[配置与迁移控制器] --> GA
  C --> GB
  C --> X[没有把两个组的成员合成一个 quorum]

MIT 6.5840 Spring 2026 的公开 Lab 5 说明明确区分这两类变化，并把配置序号、冻结、安装、删除以及控制器恢复列为任务要点。本文只以公开问题和协议约束为课程结构依据，实验接口与有限实现独立设计，没有复用课程作业解答。MIT Lab 5

组内共识只能保证本组状态转换有一致顺序。两个组分别通过本地多数确认，并不意味着跨组权限已经互斥。如果 A 仍能接受写入，B 又依据一份旧快照开始服务，两组都可能在各自合法的日志中保存不同结果。避免这种情况需要额外的迁移协议。

安全条件是最多一个服务者

定义 serve(g,s) 为组 g 当前会接受分片 s 的新业务读写。需要保持的不变量是：

1
对每个分片 s：sum_g serve(g,s) <= 1

这不限制物理副本数。源冻结后可以保留完整快照，目标也可以保存一份安装结果；只要源不再接受新请求，两个物理副本并存并不违反条件。相反，即使配置目录只写着一个 owner，旧组没有撤销服务权限，仍然可能出现双服务。

flowchart TD
  A[开始：A 服务，B 不服务] --> F[冻结 A]
  F --> Z[中间窗口：A 与 B 都不服务]
  Z --> I[安装 B，授予新 epoch 权限]
  I --> B[B 服务，A 仍冻结]
  B --> D[清理 A 的数据，保留迁移墓碑]
  D --> P[发布目录指向 B]

冻结必须与业务写共享组内顺序：在 freeze 之前成功应用的写进入迁移快照；在 freeze 之后到达的写拒绝。本文模型将业务读写都冻结。若允许旧组继续返回旧读，而目标已经处理新写，就需要额外读屏障或转发协议；不能只禁止旧组写入便推断所有读都正确。

Bigtable 2006 的 tablet 分配也强调服务权限：tablet server 失去相应锁后停止服务，master 在确认锁与相关元数据条件后才重新分配。它依赖 Chubby 和 GFS，并非本文的文件模型或 Raft 迁移实现。可借鉴的是“先撤销旧服务权限，再授予新权限”的责任划分，不能直接移植其故障检测结论。Bigtable，§5.2

冻结、安装、删除与发布

控制器先持久化 next=(s,e,A,B)，表示唯一批准的迁移意图。这个身份同时绑定分片、epoch、源和目标；只比较一个递增整数不足以发现“同一 epoch 指向不同目标”的冲突。current 仍表示已经发布的路由配置，客户端可以缓存它。

随后按顺序执行四步。Freeze 把 A 从 SERVING 改为 FROZEN，并保留稳定映像。Install 将完整映像和收据保存到 B，B 才成为 epoch e 的服务者。Delete 确认 B 已有同迁移的持久安装收据后清理 A，但保留 epoch 与迁移身份。Publish 最后把 current 指向 B，并完成 next。

sequenceDiagram
  participant C as 控制器
  participant M as 配置文件
  participant A as 源组 A
  participant B as 目标组 B
  C->>M: 保存 next(s,e,A,B)
  C->>A: Freeze：保存固定映像并停读写
  A-->>C: 冻结映像
  Note over C: 退出点一
  C->>B: Install：保存 KV、dedup、收据
  B-->>C: 安装完成
  Note over C: 退出点二
  C->>A: Delete：核对目标收据再清理
  A-->>C: 墓碑保留
  Note over C: 退出点三
  C->>M: Publish current=B，完成 next
  Note over C: 退出点四

安装完成、目录发布尚未完成时，B 已经具有服务资格；current 暂时还指向冻结的 A。B 的授权来自已批准 next 与已经完成的冻结、安装转换，不能因为 current 未更新就推导 B 非法，也不能因为 current 仍指 A 就允许 A 重新服务。旧客户端访问 A 会收到拒绝，刷新路由或等待迁移推进。

这套顺序有一个简短的安全归纳。初始时只有 A 服务。Freeze 只会撤销权限，不增加服务者；Install 的正常前置条件要求 A 已冻结且 B 尚未服务，因此新增 B 后仍至多一个；Delete 不授予权限；Publish 只改变路由，不重新激活任何组。这个归纳依赖组状态转换正确串行化、冻结检查真实有效以及操作身份经过批准，不是对任意伪造管理消息的安全证明。

本模型在冻结后传输完整分片状态，服务暂停窗口会受到快照体积、可用带宽和安装工作量影响；这里没有测量这些时延。生产方案可以先预复制，再在最终冻结后补齐增量，但仍须保留一个明确切点，区分已经纳入目标状态的写与必须拒绝或转发的后续请求。Bigtable 2006 在 §6 描述了一项迁移优化：执行两次 minor compaction，在两次之间停止服务，以缩短停服阶段。这是历史实现，本文没有实现相应增量协议。Bigtable，§6

恢复不能依赖已经删除的源快照

控制器可能在参与方保存成功后退出。新进程不能根据旧进程是否收到返回值判断步骤有没有执行，也不能重新生成另一份迁移计划覆盖原 next。恢复需要先读取持久意图，再检查参与方已经留下的事实。

flowchart TD
  R[新控制器读取 current 与 next] --> N{是否仍有 next}
  N -->|无| F[无需继续迁移]
  N -->|有| T{目标是否有同迁移安装收据}
  T -->|无| S[冻结源或读取原冻结映像]
  S --> I[安装目标并保存收据]
  T -->|有| K[沿收据继续，不重新索取源数据]
  I --> D[删除源或确认已有删除墓碑]
  K --> D
  D --> P[发布 current 并完成 next]

最关键的窗口是 Delete 已完成但 Publish 未完成。此时源 KV 和冻结映像都可以已经清空，目标却已具备全部迁移状态。恢复若仍要求先从源获取快照，就会把已经完成的大半次迁移卡死。模型先检查目标安装收据，确认其身份后直接继续 Delete 的幂等确认与 Publish。

控制器文件只保存 current、next 和配置版本，没有额外的持久阶段进度日志。恢复进度来自各组状态与收据。这降低了“参与方完成、控制器进度落后”造成的歧义，但并没有消除对持久意图的要求。超时或进程退出也不能成为解冻源的理由：目标可能已完成安装并处理过新写。

本实验使用一个可信控制器串行执行，管理方法可以同步读取配置及源、目标文件。文件原子替换不提供多个控制器的比较交换语义。多个控制器竞争同一配置时，需要另外设计 CAS、身份约束和帮助完成同一迁移的规则；本文没有把单进程文件更新冒充这些并发保证。

相同安装重试不能抹掉新写

安装收据不仅记录迁移身份，还绑定第一次快照的摘要。相同身份、相同摘要的重试只返回原收据，不再次覆盖目标 KV。同一身份却换了一份快照应被拒绝；目标已进入更高 epoch 或迁出时，旧安装也不能重新激活它。

去重表同样属于分片状态。源执行请求 (client,seq) 后，必须保存完整请求与首次结果。迁移如果只复制 KV，没有复制这个记录，目标会把重试当作新请求。用 Put 同值测试容易掩盖错误；Add 更容易显露重复执行。

flowchart TD
  A[A 执行 client/1 Add5，保存结果5] --> L[逻辑回复丢弃]
  L --> F[冻结映像包含 KV 与 dedup]
  F --> I[B 安装映像及摘要收据]
  I --> W[另一个客户端 Put50]
  W --> R[重复相同 Install]
  R --> K[只确认原收据，当前值保持50]
  K --> Q[client/1 重试 Add5]
  Q --> D[匹配完整请求，返回缓存5]
  D --> V[当前值仍为50，不再次相加]

本地实测分别检查“返回原结果”和“当前状态不变”，不能用返回当前值 50 替代首次结果 5。同一 (client,seq) 改成 Add6 会得到 identity-conflict，而不是执行一个新操作。不同分片各自保存去重表，因此这里的身份范围是 (shard,client,seq)，没有跨分片共享一个最高序号而错误过滤另一个分片的请求。

模型没有实现去重记录回收；Python 整数采用任意精度，也不同于第 15 篇拒绝 int64 溢出的 API。迁移的职责是完整保留本模型已经声明的业务语义，不是在移动过程中悄悄改变错误处理或请求身份规则。

返回原组后仍要拒绝旧迁移

A→B 完成后再执行 B→A，不能因为“源和目标都是熟悉的组”就接受第一轮迟到的消息。旧 Delete 可能误删 A 已接收的新数据，旧 Install 可能覆盖新写，旧 Freeze 则可能无故让服务再次停止。

flowchart TD
  E1[epoch1：A 迁移到 B] --> E2[epoch2：B 迁回 A]
  E2 --> W[A 在 epoch2 写入81]
  O[迟到 epoch1 的 Freeze、Install、Delete] --> G[核对批准意图及完整迁移身份]
  G --> R[拒绝旧请求，组状态不变]
  W --> R
  R --> T[B 保留 epoch2 的删除墓碑]

正式实现删除业务数据时保留 epoch 和迁移身份；然而，本次旧 RPC 负例首先被全局 cfg.next 授权检查拒绝。因此实验没有独立证明“不查询配置、仅靠本地墓碑”的隔离能力。生产系统若希望管理消息可脱离配置服务完成校验，需要设计有效期、身份、收据或其他授权证据，不能直接引用本例的成功输出作为依据。

目标收据也必须在删除源之前检查。实验在源刚冻结、目标尚未安装时实际调用 Delete，确认它拒绝且两组文件内容不变。这项负例比单纯在正常时间线上观察“Install 恰好先执行”更直接地验证了实现的前置条件。

三组实验与真实进程退出边界

正式源码是 examples/distributed-systems/sharding24/check.py，仅用 Python 标准库。它启动当前解释器执行同一正式脚本的 controller 子模式，所有文件位于仓库 .build/sharding24。控制器、A、B 分别保存独立 JSON，每次转换只更新一个服务的文件，没有用一份全局事务同时撤销 A 并激活 B。

1
2
3
4
5
# 从 examples/distributed-systems 执行
mkdir -p .build/sharding24/tmp
export TMPDIR="$PWD/.build/sharding24/tmp"
export TMP="$TMPDIR" TEMP="$TMPDIR" PYTHONDONTWRITEBYTECODE=1
python3 -B sharding24/check.py

每个保存步骤使用同目录新文件、flush、文件 fsync、replace、目录 fsync。四个退出点都在保存完成后执行 os._exit(73)；父驱动等待进程退出，再启动新 PID，从原目录恢复。它是真实的受控进程退出与重启，不是 SIGKILL、机器断电或文件撕裂测试。文件持久转换抽象了组内已正确完成的状态机操作，不等于真实 Raft 共识。

2026-09-20 的本地执行以退出码 0 完成以下三组验收。

场景 实际检查 覆盖边界
四切点退出与恢复 freeze/install/delete/publish 后退出码73，新 PID 恢复；另一分片 t 继续写；最终 B 读取50、重试返回5 不证明机器掉电或多个控制器并发恢复
重复安装与迟到控制请求 新写后相同安装不覆盖；同身份不同摘要拒绝；迁回后旧 RPC 拒绝；无安装收据不能删除 旧 RPC 由全局授权先拒绝，不是墓碑单独隔离证明
跳过冻结的变异 B 实际保存 SERVING 时 A 仍 SERVING，独立观察器检出两个服务者 只检查指定有限调度，不穷举所有故障

观察器每次读取各组真实 phase，而不是根据目录 current 推算服务者。故意变异只跳过源冻结要求，使双服务状态实际落盘；协议没有先调用观察器阻止坏转换，再把“拒绝成功”伪装成发现反例。

实验中的 reply-dropped 是驱动丢弃一次业务逻辑返回，不是 TCP 丢包。Install 切点位于函数已经返回、后续控制步骤尚未执行的位置，也不是实际网络 ACK 丢失。它们足以验证持久状态下的重试处理，但不能据此报告网络恢复时延。完整历史线性化检查未在本篇实现，结论限于已观察到的权限不变量、状态保留和重复请求结果。

论断与原始资料核验；运行、审阅与验证记录；场景结果与逐步事件。

两个推演练习

练习一：目标已经完成安装并接受 Put50，控制器退出。新控制器发现 current 仍指源，于是先解冻源以恢复可用性，再考虑重做迁移。指出违反哪条不变量，并给出一条不需要新故障的反例。

目标已经 SERVING。源一旦解冻，也可接受业务，两个组立即同时具有服务资格。随后两个客户端分别向两组写入不同值，两边都可能成功。错误来自把路由 current 当作全部权限事实，并把控制器不确定性当成撤销目标授权的依据；正确恢复应检查批准 next 与目标收据，而不是自行回退源状态。

练习二：去重表已经随分片迁移，重复 Install 仍采用“每次用旧快照覆盖目标”的实现。为什么保存去重表还不够？给出一个能明确暴露问题的测试。

先安装包含 x=5 的快照，再让目标对另一个请求成功执行 Put50，随后重复安装同一快照。无条件覆盖会把已确认的 50 回退为 5，还可能删除快照之后新增的去重记录。再次重试这些请求又可能产生重复效果。测试必须在两次安装之间实际执行新写，再验证 KV 和新请求记录都未回退；只把相同安装连续调用两遍看不出这个问题。

单分片的归属互斥仍不提供跨分片订单与库存的原子提交。两个分片分别只由一个组服务，也可能一个操作成功、另一个失败；这类跨分片事务问题留给第 25 篇。

参考资料

  • MIT 6.5840，Spring 2026，Lab 5：分片归属与 Raft 成员变化的区别、迁移顺序、current/next 恢复和并发控制器问题。公开任务说明
  • Chang 等，Bigtable: A Distributed Storage System for Structured Data，OSDI 2006：§2 范围分片，§5.2 tablet 分配与撤权。这是历史论文系统，不是当前云产品版本保证。原论文
  • Karger 等，Consistent Hashing and Random Trees，STOC 1997：§4 的映射、均衡与重映射性质。数据放置性质不等于业务请求负载均衡，也不提供迁移授权。作者 PDF
  • MIT 2026 课程安排提供从复制 KV 到分片 KV 的主线；Stanford CS244B Spring 2024提供 Dynamo、Spanner 等存储论文的横向背景，不声称有完全相同的迁移实验。