1 导言

一致性算法允许一组 Server 像一个整体一样工作，该整体能够使它的成员从失败中恢复正常。正因为此，它们在构建可靠的大规模软件系统过程中起着关键作用。过去十多年来，Paxos [15, 16] 在有关一致性算法的讨论中处于主导地位：大多数一致性算法的实现都基于 Paxos 或者受它影响，并且 Paxos 也成为有关一致性知识教学的主要工具。

不幸的是，Paxos 非常难于理解，尽管在试图使其更容易上手方面做了大量尝试。而且 Paxos 的架构需要经过复杂的修改才能用于实际的系统。结果，无论是系统构建者还是学生，都饱受折磨。

我们在经受 Paxos 折磨之后，便开始着手寻找一种新的一致性算法，希望它能为系统构建和教学奠定更好的基础。我们的做法不同于以往，因为首要的目标就是可理解性：是否我们能够定义一种一致性算法，对于实际系统实现，以及用一种比 Paxos 更容易学习的方式来描述它？并且，我们希望这种算法能够使开发变得更加容易，这对系统构建者从直觉上来理解是非常关键的。重要的是不仅仅是算法能够运行，而且还要使它的运行原理更易于理解。

我们工作的结果是找到了一种新的一致性算法，叫做 Raft。在设计 Raft 时我们使用了特殊的技巧来提高可理解性，包括分解（Raft 分解为Leader 选举、日志复制与安全）和削减状态（相对于 Paxos，Raft 降低了不确定性和 Server 之间互相不一致的方式）。在一个包含两所大学的43个学生的调研中发现，Raft 比 Paxos 更加容易理解：在学习了两种算法之后，其中33个学生解答 Raft 的问题要比 Paxos 好很多。

Raft 算法和现存的一致性算法在很多地方都类似（主要是 Oki 和 Liskov 的 ViewstampedReplication [29, 22]，但 Raft 具有如下几个新特性：

• 强 Leader（Strong Leader）：相比于其它算法，Raft 使用了更强的 Leader 形式。比如，日志条目只从 Leader 发送到其他 Server。这样简化了对日志复制的管理，并使得 Raft 更易于理解。
• Leader 选举（Leader Selection）：Raft 使用随机定时器来选举 Leader。这种方式只是对心跳机制增加了少量改动，而心跳对所有一致性算法来说都是必需的，但却能够更加简单、快速地解决冲突。
• 成员变更（Membership Change）：Raft 使用了一种新的称为联合共识（Joint Consensus）的方式，来处理集群中一组 Server 的成员变更问题，这种方法会在成员关系转换过程中，两个不同配置对应的大多数 Server 是重叠的（Overlap）。这允许在配置变更过程中，集群仍然能够继续正常运行。

我们认为，在达成教学目标和为实现算法提供基础这两个方面，Raft 要优于 Paxos 及其它算法。Raft 比其他算法更简单，并且更易于理解；Raft 具有更加完整的描述，能够满足构建一个实际系统的需要；Raft 拥有许多开源实现，并且被许多公司所采用；Raft 的安全性已经被正式提出和证明；同时， Raft 在效率方面也可以与其他算法相媲美。

这篇论文的剩余部分会介绍复制状态机（Replicated State Machine）问题（第2部分），讨论 Paxos 的优缺点（第3部分），描述我们在提高可理解性上采取的通用方法（第4部分），陈述 Raft 一致性算法（第5-8部分），给出对 Raft 算法的评估（第9部分），最后讨论了相关工作（第10部分）。