Paxos

定义

Paxos 讨论的是分布式系统中的一致性问题：多个进程各自提出一个取值(提案)，算法要保证最终只有一个值被确定(chosen)，并且所有正确运行的进程最终都能获知这个值。被确定的值可以是日志条目、配置信息，也可以是某个节点是否担任主节点这类决定。^[3]

按兰伯特本人的表述，Paxos 是为复制状态机中非拜占庭故障(即节点可能崩溃、消息可能丢失或延迟，但不伪造信息)的情形而设计的算法。它通常被划分为两部分：只就单个值达成一致的 Basic Paxos，以及在多个实例上连续确定一系列值的 Multi-Paxos 思想。^[1][2]

原理

算法中的进程可以承担 3 种角色。提议者(Proposer)提出带编号的提案，决策者(Acceptor)对提案投票并作出承诺，学习者(Learner)不参与投票，只获知已经确定的结果。实际系统中一个节点可以同时扮演多种角色。^[3]

Basic Paxos 把一轮决议分为 Prepare 与 Accept 两个阶段。Prepare 阶段，提议者选取一个全局唯一且递增的提案编号 $n$，向多数派决策者发出请求; 决策者若发现 $n$ 不小于自己已经承诺过的最大编号，就承诺不再接受更小编号的提案，并把此前接受过的编号最大的提案及其取值一并回复。

Accept 阶段，提议者收到多数派的应答后，若应答中存在已被接受的提案，就必须采用其中编号最大的取值; 若都为空，则可以自行选定取值。随后它带着编号 $n$ 和该取值再次请求多数派，获得多数接受后该值即被确定。^[3]

多数派(Quorum)机制是安全性所在: 任意两个多数派必然至少有一个共同成员，因而后一轮协商无法绕开前一轮已经确定的结果。容忍 $f$ 个节点同时失效需要 $2f+1$ 个节点，也就是 3 个节点的系统最多容许 1 个节点故障。^[3]

sequenceDiagram

participant P as Proposer 提议者

participant A1 as Acceptor 1

participant A2 as Acceptor 2

participant A3 as Acceptor 3

P->>A1: Prepare(n)

P->>A2: Prepare(n)

P->>A3: Prepare(n)

A1-->>P: Promise(n, 已有值)

A2-->>P: Promise(n)

A3-->>P: Promise(n)

Note over P: 取得多数派承诺

P->>A1: Accept(n, v)

P->>A2: Accept(n, v)

P->>A3: Accept(n, v)

A1-->>P: Accepted(n, v)

A2-->>P: Accepted(n, v)

Note over P: 多数接受，值 v 被确定

发展历程

兰伯特在 1989 年设计了这个容错算法，并于 1990 年把论文投给《ACM Transactions on Computer Systems》。文中用古代 Paxos 岛兼职议员靠信使传递议事记录的情景来比喻算法，审稿人认为故事性描述不合适、要求删除虚构情节，兰伯特未作修改。^[1]

这篇题为《The Part-Time Parliament》的论文直到 1998 年才在该刊第 16 卷第 2 期正式发表，从投稿到刊出历经约 9 年，刊登时还被处理成一份带有编者说明的“失而复得”稿件。^[4][1]

由于原始论文理解门槛较高，兰伯特在 2001 年发表《Paxos Made Simple》，改用平实的语言重新叙述算法，篇幅从 30 余页压缩到十余页，重点讲清了这两阶段的共识协议部分。^[2]

2006 年前后，Google 公开的 Chubby 锁服务论文披露其以 Paxos 作为单元内的一致性算法，Chubby 又被 BigTable 等系统采用，Paxos 由此在工业界获得广泛关注。此后 Google 的 Megastore、Spanner 等系统同样以 Paxos 状态机复制数据。^[5]

2013 年，兰伯特因在分布式系统理论与实践方面的贡献获得 ACM 图灵奖，Paxos 是其获奖工作的重要组成部分; 相关论文此前还获得了 ACM SIGOPS 名人堂奖(2012 年)。^[1]

应用

Paxos 最主要的用途是实现复制状态机: 多台机器执行同一串命令，只要多数派存活并互相通信，服务就能继续对外提供，数据也不会丢失。这使它适合做元数据管理、名字服务、主节点选举和分布式锁这类需要强一致的功能。

在 Google 内部，Chubby 用 Paxos 维持锁服务各副本的一致，Spanner 则在每个分片(tablet)上运行一个 Paxos 状态机，并通过默认 10 秒的租约维持较长期的主节点，其实现还采用了流水线方式以提高广域网环境下的吞吐。^[5]

开源与商用系统中也能见到它的身影: Apache ZooKeeper 的 ZAB 协议、MySQL 5.7 引入的组复制机制，都借鉴或改进了 Paxos 的思想; Ceph 的监视器进程、Apache Mesos 的复制日志也使用 Paxos 相关方案。需要指出，这些系统实际部署的多为 Multi-Paxos 一类的变体，并非兰伯特论文中的原始形态。^[6]

局限

Basic Paxos 一次只能确定一个值，且确定一个值至少需要两个来回的网络通信，难以直接支撑连续写入命令的场景，因此它更多被视为理论基线，工程上普遍使用 Multi-Paxos。

多个提议者同时提案时可能出现活锁: 编号较大的提案不断打断编号较小的提案，各方的 Accept 始终无法拿到多数派，进程可能循环重试而长期无法形成决议。工程上通常靠选出单一领导者、随机退避等手段加以缓解。

算法描述与真实系统需求之间存在明显落差。Google 工程人员指出，从论文到可运行的实现需要补充大量文献中分散的思路，并对协议做若干较小的扩展，最终系统的正确性往往还缺少形式化证明; 这种实现难度被普遍认为是 Paxos 的短板之一。^[7]

Paxos 的容错前提是仅存在崩溃、消息丢失等非拜占庭故障，它无法应对节点伪造或篡改消息的情形; 另外，它只保证安全性不受影响，在异步网络与持续竞争的极端情况下不保证一定能在有限时间内给出结果。^[3][8]

正是出于对可理解性的考虑，斯坦福大学的迭戈·翁加罗(Diego Ongaro)与约翰·乌斯特豪特(John Ousterhout)设计了 Raft，把可理解性作为首要设计目标，并常被视为对 Multi-Paxos 的简化。^[7]

参见

• Raft —— 一种以易理解为目标、面向复制日志的共识算法，常被视为 Multi-Paxos 的简化版本。

• ZooKeeper —— 提供分布式协调服务的开源系统，其 ZAB 协议借鉴了 Paxos 的多数派思想。

• 复制状态机 —— Paxos 的典型应用场景，使多副本按相同顺序执行同一串命令。

• 拜占庭将军问题 —— 描述节点可能伪造消息的故障模型，Paxos 不处理此类故障。

• Quorum 机制 —— 依靠多数派投票保证读写重叠的做法，是 Paxos 安全性的基础。