Lecture 20: Replication Control and Two-Phase Commit — 复制控制与两阶段提交
Lecture 20: Replication Control and Two-Phase Commit — 复制控制与两阶段提交
讲义对应：CS 425 FA2026 Lecture 22（Replication Control and Two-Phase Commit）。主要素材为 FA2025 Lecture 21「Replication Control」（
L21.FA25.txt，30 页，Final 版）；2PC 的事务与并发控制前置素材为 FA2025 Lecture 19-20「RPCs and Concurrency Control」（L19-20.FA25.txt）；复制状态机与全序多播参考 FA2025 Lecture 16「Multicast」（L16.FA25.txt）；复制与共识的关系参考 FA2025 Lecture 15-B「Paxos」（L15.B.FA25.txt）；工业界的复制实践（quorum、hinted handoff）参考 FA2025 Lecture 9-11「Key-Value Stores」（L9-11.FA25.txt）。 教材对应：Coulouris 5th Ed. Ch. 18（Replication）、Ch. 17（Distributed Transactions，17.3 两阶段提交）、Ch. 16（Transactions and Concurrency Control，2PL 与隔离性）；补充：Ch. 15（Coordination and Agreement）。 阅读材料：Schneider, Implementing Fault-Tolerant Services Using the State Machine Approach（1990）；Gray & Lamport, Consensus on Transaction Commit（2004）；Skeen, Nonblocking Commit Protocols（1981）；Corbett et al., Spanner: Google’s Globally-Distributed Database（OSDI 2012，TrueTime 与 “2PC over Paxos” 两节）；Cassandra 2.0 文档（可调一致性、hinted handoff）。
20.1 概述
上一讲解决的问题是：多个并发客户端同时操作同一台服务器上的对象时，如何保证隔离性（并发控制，2PL、时间戳排序、乐观并发控制）。本章把对象从”一台服务器”搬到”多台服务器”，于是出现两个新问题：
- 复制控制（Replication Control）：同一个对象在多台服务器上有多份副本，如何让所有客户端仍然看到”同一个逻辑对象”？这就是复制一致性问题，核心工具是主动复制与被动复制两种请求处理模式，以及它们背后的复制状态机（Replicated State Machine）假设。
- 原子提交（Atomic Commit）：一个事务的多个操作分别落在不同服务器上，如何保证”要么全部提交、要么全部中止”？讲义明确指出这就是共识问题的一个实例（”What problem is this? — Consensus! (It’s also called the ‘Atomic Commit problem’)”），工程上的标准答案是两阶段提交（Two-Phase Commit, 2PC）。
本章在整门课中处于”把前面所有积木拼起来”的位置：它的故障检测来自 Lecture 6/7，全序多播与虚拟同步来自 Lecture 16，共识（Paxos）与领导者选举来自 Lecture 15/17，Cassandra 的 quorum 与 hinted handoff 来自 Lecture 9，一致性模型与逻辑时钟来自 Lecture 10/11，事务、ACID、2PL 来自上一讲。学完本章，你应当能够回答一个系统设计面试级问题：“为什么 Spanner 要在每个分片内部跑 Paxos，跨分片还要再跑 2PC？为什么不直接用 2PC？为什么不直接用 Paxos？”
贯穿全章的核心矛盾只有一句话：复制提高可用性，但副本越多、保持一致的成本与延迟越高。而本章的黄金法则（20.6 会再次强调）是：
2PC 用两个 RTT 换来了原子性，但代价是它在协调者（coordinator）故障时会阻塞——因为它依赖一个单点的、不复制的一致性决策者。现代系统用共识来复制这个决策者，从而在保留原子性的同时消除了阻塞。把单点替换成多数派，就能把”可能永久阻塞”变成”短暂选举窗口”。
20.2 核心概念与分布式机制图解
20.2.1 复制是什么、为什么（Replication: What and Why）
定义与目的：复制（Replication） 指一个对象拥有多份完全相同的拷贝，每一份由一个独立的服务器维护，这些拷贝称为副本（replica）。讲义给出三条动机，必须逐一理解，因为后面所有的设计权衡都从这三条推出来。
- 动机一：容错与可用性（Fault-tolerance / Availability）。若每个对象有 $k$ 个副本，则可以容忍系统中任意 $k-1$ 个服务器故障而对象依然可用。设单个服务器处于宕机状态的时间比例为 $f$（即单点故障概率），则：
- 无复制时对象的可用性 $=$ 单副本存活的概率 $=1-f$；
- 有 $k$ 个副本时，只要至少一个副本存活即可用： \(A(k)=1-f^{k}\) 讲义给出的可用性表（注意这不是线性提升，而是指数级提升）：
单机故障率 $f$ 无复制 $k=3$ 副本 $k=5$ 副本 0.1 90% 99.9% 99.999% 0.05 95% 99.9875% 6 个 9 0.01 99% 99.9999% 10 个 9 直觉解释：$f=0.1$ 时，3 个副本同时宕机的概率是 $0.1^3=0.001$，所以可用性从 90% 跳到 99.9%。这就是”三副本”成为工业标准配置的原因。但要立刻补一句警告：这个公式假设副本故障相互独立。真实系统里同一个机架、同一个交换机、同一个可用区、同一份运维脚本导致的故障是相关的（correlated），所以实际可用性远低于公式——这正是后面”跨机架、跨可用区、跨地域”部署的依据。
动机二：负载均衡与性能（Load balancing / Scalability）。读/写操作分摊到 $k$ 个副本上，每个副本的负载降到单副本的 $1/k$。对读多写少的负载，这条动机甚至比容错更重要：Cassandra 的
LOCAL_QUORUM、MySQL 的读写分离、GFS 的”从就近副本读”都是这个动机的产物。此外，副本可以放在地理上靠近客户端的位置，把跨洲的 200 ms 往返变成同城 1 ms。详见 Lecture 9（Cassandra 的复制策略与多数据中心部署）。动机三：容灾（Disaster tolerance）。副本可以跨越数据中心、跨越地域甚至跨越云厂商。单个数据中心整体断电、光缆被挖断、机房被水淹时，另一个地域的副本可以接管。这是RPO/RTO 指标（20.2.15 详述）的由来：容灾能力必须在”副本放在哪里”这个架构决策里就确定下来，事后再加是来不及的。
- 核心矛盾（必须贯穿全章）：复制带来一致性维护的成本。副本越多，可用性越高、读吞吐越大，但让它们保持一致的代价（消息、延迟、协调）也越大。这个矛盾在三个地方以不同面目出现：
- 写路径：写请求必须决定”要等几个副本确认”（同步 / 半同步 / 异步）；
- 读路径：读请求必须决定”读几个副本、读到的可能是旧值吗”（$R+W>N$ quorum，Lecture 9）；
- 跨分片事务：事务的原子性必须由一个决策者协调（2PC），而这个决策者本身又成了新的单点——于是又需要复制它（共识）。
20.2.2 复制的两个必须维持的性质（Replication Transparency & Consistency）
- 定义与目的：讲义把复制的”麻烦”归结为两个必须同时维持的性质：
- 复制透明性（Replication Transparency）：客户端不应感知到服务器端存在多份拷贝。客户端写的是”对象 $O$”，不是”$O$ 的第 2 号副本”。
- 复制一致性（Replication Consistency）：尽管有复制，所有客户端看到的必须是单一的一致拷贝；对有事务的系统，必须保证 ACID。
直观解释（”它是什么？”）：把复制系统想象成一家连锁银行。客户在任意一家支行存取款（透明性：客户不需要知道总行账本有几本），但无论走进哪家支行，查到的余额都必须一致（一致性）。如果 A 支行说余额 100 元、B 支行说 80 元，那系统就是坏的——哪怕它”没有宕机”。
- 副本一致性的形式化目标：单拷贝可串行化（One-copy Serializability）。讲义给出了精确定义：
一个在复制数据库上的并发事务执行是单拷贝可串行化的，当且仅当它等价于这些事务在数据库的单一逻辑拷贝上的某个串行执行。
换句话说：复制的效果必须等同于根本没有复制——客户端的效果应当与”每个对象只有一个副本、事务一个接一个地执行”完全一样。非复制系统中的正确性判据是”串行等价（serial equivalence，见上一讲）”；有复制时，正确性判据升级为”单拷贝可串行化”。这是本章的第一个”硬指标”，20.3.1 的被动复制协议必须满足它（在不发生故障的前提下）。
- 机制图解：
+--------+ +--------+ +--------+ 客户端只看到"对象 O"
|Client 1| |Client 2| |Client 3| 不知道副本的存在
+---+----+ +---+----+ +---+----+
| | | <-- 复制透明性由 FE 提供
v v v
+--------+ +--------+ +--------+
|FrontEnd| |FrontEnd| |FrontEnd| 前端 (FE)：接口层
+---+----+ +---+----+ +---+----+ 找副本 / 转发 / 去重
| | |
+--------------+--------------+
| 请求（应答反向流动）
+---------------+----------------+
| | |
v v v
+--------+ +--------+ +--------+
|Replica1| |Replica2| |Replica3| 副本管理器 (RM)：管理一个副本
| (RM) |<---->| (RM) |<----->| (RM) | RM 之间也通信：
+--------+ +--------+ +--------+ 传播更新 / 心跳 / 投票选举
- 关键假设与系统模型：本章默认的系统模型是：异步网络（消息延迟无上界，但最终会到达，即 fair-loss 链路）、崩溃-恢复故障模型（crash-recovery）、非拜占庭（节点不会说谎，只会停止或重启）。副本数 $N$，故障数 $f$。凡是需要”超时”的地方，都意味着我们在偷偷依赖”最终同步”或”部分同步”的假设——这一点在 20.3.4 讨论阻塞性与不可能性时会反复用到。
20.2.3 系统角色：前端与副本管理器（Front End & Replica Manager）
- 定义与目的：讲义用两个角色把复制系统切开：
- 前端（Front End, FE）：客户端与副本系统之间的接口层。它接收客户端请求，负责找到（或转发给）合适的副本，并把应答返回客户端。复制透明性就是由 FE 提供的。
- 副本管理器（Replica Manager, RM）：管理一个副本的进程。它与 FE 通信（收请求、发应答），也与其他 RM 通信（传播更新、心跳、参与选举投票）。
直观解释（”它是什么？”）：FE 像医院的分诊台：病人（客户端）只需要说”我要看内科”，分诊台决定把他送到哪个诊室（副本）；RM 则是具体的诊室，诊室之间还会互相通气（”这个病人我刚看过”）。客户端永远不需要知道有几个诊室、哪个诊室更空闲——这就是透明性。
- 关键设计点：
- FE 可能是一个库、一个代理进程，或者干脆是客户端的一部分（例如 Cassandra 的”协调者节点”就是客户端连接的任意一个节点，它临时充当 FE 角色，Lecture 9）。
- FE 必须知道”当前哪个副本是主/在哪里”：被动复制下 FE 要把请求发给 primary；primary 故障切换后 FE 必须更新地址。工业界用配置服务/服务发现（ZooKeeper、etcd/Consul、Kubernetes Service）解决，20.2.8 详述。
- FE 通常还要做请求去重（dedup）或至少传递唯一请求标识（rid），这是 20.2.7 的关键细节。
20.2.4 复制状态机（Replicated State Machine, RSM）
- 定义与目的：主动复制与被动复制表面上完全不同，但它们共享同一个理论基础，讲义引用 Schneider 1990：
多份相同的状态机，从相同的初始状态出发，按相同的顺序接收相同的输入，必将到达相同的状态，并产生相同的输出。
直观解释（”它是什么？”）：这就像两台完全相同的计算器：如果你给它们按完全相同的按键序列，它们一定显示相同的结果。而如果你给它们按了不同的顺序（先 ×2 再 +1 vs 先 +1 再 ×2），结果就不同了。所以复制的全部难点可以一句话概括：把所有副本变成同一台计算器，然后保证它们收到同样顺序的按键。
- 两个推论（本章所有协议的地基）：
- 确定性要求（determinism）：状态机必须是确定性的——相同状态 + 相同输入 ⇒ 相同输出。如果操作里有
random()、time.now()、getpid()、并发线程调度导致的不确定顺序，副本状态就会发散。工程做法：由 primary 或 leader 把这些不确定值先算好并写进日志（如 Raft 把时间戳写进日志条目），使副本回放时变成确定性操作。这是主动复制必须解决的问题。 - 顺序要求（ordering）：输入必须按同一顺序送达所有副本。这正是 Lecture 16 的多播排序问题：全序多播（total order multicast / atomic broadcast） 提供这个保证。Causal 或 FIFO 多播只在应用能容忍时才够用（讲义原话：”Could also use causal (or even FIFO) ordering if application can tolerate it”）。
- 确定性要求（determinism）：状态机必须是确定性的——相同状态 + 相同输入 ⇒ 相同输出。如果操作里有
- 机制图解（RSM 与多播的关系）：
客户端请求 ──► 全序多播（Lecture 16）──► 每个副本按相同顺序投递
│
┌─────────────────────────┼─────────────────────────┐
▼ ▼ ▼
┌───────────────┐ ┌───────────────┐ ┌───────────────┐
│ 状态机 (副本1) │ │ 状态机 (副本2) │ │ 状态机 (副本3) │
│ 相同初态 S0 │ │ 相同初态 S0 │ │ 相同初态 S0 │
└───────────────┘ └───────────────┘ └───────────────┘
└──────── 相同输入序列 ⇒ 相同状态 S 与相同输出 ────────┘
- 关键假设与系统模型：RSM 要求 (a) 副本数固定或通过成员管理维护视图（Lecture 16 的 virtual synchrony 处理 join/leave/failure）；(b) 所有正确（correct）副本都能收到全部多播（可靠多播）；(c) 状态机确定性。只要这三条成立，主动复制就等价于”用一个逻辑副本服务所有客户端”，即单拷贝可串行化。
20.2.5 主动复制 vs 被动复制（Active vs Passive Replication）
- 定义与目的：讲义给出”FE 把更新转发给副本组的两种方式”：
- 被动复制（Passive Replication）：使用一个 primary 副本（也叫 leader，历史上叫 master）。只有 primary 执行请求，其余副本（backup）只接收并应用 primary 产生的更新。因为它的另一名字是 primary-backup replication。
- 主动复制（Active Replication）：所有副本同等对待，请求被多播给整个副本组，每个副本各自执行一遍。
- 直观解释（”它是什么？”）：一场会议谁来做记录？
- 被动复制：只有主持人记录，然后把结论念给其他人听。好处是只需一个人做决定，不会记岔；坏处是主持人若中途离场，会议就卡住了（需要重选主持人）。
- 主动复制：每个人同时记录同样的发言。好处是没有”主持人单点”，谁倒下都不影响；坏处是必须保证每个人听到的发言顺序完全一致，否则两份记录会对不上（状态发散）。
- 机制图解（架构与消息流对比）：
主动复制 Active Replication 被动复制 Passive Replication
Client --> FrontEnd Client --> FrontEnd
| |
| ① 请求多播给整个副本组 | ① 请求单播给 primary
+-----------+-----------+ +---------+---------+
| | | | RM1 primary |
v v v +---------+---------+
+-------+ +-------+ +-------+ | ② Xfer(状态/操作)
| RM1 | | RM2 | | RM3 | +------+------+
+-------+ +-------+ +-------+ | |
每个 RM 都执行同一个请求 v v
=> 需要全序多播 + 确定性 +------------+ +------------+
| RM2 backup | | RM3 backup |
+------------+ +------------+
只按 primary 的顺序应用，自己不执行请求
- 对照表（必须背下来的框架）：
| 维度 | 主动复制（Active） | 被动复制（Passive / primary-backup） |
|---|---|---|
| 谁执行请求 | 每个副本都执行 | 只有 primary 执行，backup 只应用结果 |
| 复制的对象 | 请求/操作本身（多播输入） | 更新结果（新状态或操作序列） |
| 顺序保证 | 必须有全序多播（否则状态发散）；可退化为 causal/FIFO（若应用容忍） | primary 天然给出全序（它自己串行执行） |
| 对确定性的要求 | 高：所有副本必须确定性执行 | 低：backup 只是重放 primary 已确定的结果 |
| 故障切换复杂度 | 低：任何副本都在同一状态，直接继续服务 | 高：需要选主、找最新副本、通知 FE、防脑裂 |
| 请求延迟 | 多播 + 等待”足够多”副本确认（取决于多播/共识实现） | 同步模式下 = 最慢的 backup；异步模式最低 |
| 客户端/FE 的负担 | FE 不需要知道 leader（透明性更强） | FE 必须知道谁是 primary（需要配置服务） |
| 代表系统 | 复制状态机 + Paxos/Raft（Chubby、ZooKeeper、etcd、Spanner 的 Paxos 组）、状态机复制中间件 | GFS/HDFS（NameNode 单点 + HA）、MySQL 主从/半同步、Redis Sentinel、Kafka 的 leader-follower 分区 |
| 主要难点 | 全序多播 + 确定性 + 成员管理 | 选主 + 数据追赶（catch-up）+ 脑裂（split-brain） |
- 关键假设与系统模型：被动复制要求 primary 唯一（否则两个 primary 都接受写 ⇒ 数据分歧，见 20.2.8 的 fence）。而”唯一 primary”这个性质本身在异步系统中无法由超时可靠地判定（Lecture 7：不可能区分”崩溃”与”很慢”），所以必须借助租约（lease）或多数派选举来近似保证，这是 20.2.15 要讨论的内容。
20.2.6 复制协议的分类：在哪里发起 × 何时传播
理解复制协议最好的框架是两个正交维度：“谁发起复制”（Where） 与 “何时传播更新”（When）。
维度一：在哪里发起（Where）
- 客户端发起的复制（Client-based）：客户端（或 FE）直接与多个 RM 通信：把写发给多个副本，自己等待足够多的确认。优点是没有额外的中间层，客户端可以按自己的偏好选择一致性级别；缺点是客户端要理解复制协议，且透明性差。
- 服务器发起的复制（Server-based）：客户端只与一个 RM 通信，由该 RM 负责转发给其他 RM。被动复制天然属于这一类；主动复制若配合一个”多播代理”也可以归入此类。优点是透明性最好、客户端逻辑最简；缺点是被选中的那个 RM 成了瓶颈与单点（例如 Cassandra 的协调者节点）。
维度二：何时传播（When）—— 同步 / 异步 / 半同步
- 同步复制（Synchronous）：写操作必须等所有副本确认。强一致（读任何副本都能读到最新值），但延迟由最慢的副本决定；任一副本宕机或变慢都会拖累甚至阻塞写入 ⇒ 可用性下降。
- 异步复制（Asynchronous）：主副本本地执行完毕（写日志）立即向客户端返回，更新在后台传播。延迟最低、可用性最高；但主副本崩溃时尚未传播的更新会丢失，即 $RPO>0$（恢复点目标大于零，会丢数据）。
- 半同步复制（Semi-synchronous）：折中方案，只要至少一个（或多数派）副本确认即可返回。既能保证”至少有一份最新数据存活”，又不必等最慢的那个。
- MySQL 半同步复制：主库等至少一个从库 ACK（
rpl_semi_sync_master_wait_for_slave_count）； - Kafka 的
acks=1：leader 写入本地日志即返回（等 ISR 全部为acks=all）； - Raft/Paxos 的多数派：写入需多数派持久化，本质就是”半同步”（只不过它同时给出了共识而非单纯复制）；
- Cassandra 的
QUORUM：$W=\lfloor N/2\rfloor+1$ 个副本确认（Lecture 9 的可调一致性）。
- MySQL 半同步复制：主库等至少一个从库 ACK（
- 权衡表：
| 方案 | 客户端写延迟 | 可用性（写） | 数据丢失风险 RPO | 一致性 | 典型参数/系统 |
|---|---|---|---|---|---|
| 同步（等全部 $N$） | 最高 = 最慢副本 | 最低（一个副本卡住就全卡） | 0（已确认的写不丢） | 强（任何副本可读最新） | Cassandra ALL、MySQL 全同步、GFS 的 pipeline ack |
| 半同步（等多数派或 1 个） | 中等（等第 $k$ 快的副本） | 较高（容忍少数副本慢） | 0（只要被确认的副本活着）或极小 | 强（配合 $R+W>N$） | Raft/Paxos、Cassandra QUORUM、Kafka acks=all、MySQL 半同步 |
| 异步（立即返回） | 最低（本地写完即返回） | 最高（副本全挂也能写） | > 0（主崩溃丢未传播更新） | 最终一致 | MySQL 异步主从、Redis 异步复制、Cassandra ONE/ANY |
- 关键的工程判断：同步 vs 异步的选择本质上是在 RPO 与延迟/可用性之间做选择，而且这个选择常常要按操作类型分级——例如”下单扣库存”用半同步，”记录用户浏览历史”用异步。真实系统几乎从不全局使用”等全部副本”的同步复制，因为它的可用性是”所有副本的可用性之积”。
20.2.7 被动复制的详细协议：请求处理与去重
被动复制的请求处理流程如下（讲义与教材的标准表述）：
- FE 把请求发给 primary RM（FE 从配置服务得知谁是 primary）。
- primary 检查请求的唯一标识符（去重）：FE 通常在超时后重发请求，因此同一条请求可能到达 primary 两次。若不去重，非幂等操作（如
x = x + 1）会被执行两次 ⇒ 数据错误。 - primary 执行请求（或先写日志再执行），然后向所有 backup 发送
Xfer(state_update)消息。 - backup 收到后更新自己的状态（同时把更新写入自己的日志），并回复 ack。
- 同步模式：primary 等所有 backup 的 ack 之后才回复 FE；异步模式：primary 立即回复 FE，更新在后台传播。
- primary 保留一份更新历史（update log），供落后或重启的 backup 追赶（catch-up）。
- 为什么必须去重（讲清楚这条链）：FE 发出请求后启动定时器；若在超时前没有收到应答，它无法区分“请求丢了”、”primary 慢”、”应答丢了”这三种情况（Lecture 19-20：RPC 在故障下难以保证 exactly-once）。于是 FE 只能重发 ⇒ 语义是 at-least-once ⇒ 请求可能被执行多次。解决办法有两条：
- 让操作幂等（idempotent）：
x = 1幂等，x = x + 1不幂等（Lecture 19-20 已给出定义）； - 让 primary 按请求 ID 去重：维护
rid → 结果表，重复请求不重新执行，直接返回缓存结果。这就把语义升级为 at-most-once（对重复请求），即”重复请求至多生效一次”。 去重表必须和状态一起持久化（或至少与状态在同一事务里更新），否则 primary 崩溃恢复后去重表丢失，重放的请求会被再执行一遍。
- 让操作幂等（idempotent）：
- 机制图解（请求处理、去重与传播）：
+-----------------------+ +------------------+
| RM1 primary | | 结果缓存 (rid) |
FE -->| ① 查重表: rid=88 ? |----------------------->| ⑤ 重复请求直接答复 |
| ② 执行 + 追加更新日志 | +------------------+
+-----------+-----------+
| ③ 同步: Xfer 并等所有 ack ; 异步: 丢进后台队列
+-------+-------+
| |
v v
+-------------+ +-------------+
| RM2 backup | | RM3 backup | ④ 应用更新, 回 ack(lsn)
+-------------+ +-------------+
| |
+-------+-------+
v
backup 落后时向 primary 请求 from = lastLSN + 1 起的更新（catch-up）
- 传递的是什么？两种传播粒度（必须讲透）：
- (a) 状态更新传播（state transfer）：primary 把更新后的状态（或状态差异，如”对象 A 的新值 = 42”）发给 backup。
- 优点：自包含（收到即可应用，不依赖副本的执行逻辑）、易恢复（新副本只需一份快照即可上线）、对副本的确定性没有要求。
- 缺点：消息大（状态可能远大于引起它的那一次操作，例如”给整个列表排序”的状态更新可能几 MB，而操作只有几个字节）；更新频率高时带宽开销大。
- (b) 操作更新传播（operation transfer）：primary 把操作本身（”插入元素 x 到位置 3”）发给 backup，由 backup 自己执行。
- 优点：消息小、与请求大小同阶；天然可压缩、可批量。
- 缺点：要求副本确定性（否则重放结果不同），且副本必须能独立完成计算（例如操作依赖
now()或随机数时，primary 必须把该值写进操作消息）。
- 工程折中：工业系统常用混合——日志里记操作、定期打快照（snapshot）；落后太多的副本不做逐条追赶（太慢），而是直接传快照再补增量。这也是 Raft 的
InstallSnapshot与 MySQL 的mysqldump + binlog组合。
- (a) 状态更新传播（state transfer）：primary 把更新后的状态（或状态差异，如”对象 A 的新值 = 42”）发给 backup。
- 关键假设与系统模型：FE→primary 与 primary→backup 的通道是 fair-loss（可能丢失、重复、乱序，但重传最终能送达）；RM 具备稳定存储（stable storage） 保存日志与状态；FD 不可靠（可能误判）。
20.2.8 故障处理与故障切换（Failover）：本章最工程化的部分
被动复制的全部难点都在故障处理上。我们分三类讨论。
(1) Backup 故障
- 同步模式：primary 等不到某个 backup 的 ack。做法通常是：(a) 在超时后把该 backup 从”需要确认的集合”中移除（若剩余副本数仍满足 quorum，例如多数派），继续服务；(b) 若剩余副本太少，则拒绝写（宁可不可用也不能丢数据）。
- 异步模式：primary 继续服务，把发给该 backup 的更新暂存在队列里；backup 恢复后需要追上（catch-up）：从 primary 获取
from = lastLSN + 1起的更新。这就要求 primary 保留更新历史；若 backup 落后太多（历史已被截断），则改用快照 + 增量。 - 一个容易被忽略的细节：backup 在追赶期间不应对外提供读服务（否则会返回旧数据），或者必须标记为
stale让 FE 回避。Cassandra 用 read repair 与 Merkle Tree 反熵修复解决同类问题（Lecture 9）。
(2) Primary 故障 → 故障切换（Failover）——标准四步：
- 检测：由故障检测器（failure detector） 判定 primary 无响应（心跳超时、Phi accrual 等，详见 Lecture 6/7）。
- 选主：在 backup 中选一个晋升为新的 primary。必须选”最新”的那个——即拥有最大更新序号的副本。这需要每个 backup 维护 日志序号（log sequence number, LSN） 或版本号。
- 通知 FE：通过配置服务/服务发现（ZooKeeper、etcd、Consul）把新 primary 的地址写入配置，FE 读取后重定向请求（Lecture 9 的 coordinator、Chubby/ZooKeeper 的用途与此一致）。
- 补齐/回退：新 primary 若比某些 backup 落后（例如它本来不是最新的），需要向其他 backup 收集缺失的更新；若某些更新在旧 primary 上存在但任何 backup 都没有，只能丢弃——这正是异步复制的 RPO。
(3) 三个必须讲透的难点
- 难点一：如何确定哪个 backup 最新？ 仅比较 LSN 是不够的：备份可能”各有部分更新”（例如双向复制、或多主写入场景，$B_1$ 有 LSN 1-10，$B_2$ 有 LSN 1-8 和 12-15）。做法：
- 在单主（single-primary） 复制中，更新只在 primary 上产生并有序传播，因此 backup 的更新历史上一定是旧主日志的前缀 ⇒ “最大 LSN 者最新”是正确的判据；
- 在多主或更一般的场景，必须比较版本向量/依赖关系，或者干脆让新 primary 向多数派收集所有已知更新并做取舍（这已经进入”共识”的领域）；
- 定序必须确定性：当两个 backup 的 LSN 相同时，用
(LSN, term/epoch, nodeID)做总序比较，否则不同节点可能选出不同的主。
- 难点二：数据丢失（RPO）。异步复制下，primary 在崩溃前已向客户端确认、但尚未传播的更新会永久丢失。这不仅是”丢一点数据”，还会破坏客户端可见的语义：客户端明明收到了”写入成功”，之后却读不到该值（历史上称为”幻影写/回滚写”）。20.4.3 的代码会用具体数字量化这个损失。
- 难点三：脑裂（Split-brain）与 fencing。若旧 primary 并没有真正死亡（进程假死、网络分区、GC 停顿、虚拟机被挂起），而新 primary 已经上线，就出现两个 primary 同时接受写：客户端可能读到两个版本，两个副本永久分歧。防护手段：
- epoch / term（任期号）：每次选主把任期号 +1；写请求必须携带当前任期号，存储层拒绝小于当前任期的写（这就是 fencing token）。Raft 的 term、Paxos 的 ballot number 都是这个东西（Lecture 15-B/Lecture 17）。
- 租约（lease）：primary 在租约有效期内是唯一写者，租约到期必须重新申请；依赖时钟同步的上界（Lecture 11），所以租约时长必须远大于时钟漂移。
- 共享存储/STONITH：用存储或仲裁节点做”门卫”（如 HDFS 的 JournalNode 多数派、共享磁盘的 SCSI reservation），或直接物理隔离旧主（shoot the other node in the head）。
- 注意：仅靠”旧 primary 在收不到心跳时自杀”是不安全的——它可能恰好卡在收不到心跳又没死透的窗口里。安全边界必须在被写的一方（存储或仲裁多数派）执行，而不能只在写的一方自我约束。
(4) Primary 恢复后：它必须降级为 backup，以新 primary 为准同步（catch-up），绝不能重新以旧身份成为 primary，否则会把已经提交的数据回退（丢失新 primary 上已发生的更新）。这也是为什么 fencing token 必须持久化并随每次选主单调递增——恢复的旧主拿的是过期的 token，写会被拒绝。
- 机制图解（故障切换的六个阶段）：
+--------------+ +-------------+ +--------------+ +------------+ +--------------+
| ①故障检测 | | ②收集状态 | | ③选主+epoch | | ④FE 重定向 | | ⑤catch-up |
| FD 心跳超时 | --> | backup 上报 | --> | max LSN 晋升 | --> | 读配置服务 | --> | 落后副本补齐 |
| 怀疑 primary | | lastLSN 105 | | fencing = 2 | | ZK / etcd | | ⑥ 旧主降级 |
+--------------+ +-------------+ +--------------+ +------------+ +--------------+
③ 必须由配置服务以多数派方式确认（否则两个 backup 会各自称主 => 脑裂）；
⑤ 要求 primary 保留可追的更新历史（日志）并能生成快照，否则追赶永远做不完。
20.2.9 分布式事务与原子提交问题（Distributed Transaction & Atomic Commit）
- 定义与目的：一个事务 $T$ 可能触及分布在不同服务器上的对象：
Transaction T +-------------------+
write(A, 1); | Server 1 |
write(B, 2); | 对象 A, 对象 B |
... +-------------------+
write(Y, 25); .
write(Z, 26); . （中间还有 Server 2 ... Server 12）
commit +-------------------+
| Server 13 |
| 对象 Y, 对象 Z |
+-------------------+
当 $T$ 试图提交时，必须保证：要么这些服务器全都提交 $T$ 的更新（$T$ 提交），要么全都不提交（$T$ 中止）。讲义明确指出这个问题的本质：
“What problem is this? — Consensus!（(It’s also called the “Atomic Commit problem”)）”
也就是说，原子提交是共识问题的一个实例。这个判断非常重要，因为 Lecture 15/17 关于共识的结论（包括 FLP 不可能性）都可以借用到这里。
直观解释（”它是什么？”）：跨境转账：从 A 银行扣 1000 元、给 B 银行加 1000 元。如果扣款成功而加款失败（或反之），钱就凭空消失了。原子提交要的就是”两边要么都成、要么都不成”。
- 一阶段提交（One-phase Commit）及其两个致命缺陷：最朴素的做法是设一个协调者服务器（Coordinator Server），它在事务结束时直接通知各服务器”提交”或”中止”。讲义列出两个问题：
- 拥有对象的服务器没有发言权：如果某个服务器上的对象已损坏 / 约束冲突 / 锁冲突，它无法阻止提交——结果就是部分服务器提交了，而它不能提交，原子性被破坏。
- 服务器可能在收到提交消息之前崩溃，此时它的更新还在内存里（没落盘），重启后丢失；而其他服务器已经提交——同样破坏原子性。
结论：必须让参与者先表态（投票），再让协调者做决定。这就是”两阶段”的由来：先问，再做。
- 与两阶段锁（2PL）的关系（必须澄清，二者解决的是不同问题）：
- 2PL（两阶段锁）保证的是隔离性（Isolation）：通过加锁/解锁的两个阶段，使并发事务的执行串行等价。它作用在单机内部的并发事务之间。
- 2PC（两阶段提交）保证的是原子性（Atomicity）：通过投票/决定的两个阶段，使跨服务器的更新全局一致地提交或中止。它作用在同一个事务的多个服务器之间。
- 真实分布式数据库两者都要用：通常先在各分片上用 2PL（或 MVCC/时间戳）做本地并发控制，再用 2PC 做跨分片提交。二者名字相似（都叫”两阶段”）但完全正交，这是考试与面试的常见陷阱。
20.2.10 两阶段提交（2PC）：角色、流程与完整时序
- 角色：
- 协调者（Coordinator / 事务管理器 Transaction Manager）：通常是发起事务的那个站点（讲义：”Special server called ‘Coordinator’ initiates atomic commit. Tells other servers to either commit or abort”）。它负责收集投票、做出全局决定、广播决定。
- 参与者（Participants / RM）：每个站点的副本管理器。它负责执行事务的本地部分并对能否提交投票。
- 两个阶段：
- 阶段 1：投票阶段（Voting / Prepare Phase）。协调者向所有参与者发
PREPARE。参与者执行事务的本地部分（但不提交），把更新写入本地日志/临时区并落盘，检查本地能否提交（约束、锁、磁盘空间等），然后回复VOTE_COMMIT（yes） 或VOTE_ABORT（no）。- 关键：回复 yes 之后，参与者进入不确定状态（uncertain / in-doubt，本笔记记作
IN_DOUBT），它必须等待协调者的最终决定，期间不能释放锁，也不能单方面决定（讲义：”Wait! Can’t commit or abort before receiving next message!”）。
- 关键：回复 yes 之后，参与者进入不确定状态（uncertain / in-doubt，本笔记记作
- 阶段 2：决定阶段（Commit / Abort Phase）。协调者收集所有投票：
- 全部 yes ⇒ 全局提交（global commit），向所有参与者发
GLOBAL_COMMIT； - 任何一个 no，或有参与者在超时前未回复 ⇒ 全局中止（global abort），发
GLOBAL_ABORT。 - 参与者收到决定后：
GLOBAL_COMMIT⇒ 提交本地事务、释放锁、回ACK；GLOBAL_ABORT⇒ 回滚本地事务、释放锁、回ACK。协调者收齐ACK（或超时）后事务结束，可以清理日志。 - 协调者与参与者都必须把”决定”写入日志（WAL）并 fsync，这是崩溃恢复的唯一依据。
- 全部 yes ⇒ 全局提交（global commit），向所有参与者发
- 阶段 1：投票阶段（Voting / Prepare Phase）。协调者向所有参与者发
- 机制图解（2PC 完整消息时序图，本章最重要的图）：
C RM1 RM2 RM3
│ │ │ │
① 写 <T,START> 到 WAL 并 fsync
├─────PREPARE──────►
├───────────────PREPARE───────────────►
├────────────────────────PREPARE─────────────────────────►
│ │ │ │
② 各 RM 执行本地部分（不提交）
③ 把临时更新 + PREPARED 写日志 fsync ← 落盘点 P1
◄───VOTE_COMMIT────┤
◄─────────────VOTE_COMMIT─────────────┤
◄──────────────────────VOTE_COMMIT───────────────────────┤
│ │ │ │
④ 收齐投票：任意一个 NO（或超时）就 ABORT；全部 YES 才 COMMIT
⑤ 把 <T,DECISION,COMMIT> 写日志并 fsync ← 落盘点 C1 = 决定点（不可回头）
├──GLOBAL_COMMIT───►
├────────────GLOBAL_COMMIT────────────►
├─────────────────────GLOBAL_COMMIT──────────────────────►
│ │ │ │
⑥ 各 RM 提交、释放锁、写 <T,COMMIT> 日志 ← 落盘点 P2
◄───────ACK────────┤
◄─────────────────ACK─────────────────┤
◄──────────────────────────ACK───────────────────────────┤
│ │ │ │
⑦ 收齐 ACK，写 <T,END>，清理日志（只有此时才能忘掉这个事务）
总延迟 = 1 RTT（PREPARE→VOTE） + 1 RTT（决定→ACK） + 4 次 fsync 等待
- 现实类比（把 2PC 一秒钟讲懂）：婚礼策划。
策划人先给所有宾客发消息问”你来不来？”（
PREPARE）。宾客回复”能来”或”来不了”（投票）。只要有一个说来不了，婚礼就取消（一票否决）；全部说来得了，策划人才发正式通知（GLOBAL_COMMIT）。 关键在宾客这边：回复”能来”之后，宾客就不能自己决定改主意了——他必须等策划人的正式通知，期间得把那个周末空出来（= 持有锁）。如果策划人失联了（协调者崩溃），所有人只能说”我先把周末空着，等消息”，谁也不敢擅自安排别的行程——婚礼办不办谁也不知道。这就是 2PC 的阻塞：所有人的日程被一个失联的人锁住了。
20.2.11 2PC 的状态机（含 IN_DOUBT）
- 协调者状态机：
客户端请求 commit
|
v
+--------+ 广播 PREPARE +--------+ 收齐投票 +---------------+
| INIT |---------------->| WAIT |------------>| DECIDED |
+--------+ +--------+ | (决定已写入 |
| | | WAL, 不可改) |
| 崩溃(未发 PREPARE) | 超时: 未投票者 +-------+-------+
v | 记为 NO | 广播决定
[恢复后: 可安全 ABORT] v v
+---------------+ +-----------+
| 决定 = ABORT | | DONE |
| (一票否决/超时) | | 等 ACK / |
+---------------+ | 重发决定 |
+-----------+
- 参与者状态机：
+--------+ 收到 PREPARE +---------------------+ 收到 GLOBAL_COMMIT +-----------+
| INIT |---------------->| IN_DOUBT (PREPARED) |-------------------->| COMMITTED |
+--------+ 执行本地部分 | 已投 YES, 持锁, | 提交 + 释放锁 +-----------+
| 写日志 fsync | 不能单方面决定 |
| +----------+----------+ 收到 GLOBAL_ABORT +-----------+
| 本地检查失败 / 崩溃 | | 超时(2PC 中什么也不做) --------->| ABORTED |
v | v +-----------+
+-----------+ 投 NO 后 | [轮询协调者/等待恢复]
| ABORTED | 立即释放锁、 |
| (可单方面) | 可单方面中止 |
+-----------+<-----------------+
- 两条不对称的规则（学生最常搞混）：
- 投了 NO 的参与者可以立即中止（讲义特意提问：”If server voted No, can abort right away (why?)”）。原因：全局提交要求所有参与者投 yes，既然它投了 no，全局决定必然是 abort。它不会与任何人的决定冲突，所以可以立刻释放锁、减少阻塞——这就是 20.2.13 的 read-only / 提前中止优化的思想来源。
- 投了 YES 的参与者绝对不能单方面决定：因为全局决定取决于别人的投票，它无从得知（这正是 20.3.4 要形式化证明的结论）。
20.2.12 2PC 的核心缺陷：阻塞（Blocking Problem）
- 场景 1：参与者崩溃（Participant crash）——相对温和：
- 参与者在收到 PREPARE 之前崩溃 ⇒ 协调者等不到它的投票 ⇒ 超时 ⇒ 视为 no ⇒ 全局中止。整个协议可以终止。
- 参与者在回复 yes 之后崩溃 ⇒ 协调者同样超时（悲观处理）⇒ 全局中止 ⇒ 其他参与者中止；崩溃者恢复后从日志看到”有 PREPARE、有我的 YES 投票、但没有决定”，它可以安全地中止（因为全局决定必为 abort），但它更稳妥的做法是向协调者询问决定——因为”协调者超时”这个事实它并不知道，且它无法排除”协调者已经决定提交、只是消息没送到”的情况。讲义给出的处理是：在阶段 1 回复之前把暂定更新写入持久存储，崩溃恢复后可以取回。
- 参与者在收到决定之后、执行之前崩溃 ⇒ 恢复后从日志重放决定、完成提交/回滚、重发 ACK。
- 场景 2：协调者崩溃（Coordinator crash）——这是 2PC 真正的问题：
- 若协调者在发送
PREPARE之后、做出决定之前崩溃 ⇒ 所有投了 yes 的参与者全部卡在IN_DOUBT：它们拿着锁、不能提交（别人可能被决定中止）、也不能中止（别人可能已提交），直到协调者恢复为止。整个系统被阻塞。 - 若协调者在做出决定之后、通知所有参与者之前崩溃 ⇒ 已收到决定的参与者照常执行，未收到的卡在
IN_DOUBT；协调者恢复后必须重发决定（因此决定必须持久化到日志）。 - 这就是 2PC 最著名的缺陷：2PC 是阻塞协议（blocking protocol）。
- 若协调者在发送
- 机制图解（阻塞的现场与传播）：
C RM1 RM2 RM3
│ │ │ │
├─────PREPARE──────►
├───────────────PREPARE───────────────►
├────────────────────────PREPARE─────────────────────────►
│ │ │ │
◄───VOTE_COMMIT────┤
◄─────────────VOTE_COMMIT─────────────┤
◄──────────────────────VOTE_COMMIT───────────────────────┤
│ │ │ │
④ 三个 RM 都投了 YES，进入 IN_DOUBT（不确定状态），继续持有锁
✖ ★★★ 协调者在写决定之前崩溃：没有人知道该提交还是该中止 ★★★
RM1: state=IN_DOUBT 锁{A,B,C} 被占用 → 事务 T2/T3 申请这些锁 ⇒ 阻塞
RM2: state=IN_DOUBT 锁{A,B,C} 被占用 → 事务 T2/T3 申请这些锁 ⇒ 阻塞
RM3: state=IN_DOUBT 锁{A,B,C} 被占用 → 事务 T2/T3 申请这些锁 ⇒ 阻塞
T2 ──等待──► RM1(A) ◄──等待── T3 T4 ──等待──► RM2(B) ...
级联：T2/T3/T4 都卡住 → 它们持有的其他对象也卡住 → 阻塞沿依赖链传播
所有 RM 只能无限期等待（不能提交：别人可能已中止；不能中止：别人可能已提交）
=== 协调者恢复（从 WAL 读出“全部 YES 已落盘、无决定”），重发决定后 ===
├──GLOBAL_COMMIT───►
├────────────GLOBAL_COMMIT────────────►
├─────────────────────GLOBAL_COMMIT──────────────────────►
│ │ │ │
⑥ RM 们终于提交、释放锁 → T2/T3/T4 才被唤醒（阻塞时长 = 协调者停机时长）
- 为什么阻塞是严重问题：
- 锁被长期持有 ⇒ 其他事务申请这些对象时被阻塞 ⇒ 级联阻塞（被阻塞的事务又持有别的锁）⇒ 系统的可用并发度迅速归零；
- 阻塞时长 = 协调者停机时长，这可能是几分钟、几小时（等运维介入），甚至是永久（协调者所在磁盘损坏且日志未备份）；
- 于是产生了”长事务/跨分区事务是危险的“这条工程共识：很多系统（早期 HBase、Cassandra、MongoDB 4.0 之前）干脆不支持跨分区事务，用”同分区事务 + 应用层补偿”绕开 2PC。
- 2PC 在协调者各崩溃点的行为（必须记住的表）：
PREPARE 发出 投票收齐 决定写入 WAL 决定送达完毕
───────┬───────────────────┬─────────────────────┬─────────────────────┬─────► 时间
┬ ┬ ┬ ┬
崩溃点① 崩溃点② 崩溃点③ 崩溃点④
未进入协议 已有人投 YES 决定已定但没发完 协议已走完
恢复后直接 未投票者按 NO 未收到者继续等待 无需恢复
ABORT ⇒ 全体 ABORT ⇒ 最长阻塞窗口 只需清理日志
（无影响） （可提前终止） （= coordinator 停机时长）
| 崩溃点 | 谁崩溃 | 参与者状态 | 是否阻塞 | 恢复后如何决定 |
|---|---|---|---|---|
① 发 PREPARE 之前 | 协调者 | 未进入协议 | 否 | 重新开始或直接 abort（无影响） |
| ② 投票进行中 | 协调者 | 部分已投 yes ⇒ IN_DOUBT | 是（已投 yes 者阻塞） | 日志无完整 yes 集合 ⇒ abort；重发决定 |
| ③ 收齐投票、决定未落盘 | 协调者 | 全部 IN_DOUBT、持锁 | 是（最经典、最长窗口） | 可安全 abort（presumed abort），也可在有完整 yes 记录时 commit；两种情况都必须重发决定 |
| ④ 决定已落盘、发送中 | 协调者 | 部分知道、部分 IN_DOUBT | 是（短窗口） | 日志中已有决定 ⇒ 重发决定（绝不可改） |
| ⑤ 决定已全部送达 | 协调者 | 全部已决定 | 否 | 只需清理日志，参与者自行完成 |
⑥ 收到 PREPARE 前 | 参与者 | 其余正常 | 否 | 超时 ⇒ 视为 no ⇒ 全局 abort；它恢复后无记录 ⇒ 无操作 |
| ⑦ 投出 yes 之后 | 参与者 | 它自己 IN_DOUBT | 否（由协调者超时兜底） | 读日志：有决定则跟随；无决定则询问协调者（不可自行提交） |
| ⑧ 收到决定之后 | 参与者 | — | 否 | 从日志重放决定，补发 ACK |
20.2.13 2PC 的优化（工程实现里必须有）
- 假定中止（presumed abort）：优化中止路径。参与者若处于
IN_DOUBT而联系不上协调者，可以假定全局决定是 abort 并释放锁（同时保留记录以便日后对账）；协调者若恢复后发现日志里没有 COMMIT 记录，也直接按 abort 处理。理由是：未记录决定 = 还没有人被告知 commit，中止不会违反原子性。这能显著缩短阻塞窗口，也是很多教科书实现的默认策略（代价：需要额外的”读未决事务状态”查询机制）。 - 假定提交（presumed commit）：对称优化，适用于”提交是常态、中止是例外”的负载。它需要协调者在开始阶段就写入一条”意图提交”记录，并在恢复时把”无决定”当作 commit。工程上较少用，因为它会让”未曾真正开始提交”的事务也变成提交，需要额外的清理协议。
- 只读优化（read-only optimization）：若某参与者在事务中只读（没有产生任何要提交的更新），它可以在投票时回复
READ_ONLY并立即释放锁，此后不必等待决定（因为它的本地状态无需回滚或提交）。这是实践中最重要的优化之一：真实负载中读操作占多数，只读参与者不再进入IN_DOUBT，既减少了阻塞面，也省掉了协调者等待它的时间。注意：协调者必须在参与者集合中把它记为”已投票 yes 但无需通知”。 - 单阶段提交（one-phase commit）：若事务只涉及一个参与者，直接跳过投票，把”PREPARE + COMMIT”合并成一次提交（省掉 1 个 RTT）。
- 本地优化（coordinator 同时是参与者）：若协调者自己也是参与者（很常见，事务发起站点通常也持有数据），它对自己的本地分支不做网络往返，直接在本地执行并记录，省掉 2 条消息与 1 个 RTT（这是 Spanner/Percolator 里”协调者分片”的成本优势）。
- 并行发送与流水线：阶段 1 的
PREPARE必须并行发给所有参与者（不能串行），阶段 2 的决定广播同理；在允许的场合可以让PREPARE与事务的最后一个数据操作合并传输（piggyback），把 2PC 的额外开销从”2 个 RTT”压到”1 个 RTT + 少量字节”。 - 超时与重传策略：所有消息都要能安全重传（协议本身幂等：重复的
PREPARE重发上次的投票，重复的决定重发 ACK），因此工程上用”至少一次 + 应用层去重”实现可靠传输。
20.2.14 三阶段提交（3PC）：用非阻塞换取一致性
- 定义与目的：三阶段提交（Three-Phase Commit, 3PC） 在 2PC 的”投票”与”决定”之间插入一个预提交（pre-commit） 阶段，使协议在无网络分区且故障数有限的假设下成为非阻塞（non-blocking） 协议。三个阶段：
CanCommit（投票阶段）：协调者问”你们能不能提交”，参与者回答 yes/no（回到can_commit状态）；PreCommit（预提交阶段）：所有人 yes 时，协调者发PRE_COMMIT，参与者进入PRECOMMITTED（此时它知道协调者已收到全体 yes）；DoCommit（提交阶段）：协调者发DO_COMMIT，参与者真正提交。
- 非阻塞的关键设计：
- (a) 参与者的中间状态
can_commit（本笔记记作WAIT_PRE）与PRECOMMITTED是不同的：处于PRECOMMITTED的参与者已经知道所有人都投了 yes，因此在超时后可以安全地自主提交； - (b) 超时自主决定：
PRECOMMITTED状态下超时 ⇒ 提交；CanCommit之后超时 ⇒ 不能直接提交，必须先运行 - (c) 终止协议（termination protocol）：处于
WAIT_PRE的参与者向其他所有节点（包括协调者）询问当前状态：若发现任何节点处于PRECOMMITTED/COMMITTED，则它必须提交（否则就会与已提交者分歧）；若所有可达节点都在WAIT_PRE，则中止；若询问不到任何节点（分区），它面临两难——这正是 3PC 的软肋。
- (a) 参与者的中间状态
- 代价（必须明确讲出这两条）：
- 代价 1：多一个 RTT。延迟从 2 个 RTT 涨到 3 个 RTT，且多一轮 fsync。
- 代价 2：在网络分区下，3PC 可能违反原子性！ 论证直觉：
WAIT_PRE的参与者无法区分”没有任何人收到PRE_COMMIT“与”有人收到了PRE_COMMIT只是我与它被分区隔开”。若它选择中止，而分区另一侧的节点已经提交，原子性就被破坏。3PC 的非阻塞性是”无分区 + 有界故障”假设下才成立的；用 FLP 的语言说，它把不可能性从”活性”搬到了”安全性”上——它用原子性换取了非阻塞性。
结论：3PC 在实践中很少使用，原因是 (a) 多一个 RTT 的延迟成本；(b) 分区下仍不安全；(c) 现代方案（共识驱动的原子提交）在延迟与安全性两方面都更好。
- 机制图解（3PC 三阶段 + 分区下的原子性违反反例）：
C RM1 RM2 RM3
│ │ │ │
├────CAN_COMMIT────►
├─────────────CAN_COMMIT──────────────►
├───────────────────────CAN_COMMIT───────────────────────►
│ │ │ │
◄───VOTE_COMMIT────┤
◄─────────────VOTE_COMMIT─────────────┤
◄──────────────────────VOTE_COMMIT───────────────────────┤
│ │ │ │
阶段 2：预提交（PreCommit）—— 这是 2PC 没有的那一个阶段
├────PRE_COMMIT────► ◄── 只有 RM1 收到（网络分区已生效）
✂ ✂ ✂ 网络分区：{C,RM1} | {RM2,RM3} ✂ ✂ ✂
│ │ │ │
├────DO_COMMIT─────► ◄── RM1 提交，数据生效
│ │ │ │
RM2/RM3：在 WAIT（已投 YES、未收到 PRE_COMMIT）超时
→ 启动 termination protocol：向 C、RM1 询问状态
→ 分区切断一切链路 ⇒ 收不到任何答复，也没看到任何 PRECOMMITTED
→ 按 3PC 规则“自主决定 ABORT”
│ │ │ │
✖ 结果：RM1 = COMMIT，RM2 = ABORT，RM3 = ABORT ⇒ ★ 原子性被违反 ★
20.2.15 共识驱动的原子提交：Spanner 式”Raft 分片 + 2PC 跨分片”
- 核心思想：2PC 阻塞的根因不是”两阶段”这个形状，而是协调者是单点且不复制。那就把协调者的状态复制起来：
- 每个分片（shard/range）内部用 Paxos/Raft 复制 ⇒ 分片自己的数据与”是否已准备”状态都抗故障；
- 跨分片事务仍用 2PC ⇒ 保留原子提交语义；
- 2PC 的协调者状态（决定）也通过共识复制 ⇒ 协调者 leader 崩溃后，新 leader 从多数派日志中恢复决定并继续广播。
- 结果：阻塞窗口从”协调者恢复时间”（可能是几小时）缩短为”多数派选主时间”（几十到几百毫秒）。
- 机制图解：
+--------+
| Client |
+--------+
| ① 提交事务 T
v
+------------------------------------+
分片内部：Raft / Paxos 复制 | 分片 S0：2PC 协调者 (Raft 组) |
分片之间：2PC 原子提交 | leader C0 + followers C1, C2 |
协调者状态也被复制 => | 决定写入多数派日志（多数派持久化） |
+------------------------------------+
| ② PREPARE → 各分片写入自己的 Raft 日志；③ 投票
+-----------------------+-----------------------+-----------------------+
| | |
v v v
+-------------------+ +-------------------+ +-------------------+
| 分片 S1 (Raft 组) | | 分片 S2 (Raft 组) | | 分片 S3 (Raft 组) |
| L1 + F1a + F1b | | L2 + F2a + F2b | | L3 + F3a + F3b |
| 对象 A, B | | 对象 Y, Z | | 对象 M, N |
+-------------------+ +-------------------+ +-------------------+
① 客户端提交 T；③ 各分片把票与本地更新一起写入自己的 Raft 日志（多数派持久化后才算“已准备”）
④ 协调者把 <T, COMMIT/ABORT> 写入 S0 的 Raft 日志 => C0 崩溃后新 leader 从日志恢复并继续广播
⑤ 阻塞窗口 = 一次选举超时（几十~几百 ms），而不是“等人来修机器”（可能几小时）
- 讲义对”用 Paxos 做原子提交”的原始表述：讲义在”Using Paxos in Distributed Servers”一页给出两条用法：
- 原子提交：”Can instead use Paxos to decide whether to commit a transaction or not. But need to ensure that if any server votes No, everyone aborts“。这一句是关键：Paxos 只保证”多数派达成一致”，而原子提交要求的是”一票否决“（所有参与者都同意才能提交）。因此不能简单地”用 Paxos 投票多数派决定提交”——必须把”是否出现过反对票”编码进共识的提案里（例如协调者只有在收到全员 yes 后才提出 COMMIT 提案，否则提出 ABORT 提案）。
- 给更新排序：”Paxos can also be used by a replica group (for an object) to order all updates — iteratively do: Server proposes message for next sequence number; Group reaches consensus (or not)”。这正是复制状态机 + 共识的组合：Paxos 每一轮为一个序号选出一条更新，所有副本按序号回放 ⇒ 全序多播的实现（对应 Lecture 16 的 total ordering 与 Lecture 17 的 Raft 日志）。
- 2PC 与共识的对比（Must know）：
| 维度 | 2PC（原子提交） | 共识（Paxos/Raft） |
|---|---|---|
| 解决的问题 | 跨多个分片的事务原子提交 | 在部分故障下让一组进程对一个值达成一致 |
| 决策规则 | 全体一致（unanimous）：全部 yes 才提交；任何一个 no 就中止（一票否决） | 多数派（majority/quorum）：> N/2 即可决定 |
| 决策者的容错 | 协调者是单点，不复制 ⇒ 协调者故障 ⇒ 阻塞 | leader 故障 ⇒ 重新选举，不阻塞（少数派故障无影响） |
| 故障下性质 | 保证安全性（原子性），可能丧失活性 | 保证安全性，最终活性（FLP 允许不终止） |
| 延迟（无故障） | 2 RTT + fsync | 1~2 RTT（一轮共识），或 2 阶段（Paxos 的 prepare/accept） |
| 决策需要谁同意 | 所有人 | 多数派 |
| 通讯代价 | $O(N)$ 消息给 $N$ 个参与分片 | $O(N)$ 消息给 $N$ 个副本（但可批量/流水线） |
- 为什么 2PC 不能容忍协调者故障，而共识可以？ 一句话：因为 2PC 的协调者没有被复制。协调者一倒，”哪些投票已收到、决定了什么”就只有它自己知道；而共识把状态放在多数派上，任何时刻至少有一个存活的多数派成员知道答案，因此新 leader 可以接管。把 2PC 的协调者复制起来（用 Raft/Paxos），就得到了现代分布式数据库的标准架构。
- 一个重要洞见（本讲的理论高点）：在异步、允许故障的系统中，非阻塞的原子提交与共识具有相同的不可能性。直觉论证：若一个原子提交协议既保证一致性又保证非阻塞，那么它必须在协调者崩溃后仍能由参与者们自行确定唯一的全局结论——这等价于让参与者们在异步系统中达成共识，而 FLP 告诉我们这不可能（Lecture 15/17）。推论：想让原子提交非阻塞，就必须引入共识（即：要么假设部分同步 + 超时，要么用多数派复制），这就是现代系统”用共识实现原子提交”的必然性。
20.2.16 复制的一致性模型、租约、Quorum 与 RPO/RTO
- 一致性模型的选择（连接 Lecture 10）：同一个复制系统可以在不同操作上提供不同强度的一致性：
- 线性一致（Linearizable）：所有操作看起来在某个全局时间点上原子生效，且与真实时间顺序一致。被动复制的同步模式、Raft 的读（ReadIndex/lease read）都属此类。
- 顺序一致（Sequential）：存在一个全局顺序，所有进程观察到的顺序一致，但不要求与真实时间同步。
- 因果一致（Causal）：只保证因果相关的操作顺序（Lecture 16 的 causal multicast 正好提供这个）。
- 最终一致（Eventual）：停止写入后副本最终收敛（Cassandra 的默认模型，Lecture 9）。 选择准则：一致性越强，代价越高（延迟、可用性）。实践做法是按操作分级——强一致用于金额、库存；最终一致用于计数、点赞、日志。
- 租约（Lease）：为了在不做全序多播的前提下保证”同一时刻只有一个写者”，可以让 primary 持有一个租约：在租约有效期内它是唯一合法的写者，其他副本不得接受写；租约到期必须重新申请（通常要多数派同意）。
- 租约的价值：读操作可以在 primary 上安全地进行本地读（无需共识），显著降低读延迟（Spanner 的 leader lease、GFS 的 master lease 都是这个思路）。
- 代价与陷阱：租约的正确性依赖时钟同步的上界（Lecture 11：物理时钟有漂移，NTP 只能保证有限偏差）。所以租约时长必须远大于最大时钟偏差，并且租约的续约必须由多数派批准，否则两个节点可能在同一时刻都认为自己的租约有效。
- Quorum 复制（复习并扩展，连接 Lecture 9）：设 $N$ 个副本，读 quorum 大小 $R$，写 quorum 大小 $W$，则强一致的两个必要条件是： \(W+R>N \quad\text{（读写 quorum 必有交集）}\qquad W>N/2 \quad\text{（避免两个写 quorum 不相交）}\) 论证：任意两个大小之和大于 $N$ 的集合必有公共元素（鸽笼原理），因此读 quorum 中至少有一个副本见过最近一次写 quorum 的写入，返回其中时间戳最新的值即可（Lecture 9 的详细论证）。常见取值：$(W=1,R=1)$ 追求最低延迟；$(W=N,R=1)$ 适合读多写少；$(W=\lceil N/2\rceil,R=\lceil N/2\rceil)$ 是读写均衡的通用选择。
- sloppy quorum + hinted handoff：当某个”正式副本”宕机时，写请求改投环上的下一个健康节点（sloppy quorum：临时放宽成员要求），并保存一条 hint；该副本恢复后把 hint 交还（hinted handoff）。这提升了写可用性（R4 宕机也能写成功），代价是读一致性被削弱——因为写可能落在”非正式副本”上，$W+R>N$ 的交叉保证不再严格成立。
- 机制图解：
N = 5 个副本；写 quorum W = 2：正常写前两个正式副本
+--------+ +--------+ +--------+ +--------+ +--------+
| R1 | | R2 | | R3 | | R4 X | | R5 |
+---+----+ +---+----+ +--------+ +--------+ +---+----+
| | |
| | ① R4 宕机, 写<key,value>改投 R5 |
+--------------+--------------------------------------------+
并保存 hint: <key, value, 目标=R4>
① R4 宕机 => 环上下一个健康节点 R5 代理接收写，并保存 hint（sloppy quorum）
② R4 恢复 => R5 把 hint 交还给它（hinted handoff），数据回到正式副本
③ 代价：写在 R5 上“成功”了，但 R5 不是正式副本 => 读可能读不到，R+W>N 的保证被削弱
复制因子（Replication Factor）与容错能力： | 目标 | 需要的副本数 | 说明 | |—|—|—| | 数据存活（不丢，容忍 $f$ 个故障） | $f+1$ | 单纯多副本，无一致性投票需求（如 HDFS 3 副本容忍 2 个 DataNode 故障） | | 多数派协商（选主、共识、$W>N/2$） | $2f+1$ | 需要任意两个多数派相交，这是 Paxos/Raft/Cassandra quorum 的要求 | | 拜占庭容错（容忍 $f$ 个作恶节点） | $3f+1$ | 详见 Lecture 15（BFT 部分） |
- RPO / RTO 术语与各方案的实际取值：
- RPO（Recovery Point Objective，恢复点目标）：故障发生时最多能丢多少数据（通常以时间或更新条数衡量）。
- RTO（Recovery Time Objective，恢复时间目标）：从故障发生到服务恢复需要多久。
方案 RPO（丢数据） RTO（恢复时间） 说明 同步复制（等全部副本） 0 秒级（FD + 选主 + FE 重定向） 延迟高；一个副本慢就拖累写 半同步 / 多数派（Raft、Cassandra QUORUM） 0（已确认的写） 几十 ms ~ 秒（选举超时） 是目前主流的折中；少数派故障不影响 异步复制（MySQL 异步主从、Redis） > 0（未传播的更新全丢） 秒级 ~ 分钟级（可能需人工介入） 延迟最低；故障时可能出现”客户端见过但不存在”的数据 Cassandra ANY+ hinted handoff通常 0（写被暂存） 秒级 hint 所在节点若也故障则会丢 GFS/HDFS（单 NameNode 时代） 0（数据）/ 元数据可能丢 分钟 ~ 小时级（NameNode 重启 + 回放日志） 元数据单点是经典 RTO 痛点，HA 后改善 2PC + Raft 复制的协调者（Spanner/CockroachDB） 0 100 ms 级（选举超时） 本章推荐的现代方案 - 地理复制的延迟现实：跨洲一次往返（RTT）通常在 100~200 ms 量级（同城 1 ms、同区域 10 ms、跨大西洋 80~100 ms、跨太平洋 150~250 ms）。这意味着：
- 同步跨洲复制的写延迟至少 2 个 RTT（票 + 决定）⇒ 200~400 ms 起步，用户体验不可接受；
- 因此跨洲部署普遍采用：分片本地多数派 + 跨地域异步复制 + 本地读优化（Cassandra 的
LOCAL_QUORUM、Spanner 的 region 内部 Paxos + 跨 region 的复制副本），把强一致的写限制在同一地域内部。
20.2.17 真实分布式数据库：复制与 2PC 如何结合
- 为什么两者都要（不能只用一个）：
- 只有复制（例如每个分片做 3 副本）⇒ 单个分片内部不会丢数据、不会停机，但跨分片事务没有原子性：事务在分片 A 提交、在分片 B 失败，就会出现”钱扣了但没到账”。
- 只有 2PC（每个分片单副本）⇒ 有原子性，但任何一个分片或协调者宕机就阻塞（20.3.4(B)），而且单副本意味着丢数据（RPO > 0）。
- 两者结合 ⇒ 分片内部靠复制获得容错与可用性，跨分片靠 2PC 获得原子性，协调者的单点问题再靠共识复制消除。这就是当代分布式数据库的标准架构。
- 组合方式（三层配方）：
- 分片内部：Paxos/Raft 复制（每个分片是一个共识组，$2f+1$ 副本，容忍 $f$ 个故障）；
- 跨分片：2PC（每个分片投一票，全员 yes 才提交）；
- 协调者：也用共识复制（把”决定”写进某个分片的共识日志）⇒ 协调者 leader 崩溃只造成一次选举窗口的停顿，而不是永久阻塞。
真实系统逐一说明：
系统 分片内复制 跨分片原子提交 时间/时钟机制 关键特点 Google Spanner 每个 split 一个 Paxos 组（含 leader lease） 跨 Paxos 组用 2PC（论文里称 “2PC over Paxos”） TrueTime：GPS + 原子钟提供有界不确定性 $\epsilon$，提交时间戳取 $\text{now} \pm \epsilon$ 并等待 $\epsilon$ 提供外部一致性（external consistency）：事务的提交顺序与真实时间一致，可实现全球一致的快照读（”读到的数据不晚于某时刻”） CockroachDB / TiDB 每个 range/region 一个 Raft 组 跨 range 用 2PC（Percolator 风格的 primary lock + 提交时间戳） HLC（混合逻辑时钟）：物理时间 + 逻辑计数，避免依赖专用硬件 用 HLC 近似 TrueTime 的效果，代价是”有界陈旧”或提交等待；MVCC + 时间戳排序提供快照隔离 MongoDB 副本集（Replica Set）内使用 Raft 风格的 pv1 协议选主与复制 4.2 起支持跨分片事务，采用 2PC 思路（coordinator + 参与者 + 决定记录） 逻辑时钟/操作时间（clusterTime） 从”不支持跨分片事务”演进到”支持但不鼓励长事务”，反映了 2PC 成本的真实约束 MySQL XA / Oracle 主从半同步 / Data Guard 等 经典 XA 两阶段提交（ XA START/END/PREPARE/COMMIT），由外部事务管理器充当协调者不依赖特殊时钟 最”原生”的 2PC 实现；协调者通常是应用服务器/中间件，是明确的单点，实践中常因 XA PREPARE后协调者挂掉而出现”悬挂事务”PostgreSQL 流复制（同步/异步，见 synchronous_standby_names）PREPARE TRANSACTION 'T1'→COMMIT PREPARED 'T1'/ROLLBACK PREPARED（需max_prepared_transactions > 0）无 把 2PC 暴露为 SQL 接口；文档明确警告：不要长时间让事务停留在 prepared 状态，因为它会阻塞 vacuum 并持有资源 Google Percolator / TiKV 事务层 底层用 BigTable/TiKV（+Raft） 2PC + 全局时间戳：先在 primary key 上写锁，再写第二阶段的提交记录 时间戳服务（TSO） 展示了”2PC 与 MVCC/快照隔离”如何共存；大量工业系统沿用了它的两阶段提交结构 - 为什么把协调者复制起来就”消除”了阻塞（把 20.3.4(B) 的证明条件补回来）：20.3.4(B) 的阻塞性证明依赖”协调者状态只存在于一个不复制的位置”。一旦把决定与准备状态写入多数派日志：
- 决定的存在性不再依赖单个节点 ⇒ 协调者 leader 崩溃后新 leader 能读出决定并继续（而不是无从判断）；
- 参与者分片的”我已投 YES”也在多数派日志里 ⇒ 该分片 leader 崩溃不会丢掉这个承诺；
- 因此参与者等待的时间上界从”协调者恢复时间”变成”一次选举超时“（Raft 通常 150~300 ms，Spanner 的 leader lease 更长但故障切换仍在秒级内）。阻塞没有消失，而是被压缩成了一个有界的、可接受的窗口。
- 2PC 与共识的关系：一句话概括——2PC 表达”一票否决”的语义，共识提供”少数派故障下仍能确定决定”的能力；二者互补而非替代（完整对比表见 20.2.15）。2PC 的阻塞源于协调者单点，而共识恰恰擅长消除单点，因此现代架构是”用共识复制 2PC 的协调者”，而不是”用共识取代 2PC”。
20.3 算法伪代码与正确性分析
算法 20.3.1：被动复制（Primary-Backup Replication）
假设与系统模型
- 进程：1 个 primary $P$，$k$ 个 backup $B_1..B_k$，若干 FE，1 个配置服务（由多数派复制，如 ZooKeeper/etcd）。
- 故障模型：崩溃-恢复（crash-recovery），非拜占庭；进程有稳定存储（WAL + 快照）。
- 通道：fair-loss（可丢失/重复/乱序，重传最终送达）；去重必须由应用层做。
- 故障检测器不可靠（可能出现误判），因此任何”唯一写者”的保证都必须由epoch/fencing在存储侧强制执行。
- 副本数 $k+1$；同步模式要求全部 backup 确认（可配置为多数派）。
伪代码
# ============ Primary P ============
init:
lsn := 0 # 本地更新序号（单调递增）
dedup := {} # rid -> 已产生的应答（去重表，持久化）
ulog := <> # 更新历史，供 backup 追赶
backups := {B1 .. Bk}
epoch := 从配置服务获得（每次选主 +1）
upon request(req = <rid, op>) from FE:
if rid in dedup: # ① 去重：重复请求不重新执行
send Reply(rid, dedup[rid]) to FE ; return
(result, delta) := execute(op) # ② 执行（或先写 WAL 再执行）
lsn := lsn + 1 # ③ 生成新版本
append <lsn, delta> to ulog (persist) # ④ 更新历史落盘
dedup[rid] := result ; persist dedup
if mode = SYNC:
for each B in backups: send Xfer(epoch, lsn, delta) to B
wait until (all backups acked lsn) or timeout # ⑤ 同步：等确认
if timeout: mark that backup STALE ; 若剩余确认数 < quorum:
abort 本次写并回滚 delta（宁可不可用，不可不一致）
else: # 异步
enqueue Xfer(epoch, lsn, delta) to replicateQueue # 后台线程发送
send Reply(rid, result) to FE
upon recover(): # primary 重启后
reload lsn, dedup, ulog from stable storage
以 backup 身份向配置服务注册（★ 绝不自称 primary，除非配置服务选它）
从当前 primary 请求 from = lsn+1 起的更新（catch-up）
# ============ Backup Bi ============
init: lastLSN := 0 ; state := S0 ; buffer := {}
upon receive Xfer(e, lsn, delta) from P:
if e < myEpoch: discard ; return # fencing：过期主
if lsn = lastLSN + 1:
apply(delta) ; lastLSN := lsn ; persist
deliver buffered updates whose gap is now filled # 缓存乱序到达者
send Ack(lsn) to P
elif lsn <= lastLSN: send Ack(lsn) to P # 重复，忽略
else: buffer[lsn] := delta ; send Nack(lastLSN) to P # 有缺口 ⇒ 触发追赶
upon recover():
load state, lastLSN from stable storage
send QueryUpdates(from := lastLSN + 1) to current primary
apply the returned updates / snapshot
# ============ 配置服务 / 故障切换（由 FD + 多数派完成）============
upon FD suspects P is dead (心跳超时):
ask every backup for its lastLSN
candidate := argmax over backups of (lastLSN, term, nodeID) # 定序必须确定
epoch := epoch + 1
以多数派写入配置：primary := candidate, epoch := epoch # ★ 必须多数派确认
把 epoch 作为 fencing token 发给 candidate（candidate 用它写存储）
通知所有 FE（FE 重新拉取配置）
# ============ FE ============
upon sending request:
rid := 全局唯一 ID ; primaryAddr := readConfig() ; send(req) to primaryAddr
若超时：重发同一条请求（同一 rid）到 primaryAddr（重新读配置）
算法逻辑解说（用一个具体例子走一遍）
- 客户端要”转账 88 元”，FE 生成
rid=88，读配置得知 primary 是 RM1，发出请求。 - RM1 查
dedup：88 ∉ dedup⇒ 执行操作，lsn: 104 → 105，把<105, delta>追加到ulog并 fsync。 - 同步模式：RM1 向 RM2、RM3 发
Xfer(epoch=1, 105, delta)。RM2 的lastLSN=104⇒105 = 104+1⇒ 应用并回Ack(105)；RM3 因网络抖动晚到 ⇒ RM1 在超时前收到两个 ack ⇒ 回Reply给 FE。若 RM3 在超时内始终不回，则标记 RM3 为STALE（后续让它追赶），但只要剩余确认数仍满足 quorum 就继续服务（同步”全部”模式下则拒绝本次写）。 - FE 若因为
Reply丢失而重发rid=88，RM1 发现88 ∈ dedup⇒ 直接返回缓存结果，不重复扣款。 - 现在 RM1 崩溃。FD 超时 ⇒ 配置服务询问
RM2.lastLSN=105、RM3.lastLSN=104⇒ RM2 晋升，epoch: 1 → 2⇒ FE 从配置服务读到新地址并重定向。RM3 向 RM2 请求from=105的更新完成追赶。 - RM1 若”复活”，它带的是
epoch=1；存储层的fence_epoch=2⇒ 它的所有写被拒绝，并被迫降级为 backup。
正确性论证
- 安全性 1（单拷贝可串行化）：所有更新都由 primary 串行地产生并赋予互不相同的 LSN；backup 只在
lsn = lastLSN+1时应用（缓存乱序到达者保证按 LSN 顺序应用），因此每个副本的状态都是同一个操作的同一个前缀。设客户端观察到的操作顺序为 primary 产生的顺序 $\sigma$，则任一时刻任一副本的状态 = 在 $\sigma$ 上执行前 $L$ 个操作的结果（$L$ 为该副本的lastLSN）。所有副本看到的是同一个逻辑副本的某个前缀 ⇒ 事务效果等价于在单副本上串行执行 ⇒ 单拷贝可串行化。 - 安全性 2（重复请求至多生效一次）：
dedup表以rid为主键，且在执行前检查、执行后与结果一起持久化。因为rid全局唯一，任何重传的相同请求都会被识别；关键在于dedup与状态更新必须在同一持久化边界内提交（否则崩溃恢复后去重表与状态不一致，会重复执行）。因此有效语义是 at-most-once（对每个rid）。 - 安全性 3（故障切换不产生分歧）：新 primary 必须在配置服务里以多数派方式注册后才能服务。设旧 primary 仍在服务，它的写带着旧
epoch；存储侧fence_epoch已提升 ⇒ 旧主的写被拒绝（fencing）。因此任意时刻至多一个 epoch 的写能生效 ⇒ 不会出现两个主各写一份造成永久分歧。（注意：这套论证依赖”存储/仲裁方强制执行 epoch”，而不是依赖旧主”自觉退出”。） - 活性（Liveness）：若故障检测最终能发现 primary 故障（部分同步假设），且至少有一个 backup 存活、配置服务可达（多数派存活），则故障切换在 $O(\text{FD 超时} + 1\ \text{轮配置写入})$ 内完成；catch-up 的时间取决于缺失更新量（有快照时是 $O(\text{快照大小} + \text{增量})$）。
- 可量化的一致性缺口（必须诚实指出的部分）：异步模式下，已被 primary 确认给客户端、但尚未到达任何 backup 的更新，在切换后不存在于系统中 ⇒ 违反”已确认的写不会消失”（durability），RPO > 0。这不是实现 bug，而是异步复制的定义性代价；要消除它只能改用同步/半同步（等至少多数派确认）。
复杂度
- 消息：同步模式每次写 $O(k)$（$k$ 条
Xfer+ $k$ 条Ack），异步模式 $\Theta(1)$ 条（对 FE）加后台 $O(k)$。 - 延迟：同步 = $\max_i(\text{RTT}_i) + \text{fsync}$；异步 = 本地 fsync 时间。
- 空间：
dedup表 $O(\text{在途请求数})$（需按超时窗口过期）、ulog$O(\text{未追赶量})$（需快照后截断）。
算法 20.3.2：2PC 协调者的完整状态机
假设与系统模型
- 1 个协调者 $C$，$N$ 个参与者 $P_1..P_N$；崩溃-恢复故障模型；可靠稳定存储；通道可丢失（靠超时 + 重传）。
- 协调者不复制（这是后面阻塞性的根源）；协议要求幂等：重复消息必须能被安全处理。
伪代码
# 状态: INIT -> WAIT -> DECIDED -> DONE
init: state := INIT ; votes := {} ; decision := ⊥ ; acks := {} ; log := <>
upon client says commit(T):
append <T, START> to log ; fsync # 崩溃后能知道"曾开始"
state := WAIT
for each P in participants: send PREPARE(T) to P # 并行广播（不许串行）
startTimer(T, τ) # τ = 超时阈值
upon receive VOTE(T, v) from P: # v ∈ {YES, NO, READ_ONLY}
votes[P] := v
if v = NO:
decide(T, ABORT) # 一票否决：立即决定，可提前终止
elif all participants have voted:
decide(T, COMMIT if all(v = YES or v = READ_ONLY) else ABORT)
upon timer τ expires: # 悲观处理
for each P not in votes: votes[P] := NO # 未投票 ⇒ 视为 NO
decide(T, COMMIT if all(v = YES or v = READ_ONLY) else ABORT)
decide(T, d):
if decision ≠ ⊥: return # 幂等：决定只做一次
decision := d
append <T, DECISION, d> to log ; fsync # ★★ 决定点（point of no return）
state := DECIDED
for each P: send GLOBAL_d(T) to P # 只通知"投了 yes 而非 READ_ONLY"的 P
startTimer(T, τ2)
upon receive ACK(T) from P:
acks := acks ∪ {P}
if acks ⊇ {P : votes[P] = YES}: # READ_ONLY 者无需 ACK
append <T, END> to log ; state := DONE
清理日志与临时状态（只有此时才能"忘掉"这个事务）
upon timer τ2 expires:
for each P without ACK: resend GLOBAL_d(T) to P # 重发直到确认或告警
upon receive DECISION_QUERY(T) from P: # 参与者恢复后询问
send DECISION_RESPONSE(T, decision) to P # 若内存已清理，从 log 读出
upon recover():
read log
if exists <T, DECISION, d>: # 决定已定 ⇒ 必须执行
decision := d ; state := DECIDED
重新广播 GLOBAL_d 并收集 ACK
elif exists <T, START> and votes 中已有完整 YES 集合:
decide(T, COMMIT) # 本实现的选择（另一种是 presumed abort）
elif exists <T, START>:
decide(T, ABORT) # presumed abort：没记决定 ⇒ 中止
fsync 后再广播，绝不能在决定上反复
算法逻辑解说
- 无故障路径：
PREPARE并行广播（1 个 RTT）→ 收齐 YES → 写决定日志（1 次 fsync）→ 广播决定（1 个 RTT）→ 收 ACK。总共 2 个 RTT + 2 次 fsync（协调者侧）。 - 提前终止：只要收到一个 NO，协调者立刻决定 ABORT，不必等其他投票——因为全局提交要求全员 YES，一票 NO 已经决定了结局。这是延迟优化，也是安全性上的关键规则：任何 NO ⇒ 必然 ABORT。
- 超时即 NO：这是”悲观”选择，牺牲活性（某个慢节点会拖垮事务）换取简单与安全。
- 决定一旦写入 WAL（
DECIDED），任何情况下都不能改变——包括协调者自身崩溃重启后。恢复逻辑之所以能安全地重发，正是因为有这条落盘记录。
正确性论证
- 安全性（决定唯一）：
decide有幂等保护（if decision ≠ ⊥: return），且决定写入 WAL 后不再变更；恢复时优先采用日志中的DECISION记录。因此对同一个 $T$，全局只会有一个决定值。 - 安全性（提交 ⇒ 全员 YES）：
decide(COMMIT)只在all(v ∈ {YES, READ_ONLY})时被调用，而该条件只能在全員投票（或超时把未投票者记为 NO 之后）成立。因此只要有一个 NO 或一个未投票者，就得到 ABORT。 - 持久性：
START、DECISION、END都 fsync；DECISION落盘先于广播，保证”发出去的决定”一定能被恢复后重发。 - 活性：无故障时在 $\tau$ 与 $\tau_2$ 内终止，即 $2\times\text{RTT} + \text{fsync}$。有故障时可能不终止（下一节证明）。
复杂度
- 消息数：$N$ 条
PREPARE+ 至多 $N$ 条投票 + 至多 $N$ 条决定 + 至多 $N$ 条 ACK $= 2N \sim 4N$，即 $O(N)$；只读优化可把 $N$ 有效地降为”有写操作的分片数”。 - 时间：$2\times\text{RTT} + 2\times\text{fsync}$；空间：日志 $O(N)$ 每事务（可在外层截断）。
算法 20.3.3：2PC 参与者的完整状态机（含 IN_DOUBT）
假设与系统模型：同上；参与者持有本地锁（2PL），并且必须把暂定更新与投票写入持久存储后才允许回复 YES。
伪代码
# 状态: INIT -> IN_DOUBT -> COMMITTED / ABORTED
init: state := INIT ; decision := ⊥ ; locks := {} ; wal := <>
upon receive PREPARE(T) from C:
if state = IN_DOUBT: resend my vote (YES) ; return # 幂等
if state ∈ {COMMITTED, ABORTED}: resend my ACK/决定 ; return
执行 T 的本地部分（写入暂定区，不修改正式状态，不放锁）
acquire locks on T's write set # 2PL：锁持有到最后
ok := checkConstraints(T) # 约束 / 冲突 / 资源
if not ok:
append <T, ABORTED> to wal ; fsync # 未做任何修改
state := ABORTED ; decision := ABORT ; releaseLocks()
send VOTE_ABORT(T) to C ; return
append <T, PREPARED, tentativeUpdates(T)> to wal ; fsync # ★ 落盘点 P1
state := IN_DOUBT ; send VOTE_COMMIT(T) to C
# ★ IN_DOUBT 期间：持有锁；不提交；不回滚；不单方面决定；不暴露未提交数据
upon receive GLOBAL_COMMIT(T) from C:
if decision = ABORT: log "冲突的决定(不应发生)" ; return # 防御性检查
apply tentativeUpdates to state ; append <T, COMMITTED> to wal ; fsync
decision := COMMIT ; state := COMMITTED ; releaseLocks() ; send ACK(T) to C
upon receive GLOBAL_ABORT(T) from C:
discard tentativeUpdates ; append <T, ABORTED> to wal ; fsync
decision := ABORT ; state := ABORTED ; releaseLocks() ; send ACK(T) to C
upon timeout while state = IN_DOUBT: # 2PC：什么也不做
send DECISION_QUERY(T) to C (可周期性重试) # 温和的轮询（教材做法）
continueWaiting() # 绝不单方面提交或中止 —— 见 20.3.4 的证明
upon recover():
read wal
if <T, COMMITTED>: 重放提交、释放锁、重发 ACK
elif <T, ABORTED>: 回滚、释放锁、重发 ACK
elif <T, PREPARED>: state := IN_DOUBT ; 持锁等待/询问 C 的决定 # ★ 不确定状态要恢复出来
else: 无记录 ⇒ 视为未参与该事务
算法逻辑解说
- 参与者有两个落盘点：投 YES 之前（
P1：把暂定更新与PREPARED写盘——这是讲义强调的 “Each server saves tentative updates into permanent storage, right before replying Yes/No in first phase”）与收到决定之后（P2：把 COMMIT/ABORT 写盘）。这两个落盘点是崩溃恢复的全部依据。 IN_DOUBT是协议的核心状态：它不是”等待”这么简单，而是”已经承诺（投了 YES，意味着我保证只要大家同意我就提交）但尚不知道全局结论“。恢复时必须能重建这个状态（所以PREPARED必须落盘），否则参与者可能”忘记自己投过 YES”，从而在别人提交时自己什么都不做 ⇒ 原子性被破坏。- 投 NO 者可立即中止：见 20.2.11 的论证。
正确性论证
- 安全性（一致性/单边不决定）：参与者只在收到
GLOBAL_COMMIT（且自己未投 NO）时提交。由算法 20.3.2，协调者只有在全员 YES 时才发GLOBAL_COMMIT⇒ 收到该消息的参与者一定是投 YES 的 ⇒ 所有投 YES 者都会提交，投 NO 者（若有）不会提交，但那种情况下根本不会有GLOBAL_COMMIT。因此”有人提交 ⇒ 所有人都提交”（uniform agreement）成立。 - 安全性（持久性）：
PREPARED与决定都在 WAL 中；崩溃恢复后可以重建IN_DOUBT/COMMITTED/ABORTED三种状态，不会出现”状态丢失导致的行为不确定”。 - 活性：只要协调者最终可达（或最终恢复），参与者就能在有限时间内收到决定并终止。若协调者永不可达且没有其他机制，则参与者永远停在
IN_DOUBT（这是算法 20.3.4 要证明的）。
复杂度：每条消息 $O(1)$；每个参与者每个事务 2 次 fsync；空间 = 事务的暂定更新大小（在 IN_DOUBT 期间必须保留）。
算法 20.3.4：2PC 的原子性证明、阻塞性证明与终止性分析（分析性论证）
(A) 原子性（Atomicity / Agreement）：所有参与者最终决定相同
要证：任意两次观察到的最终决定不矛盾，即不存在”$P_i$ 提交而 $P_j$ 中止”的执行。
证明. 设 $P_i$ 最终提交。由算法 20.3.3，$P_i$ 提交的唯一途径是收到 GLOBAL_COMMIT。由算法 20.3.2，协调者发出 GLOBAL_COMMIT 的唯一途径是执行了 decide(T, COMMIT)，而 decide(T, COMMIT) 的前置条件是所有参与者的投票都属于 {YES, READ_ONLY}（超时未投票者被记为 NO，因此也排除）。于是：
- 对所有 $P_j$（$j \ne i$），$P_j$ 的投票是 YES 或 READ_ONLY，绝不可能是 NO；
- 因
decide幂等且决定落盘后不可更改，协调者对该事务的最终决定唯一，即 COMMIT； - 参与者 $P_j$ 在投出 YES 后进入
IN_DOUBT，其唯一的退出方式（除崩溃恢复后仍走同一逻辑）是收到协调者的决定；它不会单方面中止（算法中IN_DOUBT超时不做任何决定）； - 由持久性（
DECISION已 fsync，恢复后必被重发，且参与者会主动DECISION_QUERY），$P_j$ 最终收到GLOBAL_COMMIT⇒ 提交。
因此”存在一个提交者” ⇒ “全体提交”。反之，若无人提交，则协调者的决定是 ABORT（或事务未进入决定阶段），所有投 YES 者经 GLOBAL_ABORT（或恢复后的询问）中止 ⇒ 全体中止。两种情况下全体决定相同。∎
故障情形的逐一覆盖（证明必须覆盖这些分支，否则不完整）：
- 参与者崩溃：崩溃前若未投 YES，它不影响决定；崩溃前若已投 YES，其
PREPARED已落盘，恢复后进入IN_DOUBT，随后按权威决定执行——不影响上述推理。 - 协调者崩溃：若崩溃发生在
decide之前，则没有任何参与者可能已提交（因为提交需要GLOBAL_COMMIT，而它尚未发出），恢复后协调者按日志选择一个决定（本实现：全部 YES 已记录 ⇒ COMMIT；否则 ABORT），并广播同一决定 ⇒ 一致。若崩溃发生在decide之后，则日志中已有唯一决定，恢复后必须重发该决定 ⇒ 一致。 - 消息丢失：
PREPARE/投票丢失由”超时视为 NO”处理 ⇒ 决定为 ABORT，一致；决定消息丢失由”重发 + 参与者询问”处理 ⇒ 一致。所有消息处理都是幂等的（重复PREPARE得到同样的投票，重复决定得到同样的 ACK），因此重复投递不破坏一致性。
(B) 阻塞性（Blocking）：2PC 是阻塞协议——一个”不可能性”风格的证明
命题. 在异步系统（消息延迟无上界）与崩溃-恢复模型下，存在 2PC 的一个执行，使某个参与者无限期停留在 IN_DOUBT 并持续持有资源（锁）。
证明（构造 + 反证）. 构造执行 $E$：
- 协调者 $C$ 向 $P_1..P_N$ 发出
PREPARE，所有 $P_i$ 执行本地部分、写PREPARED，回复 YES 并进入IN_DOUBT（持锁）； - $C$ 在写入任何决定之前崩溃，且此后永不恢复（或恢复时间无上界）；
- 没有任何参与者能收到决定消息。
现在证明”任何 $P_i$ 都不能安全地自行决定”：
- 假设 $P_i$ 自行提交。考虑另一个执行 $E^{\prime}$：$C$ 在崩溃前已经
decide(ABORT)（因为某个参与者（不为 $P_i$ 所知）投了 NO），并把GLOBAL_ABORT发给了其他参与者。由于 $C$ 崩溃、消息延迟无上界，$P_i$ 在 $E$ 与 $E^{\prime}$ 中观察到的本地历史完全相同（它收到的消息序列一样），因此它无法区分 $E$ 与 $E^{\prime}$。若它在 $E$ 中提交，则存在某个在 $E^{\prime}$ 中中止的参与者 ⇒ 违反原子性（$E^{\prime}$ 是合法执行）。 - 假设 $P_i$ 自行中止。对称地，考虑执行 $E^{\prime\prime}$：$C$ 已
decide(COMMIT)并把GLOBAL_COMMIT发给了 $P_j$，$P_j$ 已提交；$P_i$ 的消息恰好丢失。$P_i$ 同样无法区分 $E$ 与 $E^{\prime\prime}$，中止会与已提交的 $P_j$ 矛盾。 - 因此 $P_i$ 的唯一安全动作是继续等待（保持
IN_DOUBT、继续持锁）。若 $C$ 永不恢复，该等待是无限期的。
于是 $E$ 中存在无限期阻塞的参与者与无限期被占用的锁；2PC 是阻塞协议。∎
注：这个论证的关键假设是”异步 + 协调者不复制“。破坏任一条即可获得非阻塞性：3PC 加入超时与终止协议（代价：分区下不安全），而共识驱动的方案把协调者复制到多数派上（代价：每决定要多一轮共识）。
(C) 终止性（Termination）
- 无故障：协议在 2 个 RTT（投票 1 个、决定 1 个）加常数次 fsync 内终止；每个参与者恰好经历
INIT → IN_DOUBT → COMMITTED/ABORTED。 - 有故障：不保证终止。终止性依赖”协调者最终可达或最终恢复”这一活性假设（部分同步 + 崩溃恢复）。若协调者永久失效且无备份机制，系统在该事务上永久阻塞。这与 FLP 不可能性是一致的：我们无法在异步系统中同时保证安全性与终止性。
复杂度总结：消息 $O(N)$、时间 $2\,\text{RTT} + \Theta(1)$ 次 fsync、锁持有时间 $\ge 2\,\text{RTT}$（无故障）或无上界（协调者故障）。
算法 20.3.5：三阶段提交（3PC）与非阻塞性
假设与系统模型
- 与 2PC 相同，但额外假设：网络不会永久分区（或分区可被检测），且系统是部分同步的（存在未知但有限的超时上界），故障数有限。
- 这是 3PC 结论成立的前提；脱离它，3PC 的”非阻塞”不成立。
伪代码
# ===== 协调者 C =====
upon commit request:
state := WAIT_VOTES
for each P: send CAN_COMMIT(T) # 阶段 1：投票
wait for all votes (with timeout τ); 超时未投者记为 NO
if any NO or timeout:
send ABORT(T) to all ; return # 中止路径
append <T, PRECOMMIT_INTENT> to log ; fsync # 阶段 2 的落盘
for each P: send PRE_COMMIT(T) # 阶段 2：预提交
wait for all ACK_PRE (with timeout);
若收齐: append <T, COMMIT> to log ; fsync # 阶段 3 的落盘（不可回头点）
for each P: send DO_COMMIT(T)
收 ACK_COMMIT
否则（有 P 未确认 PRE_COMMIT）：重启选举/继续重发（简化：重发 PRE_COMMIT）
# ===== 参与者 P =====
upon CAN_COMMIT(T):
执行本地部分（持锁）; vote := 本地是否可提交
if vote = YES: state := WAIT_PRE ; send VOTE_COMMIT(T)
else: state := ABORTED ; release locks ; send VOTE_ABORT(T)
upon PRE_COMMIT(T):
state := PRECOMMITTED ; persist ; send ACK_PRE(T)
# 此时 P 知道：协调者已收到全体 YES
upon DO_COMMIT(T):
state := COMMITTED ; apply ; release locks ; send ACK_COMMIT(T)
upon timeout while state = WAIT_PRE: # ★ 非阻塞的关键
run TERMINATION_PROTOCOL()
upon timeout while state = PRECOMMITTED: # ★ 关键规则
# 已知全体投过 YES，没有任何参与者可能中止 ⇒ 可以安全提交
state := COMMITTED ; apply ; release locks
TERMINATION_PROTOCOL(): # 询问一圈再决定
send STATE_QUERY to all other nodes (含 C)
collect replies for up to τ_t
if ∃ reply ∈ {PRECOMMITTED, COMMITTED}: state := COMMITTED ; apply # 必须跟随
elif ∃ majority of replies and all ∈ {WAIT_PRE, INIT, ABORTED}: state := ABORTED
else: 无法判定 ⇒ 请求选举新协调者（简化实现：按调用者配置决定，可能 ABORT —— 危险点！）
正确性论证（非阻塞性，在”无分区 + 有限故障”下）
- 状态单调性：参与者的状态沿
INIT → WAIT_PRE → PRECOMMITTED → COMMITTED单调推进（中止是唯一的旁路，且只能从INIT/WAIT_PRE发生）。因此任何”已提交”的参与者，其状态在全体中的最大值；若有人提交，则所有人都至少达到PRECOMMITTED（因为提交者必须先收到DO_COMMIT，而DO_COMMIT只在协调者收到全体ACK_PRE后发出 ⇒ 所有人都进过PRECOMMITTED）。 - 活性（不阻塞）：处于
WAIT_PRE的参与者超时后运行终止协议。由于假设无永久分区，它能在有限时间内与其他人通信：- 若有人已
PRECOMMITTED/COMMITTED⇒ 它跟随提交（与上面的一致性一致）； - 若无人如此 ⇒ 协调者必然尚未发出
PRE_COMMIT（或已中止）⇒ 它中止是安全的（因为没有任何参与者可能已提交）。 - 处于
PRECOMMITTED的参与者超时后直接提交——安全性依据是”收到PRE_COMMIT⇒ 全体投过 YES ⇒ 不可能有参与者被决定中止”。 因此每个参与者在有限时间内做出决定，无人无限期持锁。∎
- 若有人已
- 代价（安全性缺口）：上面的活性论证依赖无分区假设。一旦存在分区，
WAIT_PRE的参与者可能询问不到任何PRECOMMITTED的节点（它们被隔在另一侧），从而错误地中止，而另一侧的节点已经提交 ⇒ 原子性被违反。反例见 20.2.14 的图与 20.4.2 的可运行实验。
复杂度：消息 $O(N)$ 每阶段，共 3 个 RTT（比 2PC 多 1 个 RTT）；空间与 2PC 相同。结论：多 1 个 RTT 且分区下不安全 ⇒ 实践中很少使用。
算法 20.3.6：共识驱动的原子提交（Spanner 式：Raft 复制的协调者 + 跨分片 2PC）
假设与系统模型
- 数据库划分为若干分片（shard / range），每个分片是一个 $2f+1$ 个副本的 Raft 组；分片 leader 处理读写。
- 故障模型：崩溃-恢复，至多 $f$ 个副本故障（每个分片内）；分片之间的网络是异步的，但同一分片内多数派通信正常。
- 时间假设：使用 TrueTime（GPS + 原子钟）或有界时钟不确定性 $\epsilon$，用于给事务分配全局单调的提交时间戳；若无 TrueTime，可用 HLC（混合逻辑时钟）代替，但外部一致性会退化为”有界陈旧”。
伪代码
# ===== 事务流程（客户端 + 协调者分片 S_c + 参与者分片 S_1..S_m）=====
1. 客户端把事务 T 交给协调者分片 S_c 的 leader C0（S_c 自身也是一个 Raft 组）
2. 各参与者分片 S_j 的 leader：
执行 T 的本地部分（2PL/MVCC 加锁，写暂定更新）
把 <T, PREPARED, 暂定更新摘要> 作为一条 Raft 提案写入本分片日志
Raft: 提案被多数派持久化后才算"已准备"（此时 S_j 的 leader 崩溃也不丢）
若本地失败 ⇒ 提案 <T, NO>
回复 C0：VOTE_COMMIT / VOTE_ABORT
3. C0 收集所有投票：
任一 NO（或超时） ⇒ 决定 ABORT
全部 YES ⇒ 决定 COMMIT
★ 把 <T, DECISION, d, commit_ts> 作为一条 Raft 提案写入 S_c 的日志
★ 多数派确认后该决定才"生效"，且**永不可改**
4. C0 通知各分片；各分片把 <T, COMMITTED> 作为 Raft 提案应用，释放锁，回复 ACK
5. C0 收齐 ACK 后写 END（也可通过日志压缩清理）
6. 若客户端要读已提交数据：等待直到本地时间 > commit_ts + ε，保证
任何读者的时间戳都晚于提交点 ⇒ 外部一致性（external consistency）
# ===== 协调者 leader 崩溃时 =====
C0 崩溃 ⇒ S_c 的 Raft 组在选举超时内选出新 leader C1
C1 提交一条 no-op 或读取日志 ⇒ 从 Raft 日志中**恢复协调者状态**（含已定决定）
C1 继续第 4 步：广播决定、收集 ACK
# 阻塞窗口 = 选举超时（election timeout），而不是 C0 的修复时间
# ===== 参与者分片 leader 崩溃时 =====
S_j 的 leader 崩溃 ⇒ 该分片内 Raft 选主；新 leader 从其日志恢复
<PREPARED, 暂定更新> ⇒ 继续参与 2PC，不会"忘记自己投过 YES"
算法逻辑解说
- 与朴素 2PC 的唯一但关键的区别是：协调者的决定与参与者的准备状态都写入了多数派复制的日志。因此：
- 协调者 leader 崩溃不影响决定的存在性（新 leader 从日志恢复）；
- 参与者分片 leader 崩溃不会丢失”已投 YES”这个承诺；
- 阻塞窗口从”协调者不可用的时长”缩短为”一次选举超时”。
- Spanner 还用 TrueTime 给事务分配提交时间戳并等待不确定性区间 $\epsilon$，使得提交顺序与真实时间顺序一致（外部一致性）。这是”复制 + 原子提交”之外的第二层机制：它让全局事务顺序也有了物理意义。
正确性论证
- 安全性（原子性）：与 2PC 相同的推理——COMMIT 只在全员 YES 时产生。额外的要求是决定必须持久且唯一：决定以 Raft 提案写入，Raft 保证”已被多数派持久化的日志条目不会被推翻”（Leader Completeness / 状态机安全性，Lecture 17），因此决定的唯一性与持久性由共识保证，即使协调者 leader 反复崩溃重启，也不会出现两个不同的决定。
- 安全性（不出现”忘记的承诺”）：参与者分片的
<PREPARED>也在多数派日志中，leader 故障后新 leader 能恢复该状态 ⇒ 不会出现”某分片认为自己没参与过事务，而其他分片已提交”的情况。 - 活性（非阻塞）：只要每个分片组内有多数派存活、组间消息最终可达，Raft 会在有限时间内选出 leader；协调者决定一旦恢复即被广播；参与者在收到决定后完成提交/回滚。没有任何参与者需要无限期持锁等待一个不可达的单点。
- 代价：每个决定多了一轮共识（多数派写入），跨分片事务的延迟约为 \(T \approx \underbrace{2\times\text{RTT}_{\text{分片间}}}_{\text{2PC}} + \underbrace{(2\sim4)\times\text{RTT}_{\text{组内}}}_{\text{Raft 提案}} + \underbrace{\epsilon}_{\text{TrueTime 等待}}\) 这也是 Spanner 跨洲事务延迟可达数百毫秒的原因（见 20.5）。
复杂度：消息 $O(m \cdot \vert \text{Raft 组}\vert )$；每分片每次准备/提交各 1 次共识提案（可流水线批量）；空间 = 各分片日志。
20.4 代码示例与分布式实现
下面三个程序都是单机可运行、只用 Python 标准库的分布式模拟：用 threading 起多个”进程”，用 queue.Queue 充当”网络链路”，用真实的文件写入 + os.fsync 模拟 WAL 落盘，用显式的 crash/recover/cut_link 注入故障与分区。它们不是玩具伪代码——每个程序的末尾都有 assert 审计断言，任何一次原子性违反都会让程序立刻报错退出，因此”程序跑通”本身就是对 20.3 正确性论证的一次机器验证。
20.4.1 示例一：2PC 的完整实现（Coordinator + Participant + WAL）
假设与系统模型：3 个参与者（RM1/RM2/RM3），1 个协调者；崩溃-恢复故障模型；通道用 queue.Queue 模拟（可靠但会积压）；每个角色有独立 WAL 文件并真实 fsync；超时阈值 0.5 s。程序覆盖五个场景：(i) 全 YES；(ii) 一个 NO（验证”投了 YES 的也必须中止”）；(iii) 某 RM 记录 YES 后崩溃、投票消息丢失（验证”协调者超时 ⇒ 中止 + 恢复者询问决定”）；(iv) 协调者收齐投票后在写决定前崩溃（验证阻塞 + 恢复后续跑）；(v) 决定已落盘但只发出第一条消息就崩溃（验证”未收到决定者只能等”）。
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Two-Phase Commit (2PC) 完整实现
Coordinator + 3 Participants，threading + queue.Queue 模拟消息通道；
每个角色维护 WAL（真实写文件 + os.fsync），演示"决定必须落盘"。
四个场景：(i) 全 YES (ii) 一个 NO (iii) participant 投票后崩溃
(iv) coordinator 决定前崩溃 -> 阻塞现场 -> 恢复完成
"""
import os
import queue
import random
import tempfile
import threading
import time
random.seed(20261020)
TMP = tempfile.mkdtemp(prefix="wal_2pc_")
TXID = "T1"
OBJECTS = ["A:账户", "B:库存", "C:订单"] # 每个 participant 本地要改的对象
def log(who, msg):
print(f"[{who:>16}] {msg}", flush=True)
class WAL:
"""预写日志：append 后 flush + fsync。真实系统里 fsync 是提交延迟的主要来源。"""
def __init__(self, name):
self.path = os.path.join(TMP, name + ".wal")
self.records = []
self._fh = open(self.path, "w", encoding="utf-8", buffering=1)
def append(self, rec):
self.records.append(rec)
self._fh.write(repr(rec) + "\n")
self._fh.flush()
os.fsync(self._fh.fileno())
log("WAL/" + os.path.basename(self.path), f"fsync {rec}")
def find(self, kind):
return [r for r in self.records if r[0] == kind]
class Bus:
"""消息总线：每个节点一个 queue.Queue，可模拟网络分区（丢弃指定链路的消息）。"""
def __init__(self):
self.inboxes = {}
self.cut = set()
def register(self, name):
self.inboxes[name] = queue.Queue()
def cut_link(self, a, b):
self.cut.add((a, b))
self.cut.add((b, a))
def send(self, src, dst, kind, txid, **payload):
if (src, dst) in self.cut:
log("NET", f"DROP {kind}: {src} -> {dst} (网络分区)")
return
self.inboxes[dst].put((src, kind, txid, payload))
def recv(self, name, timeout=0.05):
try:
return self.inboxes[name].get(timeout=timeout)
except queue.Empty:
return None
def drain(self, name):
out = []
while True:
try:
out.append(self.inboxes[name].get_nowait())
except queue.Empty:
return out
class Coordinator(threading.Thread):
def __init__(self, bus, participants, timeout=0.5, crash_plan=()):
super().__init__(daemon=True, name="Coordinator")
self.me = "Coord"
self.bus, self.participants, self.timeout = bus, participants, timeout
self.crash_plan = set(crash_plan)
self.votes, self.acks = {}, set()
self.decision = None
self.stop_flag = threading.Event()
self.wal = WAL("coord_" + TXID)
def send(self, dst, kind, **payload):
log(self.me, f"--{kind}--> {dst}")
self.bus.send(self.me, dst, kind, TXID, **payload)
# ---------- 主流程 ----------
def run(self):
self.wal.append(("START", TXID))
for p in self.participants:
self.send(p, "PREPARE")
deadline = time.time() + self.timeout
while len(self.votes) < len(self.participants) and time.time() < deadline:
m = self.bus.recv(self.me, 0.02)
if m:
self.handle(m)
for p in self.participants: # 超时未投票者按 NO 处理
if p not in self.votes:
log(self.me, f"{p} 在 {self.timeout}s 内未投票 => 悲观地视为 NO")
self.votes[p] = "no"
for p, v in sorted(self.votes.items()):
self.wal.append(("VOTE", TXID, p, v))
if "before_decision" in self.crash_plan:
log(self.me, "*** 崩溃：已收齐全部投票，但决定尚未写入 WAL ***")
return
self.decision = "COMMIT" if all(v == "yes" for v in self.votes.values()) else "ABORT"
self.wal.append(("DECISION", TXID, self.decision))
if "after_decision_partial" in self.crash_plan:
self.send(self.participants[0], "GLOBAL_" + self.decision) # 只发出第一条
log(self.me, "*** 崩溃：决定已落盘，但决定消息只发给了第一个 participant ***")
return
self.broadcast_decision()
self.finish()
def broadcast_decision(self):
for p in self.participants:
self.send(p, "GLOBAL_" + self.decision)
def finish(self, serve_after=True):
deadline = time.time() + self.timeout
while len(self.acks) < len(self.participants) and time.time() < deadline:
m = self.bus.recv(self.me, 0.02)
if m:
self.handle(m)
self.wal.append(("END", TXID, sorted(self.acks)))
log(self.me, f"事务结束（收到 {len(self.acks)}/{len(self.participants)} 个 ACK），清理日志")
if serve_after:
self.serve() # 保持在线，回答恢复者的询问
def serve(self):
while not self.stop_flag.is_set():
m = self.bus.recv(self.me, 0.05)
if m:
self.handle(m)
def handle(self, m):
src, kind, txid, payload = m
if kind == "VOTE_COMMIT":
log(self.me, f"<--VOTE_COMMIT-- {src}")
self.votes[src] = "yes"
elif kind == "VOTE_ABORT":
log(self.me, f"<--VOTE_ABORT-- {src}")
self.votes[src] = "no"
elif kind == "ACK":
log(self.me, f"<--ACK-- {src}")
self.acks.add(src)
elif kind == "DECISION_QUERY":
log(self.me, f"<--DECISION_QUERY-- {src}；查 WAL 后答复")
self.send(src, "DECISION_RESPONSE", decision=self.decision)
# ---------- 崩溃恢复 ----------
def recover(self):
log(self.me, "*** 重启：读取 WAL ***")
dec = None
for r in self.wal.find("DECISION"):
dec = r[2]
if dec is None:
votes = self.wal.find("VOTE")
all_yes = len(votes) == len(self.participants) and all(r[3] == "yes" for r in votes)
dec = "COMMIT" if all_yes else "ABORT"
log(self.me, f"WAL 中无决定记录；{'全部 YES 已落盘 => 决定 COMMIT' if all_yes else '没有完整 YES 集合 => 决定 ABORT'}")
self.wal.append(("DECISION", TXID, dec))
else:
log(self.me, f"WAL 中已有决定 {dec} => 重发决定消息")
self.decision = dec
self.stop_flag.clear()
self.broadcast_decision()
self.finish(serve_after=False)
class Participant(threading.Thread):
def __init__(self, name, bus, coord, vote="yes", crash_at=None):
super().__init__(daemon=True, name=name)
self.me, self.bus, self.coord = name, bus, coord
self.vote, self.crash_at = vote, crash_at
self.wal = WAL("part_" + name)
self.state, self.decision = "INIT", None
self.locks, self.blocked_others = set(), 0
self.alive, self.reported = True, False
self.in_doubt_at = None
def send(self, dst, kind, **payload):
log(self.me, f"--{kind}--> {dst}")
self.bus.send(self.me, dst, kind, TXID, **payload)
def run(self):
while self.alive:
m = self.bus.recv(self.me, 0.03)
if m is None:
self.on_idle()
else:
self.handle(m)
def on_idle(self):
if self.state != "IN_DOUBT":
return
waited = time.time() - self.in_doubt_at
if not self.reported or waited > 0.5:
self.reported = True
log(self.me, f"!! 卡在 IN_DOUBT 已 {waited:4.1f}s：{len(self.locks)} 把锁未释放，"
f"{self.blocked_others} 个其他事务被它阻塞，只能等决定")
def handle(self, m):
src, kind, txid, payload = m
if kind == "PREPARE" and self.state == "INIT":
if self.crash_at == "before_vote":
log(self.me, "*** 崩溃：收到 PREPARE 后、投票前崩溃（没有投出任何票）***")
self.alive = False
return
self.locks = set(OBJECTS)
self.blocked_others = 2
self.wal.append(("PREPARE", TXID, sorted(self.locks)))
log(self.me, f"<--PREPARE-- {src}；执行本地部分（不提交），持有锁 {sorted(self.locks)}")
if self.vote == "yes":
self.wal.append(("VOTE", TXID, "yes"))
self.state, self.in_doubt_at = "IN_DOUBT", time.time()
if self.crash_at == "while_voting":
log(self.me, "*** 崩溃：本地已记下 YES，但这条投票消息还没发出去就崩溃了 ***")
self.alive = False
return
self.send(self.coord, "VOTE_COMMIT")
if self.crash_at == "after_vote":
log(self.me, "*** 崩溃：投出 YES 之后、收到决定之前崩溃（锁仍未释放）***")
self.alive = False
else:
self.wal.append(("VOTE", TXID, "no"))
self.locks.clear()
self.state, self.decision = "ABORTED", "ABORT"
log(self.me, "本地检查失败（约束冲突）=> 投 NO，并立即单方面中止、释放锁")
self.send(self.coord, "VOTE_ABORT")
elif kind == "GLOBAL_COMMIT":
log(self.me, f"<--GLOBAL_COMMIT-- {src}")
self.do_commit()
elif kind == "GLOBAL_ABORT":
log(self.me, f"<--GLOBAL_ABORT-- {src}")
self.do_abort()
elif kind == "DECISION_RESPONSE":
dec = payload["decision"]
log(self.me, f"<--DECISION_RESPONSE-- {src}：{dec}")
(self.do_commit if dec == "COMMIT" else self.do_abort)()
def do_commit(self):
if self.decision is not None:
return
self.wal.append(("COMMIT", TXID))
self.locks.clear()
self.state, self.decision = "COMMITTED", "COMMIT"
log(self.me, "COMMIT：把临时更新刷入正式存储，释放全部锁")
self.send(self.coord, "ACK")
def do_abort(self):
if self.decision is not None:
self.send(self.coord, "ACK")
return
self.wal.append(("ABORT", TXID))
self.locks.clear()
self.state, self.decision = "ABORTED", "ABORT"
log(self.me, "ABORT：回滚本地临时更新，释放全部锁")
self.send(self.coord, "ACK")
# ---------- 崩溃恢复 ----------
def recover(self, seconds=2.0):
self.alive = False
pending = self.bus.drain(self.me)
if pending:
log(self.me, f"重启：丢弃崩溃期间积压在 inbox 里的 {len(pending)} 条消息 "
f"{[p[1] for p in pending]}（内存消息不可依赖）")
log(self.me, "重启：读取本地 WAL")
if self.wal.find("COMMIT"):
dec, why = "COMMIT", "WAL 中已有 COMMIT 记录"
elif self.wal.find("ABORT"):
dec, why = "ABORT", "WAL 中已有 ABORT 记录"
else:
log(self.me, "WAL 中只有 PREPARE/VOTE、没有决定 => 仍处不确定状态，向协调者询问")
self.send(self.coord, "DECISION_QUERY")
dec, why, deadline = None, "", time.time() + seconds
while dec is None and time.time() < deadline:
m = self.bus.recv(self.me, 0.05)
if m and m[1] == "DECISION_RESPONSE":
dec, why = m[3]["decision"], "协调者答复（它从自己的 WAL 读出决定）"
elif m and m[1].startswith("GLOBAL_"):
dec, why = m[1].split("_", 1)[1], "收到决定消息"
log(self.me, f"恢复结论：{dec}（依据：{why}）")
(self.do_commit if dec == "COMMIT" else self.do_abort)()
def audit(parts, expect_state=None):
decs = {p.me: p.decision for p in parts}
print(" >>> 最终决定:", decs)
assert None not in decs.values(), f"有 participant 从未做出决定: {decs}"
assert len(set(decs.values())) == 1, f"！原子性被违反: {decs}"
total_locks = sum(len(p.locks) for p in parts)
if expect_state == "IN_DOUBT":
assert all(p.state == "IN_DOUBT" for p in parts), decs
print(f" >>> AUDIT OK：3 个 participant 决定完全一致 = {next(iter(decs.values()))}；"
f"锁全部释放（剩余 {total_locks} 把）")
def build(votes, part_crash=None, coord_crash=()):
bus = Bus()
names = ["RM1", "RM2", "RM3"]
for n in names + ["Coord"]:
bus.register(n)
coord = Coordinator(bus, names, timeout=0.5, crash_plan=coord_crash)
parts = [Participant(n, bus, "Coord", vote=votes.get(n, "yes"),
crash_at=(part_crash[1] if part_crash and part_crash[0] == n else None))
for n in names]
return bus, coord, parts
def scenario(title, votes, part_crash=None, coord_crash=(), block_probe=False):
print("\n" + "=" * 84)
print(f"场景 {title}")
print("=" * 84)
bus, coord, parts = build(votes, part_crash, coord_crash)
coord.start()
for p in parts:
p.start()
time.sleep(1.3 if not coord_crash else 1.0)
if block_probe: # 场景 (iv)：证明"阻塞"真的发生了
print(" >>> 阻塞现场报告（协调者已崩溃，参与者无法推进）:")
for p in parts:
print(f" {p.me}: state={p.state:9s} locks={sorted(p.locks)} "
f"blocked_others={p.blocked_others} decision={p.decision}")
assert all(p.state == "IN_DOUBT" for p in parts), "应当全部卡在 IN_DOUBT"
print(" >>> 阻塞确认：3 个 RM 全部卡在 IN_DOUBT、共持有 9 把锁、"
"6 个其他事务被阻塞；在协调者恢复前协议无法推进")
return bus, coord, parts
def shutdown(coord, parts):
coord.stop_flag.set()
for p in parts:
p.alive = False
coord.join(timeout=1.0)
for p in parts:
p.join(timeout=1.0)
def main():
# (i) 全部投 YES
bus, coord, parts = scenario("(i) 三个 RM 全部投 YES", {})
audit(parts)
shutdown(coord, parts)
# (ii) 一个 RM 投 NO
bus, coord, parts = scenario("(ii) RM2 投 NO（RM1/RM3 投了 YES）", {"RM2": "no"})
audit(parts)
print(" >>> 注意：投了 YES 的 RM1/RM3 也必须中止 —— 这正是 2PC 原子性的体现")
shutdown(coord, parts)
# (iii) RM3 在投票后崩溃（投票消息还没发出）
bus, coord, parts = scenario("(iii) RM3 记录 YES 后崩溃，投票消息丢失", {},
part_crash=("RM3", "while_voting"))
print(f" >>> 崩溃的 RM3 恢复前：持有锁 {sorted(parts[2].locks)}（未释放）")
parts[2].recover()
audit(parts)
shutdown(coord, parts)
# (iv) 协调者在决定前崩溃 —— 阻塞现场
bus, coord, parts = scenario("(iv) 协调者收齐投票后在写决定前崩溃", {},
coord_crash=("before_decision",), block_probe=True)
print("\n >>> 让协调者从 WAL 恢复 ...")
coord.recover()
threading.Thread(target=coord.serve, daemon=True).start()
time.sleep(0.8)
audit(parts)
shutdown(coord, parts)
# (v) 对照：决定已落盘，但只发出了第一条决定消息就崩溃
bus, coord, parts = scenario("(v) 协调者决定已落盘，但只发出第一条决定消息就崩溃",
{}, coord_crash=("after_decision_partial",))
have = {p.me: p.decision for p in parts}
print(f" >>> 崩溃时刻部分参与者的已知决定: {have}")
print(" >>> 未收到决定的参与者只能继续等待（它们不能自行决定！）—— 又一次阻塞")
coord.recover()
threading.Thread(target=coord.serve, daemon=True).start()
time.sleep(0.8)
audit(parts)
shutdown(coord, parts)
print("\n所有场景通过：2PC 在无故障时 2 个 RTT 完成，在协调者故障时会阻塞，"
"但原子性从未被违反。")
if __name__ == "__main__":
main()
【代码做什么？】
WAL类：每次append都写文件并flush + os.fsync，并在控制台打印fsync (...)——你在输出里看到的每一行WAL/xxx.wal fsync ('DECISION', 'T1', 'COMMIT')就是”决定必须落盘”的现场证据。Bus类：send把消息投到目标节点的queue.Queue；drain用来在”重启”时丢弃崩溃期间积压在 inbox 里的消息（提醒我们内存中的待收消息不可依赖）。Coordinator.run()：写START→ 广播PREPARE→ 收集投票（超时者视为 NO）→ 把每条投票写日志 → 若命中before_decision崩溃点，在写决定之前直接返回（线程结束 = 进程崩溃） → 否则算出决定、写DECISION日志、广播、收ACK、写END，最后留在serve()里回答恢复者的DECISION_QUERY。Participant：收到PREPARE后加锁、执行本地部分、把PREPARE落盘；投 YES 者进入IN_DOUBT并保持持锁（on_idle会周期性打印”卡在 IN_DOUBT 已 x.x s：3 把锁未释放，2 个其他事务被它阻塞”）；投 NO 者立即释放锁并单方面中止。Participant.recover()：先丢弃 inbox 中的积压消息，再读 WAL——有COMMIT/ABORT记录就直接跟随；只有PREPARE/VOTE没有决定时，向协调者发DECISION_QUERY并按其答复执行。audit()：所有场景结束后断言”三个参与者的decision非空且完全一致”，并检查锁是否全部释放；任何违反都会AssertionError。- 场景 (iv) 的关键输出：
>>> 阻塞现场报告（协调者已崩溃，参与者无法推进）: RM1: state=IN_DOUBT locks=['A:账户', 'B:库存', 'C:订单'] blocked_others=2 decision=None RM2: state=IN_DOUBT locks=['A:账户', 'B:库存', 'C:订单'] blocked_others=2 decision=None RM3: state=IN_DOUBT locks=['A:账户', 'B:库存', 'C:订单'] blocked_others=2 decision=None >>> 阻塞确认：3 个 RM 全部卡在 IN_DOUBT、共持有 9 把锁、6 个其他事务被阻塞 [ Coord] WAL 中无决定记录；全部 YES 已落盘 => 决定 COMMIT >>> AUDIT OK：3 个 participant 决定完全一致 = COMMIT；锁全部释放（剩余 0 把）
【分布式机制透视】
- 进程与消息：每个
Participant和Coordinator是一个threading.Thread，各自有queue.Queue作为”网卡”。消息是普通的元组(src, kind, txid, payload)，对应真实系统里的 RPC 消息（Lecture 19-20 的 marshalling/消息层在这里被简化成元组）。 - 崩溃与恢复：崩溃 = 线程
return（alive=False），此时它不再消费消息，但它的 inbox 仍在接收——这精确模拟了”进程死了但网络还在把包送进来”。恢复 = 一个新的执行流读取磁盘上的 WAL 决定后续动作。这正是真实系统的 crash-recovery 语义：内存不可信，只有持久化日志可信。 - 持久化点：
PREPARE（参与者侧，投 YES 之前）与DECISION（协调者侧，广播决定之前）是两个关键 fsync 点；代码把二者都打印出来，方便对照 20.2.12 的崩溃点表。 - 为什么
IN_DOUBT期间只打印不动作：这就是 20.3.4(B) 的结论在代码里的体现——自行提交或中止都可能与别人冲突，所以程序故意什么都不做，把”事务被卡住”这件事可视化。 - 总线与分区：示例二在同一个
Bus上增加cut_link，让”丢包”变成可编程的分区注入。
【与理论的对应】 | 代码位置 | 对应理论 | |—|—| | Coordinator.run() 中 all(v == "yes") 才 COMMIT | 算法 20.3.2 的 decide(COMMIT) 前置条件；20.3.4(A) 原子性证明的第 1 步 | | 任何 NO 或超时 ⇒ ABORT | 讲义”一票否决 + 悲观超时”；2PC 的 unanimous 决策规则 | | Participant.on_idle() 在 IN_DOUBT 不做决定 | 20.3.4(B) 阻塞性证明：”唯一安全的动作是继续等待” | | 场景 (iv) 的阻塞报告 | 阻塞性证明的构造性执行 $E$（协调者崩溃且不恢复） | | Participant.recover() 的 DECISION_QUERY | 讲义”To deal with Commit or Abort message loss — Server can poll coordinator (repeatedly)” | | audit() 的一致性断言 | 原子性/一致性（uniform agreement）：要么全 COMMIT，要么全 ABORT | | WAL.append 的 fsync | 讲义”Each server saves tentative updates into permanent storage, right before replying Yes/No”与”Coordinator logs all decisions on disk” |
20.4.2 示例二：3PC 与”分区下原子性被违反”的反例实验
假设与系统模型：同一套消息框架下同时实现 2PC 与 3PC（mode="2pc"/"3pc"），参与者超时阈值 0.4 s，并支持在运行中切断指定链路（Bus.cut_link）来制造网络分区。三个场景：(A) 3PC + 协调者在决定前崩溃（无分区）；(B) 3PC + 分区 {Coord, RM1} \| {RM2, RM3}；(C) 2PC + 完全相同的分区（对照组）。
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Three-Phase Commit (3PC) vs Two-Phase Commit (2PC)
同一套消息框架下实现两种协议，用同样的故障（协调者崩溃 / 网络分区）对比：
场景 A: 3PC + 协调者在决定前崩溃 -> 不阻塞，原子性保持
场景 B: 3PC + 网络分区 -> 不阻塞，但【原子性被违反】
场景 C: 2PC + 同样的网络分区 -> 阻塞（活性丢失），但原子性保持
"""
import queue
import random
import threading
import time
random.seed(20261020)
TIMEOUT = 0.40 # 参与者等待协调者消息的超时
T0 = time.time()
def log(who, msg):
print(f"[{time.time() - T0:6.2f}s][{who:>6}] {msg}", flush=True)
class Bus:
"""消息总线，支持用 cut_link 制造网络分区。"""
def __init__(self):
self.inboxes = {}
self.cut = set()
def register(self, name):
self.inboxes[name] = queue.Queue()
def cut_link(self, a, b):
self.cut.add((a, b))
self.cut.add((b, a))
def send(self, src, dst, kind, payload=None):
if (src, dst) in self.cut:
log("NET", f"DROP {kind}: {src} -> {dst} (网络分区)")
return
self.inboxes[dst].put((src, kind, payload or {}))
def recv(self, name, timeout=0.03):
try:
return self.inboxes[name].get(timeout=timeout)
except queue.Empty:
return None
class Participant(threading.Thread):
MSG_LOCAL = ("PREPARE", "CAN_COMMIT")
MSG_COMMIT = ("GLOBAL_COMMIT", "DO_COMMIT")
MSG_ABORT = ("GLOBAL_ABORT", "ABORT")
def __init__(self, name, bus, coord, peers, mode="3pc", vote="yes"):
super().__init__(daemon=True, name=name)
self.me, self.bus, self.coord, self.peers = name, bus, coord, peers
self.mode, self.vote = mode, vote
self.state, self.decision = "INIT", None
self.vote_at = self.wait_since = self.decided_at = None
self.reports = 0
self.peer_reply = {}
self.alive = True
def send(self, dst, kind, **payload):
self.bus.send(self.me, dst, kind, payload)
def run(self):
while self.alive:
m = self.bus.recv(self.me, 0.03)
if m:
self.handle(m)
else:
self.check_timeout()
def handle(self, m):
src, kind, p = m
if kind in self.MSG_LOCAL and self.state == "INIT":
self.vote_at = self.wait_since = time.time()
if self.vote == "yes":
self.state = "WAIT_PRE"
log(self.me, f"<--{kind}-- 执行本地部分（不提交），投票 YES")
self.send(self.coord, "VOTE_COMMIT")
else:
self.state, self.decision = "ABORTED", "ABORT"
log(self.me, f"<--{kind}-- 本地检查失败，投票 NO（可单方面中止）")
self.send(self.coord, "VOTE_ABORT")
elif kind == "PRE_COMMIT":
self.state, self.wait_since = "PRECOMMITTED", time.time()
log(self.me, "<--PRE_COMMIT-- 进入 PRECOMMITTED（预提交阶段，仍持有锁）")
self.send(self.coord, "ACK_PRE")
elif kind in self.MSG_COMMIT:
log(self.me, f"<--{kind}-- 提交")
self.finish("COMMIT")
self.send(self.coord, "ACK_COMMIT")
elif kind in self.MSG_ABORT:
log(self.me, f"<--{kind}-- 回滚")
self.finish("ABORT")
self.send(self.coord, "ACK_ABORT")
elif kind == "STATE_QUERY":
self.send(src, "STATE_REPLY", state=self.state, decision=self.decision)
elif kind == "STATE_REPLY":
self.peer_reply[src] = p["state"]
def finish(self, dec):
if self.decision is None:
self.decision = dec
self.decided_at = time.time()
self.state = "COMMITTED" if dec == "COMMIT" else "ABORTED"
log(self.me, f"最终决定 = {dec}（投票后 {self.decided_at - (self.vote_at or T0):.2f}s）")
# ---------- 超时处理：2PC 阻塞、3PC 自主决定 ----------
def check_timeout(self):
if self.state == "WAIT_PRE" and time.time() - self.wait_since > TIMEOUT:
if self.mode == "2pc":
self.reports += 1
if self.reports <= 2:
log(self.me, "处于 IN_DOUBT（已投 YES、未收到决定）：持有锁，"
"不能提交也不能中止，只能一直等 —— 这就是 2PC 的阻塞")
else:
self.termination()
elif self.state == "PRECOMMITTED" and time.time() - self.wait_since > TIMEOUT:
log(self.me, "PRECOMMITTED 状态超时 => 3PC 规则：可自主提交（不等协调者）")
self.finish("COMMIT")
def termination(self):
"""3PC 的 termination protocol：问一圈，再决定。"""
log(self.me, "WAIT_PRE 超时 => 启动 termination protocol，向所有节点询问状态")
self.peer_reply = {}
for dst in self.peers + [self.coord]:
self.bus.send(self.me, dst, "STATE_QUERY")
deadline, saw_pre = time.time() + 0.45, False
while time.time() < deadline and not saw_pre:
m = self.bus.recv(self.me, 0.03)
if not m:
continue
src, kind, p = m
if kind == "STATE_REPLY":
self.peer_reply[src] = p["state"]
log(self.me, f" {src} 报告状态 {p['state']}"
+ (" <= 有人已预提交，绝不能中止！" if p["state"] == "PRECOMMITTED" else ""))
saw_pre = p["state"] in ("PRECOMMITTED", "COMMITTED")
else:
self.handle(m)
if self.decision is not None:
return
if saw_pre:
self.finish("COMMIT")
else:
log(self.me, f"无人处于 PRECOMMITTED/COMMITTED（收到的答复: {self.peer_reply or '无'}）"
f" => 自主决定 ABORT")
self.finish("ABORT")
class Coordinator(threading.Thread):
def __init__(self, bus, participants, mode="3pc", crash_after_votes=False,
pause_after_votes=0.0, precommit_to=None, docommit_to=None):
super().__init__(daemon=True, name="Coordinator")
self.me, self.bus, self.participants, self.mode = "Coord", bus, participants, mode
self.crash_after_votes, self.pause = crash_after_votes, pause_after_votes
self.precommit_to = precommit_to or participants
self.docommit_to = docommit_to or participants
self.votes, self.decision = {}, None
def send(self, dst, kind, **payload):
log(self.me, f"--{kind}--> {dst}")
self.bus.send(self.me, dst, kind, payload)
def run(self):
first = "PREPARE" if self.mode == "2pc" else "CAN_COMMIT"
for p in self.participants:
self.send(p, first)
deadline = time.time() + 0.35
while len(self.votes) < len(self.participants) and time.time() < deadline:
m = self.bus.recv(self.me, 0.03)
if m and m[1].startswith("VOTE"):
self.votes[m[0]] = "yes" if m[1] == "VOTE_COMMIT" else "no"
log(self.me, f"<--{m[1]}-- {m[0]}")
log(self.me, f"投票汇总: {self.votes}")
if len(self.votes) < len(self.participants) or any(v == "no" for v in self.votes.values()):
self.decision = "ABORT"
for p in self.participants:
self.send(p, "ABORT" if self.mode == "3pc" else "GLOBAL_ABORT")
return
if self.crash_after_votes:
log(self.me, "*** 崩溃：全部 YES 已收到，但尚未向任何人发出任何决定 ***")
return
time.sleep(self.pause) # 供 main 在此期间制造网络分区
if self.mode == "3pc":
for p in self.precommit_to:
self.send(p, "PRE_COMMIT")
time.sleep(0.3) # 收集 ACK_PRE（简化：不阻塞等待）
for p in self.docommit_to:
self.send(p, "DO_COMMIT")
else:
for p in self.docommit_to:
self.send(p, "GLOBAL_COMMIT")
self.decision = "COMMIT"
time.sleep(0.3)
def build(mode="3pc", **plan):
bus = Bus()
names = ["RM1", "RM2", "RM3"]
for n in names + ["Coord"]:
bus.register(n)
coord = Coordinator(bus, names, mode=mode, **plan)
parts = [Participant(n, bus, "Coord", [x for x in names if x != n], mode=mode) for n in names]
return bus, coord, parts
def stop(coord, parts):
for p in parts:
p.alive = False
coord.join(timeout=1.0)
for p in parts:
p.join(timeout=1.0)
def decisions(parts):
return {p.me: p.decision for p in parts}
def banner(t):
print("\n" + "=" * 84 + f"\n{t}\n" + "=" * 84)
def main():
results = {}
# ---------------- 场景 A：3PC，协调者在决定前崩溃（无分区） ----------------
banner("场景 A：3PC —— 协调者收齐 YES 后崩溃（未发出任何决定），无网络分区")
bus, coord, parts = build("3pc", crash_after_votes=True)
coord.start()
for p in parts:
p.start()
time.sleep(2.0)
dec = decisions(parts)
print(" >>> 各参与者最终决定:", dec)
assert None not in dec.values(), "3PC 不应阻塞"
assert len(set(dec.values())) == 1, "原子性被违反"
print(" >>> 3PC：每个参与者在超时后经 termination protocol 自主决定，无人永久阻塞")
results["coord_crash_no_partition"] = ("阻塞", "不阻塞", "保持")
stop(coord, parts)
# ---------------- 场景 B：3PC + 网络分区 -> 原子性违反 ----------------
banner("场景 B：3PC + 网络分区 —— 分区 {Coord, RM1} | {RM2, RM3}")
bus, coord, parts = build("3pc", pause_after_votes=0.25,
precommit_to=["RM1"], docommit_to=["RM1"])
coord.start()
for p in parts:
p.start()
time.sleep(0.12)
print(" *** 网络分区发生：切断 Coord-RM2, Coord-RM3, RM1-RM2, RM1-RM3 ***")
for a, b in [("Coord", "RM2"), ("Coord", "RM3"), ("RM1", "RM2"), ("RM1", "RM3")]:
bus.cut_link(a, b)
time.sleep(2.4)
dec = decisions(parts)
print(" >>> 各参与者最终决定:", dec)
print(" >>> 分区左侧 {Coord, RM1}: RM1 收到 PRE_COMMIT 与 DO_COMMIT => COMMIT")
print(" >>> 分区右侧 {RM2, RM3}: 无法联系任何人 => 自主决定 ABORT")
assert dec["RM1"] == "COMMIT" and dec["RM2"] == "ABORT" and dec["RM3"] == "ABORT"
print(" >>> !!! 原子性被违反：同一个事务在 RM1 提交、在 RM2/RM3 中止 !!!")
results["partition"] = ("（本轮用 2PC 对照，见场景 C）", "不阻塞", "违反")
stop(coord, parts)
# ---------------- 场景 C：2PC + 同样的分区 -> 阻塞但不违反原子性 ----------------
banner("场景 C：2PC + 完全相同的网络分区 —— 对照组")
bus, coord, parts = build("2pc", pause_after_votes=0.25, docommit_to=["RM1"])
coord.start()
for p in parts:
p.start()
time.sleep(0.12)
print(" *** 网络分区发生：切断 Coord-RM2, Coord-RM3, RM1-RM2, RM1-RM3 ***")
for a, b in [("Coord", "RM2"), ("Coord", "RM3"), ("RM1", "RM2"), ("RM1", "RM3")]:
bus.cut_link(a, b)
time.sleep(2.4)
dec = decisions(parts)
print(" >>> 各参与者最终决定:", dec)
assert dec["RM1"] == "COMMIT" and dec["RM2"] is None and dec["RM3"] is None
print(" >>> 2PC：RM2/RM3 投了 YES 却收不到决定，永远停在 IN_DOUBT 并持有锁（阻塞）")
print(" >>> 但只要协调者恢复并重发决定，它们就会跟随 => 原子性不会被违反")
stop(coord, parts)
# ---------------- 对比表 ----------------
banner("对比表：同一个故障，两种协议的不同失败方式")
print(" +---------------------------+----------------------+----------------------+")
print(" | 故障场景 | 2PC | 3PC |")
print(" +---------------------------+----------------------+----------------------+")
print(" | 协调者决定前崩溃（无分区） | 阻塞：参与者持锁等待 | 不阻塞：超时+termination |")
print(" | | 直到协调者恢复 | protocol 自主决定 |")
print(" | 网络分区 | 阻塞，但原子性保持 | 不阻塞，但原子性被违反 |")
print(" | 消息轮次（无故障） | 2 RTT | 3 RTT |")
print(" | 参与者状态数 | INIT/IN_DOUBT/决定 | +PRECOMMITTED/TERMINATING |")
print(" +---------------------------+----------------------+----------------------+")
print(" 结论：3PC 用'多一个 RTT'和'分区下可能不一致'换来了'不阻塞'。")
print(" 这不是免费的午餐：非阻塞性是在【无分区假设】下才成立的。")
if __name__ == "__main__":
main()
【代码做什么？】
Participant同时支持两套消息名（PREPARE/GLOBAL_COMMIT与CAN_COMMIT/PRE_COMMIT/DO_COMMIT），状态机因此多出PRECOMMITTED与WAIT_PRE两个状态。check_timeout()是两协议的分野：mode="2pc"：处于IN_DOUBT时只打印”不能提交也不能中止，只能一直等”，永不自决；mode="3pc"：WAIT_PRE超时 ⇒ 调用termination()；PRECOMMITTED超时 ⇒ 直接提交（因为收到过PRE_COMMIT，已知全体投过 YES）。
termination()就是终止协议：向所有同伴与协调者发STATE_QUERY，在 0.45 s 内收集STATE_REPLY；只要发现有人处于PRECOMMITTED/COMMITTED，就跟随提交；否则自主中止（并打印它收到的答复，让读者看到”它为什么敢中止”）。- 场景 B/C 的编排：先让三方投票，
time.sleep(0.12)之后切断 4 条链路，协调者再（在 0.25 s 处）发出PRE_COMMIT/GLOBAL_COMMIT给 RM1——于是 RM1 与 RM2/RM3 被永久隔开。 - 关键输出（场景 B）：
[ Coord] --PRE_COMMIT--> RM1 （RM2/RM3 被分区隔离，收不到） [ RM1] <--DO_COMMIT-- 提交 => 最终决定 = COMMIT [ RM2] 无人处于 PRECOMMITTED/COMMITTED（收到的答复: {'RM3': 'WAIT_PRE'}） => 自主决定 ABORT [ RM3] => 自主决定 ABORT >>> 各参与者最终决定: {'RM1': 'COMMIT', 'RM2': 'ABORT', 'RM3': 'ABORT'} >>> !!! 原子性被违反：同一个事务在 RM1 提交、在 RM2/RM3 中止 !!!而场景 C 的同样分区下，2PC 的输出是
{'RM1': 'COMMIT', 'RM2': None, 'RM3': None}：RM2/RM3 永远卡在IN_DOUBT（阻塞），但没有出现两个互相矛盾的决定。
【分布式机制透视】
- “决策”与”阻塞”是两个独立的维度：场景 B 与 C 用完全相同的故障（同样的分区、同样的时刻、同样的消息），却得到两种不同的失败方式——3PC 用原子性换了非阻塞，2PC 用阻塞换了原子性。这是本章最有价值的一次对照实验，也是分布式系统里”没有免费的午餐”最直观的演示。
- 分区是”双向静默”：
cut_link同时丢弃两个方向的消息（真实分区就是这样），因此 3PC 的STATE_QUERY收不到任何答复。这一点很关键：如果只是”延迟”，终止协议最终能问到；只有分区才会让”问不到”变成”永久问不到”。 - 超时值是协议的一部分：3PC 的安全性依赖”分区不存在”这一假设，而实现里超时值 $\tau$ 的选取决定了”多慢才算分区”。$\tau$ 太小 ⇒ 误判导致本可避免的自决；$\tau$ 太大 ⇒ 阻塞窗口变长。真实系统里这个参数只能靠经验与 SLA 折中（Raft 的 election timeout 同理）。
【与理论的对应】 | 代码位置 | 对应理论 | |—|—| | check_timeout() 中 2PC 分支”只打印不动手” | 20.3.4(B)：IN_DOUBT 中任何单方面决定都可能造成不一致 | | PRECOMMITTED 超时 ⇒ 自主提交 | 20.3.5 的状态单调性论证：收到 PRE_COMMIT ⇒ 全体投过 YES ⇒ 无人可能中止 | | termination() 的”发现 PRECOMMITTED 就跟随” | 20.3.5 活性论证中的关键分支，也是避免原子性违反的唯一手段 | | 场景 B 的反例 | 3PC 非阻塞性依赖无分区假设；分区下一部分提交、一部分中止 ⇒ 违反原子性 | | 场景 A（协调者崩溃、无分区） | 3PC 的非阻塞性：参与者在有限时间内自行决定，无人永久持锁 | | 末尾对比表 | 2PC = 2 RTT / 阻塞但安全；3PC = 3 RTT / 非阻塞但分区下不安全 |
20.4.3 示例三：被动复制的故障切换、RPO 量化与脑裂 fencing
假设与系统模型：1 个 primary + 2 个 backup；后台复制线程用 time.sleep(REPL_DELAY=30 ms) 模拟网络与落盘延迟，客户端两次写间隔 6 ms ⇒ 异步模式下崩溃时必然有若干更新”在路上”；FencedStore 模拟带 epoch 检查的共享存储（fencing 的执行者）；Replica 维护 data/lsn/log，lsn 即 LSN。
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
被动复制（primary-backup）故障切换实验
1) 同步 vs 异步复制：写延迟、崩溃时丢失的更新数（RPO）
2) 故障切换：用 LSN 选出最新的 backup 晋升为新 primary；落后副本 catch-up
3) 脑裂：旧 primary "复活"后继续接受写 -> 数据分歧；加入 fencing token 后写被拒绝
"""
import queue
import random
import threading
import time
random.seed(20261020)
REPL_DELAY = 0.030 # 一条更新从 primary 传播到 backup 的耗时（网络+落盘）
WRITE_GAP = 0.006 # 客户端两次写之间的间隔
class FencedStore:
"""带 fencing 的共享存储：epoch 落后的写一律拒绝（真实系统里由存储/仲裁层执行）。"""
def __init__(self, fencing=True):
self.fencing = fencing
self.fence_epoch = 1
self.rejected = 0
def accept(self, epoch):
if self.fencing and epoch < self.fence_epoch:
self.rejected += 1
return False
self.fence_epoch = max(self.fence_epoch, epoch)
return True
class Replica:
def __init__(self, name, epoch, store):
self.name, self.epoch, self.store = name, epoch, store
self.data, self.lsn, self.log = {}, 0, [] # log: [(lsn, key, value)]
self.rejected = 0
def write(self, key, value):
if not self.store.accept(self.epoch):
self.rejected += 1
print(f" {self.name}: 写 {key}={value} 被拒绝（fencing: epoch {self.epoch} "
f"< 当前 {self.store.fence_epoch}）")
return None
self.lsn += 1
self.data[key] = value
self.log.append((self.lsn, key, value))
return (self.lsn, key, value)
def apply_replicated(self, lsn, key, value):
if lsn <= self.lsn:
return False
self.lsn, self.data[key] = lsn, value
self.log.append((lsn, key, value))
return True
def run_replication(mode, writes=5, keys=3):
"""返回 (平均写延迟, 丢失的更新列表, 各副本最终状态)"""
print(f"\n--- 模式 = {mode.upper()}（primary 接受 {writes} 次写后崩溃）")
store = FencedStore()
primary = Replica("primary(epoch1)", 1, store)
backups = [Replica("backup1", 0, store), Replica("backup2", 0, store)]
q, crashed = queue.Queue(), threading.Event()
def replicator(): # 后台复制线程：模拟异步传播
while True:
item = q.get()
if item is None or crashed.is_set():
return
time.sleep(REPL_DELAY)
if crashed.is_set(): # primary 已崩溃：这条更新永远丢失
return
for b in backups:
b.apply_replicated(*item)
threading.Thread(target=replicator, daemon=True).start()
latencies = []
for i in range(1, writes + 1):
key, val = f"k{(i - 1) % keys + 1}", f"v{i}"
t0 = time.perf_counter()
rec = primary.write(key, val)
q.put(rec)
if mode == "sync": # 同步：等所有 backup 确认
deadline = time.time() + 1.0
while time.time() < deadline and not all(b.lsn >= rec[0] for b in backups):
time.sleep(0.002)
latencies.append(time.perf_counter() - t0) # 异步：本地写完立即返回
time.sleep(WRITE_GAP)
crashed.set() # >>> primary 崩溃 <<<
time.sleep(0.12) # 让复制线程退出
print(f" primary 崩溃：本地 lsn={primary.lsn}，data={primary.data}")
for b in backups:
print(f" {b.name}: lsn={b.lsn}，data={b.data}")
newest = max(backups, key=lambda b: b.lsn)
lost = [r for r in primary.log if r[0] > newest.lsn]
print(f" 最新（LSN 最大）的 backup = {newest.name}，晋升为新 primary")
print(f" 崩溃时尚未传播的更新: {lost} => 数据丢失量 RPO = {len(lost)} 次写")
return sum(latencies) / len(latencies), lost, primary, backups, newest, store
def failover(primary, backups, newest, store):
"""故障切换：晋升 LSN 最大的 backup，落后的副本从新 primary catch-up。"""
newp = Replica("backup->primary(epoch2)", 2, store)
newp.data, newp.lsn, newp.log = dict(newest.data), newest.lsn, list(newest.log)
store.fence_epoch = 2 # 提升 fencing token
print(f" 故障切换完成：{newest.name} 以 epoch2 成为新 primary（lsn={newp.lsn}）")
for b in backups:
if b is newest:
continue
missing = [r for r in newp.log if r[0] > b.lsn]
for r in missing:
b.apply_replicated(*r)
print(f" catch-up：{b.name} 从新 primary 的日志补齐 {len(missing)} 条更新 -> lsn={b.lsn}")
return newp
def demo_split_brain(fencing):
print(f"\n--- 脑裂实验（fencing {'开启' if fencing else '关闭'}）："
f"旧 primary 复活并继续接受写")
store = FencedStore(fencing=fencing)
store.fence_epoch = 2 # 集群已进入 epoch 2
old = Replica("旧 primary(epoch1)", 1, store)
new = Replica("新 primary(epoch2)", 2, store)
old.data, new.data = {"k1": "v1"}, {"k1": "v1"}
old.write("k1", "ZOMBIE") # 旧 primary 以为自己还是主
new.write("k1", "NEW")
zombie_applied = old.data["k1"] == "ZOMBIE"
print(f" 旧 primary 认为 k1 = {old.data['k1']}，新 primary 认为 k1 = {new.data['k1']}")
if zombie_applied:
print(" => 分歧（脑裂！）：旧主的写生效了，两个主各执一词，客户端读到什么都看运气")
else:
print(f" => 无分歧：旧主的写被 fencing 拒绝（被拒 {old.rejected} 次），"
f"只有新 primary 的写生效")
return (not zombie_applied), old.rejected
def main():
print("=" * 84)
print("实验一：同步复制 vs 异步复制 —— 写延迟与 RPO")
print("=" * 84)
res = {}
for mode in ("sync", "async"):
avg, lost, primary, backups, newest, store = run_replication(mode)
newp = failover(primary, backups, newest, store)
res[mode] = (avg, len(lost), newp.lsn, newp.data)
print(f" 故障切换后新 primary 的数据: {newp.data}")
print("\n" + "=" * 84)
print("实验二：脑裂与 fencing")
print("=" * 84)
no_div_prevented, rej_no = demo_split_brain(fencing=False)
yes_div_prevented, rej_yes = demo_split_brain(fencing=True)
print("\n" + "=" * 84)
print("汇总对比表")
print("=" * 84)
print(" +----------------+------------------+------------------+")
print(" | 指标 | 同步复制 | 异步复制 |")
print(" +----------------+------------------+------------------+")
print(f" | 平均写延迟 | {res['sync'][0] * 1000:8.2f} ms | {res['async'][0] * 1000:8.2f} ms |")
print(f" | 崩溃丢失更新数 | {res['sync'][1]:8d} 次 | {res['async'][1]:8d} 次 |")
print(f" | RPO | 0（不丢数据） | > 0（丢数据） |")
print(f" | 故障切换后状态 | lsn={res['sync'][2]:<12d} | lsn={res['async'][2]:<12d} |")
print(" +----------------+------------------+------------------+")
print(" 写延迟按'客户端一次写'统计；同步模式必须等 2 个 backup 确认，"
"延迟由最慢的副本决定。")
print(f" 脑裂：关闭 fencing => 旧主的写生效、发生数据分歧 = {not no_div_prevented}；"
f"开启 fencing => 旧主的写被拒 {rej_yes} 次、分歧被阻止 = {yes_div_prevented}")
assert res["sync"][1] == 0 and res["async"][1] > 0
assert not no_div_prevented and yes_div_prevented and rej_yes > 0
print("\n结论：同步复制用写延迟换 RPO=0；异步复制用 RPO>0 换低延迟；"
"fencing token 是防止脑裂期数据分歧的必要手段。")
if __name__ == "__main__":
main()
【代码做什么？】
run_replication(mode)：primary 接受 5 次写；同步模式下每次写都wait到所有 backup 的lsn追平（因此每次都要等 30 ms 的传播延迟），异步模式把更新丢进queue.Queue后立即返回。- 写满 5 次后设置
crashed事件并让复制线程退出——队列里还没传出去的更新就此永久消失，这就是崩溃。 - 打印每个副本的
lsn与数据，取 LSN 最大者晋升，并计算lost = [r for r in primary.log if r[0] > newest.lsn]，直接用条数给出 RPO。 failover()：新 primary 继承最新 backup 的状态，把store.fence_epoch提升到 2，然后让落后的 backup 从新 primary 的日志补齐缺失更新（catch-up）。demo_split_brain(fencing)：让”旧 primary（epoch 1）”与”新 primary（epoch 2）”各自写k1。关闭 fencing 时两者的写都生效 ⇒ 数据分歧；开启 fencing 时旧主的写被存储层拒绝 ⇒ 无分歧。- 关键输出：
--- 模式 = ASYNC（primary 接受 5 次写后崩溃） backup1: lsn=1，data={'k1': 'v1'} 崩溃时尚未传播的更新: [(2,'k2','v2'), (3,'k3','v3'), (4,'k1','v4'), (5,'k2','v5')] => RPO = 4 次写 --- 模式 = SYNC backup1: lsn=5，data={'k1': 'v4', 'k2': 'v5', 'k3': 'v3'} => RPO = 0 次写 | 平均写延迟 | 30.93 ms（同步） | 0.02 ms（异步） | 脑裂实验（fencing 关闭）：旧 primary 认为 k1 = ZOMBIE，新 primary 认为 k1 = NEW => 数据分歧 脑裂实验（fencing 开启）：旧 primary 的写被拒绝（epoch 1 < 当前 2） => 无分歧
【分布式机制透视】
- 延迟与 RPO 的量化对照：同步模式的平均写延迟 30.93 ms ≈ 一次传播延迟（因为客户端必须等最慢的 backup），异步模式 0.02 ms（只等本地执行）。代价是异步模式在同样的崩溃下丢了 4 次已确认的写。这组数字就是 20.2.6 权衡表的实验版本。
- 故障切换的正确性依赖 LSN 的可比性：选主用的是
argmax(lastLSN)。这在单主复制下正确，因为 backup 的历史一定是主日志的前缀；一旦允许多主写，就必须引入版本向量或共识，代码里用注释与 20.2.8”难点一”提醒了这一点。 - fencing 必须由被写方执行：
FencedStore.accept(epoch)是”存储层”的检查，而不是旧主”自觉”。这是本实验最重要的教学点——如果只让旧主自己判断”我是不是还被信任”，那么在脑裂窗口里它一定会认为自己还是主。 - catch-up 与更新历史：
failover()之所以能用”新 primary 的 log 减去 backup 的 lsn”来补齐，是因为 primary 保留了历史；一旦历史被截断，就只能传快照（对应 Raft 的InstallSnapshot）。
【与理论的对应】 | 代码位置 | 对应理论 | |—|—| | dedup/lsn 的设计意图（示例一中体现，此处由 log 承担） | 20.3.1 的安全性 1/2：按 LSN 顺序应用 ⇒ 单拷贝可串行化；按 rid 去重 ⇒ at-most-once | | 同步 vs 异步的延迟与丢失对比 | 20.2.6 权衡表；RPO 的定义（20.2.16） | | argmax(lastLSN) + store.fence_epoch 提升 | 20.2.8 的选主四步与”定序必须确定” | | fencing 关闭/开启的两组结果 | 脑裂（split-brain）与 fencing token/epoch 的必要性 | | 旧 primary 恢复后”降级为 backup”（代码注释与 recover 分支） | 20.2.8 的”(4) Primary 恢复后”：绝不能让旧主以旧身份回来，否则数据回退 |
20.5 性能与可扩展性分析
20.5.1 2PC 的延迟与消息开销分解
设参与者数为 $N$，单次单向网络延迟为 $d$，一次日志落盘（fsync）为 $f$：
\[T_{\text{2PC}} \approx \underbrace{2d}_{\text{阶段1: PREPARE}}+\underbrace{2d}_{\text{阶段2: 决定}} + \underbrace{(2\sim4)f}_{\text{协调者+参与者日志}} = 2\,\text{RTT} + O(f)\]| 组成部分 | 典型量级（同机房 SSD） | 典型量级（跨地域） | 备注 |
|---|---|---|---|
| 1 个 RTT（同机房） | 0.2~1 ms | 40~250 ms | 跨大西洋 ~80 ms、跨太平洋 ~150 ms |
| 1 次 fsync（本地 SSD） | 0.1~1 ms | — | 若用网络存储/云盘（EBS 等）可达 1~10 ms |
| 2PC 总延迟（无故障） | 约 1~5 ms | 约 100~500 ms | 跨洲事务的主要成本就是 2 个 RTT |
| 消息条数 | $2N$（无 ACK 优化）~ $4N$ | 同左 | 只读优化可把 $N$ 降为”有写的分片数” |
| 锁持有时间 | $\ge 2\,\text{RTT} + 2f$ | 可达数百 ms | 决定并发度的关键指标 |
必须记住的两条工程结论：
- 日志落盘（fsync）常常是主要瓶颈，而不是网络。在同机房场景下，4 次 fsync（每次 0.5 ms）就可能与 2 个 RTT 相当。因此 2PC 的优化重点往往是减少 fsync 次数（批量提交、组提交 group commit、并行 fsync）与只读优化。
- 2PC 的真正代价是”锁持有时间的延长”。一个事务在
IN_DOUBT期间持有全部写锁，其时长是 $\ge 2$ RTT（无故障）或无上界（协调者故障）。锁时间是并发度的倒数：若一次 2PC 事务持锁 5 ms，则单个热点对象最多支持 200 事务/秒；这解释了为什么”长事务 + 2PC”是数据库性能事故的常见配方。
20.5.2 阻塞窗口的长度（本章最需要被量化的风险）
\[T_{\text{block}} = \begin{cases} 0, & \text{协调者未崩溃} \\ \text{选举超时（几十~几百 ms）}, & \text{协调者被共识复制（Raft/Paxos）} \\ \text{协调者恢复时间} = \text{分钟} \sim \text{小时}, & \text{协调者是单点、需人工介入} \\ \infty, & \text{协调者永久失效（磁盘损坏且日志无备份）} \end{cases}\]阻塞的影响面远大于它本身：被阻塞的事务持有锁 ⇒ 依赖这些锁的事务被阻塞 ⇒ 级联（20.4.1 的代码把”3 个 RM × 3 把锁 = 6 个其他事务被阻塞”直接打印出来）。因此评估 2PC 风险的正确指标不是”协调者多久恢复”，而是”协调者恢复期间有多少事务会被挂住”。
20.5.3 三种方案的全面对比
| 维度 | 2PC | 3PC | 共识驱动的原子提交（Spanner 式） |
|---|---|---|---|
| 无故障延迟 | 2 RTT + fsync | 3 RTT + fsync | 2 RTT（分片间）+ (2~4) RTT（组内共识）+ $\epsilon$ |
| 消息复杂度 | $O(N)$ | $O(N)$ | $O(N \times \text{组大小})$ |
| 参与者状态数 | 3（INIT/IN_DOUBT/决定） | 4+（加 PRECOMMITTED） | 3（与 2PC 相同，多一次共识写入） |
| 协调者故障 | 阻塞（窗口无上界） | 不阻塞（无分区假设下） | 不阻塞（窗口 = 一次选举超时） |
| 网络分区下的安全性 | 保持原子性 | 可能违反原子性 | 保持原子性（分片内多数派；跨分片仍需 2PC，但决定与准备都已复制） |
| 决议规则 | 全体一致（一票否决） | 全体一致 | 全体一致 + 多数派持久化 |
| 实现复杂度 | 低 | 中（终止协议难做对） | 高（共识 + 事务层 + 时钟/时间戳） |
| 工业采用 | 广泛（XA、Percona XtraDB、早期 MongoDB） | 极少 | 主流（Spanner、CockroachDB、TiDB、OceanBase 等） |
20.5.4 真实系统中的延迟数据与实践（量级参考）
以下数字是公开资料中的典型量级（会随部署拓扑、硬件、负载大幅变化，仅用于建立直觉）：
| 系统 / 场景 | 事务或复制的延迟量级 | 说明 |
|---|---|---|
| 同机房 2PC（XA、Percolator 风格） | 1~5 ms | 主要是 2 个 RTT + fsync；组提交下可更低 |
| Spanner 同区域（region 内 Paxos + 2PC） | 10~20 ms | 含 Paxos 提案与 TrueTime 等待 $\epsilon$（论文给出 $\epsilon$ 约 1~7 ms） |
| Spanner 跨洲（如美东↔西欧） | 100~300 ms | 2 个跨洲 RTT 已经 160 ms 起，再加共识与 $\epsilon$ |
| CockroachDB / TiDB 同城 | 10~50 ms | Raft 提案 + HLC；跨 region 明显上升 |
Cassandra LOCAL_QUORUM 写（无事务） | 1~5 ms | 纯 quorum 复制，无原子提交（Lecture 9） |
| MySQL 半同步复制写（同城） | 1~3 ms | 等 1 个从库 ACK |
| MySQL 异步复制写 | 0.1~0.5 ms | 不等从库；RPO > 0 |
| Raft 选举超时 | 150~300 ms（默认） | 决定了”共识驱动方案”的阻塞窗口下界 |
| GFS/HDFS NameNode 故障恢复（早期） | 分钟~小时级 | 元数据单点，RTO 的经典反例 |
可扩展性瓶颈（按重要性排序）：
- 协调者的吞吐上限：所有跨分片事务都要经过协调者，它既是消息汇聚点也是日志写入点 ⇒ 分片数越多、跨分片事务比例越高，协调者越先饱和。
- 跨分片事务的比例：2PC 的成本与参与者数 $N$ 成正比，而 $N$ 取决于数据分区设计。工程上最有效的优化不是改协议，而是改键设计以减少跨分片事务（例如把同一用户的数据放到同一分片、让事务尽量单分片）。
- fsync 吞吐：每个事务至少 2 次 fsync（协调者 + 参与者各 1 次以上），IOPS 是硬上限；靠组提交（group commit）、批量 WAL、日志落 NVMe 缓解。
- 长事务/热点：锁持有时间长 ⇒ 冲突率上升 ⇒ 重试 ⇒ 又拉长延迟；Saga/补偿事务正是为规避长事务而生。
20.6 关键要点
- 复制 = 用一致性成本换可用性与性能：$k$ 副本把可用性从 $1-f$ 提升到 $1-f^k$，但一致性的维护成本（同步延迟、选举、追赶、防脑裂）随之上升。副本数不是越多越好，而是”刚好能容忍目标故障数”最好。
- 主动复制与被动复制的分界在”谁执行请求”：主动复制多播请求（必须全序 + 确定性），被动复制单播给 primary、再传播结果（需要选主与追赶）。两者的共同理论基础是复制状态机：相同初态 + 相同顺序的输入 ⇒ 相同状态。
- 被动复制的三大工程难点：请求去重（FE 超时会重发 ⇒ at-least-once ⇒ 必须按 rid 去重）、选主必须选最新（用 LSN 比大小，且定序必须确定）、脑裂必须用 fencing 防止（epoch/term 由被写方强制执行，不能靠旧主自觉）。
- 2PC = 用 2 个 RTT 换取原子性：投票阶段（谁都不能先提交）+ 决定阶段（决定必须落盘后再广播）。它保证原子性（一票否决 + 决定唯一 + 决定持久），但在协调者故障时阻塞——因为协调者是单点且不复制的。
- 阻塞是”结构性”的，不是实现瑕疵：20.3.4(B) 给出了构造性证明——处于
IN_DOUBT的参与者无法区分”协调者决定提交”与”协调者决定中止”，因此任何单方面决定都可能破坏原子性。非阻塞的原子提交需要共识。 - 分布式系统黄金法则（本章的主旋律）：
2PC 用两个 RTT 换来了原子性，但代价是它在 coordinator 故障时会阻塞——因为它依赖一个单点的、不复制的一致性决策者。现代系统用共识来复制这个决策者，从而在保留原子性的同时消除了阻塞。这个演进过程是分布式系统设计的绝佳案例：把单点替换成多数派，就能把”可能永久阻塞”变成”短暂选举窗口”。
- 3PC 是一个有价值的历史教训：它证明了”可以做到非阻塞”，但也证明了代价是把不可能性从活性搬到了安全性——分区下一部分提交、一部分中止。它几乎不被工业界采用，但它是理解”安全性与活性不可兼得”的最佳教材。
20.7 常见陷阱与注意事项
- 把 2PL 与 2PC 混为一谈。 ✗”用了两阶段锁，所以跨服务器的事务是原子的。” —— 2PL 保证的是隔离性（并发事务串行等价），它完全不涉及”多个服务器是否都提交”；2PC 保证的是原子性（跨站点 all-or-nothing）。正确做法：本地用 2PL/MVCC，跨分片用 2PC，二者叠加使用。
- 认为”投了 YES 的参与者超时后可以自己中止”以避开阻塞。 ✗”反正协调者可能已经挂了，我先回滚释放锁吧。” —— 若协调者其实已经决定提交且另一个参与者已提交，你的中止就破坏了原子性。正确做法：
IN_DOUBT期间只能等待（或向协调者轮询），要靠 presumed-abort/read-only 优化与”复制协调者”来缩短阻塞，而不是靠参与者自决。 - 把”去重”当作可选优化。 ✗”请求超时重发没什么大不了，操作反正很快。” —— FE 重发使语义变成 at-least-once，非幂等操作（
x = x + 1、扣库存）会被执行两次，产生静默的数据错误。正确做法：要么让操作幂等，要么在 primary 侧按请求 ID 去重，且去重表必须与状态一起持久化（否则崩溃恢复后退化）。 - 只比较 LSN 就以为选出了正确的主（多主场景）。 ✗”谁的 LSN 大谁最新。” —— 这只在单主复制下成立（此时备份历史是主日志的前缀）。多主或双向复制时两个副本可能”各有部分更新”，必须用版本向量/依赖集，或者干脆用共识选主。此外，LSN 相同时必须有确定的 tie-break（
(LSN, term, nodeID)），否则不同节点可能选出不同的主。 - 靠”旧主自杀”来防脑裂。 ✗”primary 收不到心跳就自己退出，不就不会脑裂了吗？” —— 旧主可能恰好卡在”收不到心跳但也没死透”的窗口（GC 停顿、虚拟化挂起、网络分区）。正确做法：让被写的一方（存储/仲裁多数派）用 fencing token 拒绝过期 epoch 的写，把安全边界放在存储侧。
- 认为 3PC 是”更好的 2PC”。 ✗”3PC 非阻塞，所以应该用它替代 2PC。” —— 3PC 多一个 RTT，且在网络分区下会违反原子性（20.4.2 的实验给出了反例）。正确做法：要非阻塞就用共识复制协调者的方案；3PC 的价值主要是教学。
- 忽略”日志落盘”这个延迟大头。 ✗”2PC 的延迟就是 2 个 RTT。” —— 协调者与参与者各有 1~2 次 fsync，同机房下这部分可能与网络相当，网络存储（云盘）下甚至更大。正确做法：统计延迟时必须把 fsync 计入，并用组提交/批量写入降低其频次。
- 把只读参与者拖进
IN_DOUBT。 ✗”所有参与者统一处理，代码简单。” —— 只读分片没有任何要提交的更新，让它们投票并等待决定，白白扩大阻塞面并增加协调者的等待时间。正确做法：实现 read-only 优化（回复READ_ONLY并立即释放锁），这在读多写少的真实负载中收益巨大。 - 在异步复制下把”确认成功”当作”数据安全”。 ✗”客户端收到 200 就说明数据不会丢。” —— 异步复制的 primary 在确认后崩溃会让这些写永久消失（RPO > 0），且客户端曾”看见”它们。正确做法：按数据的价值选择同步/半同步；把 RPO 写进 SLA 并在架构评审时明确。
20.8 思考题（带答案）
题 1（概念辨析）：有人说：”我们的系统用了 Paxos，所以跨分片事务不需要 2PC 了。”这句话对吗？请说明 Paxos 与 2PC 各自解决什么问题，以及为什么现代系统（Spanner）两者都用。
答：不对。Paxos 解决的是在一个副本组内对某个值达成一致（多数派即可决定），它保证的是”即使少数副本故障，组内仍能就某一个决定达成一致且不矛盾”。但原子提交的语义是全体一致 + 一票否决：只要有一个参与者说”我本地提交不了”（约束冲突、磁盘满、锁冲突），全局就必须中止。多数派投票无法表达”任何一个人反对就全体中止”——讲义的原话正是 “But need to ensure that if any server votes No, everyone aborts”。 因此 Spanner 的做法是三层叠加：分片内部用 Paxos 复制（容错、不丢数据、leader 故障可快速切换），跨分片用 2PC 做原子提交（表达一票否决），并且把 2PC 协调者的决定也写进一个 Paxos 组（消除协调者单点导致的阻塞）。一句话：Paxos 让”决定”变得可靠，2PC 让”决定”的语义成为 all-or-nothing；两者解决的不是同一个问题。
题 2（计算推演）：某跨分片事务涉及 $N=5$ 个分片，单向网络延迟 $d=30$ ms（同城跨机房），每次 fsync $f=1$ ms，协调者与每个参与者各需 2 次 fsync。回答： (1) 无故障时 2PC 的理想延迟是多少？(2) 若把其中 2 个分片改成只读，延迟是否下降？(3) 若协调者在收到全部 YES 之后、写决定之前崩溃，运维 20 分钟后才重启它，这段时间内系统有何后果？(4) 若改成”共识复制的协调者”（其所在分片 Raft 选举超时 300 ms），阻塞时间变成多少？
答： (1) 阶段 1：PREPARE 并行广播（$d$）+ 收集投票（$d$）= 1 个 RTT = 60 ms；协调者此时写 2 次 fsync（投票记录 + 决定）= 2 ms；阶段 2：广播决定（$d$）+ 收集 ACK（$d$）= 60 ms；参与者各 2 次 fsync，与网络并行，额外约 2 ms。故 $T \approx 60 + 60 + 2 + 2 \approx 124$ ms。（若 ACK 不等，则约 92 ms。） (2) 延迟基本不降（只读优化减少的是参与者的阻塞面与协调者的等待人数，而这里的延迟由最慢的 RTT 与 fsync 决定）；但在”部分参与者变慢/崩溃”的场景下，只读优化能显著降低阻塞风险与协调者的等待时间。这正是它的价值所在：它优化的是可用性与阻塞面，而不是无故障延迟。 (3) 所有投了 YES 的参与者都会停在 IN_DOUBT：持有全部写锁、不能提交也不能中止；依赖这些对象的事务全部被阻塞，并沿依赖链级联阻塞；20 分钟内该数据集上的并发度接近 0，且若这些锁又被其他事务持有，可能蔓延到其他对象。恢复后协调者从 WAL 读出”全部 YES 已记录、无决定”，做出决定并重发，系统才恢复。这就是 2PC 阻塞的真实代价。 (4) 阻塞窗口从 20 分钟缩短到约 300 ms（一次选举超时）+ 新 leader 重放决定并广播的时间（约 1 个 RTT）。减少约 4 个数量级——这就是”把单点换成多数派”的收益。
题 3（错在哪里）：某同学实现被动复制时，为了让 FE 的重试更可靠，把 FE 的超时设得很短，并且在超时后立即把请求改发给另一个 backup。他认为”两个副本都执行过，总有一个是对的”。请指出这个设计的错误，并给出正确做法。
答：错误至少有三处： ① 写被发给了 non-primary：被动复制中只有 primary 才能决定更新顺序，把写发给 backup 会造成两个副本各自执行、顺序不同（等价于多主写），LSN/版本无法比较，两个副本永久分歧，还会让故障切换时”谁是新的”失去良定义。 ② 重复执行：同一条请求被两个副本执行 ⇒ 若不是幂等操作（x=x+1、扣库存），结果被算了两遍；即便两个副本都执行，也没有机制保证它们只算一次。FE 的重试必须携同一个 rid 并由 primary 去重，而不是”换个副本再试”。 ③ 把超时当成故障判定：短超时会把”primary 稍慢”误判为”primary 故障”，从而触发不必要的故障切换与脑裂风险（Lecture 7：异步系统中无法区分慢与死）。 正确做法：(a) FE 只把请求发给 primary（地址从配置服务读）；(b) 超时后用同一个 rid 重发给 primary（或重新读配置，但必须保证同一 rid 不会在多主上同时生效）；(c) primary 维护持久化的去重表（rid → 结果），重复请求直接返回缓存结果；(d) 如果确实怀疑 primary 故障，必须走正规的故障切换流程：FD 判定 → 由配置服务以多数派选主并提升 epoch → FE 统一重定向 → 旧主被 fencing 拒绝写入。
题 4（不可能性风格）：请解释：为什么”在异步系统里既能保证原子性、又保证不阻塞的原子提交协议”是不存在的？请给出与你答案对应的构造性论证思路。
答：论证思路（对照 20.3.4(B)）： 考虑一个参与者 $P$ 已投 YES 并处于 IN_DOUBT，而协调者崩溃。要让协议非阻塞，$P$ 必须在有限时间内自行做出决定。但存在两个对 $P$ 而言本地不可区分的执行：
- $E_1$：协调者已决定 COMMIT，并把
GLOBAL_COMMIT发给了另一个参与者 $Q$（$Q$ 已提交）； - $E_2$：协调者已决定 ABORT（因为有别的参与者投了 NO），并把
GLOBAL_ABORT发给 $Q$。 由于网络是异步的（消息延迟无上界），$P$ 在这两个执行中收到的消息序列可以完全相同（发给它的消息恰好还在路上或已丢失）。若 $P$ 在有限时间内选择 COMMIT，则在 $E_2$ 中它与 $Q$ 的决定矛盾（违反原子性）；若它选择 ABORT，则在 $E_1$ 中与 $Q$ 矛盾。既然任何有限时间内的决定都会在某个执行中违反原子性，而”等待”又要求协调者最终可达（这不是异步系统能保证的），那么”有限时间终止 + 原子性”二者必损其一。 换言之：在异步、允许故障的系统中，非阻塞的原子提交等价于让参与者们自行达成共识，而 FLP 结论（Lecture 15/17）告诉我们这在异步系统中不可能。 因此工程上的出路只有两条：(a) 引入部分同步假设（超时 + 故障检测器），把”等待的边界”变成概率性保证；(b) 引入共识（多数派复制协调者），把”决定”的存储从单点搬到多数派上——这正是 Spanner/CockroachDB/TiDB 选择的道路。