摘要

Raft是一个管理同步日志的一致性算法。它取得和（多重）Paxos等同的结果，相似的效率，但它的结构与Paxos大不相同，这使得Raft比Paxos更易于理解，并且给构建实际的系统提供了一个更好的基础。为了加强可理解性，Raft分解了一致性的关键元素，例如领导者选举（leader election）、日志复制（log replication）和安全性（safety），同时它实施一个更强的关联性等级，以减少需要考虑的状态数量。一个用户研究结果证明，Raft相比于Paxos更易于被学生掌握。Raft也包含一个新的用于调整集群成员的机制，它使用了重叠的多数集用于保证安全性。

1 简介

一致性算法允许一个机器集合像一个相干群组那样工作，能够幸免于它的部分成员的故障。因为这个原因，它们在构建可靠的大规模软件系统时，起到了关键性的作用。Paxos[13, 14]在过去十年关于一致性算法的讨论中，一直占据主导地位：大部分一致性的实现基于Paxos，或者受它影响，并且Paxos也成为教授学生关于一致性的主要工具媒介。

不幸的是，尽管有众多尝试让它更易于接受，Paxos还是非常难以理解。此外，它的构架需要复杂的改造，才能支持实际的系统。这样的结果就是，无论系统建设者还是学生，都苦苦地与Paxos作斗争。

在我们自己挣扎于与Paxos的斗争以后，我们着手寻找一种新的一致性算法，能够为系统建设和教学提供更好的基础。我们的方法比较不同寻常，在于我们的首要目标是可理解性（understandability）：我们能否为实际的系统定义一个一致性算法，并且能以比Paxos显著简单易学的方式描述它？除此之外，我们想让这个算法更加直观，这对于系统建设者来说是非常关键的。它的重要性不止是在于这个算法能够运行，而是在于能明显地知道为什么它能够运行。

这项工作的结果是一个叫做Raft的一致性算法。在设计Raft的时候，我们使用一些特定的技巧去提升可理解性，包括分解（Raft拆分了领导者选举、日志复制和安全性）和状态空间精简（相对于Paxos，Raft减少了不确定性的等级和服务器之间可能出现不一致的途径）。一个对两所大学的43名学生的用户调查研究表明Raft比Paxos显著简单易懂：在学了这两种算法后，其中的33名学生回答关于Raft的问题比关于Paxos的问题更好。

Raft在很多方面跟现有的一致性算法相似（最明显的是Oki和Liskov的Viewstamped Replication算法[27, 20]），但是它也有一些新颖的特性：

强领导模式：Raft相比其他一致性算法，使用了一种更强的领导模式。例如，日志记录（log entry）只会从领导者节点发到其他服务器。这就简化了同步日志（replicated log）的管理，也使Raft更容易被理解。
领导者选举：Raft使用随机时钟来选举领导者。这只需要在任何一致性算法都已经需要的心跳（heartbeats）上增加少量机制，就能简单快速地解决冲突问题。
成员变更：Raft的集群服务器集合变更机制，使用了一种新的联合一致性（joint consensus）方法，在过渡阶段，两个不同配置的多数集（majorities）相互叠加。这就允许集群能在配置变更过程中，继续正常地操作。

我们相信Raft优于Paxos和其他一致性算法，无论是用于教学目的还是作为实现的基础。它更简单，也比其他算法更易于理解；它描述得足够完整，能够满足实际系统的需求；它有一些开源的实现，并且被一些公司使用；它的安全性特性已经被正式地描述和证明；它的效率能够与其他算法进行比较。

这篇论文的余下部分介绍了复制状态机问题（第2节），讨论了Paxos的长处和短处（第3节），描述了我们对于可理解性的通用方法（第4节），展示了Raft一致性算法（第5-7节），评测了Raft（第8节），并且讨论了相关的工作（第9节）。由于篇幅限制，在这里省略了Raft算法的一些元素，但可以在一篇扩展技术报告中了解它们[29]。这篇附加材料描述了客户端是如何跟系统交互的，以及Raft日志如何回收空间。

2 复制状态机

一致性算法通常产生于复制状态机上下文当中[33]。在这个方面，运行在一组服务器上的状态机，处理完全相同的状态副本，并且能够在一些服务器下线时继续运作。复制状态机被用于解决分布式系统中各种各样的容错问题。例如，在拥有一个集群领导者的大规模系统中，如GFS[7]、HDFS[34]和RAMCloud[30]，一般使用一个单独的复制状态机去管理领导者选举和保存配置信息，以便应对领导者节点的崩溃。复制状态机的例子包括Chubby[2]和ZooKeeper[9]。

图1：复制状态机架构。一致性算法管理一个包含客户端提交的状态机指令的复制日志。这些状态机处理日志中的相同序列的指令，所以他们能产生相同的输出。

复制状态机的实现，通常使用一个复制日志，如图1所示。每个服务器保存一个包含一系列指令的日志，它的状态机按顺序执行这些指令。每个日志包含相同顺序的相同指令，所以每一个状态机处理相同序列的指令集合。由于状态机是确定性的，所以每一个都处理相同的状态和相同的输出序列。

保持复制日志的一致性是一致性算法的工作。服务器上的一致性模块，接收客户端提交的指令，并把它们添加到日志当中。它跟其他服务器上的一致性模块交互，确保每一个日志最终包含相同顺序的相同请求，即使有些服务器发生了故障。一旦指令被正确地复制，每一台服务器上的状态机都按日志的顺序它们，并且结果将返回给客户端。这样，这些服务器好像组成一个单一又高可靠的状态机。

实际应用的一致性算法通常具有下列的特性：

它们确保在所有非拜占庭（non-Byzantine）条件下的安全性（从不返回不正确的结果），包括网络延迟、网络分区、丢包、重复包和乱序包。
只要多数服务器（majority）还正常运转，并且能与其他服务器和客户端通信，它们的功能就是齐全的（可用的）。因此，一个典型的由5台服务器组成的集群，可以容忍任意2台服务器发生故障。服务器假定故障停止，后续可以从持续化存储的状态中恢复，并且重新加入到集群。
它们不依赖时序去确保日志的一致性：有缺陷的时钟和极端消息延迟在最坏的情况下可能导致可用性问题。
在一般情况下，指令能在单轮集群的多数集响应RPC调用后完成，一些少数慢节点（minority）不会影响系统的整体性能。

3 Paxos有什么问题

在过去十年里，Leslie Lamport的Paxos协议[3]基本成为了一致性的同义词：它是课堂里最常教授的协议，也最常作为实现一致性的起始点。Paxos首先定义了一个能够在单个决定中达成共识的协议，例如一条复制日志记录。我们将这个子集称为单决议Paxos（single-decree）。Paxos将这个协议的多个实例组合起来，以推进一系列决定，如日志（多决议Paxos，multi-Paxos）。Paxos确保安全性（safety）和活性（liveness），并且支持集群成员变化。它的正确性已经被证明，而且通常情况下也比较高效。

不幸的是，Paxos有两个明显的缺陷。第一个缺陷是Paxos极其难以理解，它的完整说明[13]是众所周知的晦涩难懂，很少人能理解它，并且还得付出极大努力。于是，就有了一些用更简单的术语去解释Paxos的尝试[14, 18, 19]。这些解释聚焦在单决议子集，然而它们仍然具有挑战性。在一次对NSDI 2012与会者的非正式调查中，我们发现即使在富有经验的研究者里，都少有人对Paxos感觉轻松。我们也挣扎于与Paxos的斗争，我们没法理解完整的协议，直到阅读了一些简化了的解释和设计我们自己的替代协议，这个过程花了差不多一年的时间。

我们假设Paxos的不透明性来自于它将单决议子集作为它的基础的选择。单决议Paxos既难懂又隐晦：

它分成两个阶段，缺乏简单直观的解释，而且没办法单独被理解。正因如此，关于为什么单决议协议能运行，很难产生直观的认知。多决议Paxos的组合规则也显著增加了复杂度和微妙之处。我们相信在多重选择上达成共识的总体问题（即一个日志而不是单个日志条目）可以被分解成更直接和明显的方式。

Paxos的第二个问题，是它没有为构建一个实际的实现提供一个好的基础。一个原因是对于多决议Paxos算法，没有达成广泛的共识。Lamport的描述主要是关于单决议Paxos的，他描绘了一些多决议Paxos可能的方法，但缺少很多细节。现在有一些充实和优化Paxos的尝试，例如[24][35]和[11]，但是它们彼此以及Lamport的描述之间都大不相同。一些系统，例如Chubby[4]实现了类Paxos（Paxos-like）的算法，但是大部分案例都没有公布它们的细节。

此外，Paxos的架构在构建实际系统时比较糟糕，这是单决议分解的另一个后果。例如，独立地选择一组日志条目，再把它们合并成一个连续的日志，并没有什么好处，这只会增加复杂度。围绕一个日志设计系统更为简单和高效，新的日志条目以强制顺序有序添加。另一个问题是Paxos在它的核心里使用了一个对称的点对点方式（虽然它最终建议一个弱领导模式作为性能优化）。在简化的世界里只有一个决策需要处理是可行的，但是少有实际系统会这么使用。如果有一系列决策需要处理，更简单和更快速的方式是选举一个领导者，并由这个领导者来协调这些决策。

结果就是，实际的系统很少与Paxos相似。每一个实现都从Paxos开始，在实现过程中发现很多困难，然后开发一个显著不同的架构。这既耗时又容易出错，并且Paxos的难以理解又进一步恶化这个问题。Paxos的阐明方式或者有利于证明它的正确性，但是实际实现与Paxos大不相同，使得这些证明没有多少价值。下面来自Chubby实现者的评论就非常典型：

在Paxos算法的描述和实际的系统需求之间存在显著的差距……最终的系统会建立在一个没有证明过的协议之上[4]

因为这些问题，我们总结出Paxos没有为系统建设或教学提供一个好基础的结论。基于一致性在大型软件系统中的重要性，我们决定看看我们能否设计一个比Paxos具备更好特性的替代一致性算法。Raft就是这个实验的结果。

4 为易于理解而设计

我们在设计Raft的时候有几个目标：它要为系统构建提供一个完整和实用的基础，因而显著减少对开发者设计工作的要求；它要在所有条件下都安全，在典型的操作场景下可用；同时它要在一般操作中足够高效。但是我们最重要的目标，也是最困难的挑战，是可理解性。它要能被大规模的受众较舒适地理解，另外，它要能构建起对这个算法直观的理解，这样系统建设者可以进行一些扩展，这在实际的实现中是不可避免的。

在设计Raft的很多地方，我们需要在不同方法中做出选择。在这些场景中，我们基于易理解性来评估可选方案：解释每一个可选方案的难度如何（例如它的状态空间有多复杂，以及它是否有晦涩难懂的暗示），以及读者完全理解这个方法和它的含意的容易程度。

我们认识到在这些分析上具备很强主观性，尽管如此，我们使用了两种普遍适用的技巧。第一个技巧是众所周知的问题分解方法：在可能的情况下，我们将问题分解成能够被解决、解释和相对独立被理解的碎片。例如在Raft中，我们拆分了领导者选举、日志复制、安全性和成员变更。

我们的第二个方法是通过减少需要考虑的状态数量来简化状态空间，使系统更清楚易懂，并尽可能地清除非确定性。具体地，日志不允许有间隔，并且Raft限制了日志之间产生不一致的方式。虽然在大部分情况我们尝试消除不确定性，但在一些场景，不确定性实际能提升易理解性。特别地，随机方法产生不确定性，但它们倾向于通过用相同的方式处理所有可能的选择，以减少状态空间（任意选择均可）。我们使用随机来简化Raft的领导者选举算法。

5 Raft一致性算法

Raft是一个管理复制日志（如第二节描述）的算法。图表2总结了这个算法的要点以供参考，图表3列举了算法的关键属性，图表中的元素在章节后面会进行分段讨论。

状态
所有服务器上的持久化状态（在响应RPC请求前更新到持久化存储中）
currentTerm	服务器感知的最新任期（Term，初始为0，单调递增）
votedFor	当前轮次投票的候选人ID（candidateId，如果没有则为null）
log[]	日志条目，每个项包含状态机的指令，以及领导者接收时的任期（初始索引为1）
所有服务器上的非持久化状态
commitIndex	已知被提交（committed）的最新日志条目的索引（初始为0，单调递增）
lastApplied	提交（applied）给状态机的最新日志的索引（初始为0，单调递增）
领导者上的非持久化状态（选举后重新初始化）
nextIndex[]	下一个发给每个服务器的日志条目的索引（初始为领导者最新日志条目索引+1）
matchIndex[]	每个服务器已同步的最新日志条目的索引（初始为0，单调递增）

AppendEntries RPC
由领导者发起，同于同步日志条目（5.3节），也用于心跳（5.2节）
参数
term	领导者任期
leaderId	跟随者可以重定向客户端
prevLogIndex	上一个日志条目索引
prevLogTerm	prevLogIndex对应日志条目的任期
leaderCommit	领导者的commitIndex参数值
结果
term	currentTerm参数值，用于领导者更新自己
success	如果跟随者包含匹配prevLogIndex和prevLogTerm的日志条目则为true
接收者实现
如果term<currentTerm，则回复false（5.1节）如果日志没有包含在prevLogIndex索引且任期匹配prevLogTerm的项，则回复false（5.3节）如果有存在的项与新项冲突（相同index但不同term），则删除已存在及其后面的项（5.3节）附加任意日志中不存在的新项如果领导者Commit>commitIndex，设置commitIndex=min(leaderCommit，最新项的index)

RequestVote RPC
由候选人发起，用于收集选票（5.2节）
参数
term	候选人任期
candidateId	发起投票的候选人
lastLogIndex	候选人最新日志条目的Index（5.4节）
lastLogTerm	候选人最新日志条目的term（5.4节）
结果
term	currentTerm参数值，用于候选人更新自己
voteGranted	true表示candidate收到了选票
接收者实现
如果term<currentTerm，则回复false（5.1节）如果votedFor参数值为null或candidateId，并且候选人的日志最起码与接收者一样新，则授予选票（5.2和5.4节）

服务器的规则
所有服务器
如果commitIndex>lastApplied：增加lastApplied，将log[lastApplied]提交给状态机（5.3节）如果RPC请求或响应包含term T > currentTerm：设置currentTerm=T，转变角色为follower（5.1节）
跟随者（5.2节）
响应来自候选人和领导者的RPC请求如果超过选举超时时间没有收到AppendEntries RPC请求（从当前领导者或授予候选人选票后）：转变角色为候选人
候选人（5.2节）
在转变为候选人，并发起选举时：增加currentTerm 为自己投票重置选举计时器发送RequestVote RPC请求给所有其他服务器如果收到大多数服务器的选票：成为领导者如果收到新领导者的AppendEntries RPC请求：转变角色为跟随者如果超过选举超时时间：发送新选举
领导者
在当选后：发送初始空AppendEntries RPC请求（心跳）给每一台服务器，固定间隔重复避免选期超时（5.2节）如果从客户端收到指令：往本地日志附加日志条目，在日志条目提交给状态机后返回响应（5.3节）如果最新的日志index大于等于跟随者的nextIndex：发送AppendEntries RPC请求，包含从nextIndex开始的日志条目如果成功：更新跟随者的nextIndex和matchIndex（5.3节）如果AppendEntries因为日志不一致失败：减少nextIndex并重试（5.3）如果存在一个N，使得N>commitIndex，多数matchIndex[i] >= N，且log[N].term == currentTerm：设置commitIndex = N（5.3和5.4节）

图表2：Raft一致性算法的要点总结（不包括成员变更和日志压缩）。

Raft 关键属性
选举安全性	至多只有一个领导者在给定任期被选举（5.2节）
领导者追加模式	领导者从来不覆盖或删除日志中的项，只追加新项（5.3节）
日志匹配	如果两个日志包含一个相同索引和任期的项，那么日志中从开始到这个给定索引的项都是相同的（5.3节）
领导者完备性	如果一个日志条目在给定任期中提交了，那么在所有高于这个任期的领导者的日志中都包含这个项（5.4节）
状态机安全性	如果一个服务器将给定索引的日志条目提交给它的状态机，不存在其他服务器会提交相同索引的不同日志条目。

图表3：Raft在任何时候都保证这些特性为真

Raft实现一致性，首先选举出一个特别的领导者，然后让这个领导者全权负责复制日志的管理。领导者从客户端接收日志条目，将它们同步到其他服务器，并在合适的时候告知这些服务器将日志条目提交合它们的状态机。拥有一个领导者可以简化复制日志的管理，例如，领导者可以不与其他服务器商议就决定日志中新条目的位置，并且数据流以一个简单的方式从领导者到其他服务器。一个领导者可能故障或与其他服务器断开连接，在这种情况一个新的领导者会被选举出来。

在这个领导者方法中，Raft将一致性问题分解成三个相对独立的子问题，并在接下来的小节进行讨论：

领导者选举：当已有领导者故障时，新的领导者必须被选择出来。（5.2节）
日志复制：领导者必须接收来自客户端的日志条目，并将它们在集群间复制，强制其他日志与它的相一致。（5.3节）
安全性：Raft的关键安全特性就是图表3中所述的状态机安全特性。如果任一服务器已经提交某个具体的日志条目到它的状态机，那么不存在其他服务器，会提交一个相同日志索引的不同指令。第5.4节描述了Raft如何保障这个特性，第5.2节描述了这个方案在选举机制上相关的一个额外限制。

在介绍了这个一致性算法后，本节还讨论可用性问题和时机在这个系统中的作用。

5.1 Raft基础

一个Raft集群包含几个服务器，典型的数量如5个，系统可以容忍2个服务器同时故障。在任意时间点，每个服务器都将是这三个状态中的其中一个：领导者（leader），跟随者（follower），或候选人（candidate）。在正常运行时，只会有一个领导者，其他所有服务器都是跟随者。跟随者被动接收消息，它们自己不会发送请求，只单纯响应来自领导者和候选人的请求。领导者处理所有客户端请求（如果客户端连接到跟随者，跟随者会将它重定向到领导者）。第三个状态（候选人）如第5.2节所述，用于选举新的领导者。图4展示了这些状态和它们的转换，接下来将讨论这些转换关系。

图4：服务器状态。跟随者只响应其他服务器的请求。如果跟随者没有收到任何通信，将转换为候选人，并发起一次选举。候选人接收到全集群多数成员的选票后转换成领导者。领导者通常持续运行直到发生故障。

Raft将时间划分为不定长度的任期，如图5所示。任期以连续的整数编号。每个任期从一次选举开始，每次有一个或多个候选人尝试成为领导者，如5.2节所述。如果一个候选人赢得选举，它将作为领导者在任期后续时间提供服务。在某些场景选举会有分歧结果，在这种情况下，任期会终结而没有领导者，一个新任期（伴随新选举）将会快速开始。Raft确保每个任期至多只有一个领导者。

图5：时间划分为任期，每个任期从一次选举开始。在成功选举后，单一领导者管理整个集群直到任期结束。一些选举会失败，这些情况下任期结束而没有领导者被选择出来。不同服务器可能在不同时间感知到任期的转换。

不同服务器可能在不同时间感知到任期之间的转换，在某些场景，一个服务器可能没感知到选举，甚至整个任期。任期在Raft中充当逻辑时钟（logical clock[12]），支持服务器检测过期的信息，例如旧的领导者。每个服务器保存当前任期序号，并随着时间递增。服务器之间通信时会交换当前任期，如果一个服务的当前任期比其他的小，那么它会更新当前任期到较大的值。如果一个候选人或领导者发现它的任期过期了，它将立刻转换状态到跟随者。如果一个服务器接收到旧任期的请求，它将拒绝这个请求。

Raft的服务器通过远程过程调用（RPC）通信，一致性算法只需要两种RPC请求。RequestVote RPC调用由候选人在选举时发起（5.2节），AppendEntries RPC请求由领导者发起，用于同步日志条目，和提供一种心跳的形式（5.3节）。如果在适当的时间没有收到响应，服务器会重试RPC请求，并且它们会并行发起RPC请求以获得最好的性能。

5.2 领导者选举

Raft使用心跳机制来触发领导者选举。当服务器启动时，它们以跟随者开始。一个服务器持续保持跟随者状态，只要它能接收到来自领导者或候选人的合理RPC请求。领导者周期性地发送心跳请求（未携带日志条目的AppendEntries RPC请求）给所有的跟随者以保持它们的授权。如果跟随者在超过一定时间（称为选举超时）没有收到任何通信，那么它假设当前没有存活的领导者，然后开始一次选举以选择新的领导者。

开始选举时，跟随者会增加它的当前任期并转换到候选人状态，然后它投票给自己，并行地发送RequestVote RPC请求给集群中的其他服务器。候选人保持当前状态直到下列事件发生：（1）它赢得了选举，（2）另外的服务器声明它是领导者，或者（3）一段时间后没有节点竞选成功。这些结果将在下面的段落分别进行讨论。

如果候选人在同一任期内获得整个集群中大多数服务器的投票，则该候选人赢得选举。在给定的任期内，每个服务器将以先到先得的方式投票给最多一个候选人（提示：第5.4节增加了对投票的额外限制）。多数性原则确保最多有一名候选人能够赢得某一特定任期的选举（图表3中的选举安全特性）。一旦候选人赢得选举，它就成为领导者。然后，它向所有其他服务器发送心跳消息，以建立其授权并防止新的选举。

在等待投票期间，候选人可能会从另一个声称是领导者的服务器接收AppendEntries RPC请求。如果领导者的任期（包含在其RPC请求中）至少与候选人的当前任期一样大，则候选人将承认领导者是合法的，并返回到跟随者状态。如果RPC请求中的任期小于候选人的当前任期，则候选人拒绝该RPC请求并继续处于候选人状态。

第三种可能的结果是候选人既不赢也不输：如果许多跟随者同时成为候选人，选票可能会被分割，因此没有候选人获得多数选票。当这种情况发生时，每个候选人将超时，并通过增加其任期和发起另一轮RequestVote RPC请求来开始新的选举。然而，如果不采取额外措施，分裂投票可能会无限期地重复下去。

Raft使用随机选举超时来确保极少分裂投票，并且可以快速解决。为了一开始就防止分裂投票，选举超时从固定的间隔随机选择（例如，150-300ms）。这将打散服务器，因此在大多数情况下，只有一个服务器会超时，它将赢得了选举，并在其他服务器超时之前发送心跳。同样的机制也用于处理分裂投票。每个候选人在选举开始时重新设置其随机选举超时，并等待该超时结束后再开始下一次选举，这降低了在新选举中再次出现分裂投票的可能性。第9.3节表明，这种方法可以快速地选出领导者。

选举是一个例子，说明可理解性如何指导我们在设计方案之间做出选择。最初我们计划使用一个排名系统：每个候选人被分配一个唯一的排名，用于在竞争候选人之间进行选择。如果一个候选人发现了另一个排名更高的候选人，它就会回到跟随者状态，这样排名更高的候选人就更容易赢得下一次选举。我们发现这种方法在可用性方面产生了微妙的问题（如果排名较高的服务器失败，排名较低的服务器可能需要超时并再次成为候选人，但如果它这样做得太快，它可能会重置选举领导者的进度）。我们对算法进行了几次调整，但每次调整后都会出现新的极端场景。最终我们得出结论，随机重试方法更明显，更容易理解。

5.3 日志复制

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

图6:日志由条目组成，条目按顺序编号。每个条目包含创建时的任期（每个框中的数字）和状态机的指令。如果条目可以安全地应用于状态机，则认为该条目已提交。

日志组织如图6所示。每个日志条目存储一个状态机指令以及领导者接收到该条目时的任期。日志条目中的任期用于检测日志之间的不一致性，并确保图表3中的一些特性。每个日志条目还有一个整数索引，用于标识其在日志中的位置。

领导者决定何时向状态机应用日志条目是安全的，这样的条目称为已提交。Raft保证提交的条目是持久的，并且最终将由所有可用的状态机执行。一旦创建条目的领导者在大多数服务器上复制了该条目（例如，图6中的条目7），日志条目就会被提交。这也会提交领导者日志中所有之前的条目，包括之前的领导者创建的条目。第5.4节讨论了在领导者更换后应用此规则时的一些微妙之处，并表明此承诺定义是安全的。领导者记录它要提交的最大索引，并将该索引包含在未来的AppendEntries RPC请求中（包括心跳），以便其他服务器最终发现。一旦跟随者了解到日志条目已提交，它将该条目应用于其本地状态机（按日志顺序）。

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

如果不同日志中的两个条目具有相同的索引和任期，则它们存储相同的指令。
如果不同日志中的两个条目具有相同的索引和任期，则所有该条目之前日志都相同。

第一个特性源于这样一个事实，即领导者在给定的期限内最多创建一个具有给定日志索引的条目，并且日志条目永远不会改变其在日志中的位置。第二个特性由AppendEntries执行的简单一致性检查保证。当发送AppendEntries RPC请求时，领导者在其日志中包含紧随新条目的索引和任期。如果跟随者在其日志中没有找到具有相同索引和任期的条目，则拒绝新条目。一致性检查作为一个归纳步骤：日志的初始空状态满足“日志匹配特性”，无论何时扩展日志，一致性检查都保持“日志匹配特性”。因此，每当AppendEntries成功返回时，领导者就知道跟随者的日志与它自己的日志到新条目为止都相同。

图7：当领导者确认后，跟随者日志中可能出现各种情况（a-f）。每个方框代表一个日志条目，方框里的数字是它的任期。跟随者可能缺少条目（a-b），可能有额外的未提交条目（c-d），或者两者都有（e-f）。例如，场景（f）可能发生的情况：如果该服务器是任期2的领导者，在其日志中添加了几个条目，然后在提交任何条目之前崩溃，它很快重新启动，成为任期3的领导者，并在其日志中添加了更多条目，在提交任期2或任期3中的任何条目之前，服务器再次崩溃，并在几个任期内保持关闭状态。

正常情况下，领导者和跟随者的日志是一致的，所以AppendEntries一致性检查不会失败。但是，领导者崩溃可能导致日志不一致（旧领导者可能没有完全复制其日志中的所有条目）。这些不一致可能会在一系列领导者和跟随者的崩溃中加剧。图7说明了跟随者的日志可能与新领导者的不同之处。跟随者可能缺少领导者上存在的条目，也可能有领导者上没有的额外条目，或者两者兼而有之。日志中缺少的和无关的条目可能跨越多个任期。

在Raft中，领导者通过强迫跟随者的日志复制自己的日志来处理不一致。这意味着跟随者日志中的冲突条目将被来自领导者日志的条目覆盖。第5.4节将说明，如果加上另外一个限制，这样做是安全的。

为了使跟随者的日志与自己的日志保持一致，领导者必须找到两个日志一致的最新日志条目，删除跟随者日志中在该点之后的所有条目，并将领导者在该点之后的所有条目发送给跟随者。所有这些操作都是对AppendEntries RPC请求执行的一致性检查的响应。领导者为每个跟随者维护一个nextIndex，这是领导者将发送给该跟随者的下一个日志条目的索引。当领导者首次掌权时，它将所有nextIndex值初始化为其日志中最后一个值之后的索引（图7中的11）。如果跟随者的日志与领导者的日志不一致，则AppendEntries一致性检查将在下一个AppendEntries RPC中失败。拒绝后，领导者减少nextIndex并重试AppendEntries RPC请求。最终nextIndex将达到领导者和跟随者日志匹配的点。当这种情况发生时，AppendEntries将成功，它将删除跟随者日志中的任何冲突条目，并从领导者日志（如果有的话）中追加条目。一旦AppendEntries成功，跟随者的日志与领导者的日志一致，并且在任期的剩余时间内保持这种状态

可以对协议进行优化，以减少拒绝的AppendEntries RPC请求数量，详见[29]。

有了这种机制，当领导者重新上线时，不需要采取任何特殊措施来恢复日志一致性。它开始正常操作，日志自动在响应AppendEntries一致性检查失败时自动收敛。领导者永远不会覆盖或删除自己日志中的条目（图表3中的领导者追加模式）。

这个日志复制机制展示了在第2节中描述的理想的共识特性：只要大多数服务器正常运行，Raft就可以接受、复制和应用新的日志条目。在正常情况下，一个新条目可以通过一轮RPC复制到集群的大多数服务器，个别慢的跟随者不会影响整体性能。

5.4 安全性

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

本节通过添加服务器可以被选为领导者的限制来完善Raft算法。该限制确保了任何给定任期的领导者包含了在之前任期中提交的所有条目（图3中的领导者完整性特性）。考虑到选举限制，我们可以制定更精确的提交规则。最后，我们给出了领导者完备性的证明概述，并展示了它如何指引复制状态机的正确行为。

5.4.1 选举限制

在任何基于领导者的一致性算法中，领导者最终必须存储所有已提交的日志条目。在一些一致性算法中，如Viewstamped Replication[20]，即使领导者最初不包含所有提交的条目，也可以被选举出来。这些算法包含额外的机制来识别缺失的条目，并将它们发送给新的领导者，要么在选举过程中或之后不久。不幸的是，这会导致相当多的额外机制和复杂性。Raft使用了一种更简单的方法，它保证从每一个新的领导者被选举的那一刻起，之前的所有已提交条目都包含在领导者上，而不需要将这些条目转移给领导者。这意味着日志条目只在一个方向上流动，从领导者到追随者，并且领导者永远不会覆盖其日志中的现有条目。

Raft使用投票过程来阻止候选人赢得选举，除非其日志包含所有已提交的条目。候选人必须与集群的大多数成员交互才能当选，这意味着每个提交的条目必须至少出现在其中一台服务器中。如果候选人日志至少与大多数日志中的任何其他日志一样新（其中“新”的定义在下面），那么它将保存所有已提交的条目。RequestVote RPC实现了这个限制：RPC包含关于候选人日志的信息，如果投票人自己的日志比候选人的日志更新，投票人就拒绝投票。Raft通过比较日志中最后条目的索引和任期来确定两个日志中哪一个是最新的。如果日志的最后条目具有不同的任期，那么具有较大任期的日志是最新的。如果日志以相同的任期结束，则哪个日志更长则更新。

5.4.2 提交之前任期项

如5.3节所述，领导者知道当前任期的条目一旦在大多数服务器上存储，就会被提交。如果领导者在提交条目之前崩溃，则未来的领导者将尝试完成该条目的复制。但是，领导者不能立即得出结论，认为前一个任期的条目一旦存储在大多数服务器上就已经提交了。图8说明了一种情况，其中旧日志条目存储在大多数服务器上，但仍然可以被未来的领导者覆盖。

图8：一个时间序列显示了为什么领导者不能使用旧任期的日志条目来决定提交。在(a)中，S1是领导者，部分复制索引2的日志条目。在(b)中S1崩溃，S5通过S3、S4和它自己的投票当选为第3任期的领导者，并在日志索引2处接受一个不同的条目。在(c)中S5崩溃，S1重新启动，被选为领导者，并继续复制。此时，任期2中的日志条目已经在大多数服务器上复制了，但还未提交。如果S1如(d)中那样崩溃，S5可以被选为领导者(来自S2、S3和S4的投票)，并用自己在任期3中的条目覆盖该条目。但是，如果S1在崩溃之前在大多数服务器上复制其当前任期的条目，如(e)所示，则该条目被提交（S5无法赢得选举）。此时，日志中前面的所有条目也提交了。

为了消除图8所示的问题，Raft不会通过计算副本数量来提交之前任期中的日志条目，只在领导者提交当前任期的日志条目时才计算副本数量。一旦以这种方式提交了当前任期中的一个条目，那么由于日志匹配属性，所有先前的条目都将间接提交。在某些情况下，领导者可以安全地得出一个较旧的日志条目已提交的结论（例如，如果该条目存储在每个服务器上），但是Raft为了简单起见采用了更保守的方法。

Raft在提交规则中引入了这种额外的复杂性，因为当领导者复制前一任期的条目时，日志条目保留其原始的任期编号。在其他一致性算法中，如果一个新的领导者复制了先前任期中的条目，它必须用新的任期编号来复制。Raft的方法可以更容易地推断日志条目，因为它们在不同的时间和日志中保持相同的任期编号。此外，Raft中的新领导者发送的日志条目比其他算法少（其他算法在提交之前必须发送冗余的日志条目来重新编号）。

5.4.3 安全参数

给定完整的Raft算法，我们现在可以更精确地论证领导者完整性成立（这个论证是基于安全性证明，参见8.2节）。我们假设领导者完整性不成立，然后我们证明了一个矛盾。
假设任期T的领导者（领导者T）提交了一个来自其任期的日志条目，但是该日志条目没有被某个未来任期的领导者存储。考虑最小的项U > T，其领导者（领导者U）不存储该条目。

图9：如果S1（任期T的领导者）从其任期提交了一个新的日志条目，并且S5被选为下一个任期U的领导者，那么必须至少有一个服务器（S3）接受该日志条目并投票给S5。

提交的条目必须在其选举时在领导者U的日志中缺失（领导者永远不会删除或覆盖条目）。
领导者T在大多数集群节点上复制该条目，领导者U收到大多数集群节点的投票。因此，至少有一个服务器（投票人）接受了来自领导者T的条目并投票给了领导者U，如图9所示。投票是达成矛盾的关键。
投票人必须在投票给领导者U之前接受领导者T提交的条目，否则它将拒绝来自领导者T的AppendEntries请求（其当前项将高于T）。
投票人在投票给领导者U时仍然存储该条目，因为每个中间的领导者都包含该条目（假设），领导者永远不会删除条目，跟随者只在与领导者冲突时删除条目。
投票人将其选票授予了领导者U，因此领导者U的日志必须与投票人的日志一样是最新的。这导致了两个矛盾之一。
首先，如果投票人和领导者U共享相同的最后一个日志条目，那么领导者U的日志必须至少和投票者的日志一样长，所以它的日志包含投票者日志中的每一个条目。这是一个矛盾，因为投票人包含提交的条目，而领导者被认为没有。
否则，领导者U的最新日志任期一定大于选票人的日志任期。而且，它大于T，因为投票人的最后一个日志条目至少是T（它包含了从项T中提交的条目）。创建了领导者U最后一个日志条目的较早的领导者必须在其日志中包含提交的条目（假设）。那么，根据日志匹配属性，领导者U的日志必须也包含提交的条目，这是一个矛盾。
这就完整了矛盾。因此，所有大于T的任期的领导者必须包含所有在T任期中提交的来自T任期的项。
日志匹配属性保证未来的领导者也将包含间接提交的条目，如图8(d)中的索引2。

给定领导者完备性，很容易证明图3中的状态机安全属性，并且所有状态机都以相同的顺序应用相同的日志条目（参见[29]）。

5.5 跟随者和候选人崩溃

到目前为止，我们关注的是领导者的失败。跟随者和候选人崩溃比领导者崩溃更容易处理，它们的处理方式是一样的。如果跟随者或候选人崩溃，那么后续发送给它的RequestVote和AppendEntries RPC将失败。Raft通过无限重试来处理这些失败，如果崩溃的服务器重新启动，那么RPC将成功完成。如果服务器在完成RPC之后但在响应之前崩溃，那么它将在重新启动后再次接收相同的RPC。Raft的RPC是幂等的，所以这不会造成伤害。例如，如果跟随者接收到一个AppendEntries请求，其中包含其日志中已经存在的日志条目，那么它将忽略新请求中的这些条目。

5.6 时间和可用性

我们对Raft的要求之一是安全性不能依赖于时间：系统不能仅仅因为某些事件发生得比预期的快或慢而产生不正确的结果。然而，可用性（系统及时响应客户机的能力）必须不可避免地依赖于时间。例如，如果消息交换花费的时间比服务器崩溃之间的一般时间长，候选人就不会坚持足够长的时间来赢得选举，没有稳定的领导者，Raft就无法运行。

领导者选举是Raft中最关键的环节。只要系统满足以下时间要求，Raft将能够选举并保持稳定的领导者:

广播时间（broadcastTime） ≪ 选举超时（electionTimeout） ≪ 平均故障间隔（MTBF）

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

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

6 集群成员变更

到目前为止，我们已经假设集群配置（参与一致性算法的服务器集）是固定的。在实践中，有时需要更改配置，例如在服务器发生故障时更换服务器或更改复制的等级。虽然这可以通过使整个集群脱机、更新配置文件、然后重新启动集群来实现，但这会使集群在切换期间不可用。此外，如果有任何手动步骤，则有操作员出错的风险。为了避免这些问题，我们决定将配置更改自动化，并将其合并到Raft一致性算法中。

图10：直接从一种配置切换到另一种配置是不安全的，因为不同的服务器会在不同的时间切换。在本例中，集群从3台服务器增长到5台。不幸的是，在某个时间点上，两个不同的领导者可以在同一任期内当选，其中一个拥有旧配置的多数集（Cold），另一个拥有新配置的多数集（Cnew）。

为了保证配置更改机制的安全性，在过渡期间不可能出现两个领导者在同一任期内当选的情况。不幸的是，服务器直接从旧配置切换到新配置的任何方法都是不安全的。一次自动切换所有服务器是不可能的，因此集群可能在转换期间分裂成两个独立的多数集（参见图10）。

为了确保安全，配置更改必须使用两阶段方法。有多种方法可以实现这两个阶段。例如，一些系统（例如，[20]）使用第一阶段禁用旧配置，因此它不能处理客户端请求，然后第二阶段启用新的配置。在Raft中，集群首先切换到我们称之为联合一致性的过渡配置，一旦联合一致性被确认，系统就会转换到新的配置。联合共识结合了新旧形态:

日志条目在两个配置中都复制到所有服务器。
任一配置中的任何服务器都可以作为领导者。
共识（关于选举和日志提交）需要新旧配置的各自的多数集。

联合一致性允许单个服务器在不同的时间在配置之间转换，而不会影响安全性。此外，联合一致性允许集群在整个配置更改期间继续为客户端请求提供服务。

图11：配置更改的时间轴。虚线表示已创建但未提交的配置项，实线表示最近提交的配置项。领导者首先在其日志中创建Cold,new配置条目，并将其提交给Cold,new（Cold的多数集和Cnew的多数集)。然后，它创建Cnew条目并将其提交给Cnew的多数集。在任何时间点上，Cold和Cnew都不可能同时独立做出决定。

集群配置使用复制日志中的特殊条目进行存储和通信，图11说明了配置更改过程。当领导者接收到将配置从Cold更改为Cnew的请求时，它将联合一致性（图中为Cold,new）的配置存储为日志条目，并使用前面描述的机制复制该条目。一旦给定的服务器将新的配置条目添加到其日志中，它就会在以后的所有决策中使用该配置（服务器总是在其日志中使用最新的配置，而不管该条目是否已提交）。这意味着领导者将使用Cold,new的规则来确定何时提交Cold,new的日志条目。如果领导者崩溃，根据获胜的候选人是否收到了Cold,new来选择一个新的领导者。无论如何，在此期间，Cnew不能做出单方面的决定。

一旦提交了Cold,new，两个服务器都不能在未经对方批准的情况下做出决定，并且领导者完备性确保只有具有Cold,new日志条目的服务器才能被选为领导者。现在，领导者可以安全地创建描述Cnew的日志条目并将其复制到集群中。同样，此配置将在看到后立即在每个服务器上生效。当在Cnew规则下提交新配置时，旧配置是不相关的，不在新配置中的服务器可以关闭。如图11所示，不存在Cold和Cnew都能做出单方面决策的情况，这保证了安全性。

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

第二个问题是集群领导者可能不是新配置的一部分。在这种情况下，领导者一旦提交了Cnew日志条目，就会退出（返回到跟随者状态）。这意味着会有一段时间（当它正在提交Cnew时），领导者正在管理一个不包括它自己的集群，它复制日志条目，但不认为自己占多数。领导者转换发生在Cnew提交时，因为这是新配置可以在集群中独立操作的第一个点（总是可以从Cnew中选择领导者）。在此之前，可能只有来自Cold的服务器可以被选为领导者。

第三个问题是被移除的服务器（不在Cnew中的服务器）可能会破坏集群。这些服务器将不会接收到心跳，因此它们将超时并开始新的选举。然后，它们将发送带有新任期的RequestVote RPC，这将导致当前的领导者恢复到追随者状态。新的领导者最终会被选举出来，但是被移除的服务器会再次超时，这个过程会重复，导致差的可用性。

为了防止这个问题，当服务器认为当前的领导者存在时，它们会忽略RequestVote RPC。具体来说，如果服务器在当前领导者交互期的最小选举超时时间内收到RequestVote RPC，则它不会更新其任期或授予其投票。这不会影响正常的选举，其中每个服务器在开始选举之前至少等待最小的选举超时。然而，它有助于避免被移除的服务器造成的中断：如果一个领导者能够将心跳传送到它的集群，那么它就不会被更大的任期所取代。

7 客户端和日志压缩

本节由于篇幅限制省略，但在本文的扩展版中有相关材料[29]。它描述了客户端如何与Raft交互，包括客户端如何查找集群领导者以及Raft如何支持线性化语义[8]。扩展版本还描述了如何使用快照方法回收复制日志中的空间。这些问题适用于所有基于共识的系统，Raft的解决方案与其他系统类似。

8 实现与评估

我们已经将Raft作为复制状态机的一部分实现，该状态机存储RAMCloud的配置信息[30]，并协助RAMCloud协调器的故障切换。Raft实现包含大约2000行C++代码，不包括测试、注释或空白行。源代码是免费提供的[21]。根据本文的草稿，目前大约有25个独立的第三方开源Raft的实现[31]处于不同的开发阶段。此外，许多公司正在部署基于Raft的系统[31]。

本节的其余部分使用三个标准来评估Raft：可理解性、正确性和性能。

8.1 可理解性

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

我们试图使Paxos和Raft之间的比较尽可能公平。实验在两个方面对Paxos有利：43名参与者中有15人报告说他们之前有过Paxos的一些经验，Paxos的视频比Raft的视频长14%。如表1所示，我们已采取措施减轻潜在的偏倚来源。我们所有的资料都可供查阅[26,28]。

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

图12：散点图比较43名参与者在Raft和Paxos测试中的表现。对角线(33)上方的点代表在Raft中得分较高的参与者。

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

我们还在测试结束后对参与者进行了调查，看看他们觉得哪种算法更容易实现或解释，这些结果如图13所示。绝大多数参与者报告说，Raft更容易实现和解释（每个问卷41个中的33个）。然而，这些自我报告的感觉可能不如参与者的测验分数可靠，参与者可能因为我们的假设（Raft更容易理解）而有偏见。关于Raft用户研究的详细讨论可参见[28]。

图13：使用5分制，参与者被问及（左）他们认为哪种算法更容易在一个有效、正确和高效的系统中实现，（右）哪种算法更容易向CS研究生解释。

正确性

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

性能

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

我们使用Raft实现来衡量Raft领导者选举算法的性能，并回答了两个问题。首先，选举过程会很快趋同吗？其次，在领导者崩溃后可以实现的最小停机时间是多少？

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

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

图14：检测和替换崩溃的领导者的时间。顶部的图改变了选举超时的随机性，底部的图缩放了最小的选举超时。每条线代表1000次试验（“150-150ms”的100次试验除外），对应于一个特定的选举超时选择，例如“150-155ms”表示选举超时是随机选择的，并且在150ms和155ms之间均匀分布。这些测量是在一个由5个服务器组成的集群上进行的，广播时间大约为15毫秒。对于包含9台服务器的集群结果类似。

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

9 相关工作

有许多与一致性算法相关的出版物，其中许多属于以下类别之一：

Lamport对Paxos的原始描述[13]，并在试图更清楚地解释它[14,18,19]。
Paxos的细化，填补缺失的细节并修改算法，为实现提供更好的基础[24,35,11]。
实现一致性算法的系统，如Chubby [2,4]，ZooKeeper[9,10]和Spanner[5]。Chubby和Spanner的算法细节尚未公布，尽管两者都声称基于Paxos。ZooKeeper的算法已经发表了更详细的内容，但它与Paxos有很大的不同。
可应用于Paxos的性能优化[16,17,3,23,1,25]。
Oki和Liskov的Viewstamped Replication (VR)，这是一种与Paxos同时开发的一致性替代方法。最初的描述[27]与分布式交易的协议交织在一起，但核心共识协议在最近的更新中被分离[20]。VR使用基于领导者的方法，这与Raft有许多相似之处。

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

像Raft一样，VR和ZooKeeper都是基于领导者的，因此与Paxos相比，具备和Raft类似的很多优势。然而，Raft的机制比VR或ZooKeeper少，因为它最小化了非领导者的功能。例如，Raft中的日志条目只向一个方向流动：从AppendEntries RPC中的领导者向外流动。在VR中，日志条目是双向流动的（领导者可以在选举过程中接收日志条目），这导致了额外的机制和复杂性。ZooKeeper的公开描述也向日志传输日志条目，但其实现显然更像Raft[32]。

Raft的消息类型比我们所知道的基于共识的日志复制的任何其他算法都要少。例如，VR和ZooKeeper各自定义了10种不同的消息类型，而Raft只有4种消息类型（两个RPC请求和它们的响应）。Raft的消息比其他算法更密集，但它们总体上更简单。此外，VR和ZooKeeper在领导者更换期间传输整个日志，将需要额外的消息类型来优化这些机制以使其实用。

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

10 结论

算法的设计通常以正确性、效率和/或简洁性为主要目标。虽然这些都是有价值的目标，但我们相信可理解性同样重要。除非开发人员将算法转化为实际实现，否则其他目标都无法实现，而实际实现将不可避免地偏离并扩展已发布的形式。除非开发人员对算法有深刻的理解，并且能够创建关于它的直觉，否则他们很难在实现中保留其理想的属性。

在本文中，我们讨论了分布式一致性的问题，其中一个被广泛接受但难以理解的算法Paxos多年来一直挑战着学生和开发人员。我们开发了一种新的算法Raft，我们已经证明它比Paxos更容易理解。

我们也相信Raft为系统构建提供了更好的基础。将可理解性作为主要设计目标改变了我们设计Raft的方式，随着设计的进展，我们发现自己重复使用了一些技术，比如分解问题和简化状态空间。这些技术不仅提高了Raft的可理解性，而且使我们更容易相信它的正确性。

引用

[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] 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.

[6] 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.

[7] GHEMAWAT, S., GOBIOFF, H., AND LEUNG, S.-T. The Google fifile system. In Proc. SOSP’03, ACM Symposium on Operating Systems Principles (2003), ACM, pp. 29–43.

[8] 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.

[9] 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.

[10] 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.

[11] KIRSCH, J., AND AMIR, Y. Paxos for system builders. Tech. Rep. CNDS-2008-2, Johns Hopkins University, 2008.

[12] LAMPORT, L. Time, clocks, and the ordering of events in a distributed system. Commununications of the ACM 21, 7 (July 1978), 558–565.

[13] LAMPORT, L. The part-time parliament. ACM Transactions on Computer Systems 16, 2 (May 1998), 133–169.

[14] LAMPORT, L. Paxos made simple. ACM SIGACT News 32, 4 (Dec. 2001), 18–25.

[15] LAMPORT, L. Specifying Systems, The TLA+ Language and Tools for Hardware and Software Engineers. AddisonWesley, 2002.

[16] LAMPORT, L. Generalized consensus and Paxos. Tech. Rep. MSR-TR-2005-33, Microsoft Research, 2005.

[17] LAMPORT, L. Fast paxos. Distributed Computing 19, 2 (2006), 79–103.

[18] 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.

[19] LAMPSON, B. W. The ABCD’s of Paxos. In Proc. PODC’01, ACM Symposium on Principles of Distributed Computing (2001), ACM, pp. 13–13.

[20] LISKOV, B., AND COWLING, J. Viewstamped replication revisited. Tech. Rep. MIT-CSAIL-TR-2012-021, MIT, July 2012.

[21] LogCabin source code. http://github.com/ logcabin/logcabin.

[22] 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.

[23] MAO, Y., JUNQUEIRA, F. P., AND MARZULLO, K. Mencius: building effificient replicated state machines for WANs. In Proc. OSDI’08, USENIX Conference on Operating Systems Design and Implementation (2008), USENIX, pp. 369–384.

[24] MAZIERES, D. Paxos made practical. http: //www.scs.stanford.edu/˜dm/home/ papers/paxos.pdf, Jan. 2007.

[25] 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.

[26] Raft user study. http://ramcloud.stanford. edu/˜ongaro/userstudy/.

[27] 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.

[28] ONGARO, D. Consensus: Bridging Theory and Practice. PhD thesis, Stanford University, 2014 (work in progress). http://ramcloud.stanford.edu/˜ongaro/ thesis.pdf.

[29] ONGARO, D., AND OUSTERHOUT, J. In search of an understandable consensus algorithm (extended version). http://ramcloud.stanford.edu/raft.pdf.

[30] 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.

[31] Raft consensus algorithm website. http://raftconsensus.github.io.

[32] REED, B. Personal communications, May 17, 2013.

[33] SCHNEIDER, F. B. Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Computing Surveys 22, 4 (Dec. 1990), 299–319.

[34] SHVACHKO, K., KUANG, H., RADIA, S., AND CHANSLER, R. The Hadoop distributed fifile system. In Proc. MSST’10, Symposium on Mass Storage Systems and Technologies (2010), IEEE Computer Society, pp. 1–10.

[35] VAN RENESSE, R. Paxos made moderately complex. Tech. rep., Cornell University, 2012.

摘要