---
title: Paxos
url: https://doc.liz6.com/distributed-systems/02-consensus-protocols/02-Paxos
locale: zh
area: distributed-systems
tags:
- distributed-systems
- 共识协议
date: 2026-06-30
modified: 2026-06-30
description: 共识问题的第一个工业解,所有后续协议(Raft、ZAB)的理论根源。Basic Paxos 的 prepare/promise/accept 三轮消息看似简单,但从单次决议到连续日志(Multi-Paxos)的每一步都会踩坑——这也是 Raft 诞生的直接动机。
---

# Paxos

> 共识问题的第一个工业解,所有后续协议(Raft、ZAB)的理论根源。Basic Paxos 的 prepare/promise/accept 三轮消息看似简单,但从单次决议到连续日志(Multi-Paxos)的每一步都会踩坑——这也是 Raft 诞生的直接动机。

Paxos (Leslie Lamport, 1989/1998) 是共识问题的第一个工业解决方案，也是所有后续共识协议（VR, ZAB, Raft）的理论根源。但 Lamport 的原始描述以希腊议会比喻写成，晦涩难懂——"The Part-Time Parliament"。Raft 的设计动机就是"让 Paxos 能被普通工程师理解"。

## Basic Paxos

Paxos 解决**单次共识**：多个节点如何就**一个值**达成一致。

### 角色

- **Proposer**: 发起提案（客户端通常是 proposer）
- **Acceptor**: 投票, 存储 accepted 的值（通常 N=2f+1 个, 容忍 f 个故障）
- **Learner**: 从 acceptors 学习最终决定的值

实际实现中，每个节点通常同时承担三个角色。

### 两阶段协议

**Phase 1: Prepare/Promise**

```
Proposer:
  选择 proposal number N (必须大于它之前用过的任何 number, 且全局唯一)
  发 Prepare(N) → 所有 Acceptors (至少多数)

Acceptor:
  收到 Prepare(N):
    if N > 任何它见过的 Prepare number:
      承诺: 不再 accept 任何 number < N 的提案
      回复 Promise(N, 之前已 accept 的 value: {N_highest, V})
    else:
      忽略 (或回复拒绝)
```

**Phase 2: Accept/Accepted**

```
Proposer:
  等待多数 Promise 回复
  如果收到多数:
    → 准备发 Accept!
    选择 value:
      if 任何 Promise 中包含了已 accepted 的 value:
        选择 N_highest 对应的 V (即序号最大的已 accept 值)  ← 关键!
      else:
        选择自己想要的任何 value
    发 Accept(N, V) → 所有 Acceptors

Acceptor:
  收到 Accept(N, V):
    if N >= 本 acceptor 承诺的最小 N (即没有承诺过 > N 的 prepare):
      accept: 存储 (N, V)
      回复 Accepted(N)
    else:
      拒绝
```

### 为什么两阶段

Phase 1 的作用是**学习**：Proposer 通过 Prepare/Promise 知道"是否已经有值被部分 accept 了"。如果有，它**必须**用那个值而不是自己的——这防止了不同 proposer 的提案互相覆盖。

反例：如果跳过 Phase 1，两个 proposer 可能同时 propose 不同的值，各自拿到多数 accept，但它们的多数集不交叠 → 两个值都被"锁定" → 系统永远无法收敛。

### 为什么 N 必须递增

如果 Proposer A 用 N=1 propose 了 V1，但还没拿到多数 accept；Proposer B 用 N=2 propose 了 V2。第 2 轮的 Phase 1 Prepare(2) 会让 acceptors 承诺不再接受 N<2——A 的 Accept(1,V1) 会被拒绝。

这保证了**最终只有一个值被多数 accept**。

## Multi-Paxos

Basic Paxos 解决单次共识。多轮连续共识（如 replicated log 的每个 entry）就是 Multi-Paxos。

### 优化：选举 Stable Leader

如果每轮都要完整的 Prepare + Accept 两阶段 → 2 RTT per entry。Multi-Paxos 选举了一个 stable leader 后，该 leader 可以跳过 Phase 1——因为只要它还是 leader，没有其他 proposer 会竞争。

```
Leader 首次被选举: Phase 1 Prepare/Promise (确定 leader 的身份和最的高 accepted N)
之后所有 entries: 直接 Phase 2 Accept → 1 RTT per entry
新的 proposer 想成为 leader: 它发 Phase 1 Prepare 并且得到多数 → 它成为新 leader
```

## Paxos vs Raft

Paxos 定义了核心的 consensus 机制但**没有定义**：
- Leader election 算法（只说了"选一个 distinguished proposer"）
- Log compaction/snapshot 机制
- Membership change 协议

这导致每个 Paxos 实现（Google Chubby, Amazon DynamoDB, Microsoft Azure Storage）都重新发明了这些部分——实现的复杂性反而比 Raft 高。

## 参考

- **论文**: "The Part-Time Parliament" (Lamport, 1998)
- **论文**: "Paxos Made Simple" (Lamport, 2001) — 更易读的版本
- **论文**: "Paxos Made Live — An Engineering Perspective" (Google Chubby team, 2007)

*Keywords: Paxos, Basic Paxos, Multi-Paxos, Prepare/Promise, Accept/Accepted, proposal number, distinguished proposer*