单值 Paxos 为一个位置选定一个值。数据库却要不断处理请求：先设置余额，再扣款，再读取结果。即使每个位置都不会选出两个不同命令，副本按不同顺序执行这些位置，仍可能得到不同余额。Multi-Paxos 需要把逐槽共识、领导者恢复和状态机执行连接起来。

上一篇：多数派交叉与单值 Paxos建立了单值 Paxos 的承诺与选值规则。本篇沿用多数派交叉的证明方法，把共识实例扩展成日志槽。MIT 6.5840 的 Paxos 讲义也通过有序日志连接共识与数据库复制；Stanford CS244B 的课程路线提供复制与容错背景，不将其课程日程当作特定 Multi-Paxos 实现的规范。

槽号与轮号是两个维度

日志槽号 slot 表示命令的执行位置；轮号 ballot 表示一次提案权限的竞争。一个领导者可以在同一轮里推进多个槽，一个槽也可能经过多轮恢复。把它们合成一个递增整数，会丢掉“同一槽在不同轮里接受过什么”的信息。

本篇固定三个 acceptor A、B、C，多数派为两个。P 独占轮号 1，Q 独占轮号 2；两个领导者可以在一段时间内都运行。唯一轮号所有者保证同一 (ballot,slot) 只提出一个命令，不代表所有进程总能及时识别唯一活跃主节点。

模型采用非拜占庭消息和固定成员。PMMC 正式论文的基础讨论使用崩溃停止与正确进程间最终可靠交付；本文有限调度只延迟或省略指定交付，不证明一般活性。若允许崩溃重启，承诺和接受记录必须在回复前可靠保存，并在重启后恢复；本篇内存程序没有实现这层磁盘协议。PMMC，§1–2

几个状态需要分开记录。accepted 是一个 acceptor 已投过票；chosen 是同一轮、同一槽、同一命令获得多数派历史票的事实。learned 表示某个副本已经获知该决定，applied 表示它已把该命令按序执行到状态。本篇如使用“提交”，只指 chosen，不表示所有副本都已应用。

例如 A、B 接受了槽 1 的写入，通知副本的消息却还在延迟。该命令已经 chosen，落后的副本仍可能没有 learned，更没有 applied。把副本的本地游标当作全局 chosen 边界，会误判已确定命令是否存在。

稳定领导者复用第一阶段

单值协议为每次竞争执行准备与接受两个阶段。Multi-Paxos 的稳定领导者完成一轮第一阶段后，可以在该轮中为多个槽运行第二阶段。减少的是重复取得提案权限的过程，逐槽选择安全命令的责任没有消失。Paxos Made Simple，§3

本文实验采用 PMMC 的成套规则：acceptor 收到更高轮号的第一阶段请求时采用该轮号；第二阶段仅在请求轮号等于本地已采用轮号时接受。09 篇采用的宽松比较变体与这里的消息规则不同，不能只替换一个比较符号，再假定其他状态转移与证明原样成立。

领导者的 scout 为固定轮号收集第一阶段回复，commander 为固定 (ballot,slot,command) 收集第二阶段回复。每个角色必须保留自己的不可变身份。新主当前轮号变大，不会使一个旧回复自动成为新轮的票。实验还检查重复回复只能贡献一个 acceptor 身份，不能靠消息重传凑出多数派。

领导者取得第一阶段多数派后，需要合并这些回复携带的 accepted 记录，对每个槽独立计算 pmax：在该槽所有报告中选择最高 accepted ballot 的命令。不同槽可能选到来自不同轮的命令。整体日志里“最高一条记录”不能替代逐槽比较。PMMC，§2.4

第一阶段回复必须覆盖准备继续使用的槽，并带回相关接受信息。快照截断、成员变更和记录回收会改变需要携带的内容，必须另有协议证明。本篇把全部历史接受记录保留在内存，避免把尚未说明的压缩机制混进恢复规则。

一张接受票也不能随意丢弃

设 P 已建立轮号 1，五个槽的部分记录如下。应用状态初始 x=0，Set(2) 设置 x，Add(3) 加三，Mul(10) 乘十。

槽 命令 轮号 1 已接受者 此时的状态
1 a#1：Set(2) A、B chosen
2 尚无提案 无 空洞
3 a#2：Add(3) B 仅 accepted
4 b#1：Mul(10) B、C chosen
5 尚未使用 无 留给后续请求

P 发往 A 的槽 3 接受消息被延迟。Q 在 B、C 完成轮号 2 的第一阶段，得到槽 1、3、4 的记录。虽然槽 3 只有 B 报告，Q 仍然必须恢复 Add(3)。恢复规则不要求先证明这个命令已经 chosen。

Q 从 B、C 的回复恢复各槽，旧记录的轮号与新提案轮号分别保留：

flowchart TD
    B["B 回复：旧轮 1 的槽 1、3、4"] --> M["Q 完成轮 2 第一阶段多数派"]
    C["C 回复：旧轮 1 的槽 4"] --> M
    M --> P["按槽分组，各取最高 accepted ballot"]
    P --> S1["槽 1：Set 2"]
    P --> S3["槽 3：Add 3<br/>仅 B 报告也必须恢复"]
    P --> S4["槽 4：Mul 10"]
    P --> S2["槽 2：无接受记录<br/>可以提出 no-op"]
    S1 --> A["以轮 2 分别运行各槽第二阶段<br/>每槽仍需多数派"]
    S3 --> A
    S4 --> A
    S2 --> A

如果 Q 错误地只保留“有多数票证明”的槽，就会把槽 3 当成自由位置。它可以在 B、C 上让槽 3 的 no-op 获得轮号 2 的多数票。此后那条旧消息到达 A：A 尚未采用轮号 2，仍可接受轮号 1 的 Add(3)。历史上 B 已经投过这张旧票，A 的票使轮号 1 的 A、B 也形成多数派。

于是同一槽出现两个 chosen 命令：新轮的 no-op，以及更晚才凑齐多数票的旧轮 Add(3)。B 当前采用轮号 2 并不会撤销它过去投出的轮号 1 的票。仅检查 acceptor 当前最高记录，会漏掉这个反例。

正确恢复让 Q 在槽 3 继续提出 Add(3)，则两轮 chosen 的命令相同。PMMC 的 A5 同时覆盖这两种时间方向：较低轮先形成多数派，或者较高轮已接受后，低轮的延迟消息才补齐旧多数派。轮号大小不等于 chosen 事实发生的时间先后。

逐槽安全性的证明仍依靠交集。固定槽 s，较高轮第一阶段的多数派与任何较低轮可能形成的接受多数派相交。交点的承诺阻止其今后接受更低轮；已经接受的历史又通过 pmax 约束新提案。再对轮号归纳，最高接受记录携带的命令与既有选择兼容。只陈述“两个多数派总相交”，没有解释交点保存什么、何时拒绝、提案者如何选值，证明就不完整。

空洞必须通过共识填补

Q 已恢复槽 1、3、4，槽 2 在第一阶段回复中没有接受约束，可以为它提出 no-op。no-op 的含义是应用状态不变，但它仍然是槽 2 的正式候选值，需要通过同样的第二阶段多数派。

副本不能看到槽 4 就在本地把槽 2 当成 no-op。另一个领导者可能已在槽 2 推进业务命令，或者本地尚未收到相关信息。跳过未知槽，相当于未经共识决定该槽没有效果。Paxos Made Simple，§3 的空洞恢复示例

共识的通知可以乱序到达，应用游标只能推进连续已知前缀。某个副本先收到槽 4，状态仍为0、已应用游标仍为0；随后收到槽1，状态变成2、游标为1。槽3的通知先到也不能越过槽2。等槽2的 no-op 决定到达，副本依序应用2、3、4，最终得到 (2+3)*10=50。

flowchart TD
    L4["learned 槽 4：Mul 10"] --> W0["槽 1 未知，等待<br/>applied = 0，x = 0"]
    W0 --> L1["learned 槽 1：Set 2"]
    L1 --> W1["应用槽 1<br/>applied = 1，x = 2"]
    W1 --> L3["learned 槽 3：Add 3"]
    L3 --> HOLE["槽 2 未知，不能执行槽 3、4<br/>applied = 1，x = 2"]
    HOLE --> L2["learned 槽 2：已通过共识的 no-op"]
    L2 --> APPLY["连续应用槽 2 → 3 → 4<br/>x：2 → 5 → 50"]
    APPLY --> DONE["applied = 4，x = 50"]

若按到达顺序立即执行，先乘十再设置二再加三，结果是5。实验刻意使用不交换的命令，使顺序错误直接表现为状态差异。只用连续加法验证，可能让错误执行顺序恰好得到同一数值。

相同日志之外还需要确定性

复制状态机的归纳需要相同初态、同一有序命令前缀以及确定性执行。假设两个副本执行完前 k 条命令后的状态相同，第 k+1 条命令也相同，确定性转移才保证下一状态和结果相同。逐槽安全证明保证命令一致，连续前缀保证次序一致，应用层还必须保证转移一致。

例如命令只写“按本机当前时间增加计数”，每个副本读取不同时间，即使日志字节完全相同，也会生成不同状态。若业务确实需要时间或随机值，影响转移的具体值应成为已排序输入，或者由另一套可证明的协议产生。本篇变异实验注入100、200、300三个固定本地值，不依赖真实时钟碰巧不同。

外部副作用也不因日志一致而自动幂等。一个副本在调用支付接口后、记录完成前崩溃，重放可能再次调用外部接口。将状态机命令排序，只约束复制状态中的执行；跨系统的一次业务效果还需要外部幂等键、事务边界或可恢复工作流。

重试可能占据两个槽

客户端 a 的请求 a#2 在槽 3 执行 Add(3)，执行时结果是5。客户端没有收到回复，重试后来又在槽 5 chosen。逐槽 Paxos 对此没有异议：两个槽各自只选了一个命令，槽内安全性完全成立。

应用层用 (clientID,requestID) 识别逻辑请求。槽 5 到达执行位置时，查到 a#2 已执行，跳过状态变化并返回首次缓存结果5。此时 x 已经是50，因此“重试返回当前 x”与“重试返回首次结果”不是相同 API 语义。本文明确实现后者。PMMC 的命令身份与 perform，§1–2.1

同一个请求进入两个槽时，状态变化与返回值走不同路径：

flowchart TD
    S3["槽 3 chosen：a#2，Add 3"] --> MISS["按序执行，缓存未命中<br/>x：2 → 5"]
    MISS --> SAVE["记录 a#2 → 结果 5<br/>并保存对应操作身份"]
    SAVE --> S4["槽 4 执行 Mul 10<br/>当前 x = 50"]
    S4 --> S5["槽 5 chosen：重试 a#2，Add 3"]
    S5 --> HIT["按序执行到槽 5<br/>请求身份与操作匹配缓存"]
    HIT --> STATE["跳过 Add<br/>x 保持 50，游标推进到 5"]
    HIT --> REPLY["返回首次缓存结果 5<br/>不是当前状态 50"]

同一请求身份不能重新用于其他参数。实验遇到身份相同、操作不同的命令直接报错，避免把应用错误静默解释成成功重试。结果缓存属于本文教学实现的扩展；论文中的重复命令执行抑制不能直接当成任意客户端 API 的完整重试协议。

去重记录、缓存结果和状态应一起进入可恢复状态。只持久化 x、重启后清空去重表，就可能在重放或客户端重试时再次加三。本篇验证从初始状态重放完整日志能恢复同样的状态、游标和缓存，没有验证磁盘上这些信息的原子更新，也没有实现缓存淘汰、客户端会话过期或快照。

旧领导者本地读仍可能过期

一个节点可以仍自认为是主节点，却已经被多数派上的新领导者取代。若旧节点只应用到槽1，本地 x 为2；新主已执行到槽4并向客户端确认，x 为50。客户端在这次写完成之后才去旧节点读取，直接得到2，就不满足线性一致性。

Paxos Made Live 讨论了旧 master 提供陈旧读的问题。把读也作为日志命令，经共识并等待应用到它所在位置，是一种容易解释的做法；租约和其他读优化需要另外证明领导权、时间与读屏障条件，不能凭“节点名字叫 leader”省略。Paxos Made Live，§5.2

本篇程序只断言旧副本状态2与当前副本状态50。写完成后才调用旧主读的先后关系由上述场景指定，并未采集真实客户端网络历史，也没有实现日志读或租约。它证明这条未经领导权确认的本地读路径不足以保证新鲜度，不证明所有从副本读取的方案都不安全。

可运行的五槽调度

代码在 examples/distributed-systems/multipaxos10/，只使用 Go 标准库。A、B、C 和各副本都是单进程内的数据结构，消息交付由显式调用安排。程序打印准备、接受、票数以及副本游标，历史票证以 (ballot,slot,command) 为键，并按不同 acceptor 身份计数。

从 examples/distributed-systems 运行：

1
2
3
4
go run -race ./multipaxos10
go run ./multipaxos10 -scenario normal
go run ./multipaxos10 -scenario mutations
go vet ./multipaxos10

正常轨迹先建立轮号1，形成两个 chosen 槽和槽3的一张票，再让 Q 恢复并通过共识填槽2。迟到旧消息送达后，两轮在槽3仍选同一命令。三个副本分别按不同通知顺序接收日志，最终都应用到槽5，得到 x=50，a#2执行一次且缓存结果为5。从空状态重新顺序重放，全部应用状态与原副本相同。

变异轨迹故意丢弃槽3单票，历史判定器必须发现两种 chosen 命令；另三项变异分别取消顺序应用、去重和确定性。预期观测依次为 x=5、x=53，以及三个副本状态不同。变异被检测时程序输出 DETECTED 并正常退出；未检测到预期错误才会 panic，因此退出码0不能脱离场景含义被解释成“变异协议安全”。

程序还验证重复投票不增加多数派、旧轮第一阶段回复不能激活新轮、第二阶段错轮或错槽回复不能作为该 commander 的有效票。这些是固定轮号和消息关联规则的检查，不构成无界模型检查。2026-09-19 在 Go 1.27.0 darwin/arm64 上，完整调度的 race 运行与 go vet 均通过，四项变异均产生预期反例。实际命令结果见验证记录，逐项资料与版本见论断证据。

可靠交付假设之外还需要重传机制。Liu、Chand 和 Stoller 的2019版可执行规格研究讨论了放宽交付假设后，丢失请求或阶段回复如何造成停滞；它还分析了作者早期未发表规格中混淆固定阶段轮号和可变领导者轮号的问题。这些发现说明实现时需要核对假设与角色身份，不能归因为 PMMC 正式算法已被证明不安全。固定 v4，§4.3、§6.2

两道推导题

只恢复已提交日志够不够

Q 的第一阶段收集 B、C 的回复。槽3只有 B 报告旧轮接受了 X，没有任何进程提供完整多数票证明。Q 能否立即选择新命令 Y，并以“旧值未提交”为理由保证安全？

不能。B 的旧票可能与另一个未参与恢复的 acceptor 的既有票或迟到票组成多数派。即使恢复时还没 chosen，后来也可能 chosen。Q 必须遵循该槽最高 accepted 规则；对未受约束的槽才有新值选择权。仅从缺少多数证明推导“旧值永远不可能被选定”，把未知事实当成了否定事实。

重试的结果为什么不是当前值

a#2首次在 x=2 时执行加三，结果5；其他命令把 x 改成50；a#2重试进入新槽。若副本跳过加法但返回50，是否仍然只执行了一次状态变化？是否满足本文的重试接口？

状态变化确实只执行了一次，但不满足本文规定的首次结果重放语义。重试接口除了去重，还要规定返回哪次结果；缓存必须与请求身份绑定。若缓存已经回收，应明确报告结果不可恢复等约定行为，不能把当前状态伪装成原请求的返回结果。

下一篇 11 转向 Raft 的任期、领导者选举与日志复制。它会继续使用“接受、确定、获知、应用”的区分，同时按照 Raft 自身的日志与任期约束重新建立证明，不能只把 Paxos 的角色名替换成 Raft 名称。

参考资料