Paxos 协议核心流程：Prepare → Promise → Accept → Accepted 全链路解析
提出问题
分布式共识算法是分布式系统理论的基石，而 Paxos 是其中最具影响力的算法——尽管很多人觉得它难懂。ZooKeeper 的 ZAB 协议、etcd 的 Raft 都脱胎于 Paxos 的设计思想，面试中问分布式系统绕不开 Paxos。
面试官问 Paxos 通常不是想让你背状态转换图，而是想确认两件事：**第一，你是否真的理解 Prepare 和 Accept 两个阶段分别解决了什么问题；第二，你是否知道 Basic Paxos 的理论局限（活锁、单轮决策），以及工程上如何绕过这些局限（Multi-Paxos、Leader 选主）。**只答出"两个阶段"是不够的，还需要能讲清楚为什么需要两个阶段、少一个行不行。
角色定义与核心假设
三个角色
Basic Paxos 定义了三个角色：
- Proposer（提案者）：主动发起提案，是整个流程的推动者。一个集群可以有多个 Proposer。
- Acceptor（接受者）：对提案进行投票，决定是否接受。至少需要 3 个才能容忍 1 个故障（多数派机制）。5 个容忍 2 个，按
2F+1公式算。 - Learner（学习者）：被动学习已达成共识的提案值，不参与投票。通常是状态机副本。
核心假设
Paxos 假设异步网络下的非拜占庭模型——节点可能宕机、消息可能延迟或丢失，但不存在恶意篡改。算法要保证：在多数 Acceptor 存活的情况下，无论网络发生什么，最终只有一个值能被选中。注意 Paxos 不是拜占庭容错（BFT），如果节点故意作恶，Paxos 是无法保证的——要用 PBFT 或 HotStuff。
Phase 1：Prepare 阶段——解决"该听谁的"
提案编号 N 的生成
提案编号 N 必须全局唯一且严格递增。工程上不能简单用时间戳（时钟回拨会冲突），常见做法：
N = (当前时间戳秒数 × 10000) + (节点ID取模10000)但同一个节点在 1 秒内如果发起多个提案，上面的公式会冲突。更稳妥的方案：
// 每个 Proposer 维护本地递增序号
N = (currentEpoch, seqId, nodeId)
// 按三元组字典序比较，先比 epoch，再比 seqId，再比 nodeIdGoogle Chubby 的做法是：Proposer 每轮递增一个本地计数器，拼接上 nodeId 作为低位，确保不同 Proposer 的编号不会重复。比如 seqId * NODE_COUNT + nodeId。
流程
Proposer 生成一个全局唯一的提案编号 N，向 Acceptor 的多数派发送 Prepare(N) 请求。
Acceptor 收到后执行两个承诺：
- 如果 N 大于它已承诺（Promise）的最大编号
promisedId，则更新promisedId = N，返回 Promise 应答，并承诺不再接受任何编号小于 N 的提案（包括 Accept 请求）。 - 在 Promise 应答中，Acceptor 需要返回它已接受的最大编号提案的 value（如果有的话）以及对应的编号
acceptedId。
Proposer Acceptor-1 Acceptor-2 Acceptor-3
| | | |
|--- Prepare(1) --------->| | |
|--- Prepare(1) ---------------------------->| |
| | | |
|<-- Promise(1, no value) -| | |
|<-- Promise(1, no value) --------------------| |
| | | |
// 收到多数派 Promise，进入 Phase 2如果 Acceptor 收到的 N 小于等于 promisedId，直接忽略该 Prepare 请求（不返回任何响应，Proposer 通过超时感知）。
这个阶段解决了什么
解决"编号仲裁"问题：如果多个 Proposer 同时发起提案，谁的提案编号更大，谁就有优先权。Acceptor 通过"承诺不响应更小编号提案"来确保提案编号的可比较性。注意，这里不是"投票"，而是"锁定"——Acceptor 不是在选值，而是在承诺不会接受更小编号的提案。
Phase 2：Accept 阶段——解决"选哪个值"
值的选择规则
Proposer 收到多数 Acceptor 的 Promise 后，从返回的 value 中选出已接受提案中编号最大的那个 value：
def choose_value(promises):
# promises = [(promisedId, acceptedId, acceptedValue), ...]
# 找出所有已接受提案中编号最大的 value
max_accepted = max(
[(aid, aval) for _, aid, aval in promises if aid is not None],
key=lambda x: x[0],
default=None
)
if max_accepted:
return max_accepted[1] # 必须使用已接受的最大编号 value
else:
return my_value # 没有人接受过，可以用自己的值这条规则是 Paxos 正确性的关键：如果之前有提案被多数派接受，当前 Proposer 必须继承那个值，不能提新值。原因：并发场景下，如果 Proposer 不提之前的值，就会导致两个不同的值都被多数派接受，破坏一致性。
流程
Proposer 向 Acceptor 发送 Accept(N, value) 请求。
Acceptor 收到后做一次检查：如果 N >= promisedId，则接受该提案，记录 (acceptedId, acceptedValue) = (N, value)，并通知 Learner。
Proposer Acceptor-1 Acceptor-2 Acceptor-3
| | | |
|--- Accept(1, "X") ---->| | |
|--- Accept(1, "X") ----------------------->| |
| | | |
|<-- Accepted(1, "X") ----| | |
|<-- Accepted(1, "X") -----------------------| |
| | | |
// 收到多数派 Accepted，达成共识为什么 Phase 2 还要检查编号
因为从 Phase 1 到 Phase 2 之间可能有另一个 Proposer 用更大的编号完成了 Prepare。例如：
- Proposer-A 发 Prepare(5)，Acceptor 返回 Promise(5)
- Proposer-B 发 Prepare(10)，Acceptor 更新
promisedId = 10 - Proposer-A 发 Accept(5, "X") → Acceptor 检查发现 5 < 10，拒绝
没有这个检查，并发提案会直接导致值被覆盖，Paxos 的安全保证就破了。
活锁问题与 Multi-Paxos 改进
活锁的具体场景
当两个 Proposer 交替发起 Prepare 时，Acceptor 的承诺编号不断升高，导致两个 Proposer 都无法完成 Accept 阶段：
Proposer-A Proposer-B Acceptor-Majority
| | |
|--- Prepare(1) -------->| |
|<-- Promise(1) ---------| |
| |--- Prepare(2) --------->|
| |<-- Promise(2) ----------|
|--- Prepare(3) -------->| | // A 收到 Promise(2) 后发现
|<-- Promise(3) ---------| | // 必须用更大编号重试
| |--- Prepare(4) --------->|
| |<-- Promise(4) ----------|
| | | // 无限循环...实际影响：理论上是无限循环，工程上受限于网络超时和重试间隔，但可能导致共识延迟从毫秒级退化到秒级。Google Chubby 团队在论文中报告过，在 5 节点集群上，不加 Leader 的 Basic Paxos 在竞争压力下，共识延迟中位数从 5ms 飙升到 300ms+。
真正的生产案例：一个 15 分钟的 Paxos 活锁事故
某大厂中间件团队在 2022 年遇到过这个场景：5 节点 ZooKeeper 集群，一个节点因为网络抖动频繁超时，触发了 Leader 选举；选举过程中另一个节点也超时，两个节点同时发起选举提案。两个候选人交替增大 ZXID，等于两个 Proposer 交替 Prepare。结果集群 15 分钟没有产出任何提案，写操作全部阻塞，上游订单服务超时，直接影响了线上交易。
根因：ZAB 协议虽然对 Paxos 做了选主优化，但在选举阶段本质上还是 Basic Paxos 的多 Proposer 竞争。随机退避时间不够长（两个节点的退避都是 200ms 基数），导致退避窗口重叠，活锁一直持续。
修复：将退避基数从 200ms 改为 500ms × (节点 ID 取模 3 + 1) 的随机因子，确保同网段节点的退避时间不会重叠。
工程解决方案：Leader Election + Multi-Paxos
选主（Leader Election）：所有提案由唯一的 Leader 发起，其他 Proposer 不参与提案竞争，活锁自然消失。这就是 Multi-Paxos 的核心思路。
Multi-Paxos 的优化：
- 先选 Leader：通过一轮 Basic Paxos 或随机退避选出 Leader，任期（epoch）内唯一。
- Leader 任期只做一次 Prepare：Leader 上任时做一轮 Prepare，后续所有日志条目无需 Prepare，直接走 Accept 阶段。
- RTT 从 2 轮降到 1 轮：Basic Paxos 每次决策需要 2 轮 RTT（Prepare + Accept），Multi-Paxos 在 Leader 稳定后只需要 1 轮 RTT（Accept）。
Basic Paxos 每次决策：2RTT → 假设跨机房 10ms，每次决策 20ms
Multi-Paxos 稳定期决策：1RTT → 同上场景，每次决策 10ms
Multi-Paxos Leader 切换：1 次 2RTT（Prepare）+ 后续 1RTT一个简单的 Multi-Paxos Leader 选主实现（伪代码）：
class MultiPaxosLeader:
def __init__(self, node_id, acceptors):
self.node_id = node_id
self.acceptors = acceptors
self.epoch = 0 # 任期号
self.seq_id = 0 # 日志序号
self.is_leader = False
self.promised_id = -1
def try_become_leader(self):
"""尝试竞选 Leader"""
self.epoch += 1
# 生成提案编号：(epoch, 0, node_id)
proposal_id = (self.epoch, 0, self.node_id)
promises = self.prepare(proposal_id)
if len(promises) > len(self.acceptors) // 2:
self.is_leader = True
# Leader 任期开始，后续日志条目直接 Accept
self.promised_id = proposal_id
return True
return False
def propose(self, value):
"""Leader 提交一条日志（不需要 Prepare）"""
if not self.is_leader:
raise Exception("Not leader")
self.seq_id += 1
# 直接发 Accept
proposal_id = (self.epoch, self.seq_id, self.node_id)
accepts = self.accept(proposal_id, value)
return len(accepts) > len(self.acceptors) // 2真实世界的 Multi-Paxos 实现
| 系统 | 实现方案 | 差异点 | 生产规模 |
|---|---|---|---|
| Raft | 固定 Leader + 任期号 + 日志复制 | 强 Leader，日志只能从 Leader 流向 Follower，不可乱序 | 单集群 5-9 节点，etcd 管理 50k+ QPS |
| ZAB | 原子广播 + Leader 选举（ZXID） | 类似 Raft，但事务提交需等待 Follower 的 ACK | ZooKeeper 单集群 100k+ QPS |
| Google Chubby | 基于 Paxos 的租约锁服务 | 使用 Multi-Paxos，但选主用了超时+随机退避，非 Bully 算法 | 内部 5 节点集群，千级客户端 |
| Microsoft Paxos | 无 Leader 的 Fast Paxos | 允许 Proposer 跳过 Prepare 直接做 Accept，但需要特殊 condition | 主要用于 Azure 内部存储层 |
Raft 和 Paxos 的本质区别：Raft 把"选主"和"日志复制"分成了两个独立阶段，日志复制严格按顺序（append-only），不允许多个日志槽并行决策。而 Paxos 允许不同日志槽独立运行 Paxos 实例，但 Multi-Paxos 通过 Leader 实现了类似 Raft 的顺序保证。这也是为什么 Raft 比 Paxos 更容易理解且实现难度更低——Ongaro 在论文中就明确说 Raft 的设计目标就是"可理解性优先"。
工程踩坑经验
坑 1：Prepare 超时导致活锁升级
现象：5 节点集群，3 个节点部署在同一机房，2 个节点在异地机房。跨机房网络延迟 P99 约 80ms，P50 约 50ms。Proposer 设置的 Prepare 超时是 100ms（只考虑了平均延迟）。跨机房请求在 P99 时段经常超时，Proposer 发起重试，每次重试用更大的编号，导致本地节点 promisedId 不断升高，本地 Proposer 自己的 Accept 反而被拒绝。
后果：100ms 的超时窗口下，约 5% 的跨机房请求超时，触发了 50 次/秒的重试风暴。本机房的 3 个节点 promisedId 每 20ms 被提升一次，本机 Proposer 的任何 Accept 请求都被拒绝，共识延迟从 5ms 飙升到 2s 以上。
解法：超时时间设为 2 × 跨机房 P99 延迟，即 160ms，而不是 100ms。同时增加重试退避（退避因子 2，最长 2s）。重试时带上 retryCount 字段，Acceptor 对 retryCount > 3 的 Prepare 请求直接返回当前 promisedId 让 Proposer 知道真实水位，而不是静默丢弃。
坑 2：Acceptor 持久化不当导致拒绝服务
场景：Acceptor 的 promisedId 和 acceptedValue 需要持久化到磁盘。每次 Prepare 都写一次磁盘，高峰期 1000 QPS 的 Prepare 请求会把磁盘 IO 打满。实测：单节点上每次 fsync 耗时约 2ms（SATA SSD），1000 QPS 就是 2000ms 的 IO 时间，完全不可用。
解法：批量写入 + 异步刷盘。Acceptor 在内存中累积多个承诺，每隔 10ms 或积累 100 条后批量 fsync。但注意崩溃恢复时必须保证 promisedId 不丢失——可以用 WAL（Write-Ahead Log）结构：先写日志到 WAL（顺序写，约 0.1ms），再返回 Promise，后台批量 fsync WAL。崩溃恢复时重放 WAL 重建 promisedId。
坑 3：提案编号溢出
场景：提案编号用 int64，但 Proposer 的递增计数器用 int32。某集群运行了 3 年，计数器的 seqId 达到 21 亿 + 接近溢出，导致编号回绕，新编号被旧编号覆盖。后果是：新提案的编号（2, 0, node1）被 Accept 接受，但旧提案的编号（2, 2147483647, node1）在崩溃恢复时被某些 Acceptor 认为是"已接受的最大编号"，导致 Leadership 交替时值继承出错。
解法：提案编号用 int64 且 Proposer 必须用 (epoch, seqId, nodeId) 三元组，epoch 在 Leader 切换时递增，使得即使 seqId 溢出，也能通过 epoch 区分新旧。更稳妥的做法：epoch 用 int64，seqId 用 int64，nodeId 用 int16，留出 16 位填充。每秒 100 万次提案，seqId 需要 58 万年才溢出，但 epoch 溢出时间更短——epoch 每次 Leader 切换递增，如果需要频繁切换，epoch 也可能溢出，所以需要在 epoch 达到 int64 最大值前做人工重置。
坑 4：Acceptor 的持久化读写顺序问题
场景：Acceptor 先持久化到磁盘，再返回 Promise。如果持久化失败（磁盘满、权限错误），Acceptor 已经在内存中更新了 promisedId，但没持久化。崩溃后重启，promisedId 丢失，之前承诺过的编号不再被遵守，导致一致性破坏。
正确做法：先持久化，再返回 Promise。如果持久化失败，不应更新内存状态，直接返回错误或忽略。ZooKeeper 的 ZAB 协议中，Follower 对 Leader 提案的 ACK 必须等数据写入本地磁盘后才返回，就是这个原因。
面试话术
第一层（2 分钟）
"Paxos 的核心矛盾是多个 Proposer 可能同时提案，需要一种机制让编号大的提案胜出。Prepare 阶段解决的是'编号仲裁'，Acceptor 承诺不响应更小编号；Accept 阶段解决的是'值确定'，Proposer 必须继承之前已接受的最大编号值。两个阶段缺一不可——少一个就会在并发场景下出现分裂。"
第二层（1 分钟，进阶）
"但如果面试官继续问，我会补充 Basic Paxos 的活锁问题。两个 Proposer 交替 Prepare 会导致共识退化。工程上基本不用纯 Basic Paxos，而是用 Multi-Paxos 或 Raft——先选一个 Leader，Leader 任期内只做一轮 Prepare，后续所有决策只需 1 轮 RTT，而不是 2 轮。"
第三层（30 秒，加分项）
"实际实现中，提案编号的生成、Acceptor 持久化、超时和重试策略都直接影响可用性。比如提案编号如果只用时间戳拼接节点 ID，时钟回拨就会出问题；建议用 (epoch, seqId, nodeId) 三元组，epoch 在 Leader 切换时递增。另外 Acceptor 持久化必须用 WAL 结构，先写日志再返回 Promise，否则崩溃恢复会丢承诺。"
面试官常追问的 3 个问题
Q1：Paxos 能不能保证 liveness？ 不能。Paxos 只保证 safety（一致性），不保证 liveness（最终完成）。活锁就是 liveness 不保证的证明。Raft 通过选举超时值的随机化来保证 liveness。
Q2：如果 Acceptor 在 Prepare 阶段返回了 Promise，但随后宕机了，这个承诺还算数吗？ 算，但不重要。Acceptor 宕机后重启，promisedId 从持久化存储恢复。如果没持久化，约定就没了。但 Paxos 的 safety 保证不依赖每个 Acceptor 都存活——只要多数派存活，承诺就有效。宕机的 Acceptor 恢复后，如果它持久化了 promisedId，它仍然遵守承诺（不响应更小编号提案）；如果没有持久化，那它重启后 promisedId 初始化为 0，可以接受任何编号，但不会破坏 safety——因为其他 Acceptor 还在遵守承诺，多数派已经锁定了足够大的编号。
Q3：Paxos 和 Raft 在选主时有什么区别？ Paxos 的选主和提案是同一套机制，没有独立的选主阶段。Raft 把选主抽出来作为独立阶段，用随机超时（150ms-300ms）来避免活锁，工程上更简单可靠。这也是为什么 etcd 选择 Raft 而非 Paxos 的原因之一——不是 Paxos 做不到，而是 Raft 更容易实现和调优。
总结
| 概念 | 说明 |
|---|---|
| Prepare 目的 | 让 Acceptor 承诺不再接受更小编号的提案，同时返回已接受的最高编号提案值 |
| Accept 目的 | 将选定的提案值提交给 Acceptor 多数派，达成共识 |
| 为什么两个阶段 | 防止"并发提案导致分叉"——Phase 1 锁定编号，Phase 2 提交值 |
| 值选择规则 | 如果 Promise 返回中有已接受的值，必须用编号最大的那个，不能提新值 |
| 活锁解法 | 选主（Leader），Basic Paxos → Multi-Paxos |
| 工程实现差距 | 实际系统（Raft、ZAB）都通过 Leader + 日志复制简化 Paxos 的理论模型 |
| 提案编号生成 | 推荐 (epoch, seqId, nodeId) 三元组，杜绝时钟回拨和溢出 |
| 面试高频追问 | Safety vs Liveness、Acceptor 宕机后的承诺有效性、Paxos 与 Raft 选主差异 |
参考：Leslie Lamport. Paxos Made Simple (2001)；Martin Kleppmann. Designing Data-Intensive Applications 第 9 章；Diego Ongaro. In Search of an Understandable Consensus Algorithm (Raft PhD 论文)；Google Chubby 论文 (The Chubby Lock Service for Loosely-Coupled Distributed Systems, 2006)