# 23：Dynamo 风格无主复制研究

研究日期：2026-09-20。范围依据蓝图23：quorum、Gossip、反熵、冲突版本；验收为构造 `R+W>N` 仍不足以自动线性一致的反例，以及合并分区两侧写入。本文件是研究与实验设计，不是已完成文章或运行报告。未下载、编译、运行实验或生成临时程序；保留其他系列并发修改。22验收提交为 `78ec61d552ba80593400f09da1aeff587ebecdcb`，本轮检查HEAD已因并发工作推进至 `b3585611`。

## 来源、版本与核验状态

| 标题、日期、URL | 实际定位与支持论断 | 核验状态与边界 |
|---|---|---|
| DeCandia等，*Dynamo: Amazon’s Highly Available Key-value Store*，SOSP 2007-10-14–17，[作者站PDF](https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf) | §2.1–2.3：单键接口、可信环境、可用性目标及应用合并；§4.3–4.8：物理节点preference list、向量版本、R/W、sloppy quorum、hint、Merkle、membership；§5：read repair时序 | 本轮实际读PDF正文；页码采用PDF第6–10页，对应主要机制。是2007内部Dynamo，不是现今DynamoDB实现规范。父独立重读§4.4–4.8，与下文核心边界一致 |
| Attiya、Bar-Noy、Dolev，*Sharing Memory Robustly in Message-Passing Systems*，JACM42(1),124–142，1995-01，[MIT托管原文](https://groups.csail.mit.edu/tds/papers/Attiya/JACM95.pdf) | §4，PDF第8–10页；Figure2、Lemma4.4–4.6：单写多读原子寄存器，读选最大label并在返回前向多数传播，跨完成操作label不倒退 | 父本轮独立实际读原文；本代理搜索确认原文入口，直接读取批次上游500，不冒称已读全文。原论文SWMR不直接等同多写者Dynamo；这里只取同步读回写的充分条件对照 |
| [MIT6.5840 Spring2026日程](https://pdos.csail.mit.edu/6.824/schedule.html) | 本系列前文已核课程结构：KV/Raft/存储与事务 | 本轮访问批次上游500，未新增确证讲次；不能称Dynamo为MIT2026指定论文。尝试旧`notes/l-dynamo.txt`也未成功读取 |
| [StanfordCS244B Spring2024日程](https://www.scs.stanford.edu/24sp-cs244b/sched/) | May20–24周明确列Dynamo与Spanner | 本轮实际读日程43–44行，支撑23→26存储论文结构，不复制课程问题答案 |
| AWS，[DynamoDB read consistency](https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/HowItWorks.ReadConsistency.html)，滚动文档 | 仅列产品区分的候选入口，不用作具体保证证据 | 本轮读取批次上游500；正文不据此新增DynamoDB具体API承诺。本篇不需要部署DynamoDB |

访问障碍记录：Cornell候选ABD路径、Hebrew University候选路径不可访问；不以猜测URL的失败判断论文不存在。公开搜索 `Dynamo 2007 paper errata quorum`、`Dynamo errata` 未发现可核作者勘误页，但搜索不完备，不能宣称没有勘误。直接反查原文已发现多处足以约束常见泛化的文字：§4.4明确删除可能复活、向量时钟截断丢失准确祖先信息；§5明确read repair在响应后；§4.6明确选择的是可达节点而非固定N个副本。

## 论断—证据—核验矩阵

| 论断 | 证据和独立推导 | 状态 |
|---|---|---|
| 无主不等于没有请求协调者 | Dynamo§4.5任何适当节点可协调某次get/put；没有所有写共同服从的固定leader | 原文已核；不要写成无协调或无顺序 |
| `R+W>N`只推出同一固定N节点全集内读集合与已获W确认的写集合相交 | 集合论：若不交，大小之和至多N。它不说明交点保存哪个版本、不处理未完成写，也不证明后读不能倒退 | 独立数学推导；与ABD读回写机制交叉核对 |
| 固定quorum加“选最高版本”仍可能发生new-old inversion | 下方完整三操作轨迹；首次读看见尚未获W确认的版本并立即返回，修复尚未完成 | 独立构造；Dynamo§5响应后修复支持此延迟条件。不是声称复现了2007私有实现 |
| 同步读回写可阻断该轨迹 | ABD§4读返回前将最大label传播至多数；后续读多数必相交且节点不能降低label | 父独立原文核验及集合推导。有限对照通过也不是完整ABD实现证明 |
| sloppy quorum不再拥有固定N全集交集推导 | Dynamo§4.6从preference list选前N个健康节点；两个请求实际候选集合可以不同 | 原文已核；必须记录可达性与实际响应节点，不能只画两个任意集合 |
| 向量时钟的偏序与业务合并是不同职责 | Dynamo§4.4：context、并发分支、应用合并；逐分量比较只能识别祖先/并发，不能决定删除与增加谁赢 | 已核；缺失分量视0。相等版本去重；严格支配要求至少一项严格大于，不能把相等当并发 |
| 删除复活不是向量时钟计算错误 | §4.4购物车合并明确承认；集合union保留add却不能普遍保留remove意图 | 已核；实验须包含这一反例，不把union称通用无损合并 |
| hints、反熵、Gossip不能互相替代 | §4.6–4.8分别对应暂存转交、副本差异修复、membership历史传播 | 已核；父独立同结论。Merkle定位差异不自动决定正确值；Gossip不是共识 |
| 最终收敛有前提 | 停止新增写、相关持久副本仍存活、通信恢复且修复持续得到调度，合并策略确定且可重复 | 模型假设，不把2007“always writeable”修辞扩成任意故障保证；写成功至少要W个可达可写存储 |

## 最小实验：三个确定性场景

使用Python标准库，在正式路径`examples/distributed-systems/dynamo23/check.py`实现原创有限事件模型；运行输出仅`.build/dynamo23/`。此处仅设计，未创建或运行代码。模型不使用真实Amazon服务、不模拟性能，也不声称原产品端到端验证。

### A：固定quorum、完整历史与读回写对照

固定副本A/B/C，N=3，R=W=2，初始`(tag=0,value=0)`。只有一个写者，服务端持久模型保存最大tag；请求发往全体，但调度器可延迟具体投递/响应。事件如下：

1. 调用Put(1)，仅向A交付`(1,1)`并确认，B/C投递延迟；Put尚未返回。
2. 调用Read1；选A/B回复，最高tag为1，返回1。异步read repair已排队但暂不交付。
3. Read1返回之后才调用Read2；选B/C回复，返回0。
4. 最后向B交付Put并收到第2个确认，Put成功返回；再允许后台修复。

三操作都是完整操作：Put区间横跨两个读，不需要引入pending补全算法。单寄存器顺序见证必须把Put放在Read1前才能解释Read1=1，而实时顺序要求Read1在Read2前；这时Read2不可能返回0。独立小型检查器枚举三个操作的所有排列、过滤`response(a)<invocation(b)`约束，再按寄存器规格回放；预期无见证。不能用“观察到1后观察到0”硬编码替代独立历史检查。

对照只改变读返回屏障：Read1查到tag1后，向多数A/B回写并获确认才返回；此时Read2仍取B/C，必须返回1。节点处理迟到tag0不能覆盖tag1。检查器预期找到合法序列；断言具体回写ACK确实在Read1响应之前。它解释ABD式传播机制，不实现完整ABD网络、崩溃恢复、多写扩展或证明所有调度。

可加一个无代码规模增长的择值边界：即使某完成写覆盖A/B，后读B/C也不能随意返回C旧值；quorum交点存在与读选值正确是两条不同条件。仅作推导题，不强制增加第四实验。

### B：sloppy的实际可达集合与hinted handoff

固定preference list `[A,B,C,D,E,F]`，home replicas为A/B/C，N=3，R=W=2。网络分为`{A,D,E}`与`{B,C,F}`，每侧协调者只能访问所在分区。

写协调者A按同一偏好序选择可达前三个A/D/E，记录D代管B、E代管C；把新值交A/D并获两确认后写成功，E投递可稍后。另侧读协调者B按可达性选择B/C/F，先取B/C两响应返回旧值。必须断言实际写确认集合`{A,D}`与实际读响应集合`{B,C}`不交，并打印每次过滤前列表、可达集合、候选集合、已投递集合与ACK集合。`2+2>3`仍真，但两集合并不同时受同一三个home节点全集约束。

写成功后才调用读，故二操作顺序规格已有反例；独立历史检查器复用A。为避免把B的协调资格误解成ring首节点唯一资格，模型明确任何home节点可协调，符合原论文§5的负载策略。

恢复通信后D向B交付hint、收到保存确认后删除本地hint；E对应C若尚未获得副本不得假装存在hint。对未达C的新版本安排显式后台复制/反熵事件。断言hint没有在目标ACK前删除、修复后所有home副本收敛。不得把这条有限成功调度称成任意临时故障必然恢复。

### C：分区并发、向量时钟与业务合并

此场景独立选择W=1，在左右两侧从共同版本context写购物车；不沿用B的W=2数字冒称两侧都拿到固定home多数。左右协调者各递增自己的向量分量，各自本地保存并确认；必须记录该场景的N/R/W及实际确认节点。也可复用B的sloppy两分区以W=2演示，但不是当前最低实现要求。

两侧分别增加不同商品，恢复通信后合并版本集：只移除被另一向量严格支配的版本，相同向量/负载去重，不可比较的两个版本均保留。先断言两个兄弟版本都可被读取；应用union后以两者逐分量最大context生成一次新版本，再递增合并协调者分量；断言新时钟严格支配两分支，传播后各home只剩一个版本，且包含两侧新增商品。

追加同一合并函数的反例：初始购物车含tea；左侧删除tea，右侧从旧context增加coffee且仍含tea，union得到tea+coffee。断言tea复活，解释这是业务策略代价；不能改期望绕过。若要避免复活，需要额外操作身份/tombstone/明确并发删除语义，本篇点出而不扩成CRDT完整实现。

模型保持完整向量，不实现论文阈值截断；论文承认截断会损失准确祖先关系，不能用本模型的精确偏序去证明截断版本。节点ID稳定且计数不重用；Gossip/Merkle只在正文机制说明，不伪称代码已实现。若演示Merkle，必须另有规范序列化与哈希碰撞假设，当前最低验收不需要增加模块。

## 写作与图示建议

建议六图：固定N集合交叉；Put跨两个读的时间线；异步repair与同步write-back对照；sloppy两分区及hint目的节点；向量分支/合并DAG；Gossip、hint、read repair、Merkle各自输入输出路径。每图标出已确认/未确认、消息延迟、时间方向，避免把逻辑时钟画成物理时间。

正文按“前篇多数停写的取舍→固定quorum能证明什么→sloppy改变集合→版本偏序与业务冲突→三种修复路径→实验与边界→下一篇分片迁移”组织。两题可分别推导去掉read-back后的线性化矛盾、解释union为何无法同时实现任意增加和删除的直觉。不复用课程作业实现。

交付状态：研究已具备实现条件；所有实验结果仍为预期，未运行。ABD关键页由父实际核验；本代理直接读取ABD、作者2010回顾及AWS页面的批次最终上游500，没有将其记为已读。父也独立读Dynamo§5 PDF lines1002–1009，确认响应后修复。不要等待更多相关论文才能启动该有限实验，也不要把历史Dynamo能力直接冠给DynamoDB。

## 实现后的核验（2026-09-20）

以上“未实现/未运行”为研究阶段记录。正式源码`dynamo23/check.py`现已完成作者及父独立运行，SHA256 `f56641ca5a1e06bd9a0f339f4c2f744b267851feac42a7de90a50c636b40c8a2`。两次完整JSON一致：固定异步读修复历史无见证，同步回写历史有唯一见证，sloppy的AD/BC不交且hint在ACK后删除，向量siblings保留与union删除复活均通过。父CLI帮助/非法参数为0/2。独立只读审阅确认历史检查不使用协议状态；向量场景的本地写与ACK为直接内存抽象，不经消息队列。证据为有限模型本地验证，不是产品运行或一般性正确性证明；文章站点验收记录另见STATUS/素材verification.txt。


实施映射（2026-09-20）
正式check.py仅Python标准库有限模型；固定quorum反例与同步读回写对照用独立完整历史排列检查器；sloppy实际过滤ADE/BCF且AD写ACK、BC读回复；向量场景为直接内存版本集合交换。八图分别解释协调者、固定交集、new-old轨迹、同步读回写、sloppy分区、向量分支、删除复活、修复职责；依据本文已核原论文与模型，不新增产品观察。
独立父级全文源码/正文审阅通过。向量update不是任意旧context的完整持久版本分配器；反熵仅显式交换，未实现Merkle或Gossip。