深度解读：Raft 是 Paxos 的一个变种么？

Paxos 算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。Google 在自家的数据存储例如 Spanner、Chubby 中都广泛使用了 Paxos 作为一致性协议，Oracle 的 MySQL Group Replication（MGR），Aurora、Neon 也宣称实现了某种形式的 Paxos 算法。而 Meta 却未选择 Paxos，花了大力气给 MySQL 插上了 Raft 的翅膀，大洋另一端的阿里云的 PolarDB 的底层存储采用的也是 Parallel Raft。那么 Raft 和 Paxos 到底有什么共同点，区别又在哪里呢？

本期小猿姐有请深耕数据库领域十余年的超级资深专家，云猿生数据创始人 &CEO，前阿里云数据库总经理，曹伟（鸣嵩），带来 Raft 和 Paxos 的技术解读。曹伟也是 PolarDB 数据库的创始人，他在 2018 年的 VLDB 会议上发表的论文《PolarFS: An Ultra-low Latency and Failure Resilient Distributed File System for Shared Storage Cloud Database》中提出了 Parallel Raft——一个 Raft 的变种协议，这是 PolarDB 底层存储采用的一致性协议。

TL;DR

先讲结论，从当前学术界和工业界普遍的认识而言，Raft 并不被认为是 Paxos 的一个变种，而是两个不同的一致性协议。Raft 和 Paxos 很相似，但存在一些差异。从根本上来说，Raft 是一种自上而下设计的强 Leader 协议，而 Paxos 是自下而上设计的弱 Leader 协议。本文列举了 Raft 和 Paxos 的四点具体的区别。

背景

Paxos 是 Lamport 在《The Part-Time Parliament》（兼职议会）论文中通过一个晦涩难懂的隐喻描绘的共识算法，Lamport 回忆说：“我受到拜占庭将军问题成功科普了共识问题的启发，决定根据古希腊岛屿上的议会来描述该算法。写一个失落的文明使我能够避免无趣的细节，并通过说议会协议的一些细节已经丢失来表示概括。为了进一步形象地展示，我以印第安纳·琼斯风格的考古学家的角色，戴着牛仔帽，拿着酒壶进行了几次演讲。我试图在这个主题中加入一些幽默，但以惨败告终。听过我演讲的人记得印第安纳·琼斯，但不记得算法。阅读这篇论文的人显然被希腊寓言分散了注意力，以至于他们不理解算法。” 不管怎么样，我觉得 Lamport 已经达到了目的，因为如同 CS 本科课程都会学“拜占庭将军”问题一样，Paxos 协议非常的有名，已经成为了“分布式一致性”的代名词。 Google 的 Chubby、Spanner，Oracle 的 MySQL Group Replication（MGR），国内的 OceanBase 都宣称实现了某种形式的 Paxos 算法。

而 Raft 是在一篇名为《In Search of an Understandable Consensus Algorithm》（寻找可理解的共识算法）的论文中提出的，论文安排了一个实验，”为了衡量 Raft 相对于 Paxos 的可理解性，我们对斯坦福大学《高级操作系统课程》和加州大学伯克利分校《分布式计算课程》的高年级本科生和研究生进行了实验研究。我们录制了一段关于 Raft 和一段 Paxos 的视频课程，并创建了相应的测验……我们比较了参与者在每个测验的得分，来看参与者是否对 Raft 表现出更好的理解。“ 作者衡量了学生学习算法和回答问题的能力，发现 Raft 确实比 Paxos 更容易理解。因为易于理解，并且有很多开源 Raft 实现可以参考，越来越多的工业系统采用 Raft 一致性算法，包括 K8s 的“海马体” etcd，TiDB 和 CockroachDB 等 NewSQL，前不久 Meta 官宣的 MySQL Raft。

Lamport 的论文《The Part-Time Parliament》和《Paxos Made Simple》里描述的 Paxos 算法其实是完成单个决策的一致性协议，它允许一组计算机就单个值（例如一个分布式寄存器）的决定（一次赋值操作）达成共识。而在实际系统中，真正有用的是 Multi-Paxos，Multi-Paxos 允许就一系列决策达成一致：组中的所有计算机将一组操作以相同的顺序应用于各自的状态机，从而最终到达相同的状态，即 Replicated State Machines 模型。其他的一致性协议，例如本文的另一个主角 Raft、和 Paxos 同期诞生的 Viewstamped Replication、Zookeeper 的 ZAB 也都是对 Replicated State Machines 的实现。

Muti-Paxos 是从单决策 Paxos 演进而来的。你可以想像一个 Muti-Paxos 是由很多个单决策 Paxos 拼装起来得到的，（当然为了性能，这里要做优化，比如说，单决策 Paxos 是个由 Prepare 和 Accept 操作组成的两阶段过程，Multi-Paxos 会把一组单决策 Paxos 的 Prepare 操作都重合起来只做一次，然后并发的去执行它们的 Accept 操作）。因为先有单阶段 Paxos，再由此推导出 Multi-Paxos，因此我们说 Multi-Paxos 是自下而上（bottom-up）设计的。而 Raft 算法为了设计出易于理解的算法，采用了问题分解和简化状态空间的方法。问题分解体现在它将 Leader 选举、日志复制和成员变更拆解成子问题，分而治之。为了简化状态空间，Raft 增加了更多约束，例如不允许日志出现空洞、限制了日志之间可能变得不一致的方式等，这样得到的系统会更易于推理和校验。因此 Raft 是自上而下（top-down）设计的。

由此可以看到，Multi-Paxos 更复杂，也有更高的灵活性。因此市面上存在很多 Multi-Paxos 变种，本文仅讨论基于 Leader 的 Multi-Paxos（下文的 Paxos 都是指基于 Leader 的 Multi-Paxos）。还有其他类型的 Multi-Paxos 算法，例如没有 Leader 的 EPaxos，多 Leader 的 Mencius。在下文中可以看到，基于 Leader 的 Multi-Paxos 与 Raft 算法在结构上很相似，会令人误以为两者是一类算法，或者说 Raft 算法是 Paxos 的变种。其实不然，本文分析了这两者的四个显著区别。

共同点

出于简单，我们先看下朴素的 Paxos 和 Raft 算法（就是一个正确的、没有打各种优化补丁而变得更复杂的版本），它们都是通过 Replicated log 来实现。

从 High-level 的视角看，基于 Leader 的 Multi-Paxos 与 Raft 算法都具有这样的结构：

• 有 n 台服务器，其中的一个是 Leader，其余人是 Follower。所有客户端的写请求都发送给 leader，由 leader 记录到 log 里，再将 log entry 发送给所有 Follower。

• 一旦 Leader 收到来自多数派服务器的确认，该 log entry 被“提交”，所有成员最终将 log entry 应用于他们的状态机。

• 如果 Leader 失败，则多数派会选出新的 Leader。

任何时候服务器都可能处于以下三种状态之一：

• Leader，负责使用 AppendEntries RPC 将写请求添加到 replicated log 中。

• Follower，回应 Leader 发送的 AppendEntries RPC。

• Candidate，Candidate 会试图使用 RequestVotes RPC 成为 Leader。

服务器最初都是 Candidate 状态，它们会尝试互相发送 RequestVote RPC 当选 Leader。有一台 Candidate 会成为 Leader，其他服务器会成为 Follower。当 Follower 认为 Leader 失败，又会成为 Candidate 进行选举。Leader 节点必须定期发送 AppendEntries RPC 作为 keepalive，以防止 Follower 超时成为 Candidate。

服务器都会存储一个递增的数字叫做 Term（任期号），每条 RPC 消息都会包含 Term。当服务器接收到 RPC 时，它会检查 RPC 里包含的 Term 与自身 Term 的大小：

• 如果发送者的 Term 大于自身的 Term，服务器会更新 Term，如果服务器是 Candiate 或者 Leader，会变成 Follower。

• 如果发送者的 Term 等于自己的 Term，则正常工作。

• 如果发送者的 Term 小于自身的 Term，则服务器会应答一条拒绝的 RPC 响应消息。发送者收到该响应时，会降级为 Follower，并更新自身的 Term。

可以证明，Paxos 和 Raft 都满足如下特性：如果 Term=t 的 Leader 在日志的某个位置（比如 index=i）处提交了一个 entry e，那么 Term > t 的所有 Leader 也将在日志文件的 index=i 处拥有内容完全相同的 entry e。这也意味着在复制状态机里，假如某个服务器将一条日志应用到了状态机上，则所有服务器都将相同的日志应用到状态机上。

差异点

为了让算法易懂，Raft 增加了一些约束，例如只允许日志从 Leader 流向其他服务器，当 Follower 数据与 Leader 不一致时，Leader 会强制 Follower 的日志复制自己的日志，用 Leader 的日志条目来覆盖 Follower 日志中的冲突条目。这使得 Raft 成为一个强 Leader 的算法。

Leader 选举

Paxos 允许任何服务器成为 Leader，然后再从其他服务器补齐缺少的日志，而 Raft 只允许拥有最新日志的服务器成为 Leader。

Paxos 的 Candidate 在选举时，会根据服务器 ID 生成一个比已知的 term 更大的 term 来发送 RequestVotes RPC，不同 Candidate 生成的 term 不会冲突。当多个 Candidate 同时竞选时，总是由 term 更大的服务器获胜。因此 Paxos 选出一个新 Leader 是很快的。但这样新 Leader 可能会缺少一些日志条目，或者有一些日志条目与其他更新的节点有冲突，不能立即开始服务，必须首先通过从其他节点上复制缺失的、或者更新的日志条目来完成同步。而这个补日志的时间可能很花时间。

在 Raft 中，一个新的 Leader 节点必须是一个具有最长日志的副本。因为不需要从其他节点学习日志，选出的 Leader 可以立刻开始工作。但 Raft 选举有一个缺点：如果几个日志版本相同的服务器运行，它们可能都获得少数选票，必须等待一个随机时间然后重试直到有一个服务器获得多数派的投票。

Leader 是否会修改日志的 term

在 Raft 中，日志条目的 term 不会被未来的 leader 所修改。而在 Paxos 协议下，这是可能的。

在 Raft 中，新的 Leader 选举出来后，对待上一个 term 未提交的日志条目，会继续沿用原有的 term，复制到其他节点。事实上，Raft Leader 甚至永远不会覆盖或删除其日志中的条目，只会追加写新条目。

而在 Paxos 里，新的 Leader 选举出来后，会用新的 term 来覆盖所有未提交的日志条目。例如在下图里，s1, s2, s3 是三台运行 paxos 的服务器，图 a 是选举前的状态，图 b 是选举后的状态，s3 在 s1 或者 s2 投票后成为 term=6 的 Leader，s3 会用新的 term 覆盖三条本地未提交的日志条目 B、D、E。接下来，再将日志复制到其他节点，这可能造成 s2 上的已提交的日志条目 B 的 term 从 2 被修改为 6。这增加了理解系统行为的难度。

日志的连续性

Raft 的日志是严格顺序写入的，而 Paxos 通常允许无序写入，但需要额外的协议来填充可能因此发生的日志间隙。

Raft 算法在处理和复制日志条目时遵循了严格的顺序规则。在 Raft 算法中，每当有一个新的操作请求到达 Leader 节点时，Leader 会将该请求作为一个新的日志条目添加到其日志末尾。这样确保了日志条目按照它们被接收的顺序进行存储。Leader 节点负责将其日志中的条目复制到其他 Follower 节点。在复制过程中，Leader 会按照日志中的顺序将条目发送给 Follower。Follower 节点收到条目后，会将其添加到本地日志的末尾，保持与 Leader 相同的顺序。

相比之下，Paxos 算法在处理和复制日志条目时更加灵活。在 Paxos 算法中，日志条目可以独立地达成共识。这意味着，不同的日志条目可以在不同的时间点或顺序上达成共识，从而导致日志中的空隙。同样在复制过程中不要求日志条目严格按照顺序发送。这需要引入额外的机制来填补空隙，以确保日志的一致性。例如，假设日志中存在条目 1 和条目 3，但缺少条目 2。那么 Paxos 需要一种方法来确定条目 2 的内容，以便节点可以将日志修复至一致的状态。

无序写入的优势是可以实现更高的并发性和性能。但是,这需要付出额外的复杂性代价来处理日志的不一致情况。相反，Raft 的严格顺序写入降低了这种复杂性，代价是牺牲一定的并发性。

日志条目提交的条件

在 Raft 协议里，即使日志条目被多数派的节点所接受（但未提交），也有可能被回滚掉。Raft 原始论文里的图 8 展示了这一情况，只有新选举出来的 Leader 将当前 term 的第一个日志条目写到多数派服务器上，上一个 term 的日志条目才可以安全提交。

可以看到在(c)中，日志条目 2（值为 2）已经存储到 s1,s2,s3 组成的多数派节点中。但此时 s1 崩溃，s5 当选为新 leader 后，s5 在(d)还是可以用另一个值 3 来覆盖日志条目 2，因此在(c)中就认为日志条目 2 已提交是不安全的。但如果 s1 在崩溃前，将新 term 的一个条目（值为 4）复制到 s2,s3，如(e)所示，那么日志条目 2 就可以安全提交了。

而在 Paxos 系统里，只要日志条目被复制到了多数派服务器上，Paxos 就可以安全地提交日志条目。

篇幅关系，本期咱们先讲到这里，请大家期待下一期技术解读吧。

Reference

• Howard H, Mortier R. Paxos vs Raft: Have we reached consensus on distributed consensus?

• Paper review Paxos vs Raft. https://emptysqua.re/blog/paxos-vs-raft/
  

• Reading Group. Paxos vs Raft Have we reached consensus on distributed consensus, Aleksey Charapko. http://charap.co/reading-group-paxos-vs-raft-have-we-reached-consensus-on-distributed-consensus/
  

• Why does Neon use Paxos instead of Raft, and what's the difference. https://neon.tech/blog/paxos
  

• D. Ongaro, AND J. K. Ousterhout In search of an understandable consensus algorithm.

• W. Zhaoguo, Z. Changgeng, M. Shuai, C. Haibo, AND L. Jinyang On the parallels between Paxos and Raft, and how to port optimizations.