Paxos

Basic Paxos 解决一次共识实例：从提议的值中选定至多一个值。一旦值被选定，后来的合法提案不能让该实例改选其他值。要复制连续命令日志，可以为不同日志槽位运行相关实例，并在稳定 leader 下摊薄协议成本。

Paxos 的核心不是“投票最多者获胜”，而是让新提案在继续推进时，保留过去可能已经形成的决定。

角色与术语

一台服务器可以承担多个角色。这里使用固定集合中的多数 quorum，讨论非拜占庭、允许宕机恢复的模型。协议要求 acceptor 重启后仍保留必要的持久状态。

为什么 acceptor 不能只接受第一次看到的值

如果三个 acceptor 分别先收到 X、Y、Z，并且以后都不再接受任何提案，就没有值能获得多数。为了继续进展，acceptor 必须允许接受后续更高编号的提案。

但“允许更高编号覆盖”又带来安全问题：A、B 已接受 X，之后 B、C 接受 Y，两次多数明明相交，却选出了两个值。交集节点 B 若没有受约束的历史继承规则，仍可能参与两个不同决定。

因此需要两个互补机制：用 Promise 限制未来接受的旧提案，用已接受记录约束新 proposer 可以提出的值。

Phase 1：Prepare 与 Promise

Proposer 选择新的唯一 ballot n，发送 Prepare(n)。常用构造是 (本地递增计数, proposer_id) 的字典序，重启后不能复用已经用过的编号。

Acceptor 若允许承诺 n，就持久记录其承诺下界，回复 Promise：以后不接受低于该下界的提案，并附上此前接受过的最高编号提案 (accepted_ballot, accepted_value)，若没有则返回空。

Proposer 收到多数 Promise 后，查看这组回复：有接受记录，就选择其中 accepted_ballot 最大者的值；全部为空，才能选择自己的新值。不是任选一个返回值，也不是选择出现次数最多的值。

Phase 2：Accept 与 Accepted

Proposer 发送 Accept(n,v)。Acceptor 检查自己没有承诺更高 ballot 后，持久保存接受记录并返回 Accepted。若已经承诺更高 ballot，则拒绝旧请求。

当同一个 (n,v) 被多数接受，v 已经 chosen，即使 proposer 在收齐响应前崩溃。Learner 获知决定是另一个事件；“无人收到成功响应”不等于“没有形成决定”。

实现通常会把接受时的承诺下界也推进到相应 ballot，并处理同编号消息的幂等重试。对于同一实例，同一 ballot 不能被 proposer 用来提出两个不同的值。

一个完整的继承例子

设 X 在 ballot 4 被 A、B 接受。新 proposer 以 ballot 7 联系 B、C，B 报告 (4,X)，C 报告空；新 proposer 因此必须提出 X。若返回中存在更高 accepted ballot，则应继承那个值；协议的归纳性质保证它同样不会违反更早的 chosen 值。

反过来，如果 ballot 4 的 X 只到达 A，ballot 7 获得 B、C 的空 Promise，可以选择 Y。B、C 随后不再接受 ballot 4，旧 proposer 因而无法再让 X 获得多数。这说明 Phase 1 不仅收集过去，还通过承诺约束之后能发生的事。

这些例子说明安全性的两个方向：已经选定的值不能被换掉，尚未选定的低编号竞争者不能绕开新的多数承诺继续形成冲突决定。完整推导见 Paxos Made Simple。

运行两条消息轨迹：已选定与仅单点接受

下面将消息交付写成顺序调用，acceptor 的两个字段代表应持久保存的状态。ballot 用全局唯一整数简化；相同 ballot 的 Prepare 可以幂等回复，同 ballot 换值则被显式拒绝。代码没有实现网络、持久化和故障恢复。

class Acceptor:
    def __init__(self):
        self.promised = -1
        self.accepted = None

    def prepare(self, ballot):
        if ballot < self.promised:
            return False, None
        self.promised = ballot
        return True, self.accepted

    def accept(self, ballot, value):
        if ballot < self.promised:
            return False
        if self.accepted and self.accepted[0] == ballot and self.accepted[1] != value:
            raise ValueError("同一 ballot 不能换值")
        self.promised = ballot
        self.accepted = (ballot, value)
        return True

def phase1(cluster, names, ballot, proposed):
    replies = [cluster[name].prepare(ballot) for name in sorted(set(names))]
    promises = [accepted for ok, accepted in replies if ok]
    if len(promises) < len(cluster) // 2 + 1:
        raise RuntimeError("没有获得多数 Promise")
    history = [accepted for accepted in promises if accepted is not None]
    return max(history, key=lambda accepted: accepted[0])[1] if history else proposed

# 轨迹一：A、B 已接受 X，响应是否到达 proposer 不影响 chosen 事实。
c = {name: Acceptor() for name in "ABC"}
assert phase1(c, "AB", 4, "X") == "X"
assert c["A"].accept(4, "X") and c["B"].accept(4, "X")
assert sum(a.accepted == (4, "X") for a in c.values()) == 2
chosen_for_7 = phase1(c, "BC", 7, "Y")
assert chosen_for_7 == "X"
assert c["B"].accept(7, chosen_for_7) and c["C"].accept(7, chosen_for_7)
assert not c["B"].accept(4, "X")

# 轨迹二：4/X 只到 A，B 虽 Promise 4，却没有 accepted 记录。
c = {name: Acceptor() for name in "ABC"}
assert phase1(c, "AB", 4, "X") == "X"
assert c["A"].accept(4, "X")
chosen_for_7 = phase1(c, "BC", 7, "Y")
assert chosen_for_7 == "Y"
assert c["B"].accept(7, "Y") and c["C"].accept(7, "Y")
assert not c["B"].accept(4, "X") and not c["C"].accept(4, "X")
assert c["A"].accepted == (4, "X")  # 局部旧接受记录可以暂时保留

轨迹二里，B 曾经回复 Promise(4)，不等于它接受过 X。Phase 1 要返回的是 accepted 历史，不能把“承诺过的最大 ballot”与“接受过的最大 ballot/value”合并成一个字段。前者限制后续请求，后者约束新提案的值。

反过来，轨迹一中 B 只提供一个 X 的记录，仍足以约束新 proposer；不需要在 B、C 的回复里再次投票，凑出“多数回复都说 X”。B 可能是新 quorum 与旧 chosen quorum 的唯一交点。

这个模型默认 proposer 遵守 phase1 返回的选择，且全局不会把一个 ballot 分给两个 proposer。Acceptor 的本地同 ballot 检查只能发现自己见过的冲突，无法阻止恶意 proposer 向不同 acceptor 谎报不同值；Paxos 的故障模型并非拜占庭模型。状态丢失或非法 proposer 行为不在这段安全推理的前提内。Paxos Made Simple

新提案为什么不能随意换值？

在新 Promise 集合中只看到一份 X，也可能必须继承 X：这份回复可能正是与旧 chosen 多数派的交点。下面区分“只有 A 接受”和“A、B 已选定”两种初始历史，并保留旧 ballot 4 的迟到请求。这样可以同时看到 Phase 1 如何发现过去，又如何通过 Promise 封住未来的冲突路径。

安全不等于一定很快选出值

两个 proposer 可能不断提高 ballot，彼此打断，使系统保持安全却迟迟无法完成。因此实现通常依赖稳定 leader、退避或最终稳定的通信与调度条件改善进展。

收到更高 ballot 的拒绝后，简单无限重试并不能保证低延迟；需要避免故障恢复时的竞争风暴。多数节点不可通信时，基本多数方案不能继续选定新值，但不应因此放弃历史继承规则。

Multi-Paxos：把 Phase 1 的成果用于多个槽位

日志槽位 slot 与 ballot 是两个维度：slot 指命令在日志中的位置，ballot 表示谁以哪个提案代次参与竞争。不能把“新 ballot”理解成“下一条日志”。

稳定 leader 在为相关槽位建立有效的 Phase 1 承诺后，可以在这些承诺覆盖的范围内，用同一 ballot 对后续槽位执行 Phase 2，摊薄 Prepare 成本。并不是因为“我自认为还是 leader”就任意跳过恢复：新 leader 要收集接受历史，逐槽位保留受约束的值，再处理缺失槽位。

正常情况下每批提案可使用一轮 accept 请求与响应，但客户端通信、持久化、队列和状态机应用仍然存在。多个槽位可能并行达成决定，状态机通常仍需按连续前缀应用，不能因 slot 12 先完成就越过未确定的 slot 11 执行依赖命令。

Slot 12 先选定，不代表它可以先执行

设状态初始为 10，slot 10 的命令为加 2，slot 11 为减 1，slot 12 为乘 3。10、12 先被获知，11 暂时缺失。状态机只能先执行 10，再停在 11；否则先乘后减会得到错误的 35，而正确日志顺序得到 33。

def apply_prefix(chosen, next_slot, value):
    while next_slot in chosen:
        value = chosen[next_slot](value)
        next_slot += 1
    return next_slot, value

chosen = {10: lambda x: x + 2, 12: lambda x: x * 3}
next_slot, value = apply_prefix(chosen, 10, 10)
assert (next_slot, value) == (11, 12)
chosen[11] = lambda x: x - 1
assert apply_prefix(chosen, next_slot, value) == (13, 33)
assert chosen[11](chosen[12](chosen[10](10))) == 35

“11 尚未知”不等于“11 可以随便填 no-op”。新 leader 仍需通过恢复协议收集该槽位的接受历史，遵守可能已有值的约束；只有协议允许选择新值时，才可用 no-op 填补空槽。日志复制服务需要分别记录已选定集合与可应用前缀，不能用已知最大 slot 替代执行进度。

从算法到服务还缺什么

生产实现还需要日志截断与快照、成员变化、客户端请求去重、流控、读语义和运维恢复。这些不是“Paxos 不允许”，而是单值协议没有替整套系统做出唯一工程选择。

Raft把选举资格与日志前缀约束组织成更明确的协议结构；Multi-Paxos 的选举和日志恢复实现空间更大。比较应围绕具体实现与保证，而不是断言某个协议所有副本日志始终完全相同。

参考

• Lamport：Paxos Made Simple。
• 共识在实际系统中的实践。

Keywords: Paxos, Multi-Paxos, ballot, prepare, promise, accept, accepted, chosen, quorum