Paxos 与变体

• 每个日志槽位用一次 Paxos 实例
• leader 在一个 Prepare 阶段后跳过后续 Prepare，仅用 Accept
• 与 Raft 的对应关系

Multi-Paxos 把日志看作一列槽位（instance），每个槽位对应一次 Basic Paxos 实例，用于决定该索引处的一条命令。为了让多个实例高效运行，Multi-Paxos 引入 leader：leader 在当选后发现没有更高编号的提案后，后续所有实例都只需执行 Accept 阶段（跳过 Prepare），从而把每条的复杂度从两次 RTT 降为一次 RTT。选主本身也是通过 Paxos 或专门的 leader 选举完成。由此 Multi-Paxos 实现"日志索引 + 选主"的工程化，与 Raft 的 leader + 日志复制高度对应。

Multi-Paxos 的关键工程点是"跳过 Prepare"的优化，它依赖 leader 的稳定性。Raft 实质上就是 Multi-Paxos 的一种强 leader 具体化：Raft 用 term 与随机选举简化了选主，用 AppendEntries 统一了复制。理解 Multi-Paxos 有助于理解 Raft 的来龙去脉。

• 安全性（safety）保证最多选定一个值
• 约束来自 prepare 阶段对已接受值的传递
• 与活锁（liveness）的区别

Paxos 的安全性约束保证：系统最多只能选定一个 value（即所有被选定的值都相同），且已选定的值一旦被确认就不会被更改。这由"只能 propose 一个 value"的约束 P2 及 P2c 实现：proposer 在 Prepare 阶段必须承诺，若 acceptor 已接受过某些编号的提案，则新提案必须采用其中编号最大的已接受值，否则不接受。这样即使异步，也保证了"一旦有值被选定，后续更高编号提案也必然携带该值"，从而不会出现两个不同值被选定。安全性是 Paxos 的正确性上界，任何时候都成立；而活锁是活性（liveness）问题，可在有限时间内反复出现。

安全性是 Paxos 无条件保证的，它通过"新提案必须携带已接受的最大编号值"的规则，把"选定值不唯一"的可能性排除在外。正确性由数学证明保证，与消息时序无关，这正是 Paxos 的价值所在。

• 两个 proposer 交替提高编号互相阻塞
• 活锁是活性问题，不影响安全性
• 引入 leader 保证单 proposer 消除冲突

在 Basic Paxos 中，若两个 proposer 并发发起提案，一个 proposer 提高编号后，另一个可能因发现更高编号而被迫提高自己的编号重试，二者交替升级编号、互相中断对方的提案，导致迟迟无法达成一次选定——这就是活锁。活锁不影响安全性（系统始终不会选定错误值），只影响活性（一直无法完成）。为消除活锁，实际操作引入 leader 选举：保证任意时刻只有一个 proposer（leader）发起提案，从而避免多个 proposer 竞争冲突。这样即使 leader 偶尔失败，也会通过选举尽快产生新的单一 proposer，恢复正常推进。

活锁的根源是"多个 proposer 并发竞争"。Paxos 论文本身不解决活性，实际部署（如 Multi-Paxos、Raft）都通过"选唯一 leader"来规避。leader 选举把活性从"概率性"提升为"确定性"，是工程上对 Paxos 的必要补充。

• Chubby 基于 Paxos 的分布式锁服务
• Zab 是 Zookeeper 的原子广播协议，与 Paxos 的关系
• 它们如何实现高可用协调服务

Google Chubby 是基于 Paxos 的分布式锁/协调服务，为 GFS、Bigtable 等提供一致的锁与元数据，其核心是 Paxos 副本组对日志的复制。Zookeeper 使用 Zab（Zookeeper Atomic Broadcast）协议：Zab 与 Paxos 同属"primary 复制 + 多数派"一族，但更强调"广播全序"（所有事务按提交顺序应用），通过 leader 选举、发现、同步、广播四阶段实现全序广播。两者都以"领导者 + 复制日志 + 多数派确认"实现高可用的协调状态机，是 Paxos 思想在工业界的经典落地。

Chubby 直接采用 Paxos，Zab 是其变体。二者的共同点是提供"线性一致的全序广播"给上层（锁、元数据、配置），证明 Paxos 思想适用于真实的高可用协调服务，也启发了后续 Raft 与 etcd。

• quorum 相交的必要性（多数派交集非空）
• 集合论证明：|A|+|B|>N 则 A∩B≠∅
• 相交如何保证"一旦选定，值唯一且持久"

设系统共 N 个节点，多数派 quorum 大小为 ⌊N/2⌋+1（即 >N/2）。任意两个 quorum A、B，若两者不相交，则需要 |A|+|B|≤N。但 |A|+|B| ≥ 2·(N/2+1) = N+2 > N，矛盾。因此任意两个 quorum 必然相交。这一性质保证：选定值的过程（如 Prepare/Accept）与后续查询（如 Learn）必然经过至少一个共同节点，从而"已被选定的值"必然被后续任何 quorum 观察到，不会出现两个不同值在各自 quorum 中被选定。相交是 Paxos 安全性（唯一值、持久性）的集合论基础。

多数派相交是分布式共识的安全基石。它保证了"写与读、两次写"之间必然有交集，使得已选定的值能被后续的多数派覆盖确认，从而唯一且持久。这也解释了为什么 Raft、Zab 等都采用多数派作为 quorum。

• Cheap Paxos 降低副本数（f+1 即可）
• Fast Paxos 减少提交延迟（一次 RTT）
• Egalitarian Paxos 多 leader 提高吞吐

Cheap Paxos 在多数派 primary 之外，用更少的额外 acceptor（f+1）实现容错，从而降低资源成本，仅当主 quorum 故障时才需要额外 acceptor。Fast Paxos 允许在多数派接受后由领导者直接提交，把提交延迟降到一次 RTT（更优的配置），但要求特定 quorum 以避免冲突。Egalitarian Paxos（EPaxos）允许多个 leader 并发提交，通过"依赖"追踪实现无主快速路径，提升吞吐与可用性，但复杂度高。三者都是对 Paxos 在不同维度（成本、延迟、吞吐）的优化变体。

这些变体体现 Paxos 家族的演化方向：Cheap Paxos 优化成本，Fast Paxos 优化延迟，EPaxos 优化吞吐与可用性。它们揭示 Paxos 不是一个协议而是一个家族，工程上按需求选择合适变体。

• Raft 的 AppendEntries 对应 Multi-Paxos 的 Accept
• Raft 的 term 与选举对应 Multi-Paxos 的选主
• Raft 的强 leader 简化了 Paxos 的复杂流程

Raft 可以看作 Multi-Paxos 加上强 leader 约束的具体化。Multi-Paxos 中 leader 稳定后跳过 Prepare 只做 Accept，Raft 的 AppendEntries 正是这种"只复制日志"的体现；Raft 的 term 相当于 Paxos 的 ballot/round 编号，Raft 的 leader election 对应 Multi-Paxos 的选主；Raft 的日志复制与提交（多数派确认）对应 Multi-Paxos 的日志实例。Raft 的"强 leader"意味着所有读写都经 leader，日志追加顺序严格，从而合并了 Paxos 中"选值 + 传值"的复杂逻辑，使协议更简单直观。

理解"Raft = Multi-Paxos + 强 leader"能帮助把 Raft 的机制映射到 Paxos 术语，从而理解两者本质相同、只是 Raft 以可理解性为优先做了简化。工程上多数实现会选择 Raft 因其易实现。

• proposer 发起提案
• acceptor 存储并决定接受
• learner 不参与决议，学习结果

Paxos 中 proposer 负责发起提案（提出 value），它向 acceptor 发送 Prepare/Accept 请求；acceptor 是存储节点，负责响应 Prepare（承诺不再接受更低编号提案）与 Accept（接收并持久化 value），是决定提案是否被接受的关键角色；learner 不参与决议过程，只负责在学习阶段（Learn）获取最终被选定的 value，以便复制结果。角色可以重叠（一个节点可同时充当三种角色）。这种三角色分离使 Paxos 的职责清晰，便于分析和实现。

三角色划分是 Paxos 抽象能力的体现：proposer 提出、acceptor 决定、learner 获知。灵活的角色组合（如多角色合一）对应不同工程实现，例如 Raft 中 leader 兼具 proposer 与 learner。

• quorum 是达成一致所需的最小节点集合
• 多数派容错上限：N=2f+1 可容忍 f 个故障
• 多数派相交保证安全

在 Paxos 中，quorum 是"达成一次决议所需的最小节点集合"，通常取多数派（>N/2）。多数派作为容错单元决定了系统能容忍的故障数：N 个节点中，多数派大小为 ⌊N/2⌋+1，因此最多能容忍 f=⌊(N-1)/2⌋ 个故障（N=2f+1）。只要多数派存活，系统就能继续决议。多数派相交保证任何两次决议（Prepare 与 Accept、Accept 与 Learn）必然经过共同节点，从而安全与持久。多数派是 Paxos 容错与安全性的统一基础。

多数派是"安全与可用"的平衡点：取太少则无法相交、不安全，取太多则容错过差。N=2f+1 给出了最小冗余的容错方案，这一结论也适用于 Raft、Zab 等所有多数派协议。

• Single-Decree 只决定一个 value
• Multi-Paxos 用多个实例决定日志序列
• Multi-Paxos 的 leader 优化

Single-Decree Paxos（Basic Paxos）只解决"一个 value 的选定"问题，通过 Prepare/Promise/Accept/Accepted 两阶段从多个候选值中选定一个。Multi-Paxos 把多个 Basic Paxos 实例应用到日志的每个槽位，从而决定一列有序的命令（即日志），它通过 leader 选举实现"稳定 leader 跳过 Prepare"的优化，使每个新命令只需一次 RTT。Multi-Paxos 才是实际可用的复制日志协议，而 Single-Decree 是它的理论基石。Raft 可视为 Multi-Paxos 的强 leader 实现。

二者的关系是"基础与组合"：Single-Decree 一个实例决定一个值，Multi-Paxos 用多个实例构成日志序列。理解 Single-Decree 是理解 Multi-Paxos 及 Raft 的前提。

• Prepare 阶段：proposer 提出编号 n，acceptor 承诺
• Promise 阶段：acceptor 承诺忽略小于 n 的提议
• Accept 阶段：获得多数派 Promise 后提交值并广播 Accepted

Basic Paxos 将共识分为两个阶段。第一阶段 Prepare/Promise：proposer 提出一个递增的编号 n，向所有 acceptor 发送 Prepare 请求；acceptor 若收到编号为 n 的 Prepare，且 n 大于其已承诺的编号，则承诺不再接受编号小于 n 的提议，并返回其已接受的最大编号提议的值（若有）。第二阶段 Accept/Accepted：proposer 若收到多数派（>N/2）的 Promise，则从中选择编号最大的已接受值（若无则用自己的值），向 acceptors 发送 Accept 请求（编号 n 与值 v）；acceptor 若未承诺过更大的编号，则接受该提议并向 proposer 返回 Accepted。proposer 收到多数派 Accepted 即认为该值 v 被选定。若出现冲突或未获得多数派，则增大编号重试。

Basic Paxos 的两阶段通过"承诺忽略更小编号"保证唯一性：任一已选定的值被多数派接受，后续更高编号的提议只能选择该值（不能覆盖），从而保证一致性。重试时需提高编号，代价是可能产生活锁。

• P2c：更高编号提案必须携带已接受的最大编号值
• Prepare 阶段接受方承诺拒绝更小编号
• 这如何防止旧值被采纳、保证唯一值

P2c 约束是 Paxos 安全性的核心：如果某个值 v 已被编号为 n 的提案选定，则任何编号更大的提案也必须携带值 v。它的实现方式是：proposer 在 Prepare 阶段必须承诺，若多数派 acceptor 返回了 Promise 及其已接受的最大编号提案的值，则新提案必须采用该值（若没有则可用任意值）。同时 acceptor 在 Prepare 阶段承诺"不再接受编号小于当前承诺编号的提案"，从而限制了旧提案被采纳。P2c 保证"一旦选定 v，后续提案只能选 v"，杜绝了不同值被选定的可能。

"acceptor 必须接受编号更大的提案"配合"proposer 必须继承已接受的最大编号值"，共同构成 P2c。Prepare 阶段用编号承诺限制了旧提案，Accept 阶段用值继承保持了正确性，二者缺一不可。

• 两个 proposer 交替提高编号的互相阻塞时序
• 活锁的机理（编号升级竞赛）
• Multi-Paxos 选主消除竞争

经典 Paxos 活锁时序：proposer P1 提出编号 1 的 Prepare，P2 提出编号 2 的 Prepare；P1 收到 Promise 后准备 Accept(1)，但此时 P2 的 Prepare(2) 已让 acceptor 承诺不接受编号 1。P1 只好提高编号到 3 重发 Prepare，而 P2 准备 Accept(2) 时又发现 P1 的 Prepare(3) 已让 acceptor 承诺不接受 2，于是 P2 提高到 4……如此交替升级，两个 proposer 永远无法完成 Accept，形成活锁。Multi-Paxos 通过选举单一 leader，保证任意时刻只有一个 proposer 发起提案，从而根除多 proposer 竞争，消除活锁。即使 leader 失败，也会迅速选举新 leader 恢复单一 proposer。

活锁的本质是"多个 proposer 的编号升级互相作废对方提案"。Multi-Paxos 用"单 leader"从源头消除竞争，把活性从随机性变为确定性。这是 Paxos 理论到工程实践的关键一步。

• PBFT 容忍拜占庭故障（恶意/任意行为）
• PBFT 需要 3f+1 节点、三阶段
• 相比 Paxos 的容错假设更强

PBFT 是拜占庭容错协议，在节点可能恶意/任意行为（拜占庭故障）时仍保证一致性。它需要 3f+1 个节点才能容忍 f 个拜占庭节点，通过三阶段（Pre-prepare/Prepare/Commit）与 view change 实现。相比 Paxos（假设崩溃故障 CFT），PBFT 的容错模型更强，也因此在通信复杂度、节点数上成本更高。PBFT 常用于区块链等需要抵抗恶意节点的场景。Paxos 是 PBFT 的崩溃容错前提，PBFT 是 Paxos 在拜占庭模型下的扩展。

拜占庭模型与崩溃模型的关键区别是"节点是否可能撒谎/作恶"。PBFT 用 3f+1 冗余与多阶段投票来对抗恶意节点，是 BFT 的经典实现，也是区块链共识（如 Tendermint、HotStuff）的基础。

• TLA+ 形式化验证协议状态机
• 用模型检查发现并发下的边界缺陷
• 从"证明"到"工程验证"的价值

TLA+（Temporal Logic of Actions）是一种形式化规范语言，用于描述并验证分布式算法的状态机与不变量。Paxos 作者 Leslie Lamport 正是用 TLA+ 描述 Paxos，并借此验证其安全性。TLA+ 的工程价值在于：可以在实现前用模型检查器（TLC）穷举有限状态空间，自动发现并发、消息乱序、故障下的边界缺陷，从而在编码前验证协议正确性。它把"正确性"从依赖人工论证提升为可机器检查的保证，显著降低实现缺陷风险。

TLA+ 隔离了"协议设计"与"实现"，先用模型等价验证协议正确，再在实现中对照规范。这种"先验证后实现"的工程方法对分布式系统尤其有价值，因为其并发缺陷极难通过测试发现。

• Raft 用强 leader 简化 Multi-Paxos 的选主
• Raft 用 AppendEntries 统一日志复制
• Raft 的清晰子问题划分

Raft 是 Multi-Paxos 的简化实现，核心简化在"强 leader"与"日志复制"：Raft 明确随机选举 + 心跳维持单一 leader，替代 Multi-Paxos 中多 proposer 的复杂选主与冲突处理；Raft 用 AppendEntries 统一承载日志复制与心跳，通过 prevLogIndex/prevLogTerm 一致性检查解决日志对齐，替代 Multi-Paxos 中每个实例独立的 Prepare/Accept。Raft 把协议拆解为选主、复制、安全三个子问题，机制更明确、实现更简单，同时保持与 Multi-Paxos 相同的安全性。这就是"Raft = Multi-Paxos + 强 leader"的工程含义。

Raft 的价值在于"在保持正确性前提下极大降低实现复杂度"，通过强 leader 消除多 proposer 竞争，通过统一日志复制消除多实例歧义。这使 Raft 成为生产系统（etcd、TiKV）的主流选择。

• 轮值/单一 leader 保证单一 proposer
• 消除多 proposer 编号竞争
• leader 故障时重新选举

Paxos 在实际应用中通过引入"领导者选举"来解决活锁：保证任意时刻只有一个节点（leader）充当 proposer，从而不存在多个 proposer 交替提高编号的竞争，也就不再产生活锁。所谓"轮值领导者"指通过某种机制（如轮流、超时重选）确定当前 leader，当 leader 故障时其余节点重新选举出新的单一 leader。Multi-Paxos 与 Raft 都采用这一思路：用 leader 把"proposer 的多样性"简化为"唯一性"，从机制上消除冲突与活锁，同时保持安全性不变。

活锁是"多 proposer"的必然副作用，领导者选举从源头上把 proposer 数量降为 1，从而消除竞争。这是 Paxos 家族从理论到工程的关键收敛，也是"选主"为何成为所有共识协议标配的原因。