Paxos vs. Raft：我们对共识算法达成共识了吗？

以下内容来源于《深入理解分布式系统》一书，作者唐伟志（“多颗糖”）曾在网易、腾讯从事基础架构相关工作，本书深入浅出分析了各类共识算法，以及其它分布式系统相关知识点。

自 Raft 算法诞生并在许多分布式系统中取得成功后，越来越多的人好奇 Paxos 和 Raft 的差别到底是什么？作为一个架构师或开发者，应该选择 Paxos 算法还是 Raft 算法？

Paxos 几乎是分布式共识算法的代名词，但 Raft 正在以迅猛的速度追赶，尤其是，最近越来越多的系统选择基于 Raft 来构建。

2020 年剑桥博士 Heidi Howard 和 Richard Mortier 发表论文对比了 Paxos 和 Raft[1]，他们试图比较哪个是更好的共识算法。然而，他们发现，Paxos(主要是 Multi-Paxos) 其实和 Raft 非常相似，他们的共同点包括：

• 从所有节点中选出一个领导者，它接受所有的写操作，并将日志发送给跟随者；

• 多数派复制了日志后，该日志提交，所有成员最终将该日志中的命令应用于他们的状态机；

• 如果领导者失败了，多数派会选出一个新的领导者；

• 两者都满足状态机安全性和领导完整性。状态机安全性指，如果一个节点上的状态机应用了某个索引上的日志，那么其他节点永远不会在同一个索引应用一个不同的日志。领导完整性指，如果一个命令 c 在任期 t 和索引 i 处被领导者提交，那么任期大于 t 的任何领导者在索引 i 处存储同样的命令 c。

Heidi Howard 和 Richard Mortier 也对比了两者的不同点，得出 Raft 相对于 Paxos 的好处在于三点：表现形式(Presentation)、简单性(Simplicity)和高效的领导者选举算法。

首先是表现形式，Leslie Lamport 讲了一个关于 Paxos 的晦涩难懂的故事，他把具体的算法内容隐藏得太深了。对比 Raft 论文，作者在论文中直截了当地表明了，Raft 论文的主要目标是可理解性，尝试寻找一种比 Paxos 更容易学习和理解的方式来描述算法，同时希望算法对于实际系统建设者来说是实用的。Raft 还给出了代码实现的相关逻辑。所以，Raft 的表现形式是更为友好的。

第二点是简单性。如果深入挖掘 Paxos 到底比 Raft 复杂在哪里，Heidi Howard 和 Richard Mortier 发现在两个方面体现了 Paxos 的复杂性。第一，Raft 按顺序提交日志，而 Paxos 允许日志不按顺序提交，但需要一个额外的协议来填补可能因此而出现的日志空洞。第二，Raft 中的所有日志的副本都有相同的索引、任期和命令，而 Paxos 中这些任期可能有所不同。

第三点是 Raft 具备了一个高效的领导者选举算法。Paxos 论文中给出的选举算法是通过比较服务器 id 的大小，几个节点同时竞选时，服务器 id 较大的节点胜出。问题是，这样选出的领导者如果缺少一些日志，它不能立即执行写操作，必须首先从别的节点那里复制一些日志。Raft 日志总能选出拥有多数派日志的节点，从而不需要追赶日志，虽然有时候选举会因为瓜分选票而重试，但总体来说是一个更有效率的选举算法。

对于 Paxos 算法，如果一个服务器非常落后，甚至落后了几天的日志，但却在某个时候选为了领导者，这将导致一定时间的阻塞。可在 Raft 算法中，永远不会选出日志落后的节点。

Heidi Howard 和 Richard Mortier 还得出一个结论，Raft 算法和 Paxos 算法其实非常相似，通常你选择哪个并不重要，适用于一个算法的优化几乎同样适用于另一个算法（Raft 算法本身就来自于一系列的 Paxos 协议族）。但是 Raft 的领导者选举算法是一个非常高效的算法。

上海交通大学并行与分布式系统研究所(IPADS)也发表关于 Paxos 和 Raft 的论文[2]并指出，近年来 Raft 已经逐渐超越了 Paxos，成为共识协议的首选（In recent years, Raft has surpassed Paxos to become the more popular consensus protocol in the industry. ）。

综上，于是我们看到了，现在的一些共识算法都从 Raft 开始，然后长得越来越像 Paxos 算法。

笔者认为，Paxos 最大的问题是他留给读者的恐惧，由于 Lamport 在论文中模糊地表述，无论之后再怎样重新解释，都无法克服这一印象。另外，Raft 除了领导者选举和日志复制，配置变更和领导者选举部分都非常清晰，具体到算法的实现细节，而 Paxos 算法有太多空白需要开发者去思考和推敲，以至于实现出来的 Paxos 各有不同，亚马逊的 Michael Deardeuff 发现，Github 上许多 Paxos 的实现都有问题。对于一个基础架构依赖库来说这是致命的，意味着你很难找到一个优秀的参考者，你可能需要一遍遍去踩坑。而 Raft 算法在 etcd 等系统中的成功实现，给了开发者足够的信心，大家开始模仿 etcd 并进行一定的优化。笔者认为，在 Paxos 算法找到一个开源的“杀手级”工业应用之前，Raft 算法的赶超速度几乎是不可阻挡的。Paxos 协议族会逐步成为 Raft 算法的优化策略（我们看到 FPaxos 之类的协议已经被用到 Raft 算法中了）。

[1]: Heidi Howard and Richard Mortier. “Paxos vs Raft: Have We Reached Consensus on Distributed Consensus?” In: Proceedings of the 7th Workshop on Principles and Practice of Consistency for Distributed Data(Apr. 2020), pp. 1–9. doi: 10 . 1145 / 3380787 . 3393681.

[2]: Zhaoguo Wang, Changgeng Zhao, Shuai Mu, Haibo Chen, and Jinyang Li. 2019. "On the Parallels between Paxos and Raft, and How to Port Optimizations." In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Toronto ON, Canada) (PODC '19). Association for Computing Machinery, New York, NY, USA, 445--454.