分布式算法 #01：Paxos 共识算法

Paxos 是分布式共识问题的奠基性算法，由 Leslie Lamport 于 1998 年发表。本文从 Basic Paxos 的三阶段协议出发，推导 Multi-Paxos 的 Leader 优化，并深入分析 Leader 宕机、消息丢失、网络分区、活锁等异常场景下算法如何保证安全性。

相关文章：Raft 共识算法 · Gossip 协议与 SWIM 故障检测 · Quorum 与 NWR 模型 · Byzantine 容错（BFT/PBFT）

章节	说明
问题定义	共识的三个安全属性
角色与消息	Proposer / Acceptor / Learner
Basic Paxos 协议	两阶段流程与伪代码
异常场景分析	消息丢失 / Proposer 崩溃 / 活锁 / 脑裂
Multi-Paxos 优化	Leader 选举消除 Prepare 阶段
正确性证明直觉	为什么 Paxos 不会选出两个不同值
工程局限与替代	为什么生产系统更多用 Raft

问题定义

共识（Consensus）：集群中 N 个节点各自提议一个值，最终所有节点就同一个值达成一致。

共识算法必须满足三个属性：

属性	含义
Safety（安全性）	只有被提议的值才能被选定；一旦某个值被选定，所有节点最终看到的都是这个值
Liveness（活性）	只要大多数节点存活且能通信，集群最终一定能达成共识
Fault Tolerance	能容忍少数节点（< N/2）宕机或消息丢失

FLP 不可能定理（Fischer-Lynch-Paterson 1985）：在异步网络中，只要有一个节点可能崩溃，就不存在既满足 Safety 又满足 Liveness 的确定性共识算法。Paxos 的解法是：在实践中放宽活性（某些情况下可能无法推进），但永远保证安全性。

角色与消息

Proposer  ──→  发起提案，驱动共识过程
Acceptor  ──→  存储状态，对提案投票（必须是奇数个，通常 2f+1）
Learner   ──→  学习最终选定的值（可以是 Proposer 兼任）

一个节点可以同时扮演多个角色。关键约束：超过半数的 Acceptor 同意 = 提案通过（Quorum）。

Basic Paxos 协议

paxos basic flow

阶段一：Prepare / Promise

Proposer 发起 Prepare：

Proposer:
  n = 生成全局唯一且单调递增的提案编号
  向所有 Acceptor 广播 Prepare(n)

Acceptor 处理 Prepare：

Acceptor on receive Prepare(n):
  if n > minProposal:
    minProposal = n
    回复 Promise(n, acceptedProposal, acceptedValue)
    // acceptedProposal: 之前接受过的最大提案编号（没有则为 null）
    // acceptedValue:    对应的值（没有则为 null）
  else:
    忽略或回复 Nack(minProposal)  // 告知 Proposer 已有更高编号

Promise 的含义：Acceptor 承诺不再接受编号 < n 的任何提案。

阶段二：Accept / Accepted

Proposer 收到 Quorum 的 Promise 后：

Proposer on receive Quorum of Promise(n, ...):
  // 关键：检查是否有 Acceptor 已经接受过某个值
  if 任意 Promise 中 acceptedValue != null:
    v = 编号最大的 acceptedProposal 对应的 acceptedValue
    // 必须沿用已接受的值，不能使用自己想提议的值！
  else:
    v = 自己想提议的值  // 自由选择
  
  向所有 Acceptor 广播 Accept(n, v)

Acceptor 处理 Accept：

Acceptor on receive Accept(n, v):
  if n >= minProposal:
    minProposal = n
    acceptedProposal = n
    acceptedValue = v
    回复 Accepted(n, v)
  else:
    忽略或回复 Nack(minProposal)

阶段三：Learn（学习阶段）

Proposer on receive Quorum of Accepted(n, v):
  共识已达成，值为 v
  通知所有 Learner: Decided(v)

Learner on receive Decided(v):
  记录 learnedValue = v

异常场景分析

异常 1：Prepare 阶段消息丢失

场景：Proposer P1 发出 Prepare(n=5)，只有 1 个 Acceptor 收到（未达 Quorum）

处理：
  P1 等待超时后，重新广播 Prepare(n=5) 或递增 n 重试
  幂等保证：Acceptor 收到相同 n 的 Prepare 可安全重复处理
  Safety 不受影响：没有 Quorum Promise，P1 不会发出 Accept

异常 2：Accept 阶段消息丢失（最危险场景）

场景：
  P1 发出 Accept(n=5, v="A")
  Acceptor A1、A2 接受，A3 未收到
  P1 在通知 Learner 前崩溃

此时状态：
  A1.acceptedValue = "A"
  A2.acceptedValue = "A"
  A3.acceptedValue = null

新 Proposer P2 发起 Prepare(n=6)：
  P2 收到 Promise(6, 5, "A") 来自 A1
  P2 收到 Promise(6, 5, "A") 来自 A2
  P2 收到 Promise(6, null, null) 来自 A3

P2 发现已有 acceptedValue="A"（编号最大为 5）
→ P2 必须沿用 v="A"，发出 Accept(n=6, v="A")
→ Safety 保证：最终选定的值仍是 "A"，不会出现 "B"

关键设计：Prepare 阶段的 "携带已接受的值" 正是为了处理这个场景——即使原 Proposer 崩溃，新 Proposer 也能发现并延续已经 "半提交" 的值。

异常 3：Proposer 崩溃后新 Proposer 接管

场景：P1 在 Prepare 阶段收到 Quorum Promise 后崩溃，未发出 Accept

P2 发起 Prepare(n=6)：
  所有 Acceptor 的 acceptedValue = null（P1 未来得及 Accept）
  P2 自由选择自己的值 v="B"
  发出 Accept(n=6, v="B") → 合法，Safety 不受影响

为什么安全？
  P1 没有 Accept 任何 Acceptor，"A" 不可能被选定
  P2 可以安全选择新值

异常 4：两个 Proposer 竞争导致活锁（Livelock）

时序：
  P1: Prepare(n=1) → 收到 Promise
  P2: Prepare(n=2) → 覆盖 P1 的 minProposal，P1 的 Accept 被拒
  P1: Prepare(n=3) → 覆盖 P2 的 minProposal，P2 的 Accept 被拒
  P2: Prepare(n=4) → ...
  → 无限循环，永远无法达成共识（违反 Liveness）

解决方案：
  1. 随机退避：Proposer 在重试前等待随机时间（打破对称）
  2. Leader 选举：同一时刻只有一个 Proposer（Multi-Paxos 的核心思想）
  3. 指数退避：每次失败后等待时间翻倍

异常 5：网络分区（脑裂）

场景：5 个 Acceptor，分区为 {A1,A2} 和 {A3,A4,A5}

分区 1（少数派 2 个）：
  P1 发起 Prepare，只能收到 A1、A2 的 Promise（< Quorum=3）
  → P1 无法完成 Accept 阶段
  → 分区 1 无法达成共识（阻塞，但不会选出错误值）

分区 2（多数派 3 个）：
  P2 发起 Prepare，收到 A3、A4、A5 的 Promise（= Quorum）
  → P2 正常完成共识，选定值 v="B"

分区恢复后：
  A1、A2 的 minProposal 可能低于 A3-A5 的值
  P2 或新 Proposer 重新广播 Accepted/Decided 通知 A1、A2
  A1、A2 更新 acceptedValue="B"
  → 最终一致，Safety 保证（多数派已选定的值不会改变）

异常 6：Acceptor 重启后状态丢失

问题：Acceptor 崩溃重启后，如果内存状态（minProposal、acceptedValue）丢失，
     可能违背 Promise 承诺，接受它之前拒绝过的提案

解决方案：
  Acceptor 必须将 minProposal 和 acceptedValue 持久化到磁盘
  每次更新后先 fsync 再回复 Promise/Accepted
  重启后从磁盘恢复状态，再重新加入集群

Multi-Paxos 优化

Basic Paxos 每次共识需要两轮 RPC（Prepare + Accept），高延迟。Multi-Paxos 通过 稳定 Leader 优化：

优化思路：
  1. 选出稳定 Leader（唯一 Proposer）
  2. Leader 一次 Prepare 可以覆盖后续所有 slot（而非每个值都 Prepare）
  3. 正常情况下只需一轮 RPC（Accept 阶段）

Leader 存活时的流程：
  Leader 发出 Prepare(n, slot=∞)  // 一次性 Prepare 所有未来 slot
  收到 Quorum Promise 后
  后续每个新值只需：Accept(n, slot=i, v) → Quorum Accepted → Decided

Leader 失效时：
  检测到心跳超时的节点发起新一轮 Leader 选举
  新 Leader 必须重新执行 Prepare 阶段，补齐所有未完成的 slot
  未完成 slot 的处理：
    如果 Promise 中有 acceptedValue → 沿用该值
    如果所有 Promise 中 acceptedValue=null → 可以用 no-op 填充

paxos multi flow

正确性证明直觉

核心不变式：如果值 v 被选定（Quorum Accepted），那么任何编号更高的提案也必须使用值 v。

证明：

假设 v 在提案编号 n 时被选定：
  存在 Quorum Q1 中的所有 Acceptor 都 Accepted(n, v)

任意更高编号的提案 m > n：
  Proposer 必须先执行 Prepare(m)，收集 Quorum Q2 的 Promise
  Q1 ∩ Q2 ≠ ∅（两个 Quorum 必有交集）
  交集中的 Acceptor 会在 Promise 中携带 acceptedProposal=n, acceptedValue=v
  Proposer 看到编号最大的 acceptedValue=v，被迫选择 v
  → 归纳：所有更高编号的提案值都是 v

工程局限与替代

问题	说明
难以理解	Lamport 自己说："虽然不难，但出了名的难以理解"
难以实现	状态机复制、日志压缩、成员变更等工程细节极复杂
活锁问题	需要额外的 Leader 选举机制
无参考实现	原始论文没有给出完整实现规范

为什么工程中更多用 Raft：Raft 是为可理解性设计的 Paxos 变体，提供了完整的实现规范（包括成员变更、日志压缩），并且已被证明与 Multi-Paxos 等价。参见 Raft 共识算法。

实际使用 Paxos 的系统：

Google Chubby（锁服务）
Google Spanner（TrueTime + Paxos）
Apache Zookeeper（ZAB，Paxos 变体）

参考资料

Lamport, L. (1998). The Part-Time Parliament. ACM TOCS.

Lamport, L. (2001). Paxos Made Simple.

《Designing Data-Intensive Applications》Ch.9 — Consensus

Howard, H. (2016). Flexible Paxos