复制到多个节点并等待若干确认，可以提高故障期间成功处理请求的机会，却不能仅凭 R + W > N 推出线性一致性。参与确认的是哪些节点、读是否传播读到的版本、并发写如何比较、故障恢复后如何处理分歧，都属于协议本身。

前篇的 etcd 实验在失去多数派后无法完成默认读写。Dynamo 风格系统采用另一种取舍：允许部分故障期间的写入，在副本之间保留可能冲突的版本，把一部分协调工作推迟到读取、修复或业务合并时。这里的 Dynamo 指 Amazon 2007 年论文描述的内部系统；不能把论文机制直接当作今天 Amazon DynamoDB 的 API 保证。

请求协调者与全局主节点不同

Dynamo 论文讨论的是按键访问的高可用存储。系统需要在节点故障、通信延迟和临时不可达时继续处理相当一部分请求，并接受副本暂时不同。论文没有依赖一个全局领导者，为所有键的写入生成统一日志顺序；不过每次请求仍可由一个协调者收集副本响应。无主复制不等于没有请求协调者。

一致性哈希把键映射到环上的位置，preference list 决定优先存储该键的物理节点。虚拟节点用于划分负载和分配范围；多个虚拟位置不能被误算为多个独立物理故障域。复制因子 N 表示期望的副本数量，W 是写返回所需响应数，R 是读返回所需响应数。这些数量必须与具体节点集合、故障假设和版本规则一起解释。Dynamo，2007，§4.1–4.3、§4.5

flowchart TD
  K[键 k] --> H[哈希位置与 preference list]
  H --> P[期望副本 A B C]
  Q[一次请求的协调者] --> P
  P --> W[写：收集 W 个响应]
  P --> R[读：收集 R 个响应与版本]
  R --> V[比较版本或返回 siblings]

图中的协调者只负责这次访问。将它替换为另一个节点，并不会自动产生类似 Raft 任期、领导权确认和已提交前缀的证明。反过来，高可用也不表示任何分区都能完成任意操作：一个分区是否有足够可达节点，仍受 N、R、W 和副本放置约束。

集合交叉能证明什么

先固定三个副本 A、B、C，令 N=3、R=W=2。任意两个大小为 2 的集合必有交集。若某次写已在写集合中保存版本 v，之后的读集合就至少包含一个保存过 v 的节点。这个集合结论本身没有规定读端如何识别 v，也没有规定该节点重启后是否还保存 v。

flowchart TD
  U[固定副本全集 A B C] --> W[写集合 A B]
  U --> R[读集合 B C]
  W --> X[交点 B]
  R --> X
  X --> C[仍需：版本可比较、状态不丢失、读规则正确]
  C --> G[才能继续推导读的保证]

即使模型已经满足单写者、标签单调、节点不丢数据，仍有一个容易遗漏的情况：一个尚未完成的写只到达少数节点，第一次读读到新值，第二次读又读到旧值。两次读各自与最终的写 quorum 相交，并不能防止这种返回倒退。

设初值为 0。写操作 Put(1) 已调用，但只到达 A；A 保存标签 1、值 1，B、C 仍保存标签 0、值 0。读 G1 查询 A、B，取最高标签，返回 1。随后 G2 查询 B、C，返回 0。最后原写到达 B，收齐 A、B 的确认才返回成功。

sequenceDiagram
  participant W as 写操作 Put1
  participant A as A
  participant B as B
  participant C as C
  participant R as 读操作
  W->>A: 保存 tag1,value1
  A-->>W: ACK，写仍未完成
  R->>A: G1 读取
  A-->>R: 1
  R->>B: G1 读取
  B-->>R: 0
  Note over R: G1 返回1后才调用G2
  R->>B: G2 读取
  B-->>R: 0
  R->>C: G2 读取
  C-->>R: 0，G2返回0
  W->>B: 原写延迟到达
  B-->>W: ACK，Put1完成

这是完整的三个操作历史，不能简单把未完成的写删除，因为它最终完成了。线性化允许把与读取重叠的 Put 放在多个候选位置，但 G1 返回 1 要求 Put 排在 G1 之前；G1 已完成后才调用 G2，要求 G1 排在 G2 之前。于是 Put 必须在 G2 之前，G2 却返回初值 0，矛盾。

本篇的独立检查器枚举所有操作排列，只使用调用与返回时刻、初始值和寄存器顺序规范。它不读取 A、B、C 的内部状态，也不读取版本标签。这可以防止协议模拟器按自己的内部解释直接宣布历史正确。

读回写为何必须位于返回之前

一种修正是：读取得最高标签后，先把这个标签和值传播到多数副本，获得确认后才返回。上述 G1 若把版本 1 保存到 A、B，再向调用方返回，后续任意两副本读都与这个保存集合相交，至少能发现版本 1。节点保留最大标签，迟到的低标签消息也不能把它覆盖回 0。

flowchart TD
  Q[查询多数副本，选最高标签] --> M{返回前是否同步回写}
  M -->|否| E[立即返回新值]
  E --> D[修复消息延迟]
  D --> O[后读仍可只见旧值]
  M -->|是| S[将所选版本写回多数]
  S --> A[收到多数确认]
  A --> F[读返回]
  F --> N[后读与保存集合相交]

这个论证来自 ABD 单写者原子寄存器的核心读协议：读不仅查询，还在完成前执行传播阶段。它不是“读到最大时间戳”一个条件就能替代的。原论文 Figure 2 的范围是单写者、多读者；这里的实验只复现对应的有限执行，没有实现完整多写者协议，也没有把寄存器等同于任意状态机共识。Attiya、Bar-Noy、Dolev，1995，§4、Figure 2

Dynamo 的 read repair 与这个同步读阶段不能混用。论文 §5 描述的读修复可以在响应发出之后推动副本更新。它有助于传播状态，却不能撤销已经返回的历史。实验故意让异步修复消息排队，等两次读取返回后才交付；副本最终相同，先前历史仍无法线性化。

Sloppy quorum 改变了交集的全集

固定集合的反例还没有使用 sloppy quorum。后者放宽的是副本位置：故障期间可以在 preference list 上选择最先可达的 N 个节点，让临时副本代管写入。此时两次请求的实际节点集合可能不同，R + W > N 中的 N 就不能直接被当作所有确认节点共同所在的全集。

令一个键的期望副本为 A、B、C，后续候选为 D、E、F。网络分为 {A,D,E} 与 {B,C,F}。A 协调写时选择 A、D、E，收到 A、D 两个确认即返回；之后 B 协调读时选择 B、C、F，从 B、C 收到两个旧值。N、R、W 仍是 3、2、2，写确认集合 AD 与读响应集合 BC 却不相交。

flowchart TD
  H[期望副本 A B C；候选次序 A B C D E F] --> P1
  H --> P2
  subgraph P1[分区一]
    A[A 保存新值并确认] --> D[D 保存新值及 hint 指向 B]
    A -.-> E[E 的写消息未交付]
  end
  subgraph P2[分区二]
    B[B 返回旧值] --- C[C 返回旧值]
    B -.-> F[F 是第三候选，回复未收齐]
  end
  P1 --> W[写 ACK 集合 A D]
  P2 --> R[读响应集合 B C]
  W --> X[两个集合没有交点]
  R --> X

这个模型保留了具体发送、投递、保存和确认步骤。D 只有处理到更新后才产生指向 B 的 hint；E 的消息仍在队列中，因此不能声称 E 已经代管 C。候选名单、已发送请求、实际存储和调用完成是不同事实。Dynamo，§4.6

通信恢复后，D 把代管版本发给 B，收到 B 的确认后才删除 hint。若发送后立刻删除，而传输失败或目标未保存，代管信息就可能丢失。实验在 B 已处理更新、ACK 尚未投递时检查 D 仍保留 hint，随后投递 ACK，再检查删除。C 则通过另一条明确的副本修复消息更新，没有把从未发生的 E 写入补成事实。

这说明 hinted handoff 是临时副本向原目标转交数据的机制，不是让两个分区此前的读写获得同一个顺序。修复后的 A、B、C 可以全为 1，先前已成功 Put 后返回 0 的 Get 仍然违反单寄存器的线性一致性规范。

向量时钟保存并发关系，不决定业务胜者

前两个场景为清楚讨论读写历史，只使用单写者递增标签。Dynamo 的多版本问题还需要处理不同协调者并发写入。若强行按一个标量时间排序并只保留最大者，系统可能丢掉没有因果先后关系的业务更新。

向量时钟为不同节点保存计数。对两个向量 u、v，若每个分量都有 u[i] ≤ v[i]，且至少一个严格小于，则 u 在这个表示中先于 v。两边各有一个更大的分量时，它们不可比较，应保留为 siblings。缺省分量视为 0。

初始购物车版本是 {A:1}。分区期间 A 在这个上下文上加入 apple，产生 {A:2}；B 在相同上下文上加入 pear，产生 {A:1,B:1}。第二个向量的 B 分量较大，第一个的 A 分量较大，任何一个都不能被当作另一个的后继而删除。

flowchart TD
  V[共同上下文 A1：空购物车] --> L[A2：apple]
  V --> R[A1 B1：pear]
  L --> S[副本交换后保留两个 siblings]
  R --> S
  S --> U[应用显式合并为 apple 与 pear]
  U --> C[合并上下文并更新 C 分量]
  C --> N[A2 B1 C1：同时支配两个旧版本]

读取可以把值和上下文一起返回。应用提交合并结果时携带相关上下文，新版本才有依据同时取代两个 siblings。只取其中一个上下文再写回，不能凭最终值“看起来正确”就证明已经覆盖另一个并发分支。Dynamo，§4.4

本篇第三个实验使用独立的 R=1、W=1 场景。它直接更新内存中的本地版本集合，再按明确顺序交换版本；分区和本地 ACK 是模型记录，不经过前两个场景的消息队列，更不是真实网络故障注入。完整向量、稳定节点身份和不重用计数也都是这里的边界。update 只对当前场景合并 context 后递增分量，没有实现面对任意陈旧 context 的完整持久版本分配器。

论文为控制元数据增长，还讨论了按阈值截断向量条目。截断会牺牲因果信息的精度，不能把这个工程优化当作完整向量比较的等价变换。有限实验没有实现截断，也不以少量节点的结果推断长期运行时版本数量的上界。

删除为什么会在合并后重新出现

向量时钟能说明两个更新并发，但“两个购物车取并集”是应用策略，不是时钟协议。假设共同版本包含 tea：A 删除 tea，B 在尚未看到删除时加入 coffee，B 的值仍包含 tea。两个分支不可比较，随后取并集得到 {tea, coffee}，tea 重新出现。

flowchart TD
  B[共同版本：tea] --> D[A 分支：删除 tea，值为空]
  B --> W[B 分支：加入 coffee，仍有 tea]
  D --> S[并发 siblings 均保留]
  W --> S
  S --> U[应用采用集合并集]
  U --> R[结果 tea 与 coffee：删除被抵消]

这不是向量比较漏掉了一条先后边，而是这两次修改本来就没有因果先后。若业务要求删除优先、添加优先或按具体添加实例删除，就必须把这些语义编码进数据结构、操作或删除标记中。只有当前值的集合并集不足以表达所有删除意图。Dynamo 论文 §4.4 用购物车说明了这类协调代价；本例不把简化的 union 实现称作支持任意删除的通用 CRDT。

版本集合交换遵循三个不变量。首先，只保留未被其他版本因果支配的元素。相同版本重复交换不增加结果；交换次序也不改变最终版本集合。实验对有限样本检查幂等、交换和结合性质，又在完整上下文合并后检查所有节点只剩一个支配两个旧分支的新版本。这些断言验证所列样本，不能替代全部状态空间的证明。

发现故障、定位差异与解决冲突各有职责

Dynamo 的后台机制处理不同问题。Gossip 传播成员及相关状态，帮助节点逐渐获得拓扑信息；故障检测给出当前是否可达的判断，但怀疑失效不等于节点永久损坏。Hinted handoff 处理临时替代存储。Read repair 利用读请求暴露的差异推动修复。Merkle 树则通过范围哈希定位副本之间的数据差异，减少无差异范围的传输。Dynamo，§4.6–4.8

flowchart TD
  G[Gossip：传播成员信息] --> P[决定向哪些节点尝试请求]
  H[Hinted handoff：已知代管目标] --> T[把临时副本交回目标]
  R[Read repair：访问发现差异] --> X[交换缺失版本]
  M[Merkle：比较范围哈希] --> L[下钻到不同的叶范围]
  L --> X
  T --> V[版本比较与 siblings 保留]
  X --> V
  V --> A[应用规则决定并发内容如何合并]

Merkle 根不同只表明范围内容不同，不说明哪个值较新，也不决定删除是否应优先。根相同的判断还依赖一致的数据编码、覆盖范围和哈希假设。成员变更或键范围迁移会影响比较范围，不能把静态两副本的树直接当作整个集群重配置协议。

最终收敛需要明确条件：新更新停止，至少有可用副本保留相关版本，通信恢复，修复持续得到执行，合并规则确定。一个有限程序把消息全部交付后观察到相同状态，只证明这条轨迹收敛；它没有证明调度公平、永久故障下的数据存活，也没有给出所有故障的恢复时间上界。

运行有限模型并检查历史

正式实验位于 examples/distributed-systems/dynamo23/check.py，仅使用 Python 标准库，不下载产品、不启动服务、不创建编译产物。运行资料写到仓库内唯一目录，保留旧结果。

# 在 examples/distributed-systems 目录执行
mkdir -p .build/dynamo23/tmp
export TMPDIR="$PWD/.build/dynamo23/tmp"
export TMP="$TMPDIR" TEMP="$TMPDIR" PYTHONDONTWRITEBYTECODE=1
python3 -B dynamo23/check.py

2026-09-20 的本地运行及独立复跑均完成三组断言，两份原始 JSON 内容逐值一致。观察结果如下。

场景	实际检查结果	不能由此推出的结论
固定 quorum，异步读修复	完整三操作历史没有合法排列	所有固定 quorum 协议都不可能线性一致
返回前同步多数读回写	唯一见证为 write、read1、read2	已实现完整 ABD 或任意多写者协议
Sloppy quorum	AD 与 BC 不相交；handoff 等 ACK；home 最终一致	修复能使过去返回的旧读变正确
向量版本与应用 union	siblings 保留；完整上下文合并收敛；tea 复活	任意业务的冲突都能用集合并集解决

检查器只接收至多 8 个完整的单寄存器操作，初值为 0；不处理 pending 补全、跨键事务和真实服务超时。消息模型保留未交付队列，旧标签更新只得到“消息已处理”的 ACK，本地标签不降低。它没有磁盘持久化、进程重启或真实网络语义。

论断、来源与核验记录；运行、独立审阅与验证边界；原始模型轨迹与完整历史。

两个推演练习

练习一：固定 A、B、C 的反例中，把第一次读的回写改为“已发送给 A、B，但不等待确认”，能否保证后读不倒退？请同时给出满足这个规则的坏调度和独立寄存器规范中的矛盾。

只要给 B 的回写尚未交付，A=1、B=C=0 的状态就仍存在。G1 可以返回 1，G2 随后从 B、C 返回 0，原写最后完成。发送动作没有建立多数副本已保存版本的事实。线性化矛盾仍是 Put 必须先于 G1，而 G1 必须先于 G2，G2 因此不能返回 0。

练习二：D 把 hint 对应的新值发送给 B 后立即删除 hint；与此同时，应用把并发购物车直接取并集。分别指出这两个选择可能丢失什么信息，并说明为什么 Merkle 比较不能单独修正它们。

前者在 B 尚未确认保存时丢掉代管责任，传输失败后可能失去恢复所需的线索乃至仅存副本；后者丢掉“某次删除针对哪些添加”的业务语义，并集可重新带入被删除元素。Merkle 可以定位仍然存在于不同副本的差异，不能凭哈希重建所有副本都丢失的数据，也不能从两个当前值推断未编码的删除意图。

第 24 篇转向分片与迁移：当一个键的负责节点集合需要变化时，如何表达所有权、转移状态，并处理迁移期间的请求。Dynamo 的副本选择与修复提供了背景，但静态 quorum 交集不能直接代替迁移协议的正确性条件。

参考资料

DeCandia 等，Dynamo: Amazon’s Highly Available Key-value Store，SOSP 2007：§4.1–4.3 副本与协调者，§4.4 版本与购物车合并，§4.6–4.8 handoff、反熵和成员信息，§5 读修复。原论文
Attiya、Bar-Noy、Dolev，Sharing Memory Robustly in Message-Passing Systems，JACM 1995：§4、Figure 2，单写者原子寄存器及读完成前传播。作者托管论文
Stanford CS244B，Spring 2024：5 月课程安排中的 Dynamo 与 Spanner 单元，作为从复制协议扩展到存储设计的课程依据。课程表
MIT 6.5840，2026：承接本系列复制、故障与一致性主线；本篇 Dynamo 内容为结合原论文的扩展，不声称是该年指定课程单元。课程安排