客户端发出 Put(x, 1)，等待超时。服务端究竟有没有修改 x？只凭这条错误，无法判定。请求可能没到，也可能已经执行，只是回复没有回来。工程上需要重试、查询或人工核对，理论上需要先写清楚：哪些事件发生了，谁能观察到这些事件，协议允许哪些执行。

分布式系统的学习从这个区别开始。运行在不同进程里的代码通过消息合作，每个进程只掌握局部状态；一项业务动作可以跨越多个故障边界。正确性不能只根据正常路径上的最终输出判断。

这是系列的入口篇。验收目标是根据三个节点和客户端的时间线，区分确定发生、仍有可能和无法判定的结果；配套 Go 程序重放有限故障组合，不实现共识协议。

从课程结构到实验路径

MIT 6.5840 Spring 2026把 RPC、存储和复制实验逐步连起来；Stanford CS244B Spring 2024更突出原论文讨论与研究。两份课表覆盖事务、分布式计算和信任模型，学习范围远大于 Paxos、Raft、ZooKeeper 与 etcd。

系列按先修关系重新排列：先获得分析请求、状态和故障的语言，再实现任务调度、KV、复制与分片，随后讨论协调服务、事务、缓存、计算系统和拜占庭故障。00–07 的系统编程桥接是本系列自行设计的，不代表两校官方本科课程。代码使用 Go 标准库，题目独立设计，不复刻课程作业解答。

已有的 《AWS 的分布式系统相关挑战》 讨论请求与回复之间的不确定性；《数据密集型应用系统设计》读书笔记 提供更广的存储背景。本系列增加模型、推导和实验验收；旧文不作为未经复核的协议定义。

主线与选修的阅读入口

下图表示本系列的推荐阅读顺序。箭头连接学习阶段，不表示后一阶段的每篇文章都依赖前一阶段的每个协议。

flowchart TD
  A["00–07：请求、存储与故障模型"] --> B["08–16：复制、共识与容错 KV"]
  B --> C["17–22：ZooKeeper、ZAB 与 etcd"]
  C --> D["23–29：版本、迁移、事务与日志"]
  D --> E["30–32：分布式计算与状态恢复"]
  E --> F["33：拜占庭故障与认证"]
  F --> G["34：综合系统故障恢复"]
  G --> H["35：提出假设并复现实验"]
  B -.补充协议假设与证明.-> X["E05–E06"]
  D -.补充多写者与存储.-> Y["E01–E02"]
  F -.补充开放网络信任.-> Z["E03"]
  E -.补充调度与工程.-> W["E04、E07–E08"]
阅读阶段 文章入口 本阶段需要回答的问题
请求、存储与故障模型 00 · 01 · 02 · 03 · 04 · 05 · 06 · 07 区分超时、持久性、因果关系和一致性
复制与共识 08 · 09 · 10 · 11 · 12 · 13 · 14 · 15 · 16 从协议不变量进入可恢复 KV 和有限状态搜索
协调服务 17 · 18 · 19 · 20 · 21 · 22 区分协议、会话、客户端 API 和多数派故障
存储与事务 23 · 24 · 25 · 26 · 27 · 28 · 29 分析并发版本、归属迁移、提交、时间与可见边界
计算与信任 30 · 31 · 32 · 33 追踪重算、状态恢复、外部副作用及恶意行为
综合与研究 34 · 35 组合既有机制，设计可检验的研究问题
选修：多写者与系统架构 E01 · E02 · E03 · E04 补充收敛、存储、开放身份及云调度
选修：协议与工程 E05 · E06 · E07 · E08 比较协议假设、形式化验证、控制面和尾延迟

课程目录用于安排问题，协议论文用于解释模型，官方文档用于界定 API。练习与累计代码是独立设计的教学材料；某个模型通过检查，不会自动为同名产品提供保证。

沿着业务承诺选择证据

一次写入的确认、排序、跨分片决定和故障重算解决不同问题。分析服务时，需要先写出承诺，再确定哪个状态转换能支撑它。

flowchart TD
  A["客户端收到成功"] --> Q["成功承诺覆盖什么故障？"]
  Q --> D["同一存储上的进程恢复：检查持久化与恢复边界"]
  Q --> R["副本切换：检查复制、选举及已确认前缀"]
  Q --> T["多个参与者共同提交：检查决定记录与恢复规则"]
  Q --> S["任务重试：检查输入、血缘及结果发布"]
  R --> I["读 API：另查线性化与陈旧读取"]
  T --> O["外部副作用：另查幂等与补偿"]
  S --> O

共识确定被选定的值或日志顺序；线性一致接口还需要正确的应用顺序与读路径。原子提交处理多个参与者的共同决定；共识组复制决定记录可以改善恢复，但仍须说明参与者的准备状态。任务重算恢复数据，外部副作用则需要自己的提交或去重机制。这些区别会在第 06、15、25、30、34 篇分别展开。

系列状态记录区分论文模型、实现源码、接口声明和实际运行。有限枚举只能覆盖所声明的状态空间；进程退出后恢复也不能充当断电测试。每篇随文证据用于定位资料与观察边界，累计验证状态见仓库的 writing-plans/distributed-systems/STATUS.md。

一个请求经过哪些状态

设客户端为 K，三个服务节点为 A、B、C，每个节点最初都有 x=0。K 向 A 发送唯一的一次 Put(x,1)。这里 A 只是指定的接收者，没有经过领导者选举；B、C 在观察期间收不到复制消息，仍可回答自己的本地读。

节点状态用两个变量表示：memory 是当前进程能读取的值，stable 是模型规定能跨重启保存的值。初始时两者均为 0。处理写请求只把 memory 改成 1；执行同步动作才把它复制到 stable。重启动作销毁易失状态，并从 stable 恢复 memory。

这是一个刻意简化的存储模型。没有写入撕裂、文件名、目录项、缓存层和设备损坏，也没有把某个真实系统调用认定为永远可靠。stable=1 是模型中的前提，稍后的实验只检验建立在这个前提上的程序行为。

1
2
3
4
5
6
7
K                 A                    B             C
Put(x,1) --------> 接收请求             x=0           x=0
                  memory=1             无复制消息    无复制消息
                  stable=1（可选）
        <-------- OK（可能丢失）
截止期限到达      重启（可选）
                  memory=stable

图中从上到下表示这次构造执行的顺序，不能把不同机器日志上的墙上时钟直接当成这样的全局顺序。节点内部的动作先后、消息发送先于接收，能提供因果约束；没有消息关联的两个事件未必可比较。第 05 篇会用偏序和逻辑时钟精确表示这种关系。

这里至少有四个不同事实：请求被处理，结果进入稳定存储，服务端发送成功回复，客户端收到成功回复。哪个事实足以返回业务成功，取决于 API 的承诺。单机持久化接口可以要求同步完成后再回复；复制服务还必须定义副本确认和恢复规则，不能把这四个阶段全部叫作“提交”。

故障模型决定允许讨论什么

进程停止与进程恢复

崩溃停止模型允许进程停止，之后不再执行动作。崩溃恢复模型允许它重新启动，但恢复时哪些状态保留必须说明。把投票、日志或请求去重记录只放在内存里，与持久化它们，会得到不同的协议性质。

本篇只使用第二种模型：A 最多发生一次恢复，磁盘抽象保持不变。B、C 没有自动接管职责。三个节点同时存在，并不会自动产生选举、复制或容错能力；代码必须实际实现这些机制。

实际故障可能相关。同一主机上的三个进程会共享宿主机停机风险，同一机房中的三台服务器也可能共享供电或网络故障。一个模型允许“最多一个节点崩溃”，并不意味着现实一定遵守这一限制。部署拓扑需要解释这个故障上限为何合理。

消息延迟与超时

异步模型不给处理速度和消息传输延迟设置已知上界。到某个有限时刻没有收到回复，既可能是节点停止，也可能是节点仍在执行或者消息仍在传输。延长超时能改变等待成本，不能凭空增加一个原本不存在的时延上界。

FLP 论文在其模型中保留可靠消息传递，仍然存在这类不可区分性。因此“异步”和“可以丢消息”必须分别声明；不能用丢包解释所有异步系统困难。本篇为了演示请求不确定性，额外允许丢弃请求或回复。它并不是 FLP 原模型的完整实现。Fischer、Lynch、Paterson，1985，模型部分

同步模型允许利用规定的处理和传输上界。部分同步可以假定：经过一个未知的稳定时刻后，系统开始满足既定时限。Dwork、Lynch、Stockmeyer，1988实际系统据此设计故障怀疑和恢复机制，但“超过经验上的 200 毫秒”与“违反已证明的模型上界”是两回事。第 08 篇会详细讨论部分同步与故障检测。

本篇程序没有真实计时器。TIMEOUT 表示在选定观察截止点之前没有成功回复；被丢弃和晚于截止点到达，在这段客户端观察中都可以表现为无回复。程序没有枚举截止点之后迟到请求的行为。

持久化边界

应用修改内存、操作系统接受写入、设备报告同步完成，是不同阶段。Linux 的 fsync(2)还明确区分文件同步与父目录项同步，并提供错误返回。这个 Linux 契约不能直接替代 macOS 的实现说明。

SQLite 的原子提交文档把底层同步行为列为所依赖的假设；ATC 2020 关于 fsync 失败恢复的研究则说明错误处理路径值得单独验证。真实持久化实验必须写明操作系统、文件系统、同步方式和故障类型。本机正常退出后重启成功，不能证明突然断电也能恢复。

后续 KV 实验会接入文件与真实进程。本篇只把持久化作为显式状态转换，用来观察“何时确认成功”对恢复结果的影响。

相同的客户端观察，不同的系统结果

请求未到与回复丢失

第一条执行中，K 发出的请求被丢弃。A 没有执行任何写入，三个节点都保留 0，K 等到超时。

第二条执行中，请求到达 A，A 修改内存并同步，回复被丢弃。A 的两个状态都是 1，B、C 仍是 0，K 同样等到超时。

两条执行在 A 上留下不同状态，但 K 在截止点看到的都是无回复。图中的分支是两次独立执行，不是同一次请求先丢失、随后又被执行。

sequenceDiagram
    participant K as 客户端 K
    participant A as 节点 A
    alt 请求丢失
        K-xA: Put(x,1) 未到达
        Note over A: memory=0，stable=0
        Note over K: 截止点：TIMEOUT
    else 执行后回复丢失
        K->>A: Put(x,1)
        A->>A: memory=1，同步为 stable=1
        A--xK: OK 未到达
        Note over K: 截止点：TIMEOUT
    end

如果只把 K 的调用和返回记录交给判断程序，两条执行具有相同的输入：一次写调用和一次超时。判断程序如果宣告“没有执行”，就在第二条执行中出错；如果宣告“已经执行”，就在第一条执行中出错。可靠的输出必须保留未知，或者获取能区分两种执行的额外证据。

这是一种不可区分性论证。它足以否定“超时意味着没有执行”，但还没有证明共识不可解，也没有涵盖所有可能的请求历史。MIT 的 RPC 讲义列出了同类失败路径；gRPC 的 DEADLINE_EXCEEDED 契约也明确允许状态修改已经成功后返回截止期限错误。

成功回复与重启后丢失

第三条执行更直接：A 修改内存后就回复，K 收到 OK；A 没有同步就重启，恢复出 0。若接口承诺“成功后同一磁盘上的进程重启不会丢写入”，这条有限执行已经违反承诺。

把确认条件改为“同步成功后才能发送 OK”，可以消除这个模型中的反例。证明只需追踪不变量：收到 OK 意味着先前已有 stable=1；之后没有其他写入，允许的重启动作只把 memory 设为 stable，所以恢复后仍为 1。

确认放在同步之前还是之后，会改变重启后的可恢复值。两条路径都从 memory=0, stable=0 开始；图中的稳定状态只服从本篇抽象模型。

flowchart TD
    W["处理写入：memory=1，stable=0"]
    W --> V["易失确认：客户端收到 OK"]
    V --> VC["未同步就重启"]
    VC --> VL["从 stable=0 恢复：已确认写丢失"]
    W --> S["同步完成：stable=1"]
    S --> D["持久化确认：客户端收到 OK"]
    D --> DC["重启，从 stable=1 恢复"]
    DC --> DL["memory=1：该模型中保留写入"]

证明依赖三个限制：稳定状态不丢失、没有后续覆盖写、所有成功回复都经过同步条件。若增加磁盘损坏、第二个写者或者绕过条件的回复路径，就必须重新检查，不能沿用这个结论。

读到旧副本不能判定写入失败

即使第四条执行中 A 同步、回复、重启都成功，B、C 的本地值仍是 0。向 B 读取 0 并不能说明 A 没有执行写入，因为模型根本没有把更新传播给 B。

进一步，若 K 已经收到写成功，随后调用 B 的读，读却返回 0，这个读写历史不能满足一个初值为 0、没有其他写入的线性一致寄存器规格。线性一致要求每项操作能在调用与响应之间某处生效，同时保留不重叠操作的实时先后。已经完成的写必须排在随后开始的读之前。Herlihy 与 Wing，1990

这个反例只判定给定 API 组合不满足该规格。允许陈旧读取的接口本来就没有承诺这样的语义。为了改变承诺，系统可能需要等待传播、约束读目标或者运行读屏障；第 06、07 篇会分析各自成本。

安全性、活性和完成时限

安全性描述不允许发生的错误。一个成功确认的写在约定重启后消失，就是本篇持久性规格的违例。观察到这段有限历史，已经足以确认违例；后面再把值修回去也不能抹掉先前发生过的错误。

活性描述最终需要发生的进展，例如在相应环境假设下，每个有效请求最终得到处理。一个服务始终等待同步而从不回复，可以避免错误确认，却不能因此声称服务可用。Alpern 与 Schneider 的定义和 Lamport 的教程分别给出了形式化区分与停滞反例。

本篇第五条执行把这个取舍暴露出来：请求已被处理，但同步没有发生；即使回复通道畅通，要求持久化的策略也不产生 OK。在尚未重启丢失易失状态时，继续等待只有在同步最终完成、相关进程继续运行、回复最终可达等前提下才可能成功。第五条具体轨迹已经重启并丢失该写入，单纯等待不能补回请求，还需要重试等额外机制。把永远失败的设备换掉，属于额外的恢复设计。

“最终完成”也不等于“十秒内完成”。带上界的要求一旦错过截止点，就有可观察的有限违例；单纯的最终性不能靠等十秒就否定。工程 SLO、超时策略和协议活性应分别描述。

有限实验通常能有效找出安全性反例，却不能靠几次顺利运行证明无限执行中的活性。本篇自检也没有检查调度公平性或无穷次重试，不宣称完成活性证明。

运行确定性模型

累计代码位于仓库 examples/distributed-systems/，本篇入口是 model00/main.go。它只使用 Go 标准库，不联网、不创建服务、不修改系统配置。需要 Go 1.23 或更新版本；本次运行环境和原始输出放在随文的验证记录。

在博客仓库根目录执行：

1
2
3
cd examples/distributed-systems
go run -race ./model00
go run ./model00 -check

程序先打印五条构造执行，再执行自检。以下是本次实际输出，不是对真实集群的预测：

1
2
3
4
5
6
request-lost client=TIMEOUT executed=false A(memory=0,stable=0) B=0 C=0
reply-lost client=TIMEOUT executed=true A(memory=1,stable=1) B=0 C=0
volatile-ack-restart client=OK executed=true A(memory=0,stable=0) B=0 C=0
durable-ack-restart client=OK executed=true A(memory=1,stable=1) B=0 C=0
sync-missing client=TIMEOUT executed=true A(memory=0,stable=0) B=0 C=0
CHECK histories=10 volatile-ack-losses=1 durable-ack-losses=0 timeout-has-both-outcomes=true

executed 是模拟器的全局观察字段，客户端没有读取这个字段的接口。client 只表示收到 OK 或截止前没有成功回复。把调试输出中掌握的全部状态赋予客户端，会破坏前面的不可区分性论证。

枚举的四个布尔选择是：请求是否到达、是否执行同步、回复通道能否在截止前交付、之后是否重启。请求未到达时，不允许执行同步，也不把不存在的回复交付出去；16 种组合中留下 10 种。每种组合比较两种确认策略，统计已成功确认但最终内存值不为 1 的情况。

在持久化确认策略中，“回复通道可交付”只表示传输条件满足；若同步未发生，服务端根本不产生成功回复。因此第五行仍然超时。它与第三行使用同样的环境条件，仅确认策略不同。

这个有限枚举覆盖的是固定顺序的单次写入片段。它没有枚举消息重排、重复请求、并发写入、复制确认和多次重启；B、C 在所有片段里均保持隔离。输出中的 durable-ack-losses=0 仅表示这 10 种组合没有出现该类违例。

程序内置检查还要求：确实找到易失确认丢写的反例；确实存在执行与未执行两类超时；没有接收消息的 B、C 不能凭空变化。任一检查不满足，进程返回非零状态。删除同步赋值后应触发失败，可以用这个变异检查验证自检并非只会打印 PASS。

先修自测与练习

系统编程自测

解释一条 RPC 至少需要识别调用参数、发送、服务端处理、回复和客户端截止期限。解释一次恢复至少需要区分内存状态与被恢复的状态。解释并发程序还需要知道“读取后加一再写回”由多个动作构成，两个执行流可能都读取旧值。

如果这些动作还不能独立拆开，先完成 Go Tour 的并发章节，并用纸笔列出两个执行流对初值 0 做一次加一时，怎样得到最终值 1。互斥锁可以保护同进程内的临界区，却不能自动保护另一个节点上的副本。

数学自测是把“可能”写成集合。对仅观察到超时的 K，允许的执行至少包含请求丢失和回复丢失两种。判断“确定已执行”需要这个集合里的每条执行都已执行；证明“有可能执行”只需找到其中一条。把存在量词误当全称量词，是从单次实验推出协议保证时常见的错误。

练习一：补全三节点时间线

A、B、C 初值都是 0，B、C 在全过程中没有收到更新。K 发出一次写请求并超时，随后向 B 读取到 0。分别构造 A 从未执行和 A 已同步写入两条时间线，再回答：增加 B 的读结果是否消除了写入的不确定性？

参考推导：两条执行都能产生 TIMEOUT 和 B=0，因此仍不能区分。若要提供额外证据，必须说明查询对象、查询语义和请求身份；例如某个可靠的操作状态接口明确记录该请求已完成。随便读到 x=1 也未必能确认请求身份，在允许其他写者时尤其如此。

练习二：修改故障前提

保留“同步后才能确认”的策略，但把故障改成磁盘内容丢失，重启时 stable 也变回 0。写出最短的已确认丢写时间线，并指出前面归纳论证的哪条前提被破坏。再判断：只增加一个长期不可达的 B，是否足以恢复原承诺？

参考推导：处理、同步、收到 OK、磁盘丢失、重启，即得到反例。被破坏的是稳定状态跨故障保留的前提。B 如果没有收到并保留更新，就没有可恢复的数据；节点数量本身不能替代复制和恢复协议。若把成功条件改成必须等待 B，则还需要讨论 B 长期不可达时的进展。

第 01 篇将把单次调用扩展到重试：响应丢失后，如何识别同一个请求，怎样让并发重试不重复产生副作用，以及去重记录丢失后承诺如何变化。本篇尚未实现这些机制。

参考资料与证据层次

研究核验日期为 2026-09-19。两校课表用于教学结构；FLP、线性一致性与安全性/活性论文用于模型定义；gRPC、Linux 和 SQLite 文档用于说明接口边界。对应标题、版本或日期、论断及核验状态保存在本篇证据索引。

实验输出属于本地教学模型观察，没有运行 ZooKeeper、etcd 或真实三节点服务，没有进行文件系统故障注入或断电测试。原始论文的结论、接口声明与这份输出分别提供不同层次的证据，不能相互替代。