Paxos

共识问题的第一个工业解,所有后续协议(Raft、ZAB)的理论根源。Basic Paxos 的 prepare/promise/accept 三轮消息看似简单,但从单次决议到连续日志(Multi-Paxos)的每一步都会踩坑——这也是 Raft 诞生的直接动机。

Paxos (Leslie Lamport, 1989/1998) 是共识问题的第一个工业解决方案，也是所有后续共识协议（VR, ZAB, Raft）的理论根源。但 Lamport 的原始描述以希腊议会比喻写成，晦涩难懂——"The Part-Time Parliament"。Raft 的设计动机就是"让 Paxos 能被普通工程师理解"。

Basic Paxos

Paxos 解决单次共识⁠：多个节点如何就一个值达成一致。

角色

Proposer: 发起提案（客户端通常是 proposer）
Acceptor: 投票, 存储 accepted 的值（通常 N=2f+1 个, 容忍 f 个故障）
Learner: 从 acceptors 学习最终决定的值

实际实现中，每个节点通常同时承担三个角色。

两阶段协议

Phase 1: Prepare/Promise

Proposer:
  选择 proposal number N (必须大于它之前用过的任何 number, 且全局唯一)
  发 Prepare(N) → 所有 Acceptors (至少多数)

Acceptor:
  收到 Prepare(N):
    if N > 任何它见过的 Prepare number:
      承诺: 不再 accept 任何 number < N 的提案
      回复 Promise(N, 之前已 accept 的 value: {N_highest, V})
    else:
      忽略 (或回复拒绝)

Phase 2: Accept/Accepted

Proposer:
  等待多数 Promise 回复
  如果收到多数:
    → 准备发 Accept!
    选择 value:
      if 任何 Promise 中包含了已 accepted 的 value:
        选择 N_highest 对应的 V (即序号最大的已 accept 值)  ← 关键!
      else:
        选择自己想要的任何 value
    发 Accept(N, V) → 所有 Acceptors

Acceptor:
  收到 Accept(N, V):
    if N >= 本 acceptor 承诺的最小 N (即没有承诺过 > N 的 prepare):
      accept: 存储 (N, V)
      回复 Accepted(N)
    else:
      拒绝

为什么两阶段

Phase 1 的作用是学习⁠：Proposer 通过 Prepare/Promise 知道"是否已经有值被部分 accept 了"。如果有，它必须用那个值而不是自己的——这防止了不同 proposer 的提案互相覆盖。

反例：如果跳过 Phase 1，两个 proposer 可能同时 propose 不同的值，各自拿到多数 accept，但它们的多数集不交叠 → 两个值都被"锁定" → 系统永远无法收敛。

为什么 N 必须递增

如果 Proposer A 用 N=1 propose 了 V1，但还没拿到多数 accept；Proposer B 用 N=2 propose 了 V2。第 2 轮的 Phase 1 Prepare(2) 会让 acceptors 承诺不再接受 N<2——A 的 Accept(1,V1) 会被拒绝。

这保证了最终只有一个值被多数 accept。

Multi-Paxos

Basic Paxos 解决单次共识。多轮连续共识（如 replicated log 的每个 entry）就是 Multi-Paxos。

优化：选举 Stable Leader

如果每轮都要完整的 Prepare + Accept 两阶段 → 2 RTT per entry。Multi-Paxos 选举了一个 stable leader 后，该 leader 可以跳过 Phase 1——因为只要它还是 leader，没有其他 proposer 会竞争。

Leader 首次被选举: Phase 1 Prepare/Promise (确定 leader 的身份和最的高 accepted N)
之后所有 entries: 直接 Phase 2 Accept → 1 RTT per entry
新的 proposer 想成为 leader: 它发 Phase 1 Prepare 并且得到多数 → 它成为新 leader

Paxos vs Raft

Paxos 定义了核心的 consensus 机制但没有定义⁠：

Leader election 算法（只说了"选一个 distinguished proposer"）
Log compaction/snapshot 机制
Membership change 协议

这导致每个 Paxos 实现（Google Chubby, Amazon DynamoDB, Microsoft Azure Storage）都重新发明了这些部分——实现的复杂性反而比 Raft 高。

参考

论文⁠: "The Part-Time Parliament" (Lamport, 1998)
论文⁠: "Paxos Made Simple" (Lamport, 2001) — 更易读的版本
论文⁠: "Paxos Made Live — An Engineering Perspective" (Google Chubby team, 2007)

Keywords: Paxos, Basic Paxos, Multi-Paxos, Prepare/Promise, Accept/Accepted, proposal number, distinguished proposer