21.4 Multi-Paxos

一句话

Multi-Paxos 把 Basic Paxos 的"每个值两轮"压成"选一次 leader，之后每个值只跑第二轮"——省下的是阶段 1 的 1 个 RTT，代价是引入 leader 选举（论文没规定怎么做），并接受日志可以有洞、可以乱序，恢复时必须先补齐才知道哪些值已经选定。

从"一个值"到"一串值"

slot:       1      2      3      4      5
          ┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐
日志      │ a  │ │ b  │ │ c  │ │ ?  │ │ e  │   ← 每个 slot 是一次独立的 Basic Paxos
          └────┘ └────┘ └────┘ └────┘ └────┘
                                ↑ 洞：还没选定

每个 slot 独立跑一次 Paxos，就得到一条"可复制的日志"。但朴素做法要为每个 slot 付 2 RTT / 4N 条消息——这就是 Multi-Paxos 要解决的性能问题（Basic Paxos 的协议与证明见 21.3 Basic Paxos）。

三个优化

优化	做法	省下什么	前提（不满足就退化）
稳定 leader	选一个 proposer 长期负责，之后的 slot 跳过阶段 1，直接 accept	每值 1 RTT、2N 消息	leader 稳定：没有别的 proposer 用更高编号打断
流水线（pipelining）	不等 slot i 的 accepted 就发 slot i+1	吞吐 ≈ 窗口 / RTT	乱序响应要按 slot 归位
批量（batching）	一条 accept 带多个 slot	摊薄 RTT 与 fsync	单条延迟上升（等攒批）

为什么"跳过阶段 1"是安全的：leader 连续用递增的编号提案，在它稳定期间没有别人发更大的 prepare，所以"承诺"这件事已经被第一次阶段 1 覆盖了；而它自己知道每个 slot 的最新状态（它就是那个发提案的人）。一旦有别的 proposer 用更大编号出现，旧 leader 的 accept 会被拒绝——此时它要么退位，要么重新跑阶段 1。

⚠️ "跳过阶段 1"只对"确定没有更早选定值"的 slot 安全。leader 换人后，新 leader 对任何不确定的 slot 都必须先跑阶段 1，否则可能覆盖已选定的值——这就是「恢复」那一节要展开的规则。

日志可以有洞、可以乱序

现象	为什么允许	读的时候要注意什么
洞（slot 3 未选定，slot 4 已选定）	每个 slot 独立决定，后面的 slot 不必等前面的	读不能"跳过洞"：读到洞就停下等它被填上，否则状态机顺序错乱
乱序完成	不同 slot 的 Paxos 实例独立推进	apply 必须按 slot 顺序，不能按完成顺序
重复提案	客户端超时重试	需要幂等（见 25.4 幂等设计与去重）

对比 Raft：Raft 的日志必须连续、且提交位置由"多数派 matchIndex 中位数"推进；Multi-Paxos 允许洞，代价是"已选定到哪"不像 Raft 那样有单一指针，恢复时要逐 slot 确认（见 21.6 Raft：日志复制）。

恢复：新 leader 必须先补齐

旧 leader L1：slot1..3 已选定（多数派接受），但只来得及通知一部分节点就崩了
新 leader L2：知道 slot1、slot2，但 slot3 是"已选定却不知道"
                │
                ├─ 错误做法：直接 accept(slot3, 新值) → 覆盖已选定的值
                └─ 正确做法：对 slot3 先 prepare → 学到旧值 → 沿用

package main

import "fmt"

type slot struct {
	promised int // 该 slot 上承诺过的最大提案编号
	an       int // 已接受的编号
	av       string
}

type acceptor struct {
	name  string
	slots []slot // 下标 0 对应 slot 1
}

func newCluster(n, m int) []*acceptor {
	as := make([]*acceptor, n)
	for i := range as {
		as[i] = &acceptor{name: fmt.Sprintf("A%d", i+1), slots: make([]slot, m)}
	}
	return as
}

func (a *acceptor) prepare(s, n int) (bool, int, string) {
	if n > a.slots[s].promised {
		a.slots[s].promised = n
		return true, a.slots[s].an, a.slots[s].av
	}
	return false, 0, ""
}

func (a *acceptor) accept(s, n int, v string) bool {
	if n >= a.slots[s].promised {
		a.slots[s].promised = n
		a.slots[s].an, a.slots[s].av = n, v
		return true
	}
	return false
}

// 某个 slot 上被多数派接受的值（"已选定"），没有则返回空
func chosen(as []*acceptor, s int) string {
	cnt := map[string]int{}
	for _, a := range as {
		if a.slots[s].an > 0 {
			cnt[a.slots[s].av]++
		}
	}
	for v, c := range cnt {
		if c >= len(as)/2+1 {
			return v
		}
	}
	return ""
}

func phase1(as []*acceptor, s, n int) (string, bool) {
	bestN, inherit, promises := -1, "", 0
	for _, a := range as {
		if ok, an, av := a.prepare(s, n); ok {
			promises++
			if an > bestN {
				bestN, inherit = an, av
			}
		}
	}
	return inherit, promises >= len(as)/2+1
}

func phase2(as []*acceptor, s, n int, v string) bool {
	acc := 0
	for _, a := range as {
		if a.accept(s, n, v) {
			acc++
		}
	}
	return acc >= len(as)/2+1
}

func copyCluster(as []*acceptor) []*acceptor {
	out := make([]*acceptor, len(as))
	for i, a := range as {
		out[i] = &acceptor{name: a.name, slots: append([]slot(nil), a.slots...)}
	}
	return out
}

func main() {
	const M = 3
	as := newCluster(3, M)

	// L1：用编号 1..3 写 slot1..3，但 A3 掉线，只有 A1、A2 接受
	for i := 0; i < M; i++ {
		v := string(rune('a' + i))
		if phase2(as[:2], i, i+1, v) {
			fmt.Printf("L1 accept slot%d n=%d v=%q → A1、A2 接受（A3 掉线）\n", i+1, i+1, v)
		}
	}
	fmt.Printf("此时 chosen = [%q %q %q]：slot3 已被多数派选定为 %q，但 L1 还没来得及学习就崩了\n\n",
		chosen(as, 0), chosen(as, 1), chosen(as, 2), chosen(as, 2))

	// 错误路径：新 leader 跳过阶段 1，直接用自己的值覆盖
	bad := copyCluster(as)
	fmt.Println("错误做法：L2 跳过阶段 1，直接 accept(slot3, n=10, \"X\")")
	phase2(bad, 2, 10, "X")
	fmt.Printf("  → chosen[slot3] = %q（已选定的 %q 被覆盖）\n\n", chosen(bad, 2), "c")

	// 正确路径：先跑阶段 1，继承已接受的值
	good := copyCluster(as)
	fmt.Println("正确做法：L2 先 prepare(slot3, n=10)")
	inherit, ok := phase1(good, 2, 10)
	fmt.Printf("  → 多数派承诺=%v，返回已接受的最高编号值 %q\n", ok, inherit)
	v := "X"
	if inherit != "" {
		v = inherit // 必须沿用，不能替换
	}
	phase2(good, 2, 10, v)
	fmt.Printf("  → 提案值被强制改为 %q，chosen[slot3] = %q\n", v, chosen(good, 2))
}

输出（本机实测）：

L1 accept slot1 n=1 v="a" → A1、A2 接受（A3 掉线）
L1 accept slot2 n=2 v="b" → A1、A2 接受（A3 掉线）
L1 accept slot3 n=3 v="c" → A1、A2 接受（A3 掉线）
此时 chosen = ["a" "b" "c"]：slot3 已被多数派选定为 "c"，但 L1 还没来得及学习就崩了

错误做法：L2 跳过阶段 1，直接 accept(slot3, n=10, "X")
  → chosen[slot3] = "X"（已选定的 "c" 被覆盖）

正确做法：L2 先 prepare(slot3, n=10)
  → 多数派承诺=true，返回已接受的最高编号值 "c"
  → 提案值被强制改为 "c"，chosen[slot3] = "c"

这条规则说起来简单，工程上要落到三个地方：

场景	必须做什么	漏了会怎样
新 leader 上任	对每个"不确定"的 slot 跑阶段 1（或一次覆盖全部 slot 的批量阶段 1）	覆盖已选定值（上图错误路径）
从快照恢复	快照里必须记录"覆盖到哪个 slot"，之后的 slot 重新确认	重放错位或跳过未决 slot
客户端读	读到洞就停，不能跳过	状态机顺序错乱，业务看到"未来的状态"

🔑 Paxos 的恢复比 Raft 更"贵"：Raft 的新 leader 只需要提交一条当前任期的 no-op，就能通过"日志匹配 + 多数派"反推提交位置（见 21.7 Raft：安全性证明）；Multi-Paxos 没有"连续日志"这个结构，只能逐 slot 询问"你接受过什么"。这是"允许洞"换来的灵活性所付的账。

与 Raft 的对比：安全性等价，工程完备度不同

维度	Multi-Paxos	Raft
安全性	等价（都满足共识三性质）	等价
leader 选举	论文未规定，各实现自造（Chubby 用租约、Spanner 用 TrueTime + term）	任期 + 随机超时，规则明确
日志	允许洞、允许并行提案	必须连续，先补齐再提交
恢复	逐 slot 阶段 1 补齐	提交当前任期 no-op + 日志匹配
成员变更	未定义	单节点变更 / 联合共识（21.8 Raft：成员变更与快照）
快照	未定义	InstallSnapshot
实现难度	高（"Paxos 很难"主要难在这些没写的地方）	中（论文给全了状态机与 RPC）

这张表的结论不是"谁更强"，而是：Paxos 是一个可证明的核心，Multi-Paxos 是一份留给工程填空的骨架。Chubby / Spanner 之所以能基于它，是因为 Google 自己把那部分填空做了二十年（细节对比见 21.12 共识算法对比）。

代价表：两轮变一轮省了多少

方案	每值消息数	每值 RTT	吞吐上限（批大小 B）
Basic Paxos	4N	2	B / (2 RTT)
Multi-Paxos（稳态）	2N	1	B / RTT
Multi-Paxos + 流水线	2N（每批）	摊销到 ≈ RTT / 窗口	≈ 窗口 × B / RTT

所以"Multi-Paxos 比 Basic Paxos 快一倍"只在同步场景成立；真正把吞吐拉起来的是批量 + 流水线，RTT 只是下限（同 21.6 Raft：日志复制 的结论一致）。

反模式

反模式	后果
leader 换人后直接用自己的值写"未确认的 slot"	覆盖已选定值（上图错误路径）
把洞当成"空"，读的时候跳过去	状态机顺序错乱
无稳定 leader，每个值都跑两轮	吞吐减半，且 dueling 风险回归（21.3 Basic Paxos）
流水线无上限	内存暴涨；乱序缓存开销超过收益
以为 Multi-Paxos 自带选主	论文没有；不实现选主就退化成"多个 proposer 抢编号"
批量无限攒	单条延迟不可控；小流量下"永远等不到批"

自检

Q1 Multi-Paxos 为什么能跳过阶段 1？什么情况下这个"跳过"不再安全？

▸ 答案：因为同一个 leader 连续用递增编号提案，阶段 1 的"承诺"已经覆盖了它后续的提案，且它自己掌握每个 slot 的状态；在没有更高编号 prepare 出现时，不会有人覆盖它。一旦发生 leader 变更（或另一个 proposer 用更高编号出现），"每个 slot 上是否有更早的选定值"就不再确定，新 leader 必须对不确定的 slot 重新跑阶段 1，否则可能覆盖已选定值。

Q2 上图里 L1 崩在"slot3 已被选定但没来得及学习"的时刻。为什么这是可能的？

▸ 答案："选定"的判据是多数派接受，而"学习"是 proposer 收到多数派 accepted 之后的动作，两者之间有一个窗口。L1 在 A1、A2 接受后就已经让 slot3 选定，但它在收到/处理这些响应之前崩溃，于是它自己（以及任何依赖它通知的节点）都不知道 slot3 已定。这正是新 leader 必须"先问再说"的原因。

Q3 Multi-Paxos 允许日志有洞，这给读带来什么额外约束？

▸ 答案：状态机必须按 slot 顺序 apply，所以读不能跳过洞去读后面的 slot——否则会读到"建立在缺失状态之上"的结果，业务看到未来的值（例如"扣款了但订单还没创建"）。实现上通常维护一个 applied 指针，只有洞被填上、指针连续推进后才对外提供读。

Q4 为什么 Multi-Paxos 的恢复比 Raft 贵？

▸ 答案：Raft 的日志连续 + 日志匹配性质，让新 leader 只要提交一条当前任期条目，就能用"多数派 matchIndex 中位数"反推所有旧的提交位置；Multi-Paxos 的每个 slot 是独立的 Paxos 实例，没有"连续前缀"可依赖，只能对每个不确定的 slot 跑一次阶段 1（或用批量阶段 1 一次覆盖所有 slot），成本与"不确定 slot 的数量"成正比。

Q5 Basic Paxos 2 RTT、Multi-Paxos 1 RTT，是不是把 RTT 砍半就能让吞吐翻倍？

▸ 答案：不一定。同步场景（一次只发一个值、等结果）下确实约 2 倍；但真实吞吐由"每个 RTT 能确认多少字节"决定，所以批大小与流水线才是主杠杆。批 100 条、RTT 1ms 时，Basic 也能到 50k/s，Multi-Paxos 的收益主要体现在"省掉一半的协调往返与消息量"，而不是无条件的吞吐翻倍。

关联

• 前置：21.3 Basic Paxos、21.2 Quorum 与 W + R > N 的证明
• 并列：21.12 共识算法对比、21.9 ZAB
• 下游：21.5 Raft：选主、21.6 Raft：日志复制、21.7 Raft：安全性证明