Paxos
Paxos 是一类共识协议，让节点在消息延迟、丢失和部分节点故障时，仍不会为同一个决策选出两个不同的值。Basic Paxos 解释一次决策；Multi-Paxos 把多次决策组织成日志，并通过稳定领导者减少重复协调。
理解它的关键不只是记住 Prepare 和 Accept 两个阶段，而是能回答：换了提议者、消息晚到了，甚至已经成功但没人收到回复时，为什么后面的提案还不能推翻已经选定的值？本文采用固定成员、普通多数派和非拜占庭故障模型。
1. 面试核心
先记住这几条，再读正文- Basic Paxos 为单个决策位置选定一个值；Multi-Paxos 面向一系列日志位置，稳定领导者可复用第一阶段的结果，逐个位置继续执行第二阶段。卡 · 角色与决策对象
- 提案编号必须全局可比较且不被错误复用。编号用来区分竞争轮次，不是业务值的大小，也不是日志位置。
- Prepare 同时取得拒绝更低编号的承诺和已接受提案的信息；提议者要继承响应中最高编号已接受提案的值，不能总选自己的新值。卡 · 新提案为什么必须继承旧值
- 单个节点接受不代表选定。同一提案被多数接受才构成选定，提议者是否收到回复是另一件事。卡 · Accept：请求接受具体提案
- 多数相交要与承诺、继承规则及持久状态一起使用。节点重启后不能忘记相关承诺和已接受记录。卡 · 回复丢失、重启与推进条件
- 安全性不等于总能推进。竞争提议者反复抢占、失去多数或通信持续不稳定，都可能使协议暂时无法选定新值。卡 · 回复丢失、重启与推进条件
2. 角色与决策对象
一次共识要在候选值中选出一个结果。假设三个节点共同维护配置，当前决策是“这次配置修订采用 blue 还是 green”。我们希望某个结果选定以后，任何后续恢复都不能把同一次决策改成另一个结果；下一次配置修订则属于新的决策。
协议把职责分成三类，同一个进程可以同时承担多种角色：
| 角色 | 职责 |
|---|---|
| Proposer，提议者 | 发起提案，收集响应，决定这一轮能够提出什么值 |
| Acceptor，接受者 | 记录承诺与已接受提案，按规则接受或拒绝请求 |
| Learner，学习者 | 获知哪些提案已经被多数接受，从而知道选定结果 |
提案包含编号和候选值，例如 (10, blue)。编号需要形成全序：任意两个不同编号都能比较先后。实现可以使用 (递增轮次, 节点标识) 按字典序比较，但节点重启也不能重新用旧编号提出另一个值。下面为了便于推演，只写互不重复的整数编号。
法定人数（quorum）是能够满足协议决策条件的节点集合。本文采用多数派，三个接受者 A、B、C 中任意两个就构成多数，任意两个多数集合必然至少共享一个接受者。
接受者不是“这一生只投一次票”。它可以在更高编号的提案中再次接受，协议要保证同一个决策中已经选定的值不被后续轮次改变。如果一旦接受就永远不再参与，三个节点各自接受不同提案后，就可能没有任何值取得多数。
3. Prepare 与 Accept
两个阶段解决不同问题：Prepare 为这一轮建立安全的提交条件；Accept 才请求接受具体的值。接受者需要保存最高承诺编号，以及自己接受过的最高编号提案。对同一决策，同一提案编号不能被用于两个不同值。
3.1 Prepare：取得承诺并收集历史
提议者选择新的编号 n，发送 Prepare(n)。接受者在 n 高于自己已经承诺的编号时，记录新承诺：以后不再接受编号小于 n 的提案。同时，它回复自己已接受的最高编号提案；从未接受过则报告为空。
提议者需要取得多数接受者针对 n 的有效承诺，才能进入第二阶段。此时按响应选择值：
- 响应中没有已接受提案，可以采用自己原本想提出的值。
- 只要有已接受提案，就采用其中提案编号最高的那一个所携带的值。
比较的是提案编号，不是 blue、green 这样的业务值，也不是哪个值在这批响应里出现得更多。这里收集到的历史还不一定能证明某个值已经被选定，但它足以约束这一轮能安全提出什么。
3.2 Accept：请求接受具体提案
提议者发送 Accept(n, v)。接受者若没有承诺过更高编号，就可以接受它，保存已接受提案后回复；如果已经承诺更高编号，则拒绝这个旧请求。
已选定（chosen）表示同一提案已经被多数接受者接受。三个节点中，只要 A、B 接受 (10, blue)，blue 就已经选定；不必等待 C。学习者取得多数接受的信息后，才知道这个结果已经成立。
Prepare 成功不是预订了一个永久有效的执行机会。它与 Accept 之间，另一个提议者可能用更大的编号取得承诺，使当前轮次的 Accept 被拒绝。原提议者需要观察更大编号，选择新的编号重新尝试。
4. 新提案为什么必须继承旧值
先看已经选定的情况。假设 A、B 已接受 (10, blue)，C 没收到它，新提议者原本想提出 green：
| 步骤 | A | B | C | 这一轮能做什么 |
|---|---|---|---|---|
| 初始 | 已接受 (10, blue) | 已接受 (10, blue) | 未接受 | blue 已选定 |
Prepare(20) 到达 B、C | 未参与 | 承诺 20，报告 (10, blue) | 承诺 20，报告为空 | 多数承诺取得，但必须选择 blue |
Accept(20, blue) 到达 B、C | 保留原记录 | 接受 (20, blue) | 接受 (20, blue) | 更高编号仍选定同一个值 |
旧多数 {A, B} 与新多数 {B, C} 共享 B，因此新提议者不会只看到一片空白。如果后续轮次又带来了更高编号的已接受提案，同样的继承约束会沿着这些轮次传递，保护原先选定的值。
多数相交本身还不够。假设新提议者听到 B 报告的 blue 后仍执意发 Accept(20, green)，B、C 从编号检查上都可能允许它。这样先前的多数选定 blue，新的多数又选定 green，安全性就被破坏了。接受者遵守编号承诺，并不能替提议者完成正确的值选择。
4.1 只被一个节点接受的值，能被替换吗？
可能，但不能随意替换。假设 (10, blue) 只被 A 接受，B、C 都未接受任何提案。新提议者从 B、C 取得 Prepare(20) 的承诺，响应全为空，就可以提出 green。
这时 B、C 已承诺拒绝低于 20 的提案，即使迟到的 Accept(10, blue) 随后到达，它也无法再取得多数。新提案因此能够安全地选定 green。这不推翻已选值，因为旧提案此前只有一个接受者。
反过来，如果新提议者询问的是 A、B，它就会看见 (10, blue)，并必须继承 blue。提议者不需要、也不能只凭这一份报告断言 blue 早已被多数选定；它是在遵守足以保护所有可能历史的规则。
5. 回复丢失、重启与推进条件
客户端超时只说明调用者没有及时拿到结果，不证明提案未选定。如果 A、B 已接受提案，但回复丢失，结果仍然已经选定。后续提议者按 Prepare 与继承规则恢复，不能把“我不知道结果”解释为可以覆盖它。
接受者的承诺和已接受记录需要在相应回复之前持久化。若 B 重启后忘记已经接受 (10, blue)，新提议者向 B、C 查询时可能错误地看到两份空历史，进而选出不同值。持久存储是恢复模型的前提，不是可以随意省略的性能优化。
安全性要求不出现冲突决策；活性关注是否最终能完成决策。两个提议者可以不断用更大编号互相抢占：一方刚完成 Prepare，另一方就把多数的承诺推进到更大编号，前者的 Accept 因而失败。每一步都守规则，也可能一直没有结果。
实际系统会设法形成稳定领导者，减少这种竞争，并通过重试和超时处理消息丢失。继续推进还要求领导者能够与足够的接受者持续通信。纯异步故障模型下，不能仅凭“存在多数存活节点”就保证所有执行都终止。
固定 2f+1 个接受者时，最多 f 个不可用后仍可能保有多数，但剩余节点必须能够通信。三个节点分成两台和一台的分区时，两台的一侧才有继续形成多数的条件；单独一台不能绕过多数要求继续选定新值。协议假设节点遵守规则，不处理恶意伪造或相互矛盾的响应。
6. Multi-Paxos 与连续日志
Multi-Paxos 把共识用于一系列日志位置，让副本对每个位置的命令达成一致。位置 1 可以是“设置配置为 blue”，位置 2 可以是“设置配置为 green”；两个不同位置选择不同值并不冲突。
这里需要分清两个编号：
| 编号 | 表示什么 | 关系 |
|---|---|---|
| 提案轮次编号，ballot | 谁正在尝试以哪一轮领导权协调提案 | 一个 ballot 可以用于多个日志位置 |
| 日志位置，slot | 这一条命令在序列中的位置 | 同一个 slot 可能经历多个 ballot 才选定 |
稳定领导者可以用一个 ballot，为一组日志位置统一完成第一阶段，并收集这些位置的已接受信息。此后在这轮领导权仍有效、对应位置已受第一阶段覆盖时，新命令可以直接进入第二阶段，仍需多数接受。它省掉的是每条命令重复进行 Prepare 的成本，没有省掉多数确认。
领导者切换时，新领导者必须重新取得更高 ballot 的多数承诺，并按每个日志位置继承报告中最高 ballot 对应的值。不能因为换了领导者，就把自己本地没看见的命令全部覆盖。旧领导者即使暂时仍认为自己有效，也会受到接受者更高承诺的限制。
日志位置可以并行协商，但状态机需要按确定的连续顺序执行。若位置 3 已选定，位置 2 仍未确定，就不能先执行 3 再补 2。恢复时可在确认没有必须继承的值之后，为空缺位置提出 no-op（不改变业务状态的命令）；no-op 自身也要经过共识，不能本地填上就算完成。
6.1 Basic Paxos 与 Multi-Paxos 的分工
| 比较点 | Basic Paxos | Multi-Paxos |
|---|---|---|
| 决策对象 | 一个值 | 一系列日志位置上的值 |
| 基本规则 | Prepare 收集承诺与历史，Accept 请求多数接受 | 保留相同安全约束，并管理多个位置 |
| 稳定领导者的作用 | 可减少同一次决策中的提案竞争 | 还可把第一阶段成本分摊到多条日志 |
| 故障恢复 | 保留单次决策可能已选定的值 | 逐位置恢复历史、处理空缺，再按序执行 |
Multi-Paxos 不是“多几个提议者”，也不是把 Basic Paxos 的多数条件取消。Raft同样面向复制日志，但用更明确的领导者选举、日志匹配和提交规则组织协议。比较两者时应对齐日志复制的范围，不能把“Paxos 没有 Leader”或固定的性能高低当成通用结论。
共识日志也不会自动解决业务重复执行。客户端超时重试可能让同一业务请求出现在多个位置，仍需请求标识、去重和结果记录；外部副作用的恢复见分布式流程恢复。
7 · 面试题卡片
本页题目与参考回答
7.1 什么是 Paxos，Basic Paxos 和 Multi-Paxos 有什么区别？
考察重点：单值共识、复制日志、两阶段规则与稳定领导者的作用。
相关内容：角色与决策对象、Multi-Paxos 与连续日志。
参考回答
Paxos 通过承诺、历史继承与多数接受，使同一次决策不会选出不同值；Basic Paxos 处理单次决策，Multi-Paxos 把它用于连续日志。
Basic Paxos 用 Prepare 收集多数承诺和已接受提案，按规则选择值，再用 Accept 请求多数接受。Multi-Paxos 为每个日志位置选择命令，稳定领导者可以统一完成多个位置的第一阶段，后续命令主要执行第二阶段。
新领导者仍要恢复已有提案，保留各位置可能已选定的值。稳定状态下减少协调轮次，不意味着跳过多数确认或不再处理故障。
7.2 Prepare 收到已接受提案后，为什么不能继续提出自己想要的新值？
考察重点：多数相交、最高编号历史的继承，以及已接受与已选定的区别。
相关内容：新提案为什么必须继承旧值。
参考回答
**这个值可能已经被多数选定，提议者必须继承本次多数响应中最高编号已接受提案的值。**新旧多数相交，使先前可能已选定的值能够通过历史报告传递下来；承诺则限制旧提案继续取得新的接受。
单份报告不一定证明值已经选定，但随意忽略它可能推翻真实存在的旧多数。只有本次多数响应都没有已接受提案时，提议者才可自由选择自己的值。
7.3 提议者超时，没有收到多数回复，能断定值尚未选定吗？
考察重点：接受事实、学习结果与客户端观测的区别。
相关内容：请求接受具体提案、回复丢失、重启与推进条件。
参考回答
**不能，多数接受可能已经发生，只是回复丢失或延迟。**选定由接受者实际接受同一提案的事实决定，不取决于提议者是否及时看到回复。
恢复应继续遵守 Prepare 和历史继承规则。不能把超时直接当作失败并覆盖旧决策，业务调用也要考虑结果未知后的去重与查询。
7.4 接受者重启后，为什么不能只从空状态重新加入？
考察重点：持久承诺、已接受记录与故障恢复的安全前提。
相关内容：回复丢失、重启与推进条件。
参考回答
**空状态会遗忘原有承诺和已接受提案，可能让新的多数选出与旧决策冲突的值。**接受者必须在发送相应回复前持久化这些信息，重启后继续遵守。
若持久数据确实丢失，需要按系统的恢复或成员变更协议处理，不能让同一个接受者身份直接把历史清零后继续计票。提议者也不能重用旧编号提出另一个值。
7.5 多数节点都在线，为什么 Paxos 仍可能一直没有结果？
考察重点：安全性与活性、提案抢占及稳定通信条件。
相关内容：回复丢失、重启与推进条件。
参考回答
**在线不等于能完成一轮有效协调，竞争提议者可能反复抬高承诺编号，使对方的 Accept 不断被拒绝。**消息持续延迟或丢失也会阻止收集多数响应。
稳定领导者、合适的重试与超时可以帮助推进，但仍依赖能够持续通信的多数。没有结果与产生冲突结果是两回事，安全规则不能因为暂时无法推进就被取消。
8. 参考资料
- Leslie Lamport：Paxos Made Simple，第 2、3 节
- Robbert van Renesse、Deniz Altınbüken：Paxos Made Moderately Complex，协议与活性说明
来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明