分布式共识算法的工程演进：从 Multi-Paxos 到 Raft 到 EPaxos

引言

共识问题是分布式系统的基座。当多个节点就某个值达成一致时，我们才能构建可靠的状态机复制、配置管理和 Leader 选举。然而，半个世纪以来，从 FLP 不可能定理到 Paxos 的晦涩难懂，再到 Raft 的教育革命，共识算法的工程落地始终在理论优雅与实现复杂度之间反复拉锯。本文梳理这条演进路径，并分析现代生产系统中的实践选择。

1. FLP 不可能定理：理论的地板

Fischer-Lynch-Paterson 在 1985 年证明了一个悲观结论：在异步网络模型中，即使只有一个进程可能崩溃，也不存在确定性算法能保证共识。这意味着任何实用共识算法都必须放松三个条件之一：

• 放弃异步假设：引入部分同步超时（如 Raft 的 election timeout）
• 放弃确定性：采用随机化算法（如 Ben-Or 协议）
• 放弃容错保证：依赖故障检测器（如 Omega 类检测器）

主流系统选择了第一条路——通过超时机制打破纯异步假设。

2. Paxos：优雅的诅咒

Leslie Lamport 在 1998 年发表的 The Part-Time Parliament 用一篇隐喻论文描述了 Paxos 协议。其核心分为三个阶段：Prepare/Promise、Accept/Accepted、Learn。

2.1 Basic Paxos 的困境

Basic Paxos 每次决策需要至少两轮 RPC，且多个 Proposer 并发时可能出现活锁。在生产环境中，Multi-Paxos 通过选举一个稳定的 Leader 来跳过 Prepare 阶段，将每轮决策压缩到一轮 Accept。但这引入了新的问题：

• Leader 选举本身就是另一个 Paxos 实例——鸡生蛋问题
• 日志空洞处理：Leader 必须填充前任留下的空洞条目
• 成员变更：Joint Consensus 的正确性证明极为微妙

2.2 工业实现的割裂

Google 的 Chubby 使用 Paxos，但其实现细节直到多年后才逐步公开。开源社区面临"Paxos 有 1000 种实现，每种都声称正确"的困境。Lamport 后来发表的 Paxos Made Simple 并未真正简化实现。

3. Raft：可理解性优先

2014 年，Ongaro 和 Ousterhout 提出 Raft，明确将"可理解性"作为核心设计目标。

3.1 核心机制

Raft 将共识问题分解为三个相对独立的子问题：

• Leader 选举：随机超时 + Term 机制，Follower 超时后成为 Candidate，获得多数票后成为 Leader
• 日志复制：Leader 并行发送 AppendEntries RPC，收到多数确认后提交并应用到状态机
• 安全性：Election Restriction 确保当选 Leader 包含所有已提交条目；Log Matching Property 保证一致性

3.2 工程优势

Raft 的工程友好性体现在：

• 每个状态转换都有明确的触发条件和状态约束，可以逐条单元测试
• Snapshotting 和 Log Compactor 天然集成，无需额外协议
• Joint Consensus 替换为 Joint Configuration 的单阶段成员变更

3.3 性能局限

Raft 的 Leader 串行处理所有客户端请求，存在单点瓶颈。写密集型负载下，Leader 成为吞吐天花板。Pre-Vote 和 CheckQuorum 扩展缓解了扰动问题，但未根本改变串行模型。

4. EPaxos 与无领导者范式

2013 年，SOSP 发表的 EPaxos（Egalitarian Paxos）打破了领导者假设。核心洞察：在 Paxos/Raft 中，Leader 只是优化而非必需。

4.1 排序依赖图

EPaxos 通过跟踪命令间的依赖关系实现无领导并发执行。如果两个命令不互相影响（如对不同 key 的写），则可以并行提交无需排序。排序依赖图（ordering dependency graph）在每个副本上独立构建，通过 Fast Quorum（N-F 个副本）加速无冲突场景。

4.2 慢路径 vs 快路径

• 快路径（无冲突）：Fast Quorum 中直接将命令附加到依赖图，广播 commit 消息
• 慢路径（冲突）：Leader 协调，执行经典 Paxos Accept 将命令与依赖集一起提交

EPaxos 的恢复成本也更低——任何副本都可以充当 Recoordinator，无需选举。

4.3 工程复杂性

EPaxos 的依赖图构建和冲突检测逻辑远比 Raft 的 AppendEntries 复杂。状态空间爆炸使得验证变得困难，这也是其生产级实现稀少的主要原因。

5. 现代生产系统实践

5.1 ZooKeeper / etcd

两者都基于 ZAB 和 Raft 的变体。etcd 的 Raft 实现（etcd/raft）是工业级 Raft 的标杆：Pre-Vote、CheckQuorum、Lease Read、Pipeline 复制、Batching 全部支持。

5.2 CockroachDB

使用 Raft 复制的 Range（64MB 分片）。通过 Multi-Raft —— 每个 Range 独立运行 Raft 实例 —— 解决了单 Raft Group 的扩展瓶颈。

5.3 TiKV / TiDB

基于 Raft 的 KV 引擎，Region（96MB 而非 64MB，因为 SSD 随机读性能更好）。引入 Raft Store 的异步 Apply 和 SIMD 加速的日志编码。

5.4 ScyllaDB 的 Raft (Alternator)

在 CQL 之上提供 DynamoDB 兼容 API 时使用 Raft 保证 Schema 一致性。通过 Shared-Nothing 架构 + Raft 实现轻量级事务。

6. 性能基准对比

在 3 节点 AWS c5.2xlarge 上的典型吞吐：

• Raft (单 Leader) ~20K writes/s，平均延迟 ~3ms（同机房）
• EPaxos (无 Leader) ~35K writes/s，平均延迟 ~2ms（同机房，冲突率 <10%）
• Raft + Pre-Vote + Pipeline ~30K writes/s
• Multi-Raft (CockroachDB 16 Range) ~80K writes/s（线性扩展至节点数上限）

7. 选择指南

8. 总结

共识算法的演进史是一条"可理解性"与"性能"之间的拉锯战线。Raft 通过将复杂问题分解为可独立验证的子步骤，大幅降低了工程门槛；EPaxos 通过消除领导者瓶颈打开了写并发的上限但牺牲了可验证性。在实际工程中，算法选择取决于团队的综合能力——一个你能完全理解并可靠运维的次优算法，往往优于一个你无法正确实现的"最优"算法。