2.1 三种角色#

实际部署中，一个节点通常同时扮演多种角色。

2.2 两阶段协议#

Basic Paxos 分为两个阶段：

阶段一：Prepare

1. Proposer 选择提案编号 n，向所有 Acceptor 发送 Prepare(n)
2. Acceptor 收到 Prepare(n) 后：
   • 如果 n 大于已承诺的编号，承诺不再接受小于 n 的提案，并返回已接受的最大编号提案
   • 否则拒绝

阶段二：Accept

1. Proposer 收到多数 Acceptor 的 Promise 后：
   • 如果返回中有已接受提案，使用最高编号提案的值
   • 否则使用自己提议的值
2. 向所有 Acceptor 发送 Accept(n, value)
3. Acceptor 收到后，如果 n 不小于已承诺编号，则接受

2.3 安全性推导#

Paxos 的安全性证明核心：如果值 v 在提案编号 n 被选定，则任何更高编号的提案的值也必须是 v。

推导过程：

1. 值 v 在编号 n 被 Accept 阶段多数接受
2. 任何更高编号 m 的提案，其 Prepare 阶段必须收到至少一个接受过 v 的 Acceptor 的响应
3. Proposer 必须使用已接受提案中最高编号的值
4. 通过归纳，更高编号的提案值必为 v

3.1 Leader 选举#

选出一个稳定的 Leader 后，所有提案由 Leader 发起，省去 Prepare 阶段：

• Leader 一次性发送 Prepare 覆盖所有未决定的槽位
• 后续请求直接执行 Accept 阶段
• 将两轮 RPC 减少为一轮

3.2 日志复制#

Multi-Paxos 将共识扩展到日志序列，每个槽位独立运行 Paxos：

3.3 日志压缩#

通过快照机制截断已提交的日志前缀，与 Raft 类似。

4.1 日志空洞#

Multi-Paxos 允许日志存在空洞（某些槽位未决定），需要额外的补洞机制。

4.2 Leader 选举#

Basic Paxos 未定义 Leader 选举过程，各实现需自行设计。

4.3 成员变更#

原始论文未涉及成员变更，实际系统需扩展协议支持。

4.4 磁盘持久化#

Acceptor 的承诺和接受状态必须持久化，崩溃后恢复才能保证安全性。

1
// 持久化状态
2
type AcceptorState struct {
3
    PromisedID  int64  // 已承诺的最大提案编号
4
    AcceptedID  int64  // 已接受的最大提案编号
5
    AcceptedVal []byte // 已接受的值
6
}

6.1 Google Chubby#

Chubby 是 Google 的分布式锁服务，基于 Paxos 实现。GFS、BigTable 等系统依赖 Chubby 进行 Leader 选举和元数据存储。

6.2 Google Spanner#

Spanner 使用 Paxos 组（Paxos Group）管理数据分片，每个分片是一个 Paxos 复制组。Spanner 在 Paxos 之上引入 TrueTime API，实现外部一致性。

6.3 阿里 OceanBase#

OceanBase 使用 Multi-Paxos 实现分布式事务的一致性提交，支撑支付宝核心交易。