论文原文: https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf

摘要

Raft 是一种用于管理 复制日志 (replicated log) 的 共识算法 (consensus algorithm). 它产生一个等同于(多) paxos 的结果, 并且和 Paxos 一样高效, 但是结构与 Paxos 不同; 这使得 Raft 比 Paxos 更加易于理解, 也为构建实用系统提供了更好的基础. 为了增强可理解性, Raft 分离了共识的关键因素, 例如: 领导人选举, 日志复制和安全性, 并强制执行更强程度的一致性以减少必须考虑的状态数量。 用户研究的结果表明，Raft 比 Paxos 更容易让学生学习。 Raft 还包括一种用于更改集群成员的新机制，该机制使用重叠多数来保证安全。

1 引言

共识算法允许一组机器作为一个整体进行工作，可以在其某些成员的失败中幸存下来。 正因为如此，它们在构建可靠的大型软件系统方面发挥着关键作用。 Paxos ^{15 16} 在过去十年中主导了共识算法的讨论：大多数共识实现都基于 Paxos 或受其影响，Paxos 已成为用于教授学生共识的主要工具。

不幸的是，Paxos 很难理解，尽管人们多次尝试使其更易于理解。 此外，它的架构需要复杂的更改来支持实际系统。 结果，系统构建者和学生都在为 Paxos 苦苦挣扎。

在自己与 Paxos 苦苦挣扎之后，我们着手寻找一种新的共识算法，可以为系统构建和教育提供更好的基础。 我们的方法与众不同，因为我们的主要目标是可理解性：我们能否为实际系统定义一个共识算法，并以一种比 Paxos 更容易学习的方式来描述它？ 此外, 我们希望算法更加的直观。 重要的不仅仅是算法能够工作，而且为什么有效非常明显.

这项工作的结果是一种称为 Raft 的共识算法。 在设计 Raft 时，我们应用了特定的技术来提高可理解性，包括分解（Raft 分离领导者选举、日志复制和安全性）和状态空间缩减（相对于 Paxos，Raft 降低了不确定性的程度以及服务器之间可能不一致的方式 )。 一项针对两所大学 43 名学生的用户研究表明，Raft 比 Paxos 更容易理解：在学习了这两种算法之后，其中 33 名学生能够更好地回答有关 Raft 的问题，而不是有关 Paxos 的问题。

Raft 在很多方面都与现有的共识算法相似（最值得注意的是，Oki 和 Liskov’s Viewstamped Replication ²⁹, ²²），但它有几个新颖的特性：

• 强大的领导者：Raft 使用比其他共识算法更强大的领导形式。 例如，日志条目仅从领导者流向其他服务器。 这简化了对复制日志的管理，并使 Raft 更易于理解。
• 领导者选举：Raft 使用随机计时器来选举领导者。 这只会为任何共识算法已经需要的心跳添加少量机制，同时简单快速地解决冲突
• 成员更改：Raft 更改集群中服务器集的机制使用一种新的联合共识方法，其中两种不同配置的大多数在转换期间重叠。 这允许集群在配置更改期间继续正常运行。

我们认为 Raft 优于 Paxos 和其他共识算法，无论是出于教育目的还是作为实现的基础。 比其他算法更简单易懂； 描述得足够完整，可以满足实际系统的需要； 它有几个开源实现，并被多家公司使用； 其安全特性已得到正式规定和证明； 其效率与其他算法相当。

论文的其余部分介绍了复制状态机问题（第 2 节），讨论了 Paxos 的优缺点（第 3 节），描述了我们对可理解性的一般方法（第 4 节），介绍了 Raft 共识算法（第 5-8 节） ，评估 Raft（第 9 节），并讨论相关工作（第 10 节）。

2 复制状态机

共识算法通常出现在复制状态机的上下文中³⁷。 在这种方法中，服务器集合上的状态机计算相同状态的相同副本，并且即使某些服务器关闭，也可以继续运行。 复制状态机用于解决分布式系统中的各种容错问题。 例如，具有单个集群领导者的大型系统，如 GFS ⁸、HDFS ³⁸ 和 RAMCloud ³³，通常使用单独的复制状态机来管理领导者选举并存储必须生存的配置信息 领导崩溃。 复制状态机的示例包括 Chubby ² 和 ZooKeeper ¹¹。

复制状态机通常使用复制日志来实现，如图 1 所示。每个服务器存储一个包含一系列命令的日志，其状态机按顺序执行这些命令。 每个日志包含相同顺序的相同命令，因此每个状态机处理相同的命令序列。 由于状态机是确定性的，每个状态机计算相同的状态和相同的输出序列

保持复制日志的一致性是共识算法的工作。 服务器上的共识模块接收来自客户端的命令并将它们添加到其日志中。 它与其他服务器上的共识模块进行通信，以确保每个日志最终以相同的顺序包含相同的请求，即使某些服务器出现故障。 一旦命令被正确复制，每个服务器的状态机都会按日志顺序处理它们，并将输出返回给客户端。 结果，服务器似乎形成了一个单一的、高度可靠的状态机。

实际系统的共识算法通常具有以下属性:

• 它们确保在所有非拜占庭条件下的安全性（永远不会返回错误的结果），包括网络延迟、分区和数据包丢失、重复和重新排序
• 只要大多数服务器都在运行中且他们之间可以相互通信, 且客户端能与之连接，它们就可以完全正常工作（可用）。 因此，一个典型的五台服务器集群可以容忍任何两台服务器的故障。 假设服务器因停止而失败； 它们稍后可能会从稳定存储上的状态恢复并重新加入集群
• 它们不依赖时间来确保日志的一致性：错误的时钟和极端的消息延迟在最坏的情况下会导致可用性问题
• 在常见的情况下，只要集群的大部分响应了一轮远程过程调用，命令就可以完成。 少数慢速服务器不需要影响整体系统性能。

3 Paxos 有哪些问题?

在过去的十年中, Leslie Lamport 的 Paxos 协议 ¹⁵ 几乎成为共识的同义词：它是课程中最常教授的协议，大多数共识的实现都以它为起点。 Paxos 首先定义了一种能够就单个决策达成一致的协议，例如单个复制的日志条目。 我们将此子集称为“single-decree” Paxos 。 然后 Paxos 结合了该协议的多个实例，以促进一系列决策，例如日志（multi-Paxos）。 Paxos 保证了安全性和活跃性，并且它支持集群成员的变化。 它的正确性已经被证明，并且在正常情况下是有效的。

不幸的是，Paxos 有两个明显的缺点。 第一个缺点是 Paxos 非常难以理解。 完整的解释 [15] 是出了名的不透明。 很少有人能成功理解它，而且只有付出巨大的努力。 因此，已经有几次尝试用更简单的术语来解释 Paxos [16,20,21]。 这些解释集中在single-decree子集上，但它们仍然具有挑战性。 在 NSDI 2012 对与会者的非正式调查中，我们发现很少有人对 Paxos 感到满意，即使是经验丰富的研究人员也是如此。 我们自己在 Paxos 上苦苦挣扎； 直到阅读了几个简化的解释并设计了我们自己的替代协议之后，我们才能够理解完整的协议，这个过程花了将近一年的时间。

我们假设 Paxos 的复杂性源于它选择single-decree子集作为其基础。 single-decree Paxos 混沌而又深奥：分为两个阶段，没有简单直观的解释，无法独立理解。 正因为如此，很难对 single-decree 协议的工作原理产生直观感受。 multi-Paxos 的组合规则显着增加了复杂性和深度。 我们相信，就多个决策（即日志替代单个条目）达成共识的整体问题可以用其他更直接和明显的方式分解。

Paxos 的第二个问题是它没有为构建实际实现提供良好的基础。 原因之一是没有广泛认可的多 Paxos 算法。 Lamport 的描述主要是关于 single-decree Paxos； 他勾勒了多 Paxos 的可能方法，但缺少许多细节。 已经多次尝试充实和优化 Paxos，例如 ²⁶、³⁹ 和 ¹³，但它们彼此不同，也与 Lamport 的草图不同。 Chubby ⁴ 等系统已经实现了类似 Paxos 的算法，但在大多数情况下，它们的详细信息尚未公布。

此外，Paxos 架构对于构建实际系统来说是一种糟糕的架构。 这是 single-decree 分解的另一个结果。 例如，单独选择一组日志条目然后将它们融合到一个顺序日志中几乎没有什么好处； 这只会增加复杂性。 围绕日志设计一个系统更简单、更有效，其中新条目以受约束的顺序顺序附加。 另一个问题是 Paxos 在其核心使用了对称的点对点方法（尽管它最终暗示了一种弱领导形式作为性能优化）。 这在一个只会做出一个决定的简化世界中是有意义的，但很少有实际系统使用这种方法。 如果必须做出一系列决策，首先选举一个领导者，然后让领导者协调决策会更简单、更快捷。

因此，实际系统与 Paxos 几乎没有相似之处。 每个实现都从 Paxos 开始，发现实现它的困难，然后开发出截然不同的架构。 这是耗时且容易出错的，理解 Paxos 的困难加剧了这个问题。 Paxos 的公式对于证明其正确性的定理可能是一个很好的公式，但实际的实现与 Paxos 是如此不同，以至于证明几乎没有价值。 Chubby 实施者的以下评论很典型：

Paxos 算法的描述与现实世界系统的需求之间存在很大差距。 . . . 最终系统将基于未经证实的协议 ⁴。

由于这些问题，我们得出结论，Paxos 没有为系统构建或教育提供良好的基础。 鉴于共识在大型软件系统中的重要性，我们决定看看我们是否可以设计一种性能比 Paxos 更好的替代共识算法。 Raft 就是那个实验的结果。

4 以利于理解作为设计基础

我们在设计 Raft 时有几个目标：它必须为系统构建提供完整且实用的基础，从而显着减少开发人员所需的设计工作量； 它必须在所有条件下都是安全的，并且在严格的操作环境下可用； 并且对于常见的操作必须是高效的。 但我们最重要的目标——也是最困难的挑战——是可理解性。 大量受众必须能够轻松地理解算法。 此外，必须能让开发者对算法的实现有着直观的感受，以便系统构建者遇到需要修改的情况时可以做出扩展。

在 Raft 的设计中有很多点我们必须在替代方法中进行选择。 在这些情况下，我们根据可理解性评估备选方案：每个备选方案有多难解释（例如，它的状态空间有多复杂，是否有模糊不清的含义？），读者是否容易完全理解这种方案和含义？

我们认识到这种分析存在高度的主观性； 尽管如此，我们还是使用了两种普遍适用的技术。 第一种技术是众所周知的问题分解方法：只要可能，我们将问题分成可以相对独立地解决、解释和理解的独立部分。 例如，在 Raft 中，我们将领导者选举、日志复制、安全性和成员资格更改分开。

我们的第二种方法是通过减少要考虑的状态数量来简化状态，使系统更加连贯并尽可能消除不确定性。 具体来说，日志不允许有缺口，Raft 限制了日志相互不一致的方式。 尽管在大多数情况下我们试图消除不确定性，但在某些情况下，不确定性实际上提高了可理解性。 特别是，随机方法引入了非确定性，但它们倾向于通过以类似方式处理所有可能的选择来减少状态空间（”没关系的, 都一样”）。 我们使用随机化来简化 Raft 领导者选举算法。

5 Raft 一致性协议

Raft 是一种用于管理第 2 节中描述的形式的复制日志的算法。图 2 以精简形式总结了该算法以供参考，图 3 列出了该算法的关键属性； 这些图的元素将在本节的其余部分进行分段讨论。

Raft 通过首先选举一个杰出的领导者来实现共识，然后让领导者完全负责管理复制的日志。 领导者接受来自客户端的日志条目，将它们复制到其他服务器上，并告诉服务器何时可以安全地将日志条目应用于其状态机。 拥有领导者可以简化复制日志的管理。 例如，领导者可以在不咨询其他服务器的情况下决定在日志中放置新条目的位置，并且数据以简单的方式从领导者流向其他服务器。 领导者可能会失败或与其他服务器断开连接，在这种情况下会选出新的领导者。

考虑到领导者的作用，Raft 将共识问题分解为三个相对独立的子问题，这些子问题将在以下小节中讨论:

• 领导者选举：当现有领导者失败时必须选择新领导者（第 5.2 节）。
• 日志复制：领导者必须接受来自客户端的日志条目并在整个集群中复制它们，并强制其他节点与自己同步（第 5.3 节）。
• 安全性：Raft 的关键安全属性是图 3 中的状态机安全属性：如果任何服务器已将特定日志条目应用到其状态机，则没有其他服务器可以对同一日志索引应用不同的命令。 5.4 节描述了 Raft 如何确保这个属性； 该解决方案涉及对第 5.2 节中描述的选举机制的额外限制。

在介绍了共识算法之后，本节讨论了可用性问题和时间在系统中的作用。

5.1 Raft 基础

一个 Raft 集群包含多台服务器: 常常由5台组成，它允许集群中2台主机故障。 无论何时, 服务器都处在以下状态之一: 领导者、追随者或候选者. 在正常情况下，只有一个领导者，其余服务器都是追随者。 追随者是被动的：他们不会自己发出请求，而只是响应领导者和候选人的请求。 领导者处理所有客户端请求（如果客户端联系跟随者，则跟随者将其重定向到领导者）。 第三个状态，候选人，用于选举一个新的领导者，如第 5.2 节所述。 图 4 显示了状态及其转换； 等会将会讨论角色之间是如何转换

Raft 将时间划分成任意长度并称之为 Term, 入图5所示. Term 使用连续的数字编号. 每个 Term 都以启动领导的选举开始, 其中一个或多个候选人尝试成为第 5.2 节所述的领导者. 在某些情况下，选举会导致分裂投票, 这会导致任期在没有领导者的情况下结束. 一个新的任期和选举也会随之开始. Raft 确保在给定的任期内.最多有一个领导者.

不同的服务器会在不同的时间观察 term 的转换, 某些情况下甚至不会察觉到选举或者是整个 term. Term 就像在 Raft 中充当逻辑时钟¹⁴, 允许服务器查询过时的信息, 例如过时的领导者. 每个服务器将会存储当前 Term 的序列号, 该序列号随时间增长, 服务器之间会交换当前所在的 Term .如果服务器接收到当前的 Term 比已有的 Term 序列大, 那么将会当前 Trem 标识更新为更大值. 如果候选者或者领导人发现当前 Term 已过, 将会变成跟随者的状态. 如果服务器收到过期 Term 序列号时, 将会拒绝该请求.

Raft 服务使用远程过程调用(RPC)进行通信,基本的共识算法只需要两种类型的 RPC. RequestVote RPC 由候选人在选举期间进行发起(5.2节), 而AppendEntries RPC 由领导者发起, 用于日志的复制.并提供心跳的作用(5.3节). 第七节添加了第三个 RPC , 用于在服务器之间传输快照. 如果服务器没有及时收到响应, 则服务器将会重试 RPC , RPC 将会以并行的方式进行以获得最佳性能.

5.2 领导者选举

Raft 使用心跳机制来触发领导者选举. 当服务器启动时, 他们以追随者的身份开始. 只要从领导者或者候选人那里收到有效的RPC他们将会保持追随者的状态. 领导者定期向所有追随者发送心跳(使用AppendEntries RPC, 但是不携带日志), 以维护权威. 如果在选举超时时间内没有收到任何通信信息, 那么追随者就假定没有可追随的 leader 并开始着手进行选举产生新的领导者.

开始选举时, 追随者会增加当前任期序列号并将当前角色变更为候选者状态, 并为自己投票然后向集群中的其他服务器发出 RequestVote RPC. 候选者将会保持这种状态直到以下几种情况: a) 它赢得了这个选举 b) 其他服务器确立了自身leader的身份 c) 一段时间过去了, 没有任何人确认成为leader. 这些情况将在以下单独讨论

一个候选人能在选举中胜出的条件是在一个 term 中获得集群中大多数服务的投票. 每个服务器在一个 Term 最多投票给一个候选人, 先到先得(注意: 5.4节增加了投票的额外限制) 大多数原则确保了最多只有一名候选人可以获得特定 Term 的选举(图3 中的选举安全属性). 一旦候选人赢得选举, 它将成为 leader 然后将向其他服务器发送心跳消息建立权威, 并阻止新的选举.
// TODO 不确定是否有等于
等待投票期间, 候选人可能会收到另一个声称自己为领导者的服务器发送的 AppendEntries RPC. 如果收到的消息中包含的 Term 序列号大于等于当前候选人的 Term 序列号, 那么候选人将认定该服务器为领导者, 并修改自己的状态为追随者. 如果 RPC 中的 Term 序列号小于候选人的当前 Term 序列号, 则候选人拒绝 RPC 并继续处于候选人状态.

第三种情况可能是候选者在选举中既没有赢也没有输: 如果有过多的跟随者在此时变成了候选者, 选票将会分裂, 没有任何候选者获得大多数服务器的选票. 当这种情况发生时, 每个候选人将会超时, 并通过增加 Term 序列号启动新的一轮RequestVote RPC 来开始新的选举.但是，如果不采取额外措施，分裂投票可能会无限期重复

Raft 使用随机的选举超时时间来减少分裂投票的出现, 并可以快速解决. 为了防止分裂投票的第一步, 选举超时时间是从一个时间范围内(例如 150 ~ 300ms)随机选择的. 这分散了所有服务器的超时时间, 所以大多数情况下,只有一台服务器将会超时, 并且它将会在其他服务器超时之前赢得选举. 相同的机制也被运用在处理分裂投票. 每个候选人在选举开始之后重新设置选举超时时间, 并在这时间超过之后才能进行下一次选举. 这减少了新选举中再次分裂投票的可能性. 9.3 节表明，这种方法可以快速选举领导者

选举的过程是一个例子, 展示了我们如何在可理解性之间做出的选择. 最初我们计划使用排名系统: 为每个候选人分配一个唯一的排名, 用于在竞争候选人中进行选举. 如果一个候选人发现了另一个更高级别的候选人, 它将返回追随者状态, 以便更高级别的候选人容易赢得下一次选举. 我们发现这种方式在可用性上产生了微妙的问题.( 如果排名较高的服务器发生故障, 排名较低的服务器需要超时才能成为候选者, 但如果太早成为候选者, 那么可能会重置选举领导者的进度). 我们对算法进行了多次调整, 但每次调整后都会出现新的极端情况. 最终我们得出了结论, 随机重试方法更加明显和易于理解.

5.3 日志复制

一旦选出了领导者, 它就会开始为客户端请求进行服务. 每个客户端请求都包含一个由复制状态机执行的命令. 领导者将命令作为新条目附加到其日志中，然后向其他每个服务器并行发出 AppendEntries RPC 以复制该条目。当条目被安全复制后（如下所述），领导者将条目应用到其状态机并将执行结果返回给客户端. 如果追随者崩溃或运行缓慢，或者网络数据包丢失，领导者会无限期地重试 AppendEntries RPC（即使它已经响应客户端），直到所有追随者最终存储所有日志条目。

日志的结构如图6所示, 每个 log 存储一个状态机命令以及领导者收到条目时的 Term 序列号. log 中的 Term 序列号是为了检测不同服务器日志之间是否不一致并确保在图3中描述的一些属性, 每个 log 条目有相应的 index 去标识在 log 中的位置

领导者决定何时将 log 应用到状态机是安全的, 这样的 log 称为已提交. Raft 保证提交的日志是持久化的, 并最终被所有可用的状态机执行. 一旦领导者将 log 分发到了大多数的主机上(例如 图6 中的 log7), 就会进行 log 的提交. 这也提交了之前的 log 包括之前领导者创建的 log. 5.4 节讨论了在领导者变更后应用此规则时的一些微妙之处，并且还表明这种承诺的定义是安全的. 领导者对已提交的最高索引保持高度敏感，并将该索引包含在未来的 AppendEntries RPC（包括心跳）中，以便其他服务器最终发现. 一旦追随者得知日志已提交, 它将该条目应用于本地的状态机(按照 log 中的顺序).

我们设计了 Raft 日志机制来保持不同服务器上的日志之间的高度一致性。这不仅简化了系统的行为并使其更具可预测性，而且是确保安全的重要组成部分。 Raft 维护了以下属性，它们共同构成了图 3 中的 Log Matching Property：

• 如果不同机器中的两条日志有着相同的 index 和 Term, 则他们存储相同的命令.
• 如果不同机器中的两条日志有着相同的 index 和 Term, 则所有前面的日志都是相同的.

第一条是由于: 领导者在任期内最多创建一个相应索引的条目, 并且日志条目永远不会改变所在日志的索引位置. 第二条是当领导者发起 AppendEntries, 追随者将会进行简答的一致性检查. 领导者在发送 AppendEntries RPC 的同时也会将附加的新条目之前的 index 和 Term 序列号一并发送. 如果追随者检查过程中发现日志的末尾于请求中的不同, 那么将会拒绝新条目. 一致性检查就是归纳的一个步骤: 如果日志的初始状态为空满足日志匹配, 当日志附加时检查前一个是否满足. 这样当 AppendEntries 成功返回时，领导者通过新条目成功合并知道跟随者的日志与自己的日志相同。

正常运行时, 领导者和追随者的日志保持一致, 所以 AppendEntries 一致性检查永远不会失败. 但是, leader 崩溃会导致日志变得不一致( 旧的 leader 没能完全将 log 中的条目进行复制). 这些不一致会在一系列领导者和追随者的崩溃中加剧. 图7 说明了追随者的日志可能会与新领导者的日志不同的情况. 追随者可能缺少领导者上存在的条目, 或者具有领导者所没有的, 或者两种情况都有. 日志缺失的和额外的可能跨越多个 Term.

Raft 通过强制追随者使追随者的日志与自己的一致. 意味着如果追随者与领导者的日志存在冲突, 那么将会被覆盖. 在 5.4 节将会说明, 当再加上一个限制时会是安全的.

为了让追随者的日志与自己的日志保持一致, 领导者必须找到他们之间相同日志的最大索引. 删除该索引之后的日志, 并将之后的信息发送给追随者. 所有的这些操作都是在 AppendEntries RPC 执行一致性检查响应之后发生的. 领导者将会为每一个跟随者维护一个 nextIndex , 这是领导者将发给追随者的下一个日志的索引. 当领导者首次上台时, 它将会把所有的 nextIndex 初始化为自身日志的最后一个索引( 如图 7 中的 11 ). 如果追随者的日志与领导者的日志不一致, 则 AppendEntries 一致性检查将在下一个 AppendEntries RPC 中失败, 领导者将会减小 nextIndex 并重新发起 AppendEntries RPC . 最终 nextIndex 将达到领导者和追随者日志匹配的点. 此时 AppendEntries 的一致性检查将会成功. 这将从跟随者中删除所有冲突的条目, 并从领导者的日志中获取随后的条目(如果有). 当缺失的日志补齐后, 领导者与跟随者的日志将保持一致, 并且在接下来的任期内保持这种状态.

如果需要, 可以优化协议以减少被拒绝的 AppendEntries RPC 的数量. 例如, 当拒绝 AppendEntries 请求时, 跟随者可以将冲突的 Term 序列号以及使用该序列号的第一个 log 条目. 领导者有这些信息能更快的绕过冲突的条目. 这样一个 Term 导致的冲突只要一个请求就能解决. 在实践中，我们怀疑这种优化是否必要，因为失败很少发生，而且不太可能有很多不一致的条目。

通过这种属性, 领导者上台时无需采取任何措施来恢复日志的一致性. 只要正常开始运行, 日志将在 AppendEntries 一致性检查的失败响应中收敛. 领导者永远不会覆盖或者删除自己日志中的条目(图3 中的 Leader Append-Only Property ).

这种日志复制机制展示了第 2 节中描述的理想共识属性：只要大多数服务器处于运行状态，Raft 就可以接受、复制和应用新的日志条目； 在正常情况下，可以通过单轮 RPC 将新条目复制到大多数集群； 并且单个缓慢的追随者不会影响性能。

5.4 安全

前面部分描述了 Raft 如何进行选举领导者和复制日志条目. 然而到目前为止所描述的机制还不足以确保每个状态机以相同的顺序执行完全相同的命令。 例如，当领导者提交多个日志条目时，跟随者可能不可用，然后它可以被选举为领导者并用新条目覆盖这些条目； 因此，不同的状态机可能会执行不同的命令序列。

本章节补充了 Raft 中服务器能被选举为 Leader 的限制. 该限制确保任意 Term 的领导者都包含之前领导者提交的条目(图3中的 Leader Completeness Property). 通过选举的限制, 我们使提交的规则更加详细. 最后展示了 Leader Completeness Property 的证明草图, 并说明了为什么能够使复制状态机的行为正确.

5.4.1 选举限制

在任何基于领导者的共识算法中, 领导者最终都必须存储所有已提交的 log. 在某些共识算法中, 例如 Viewstamped Replication ²², 即使最初不包含所有已提交的条目, 也可以被选举为领导者. 这些算法使用额外的机制来识别丢失的条目并将它们传输给新的领导者, 无论是在选举过程中还是之后不久. 不幸的是, 这导致了相当多的额外机制和复杂性. Raft 使用了一种更简单的方法, 它保证从选举的那一刻起, 每个新领导上都存在所有之前已提交的条目, 而无需将这些条目转移到领导者. 这意味着日志条目仅有从领导者向跟随者流动, 并且领导者永远不会覆盖自身日志已有的条目.

Raft 使用投票程序防止日志未包含所有已提交条目的候选人赢得选举. 一个候选人需要与集群中的大多数服务器进行联系, 这意味着, 候选人已提交的日志中至少存在这些所联系的某一个服务器中. 如果候选人的日志至少和多数服务器中的日志一样是最新的(这里”最新”在后续有精确的定义), 那么将包含所有已提交的日志条目. RequestVote RPC实现了这一限制：RPC消息中包括关于候选人的日志情况，如果投票人自己的日志比候选人的日志更及时(更全)，那么投票人将拒绝其投票.

Raft 使用尾部日志的 Term 和索引进行比较哪一个比较及时. 如果两个日志末尾的 Term 不同, 那么 Term 序列号较大的比较新. 如果 Term 相同, 那么日志较长的比较及时.

5.4.2 来自前一个 Term 已提交的条目

就如5.3节描述的那样, 一旦一个日志条目被存储在大多数的服务器时, 领导者就知道该条目在当前 Term 被提交. 如果领导者在日志条目提交之前崩溃, 未来的领导者将尝试复制日志条目到其他主机. 但是领导者无法确定之前 Term 复制的日志是否被提交. 图 8 展示了这样一种情况: 一个旧的日志条目被存储在大多数服务器上, 但仍然可能被未来的领导者覆盖.

为了消除图 8 中出现的情况, Raft 永远不会通过计算已有副本来对之前的日志条目进行提交. 只有来自当前 Term 的日志领导者才会统计副本数量进行提交; 一旦以这种方式提交了当前 Term 中的条目, 因为 Log Matching Property 就间接的认为之前的日志已经提交了. 在某些情况下, 领导者可以安全的断定已提交的日志条目(例如: 如果该条目存储在每一个服务器上)但 Raft 为简单起见采取了更保守的方法.

Rust 引入了额外的复杂性在提交的规则中：领导者在复制先前的日志条目时，将会保留原有 Term 序列号. 在其他的共识算法中, 如果一个新的领导复制以前的”term”的条目, 必须使用新的 “Term” 序列号. Raft 的方式使得日志条目的推理更加容易. 因为在不同的时间和不同的日志中保持相同的 Term 序列号. 此外和其他算法相比, Raft 的新领导发送之前的日志的行为较少(其他算法需要对日志进行重新编号分发)

5.4.3 安全性论证

基于完整的 Raft 算法, 我们现在可以更精确的论证 Leader Completeness Property 是成立的(这个论证是基于安全证明; 见9.2节). 我们假设 Leader Completeness Property 不成立, 那我们就证明了一个矛盾点. 假设 Term T 的领导者在任期内提交了一个日志条目, 但是这个日志条目没有被未来的领导者所存储. 假设至少 U > T 的 Term 序列号, 领导者 U 没有存储该条目.

1. 提交的条目不存在 Leader U 的日志中, 当进行选举的时候 ( 领袖从不删除或者重写条目 )
   
2. 领导者T在集群的大多数服务器上复制了该日志条目, 而领导者U获得了集群中大多数人的投票. 所以至少有一个服务器(“投票者”)既接受 leader T的条目, 又将票投给了leader U. 这显然是矛盾的.
3. 投票人必须在把票投给 U 之前将领导者 T AppendEntries RPC的日志提交, 否则领导T的 AppendEntries 请求将会失败(投票后当前的 Term 序列号增加)
4. 投票人在给 leader U 投票时仍然存储了这个日志条目. 由于每一个参与的领导者都包含这个日志条目(根据假设)领导者从不删除日志条目, 跟随者只有在与领导者发生冲突时才会进行删除条目
5. 由于投票者将票投给了 U , 那么说明 领导者U的日志至少和选民是一样新的, 这导致了两个矛盾中的一个.
6. 如果投票者和领导者 U 最后一个日志项相同, 那么 leader U 的日志至少要和投票者的一样长, 这是一个矛盾, 因为投票者包含了已提交的条目, 而 leader U 被假设没有.
7. 或者 leader U 的最后一个日志条目的Trem 序列号要大于投票者. 此外它比T大，因为投票人的最后一个日志项至少是T 任期的（它包含T项的承诺条目). 给予leader U 的最后一个日志的领导,它日志中一定包含了已提交的日志条目. 根据 Log Matching Property 领导者U的日志也必须包含已承诺的条目，这就是矛盾的.
8. 这样就补充完成了矛盾, 因此所有大于 T 的领导者必须包含任期T中在任期T中提交的所有日志条目.
9. Log Matching Property 保证未来的领导者也将包含间接提交的条目，例如图 8(d) 中的索引 2。

基于 Leader Completeness Property, 我们可以证明图3中 State Machine Safety Property, 该属性表明如果服务器已将相应索引的日志应用到状态, 那么不会有其他服务器将相同位置的索引(内容与前面应用到状态机的不同). 当服务器将日志条目应用于状态机时, 相应的日志一定与服务器上的日志一致, 并且是已提交的状态.
现在假设较小的 Term 序列号将给定的日志索引信息应用到了状态机; Log Completeness Property 将确保更高任期的领导者将保存相同的日志, 所以在更高任期中将应用相同索引的相同值. 所以State Machine Safety Property成立

最后，Raft 要求服务器按日志索引顺序应用条目。结合 State Machine Safety Property，这意味着所有服务器将以相同的顺序将完全相同的一组日志条目应用到它们的状态机。

5.5 候选者或跟随者崩溃

在这之前, 我们一直专注于领导者的失败. 跟随者和候选者的崩溃比领导者要简单的多. 而且他们的处理方式都一样. 如果一个追随者或候选人崩溃了，那么未来发给它的RequestVote和AppendEntries RPC将 失败。Raft通过无限期地重试来处理这些失败。如果崩溃的服务器重新启动，那么RPC将成功完成 。如果一个服务器在完成RPC后但在响应前崩溃，那么它将在重启后再次收到相同的RPC 。Raft RPC是幂等的，所以这不会造成任何损害。例如，如果一个跟随者收到一个 AppendEntries请求，其中包括已经存在于其日志中的日志条目的请求，它就会在新的请求中忽略这些条目。

5.6 时机和可用性

我们对 Raft 的要求之一是, 安全必须不依赖于时间: 系统不能因为某些事情发生得比预期快或者慢而产生错误得结果. 然而, 可用性(系统及时响应客户的能力)必不可免的依赖于时间. 例如, 如果信息交换的时间超过了定义服务器奔溃的时间, 那么候选人没有足够长的时间来赢得选举; 没有一个稳定的领导, Raft 就不能取得进展.

领导者选举只是 Raft 的一个方面, 时机是关键的因素. Raft 可以进行选举并保持一个稳定的领导者, 只要系统满足以下时间条件:

broadcastTime ≪ electionTimeout ≪ MTBF
广播时间 << 选举时间 << 平均无故障时间

在这个不等式中，broadcastTime是一台服务器向集群中的每台服务器并行发送RPC并接收其响应所需的平均时间；electionTimeout是第5.2节中描述的选举超时；MTBF是单台服务器的平均故障间隔时间. 广播时间应该比选举超时少一个数量级，这样领导者就可以可靠地发送心跳信息，以防止追随者开始选举；考虑到选举超时使用的随机方法，这种不平等也使得分裂投票不太可能发生。选举超时应该比MTBF小几个数量级，这样系统才能稳步前进。当领导者崩溃时，系统将在大约选举超时的时间内不可用；我们希望这只占总体时间的一小部分.

广播时间和MTBF是底层系统的属性，而选举超时是我们必须选择的。Raft的RPC通常要求接收者将信息持久化到稳定的存储中，所以广播时间可能在0.5ms到20ms之间，这取决于存储技术。因此，选举超时可能是在10ms到500ms之间。典型的服务器MTBF是几个月或更长时间，这很容易满足时间要求。

6 集群成员变化

到目前为止，我们一直假设集群配置（参与共识算法的服务器集合）是固定的。在实践中，偶尔有必要改变配置，例如在服务器故障时更换服务器或改变复制的程度。虽然这可以通过将整个集群下线，更新配置文件，然后重新启动集群来完成，但这将使集群在转换期间不可用。此外，如果有任何手动步骤，就有可能出现操作错误。为了避免这些问题，我们决定将配置变更自动化，并将其纳入Raft共识算法中。

为了使配置变化机制安全，在过渡期间必须没有任何一点可以让两个领导人在同一任期内当选。不幸的是，任何服务器直接从旧配置切换到新配置的方法都是不安全的。不可能一次性地切换所有的服务器，所以集群有可能在过渡期间分裂成两个独立的多数派（见图10）。

为了确保安全，配置变更必须使用两阶段的方法。实现这两个阶段的方法有很多种。 例如，一些系统（如[22]）使用第一阶段禁用旧配置，使其无法处理客户端请求；然后第二阶段启用新配置。在Raft中，集群首先切换到一个过渡性配置，我们称之为联合共识；一旦联合共识被承诺，系统就会过渡到新的配置。联合共识结合了新旧两种配置。

• 日志条目被复制到两个配置中的所有服务器。
• 两个配置中的任何一个服务器都可以作为领导者
• 达成协议（选举和进入承诺）需要新旧组合分别获得多数票。

联合共识允许单个服务器在不同时间在配置之间转换，而不影响安全。此外，联合共识允许集群在整个配置变化过程中继续为客户请求提供服务。

集群配置使用冗余日志中的特殊条目进行存储和通信；图11说明了配置变更过程。当领导者收到将配置从 $C_{old}$ 改为 $C_{new}$ 的请求时，它将联合共识的配置（图中的 $C_{old, new}$ ）存储为一个日志条目，并使用前面描述的机制复制该条目。一旦某个服务器将新的配置条目添加到其日志中，它就会将该配置用于所有未来的决策（一个服务器总是使用其日志中的最新配置，无论该条目是否被提交）。这意味着领导者将使用 $C_{old, new}$ 的规则来决定 $C_{old, new}$ 的日志条目何时被提交。 如果领导者崩溃了，可能会在 $C_{old}$ 或 $C_{old, new}$ 下选择一个新的领导者，这取决于获胜的候选人是否已经得到了 $C_{old, new}$。在任何情况下， $C_{new}$ 在这期间都不能做出单边决定。

一旦 $C_{old, new}$ 被提交, $C_{old}$ 和 $C_{new}$ 都不能在未经对方批准的情况下做出决定. 而 Leader Completeness Property 确保了只有具有 $C_{old, new}$ 日志条目的服务器才能被选为领导者。现在领导者创建一个描述 $C_{new}$ 的日志条目并将其复制到集群中是安全的。同样，这个配置一旦可见，就会在每个服务器上生效。当新的配置在B的规则下被提交后，旧的配置就不重要了，不在新配置中的服务器可以被关闭了。如图11所示，没有任何时候 $C_{old}$ 和 $C_{new}$ 可以同时做出单边决定；这保证了安全。

对于重新配置，还有三个问题需要解决。第一个问题是，新的服务器最初可能不会存储任何日志条目。如果它们在这种状态下被添加到集群中，可能需要相当长的时间才能赶上，在此期间，可能无法提交新的日志条目。为了避免可用性差距，Raft在配置改变之前引入了一个额外的阶段，在这个阶段，新的服务器作为非投票成员加入集群（领导者将日志条目复制给他们，但他们不被考虑为多数）。一旦新的服务器赶上了集群的其他部分，重新配置就可以按上述方法进行。

第二个问题是，集群领导者可能不是新配置的一部分。在这种情况下，一旦它提交了 $C_{old}$ 日志条目，领导者就会下台（返回到跟随者状态）。这意味着会有一段时间（在它提交 $C_{old}$ 的时候），领导者在管理一个不包括自己的集群；它复制日志条目，但不把自己算在多数中。领导者过渡发生在 $C_{old}$ 被提交的时候，因为这是新配置可以独立运行的第一个点（总是可以从 $C_{old}$ 中选择一个领导者）。在这之前，可能只有 $C_{new}$ 的一个服务器可以被选为领导者。

第三个问题是，被移除的服务器（那些不在 $C_{new}$ 中的服务器）会扰乱集群。这些服务器不会收到心跳，所以它们会超时并开始新的选举。然后他们会发送带有新任期编号的RequestVote RPCs，这将导致当前的领导者恢复到追随者状态。一个新的领导者最终将被选出，但被移除的服务器将再次超时，这个过程将重复，导致可用性差。

为了防止这个问题，当服务器认为存在一个当前的领导者时，它们就会忽略RequestVote RPCs。具体来说，如果一个服务器在听到当前领袖的最小选举超时内收到RequestVote RPC，它不会更新其任期或授予其投票。 这并不影响正常的选举，每个服务器在开始选举之前至少要等待一个最小的选举超时。 然而，这有助于避免被移除的服务器的干扰：如果一个领导者能够在集群中发送心跳，那么它就不会被较大的任期数字所废黜。

7 日志压缩

Raft的日志在正常运行期间不断增长，以纳入更多的客户端请求，但在一个实际的系统中，它不能无限制地增长。随着日志的增长，它占据了更多的空间，需要更多的时间来重放。如果没有某种机制来丢弃积累在日志中的过时信息，这最终会导致可用性问题。

快照是最简单的压缩方法。在快照中，整个当前系统状态被写入稳定存储的快照中，然后丢弃截至该点的整个日志。快照在Chubby和ZooKeeper中使用，本节的其余部分将介绍Raft中的快照。

增量压缩方法，如日志清理[36]和日志结构的合并树[30，5]，也是可能的。这些方法一次对一部分数据进行操作，因此它们将压缩的负荷更均匀地分散在一段时间内。它们首先选择一个已经积累了许多删除和覆盖对象的数据区域，然后将该区域的活对象重写得更紧凑，并释放该区域。与快照相比，这需要大量的额外机制和复杂性，因为快照总是对整个数据集进行操作，从而简化了问题。虽然日志清理需要对Raft进行修改，但状态机可以使用与快照相同的接口实现LSM树。

图12显示了Raft中快照的基本思路。每台服务器独立进行快照，只覆盖其日志中已提交的条目。大部分的工作包括状态机将其当前状态写入快照。Raft还在快照中包含了少量的元数据：”last included index” 是快照所取代的日志中最后一个条目的索引（状态机应用的最后一个条目），”last included term” 是这个条目所在的 Term 序列号。这些被保留下来是为了支持快照后的第一个日志条目的AppendEntries一致性检查，因为该条目需要一个先前的日志索引和 Term 序列号。为了实现集群成员的变化（第6节），快照还包括日志中的最新配置，即最后包含的索引。一旦服务器完成写入快照，它可以删除所有的日志条目，直到最后包含的索引，以及任何先前的快照。

尽管服务器通常是独立进行快照，但领导者偶尔必须向落后的跟随者发送快照。这种情况发生在领导者已经丢弃了它需要发送给跟随者的下一个日志条目。幸运的是，这种情况在正常操作中不太可能发生：一个跟上领导者的追随者已经有了这个条目。然而，一个特别慢的跟随者或一个新加入集群的服务器（第6节）就不会有这样的情况。让这样的追随者跟上的方法是，领导者通过网络向它发送一个快照。

领导者使用一个叫做InstallSnapshot的新RPC来向落后于它的跟随者发送快照；见图13。当跟随者收到这个RPC的快照时，它必须决定如何处理其现有的日志条目。通常情况下，快照将包含新的信息，而不是已经在接收者的日志中。在这种情况下，跟随者会丢弃它的整个日志；它都被快照取代了，而且可能有与快照冲突的未提交的条目。相反，如果跟随者收到描述其日志前缀的快照（由于重传或错误），那么被快照覆盖的日志条目被删除，但快照之后的条目仍然有效，必须保留。

这种快照方法偏离了Raft的强势领导原则，因为跟随者可以在领导不知情的情况下进行快照。然而，我们认为这种背离是合理的。虽然有一个领导者有助于在达成共识时避免冲突的决定，但在快照时已经达成了共识，所以没有决定冲突。数据仍然只从领导者流向追随者，只是追随者现在可以重新组织他们的数据。

我们考虑了另一种基于领导者的方法，即只有领导者会创建一个快照，然后它将把这个快照发送给它的每个追随者。然而，这有两个缺点。首先，向每个追随者发送快照会浪费网络带宽，并减缓快照过程。每个追随者都已经拥有产生其自身快照所需的信息，而且对于服务器来说，从其本地状态产生快照通常比通过网络发送和接收快照要便捷得多。第二，领导者的实现将更加复杂。例如，领导者需要在向追随者复制新的日志条目的同时向他们发送快照，以免阻碍新的客户请求。

第二个性能问题是，写入快照可能需要大量的时间，我们不希望因此而耽误正常的操作。 解决方案是使用写时复制技术，这样新的更新可以被接受而不影响正在写入的快照。 例如，用功能数据结构构建的状态机自然支持这一点。 另外，操作系统的写时拷贝支持（例如Linux上的fork）可以用来创建整个状态机的内存快照（我们的实现采用了这种方法）。

8 与客户端的互动

本节介绍了客户如何与Raft互动，包括客户如何找到集群领导者以及Raft如何支持可线性化语义¹⁰。这些问题适用于所有基于共识的系统，而且Raft的解决方案与其他系统相似。

Raft 的客户端将其所有的请求发送给领导者。当客户端第一次启动时，它连接到一个随机选择的服务器。如果客户端的第一选择不是领导者，该服务器将拒绝客户端的请求，并提供它最近收到的领导者的信息（AppendEntries请求包括领导者的网络地址）。如果领导者崩溃了，客户端的请求就会超时；然后客户端会在随机选择的服务器上再次尝试。

我们对Raft的目标是实现可线性化的语义（每个操作看起来都是瞬间执行的，在其调用和响应之间的某个点上正好一次）。然而，正如目前所描述的那样，Raft可以多次执行一个命令：例如，如果领导者在提交日志条目后但在响应客户端之前崩溃，客户端将用一个新的领导者重试该命令，导致它被第二次执行。解决方案是让客户端为每个命令分配唯一的序列号。然后，状态机跟踪为每个客户处理的最新序列号，以及相关的响应。如果它收到一个序列号已经被执行的命令，它会立即响应，而不重新执行该请求。
只读操作可以在不向日志中写入任何内容的情况下进行处理。然而，如果没有额外的措施，这将有返回陈旧数据的风险，因为响应请求的领导者可能已经被它不知道的较新的领导者所取代。可线性化的读取必须不返回陈旧的数据，Raft需要两个额外的预防措施来保证这一点而不使用日志。首先，领导者必须拥有关于哪些条目被提交的最新信息。领导者完整性属性保证领导者拥有所有已提交的条目，但在其任期开始时，它可能不知道哪些是。为了找到答案，它需要从其任期内提交一个条目。Raft通过让每个领导者在其任期开始时向日志提交一个空白的无操作条目来处理这个问题。第二，领导者在处理只读请求之前，必须检查它是否已经被废黜（如果最近的领导者已经当选，那么它的信息可能是过时的）。Raft通过让领导者在响应只读请求之前与集群中的大多数人交换心跳信息来处理这个问题。另外，领导者可以依靠心跳机制来提供一种租赁形式⁹，但这要依靠时间来保证安全（它假定了有界的时钟偏移）。

9 实施和评估

我们将Raft实现为复制的状态机的一部分，该状态机存储RAMCloud[33]的配置信息，并协助RAMCloud协调器的故障转移。 Raft的实现包含大约2000行的C++代码，不包括测试、注释或空行。源代码可以免费获得[23]。 根据本文的草稿，还有大约25个独立的第三方开源实现[34]，处于不同的开发阶段。此外，各种公司也在部署基于Raft的系统[34]。本节的其余部分使用三个标准对Raft进行评估：可理解性、正确性和性能。

9.1 可理解性

为了衡量Raft相对于Paxos的可理解性，我们对斯坦福大学高级操作系统课程和加州大学伯克利分校分布式计算课程的高年级本科生和研究生进行了一项实验性研究。我们录制了Raft和Paxos的视频讲座，并制作了相应的测验。Raft的讲座涵盖了本文的内容，除了日志压缩；Paxos的讲座涵盖了足够的材料来创建一个等效的复制状态机，包括单法令Paxos、多法令Paxos、重新配置，以及实践中需要的一些优化（如领导者选举）。测验测试了对算法的基本理解，还要求学生对角落的情况进行推理。每个学生都看了一个视频，做了相应的测验，看了第二个视频，做了第二个测验。大约一半的参与者先做Paxos部分，另一半先做Raft部分，以便考虑到个人表现的差异和从研究的第一部分获得的经验。我们比较了参与者在每次测验中的得分，以确定参与者是否对Raft有更好的理解。

我们试图使Paxos和Raft之间的比较尽可能的公平。实验在两个方面对Paxos有利。43名参与者中的15名报告说以前有一些使用Paxos的经验，而且Paxos的视频比Raft的视频长14%。正如表1所总结的，我们采取了措施来减少潜在的偏见来源。我们所有的材料都可供查阅[28, 31]。

平均而言，参与者在Raft测验中的得分比Paxos测验高4.9分（在可能的60分中，Raft的平均得分是25.7分，Paxos的平均得分是20.8分）；图14显示了他们的个人得分。成对的t检验表明，在95%的置信水平下，Raft分数的真实分布比Paxos分数的真实分布至少大2.5分。

我们还创建了一个线性回归模型，根据三个因素预测新学生的测验分数：他们参加的测验，他们以前的Paxos经验程度，以及他们学习算法的顺序。该模型预测,测验的选择会产生有12.5分的差异对Raft的偏好。这明显高于观察到的4.9分的差异，因为许多实际的学生之前有Paxos的经验，这对Paxos的帮助很大，而对Raft的帮助则略小。奇怪的是，模型还预测已经参加过Paxos测验的人在Raft上的得分要低6.3分；虽然我们不知道为什么，但这似乎在统计上是显著的。

我们还在测验后对参与者进行了调查，看看他们认为哪种算法更容易实施或解释；这些结果见图15。绝大多数参与者认为Raft更容易实施和解释（每个问题41人中有33人）。然而，这些自我报告的感受可能不如参与者的测验分数可靠，而且参与者可能因为知道我们的假设—Raft更容易理解而产生偏差。

关于Raft用户研究的详细讨论，可参见[31]。

9.2 正确性

我们已经为第5节中描述的共识机制开发了一个正式的规范和安全证明。形式规范[31]使用TLA+规范语言[17]使图2中总结的信息完全精确。它长约400行，作为证明的主题。它本身对实现Raft的人来说也是有用的。我们已经使用TLA证明系统[7]机械地证明了对数完整性属性。然而，这个证明依赖于没有经过机械检查的不变量（例如，我们没有证明规范的类型安全）。此外，我们已经写了一个关于状态机安全属性的非正式证明[31]，它是完整的（它仅仅依赖于规范）和相对精确的（它大约有3500字）。

9.3 性能

Raft的性能与其他共识算法（如Paxos）相似。对于性能来说，最重要的情况是当一个已建立的领导者在复制新的日志条目时。Raft使用最少的信息数量（从领导者到一半集群的单次往返）实现了这一点。进一步提高Raft的性能也是可能的。例如，它很容易支持批处理和管道化请求，以获得更高的吞吐量和更低的延迟。文献中已经为其他算法提出了各种优化方案；其中许多方案可以应用于Raft，但我们将此留给未来的工作。

我们用我们的Raft实现来衡量Raft的领导人选举算法的性能，并回答两个问题。首先，选举过程是否快速收敛？第二，领导者崩溃后能实现的最小停机时间是多少？

为了测量领导者的选举，我们反复地让五个服务器集群的领导者崩溃，并计时检测崩溃和选举新的领导者所需的时间（见图16）。为了产生一个最坏的情况，每次试验中的服务器都有不同的日志长度，所以一些候选人没有资格成为领导者。此外，为了鼓励分裂投票，我们的测试脚本在终止其进程之前触发了领导者的心跳RPC的同步广播（这接近于领导者在崩溃前复制新的日志条目的行为）。领导者在其心跳间隔内被均匀地随机崩溃，这个间隔是所有测试中最小选举超时的一半。因此，最小的可能停机时间是最小选举超时的一半左右。

图16中的顶部图表显示，选举超时中的少量随机性足以避免选举中的分裂票。在没有随机性的情况下，在我们的测试中，由于许多分裂的投票，领导选举的时间一直超过10秒。仅仅增加5毫秒的随机性就有很大的帮助，导致中位数停机时间为287毫秒。使用更多的随机性可以改善最坏情况下的行为：使用50ms的随机性，最坏情况下的完成时间（超过1000次试验）为513ms。

图16中的底图显示，通过减少选举超时，可以减少停机时间。在选举超时12-24ms的情况下，平均只需要35ms就能选出一个领导者（最长的试验花了152ms）。然而，将超时时间降低到超过这个点，就违反了Raft的时间要求：领导者很难在其他服务器开始新的选举之前广播心跳声。这可能会导致不必要的领导者更换，降低系统的整体可用性。我们建议使用保守的选举超时，如150-300ms；这样的超时不太可能导致不必要的领导者变更，而且仍将提供良好的可用性。

10 相关工作

有许多与共识算法有关的出版物，其中许多属于以下类别之一:

• Lamport对Paxos的原始描述[15]，以及尝试更清楚地解释[16, 20, 21]。
• 对Paxos的阐述，填补了缺失的细节，修改了算法，为实现提供了更好的基础[26, 39, 13]。
• 实现共识算法的系统，如Chubby [2, 4], ZooKeeper [11, 12], 和Spanner [6]。Chubby和Spanner的算法还没有详细公布，尽管两者都声称是基于Paxos的。ZooKeeper的算法已经公布了更多的细节，但它与Paxos有很大的不同。
• 可以应用于Paxos的性能优化[18, 19, 3, 25, 1, 27]。
• Oki和Liskov的Viewstamped Replication (VR)，这是一种与Paxos差不多同时开发的共识的替代方法。最初的描述[29]与分布式交易的协议交织在一起，但在最近的更新中[22]，核心共识协议被分离出来。VR使用了一种基于领导者的方法，与Raft有许多相似之处。

Raft和Paxos的最大区别是Raft的强大领导力。Raft将领导者选举作为共识协议的一个重要部分，它将尽可能多的功能集中在领导者身上。这种方法导致了更简单的算法，更容易理解。例如，在Paxos中，领导者选举与基本的共识协议是正交的：它只是作为一种性能优化，并不是实现共识的必要条件。然而，这导致了额外的机制。Paxos包括一个两阶段的基本共识协议和一个单独的领袖选举机制。相比之下，Raft将领袖选举直接纳入共识算法，并将其作为共识的两个阶段中的第一阶段。这导致了比Paxos更少的机制。

与Raft一样，VR和ZooKeeper也是基于领导者的，因此与Paxos相比，Raft有很多优势。然而，Raft的机制不如VR或ZooKeeper，因为它将非领导者的功能降到最低。例如，Raft中的日志条目只向一个方向流动：从AppendEntries RPCs的领导者向外流动。在VR中日志条目是双向流动的（领导者可以在选举过程中接收日志条目）；这导致了额外的机制和复杂性。ZooKeeper的公开描述也是将日志条目同时传送到领导者或从领导者那里获取，但其实现显然更像Raft[35]。

Raft的消息类型比我们所知的任何其他基于共识的日志复制算法都少。例如，我们计算了VR和ZooKeeper用于基本共识和成员变化的消息类型（不包括日志压缩和客户端互动，因为这些几乎是独立于算法的）。VR和ZooKeeper各自定义了10种不同的消息类型，而Raft只有4种消息类型（两个RPC请求和它们的响应）。Raft的消息比其他算法的更密集一些，但它们总体上更简单。此外，VR和ZooKeeper的描述是在领导者变化期间传输整个日志；为了优化这些机制，将需要额外的消息类型，以便它们能够实用。

Raft的强领导方法简化了算法，但它排除了一些性能优化。例如，Egalitarian Paxos（EPaxos）在某些条件下可以通过无领导的方法获得更高的性能[27]。EPaxos利用了状态机命令的交换性。只要其他同时提出的命令与之换算，任何服务器都可以只用一轮通信来提交一个命令。然而，如果同时提出的命令不能相互交换，EPaxos需要额外的一轮通信。由于任何服务器都可以提交命令，EPaxos可以很好地平衡服务器之间的负载，并能够在广域网环境中实现比Raft更低的延迟。然而，它给Paxos增加了很大的复杂性。

其他工作中已经提出或实施了几种不同的集群成员变化方法，包括Lamport的原始提议[15]、VR[22]和SMART[24]。我们为Raft选择了联合共识的方法，因为它利用了共识协议的其他部分，所以成员资格变更所需的额外机制非常少。Lamport的基于α的方法不是Raft的选择，因为它假设没有领导者也能达成共识。与VR和SMART相比，Raft的重新配置算法的优点是，成员变化可以在不限制正常请求的处理的情况下发生；相反，VR在配置变化期间停止所有的正常处理，而SMART对未完成的请求数量施加了类似α的限制。Raft的方法也比VR或SMART增加了更少的机制。

11 结语

算法的设计通常以正确性、效率和/或简洁性为主要目标。尽管这些都是有价值的目标，但我们认为可理解性也同样重要。在开发者将算法转化为实际的实现之前，其他的目标都无法实现，而实际的实现将不可避免地偏离和扩展公布的形式。除非开发者对该算法有深刻的理解，并能对其产生直觉，否则他们将很难在实现中保留其理想的属性。

在本文中，我们讨论了分布式共识的问题，其中一个被广泛接受但难以理解的算法—Paxos，多年来一直在挑战学生和开发者。我们开发了一种新的算法—Raft，我们已经证明它比Paxos更容易理解。我们还认为Raft为系统建设提供了一个更好的基础。将可理解性作为主要的设计目标改变了我们设计Raft的方式；随着设计的进展，我们发现自己反复使用了一些技术，例如分解问题和简化状态空间。这些技术不仅提高了Raft的可理解性，而且也使我们更容易相信它的正确性。

12 致谢

The user study would not have been possible without the support of Ali Ghodsi, David Mazieres, and the students of CS 294-91 at Berkeley and CS 240 at Stanford. Scott Klemmer helped us design the user study, and Nelson Ray advised us on statistical analysis. The Paxos slides for the user study borrowed heavily from a slide deck originally created by Lorenzo Alvisi. Special thanks go to David Mazieres and Ezra Hoch for finding subtle bugs in Raft. Many people provided helpful feedback on the paper and user study materials, including Ed Bugnion, Michael Chan, Hugues Evrard, Daniel Giffin, Arjun Gopalan, Jon Howell, Vimalkumar Jeyakumar, Ankita Kejriwal, Aleksandar Kracun, Amit Levy, Joel Martin, Satoshi Matsushita, Oleg Pesok, David Ramos, Robbert van Renesse, Mendel Rosenblum, Nicolas Schiper, Deian Stefan, Andrew Stone, Ryan Stutsman, David Terei, Stephen Yang, Matei Zaharia, 24 anonymous conference reviewers (with duplicates), and especially our shepherd Eddie Kohler. Werner Vogels tweeted a link to an earlier draft, which gave Raft significant exposure. This work was supported by the Gigascale Systems Research Center and the Multiscale Systems Center, two of six research centers funded under the Focus Center Research Program, a Semiconductor Research Corporation program, by STARnet, a Semiconductor Research Corporation program sponsored by MARCO and DARPA, by the National Science Foundation under Grant No. 0963859, and by grants from Facebook, Google, Mellanox, NEC, NetApp, SAP, and Samsung. Diego Ongaro is supported by The Junglee Corporation Stanford Graduate Fellowship.

引用

[1] BOLOSKY, W. J., BRADSHAW, D., HAAGENS, R. B., KUSTERS, N. P., AND LI, P. Paxos replicated state
machines as the basis of a high-performance data store. In Proc. NSDI’11, USENIX Conference on Networked Systems Design and Implementation (2011), USENIX, pp. 141–154.
[2] BURROWS, M. The Chubby lock service for looselycoupled distributed systems. In Proc. OSDI’06, Symposium on Operating Systems Design and Implementation (2006), USENIX, pp. 335–350.
[3] CAMARGOS, L. J., SCHMIDT, R. M., AND PEDONE, F. Multicoordinated Paxos. In Proc. PODC’07, ACM Symposium on Principles of Distributed Computing (2007), ACM, pp. 316–317.
[4] CHANDRA, T. D., GRIESEMER, R., AND REDSTONE, J. Paxos made live: an engineering perspective. In Proc. PODC’07, ACM Symposium on Principles of Distributed Computing (2007), ACM, pp. 398–407.
[5] CHANG, F., DEAN, J., GHEMAWAT, S., HSIEH, W. C., WALLACH, D. A., BURROWS, M., CHANDRA, T.,
FIKES, A., AND GRUBER, R. E. Bigtable: a distributed storage system for structured data. In Proc. OSDI’06, USENIX Symposium on Operating Systems Design and Implementation (2006), USENIX, pp. 205–218.
[6] CORBETT, J. C., DEAN, J., EPSTEIN, M., FIKES, A., FROST, C., FURMAN, J. J., GHEMAWAT, S., GUBAREV, A., HEISER, C., HOCHSCHILD, P., HSIEH, W., KANTHAK, S., KOGAN, E., LI, H., LLOYD, A., MELNIK, S., MWAURA, D., NAGLE, D., QUINLAN, S., RAO, R., ROLIG, L., SAITO, Y., SZYMANIAK, M., TAYLOR, C., WANG, R., AND WOODFORD, D. Spanner: Google’s globally-distributed database. In Proc. OSDI’12, USENIX Conference on Operating Systems Design and Implementation (2012), USENIX, pp. 251–264.
[7] COUSINEAU, D., DOLIGEZ, D., LAMPORT, L., MERZ, S., RICKETTS, D., AND VANZETTO, H. TLA+ proofs. In Proc. FM’12, Symposium on Formal Methods (2012), D. Giannakopoulou and D. M´ery, Eds., vol. 7436 of Lecture Notes in Computer Science, Springer, pp. 147–154.
[8] GHEMAWAT, S., GOBIOFF, H., AND LEUNG, S.-T. The Google file system. In Proc. SOSP’03, ACM Symposium on Operating Systems Principles (2003), ACM, pp. 29–43.
[9] GRAY, C., AND CHERITON, D. Leases: An efficient faulttolerant mechanism for distributed file cache consistency. In Proceedings of the 12th ACM Ssymposium on Operating Systems Principles (1989), pp. 202–210.
[10] HERLIHY, M. P., AND WING, J. M. Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems 12 (July 1990), 463–492.
[11] HUNT, P., KONAR, M., JUNQUEIRA, F. P., AND REED, B. ZooKeeper: wait-free coordination for internet-scale systems. In Proc ATC’10, USENIX Annual Technical Conference (2010), USENIX, pp. 145–158.
[12] JUNQUEIRA, F. P., REED, B. C., AND SERAFINI, M. Zab: High-performance broadcast for primary-backup systems. In Proc. DSN’11, IEEE/IFIP Int’l Conf. on Dependable Systems & Networks (2011), IEEE Computer Society, pp. 245–256.
[13] KIRSCH, J., AND AMIR, Y. Paxos for system builders. Tech. Rep. CNDS-2008-2, Johns Hopkins University, 2008.
[14] LAMPORT, L. Time, clocks, and the ordering of events in a distributed system. Commununications of the ACM 21, 7 (July 1978), 558–565.
[15] LAMPORT, L. The part-time parliament. ACM Transactions on Computer Systems 16, 2 (May 1998), 133–169.
[16] LAMPORT, L. Paxos made simple. ACM SIGACT News 32, 4 (Dec. 2001), 18–25.
[17] LAMPORT, L. Specifying Systems, The TLA+ Language and Tools for Hardware and Software Engineers. AddisonWesley, 2002.
[18] LAMPORT, L. Generalized consensus and Paxos. Tech. Rep. MSR-TR-2005-33, Microsoft Research, 2005.
[19] LAMPORT, L. Fast paxos. Distributed Computing 19, 2 (2006), 79–103.
[20] LAMPSON, B. W. How to build a highly available system using consensus. In Distributed Algorithms, O. Baboaglu and K. Marzullo, Eds. Springer-Verlag, 1996, pp. 1–17.
[21] LAMPSON, B. W. The ABCD’s of Paxos. In Proc. PODC’01, ACM Symposium on Principles of Distributed Computing (2001), ACM, pp. 13–13.
[22] LISKOV, B., AND COWLING, J. Viewstamped replication revisited. Tech. Rep. MIT-CSAIL-TR-2012-021, MIT, July 2012.
[23] LogCabin source code. http://github.com/logcabin/logcabin.
[24] LORCH, J. R., ADYA, A., BOLOSKY, W. J., CHAIKEN, R., DOUCEUR, J. R., AND HOWELL, J. The SMART
way to migrate replicated stateful services. In Proc. EuroSys’06, ACM SIGOPS/EuroSys European Conference on Computer Systems (2006), ACM, pp. 103–115.
[25] MAO, Y., JUNQUEIRA, F. P., AND MARZULLO, K. Mencius: building efficient replicated state machines for WANs. In Proc. OSDI’08, USENIX Conference on Operating Systems Design and Implementation (2008), USENIX, pp. 369–384.
[26] MAZIERES , D. Paxos made practical. http://www.scs.stanford.edu/˜dm/home/ papers/paxos.pdf, Jan. 2007. [27] MORARU, I., ANDERSEN, D. G., AND KAMINSKY, M. There is more consensus in egalitarian parliaments. In Proc. SOSP’13, ACM Symposium on Operating System Principles (2013), ACM. [28] Raft user study. http://ramcloud.stanford.edu/˜ongaro/userstudy/. [29] OKI, B. M., AND LISKOV, B. H. Viewstamped replication: A new primary copy method to support highly-available distributed systems. In Proc. PODC’88, ACM Symposium on Principles of Distributed Computing (1988), ACM, pp. 8–17. [30] O’NEIL, P., CHENG, E., GAWLICK, D., AND ONEIL, E. The log-structured merge-tree (LSM-tree). Acta Informatica 33, 4 (1996), 351–385. [31] ONGARO, D. Consensus: Bridging Theory and Practice.PhD thesis, Stanford University, 2014 (work in progress).http://ramcloud.stanford.edu/˜ongaro/thesis.pdf. [32] ONGARO, D., AND OUSTERHOUT, J. In search of an understandable consensus algorithm. In Proc ATC’14, USENIX Annual Technical Conference (2014), USENIX. [33] OUSTERHOUT, J., AGRAWAL, P., ERICKSON, D., KOZYRAKIS, C., LEVERICH, J., MAZIERES , D., MITRA, S., NARAYANAN, A., ONGARO, D., PARULKAR, G., ROSENBLUM, M., RUMBLE, S. M., STRATMANN,
E., AND STUTSMAN, R. The case for RAMCloud. Communications of the ACM 54 (July 2011), 121–130.
[34] Raft consensus algorithm website. http://raftconsensus.github.io.
[35] REED, B. Personal communications, May 17, 2013.
[36] ROSENBLUM, M., AND OUSTERHOUT, J. K. The design and implementation of a log-structured file system. ACM Trans. Comput. Syst. 10 (February 1992), 26–52.
[37] SCHNEIDER, F. B. Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Computing Surveys 22, 4 (Dec. 1990), 299–319.
[38] SHVACHKO, K., KUANG, H., RADIA, S., AND CHANSLER, R. The Hadoop distributed file system.
In Proc. MSST’10, Symposium on Mass Storage Systems and Technologies (2010), IEEE Computer Society,
pp. 1–10.
[39] VAN RENESSE, R. Paxos made moderately complex. Tech. rep., Cornell University, 2012.