我们小区最近准备动用公共维修基金：是修大门、装路灯，还是给电梯做保养？业委会需要拿出一份大家认可的计划。可麻烦的是——业委会成员有时会请假（节点宕机），消息可能在楼道里传丢（网络延迟），没人能保证所有成员同时在场。这时怎么保证最终所有人记住的是同一个方案？ Paxos 就是解决这类问题的经典算法，像一套“业委会开会章程”。Basic Paxos 解决“一个值怎么被团队公认”——任何一位热心业主都能提议，但正式投票前要先拿个编号，先问一圈“大家最近通过过什么”，再提交表决。只要超过半数的业委会成员点头，方案就算定了。 但每次都这样两轮问询太慢，于是 Multi-Paxos 让大家先选出一位“业委会主任”（Leader），由主任连续提出全年计划，不必每件事都重新问询。后面我们还会发现，另一个更年轻的协议 Raft 把这套章程简化成了更易读的版本。这一路，我们一起读懂这套“开会章程”是怎么写出来的。

岗位关联

职业价值：Paxos 理念是理解 ZooKeeper、etcd、Raft 等一切分布式共识系统的钥匙。掌握它，你就能看懂服务注册、配置中心、分布式锁等基础设施的设计逻辑，也能在系统设计中自信地谈论“一致性”。

目录
  1. 可视化演示
  2. 共识问题背景
  3. 三大角色模型
  4. 预备阶段
  5. 接受阶段
  6. 领导者优化
  7. 日志复制机制
  8. Raft协议对比
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

通过步进展示Basic Paxos的Prepare/Accept两阶段共识过程，Multi-Paxos的Leader优化与日志复制，以及Paxos与Raft对比，滑块调节Acceptor数量。

本节配有交互动效（进入视口后自动加载，约 3KB）。

Basic Paxos：准备阶段 Proposer向Acceptor发送Prepare(n) Acceptor承诺不再接受更小提案号 获取多数派承诺并发现已接受值

共识问题背景

我们小区每年召开业主大会，几百名业主对“今年修什么”吵得不可开交，但最重要的问题其实只有一个：如何在大家意见不一时，最终所有人都记住同一个决定。这就是分布式系统的核心难题——共识问题（Consensus Problem）：多个节点必须在同一个值上“对齐”，谁也不能私下记一套。

在分布式系统中，“业主们”就是分布在不同机器上的节点。它们要共同决定的事很多：谁是新任主节点、某个键的值是什么、事务该提交还是回滚。麻烦在于，节点会宕机、消息会延迟或丢失、网络可能分区。Paxos 的创造者 Leslie Lamport 最初用一则古希腊议会寓言描述这个场景，后来正式提出 Paxos 算法，成为第一个被严格证明的正确共识算法，回答了“多副本之间如何安全地确定唯一值”这一基本问题。

Paxos 对系统做出这样的假设：节点可能停止工作或反应很慢，消息可能丢失、延迟、乱序，但节点不会伪造或恶意撒谎——这被称为“无拜占庭错误”模型。在这样的异步系统中，决策只需要由严格超过半数的“多数派”（Quorum）批准。没有一个节点能预知未来，但只要保证任意两个多数派都有至少一个公共节点，就能避免“两个方案都自称赢了”的矛盾。这个多数派交集属性，是 Paxos 安全的基石。

回到小区，这套规则保证了：即便业委会分两拨分别在周六周日开会，只要每场会议都要求超过半数成员到场，两场会议就不可能定出两套互相矛盾的计划——因为至少有一个成员两场都参加了。正是这个朴素的“多数派交集”思想，撑起了整套 Paxos 大厦。

Consensus: ∣Q∣>n2,Q1∩Q2≠∅\displaystyle Consensus:\ |Q| > \frac{n}{2},\quad Q_1 \cap Q_2 \neq \emptyset
这条公式说明：共识的前提是“少数服从多数”，并且任意两个过半数团体必然重叠。重叠的那个成员，正是新旧决策互相“传话”的桥梁。
  1. 多数派大小$|Q|$ 表示一个群体 Q 的人数，Paxos 要求它严格大于节点总数 n 的一半，也就是 $\frac{n}{2}$；哪怕只多一个人也算多数派。
    ∣Q∣>n2|Q| > \frac{n}{2}
  2. 任意两个多数派必有交集$Q_1 \cap Q_2 \neq \emptyset$ 表示两个各占过半人数的队伍不可能完全不相交，就像两条各占过半的投票队伍里必定有重复站队的人。
    Q1∩Q2≠∅Q_1 \cap Q_2 \neq \emptyset
  3. 交集的意义只要有交集，全局就不会出现两个互不认识的多数派分别通过不同方案，从根上杜绝了“两套决定并存”。
    Paxos 安全性根基: Q1∩Q2≠∅\text{Paxos 安全性根基: } Q_1 \cap Q_2 \neq \emptyset

三大角色模型

小区业委会里，角色分工很清晰：热心业主负责写提案，业委会成员负责投票表决，全体业主负责知悉结果。Paxos 也把参与协议的节点抽象成三种角色，各自只操心自己那一摊事，互不越权。

提议者（Proposer）是“提案人”，主动选择编号和值并发起决策；接受者（Acceptor）是“表决人”，负责存储状态、做出承诺和投票；学习者（Learner）是“观众”，它们不参与表决，只学习已经确定的决定。一个物理节点可以同时充当多种角色，比如一个节点既是接受者又是学习者，这在工程实现中很常见。

接受者需要维护三块状态：它记录自己承诺过的最高提案编号，以及自己接受过的编号和值。提案编号是一个全局唯一、单调递增的自然数，通常由“轮次×节点数+节点序号”这类方式生成，这样不同节点独立生成编号也不会撞车。角色与状态的定义，让后续的两阶段流程有了清晰的载体。

就像业委会成员的“工作台账”：记着自己承诺过支持到几号提案、最近投票支持了谁。这本台账虽简陋，却是“两阶段协议”里一切判断的依据——谁能当提案人、提什么内容，都从台账出发。

acc=(npromise, naccept, vaccept)\displaystyle acc = (n_{promise},\ n_{accept},\ v_{accept})
接受者就像一本“工作台账”：承诺过几号、投过谁的票、投的是哪个方案，全部记在案。这本台账是后续一切判断的依据。
  1. 承诺编号$n_{promise}$ 是这个接受者承诺过的最高提案编号，表示“编号小于它的提案我不再考虑”，它是两阶段协议中安全性的第一道闸门。
    npromisen_{promise}
  2. 已接受编号$n_{accept}$ 是它真正投票接受过的提案编号，初始为 0，表示什么都没接受过；编号越大代表它最近一次表态越“新鲜”。
    nacceptn_{accept}
  3. 已接受值$v_{accept}$ 是随之记录下来的提案值，和 $n_{accept}$ 成对出现，初始为空；它会在未来的 Prepare 阶段被新提议者读取并可能继承。
    (naccept, vaccept)(n_{accept},\ v_{accept})

预备阶段

热心业主小新想提议“修大门”，但怕自己不了解之前大家有没有通过别的方案。他先不直接表决，而是请业委会秘书发一个通知：编号 n 的提案准备登场，请每位成员回复两件事——你最近承诺到几号了？你最近投票支持过什么？

对应到 Paxos，提议者选择一个比自己见过的任何编号都大的编号 n，向所有（或多数）接受者发送 Prepare(n) 请求。接受者接到请求后做两件事：如果 n 大于自己承诺过的编号，就更新承诺并回复 Promise；同时必须附上自己“接受过的编号最高的提案”，方便新提案人发现并“继承”还没被最终确定的旧值。

接受者一旦承诺了编号 n，就不允许再接受任何编号小于 n 的提案——这是协议的灵魂，它保证编号越大的提案越有“发言权”，也保证信息收集不会被旧编号污染。提议者要等多久？它只需要等到自己收到超过半数的 Promise，就可以进入下一阶段；不需要等所有人，因为多数派已经足以代表集体的意志。

就像业委会秘书更新台账：“我承诺过支持到 7 号提案了，8 号可以上会；之前 5 号有一个'修大门'的方案还悬而未决，请新提案人一并考虑。”这一问询阶段不产生最终决定，却为后续的安全打下了地基。

Prepare(n): ∀ acc∈Q: n>npromise  ⟹  npromise←n\displaystyle Prepare(n):\ \forall\, acc \in Q:\ n > n_{promise} \implies n_{promise} \leftarrow n
这一阶段像“开会前先查台账”：编号更大的提案才有资格上会，一旦承诺，就不能吃回头草。
  1. 广播请求$Prepare(n)$ 是提议者广播出去的请求，n 是它精心挑选的、比所有已知编号都大的新编号。
    Proposer→所有 Acceptor: Prepare(n)\text{Proposer} \to \text{所有 Acceptor}:\ Prepare(n)
  2. 条件判断对于多数派 Q 中的每个接受者，只有当 $n > n_{promise}$ 成立时，它才愿意受理；否则直接拒绝，这是编号权威性的体现。
    n>npromisen > n_{promise}
  3. 更新承诺满足条件后执行赋值 $n_{promise} \leftarrow n$，并回复 Promise；回复中附带的旧提案信息，是下一阶段“继承值”的来源。
    npromise←nn_{promise} \leftarrow n

接受阶段

小新收到了超过半数的回复，发现有个 5 号提案“修大门”还悬着。按照章程，他不能假装不知道，于是把 5 号的值“修大门”作为自己提案的值正式提交；如果没人提过旧方案，他就可以提交自己想要的“装路灯”。

这是 Paxos 最关键的继承规则：提议者从所有 Promise 回复中，挑出“已接受编号最高”的提案的值作为自己的值；只有当没有任何旧值时，才使用自己的值。然后它向接受者发送 Accept(n, v)，等待最终投票。接受者收到后检查：只要这个编号 n 不小于自己承诺过的最小限制，就接受它，否则拒绝。

当严格超过半数的接受者接受了同一编号 n 的值 v，这个值就被“选定”（chosen）了。此后即使有更高的编号出现、换一个新值，v 已经被选定的历史也不会被抹去。协议的安全性（Safety）由此确立：不存在两个不同的值都能成为最终决定——这就是分布式系统最看重的“不撕裂”。

小区里，新提案人总是主动继承“悬而未决”的旧方案，这条规则乍看像对热心业主的限制，实则是整部章程的保险丝——正是因为它保证了不会有第二个方案在不了解历史的情况下凭空当选。Basic Paxos 就在这两轮对话中，解决了“一个值如何被公认”的问题。

chosen(v)  ⟺  ∃ Q, ∣Q∣>n2: ∀ acc∈Q, accepted(acc, n, v)\displaystyle chosen(v) \iff \exists\, Q,\ |Q| > \frac{n}{2}:\ \forall\, acc \in Q,\ accepted(acc,\ n,\ v)
选定的标准不是“全体同意”，而是“超过半数且互相知道”。多数派交集保证后来者一定听得到这个决定。
  1. 选定成立$chosen(v)$ 表示值 v 被最终确定，它当且仅当存在一个多数派 Q 满足右边的条件。
    chosen(v)  ⟺  ∃ Qchosen(v) \iff \exists\, Q
  2. 多数派用量化这个 Q 的规模必须 $|Q| > \frac{n}{2}$，也就是严格超过半数，保证任何后续决策都绕不开它。
    ∣Q∣>n2|Q| > \frac{n}{2}
  3. 每个成员都接受对于 Q 中每一个接受者 acc，都有 $accepted(acc, n, v)$，意为它们正式接受了编号为 n 的提案 v；一旦此式成立，v 成为“既成事实”。
    ∀ acc∈Q: accepted(acc, n, v)\forall\, acc \in Q:\ accepted(acc,\ n,\ v)

领导者优化

如果每个热心业主都想提议，每次都要先 Prepare 问一圈再 Accept 表决，光开会就开掉一整天。于是 Multi-Paxos 的改进是：大家先选举出一位“业委会主任”——Leader。平时只有主任可以发起提案，其他人只负责表决和学习。

Leader 任期内的核心优化是：整个任期只需做一次 Prepare，也就是“一次性问清历史”；之后对日志的每一个位置（实例），都可以直接发 Accept，省掉了反复的 Prepare。这是因为 Leader 的编号在任期内保持优势，其他节点不会用更大编号来打断它，两阶段因此被压缩成“一阶段”。

如果 Leader 故障了怎么办？其他节点通过心跳超时发现异常，再竞选出新的 Leader，新 Leader 再次执行一次 Prepare，继承所有“可能已选定但还没人学到”的值，然后继续从断点推进日志。故障恢复的代价只是再经历一轮 Basic Paxos，之后的效率依旧。

业委会主任并非独裁者——他来自选举，受制于章程，但一旦上任，平时开会就简单多了：主任报方案，成员表决，纪要员记录。只有主任“失联”时，大家才重启一次完整的选举流程。这正是 Multi-Paxos 为工程系统带来的效率革命。

Prepare(N)⏟仅一次⟶Accept(N+1, v1), Accept(N+2, v2), …⏟连续实例直接接受\displaystyle \underbrace{Prepare(N)}_{\text{仅一次}} \longrightarrow \underbrace{Accept(N+1,\ v_1),\ Accept(N+2,\ v_2),\ \ldots}_{\text{连续实例直接接受}}
一句话：Leader 上台前把历史问题“一次问清”，之后每件事只做一次提案表决，效率从每事两轮降为每事一轮。
  1. 一次 PrepareLeader 上任时执行一次编号为 N 的预备阶段，用来收集历史遗留值和确立自己的编号优势。
    Prepare(N)\text{Prepare}(N)
  2. 连续 Accept从 N+1 开始，每个日志位置都用递增的编号直接发送接受请求，不再重复广播预备。
    Accept(N+1, v1), Accept(N+2, v2), …\text{Accept}(N+1,\ v_1),\ \text{Accept}(N+2,\ v_2),\ \ldots
  3. 轮次对比Basic Paxos 每决定一个值要两轮通信，Multi-Paxos 在 Leader 稳定期每决定一个值只要一轮，这就是它高效的根本原因。
    O(1) per instance (稳定期)O(1)\ \text{per instance (稳定期)}

日志复制机制

业委会最终的目标不是只定一件事，而是定下一整年的计划。一台服务器的状态往往就是一条有序的决策记录：日志。Multi-Paxos 把每一次 Basic Paxos 决策对应日志的一个“空位”（instance），顺序编号 1、2、3… 由 Leader 依次填充。

因此 Multi-Paxos 本质上是在一条日志上连续运行 Paxos：日志位置 i 的值 $v_i$ 是对客户端第 i 个操作的共识结论。所有节点都拥有这条日志副本，一旦某个位置的多数派决定产生，该位置就被“提交”（committed），提交点之前的日志前缀便不可更改。

日志复制还带来两个工程价值：第一，容忍乱序——节点可能先收到位置 5 的决定，还没收到位置 4，它会在本地把 5 暂存，等 4 补上后再对外呈现连续日志；第二，状态机应用——只要每个节点按同样的顺序把日志里的命令应用到状态机，所有节点最终状态完全一致。这也是“复制状态机”这一广为应用的模型的基础。

就像业委会的大事记：1 月修大门、2 月装路灯、3 月做电梯保养……只有连续写满的月份才算“板上钉钉”，刚起的草稿（未提交位置）在新旧主任交接时可能被改写。这份大事记把一个个孤立的共识串成了可无限延伸的“状态机”。

log⁡=[v1, v2, …, vc, vc+1, …],committed: [v1, …, vc]\displaystyle \log = [v_1,\ v_2,\ \ldots,\ v_c,\ v_{c+1},\ \ldots],\qquad \text{committed: } [v_1,\ \ldots,\ v_c]
日志就是“集体的大事记”：从第 1 条到第 c 条人人确认、永不改写；c 之后的条目还只是草稿，可能随 Leader 交接而变动。
  1. 日志结构$\log = [v_1,\ v_2,\ \ldots]$ 是全体节点共同维护的有序列表，每个 $v_i$ 都来自一次 Paxos 决策。
    log⁡=[v1, v2, …]\log = [v_1,\ v_2,\ \ldots]
  2. 提交前缀$[v_1,\ \ldots,\ v_c]$ 表示位置 1 到 c 都已被多数派确认，是“板上钉钉”、不可回退的既定事实。
    committed: [v1, …, vc]\text{committed: } [v_1,\ \ldots,\ v_c]
  3. 未提交后缀$v_{c+1}$ 及之后仍可能变动——如果 Leader 切换，新 Leader 可能补写或修正这些位置，然后再向前推进提交点。
    vc+1, vc+2, …v_{c+1},\ v_{c+2},\ \ldots

Raft协议对比

如果说 Paxos 是一套学术上优雅但难懂的“议会章程”，Raft 就是为工程界量身定做的“公司章程简版”。当年很多人学了 Paxos 依然实现不出正确系统，于是 Raft 的作者把目标定为“可理解性优先”，重新设计了共识协议。

两者的差异主要体现在三处：选举方式上，Paxos 靠提案编号竞争、任何节点都能发起编号更大的提案，Raft 则用随机超时触发选举、每个任期最多一个 Leader，竞争更温和；日志推进上，Multi-Paxos 允许并发提案与乱序补洞，Raft 强制“日志只能从前到后连续填充”，绝不接受跳跃；角色划分上，Raft 明确把提议权交给 Leader，简化了接受者逻辑。

从工程角度看，Raft 几乎就是 Multi-Paxos 的一个受限特例：牺牲了并行提案的灵活性，换来了便于验证的日志匹配属性和清晰的任期概念。两者安全性都经过严格证明，但 Raft 更常用于教学与商用实现（如 etcd、Consul），而 Paxos 思想则内化在 Google Chubby、ZooKeeper 等老牌系统的血脉中。

回到小区：Paxos 像一位深藏不露的老教授，能处理各种复杂局面但难懂；Raft 像一位把开会流程画成流程图的新主管，规则更死板但人人都能照着执行。理解 Multi-Paxos 再学 Raft，就像先读透议会章程再看简化版——你会更明白每条简化背后的代价与考量。

∀ i, j, k: log⁡i[k]=log⁡j[k]∧termi[k]=termj[k]  ⟹  ∀ m≤k: log⁡i[m]=log⁡j[m]\displaystyle \forall\, i,\ j,\ k:\ \log_i[k] = \log_j[k] \land \text{term}_i[k] = \text{term}_j[k] \implies \forall\, m \leq k:\ \log_i[m] = \log_j[m]
这是 Raft 的“日志匹配”性质：只要两条日志在某一位的任期和内容相同，前面所有位也必然相同。Raft 用这条硬规则换取了实现的简单性。
  1. 前提条件$\log_i[k] = \log_j[k] \land \text{term}_i[k] = \text{term}_j[k]$ 表示在节点 i 和 j 的日志里，第 k 条记录的值与任期都一模一样。
    log⁡i[k]=log⁡j[k]∧termi[k]=termj[k]\log_i[k] = \log_j[k] \land \text{term}_i[k] = \text{term}_j[k]
  2. 推导结论由上述前提可以推出 $\forall\, m \leq k$，两条日志从第 1 条到第 k 条完全相同，即前缀完全一致。
    ∀ m≤k: log⁡i[m]=log⁡j[m]\forall\, m \leq k:\ \log_i[m] = \log_j[m]
  3. 工程意义Leader 强制覆盖落后节点时，因为有这条性质打底，不可能破坏已经提交的日志，安全性因此易验证、易实现。
    LogMatch⇒Safety\text{LogMatch} \Rightarrow \text{Safety}

AI 应用场景

配置中心的“一致发布”

阶段：基础设施层（模型服务配置管理）

解决的问题：传统配置中心若用单台数据库做主备切换，切换时可能读到旧配置，导致模型服务行为不一致；AI 模型上线时，需要“全集群要么都用新配置、要么都用旧配置”。Paxos 系共识（如 ZooKeeper 的 ZAB、etcd 的 Raft）让配置写入先被多数派确认再生效，从根上杜绝了配置撕裂。这就好比业委会修改章程必须多数成员签字，而不是主任一个人说了算。

具体案例：某推荐系统团队用 etcd 保存模型特征开关。发布新特征时向 etcd 写入，只有超过半数 etcd 节点提交后，客户端才能读到新值，杜绝了“部分机器用新规则、部分机器用旧规则”的脏读问题。

分布式训练中的全局状态同步

阶段：模型训练（分布式训练协调）

解决的问题：大规模分布式训练中，多个 worker 需要同步“当前训练到第几步、checkpoint 是否有效”。若各 worker 各自记账，崩溃恢复时无法对齐。用 Multi-Paxos 思想维护一条“训练事件日志”——每个 worker 训练完一个 batch 就向日志追加一条，多数派确认后再继续，就像业委会的年度大事记一样，每个人手里的版本都一致。

具体案例：某大模型训练框架的容错模块，把“全局步数”作为日志实例：协调节点（Leader）每次追加一个步数条目，由参数服务器集群多数派确认后广播，任何 worker 崩溃重启后都从日志中恢复步数，避免重复训练或步数错乱。

模型版本发布的状态机

阶段：MLOps 模型管理

解决的问题：模型版本的上线与回滚是一个典型的状态机问题：全体推理节点必须对“当前生效版本”达成一致。把“发布 v2”“回滚 v1”等命令写成日志并按相同顺序应用，每个节点最终状态完全一致，无论灰度还是回滚都不会出现“部分节点新版本、部分节点旧版本”的混乱。

具体案例：某内容平台的模型网关，将“模型发布”命令写入共识日志；每台推理机按日志顺序切换本地模型，一旦某条发布命令被多数派确认提交，网关统一放量，回滚时同样按日志撤销，避免了部分节点卡在新版本的尴尬。

Python 演示

python69 行
class Acceptor:    """接受者：每个日志位置拥有独立的表决状态"""     def __init__(self, name, slots):        self.name = name        self.slots = slots  # slots[pos] 是该节点在日志位置 pos 的状态     def prepare(self, pos, n):        s = self.slots[pos]        if n > s["promised"]:            s["promised"] = n            return ("Promise", s["accepted_n"], s["accepted_v"])        return ("Reject", None, None)     def accept(self, pos, n, v):        s = self.slots[pos]        if n >= s["promised"]:            s["promised"] = n            s["accepted_n"] = n            s["accepted_v"] = v            return ("Accept", self.name)        return ("Reject", None)  def make_acceptors(names, positions):    return [        Acceptor(            name,            [{"promised": 0, "accepted_n": 0, "accepted_v": None}             for _ in range(positions)],        )        for name in names    ]  def basic_paxos(acceptors, pos, n, value):    """Basic Paxos：在日志位置 pos 上完成一轮两阶段决策"""    quorum = len(acceptors) // 2 + 1    promises = [a.prepare(pos, n) for a in acceptors]    promises = [r for r in promises if r[0] == "Promise"]    if len(promises) < quorum:        return False, None    best = max((r for r in promises if r[2] is not None),               default=None, key=lambda r: r[1])    final = value if best is None else best[2]    accepts = [a.accept(pos, n, final) for a in acceptors]    ok = sum(1 for r in accepts if r[0] == "Accept") >= quorum    return ok, final  def multi_paxos(acceptors, leader_n, values):    """Multi-Paxos：Leader 在连续日志位置上依次提交"""    log = []    for i, v in enumerate(values, 1):        ok, chosen = basic_paxos(acceptors, i, leader_n * 100 + i, v)        log.append(chosen if ok else None)    return log  if __name__ == "__main__":    members = make_acceptors(["M%d" % i for i in range(5)], 8)    ok1, v1 = basic_paxos(members, 1, 1, "修大门")    print("日志位置1:", v1, "选定:", ok1)    plan = multi_paxos(members, 2, ["装路灯", "电梯保养", "刷外墙"])    print("Multi-Paxos 日志:", plan)    trio = make_acceptors(["T%d" % i for i in range(3)], 4)    trio[0].accept(1, 5, "旧方案")    ok2, v2 = basic_paxos(trio, 1, 10, "新方案")    print("继承规则演示:", v2)
目的：用 5 个节点模拟业委会表决，演示 Basic Paxos 的“多数派+继承旧值”规则，以及 Multi-Paxos 在连续日志位置上提交决策的过程。
  1. s = self.slots[pos]每个日志位置有独立表决状态，位置之间互不干扰，就像不同月份的台账分开记。
  2. if n > s["promised"]:编号更大的提案才被受理，这是提案权威性的第一道门槛。
  3. promises = [a.prepare(pos, n) for a in acceptors]阶段一：向所有接受者广播 Prepare 请求，收集历史。
  4. best = max((r for r in promises if r[2] is not None), default=None, key=lambda r: r[1])从承诺中挑出“已接受编号最高”的旧提案。
  5. final = value if best is None else best[2]有旧值必须继承旧值，不能自己另选新值，这是安全性的关键。
  6. ok = sum(1 for r in accepts if r[0] == "Accept") >= quorum超过半数接受才算选定，多数派门槛由 len(acceptors)//2 + 1 得出。
  7. trio[0].accept(1, 5, "旧方案")人为制造一条“悬案”（已被某节点接受的旧提案），用来演示新提案如何被迫继承它。

常见误区

误区很多人以为 Paxos 不过是“超过一半人同意就通过”，既然最终看票数，何必搞两轮沟通？直接把提案发给所有人，数票不就完了？

正解多数派投票只解决了“数量”，没解决“继承”。Prepare 阶段的核心目的是先问出大家手里编号最高的旧提案，让新提案必须继承可能已确定的旧值。如果没有 Prepare，一个节点可能先接受 A 再接受 B 再接受 A，旧值丢失，最终既可能选出矛盾值，也可能谁都没赢。就像业委会开会不先查台账直接举手，新旧方案互相覆盖，乱成一团。

为何常见：因为多数派投票是最终表现形式，教程中两阶段细节容易被简化为“先问问再投票”，让人以为 Prepare 只是礼貌性询问，而非安全性的生命线。

误区看到"Multi"就以为是把 Basic Paxos 重复执行若干次，每个值独立跑一轮完整的两阶段，没有本质区别。

正解每一轮实例确实各是一次 Basic Paxos 决策，但 Multi-Paxos 的实质是 Leader 机制：只有 Leader 能提案，任期内只做一次 Prepare，后续实例直接 Accept，通信开销从“每值两轮”降到“每值一轮”。如果把 Leader 拿掉、让所有节点自由竞争编号，系统会频繁活锁，效率与安全性都大打折扣。

为何常见：名字“Multi“的直观字面意思就是”多次”，容易让人忽略掉它真正的增量——领导者的引入和阶段的压缩。

误区既然算法被证明“正确”，那不管什么情况，系统最后一定能在有限时间内选出某个值。

正解Paxos 保证的是安全性（Safety）：不会有两个不同的值都当选；但活性（Liveness）不保证。两个 Proposer 可以无限交替发起更大编号的提案，让多数派不断改变承诺，导致谁也无法最终定值——这种现象叫活锁。工程上用“选举唯一 Leader”和“随机退避”来规避，但理论上的 Paxos 本身不承诺“一定出结果”。

为何常见：直觉上“多数派投票”总会出结果，忽略了异步系统中消息延迟和并发竞争可以无限持续，人们常把“安全”误当成“一定完成”。

误区Raft 教学资料多、工程实现广泛，很多人因此认为 Paxos 有缺陷，Raft 是“修复版”。

正解两者安全性等价，都经过严格证明。Raft 本质上是 Multi-Paxos 的一个受限特例：固定唯一 Leader、日志只能连续追加、选举按任期轮换。它的优势在于可理解性和工程落地容易，而不是正确性更高。Paxos 的灵活性（并发、乱序补洞）在某些场景下反而是优势。

为何常见：Raft 论文以“可理解性优先”著称，通俗的教程让读者误以为“易懂=更优”，把工程上的友好误解为理论上的先进。

面试题

Q1. 在 Paxos 协议中，一个提案的值被“选定”的条件是什么？

单选题 · easy

  • A.全部接受者都接受了该提案
  • B.超过半数的接受者接受了该提案← 正确答案
  • C.提议者单独确定该提案的值
  • D.学习者统一批准该提案的值

答案：B。Paxos 采用多数派（Quorum）机制，只要超过半数（n/2+1）的接受者接受同一编号的提案，值就被选定。分布式系统无法保证所有节点同时可用，所以不要求全员同意。就像业委会表决只需要过半成员到场，不必等所有人。A 过于苛刻，C 混淆了提议者的职责，D 错在定值权在学习者之外。

Q2. 下列哪一项不属于 Paxos 协议中的标准角色？

单选题 · easy

  • A.提议者
  • B.接受者
  • C.学习者
  • D.协调者← 正确答案

答案：D。Paxos 的三个经典角色是 Proposer（提议者）、Acceptor（接受者）、Learner（学习者）。协调者不是标准角色，虽然某些资料会把 Proposer 中的主协调者单列出来，但那只是实现细节，不是协议定义的角色。做题时抓住“提议-接受-学习”三条主线即可。

Q3. 接受者收到 Prepare(n) 且 n 大于其已承诺编号时，它必须执行什么操作？

单选题 · mid

  • A.立即接受该编号的提案
  • B.更新承诺并上报最高编号已接受提案← 正确答案
  • C.拒绝并索要一个更大的编号
  • D.将该提案转发给所有其他节点

答案：B。接受者先把承诺编号更新为 n，然后在 Promise 回复中附上自己接受过的最高编号提案（编号与值）。这样提议者才能得知历史、继承可能已选定的旧值。A 是把 Prepare 误当成 Accept；C 是“n 不够大”时的行为；D 不属于接受者的职责。

Q4. 关于 Paxos 提案编号，下列说法正确的有哪些？

多选题 · mid

  • A.编号必须全局唯一且单调递增← 正确答案
  • B.编号越大的提案优先级越高← 正确答案
  • C.编号可由不同节点独立生成← 正确答案
  • D.编号较小的提案可以覆盖大编号

答案：ABC。编号必须全局唯一且单调递增，工程上常用“轮次×节点数+节点号”生成，因此不同节点可独立生成互不冲突的编号（C 对）；编号越大优先级越高，接受者承诺后不得再接受更小编号（A、B 对）。D 与承诺规则完全相反，接受者一旦承诺了 n，就再也不会接受任何编号小于 n 的提案。

Q5. Multi-Paxos 相对 Basic Paxos 最核心的优化是什么？

单选题 · mid

  • A.取消接受者角色以减少通信开销
  • B.选举 Leader 后跳过重复的 Prepare 阶段← 正确答案
  • C.让所有提案并发执行且无需排序
  • D.用随机超时替代提案编号的机制

答案：B。Multi-Paxos 先选出唯一 Leader，Leader 上任只需一次 Prepare 收集历史并确立编号优势，此后每个日志位置直接发送 Accept，把每轮两次通信降为一次。A 错在角色不能取消，否则多数派无法构成；C 错在并发仍需编号排序；D 是 Raft 的选举做法而非编号机制。

Q6. 关于 Paxos 的安全性与活性，下列说法正确的有哪些？

多选题 · hard

  • A.保证不会选出两个不同的值← 正确答案
  • B.保证最终一定会选出某个值
  • C.多个提议者竞争可能造成活锁← 正确答案
  • D.网络完全可靠时活性必然满足

答案：AC。Paxos 的安全性保证不会有两个不同的值都被选定（A 对）。但活性不保证：两个提议者不断用更大的编号打断对方，多数派不断改承诺，可能谁都定不下来，这就是活锁（C 对）。即使网络完全可靠，只要系统是异步的，冲突轮次仍可无限交替，D 过于绝对。

Q7. 为什么 Paxos 要求任意两个多数派都必须有交集？

单选题 · hard

  • A.为了保证消息能够在节点间可靠转发
  • B.为了避免两个不同值同时被选定← 正确答案
  • C.为了保证提案编号能够单调递增
  • D.为了保证学习者能获取最终的决定

答案：B。两个多数派若不相交，可能分别在互不知情的情况下选定不同值，造成“双主”矛盾。有交集意味着新提案在 Prepare 阶段必然从交集节点那里得知历史选定值，从而必须继承，从根本上杜绝双重决策。A、C、D 都与交集性质没有直接关系。

Q8. 在 Multi-Paxos 中，日志实例（instance）的用途是什么？

单选题 · easy

  • A.记录所有节点的物理部署位置
  • B.存储一系列按顺序确定的共识值← 正确答案
  • C.保存提案编号的生成与分配规则
  • D.缓存还没有被提交的临时提案

答案：B。每个日志位置对应一次 Basic Paxos 决策，所有决策按位置编号串成一条日志，节点们按序应用日志即可让状态机保持一致，这是“复制状态机”的核心思想。A 是部署元数据，C 是编号方案，D 说的是未提交日志，都不是实例的本质用途。

Q9. 关于 Raft 与 Paxos 的区别，下列说法正确的有哪些？

多选题 · mid

  • A.Raft 通过随机超时选举唯一 Leader← 正确答案
  • B.Raft 日志只能按顺序连续追加← 正确答案
  • C.Paxos 允许并发提案与乱序补洞← 正确答案
  • D.Raft 比 Paxos 具有更强的安全性

答案：ABC。Raft 用随机超时让候选者竞选任期 Leader（A 对），日志只能从前到后追加、不允许空洞（B 对）；Multi-Paxos 允许多个提案并发、日志可乱序后补（C 对）。两者安全性等价，都经过严格证明，Raft 的优势是可理解性而非更强的安全保证，D 错。

Q10. 某接受者已接受编号 5 的提案，随后收到 Prepare(8)，它应当如何处理？

单选题 · hard

  • A.拒绝该请求因为编号没有变大
  • B.更新承诺并上报编号 5 的旧提案← 正确答案
  • C.立即接受编号 8 对应的提案
  • D.删除编号 5 的记录以释放空间

答案：B。8 大于 5，接受者应把承诺编号更新为 8，并在 Promise 中带上自己接受过的最高编号提案（即编号 5 的提案），这样新提议者才能继承“可能已选定的旧值”，这正是两阶段协议保证安全的关键。A 说反了；C 跳过了先收集历史的环节；D 删除记录会破坏继承链，直接导致安全性崩溃。