Paxos 与 Raft 深度对比：分布式共识算法的工程实践
引言
在分布式系统中，共识算法（Consensus Algorithm）是解决多个节点之间数据一致性的核心算法。无论是分布式数据库、分布式存储系统，还是微服务协调服务（如 ZooKeeper、etcd），共识算法都是其底层基石。
多年来，Paxos 一直是分布式共识领域的主导算法，但其难以理解和实现的窠臼也饱受诟病。直到 2014 年，Diego Ongaro 和 John Ousterhout 提出了 Raft 算法——一种以"可理解性"为首要目标的共识算法，彻底改变了分布式共识的工程实践格局。
本文将从原理推导、工程实现、性能对比和实战选型四个维度，对 Paxos 和 Raft 进行深度对比分析。
一、共识问题的本质
1.1 什么是共识？
在分布式环境下，共识问题可以简单描述为：多个节点就某个值达成一致。一个正确的共识算法必须满足以下三个性质：
终止性（Termination）：所有最终决定一个值，且该值是某个节点提出的。
协定性（Agreement）：不能有两个不同的值被决定。
有效性（Validity）：被决定的值必须是某个提案者提出的。
1.2 FLP 不可能定理
Fischer、Lynch 和 Paterson 在 1985 年证明了著名的 FLP 不可能定理：在异步网络模型中，即使只有一个进程可能崩溃，也没有确定性算法能解决共识问题。
这个定理告诉我们，要获得实际的共识算法，必须引入一些额外的假设：部分同步模型、故障检测器、随机化或领导者选举机制。Raft 和 Paxos 都采用了领导者选举 + 日志复制的方式来突破 FLP 障碍。
二、Paxos 算法深度解析
2.1 历史背景
Leslie Lamport 在 1998年发表了《The Part-Time Parliament》论文，以虚构的 Paxos 岛上被部分时间工作的议员（part-time parliament）来描述算法，导致论文晦涩难懂。2001年，Lamport 改用更直白的语言重新发表了《Paxos Made Simple》，但这依然被认为是最难理解的分布式算法之一。
2.2 Paxos 的角色模型
Paxos 算法中，节点扮演三种角色（同一节点可以同时扮演多个角色）：
提案者（Proposer）：负责提出提案值，推动共识流程。
接受者（Acceptor）：负责对提案进行投票，一个提案需要获得多数接受者的同意才能被选定。
学习者（Learner）：学习被选定的值，不参与投票过程。
2.3 Paxos 的两阶段执行
Paxos 的执行分为两个阶段：
阶段一：Prepare 阶段
- Proposer 选择一个提案编号 n，向多数 Acceptors 发送 Prepare(n) 请求
- Acceptor 收到 Prepare(n) 后，如果 n 大于其之前响应过的所有提案编号，则承诺不再接受编号小于 n 的提案，并返回已接受过的最大编号提案（如果存在）
阶段二：Accept 阶段
- Proposer 收到多数 Acceptors 对 Prepare(n) 的响应：
- 如果响应中没有已接受的提案值，则可以自由选择自己的值 v
- 如果响应中包含了已接受的提案，则必须选择其中编号最大的提案的值 v
- Proposer 向多数 Acceptors 发送 Accept(n, v) 请求
- Acceptor 收到 Accept(n, v) 后，只要尚未响应过编号大于 n 的 Prepare 请求，就接受该提案
2.4 Paxos 的关键特性
提案编号全序性：每个提案都有一个全局唯一的、单调递增的编号（通常用 (round_number, server_id) 二元组实现），这保证了提案之间的全序关系。
多数派交集原理：两个多数派必然存在交集，这保证了如果某个值已经被选定（获得多数派接受），后续的任何 Prepare 阶段都能"看到"这个值。
活性保证：如果多个 Proposer 同时提案，可能产生活锁（每个都不断提出更高编号的 Prepare），通常通过随机退避或选举 Leader 来解决。
三、Raft 算法深度解析
3.1 设计哲学
Raft 的设计哲学是 "可理解性优先"（Understandability First）。Ongaro 和 Ousterhout 认为：
我们不能在获得可用（usable）的同时，不牺牲可理解性（understandability）。
Raft 采用两个核心策略： - 分解（Decomposition）：将共识问题分解为领导者选举、日志复制、安全性三个相对独立的子问题 - 减少状态空间（State Space Reduction）：通过更清晰的状态转换规则消除不确定性
3.2 Raft 的三种状态
在任一时刻，每个节点处于以下三种状态之一：
Leader：处理所有客户端请求，复制日志给 Follower，通常系统中只有一个 Leader。
Follower：被动响应 Leader 和 Candidate 的请求，不主动发起请求。如果收不到 Leader 的超时心跳则转变为 Candidate。
Candidate：发起 Leader 选举，获得多数票即成为 Leader。
3.3 领导者选举机制
随机超时（Randomized Timeout）：每个 Follower 维护一个随机化的选举超时（通常 150ms~300ms）。当超时时间内未收到 Leader 心跳，Follower 转变为 Candidate 并发起选举。
选举流程： 1. Candidate 递增当前 Term（任期号），为自己投票，向其他节点发送 RequestVote RPC 2. 每个节点在同一 Term 只能投一票（先到先得） 3. 如果 Candidate 获得多数票，成为 Leader，向其他节点发送心跳（AppendEntries RPC，entries 为空）巩固领导地位 4. 如果 Candidate 收到更高 Term 的 RPC，退回到 Follower 状态 5. 如果选举超时后仍无结果，重新发起新一轮选举
安全性保证：RequestVote RPC 中包含候选人的日志信息，投票者会拒绝日志不如自己新的候选人的投票请求，确保新 Leader 一定包含所有已提交的日志条目。
3.4 日志复制机制
Leader 接收到客户端命令后：
- 将命令作为新日志条目追加到本地日志
- 并行向所有 Follower 发送 AppendEntries RPC
- 收到多数 Follower 的确认后，认为日志条目已提交（committed），应用到状态机
- 通知 Follower 提交该条目
日志匹配特性：如果两个日志条目具有相同的索引和 Term，则这两个条目之前的所有日志条目也相同。
3.5 安全性保证
Raft 通过以下机制保证安全性：
选举限制：Leader 必须包含所有已提交的日志条目
提交规则：Leader 不能通过计算副本数来提交之前 Term 的日志条目，只能通过提交当前 Term 的日志来间接提交之前 Term 的日志
日志压缩与快照：当日志过大时，Raft 使用快照（Snapshot）机制压缩快照之前的日志
四、核心差异对比
4.1 设计哲学的差异
Paxos 追求理论上的优雅和通用性。它是基于数学归纳法证明的正确性证明构建的，但其设计并未刻意追求易于实现。Paxos 论文中假设的是一个理想化的异步消息传递模型。
Raft 则从工程实践角度出发，将算法设计得更接近实现的形态。其论文中几乎每个伪代码片段都可以直接翻译为实际的工程代码。
4.2 领导模型差异
Paxos 本质上是一个无固定领导者的系统。虽然 Multi-Paxos 通过选举 Leader 来优化性能，但标准 Paxos 允许多个 Proposer 同时提案，理论上没有 Leader 的概念。
Raft 采用强 Leader 模型。系统中任何时候只有一个 Leader，所有请求都必须经过 Leader。这简化了系统行为，但也引入了 Leader 单点性能瓶颈。
4.3 日志连续性
Paxos 不保证日志的连续性。Acceptors 可能会接受"空洞"日志（即之间存在缺失条目的状态）。Paxos 协议只保证最终能够就某个位置的值达成共识，但不保证位置的连续性。
Raft 强制日志必须是连续的。Followers 必须严格按照 Leader 指定的顺序接受日志条目。这简化了日志管理和快照机制，但对日志复制效率有一定影响（缺失的条目需要重传）。
4.4 成员变更
标准 Paxos 对成员变更（增减节点）没有明确的协议规定，需要额外的机制来实现。Multi-Paxos 的各种实现自行处理成员变更。
Raft 明确内置了联合共识（Joint Consensus）机制来处理成员变更。新配置通过一个过渡的配置（Cold,new）来保证新旧多数派之间始终存在交集。
4.5 消息复杂度
单次 Paxos 达成共识（未优化的 Basic Paxos）的消息复杂度为 2 轮 RPC： - Proposer → Acceptors（Prepare）→ Acceptors → Proposer - Proposer → Acceptors（Accept）→ Acceptors → Proposer
Raft 的领导者选举平均需要 1~2 轮 RPC，后续日志复制仅需 1 轮 AppendEntries RPC。但选举失败时的重试会增加消息总数。
五、性能对比与实测数据
5.1 吞吐量对比
在典型的 5 节点集群中：
| 指标 | Multi-Paxos | Raft |
|---|---|---|
| 单条日志写入延迟 | ~1 RTT | ~1 RTT |
| 稳定状态吞吐量 | 极高（优化后） | 高 |
| 选举恢复延迟 | 取决于实现 | ~100ms（随机超时） |
| 日志复制开销 | 较低 | 较高（包含额外元数据） |
5.2 磁盘写入分析
Raft 的 AppendEntries RPC 需要携带：Term、Leader ID、前一条日志的索引和 Term、待复制条目列表、Leader 的 commitIndex。
Paxos 的 Accept 消息只需要携带：提案编号、提案值。从网络传输角度来看，Raft 的每条消息可能略大（因为需要携带日志相关的元数据），但大多数场景下差异不大。
5.3 实现复杂度量化
根据 GitHub 上的多个开源实现统计：
- etcd（Raft 实现）：约 15,000 行 Go 代码（核心共识部分约 5,000 行）
- Paxos 实现（各种变体）：通常 3,000~10,000 行不等
有趣的是，虽然 Paxos 的代码量有时更小，但读懂 Paxos 实现并保证其正确性的难度远高于 Raft。
六、工程实践深入
6.1 Multi-Paxos 的工程现实
在实际的工程应用中，几乎没有系统使用 Basic Paxos 来逐条复制日志。大多数 Paxos 系统使用 Multi-Paxos，它在 Basic Paxos 的基础上：
- 选举一个稳定的 Proposer 作为 Leader
- 跳过正常情况下的 Prepare 阶段（因为 Leader 信息已知）
- 直接在 Accept 阶段追加日志
Multi-Paxos 的工程细节（如 Leader 选举、成员变更、日志截断、快照机制）并没有标准化，每个实现都有所不同。Google 的 Chubby、Spanner，以及微信的 PaxosStore 等都是基于 Paxos 自主演进的系统。
6.2 Raft 的工程优势
Raft 的工程优势恰恰在于它的完整性和精确性。论文中详细规定了：
- 消息的完整数据结构和语义
- 各种边界条件下的行为（如 Leader 崩溃、网络分区、日志冲突等）
- 持久化状态的精确要求
- 快照机制的设计
这意味着，按照 Raft 论文可以实现一个"正确"的共识系统，而 Paxos 论文虽然正确，但要将它转化为一个可直接使用的系统则需要大量的工程判断和经验。
6.3 适用场景分析
Paxos/Multi-Paxos 更适合： - 已经有大量 Paxos 部署经验的团队 - 需要极致性能优化的场景（Google 级别的规模） - 已有成熟的 Paxos 代码库和工具链 - 变体丰富的场景（如 Fast Paxos、Cheap Paxos、EPaxos）
Raft 更适合： - 需要快速交付的新项目 - 团队对共识算法经验有限 - 需要多国开发者协作的系统（可理解性更重要） - 需要内置成员变更的场景 - 已有 Raft 生态工具（如 etcd、Consul、TiKV）
七、常见误区与最佳实践
7.1 误区一："如果某个值被多数派接受，它就一定被提交了"
这不完全准确。在 Paxos 中，一个值被多数派 Accept 后，有可能因为 Proposer 崩溃而"丢失"的概念。但在 Raft 中，一旦日志条目被确认（committed），它就不会被覆盖（这是 Raft 论文中的核心安全性质）。
7.2 误区二："Raft 比 Paxos 慢"
在稳定状态下，两者性能非常接近。Raft 的强 Leader 模型实际上有助于减少消息冲突。选举阶段的开销在正常运行中只占极小比例。但在跨数据中心部署（高延迟）场景下，Paxos 的优化变体（如 EPaxos）可能更有优势。
7.3 误区三："Paxos 已经过时"
完全错误。Paxos 仍然是许多大规模分布式系统的核心算法。Google 的 Spanner、Chubby 使用 Paxos，国内许多大型互联网公司的核心存储系统也基于 Paxos。Paxos 的变体（如 EPaxos、WPaxos）在减少消息传递和应对广域网方面持续演进。
7.4 最佳实践
日志压缩：无论使用哪种算法，都必须实现日志压缩或快照机制，防止日志无限增长。
持久化：所有涉及已接受值的状态（Paxos 的 promised_n、accepted_v；Raft 的 currentTerm、votedFor、log[]）都必须持久化到磁盘。
监控告警：监控 Leader 选举频率、日志复制延迟、磁盘写入延迟等关键指标。
测试验证：共识算法的正确性极为重要，使用 Jepsen 等混沌工程工具进行充分测试。
八、总结
Paxos 和 Raft 都是解决分布式共识问题的正确算法。Paxos 是理论的先驱，优雅而简洁，但难以理解和正确实现；Raft 是工程的典范，完整而详尽，几乎可以直接翻译为生产级代码。
选择哪种算法取决于团队的技术背景、性能需求和工程哲学。对于大多数现代分布式系统，Raft 是更推荐的选择——不是因为 Paxos 不够好，而是因为让多个工程师同时理解、调试和演进 Paxos 系统所需要付出的工程成本远远高于 Raft。
正如 Raft 论文标题所言：In Search of an Understandable Consensus Algorithm。在工程实践中，可理解性本身就是一种极其重要的性能。
参考资料
- Lamport, L. (1998). The Part-Time Parliament. ACM Transactions on Computer Systems.
- Lamport, L. (2001). Paxos Made Simple. ACM SIGACT News.
- Ongaro, D., & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm. USENIX ATC.
- Chandra, T., Griesemer, R., & Redstone, J. (2007). Paxos Made Live: An Engineering Perspective. PODC.
- Howard, H., Malkhi, D., & Spiegelman, A. (2016). Flexible Paxos: Quorum Intersection Reconsidered. OPODIS.
- etcd Raft 实现: https://github.com/etcd-io/etcd
发表评论 取消回复