在《浅谈分布式协调》一文中，共识算法被称为现代 CP 架构的核心，而 Paxos 算法是共识算法中的重量级，本文把它展开。

分布式协调要解决的三个问题——顺序性、存活检测、互斥性，最终都收敛到一件事：让多个节点对“某个事实”达成一致。Leader 与多数派是达成一致的手段，但 Leader 换人时，“谁是新的 Leader”本身又需要一次一致——用一致来保证一致，这就是共识问题。

共识问题

共识（Consensus）：一组进程各自提出一个值，最终所有进程对同一个值达成一致，并且该值必须是某个进程提出过的。

一个可用的共识算法需要满足三个性质：

  • 有效性（Validity）：最终达成的值必须是某个进程提议过的值，不能凭空产生；
  • 一致性（Agreement）：所有进程达成的必须是同一个值，不允许两个进程各自认为自己的值被采纳；
  • 终止性（Termination）：算法最终会得出结果，不会无限拖延。

严格来说，三者无法在异步网络中兼得。FLP 不可能性定理（Fischer-Lynch-Paterson，1985）指出：在异步网络中，只要存在一个节点可能发生故障，就不存在同时保证一致性与终止性的确定性共识算法。原因很朴素：节点失联与消息延迟在异步网络里无法区分，算法无从判断“该等”还是“该换”。

因此实用共识算法（Paxos、Raft、ZAB）都选择“安全优先”：任何时候都保证有效性与一致性，绝不出现两个值；终止性交给概率与工程手段——只要某个提议者能在一段时间内不受打扰地完成一轮，共识就会达成。

推导：从“接受第一个”到两阶段

Paxos 由 Leslie Lamport 提出，其完整推导在《The Part-Time Parliament》（1998）与《Paxos Made Simple》（2001）中呈现。推导从最朴素的方案开始。

最简单的方案：一个接受者。提议者把提案交给它，它接受即为共识。问题是接受者一旦宕机，整个系统停摆——于是换成多个接受者，用多数派做决策。

系统中有三种角色：

  • 提议者（Proposer）：发起提案（Proposal）。一个提案是“编号 + 值”的组合 (n, v)，编号全局唯一且可比较大小；
  • 接受者（Acceptor）：对提案投票，一个提案被多数派接受即为选中（Chosen）；
  • 学习者（Learner）：不参与投票，向多数派打听最终被选中的值。

朴素的投票规则：接受者接受第一个收到的提案（约束 P1）。多数派规则保证任意两个多数派集合必有交集，因此任意时刻至多有一个值被选中。

但 P1 有两个麻烦：

  • 僵死：接受者一旦接受某个值就拒绝一切后续提案，不同接受者各自守着不同的值，谁都凑不满多数派，共识永远无法达成；
  • 分裂：若为避免僵死而放开限制、允许接受者接受多个提案，那么值 x 被选中之后，另一个值 y 也可能被另一个多数派选中，共识被撕裂。

两个麻烦指向同一个结论：接受者必须能接受多个提案，但同时必须保证——一旦某个值被选中，之后所有被接受的提案都是同一个值。这就是约束 P2：如果一个值为 v 的提案被选中，那么任何编号更高的被接受的提案，其值都必须为 v。

事实上，接受者完全可能不知道旧值已被选中，所以 P2 只能落实在提议者一侧：提议者在发出提案之前，必须先“打听”现状。这个“先打听、后提议”的过程，自然把算法拆成两个阶段。

第一阶段：Prepare（准备）

  • 提议者选定提案编号 n，向多数派接受者发送 Prepare(n)；
  • 接受者收到 Prepare(n) 后做出承诺（Promise）：不再接受编号小于 n 的任何提案，并回复自己已接受过的编号最大的提案（若有）。

第二阶段：Accept（接受）

  • 提议者收集多数派的承诺：若有人回复了已接受的提案，就挑出其中编号最大的，沿用它的值 v（编号最大意味着它最接近“已选中”，哪怕只是可能，也必须假设“已经”）；若无人回复，则选择自己的值；
  • 提议者向多数派发送 Accept(n, v)。接受者只要没有承诺过比 n 更大的编号，就接受该提案，落盘后回复；
  • 多数派接受后，共识达成，值 v 被选中。

“编号全局唯一且可比较”是两阶段成立的根基。工程上常用（轮次，节点编号）二元组，不同提议者的编号永不相撞。Raft 的任期号（Term）、ZAB 的 Epoch，都是这一编号在选主场景下的形态。

为什么这样设计是安全的

Paxos 的安全性来自三处环环相扣的设计：

  • 多数派交集：任意两个多数派必有交集，任意时刻至多一个值被选中；
  • 承诺不回退：接受者一旦承诺更高的编号，就拒绝旧编号的一切请求；
  • 值继承：第二阶段必须沿用“已接受提案中编号最大的值”，新提案永远不背离已达成或即将达成的共识。

只要多数派回复中有人携带了已接受的值，说明某个值可能已经被选中。协议无从确认“可能”是否已成事实，于是按“已经”处理——这是 Paxos 保守而安全的根本态度。

活性与工程化

Paxos 的著名工程问题是活锁（Livelock）：两个提议者交替进入第一阶段，A 刚拿到承诺，B 就用更高的编号把承诺全部作废，谁的 Accept 都凑不满多数派，算法永远在 Prepare 之间打转。安全无损，终止性不保。

最直接的缓解是随机退避（Random Backoff）：提议者被打断后随机等待一段时间再重试，降低对撞概率。但退避只是降低概率，竞争依然存在——要根治活锁，就得从根上消除竞争：只保留一个活跃提议者。这一思路引出了 Paxos 最重要的工程形态：Multi-Paxos。

Multi-Paxos：从一次一值到一条日志

回头看 Basic Paxos 在工程上的三个缺陷：

  • 一次共识只确定一个值：业务需要的是连续确定一串值（复制日志），逐条跑 Basic Paxos 太低效；
  • 每次共识两轮往返：Prepare + Accept 需要两个网络往返，跨机房部署时延迟翻倍；
  • 活锁风险：提议者不固定，竞争随时可能发生，终止性没有保障。

Multi-Paxos 用三个改动对应解决：

  • 槽位（Slot）：为日志的每个位置运行一个独立的 Paxos 实例，槽位序号与提案编号组合，共识的值就是日志条目；
  • 选主：通过一次 Basic Paxos 选出一个 Leader 作为唯一活跃提议者，从根上消除竞争；
  • 跳过 Prepare：Leader 在当选后只运行一次完整的 Prepare 抢占编号，并借此回查前任 Leader 遗留的提案、沿用其中的值；此后每个槽位直接发送 Accept，编号随槽位递增。一次共识从两轮往返压缩为一轮。

三个改动对应三个好处：

  • 吞吐：常态下延迟减半，这是复制日志能支撑高写入量的前提；
  • 稳定：单一提议者让每一轮都能顺利完成，终止性从“概率”变成“常态”；
  • 收敛：值继承的回查只在换主时发生一次，恰好补齐前任 Leader 已提交但未确认的日志——Leader 换届时的补日志，就是新任 Leader 上任时那一次 Prepare 在做的事。

Raft 与 ZAB 都从这里出发：任期号对应提案编号，日志序号对应槽位，日志匹配规则取代“值继承”的回查逻辑。理解了 Paxos，再读 Raft 就是看同一套原理换了一种更易读的讲述。