21.3 Basic Paxos
一句话
Basic Paxos 用两轮多数派投票决定一个值：第一轮抢编号（承诺"我不会再接受更小的"），第二轮按编号接受提案；它用"继承已接受的最高编号值"这根链子保证已选定的值不会被改掉，代价是每个值两轮 RTT，而且不保证选得出来。
三个角色，可以重叠
| 角色 | 做什么 | 关键状态 |
|---|---|---|
| Proposer | 发起提案，抢编号，收集结果 | 自己见过的最大编号 |
| Acceptor | 承诺 / 接受（投票者） | promised（承诺过的最大编号）、acceptedN/acceptedV（已接受的编号与值） |
| Learner | 学习已选定的值 | 已知的选定值 |
一个进程通常同时扮演三个角色。安全性只依赖 acceptor 的两条规则，与谁当 proposer 无关：
- acceptor 只在
n > promised时承诺，并记住promised = n； - acceptor 只在
n ≥ promised时接受提案(n, v)，并记录(n, v)。
两轮，四个消息
阶段 1（Prepare / Promise）
proposer ── prepare(n) ──▶ 所有 acceptor
acceptor ── promise(n, 已接受的最高编号 (an, av)) ──▶ proposer
proposer：拿到多数派承诺 → 进入阶段 2
阶段 2（Accept / Accepted）
proposer ── accept(n, v) ──▶ 所有 acceptor v = 多数派回报的最高 an 对应的 av（若没有则任意）
acceptor ── accepted(n, v) ──▶ proposer
proposer：拿到多数派接受 → 该值被选定（chosen），通知 learner
| 消息 | 方向 | 带什么 | 少了会怎样 |
|---|---|---|---|
prepare(n) | proposer → acceptor | 提案编号 | 无法拒绝旧提案，两个值可能都被"接受" |
promise(n, an, av) | acceptor → proposer | 承诺 + 已接受的最高编号提案 | proposer 不知道要继承，直接覆盖已选定值 |
accept(n, v) | proposer → acceptor | 编号 + 值 | —— |
accepted(n, v) | acceptor → proposer | 确认 | proposer 不知道是否达到多数派 |
🔑 整个协议只有一处"反直觉"的设计：阶段 1 的回报必须带已接受的提案。少了它，Paxos 与"随便投票"没有区别——下一条消息就能覆盖已选定的值。
安全性：一根链子，三步归纳
| 性质 | 内容 | 靠什么保证 |
|---|---|---|
| P1 | acceptor 接受编号 n 的提案，当且仅当它没有承诺过 > n 的编号 | acceptor 的 promised 检查 |
| P2 | 若提案 (n, v) 被选定，则任何编号 > n 的被选定提案值也是 v | 下面的 P2c |
| P2a | 若 (n, v) 被选定，则任何 acceptor 接受的更高编号提案值也是 v | 由 P2b 推 |
| P2b | 若 (n, v) 被选定，则任何 proposer 发出的更高编号提案值也是 v | 由 P2c 推 |
| P2c | 发提案 (n, v) 前，存在多数派 S：S 中没人接受过 < n 的提案，或 v 是 S 中已接受的最高编号提案的值 | 阶段 1 的回报 |
为什么 P2c 成立（核心论证）：设 (n₀, v₀) 已被选定，则多数派 Q_c 接受了它。新提案 (n, v) 的 n > n₀，它的阶段 1 需要多数派 Q_p 承诺，而 Q_c ∩ Q_p ≠ ∅（相交引理，见 21.2 Quorum 与 W + R > N 的证明）。取交集中的 acceptor x：它接受过 (n₀, v₀)，且 n > n₀ > promised 才会承诺；承诺时它回报了"已接受的最高编号提案"，其中至少包含 (n₀, v₀)。于是 proposer 在 Q_p 的回报里能看到的最高编号提案，其值必然是 v₀（若有更高编号的提案被接受，按归纳它也是 v₀）。proposer 被迫采用 v₀。∎
已选定 (n₀,v₀) 落在 Q_c ─┐
├─ 必有交集 x：x 回报 (n₀,v₀)
新提案 (n,v) 的 Q_p ─────┘ ↓
新提案值被强制为 v₀
"选定"的定义：多数派接受即选定。但 proposer 只有在收到多数派 accepted 之后才知道选定——这两个时刻之间的窗口，正是"新 leader 必须先补齐"的根源（见 21.4 Multi-Paxos）。
活性：安全性成立，但不保证选得出来
两个 proposer 互相抢编号，可以无限循环：
package main
import "fmt"
// 每个 acceptor 记住：承诺过的最大编号、已接受的编号与值
type acceptor struct {
name string
promised int
an int
av string
}
func (a *acceptor) prepare(n int) (ok bool, an int, av string) {
if n > a.promised {
a.promised = n
return true, a.an, a.av
}
return false, 0, ""
}
func (a *acceptor) accept(n int, v string) bool {
if n >= a.promised {
a.promised = n
a.an, a.av = n, v
return true
}
return false
}
// Phase 1：拿到多数派承诺；返回值必须继承「已接受的最高编号提案」
func phase1(as []*acceptor, n int) (ok bool, inherit string, promises int) {
bestN := -1
for _, a := range as {
if yes, an, av := a.prepare(n); yes {
promises++
if an > bestN {
bestN, inherit = an, av
}
}
}
return promises >= len(as)/2+1, inherit, promises
}
// Phase 2：多数派接受即选定
func phase2(as []*acceptor, n int, v string) (bool, int) {
accepted := 0
for _, a := range as {
if a.accept(n, v) {
accepted++
}
}
return accepted >= len(as)/2+1, accepted
}
func propose(as []*acceptor, n int, v string) (bool, string) {
ok, inherit, promises := phase1(as, n)
if !ok {
fmt.Printf(" n=%d 提案 %q：阶段1 只拿到 %d 个承诺 → 放弃\n", n, v, promises)
return false, ""
}
chosenV := v
if inherit != "" {
chosenV = inherit // 关键：不能覆盖可能已被选定的值
}
ok2, accepted := phase2(as, n, chosenV)
fmt.Printf(" n=%d 提案 %q：阶段1 %d 个承诺（继承=%q）→ 阶段2 %d 个接受 → %v\n",
n, v, promises, inherit, accepted, ok2)
return ok2, chosenV
}
func fresh() []*acceptor { return []*acceptor{{name: "A1"}, {name: "A2"}, {name: "A3"}} }
func main() {
fmt.Println("场景 1：第一次提案，3 个接受者中 2 个同意即选定")
as := fresh()
ok, v := propose(as, 1, "A")
fmt.Printf(" → chosen=%v value=%q\n\n", ok, v)
fmt.Println("场景 2：另一个 proposer 想改值（n=2, v=B），但它必须继承已接受的值")
ok, v = propose(as, 2, "B")
fmt.Printf(" → chosen=%v value=%q（值仍然是 A）\n\n", ok, v)
fmt.Println("场景 3：两个 proposer 互相抢编号 —— 安全性没破，但永远选不出值")
as = fresh()
steps := []struct {
who string
phase int // 1=prepare, 2=accept
n int
v string
}{
{"P1", 1, 2, ""},
{"P2", 1, 3, ""},
{"P1", 2, 2, "X"},
{"P1", 1, 4, ""},
{"P2", 2, 3, "Y"},
{"P2", 1, 5, ""},
{"P1", 2, 4, "X"},
}
for _, s := range steps {
if s.phase == 1 {
_, inherit, p := phase1(as, s.n)
fmt.Printf(" %s prepare n=%d → 承诺 %d/3，继承=%q\n", s.who, s.n, p, inherit)
} else {
ok, acc := phase2(as, s.n, s.v)
fmt.Printf(" %s accept n=%d v=%q → 接受 %d/3 → %v\n", s.who, s.n, s.v, acc, ok)
}
}
fmt.Println(" → 7 步之后仍无值被选定：每个 proposer 的 accept 都被对方的更高编号 prepare 打断")
}
输出（本机实测）：
场景 1：第一次提案，3 个接受者中 2 个同意即选定
n=1 提案 "A"：阶段1 3 个承诺（继承=""）→ 阶段2 3 个接受 → true
→ chosen=true value="A"
场景 2：另一个 proposer 想改值（n=2, v=B），但它必须继承已接受的值
n=2 提案 "B"：阶段1 3 个承诺（继承="A"）→ 阶段2 3 个接受 → true
→ chosen=true value="A"（值仍然是 A）
场景 3：两个 proposer 互相抢编号 —— 安全性没破，但永远选不出值
P1 prepare n=2 → 承诺 3/3，继承=""
P2 prepare n=3 → 承诺 3/3，继承=""
P1 accept n=2 v="X" → 接受 0/3 → false
P1 prepare n=4 → 承诺 3/3，继承=""
P2 accept n=3 v="Y" → 接受 0/3 → false
P2 prepare n=5 → 承诺 3/3，继承=""
P1 accept n=4 v="X" → 接受 0/3 → false
→ 7 步之后仍无值被选定：每个 proposer 的 accept 都被对方的更高编号 prepare 打断
读法：
- 场景 2 是安全性的全部：明明提案是
"B"，阶段 1 回报了已接受的"A"，于是被迫提"A"。去掉这一步继承，"B"就会被选定，"A"被覆盖。 - 场景 3 是活性的失败：每个
accept都被对方更高的prepare打断。安全性没破（没有任何值被选定），但系统一直不收敛。
| 解决活性的手段 | 做法 | 代价 |
|---|---|---|
| 随机退避 | 抢编号前等一段随机时间，打破对称 | 延迟不确定；极端情况仍可能撞 |
| 稳定 leader | 只让一个 proposer 提案（Multi-Paxos 的核心优化） | 需要选主，选主本身又要共识 |
| 编号分配 | 不同 proposer 用不重叠的编号区间 | 仍可能冲突；实现复杂 |
🔑 这正是 FLP 的工程映射：Paxos 保证"不会错"，不保证"一定能选出来"。工程上用随机化 + 选主把"以概率 1 终止"变成"实际几乎总是很快终止"（22.2 FLP 不可能性）。
代价：一次决定 2 RTT、4N 条消息
| 阶段 | 消息数 | RTT |
|---|---|---|
| 阶段 1（prepare + promise） | 2N | 1 |
| 阶段 2（accept + accepted） | 2N | 1 |
| 合计 | 4N | 2 |
这就是 Multi-Paxos 存在的全部理由：把阶段 1 摊销掉之后，稳态只剩 2N 条消息、1 RTT（见 21.4 Multi-Paxos）。
常见误解
| 误解 | 现实 |
|---|---|
| "Paxos 决定一个值，所以没用" | 多值共识 = 每个日志位置跑一次 Paxos；Multi-Paxos 是它的工程化（21.4 Multi-Paxos） |
| "Paxos 保证活性" | 不保证：dueling proposers 可以无限循环；FLP 早已说明 |
| "多数派接受就结束了" | 多数派接受 = 已选定，但 proposer 可能还不知道；"知道"需要收到多数派 accepted |
| "提案编号可以在 acceptor 本地生成" | 编号必须全局可比且能持久化，否则重启后可能接受更小的编号 |
| "Paxos 只能选一次值，所以不能做日志" | 每个 slot 独立跑；代价是 slot 可以乱序、可以有洞，恢复时要补齐 |
| "两阶段提交和 Paxos 差不多" | 2PC 有协调者单点与阻塞；Paxos 的"协调者"（proposer）随时可换，只要编号更大 |
反模式
| 反模式 | 后果 |
|---|---|
| 阶段 1 只回报"同意/拒绝"，不回报已接受的值 | 新提案直接覆盖已选定值，安全性崩塌 |
接受编号等于 promised 的提案（用 > 而非 ≥） | 同一编号两个值都可能被接受 → 一个编号两个值 |
promised 不持久化 | 重启后接受旧编号，破坏 P1 |
| 用本地时钟/随机数当提案编号 | 编号不单调，旧提案覆盖新提案 |
| 把"多数派接受"当成"客户端可见" | 客户端看到成功但值可能尚未被 learner 学到（读语义问题） |
| 没有随机退避 | dueling proposers 长时间不收敛 |
自检
Q1 为什么阶段 1 的 promise 必须带"已接受的最高编号提案"？只回"我承诺"行不行？
▸ 答案：不行。若只回承诺，proposer 会自由选择自己的值，可能覆盖一个已被选定的值。带上已接受的最高编号提案后，proposer 被强制继承它，这正是 P2c 的来源。场景 2 就是最小演示：提案 "B" 被强制改成 "A"。这条规则是 Paxos 安全性的全部机关所在。
Q2 3 个 acceptor，一个值已被 A1、A2 接受（选定），此时 A3 完全不知道。新 proposer 用更大编号提案，它能覆盖这个值吗？
▸ 答案：不能。新 proposer 的阶段 1 需要多数派承诺，任何多数派（3 选 2）必包含 A1 或 A2 之一，它们会回报已接受的该值；新 proposer 必须继承它。即使 A3 不知情也不影响，因为多数派相交保证"至少有一个人知道"。这正是"多数派"而不是"所有人"就够的原因。
Q3 Basic Paxos 的安全性成立，为什么还会"卡住"？这是 bug 吗？
▸ 答案：不是 bug。安全性（不会有两个决定）与活性（最终做出决定）是两件事；Basic Paxos 只保证前者。两个 proposer 交替用更高编号打断对方，可以让系统永远不选定任何值（场景 3）。FLP 说明在异步模型下二者不可兼得；工程上用随机退避 + 稳定 leader（Multi-Paxos）缓解。
Q4 一次决定为什么是 2 RTT / 4N 条消息？如果要降到 1 RTT，能省掉哪一轮？
▸ 答案：阶段 1（N 条 prepare + N 条 promise）与阶段 2（N 条 accept + N 条 accepted）各 1 RTT，共 2 RTT、4N 条。能省的是阶段 1——但只有"同一个 proposer 连续提案、编号确定更大、且该 slot 上没有更早的选定值"时才安全，这就是 Multi-Paxos 的 leader 稳定假设与它的恢复规则。
Q5 把 accept 的条件从 n ≥ promised 改成 n > promised，会发生什么？
▸ 答案：同一个编号 n 的两次 accept（比如两个 proposer 恰好用了同一个编号，或 acceptor 重启后 promised 恰好等于 n）都可能被接受，于是同一编号下出现两个不同的值——"一个编号一个值"的前提被破坏，后续按编号比较时无法判断哪个是真相。≥ 与 > 的差别看起来是一个符号，实际是安全性的分界线。