【分布式系统百科】Paxos：从 Single-Decree 到 Multi-Paxos 的工程之路

你有五台服务器，需要让它们对”下一条写入是什么”达成一致。网络会丢包、会延迟、会乱序；任意一台服务器随时可能宕机重启。你不能依赖任何一台单机的判断——因为它可能已经挂了，你还不知道。

这就是共识（Consensus）问题。1990 年 Leslie Lamport 提交了一篇用虚构的希腊议会类比来描述共识算法的论文，审稿人没看懂，退回。1998 年重新发表为《The Part-Time Parliament》。2001 年他又写了《Paxos Made Simple》，开篇第一句：“The Paxos algorithm, when presented in plain English, is very simple.” 这句话的讽刺意味一直延续到今天——二十多年来，Paxos 是被引用最多、也是被误解最多的分布式算法。

Google 内部用 Paxos 构建了 Chubby 锁服务。2007 年 Chandra、Griesemer 和 Redstone 发表了《Paxos Made Live》，文中坦承：从 Paxos 论文到生产系统的距离，远比任何人预想的要大。他们花了数年时间填坑，其间发现的 bug 涉及磁盘故障处理、成员变更、快照交互等方方面面。

本文的目标不是再写一遍”Paxos 很简单”。而是把 Single-Decree Paxos 的精确语义和安全性证明说清楚，然后推导 Multi-Paxos 的工程扩展，分析已知的实现陷阱，最后给出一份可以编译和测试的 Go 实现。

一、Single-Decree Paxos：对一个值达成共识

Single-Decree Paxos 解决的问题非常精确：一组进程（Process）需要选定（Chosen）恰好一个值（Value），一旦选定就不再更改。

1.1 三个角色

Paxos 定义了三个逻辑角色。在实际部署中，一个物理节点通常同时扮演多个角色。

提议者（Proposer）：发起提案（Proposal），试图让一个值被选定。每个提案包含一个全局唯一的提案编号（Proposal Number） n 和一个值 v，记作 (n, v)。提案编号必须满足全序关系。实践中常用 (sequence, node_id) 组合来生成全局唯一的递增编号。

接受者（Acceptor）：对提案进行投票。Acceptor 是 Paxos 的”记忆”——算法的安全性依赖 Acceptor 记住自己做过的承诺。一组 Acceptor 中的多数派（Majority / Quorum） 构成决策基础。对于 2f+1 个 Acceptor，多数派至少需要 f+1 个。

学习者（Learner）：获知已被选定的值。Learner 不参与投票，只被动地从 Acceptor 处得知结果。

1.2 两阶段协议

Paxos 分两个阶段运行。每个阶段包含一个请求和一个响应，共四种消息。

Phase 1a — Prepare：Proposer 选择一个新的提案编号 n，向至少多数派 Acceptor 发送 Prepare(n) 请求。

Phase 1b — Promise：Acceptor 收到 Prepare(n) 后：

• 如果 n 大于该 Acceptor 已经响应过的所有 Prepare 请求的编号，则回复 Promise(n, accepted_proposal)，其中 accepted_proposal 是该 Acceptor 已经 Accept 过的编号最高的提案 (n_a, v_a)，如果没有则为空。同时，Acceptor 承诺不再接受任何编号小于 n 的提案。
• 否则，忽略该请求（或回复 NACK）。

Phase 2a — Accept：如果 Proposer 收到了多数派 Acceptor 的 Promise 回复，它发送 Accept(n, v) 请求，其中：

• 如果所有 Promise 回复中都没有已接受的提案，v 可以是 Proposer 自己想提议的任意值。
• 如果有 Promise 回复包含已接受的提案，v 必须是编号最高的那个已接受提案的值。这一条是 Paxos 安全性的关键。

Phase 2b — Accepted：Acceptor 收到 Accept(n, v) 后：

• 如果 n 不小于该 Acceptor 已经承诺过的最高编号，则接受该提案，将 (n, v) 持久化，回复 Accepted(n, v)。
• 否则，拒绝。

当多数派 Acceptor 接受了同一个提案 (n, v) 时，值 v 就被选定（Chosen）了。

下图展示了一次完整的消息流：

1.3 Acceptor 的持久化状态

每个 Acceptor 需要在稳定存储（Stable Storage）上维护以下状态，以保证宕机重启后协议的安全性：

这三个值必须在回复任何消息之前持久化到磁盘。如果在 Promise 回复之后、写入磁盘之前宕机，重启后可能违反承诺，导致安全性被破坏。这是生产系统中最常见的 Paxos 实现 bug 之一。

1.4 安全性证明：为什么选定的值不会改变

Paxos 需要保证的核心安全性属性：

P2c（Safety）：如果一个值 v 在提案编号 n 下被选定，那么任何编号 n' > n 的提案，其值也必须是 v。

证明思路是矛盾法加归纳法的结合。

定理：如果提案 (n, v) 被选定（即被多数派接受），则对于所有 n' > n，任何被发起的提案 (n', v') 都有 v' = v。

证明（强归纳法）：

假设对所有编号 m，n ≤ m < n'，如果提案 (m, v_m) 被发起，则 v_m = v。现在证明编号为 n' 的提案也必须提议值 v。

1. 提案 (n, v) 被选定意味着存在一个多数派 S 接受了它。
2. Proposer 要发起提案 (n', v')，它必须先在 Phase 1 收到某个多数派 S' 的 Promise 回复。
3. 任意两个多数派 S 和 S' 必有交集（这是多数派的基本性质）。设 a 是 S ∩ S' 中的一个 Acceptor。
4. Acceptor a 接受了 (n, v)（因为 a ∈ S），并且回复了 Promise 给提案 n'（因为 a ∈ S'）。
5. a 回复 Promise 给 n' 时，它报告了自己已接受的编号最高的提案。由于 n' > n，Promise 回复中报告的已接受提案的编号至少为 n。
6. 按照 Phase 2a 的规则，Proposer 必须采用 Promise 回复中编号最高的已接受值。
7. 如果 Promise 回复中编号最高的已接受提案编号 m 满足 n ≤ m < n'，根据归纳假设，该提案的值就是 v。
8. 因此 v' = v。

这个证明的关键在于两个多数派必有交集。这是 Paxos 正确性的几何基础：2f+1 个 Acceptor 中的任意两个 f+1 的子集，至少共享一个成员。这个共享成员既参与了旧值的 Accept，又参与了新 Prepare 的 Promise，从而把旧值”传递”给新的 Proposer。

需要特别注意的是，以上证明保证的是 Safety——选定的值不会改变。Paxos 并不保证值一定能被选定（Liveness），这一点在后文”Dueling Proposers”一节会详细讨论。

1.5 几个容易混淆的细节

Proposer 不知道值何时被选定。Proposer 收到多数派的 Accepted 回复后，可以推断值已被选定。但如果网络延迟导致部分 Accepted 丢失，Proposer 无法区分”值已选定但我没收到回复”和”值未选定”。正确的做法是重试（用相同编号重新发起 Accept）或重新开始新一轮。

Acceptor 也不知道值何时被选定。单个 Acceptor 只知道自己接受了什么，不知道其他 Acceptor 的状态。“选定”是一个全局概念，需要有人统计多数派的 Accepted。

Learner 如何得知选定的值：最简单的方式是每个 Acceptor 在接受提案后，把 Accepted 消息发给所有 Learner。Learner 统计到多数派的 Accepted 后，就知道值已被选定。代价是 O(Acceptors × Learners) 条消息。另一种方式是选一个”Distinguished Learner”作为中转。

提案编号的生成：编号需要全局唯一且递增。常见做法是 (round_number, node_id)，按字典序比较。round_number 递增保证同一节点的编号递增，node_id 保证不同节点的编号不冲突。

二、Multi-Paxos：从单值到日志

Single-Decree Paxos 只能就一个值达成共识。实际系统需要的是一系列值的共识——一个有序的复制日志（Replicated Log）。客户端不断提交命令，系统需要让所有副本以相同的顺序执行这些命令。

Multi-Paxos 的核心思路：为日志中的每个槽位（Slot）运行一个独立的 Single-Decree Paxos 实例。Slot 1 的 Paxos 选定第一条命令，Slot 2 的 Paxos 选定第二条命令，以此类推。

Lamport 在原始论文中只是简略提到了这个扩展。他从未发表过 Multi-Paxos 的完整协议规范。这正是后来许多工程困难的根源——每个实现者都要自己”发明”剩下的部分。

2.1 Leader 选举阶段（Phase 1 批量执行）

Multi-Paxos 的运行可以清晰地分为两个阶段：Leader 选举阶段和稳态复制阶段。理解这两个阶段的分界是理解 Multi-Paxos 性能特征的关键。

Leader 选举阶段的目标：通过某种机制（租约、心跳、超时）选出一个稳定 Leader（Distinguished Proposer），并让该 Leader 完成对所有 Slot 的 Phase 1。

具体流程：

1. 候选 Leader 选择一个足够高的提案编号 n。
2. 向所有 Acceptor 发送一次批量 Prepare——这个 Prepare 覆盖所有尚未选定的 Slot。
3. 多数派 Acceptor 回复 Promise，报告每个 Slot 上已接受的最高提案。
4. Leader 根据回复，对每个有已接受值的 Slot 执行一轮 Accept（使用学到的值）；对空 Slot 提议 no-op 或等待新命令。

这个阶段的代价：1 个额外 RTT（Prepare/Promise 往返），加上填补空洞所需的 Accept 轮次。在 Leader 切换不频繁的系统中，这个代价被摊薄到可以忽略。

Leader 选举阶段的典型触发条件：

• 当前 Leader 的心跳超时（Follower 在 election_timeout 内未收到心跳）。
• 新节点加入集群，发起更高编号的 Prepare（较少见，通常通过配置变更处理）。
• 网络分区恢复后，两侧的 Leader 需要重新协商。

2.2 稳态复制阶段（仅 Phase 2）

一旦 Leader 选举完成，系统进入稳态。这是 Multi-Paxos 的正常工作模式，绝大多数时间都运行在这个阶段。

在稳态下，Leader 已经通过 Phase 1 获取了提案权，后续新 Slot 的共识只需要 Phase 2：

稳态消息流（1 RTT）：
Client → Leader: Request(cmd)
Leader → Acceptors: Accept(slot, n, cmd)     [广播]
Acceptors → Leader: Accepted(slot, n, cmd)   [多数派回复]
Leader → Client: Response

Phase 1 被完全跳过——这是 Multi-Paxos 相对 Single-Decree Paxos 的核心优化。每次共识只需 1 RTT，和 Raft 在正常情况下的延迟相同。

这个优化的正确性来自一个观察：Phase 1 的目的是让 Proposer”夺取”提案权并了解已有的最高提案。如果 Leader 是唯一的 Proposer，没有其他人竞争，那么 Phase 1 的结果在后续 Slot 中仍然有效。只有当新的 Leader 出现（使用更高的编号发起 Prepare）时，旧 Leader 的 Phase 1 才失效。

稳态的打破条件：当另一个 Proposer 使用更高编号的 Prepare 抢占了提案权时，当前 Leader 的 Accept 请求会被 Acceptor 拒绝。此时系统退回到 Leader 选举阶段。这就是 Multi-Paxos 在两个阶段之间的切换点。

2.2 空洞处理

多个 Proposer 并发工作时（或者 Leader 切换时），日志中可能出现空洞（Hole）：Slot 5 已选定，Slot 6 未选定，Slot 7 已选定。

新 Leader 在 Phase 1 之后会发现这些空洞。处理方式是对每个未选定的 Slot 执行一轮完整的 Paxos——使用 Phase 1 中学到的已接受值（如果有），或者提议一个 no-op（空操作） 命令。

对于状态机来说，no-op 不改变状态，只是占据一个 Slot 位置，确保日志连续。没有这个机制，后续的 Slot 就无法 apply，状态机会卡住。

2.3 配置变更

Paxos 原始论文没有详细讨论集群成员变更。实际上，配置变更（Configuration Change）是 Multi-Paxos 工程实现中最复杂的部分之一。

Lamport 在后续工作中提出了一种方法：把配置本身作为日志中的一条特殊命令。Slot i 中的配置变更命令规定”从 Slot i + α 开始，使用新配置”。α 是一个足够大的延迟窗口，保证在新配置生效时，所有节点都已经看到了这条配置变更命令。

这种方式的问题是 α 的选择很微妙。太小可能导致部分节点还在用旧配置投票，太大会导致变更延迟过高。而且如果在延迟窗口内又发生了另一次配置变更，推理正确性会变得非常困难。

Google 的 Chubby 实现采用了一种更保守的方式：停止接受新请求，等所有正在进行的 Paxos 实例完成，切换配置，然后恢复服务。简单但会造成短暂的不可用。

相比之下，Raft 提出了更明确的 Joint Consensus 和 Single-Server Change 机制，这也是 Raft 相对 Paxos 的一个工程优势。

2.4 快照与日志压缩

日志不能无限增长。Multi-Paxos 的实现需要一种日志压缩（Log Compaction）机制：

1. 当日志增长到一定大小后，状态机对当前状态做一个快照（Snapshot）。
2. 快照完成后，快照点之前的日志可以安全删除。
3. 如果一个落后的副本需要追赶，Leader 可以直接发送快照，而不是重放全部日志。

快照的时机、与正在进行的 Paxos 实例之间的交互、快照传输的效率——这些都是论文中一笔带过但实现中非常棘手的问题。

三、Paxos 的已知问题

3.1 Dueling Proposers 与活锁

Paxos 不保证 Liveness。最经典的反例是 Dueling Proposers（对决的提议者）：

场景如下：

1. Proposer A 发起 Prepare(1)，收到多数派 Promise。
2. 在 A 发出 Accept(1, v) 之前（或之后但 Acceptor 还没处理），Proposer B 发起 Prepare(2)。
3. Acceptor 承诺了 n=2，拒绝 A 的 Accept(1, v)。
4. A 发起 Prepare(3) 反击，Acceptor 承诺了 n=3，拒绝 B 的 Accept(2, w)。
5. B 发起 Prepare(4) 再反击……

两个 Proposer 不断用更高的编号抢占对方，Phase 2 永远无法完成。协议在理论上可以无限循环，一个值也选不出来。

这不违反 FLP 不可能定理——FLP 说的就是异步系统中无法同时保证 Safety 和 Liveness。Paxos 选择了始终保证 Safety，牺牲 Liveness。

工程解决方案有两种：

方案一：选举 Leader。让同一时间只有一个 Proposer 活跃。这就是 Multi-Paxos 的做法。只要 Leader 稳定，就不会出现竞争。但 Leader 选举本身是一个共识问题——这里存在一个循环依赖。实际做法是用一个不完美的 Leader 选举（如基于超时和租约的机制），在大多数情况下保证只有一个 Leader，偶尔出现多个 Leader 时退化回基本 Paxos 的竞争模式。

方案二：随机退避（Randomized Backoff）。Proposer 在被抢占后，等待一个随机时间再重试。如果两个 Proposer 的退避时间不同，其中一个会先完成。这在概率上保证了 Liveness。Lamport 本人也推荐这种方式作为简单场景的解决方案。

3.2 性能分析

在稳态下（稳定 Leader），Multi-Paxos 的性能特征：

没有 Leader 竞争时，Multi-Paxos 的延迟下界就是一次网络往返加一次磁盘 fsync。这和 Raft 相同。

Leader 切换时的性能退化：

• 新 Leader 需要执行一次完整的 Phase 1（额外 1 RTT）。
• 需要填补所有空洞（每个空洞一轮 Paxos）。
• 在此期间新请求被阻塞。

如果 Leader 频繁切换，系统吞吐会大幅下降。极端情况下退化为 Dueling Proposers，吞吐降为零。

3.3 “Paxos 很难实现”的证据

“Paxos 很难实现”不只是一种感觉，有具体的工程证据。

Google Paxos Made Live（2007）的经验。Chandra、Griesemer 和 Redstone 在论文中记录了从 Paxos 论文到 Chubby 生产系统之间的巨大鸿沟：

1. 论文到系统的距离：“There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system.” 论文描述了一个理想化的算法，但没有涉及磁盘故障、快照、配置变更、日志压缩等实际问题。
2. Multi-Paxos 没有规范：“While Lamport briefly sketched the idea, no complete protocol specification is available.” 每个实现团队都要自己设计 Multi-Paxos 的完整协议。
3. Bug 的来源：许多 bug 来自 Paxos 算法与其他系统组件（快照、成员变更、磁盘 I/O）的交互，而不是 Paxos 算法本身。他们发现了硬盘上的数据损坏会导致 Acceptor 状态不一致的问题，最终加入了校验和（Checksum）机制。
4. 测试困难：分布式协议的 bug 往往只在特定的故障序列下触发，传统单元测试很难覆盖。他们开发了专门的确定性模拟测试框架来重放故障序列。

Raft 论文的用户研究（2014）。Ongaro 和 Ousterhout 在斯坦福大学做了一个对照实验：让两组学生分别学习 Paxos 和 Raft，然后回答理解题。结果 Raft 组的成绩显著高于 Paxos 组（中位数高 4.9 分，满分 60）。当然，这个实验衡量的是可理解性而非实现难度，但可理解性和实现正确性之间有很强的相关性。

ZooKeeper 的演进。ZooKeeper 最初基于 ZAB（ZooKeeper Atomic Broadcast）协议，这是一个受 Paxos 启发但有显著差异的协议。ZAB 的设计者 Benjamin Reed 和 Flavio Junqueira 在 2008 年的论文中明确指出，他们选择设计一个新协议而不是直接实现 Paxos，部分原因是 Multi-Paxos 的规范不够完整，难以直接用于构建主从复制系统。

这些证据共同指向一个结论：Paxos 作为理论工具是优雅的，但作为工程规范是不完整的。从论文到生产代码之间的那些”显然”的决定——Leader 怎么选、日志怎么压缩、成员怎么变更、磁盘坏了怎么办——加起来构成了比算法本身更大的工程量。

四、Paxos 变体概览

Paxos 家族有许多变体，各自针对不同的优化目标。

4.1 Cheap Paxos

Lamport 在 2004 年提出的 Cheap Paxos 旨在减少正常运行时所需的活跃服务器数量。

核心思路：使用 f+1 个主 Acceptor 和 f 个辅助 Acceptor。正常运行时只有主 Acceptor 参与投票。当某个主 Acceptor 故障时，才启用辅助 Acceptor 来恢复多数派，完成一轮配置变更后把辅助 Acceptor 再下线。

优势是正常情况下只需要 f+1 台服务器处理请求，而不是 2f+1 台。代价是故障恢复时需要额外的配置变更步骤，可用性窗口更窄。适用于成本敏感、故障率低的场景。

4.2 Disk Paxos

Gafni 和 Lamport 在 2003 年提出的 Disk Paxos 用共享磁盘替代 Acceptor 进程之间的网络通信。

场景是多个处理器共享一个 SAN（Storage Area Network）或共享磁盘系统。每个 Proposer 通过读写共享磁盘上的特定块来执行 Prepare 和 Accept 操作，而不是发送网络消息。共享磁盘提供了持久化和通信两个功能。

这种变体主要用于存储集群（如共享存储的集群文件系统）中的协调问题，在 SAN 环境下可以降低网络通信的复杂性。

4.3 Fast Paxos

Lamport 在 2006 年提出 Fast Paxos，核心目标很简单：在没有冲突时，让客户端绕过 Leader 直接提交值，把延迟从 2 个消息延迟降低到 1 个。

无冲突路径（快速路径）：

1. Leader 预先执行 Phase 1，获取提案权，然后发出一条特殊的 Accept(n, ANY) 消息——告诉 Acceptor”我允许你直接接受客户端发来的值”。
2. 客户端直接向所有 Acceptor 发送自己的值。
3. 如果足够多的 Acceptor 接受了同一个值，该值被选定。客户端只等了 1 个消息延迟（客户端 -> Acceptor -> 客户端）。

这里的关键问题是”足够多”是多少。经典 Paxos 的多数派是 f+1（在 2f+1 个 Acceptor 中），但 Fast Paxos 需要更大的快速 Quorum（Fast Quorum）。直觉上的原因是：两个并发客户端可能提交了不同的值，Leader 在恢复时需要从 Acceptor 的回复中判断哪个值”赢了”。更大的 Quorum 保证了即使有冲突，Leader 也能安全地确定正确的值。

具体来说，Fast Quorum 的大小通常为 2f+1 中的至少 2f+1 - f/2（向上取整），即大约四分之三的 Acceptor。例如在 5 节点集群（f=2）中，Fast Quorum 需要 4 个 Acceptor，而经典 Quorum 只需要 3 个。

冲突路径（退回经典 Paxos）：

如果两个客户端同时提交了不同的值，Acceptor 之间会出现分歧——一些接受了值 A，另一些接受了值 B，没有任何值获得 Fast Quorum。此时 Leader 介入，执行经典 Paxos 的恢复流程（Phase 1 + Phase 2），解决冲突。这条路径的延迟比经典 Paxos 更长——先有一轮失败的快速尝试，再有一轮 Leader 协调的恢复。

适用场景与局限：

Fast Paxos 在写入冲突率低的场景中表现优异——比如单客户端写入、或请求之间有天然的序列化（如按 key 分区）。但在高冲突场景下，频繁的冲突恢复导致延迟比经典 Paxos 更高。正因如此，实际采用 Fast Paxos 的生产系统很少。它的理论价值在于证明了”1 个消息延迟的共识是可能的”，并为后续的 Generalized Paxos 和 EPaxos 提供了基础。

4.4 变体对比

五、Go 实现：Single-Decree Paxos

下面是一份可编译、可测试的 Single-Decree Paxos 实现。为了清晰，所有通信使用 Go channel 模拟，不涉及网络序列化。生产系统需要加上持久化、超时、网络传输等。

5.1 数据结构

package paxos

import "sync"

// ProposalID 提案编号，(Round, NodeID) 的字典序构成全序。
type ProposalID struct {
    Round  int
    NodeID int
}

func (a ProposalID) GreaterThan(b ProposalID) bool {
    if a.Round != b.Round {
        return a.Round > b.Round
    }
    return a.NodeID > b.NodeID
}

func (a ProposalID) GreaterOrEqual(b ProposalID) bool {
    return a.GreaterThan(b) || a == b
}

// PrepareReq Phase 1a 消息
type PrepareReq struct {
    ID ProposalID
}

// PrepareResp Phase 1b 消息
type PrepareResp struct {
    OK             bool
    AcceptedID     ProposalID
    AcceptedValue  string
    HasAccepted    bool
}

// AcceptReq Phase 2a 消息
type AcceptReq struct {
    ID    ProposalID
    Value string
}

// AcceptResp Phase 2b 消息
type AcceptResp struct {
    OK bool
    ID ProposalID
}

5.2 Acceptor 实现

// Acceptor 维护 Paxos 协议中 Acceptor 角色的状态。
type Acceptor struct {
    mu            sync.Mutex
    minProposal   ProposalID // 已承诺的最高编号
    acceptedID    ProposalID // 已接受的提案编号
    acceptedValue string     // 已接受的值
    hasAccepted   bool       // 是否已接受过提案
}

func NewAcceptor() *Acceptor {
    return &Acceptor{}
}

// Prepare 处理 Phase 1a 请求。
// 如果提案编号高于已承诺的编号，更新承诺并返回已接受的最高提案。
func (a *Acceptor) Prepare(req PrepareReq) PrepareResp {
    a.mu.Lock()
    defer a.mu.Unlock()

    if a.minProposal.GreaterOrEqual(req.ID) {
        return PrepareResp{OK: false}
    }

    a.minProposal = req.ID

    return PrepareResp{
        OK:            true,
        AcceptedID:    a.acceptedID,
        AcceptedValue: a.acceptedValue,
        HasAccepted:   a.hasAccepted,
    }
}

// Accept 处理 Phase 2a 请求。
// 如果提案编号不低于已承诺的编号，接受该提案。
func (a *Acceptor) Accept(req AcceptReq) AcceptResp {
    a.mu.Lock()
    defer a.mu.Unlock()

    if a.minProposal.GreaterThan(req.ID) {
        return AcceptResp{OK: false, ID: a.minProposal}
    }

    a.minProposal = req.ID
    a.acceptedID = req.ID
    a.acceptedValue = req.Value
    a.hasAccepted = true

    return AcceptResp{OK: true, ID: req.ID}
}

5.3 Proposer 实现

// Proposer 执行 Paxos 协议的两阶段提案流程。
type Proposer struct {
    nodeID    int
    round     int
    acceptors []*Acceptor
}

func NewProposer(nodeID int, acceptors []*Acceptor) *Proposer {
    return &Proposer{
        nodeID:    nodeID,
        round:     0,
        acceptors: acceptors,
    }
}

// Propose 尝试让值 v 被选定。
// 如果 Acceptor 已经接受了更高编号的值，则提议那个值（保证安全性）。
// 返回被选定的值和是否成功。
func (p *Proposer) Propose(v string) (string, bool) {
    p.round++
    id := ProposalID{Round: p.round, NodeID: p.nodeID}
    majority := len(p.acceptors)/2 + 1

    // Phase 1: Prepare
    var promiseCount int
    var highestAccepted ProposalID
    var valueToPropose string
    hasAnyAccepted := false

    for _, acc := range p.acceptors {
        resp := acc.Prepare(PrepareReq{ID: id})
        if !resp.OK {
            continue
        }
        promiseCount++
        if resp.HasAccepted && (!hasAnyAccepted ||
            resp.AcceptedID.GreaterThan(highestAccepted)) {
            highestAccepted = resp.AcceptedID
            valueToPropose = resp.AcceptedValue
            hasAnyAccepted = true
        }
    }

    if promiseCount < majority {
        return "", false
    }

    // Phase 2a: 选择提议值
    if !hasAnyAccepted {
        valueToPropose = v
    }

    // Phase 2: Accept
    var acceptCount int
    for _, acc := range p.acceptors {
        resp := acc.Accept(AcceptReq{ID: id, Value: valueToPropose})
        if resp.OK {
            acceptCount++
        }
    }

    if acceptCount < majority {
        return "", false
    }

    return valueToPropose, true
}

5.4 测试

package paxos

import (
    "fmt"
    "sync"
    "testing"
)

func TestSingleProposer(t *testing.T) {
    acceptors := make([]*Acceptor, 3)
    for i := range acceptors {
        acceptors[i] = NewAcceptor()
    }
    p := NewProposer(1, acceptors)
    val, ok := p.Propose("hello")
    if !ok {
        t.Fatal("expected proposal to succeed")
    }
    if val != "hello" {
        t.Fatalf("expected 'hello', got %q", val)
    }
}

func TestTwoProposersSequential(t *testing.T) {
    acceptors := make([]*Acceptor, 3)
    for i := range acceptors {
        acceptors[i] = NewAcceptor()
    }

    p1 := NewProposer(1, acceptors)
    p2 := NewProposer(2, acceptors)

    // p1 先提议并成功
    val1, ok1 := p1.Propose("alpha")
    if !ok1 {
        t.Fatal("p1 should succeed")
    }
    if val1 != "alpha" {
        t.Fatalf("p1: expected 'alpha', got %q", val1)
    }

    // p2 后提议——由于 Acceptor 已接受 "alpha"，
    // p2 在 Phase 1 会学到这个值，Phase 2 必须提议 "alpha"。
    val2, ok2 := p2.Propose("beta")
    if !ok2 {
        t.Fatal("p2 should succeed")
    }
    if val2 != "alpha" {
        t.Fatalf("p2: expected 'alpha' (learned from acceptors), got %q", val2)
    }
}

func TestConcurrentProposers(t *testing.T) {
    acceptors := make([]*Acceptor, 5)
    for i := range acceptors {
        acceptors[i] = NewAcceptor()
    }

    const numProposers = 10
    results := make([]string, numProposers)
    succeeded := make([]bool, numProposers)

    var wg sync.WaitGroup
    for i := 0; i < numProposers; i++ {
        wg.Add(1)
        go func(id int) {
            defer wg.Done()
            p := NewProposer(id+1, acceptors)
            val := fmt.Sprintf("value-%d", id)
            // 重试最多 100 次
            for attempt := 0; attempt < 100; attempt++ {
                result, ok := p.Propose(val)
                if ok {
                    results[id] = result
                    succeeded[id] = true
                    return
                }
            }
        }(i)
    }
    wg.Wait()

    // 验证安全性：所有成功的 Proposer 选定的值必须相同
    var chosenValue string
    for i := 0; i < numProposers; i++ {
        if !succeeded[i] {
            continue
        }
        if chosenValue == "" {
            chosenValue = results[i]
        } else if results[i] != chosenValue {
            t.Fatalf("safety violation: proposer %d chose %q, "+
                "but expected %q", i, results[i], chosenValue)
        }
    }

    if chosenValue == "" {
        t.Log("warning: no proposer succeeded (livelock), " +
            "this is allowed by Paxos but unlikely in practice")
    } else {
        t.Logf("all successful proposers agreed on: %q", chosenValue)
    }
}

func TestAcceptorRejectsLowerProposal(t *testing.T) {
    a := NewAcceptor()

    // Prepare(5,1) 成功
    resp1 := a.Prepare(PrepareReq{ID: ProposalID{Round: 5, NodeID: 1}})
    if !resp1.OK {
        t.Fatal("prepare(5,1) should succeed")
    }

    // Prepare(3,1) 被拒绝——编号低于已承诺的 5
    resp2 := a.Prepare(PrepareReq{ID: ProposalID{Round: 3, NodeID: 1}})
    if resp2.OK {
        t.Fatal("prepare(3,1) should be rejected")
    }

    // Accept(2,1,"x") 被拒绝
    resp3 := a.Accept(AcceptReq{
        ID:    ProposalID{Round: 2, NodeID: 1},
        Value: "x",
    })
    if resp3.OK {
        t.Fatal("accept(2,1) should be rejected")
    }
}

func TestAcceptorReportsAcceptedValue(t *testing.T) {
    a := NewAcceptor()

    a.Prepare(PrepareReq{ID: ProposalID{Round: 1, NodeID: 1}})
    a.Accept(AcceptReq{
        ID:    ProposalID{Round: 1, NodeID: 1},
        Value: "first",
    })

    // 更高编号的 Prepare 应该看到已接受的值
    resp := a.Prepare(PrepareReq{ID: ProposalID{Round: 2, NodeID: 1}})
    if !resp.OK {
        t.Fatal("prepare(2,1) should succeed")
    }
    if !resp.HasAccepted {
        t.Fatal("should report previously accepted value")
    }
    if resp.AcceptedValue != "first" {
        t.Fatalf("expected 'first', got %q", resp.AcceptedValue)
    }
}

func TestMinorityAcceptorsDown(t *testing.T) {
    acceptors := make([]*Acceptor, 5)
    for i := range acceptors {
        acceptors[i] = NewAcceptor()
    }

    // 只使用前 3 个 Acceptor 模拟 2 个宕机
    p := NewProposer(1, acceptors[:3])
    val, ok := p.Propose("survive")
    if !ok {
        t.Fatal("should succeed with 3/5 majority")
    }
    if val != "survive" {
        t.Fatalf("expected 'survive', got %q", val)
    }
}

把上述代码放在同一个 Go package 中即可运行 go test。TestConcurrentProposers 是最有意思的测试——它验证了 Paxos 的核心安全性属性：即使多个 Proposer 并发竞争，只要有人成功，所有成功者选定的值必须相同。这个测试偶尔会出现所有 Proposer 都失败的情况（活锁），这是 Paxos 的正常行为，不是 bug。

5.5 实现说明

这份实现有意省略了以下内容，以保持代码聚焦在算法核心：

1. 持久化：生产实现必须在 Acceptor 回复之前将状态写入磁盘。这里用内存模拟。
2. 网络传输：用直接函数调用替代网络 RPC。
3. 超时与重试：Proposer 的 Propose 方法是同步的，不处理超时。
4. Learner：省略了 Learner 角色，由 Proposer 直接返回选定的值。
5. 提案编号持久化：Proposer 的 round 应该持久化，防止重启后生成重复编号。

六、从 Paxos 到现代共识

回顾 Paxos 的历史，有几件事值得记住。

Paxos 证明了一件重要的事：在异步网络中，用多数派投票（Quorum Intersection）可以保证共识的安全性。这个洞见是所有后续共识算法的基础——Raft、ZAB、Viewstamped Replication，底层都是同一个原理。

Paxos 也暴露了一个教训：算法的理论正确性和工程可实现性之间存在鸿沟。Lamport 用一篇论文证明了 Single-Decree Paxos 的正确性，但 Multi-Paxos 的工程规范至今没有一篇被广泛认可的完整描述。Google 花了数年、投入了顶尖工程师，才把它变成 Chubby 这个生产系统——而且即便如此，他们仍然发现了许多微妙的 bug。

Raft 的贡献不在于发明了新的理论，而在于提供了一个完整的、可理解的、可直接实现的共识协议规范。它把 Leader Election、Log Replication、Safety 和 Membership Change 作为一个整体来设计和证明，而不是留给实现者自己拼装。

但 Paxos 在特定场景下仍然有独特的价值。Flexible Paxos（2016，Howard 等人）指出经典 Paxos 的 Quorum 要求可以放松：Phase 1 和 Phase 2 的 Quorum 不需要各自都是多数派，只需要它们之间有交集。这为异构部署（如跨数据中心的加权投票）提供了优化空间，而 Raft 的固定多数派要求不容易做到这一点。

理解 Paxos 不只是学一个算法。它是理解分布式共识——安全性与活性的权衡、多数派交集的本质、理论正确性与工程可实现性的距离——的一把钥匙。

参考资料

1. Leslie Lamport. “The Part-Time Parliament.” ACM Transactions on Computer Systems, 16(2):133–169, 1998. 原始 Paxos 论文，用 Paxos 岛议会的寓言描述共识算法。
2. Leslie Lamport. “Paxos Made Simple.” ACM SIGACT News, 32(4):18–25, 2001. 用直白英语重新描述 Paxos，去掉了寓言外壳。
3. Tushar Chandra, Robert Griesemer, Joshua Redstone. “Paxos Made Live — An Engineering Perspective.” Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing (PODC), 2007. Google 将 Paxos 应用于 Chubby 的工程经验，记录了从论文到生产的大量实际问题。
4. Leslie Lamport. “Fast Paxos.” Distributed Computing, 19(2):79–103, 2006. 在无冲突情况下将延迟降低到 1 个消息延迟的 Paxos 变体。
5. Leslie Lamport, Mike Massa. “Cheap Paxos.” Proceedings of the International Conference on Dependable Systems and Networks (DSN), 2004. 使用辅助 Acceptor 减少正常运行所需节点数的变体。
6. Eli Gafni, Leslie Lamport. “Disk Paxos.” Distributed Computing, 16(1):1–20, 2003. 基于共享磁盘而非网络消息的 Paxos 变体。
7. Diego Ongaro, John Ousterhout. “In Search of an Understandable Consensus Algorithm.” Proceedings of the 2014 USENIX Annual Technical Conference (ATC), 2014. Raft 论文，包含 Paxos 可理解性的对照实验数据。
8. Heidi Howard, Dahlia Malkhi, Alexander Spiegelman. “Flexible Paxos: Quorum Intersection Revisited.” arXiv:1608.06696, 2016. 放松 Paxos Quorum 要求的理论分析。