Paxos：两阶段承诺与工程困难
本文基于模型知识整理（生成时未联网核对），关键结论建议对照经典文献复核。
一句话定义
Paxos 用"提案编号 + 两阶段（先问询后决定）"让多数派就一个值达成一致，任何时刻至多一个提案能获得多数承诺；Multi-Paxos 把逐实例的共识摊薄为稳定的 leader 加日志复制。
为什么重要
Paxos 是 1990 年代以来分布式共识的源头协议，Spanner、Chubby、Ceph mon 等生产系统的内核。虽然新系统多改用 Raft，但 Paxos 的两阶段思想（prepare 承诺 / accept 接受）渗透在几乎所有共识与事务协议里；读懂 Paxos 才能读懂这些系统的演进理由。
前置知识
核心概念
- 角色：proposer（提议者）、acceptor（接受者，存多数派状态）、learner（学习者）。实际部署中三者常合一。
- 提案编号（proposal id / ballot）：全局（或字典序）唯一且可比大小；编号大者权柄大。
- Phase 1（prepare/promise）：proposer 请求 acceptor 承诺"不再接受编号更小的 prepare，也不再接受编号更小的已接受值"，并带回其已接受的最高编号值。
- Phase 2（accept/accepted）：proposer 以原编号提出值（若 Phase 1 见过值，必须沿用），多数派 accepted 即决定。
原理与机制
安全性从哪来：两个不变量——① acceptor 不接受编号小于其承诺的提案；② proposer 在 Phase 1 若发现任何已接受的值，必须提议该值（不能另起炉灶）。二者共同保证：一旦某值获多数派接受，后续任何成功提案都携带它 ⇒ 已决定值不可被推翻。多数派交集是这两条不变量成立的物理基础。
活性问题与活锁：两个 proposer 交错升号互相打断（P1 打断 P2、P2 又升号打断 P1），永不收敛——这是 FLP 在协议中的具象。工程解法：选出唯一 proposer（leader），由它串行提案；leader 崩溃再选举。这就是从 Basic Paxos 到 Multi-Paxos 的跳跃：稳定 leader 后，Phase 1 只需执行一次（对新 leader），之后逐条日志只跑 Phase 2——把"每次决策两轮 RTT"摊薄为"每条一轮"。
为什么实现难："Paxos Made Live"（Chubby 论文）列举的工程清单：成员变更、磁盘状态恢复（accepted/promise 必须先落盘再应答）、快照与日志压缩、重复消息去重、时钟无关性……协议本体一页纸，工程落地数千行细节——这正是 Raft 出现的直接动因（kp-019）。
图示
Proposer Acceptors (n=5)
│ P1: prepare(7) ─► 承诺: 拒绝 <7；回已接受值(无/旧值)
│ ◄─ promise ×3
│ P2: accept(7, v) ─► (v 必须 = P1 见到的最高编号值)
│ ◄─ accepted ×3 → v 决定 (多数派)直观类比
拍卖行卖一件孤品：每个竞标者先举手问"各位收到我 7 号竞价权了吗"（prepare，拿到多数派承诺），再出价"以 7 号买 v"（accept）。一旦有人成交（多数派接受），后来者升号进场时必须先问一遍——只要问过，就会被强迫"沿用已成交的那件"，孤品不可能被二次卖出。
实例或案例
- Google Chubby（Paxos Made Live）：分布式锁服务，Paxos 日志 + 会话/租约层。
- Spanner：每个 Paxos group 一条日志，跨 group 用 TrueTime 两阶段提交（kp-032）。
- Ceph MON / CockroachDB：Multi-Paxos 变体管理元数据/区间副本日志。
常见误区
- 误区一："Paxos 慢是因为两阶段"。稳定 leader 后每条日志一轮 RTT，与 Raft 相当；慢的感觉多来自实现与部署差异。
- 误区二："可以跳过 Phase 1"。Phase 1 是安全性的根（发现已接受值并沿用）；任何"优化掉 Phase 1"的设计都必须另行证明等价性。
- 误区三："Raft 是 Paxos 的简化版所以更弱"。两者在崩溃模型下安全性等价；Raft 的差异是结构与可理解性（更强的 leader、明确的成员变更），不是强度。
与其他知识点的关系
- kp-017：FLP 的活锁问题在 Paxos 中具体化。
- kp-019：Raft 对同一问题的结构化重构。
- kp-023：2PC 的 prepare/commit 与 Paxos 两阶段形似而神异（2PC 无多数派容错）。
自测题
- Phase 1 发现已接受的值时，proposer 为什么必须沿用？
答：该值可能已获多数派接受（已决定）；另提议新值会破坏一致性。沿用不变量保证已决定值不可翻转。
- Multi-Paxos 相对 Basic Paxos 的核心优化？
答：稳定 leader 使 Phase 1 每届只执行一次，日志逐条只需一轮 Phase 2，摊薄共识成本。
- Paxos 活锁的本质是什么、工程上怎么消？
答：FLP 不可能性在确定性协议里的体现——并发 proposer 互相升号打断；选唯一 leader 串行提案消除竞争。
延伸阅读
- Leslie Lamport, "The Part-Time Parliament"（1998）与 "Paxos Made Simple"（2001）。
- Tushar Chandra 等, "Paxos Made Live"（OSDI 2007）。
- Heidi Howard 的 Multi-Paxos 综述与 Raft 对比论文。