Raft共识算法论文学习
In Search of an Understandable Consensus Algorithm(Extended Version) https://raft.github.io/
摘要 Abstract
Raft是用于管理复制日志replicated log的一致性算法。它产生的效果相当于(multi-)Paxos，它和Paxos一样有效，但它的结构与Paxos不同;这使得Raft比Paxos更容易理解，也为构建实用系统提供了更好的基础。为了提高可理解性，Raft将共识的关键要素（如领导者选举，日志复制和安全性）分解，并强制实施更强的一致性，以减少必须考虑的状态数量。用户学习的结果表明，对学生来说Raft比Paxos更容易学习。Raft还包括一种用于更改群集成员身份的新机制，该机制使用重叠多数overlapping majorities来保证安全性。
1 介绍 Introduction
一致性（共识）算法允许机器集合作为一个连贯的组，可以在其某些成员失败时仍存活下来。因此，它们在构建可靠的大型软件系统中发挥着关键作用。Paxos [15,16]在过去十年中主导了对一致性算法的讨论：大多数共识的实现都基于Paxos或受其影响，而Paxos算法已成为用于教导学生学习共识机制的主要工具。
不幸的是，Paxos很难理解，尽管有许多尝试使其更加平易近人。此外，其架构需要复杂的变化来支持实际系统。结果，系统构建者和学生都在与Paxos斗争挣扎。
在与Paxos挣扎之后，我们开始寻找一种新的共识算法，为系统构建和教育提供更好的基础。我们的方法很不寻常，因为我们的主要目标是可理解性：我们能否为实际系统定义一致性算法，并以比Paxos更容易学习的方式描述它？此外，我们希望算法能够促进对系统构建者至关重要的直觉的开发。重要的不仅仅是算法能工作，而且它的工作原理很显而易见（直觉上就容易理解）。
这项工作的结果是一个叫做Raft的一致性（共识）算法。在设计Raft时，我们应用特定技术来提高可理解性，包括分解（Raft分离领导者选举leaderelection，日志复制log replication和安全性safety）和状态空间的减少（相对于Paxos，Raft减少了非确定性程度以及服务器彼此不一致的方式）。一项针对两所大学的43名学生的用户学习情况显示，Raft比Paxos更容易理解：在学习这两种算法之后，其中33名学生能够更好地回答关于Raft的问题，而不是关于Paxos的问题。
Raft在许多方面与现有的一致性算法类似（最值得注意的是，Oki和Liskov的Viewstamped Replication [29,22]），但它有几个新颖的功能：
Strong leader：Raft使用比其它共识算法更强的领导者形式。例如，日志条目（log entries）仅从领导者流向其它服务器。这简化了复制日志（replicated log）的管理，使Raft更易于理解。
•Leader election：Raft使用随机计时器（randomizedtimers）来选举领导者。这仅在任何一致性算法已有的心跳heartbeats上添加了少量机制，却同时简单快速地解决冲突。
•Membership changes：Raft用于更改群集中服务器集的机制使用新的联合共识（jointconsensus）方法，其中两个不同配置的多数majorities在转换期间重叠。这允许群集在配置更改期间继续正常运行。
我们相信Raft优于Paxos和其他一致性算法，无论是出于教育目的还是作为项目实施的基础。它比其它算法更简单，更容易理解; 它的描述足以完全满足实际系统的需要; 它有几个开源实现，并被几家公司使用;其安全性能已经正式规定并得到证实;其效率可与其它算法相媲美。
本文的其余部分介绍了复制状态机replicated state machine问题（第2节），讨论了Paxos的优缺点（第3节），描述了我们可理解性的一般方法（第4节），提出了Raft一致性算法（第5-8节），评估Raft（第9节），并讨论相关工作（第10节）。
2 复制状态机 Replicated state machines
共识算法通常出现在复制状态机的上下文中[37]。在这种方法中，服务器集合上的状态机计算相同状态的相同副本，并且即使某些服务器关闭down也可以继续运行。复制状态机用于解决分布式系统中的各种容错问题。例如，具有单个集群领导者的大规模系统，例如GFS[8]，HDFS[38]和RAMCloud[33]，通常使用单独的复制状态机来管理领导者选举和存储配置信息，这些信息必须能够承受领导者崩溃。复制状态机的示例包括Chubby [2]和ZooKeeper[11]。
复制状态机通常使用复制日志replicated log实现，如图1所示。每个服务器都存储一个包含一系列命令的日志，其状态机按顺序执行。每个日志包含相同顺序的相同命令，因此每个状态机处理相同的命令序列。由于状态机是确定性的，因此每个都计算相同的状态和产生相同的输出序列。
保持replicated log（日志副本）的一致性是一致性算法的工作。服务器上的共识模块从客户端接收命令并将添加到其日志中。它与其他服务器上的共识模块通信，以确保每个日志最终包含相同顺序的相同请求，即使某些服务器发生故障。正确复制命令后，每个服务器的状态机按日志顺序处理它们，并将输出返回给客户端。结果，服务器似乎形成一个高度可靠的状态机。
实际系统的共识算法通常具有以下属性：
•它们确保在所有非拜占庭non-Byzantine条件下的安全性（永远不会返回错误的结果），包括网络延迟，分区和数据包丢失，重复和重新排序。
•只要大多数服务器都可以运行并且可以相互通信并与客户端通信，它们就可以完全正常运行（可用）。因此，典型的五个服务器集群可以容忍任何两个服务器的故障。假设服务器因停止而失败；他们可能稍后从稳定存储状态恢复并重新加入群集。
•它们不依赖于时间来确保日志的一致性：错误的时钟和极端的消息延迟在最坏的情况下可能导致可用性问题。
•在常见情况下，只要大多数群集响应单轮远程过程调用，命令就可以完成; 少数慢速服务器不能影响整体系统性能。
3 Paxos有什么问题？What’s wrong with Paxos?
在过去十年中，Leslie Lamport的Paxos协议[15]几乎已成为共识的同义词：它是课程中最常教授的协议，大多数共识实现都将其作为起点。Paxos首先定义了一个能够就单个决策达成一致的协议，例如单个日志副本条目。我们将此子集称为单一法令single-decree Paxos。 Paxos然后组合该协议的多个实例以促进一系列决策，例如日志（multi-Paxos）。Paxos确保安全性和活跃性，并支持群集成员资格的更改。它的正确性已被证实，并且在正常情况下它是高效的。
不幸的是，Paxos有两个明显的缺点。第一个缺点是Paxos特别难以理解。完整的解释[15]是众所周知的不透明; 很少有人能够成功地理解它，并且只有付出很大的努力。因此，有几次尝试用简单的术语解释Paxos [16,20,21]。这些解释集中在单一法令single-decree子集上，但它们仍然具有挑战性。在NSDI 2012的与会者非正式调查中，我们发现很少有人对Paxos感到满意，即使是经验丰富的研究人员。我们自己与Paxos斗争; 在阅读了几个简化的解释并设计我们自己的替代协议之前，我们无法理解完整的协议，这个过程花了将近一年的时间。
我们假设Paxos的不透明性源于其选择单一法令single-decree子集作为其基础。单一法令Paxos是密集和微妙的：它分为两个阶段，没有简单直观的解释，无法独立理解。因此，很难对单一协议的工作原理产生直观感觉。Multi-Paxos的组合规则增加了显著的额外复杂性和微妙性。我们认为，在多个决策（即日志而不是单个条目）上达成共识的整体问题可以通过更直接和明显的其它方式进行分解。
Paxos的第二个问题是它没有为构建实际系统的实现提供良好的基础。一个原因是没有广泛认可的multi-Paxos算法。Lamport的描述主要是关于单一法令single-decreePaxos; 他概述了mulit-Paxos的可能方法，但缺少许多细节。已经有多次尝试充实和优化Paxos，例如[26]，[39]和[13]，但这些尝试彼此不同并且与Lamport的草图不同。诸如Chubby [4]之类的系统已经实现了类似Paxos的算法，但在大多数情况下，他们的细节尚未发布。
此外，Paxos架构在构建实用系统方面很差; 这是单一法令single-decree分解的另一个结果。例如，单独选择一组日志条目然后将它们合并到一个顺序日志中几乎没有好处;这只会增加复杂性。围绕日志设计系统更简单，更有效，其中新条目以受约束的顺序依次附加append。另一个问题是，Paxos在其核心使用对称的点对点peer-to-peer方法（尽管它最终表明是弱形式的领导<Raft是Strongleader形式>作为性能优化）。这在简化的世界中是有意义的，其中只做出一个决定，但很少有实际系统使用这种方法。如果必须做出一系列决定，首先选举领导者，然后让领导者协调决策，这样会更简单快捷。
因此，实际系统与Paxos几乎没有相似之处。每个实现都从Paxos开始，过程中发现实现Paxos的困难，然后开发了一个显着不同的架构。这是耗时且容易出错的，理解Paxos的困难加剧了这个问题。 Paxos的公式化可能是证明其正确性的好方法，但真正的实现与Paxos有很大的不同，因此证明这没有什么价值。来自Chubby实施者的以下评论是典型的：“Paxos算法的描述与现实世界系统的需求之间存在显着差距… …最终系统将基于未经证实的协议[4]。”
由于这些问题，我们得出结论，Paxos没有为系统建设或教育提供良好的基础。鉴于在大规模软件系统中达成共识的重要性，我们决定看看我们是否可以设计一个具有比Paxos更好属性的替代一致性算法。Raft便是该实验的结果。
4设计可理解性 Designing for understandability
我们在设计Raft时有几个目标：它必须为系统构建提供完整而实用的基础，从而显着减少开发人员所需的设计工作量;它必须在所有条件下都是安全的，并且在典型的操作条件下可用;它必须对普通操作高效。但是，我们最重要的目标--- 也是最困难的挑战--- 是可理解性。大量读者必须能够舒适地理解该算法。此外，必须能够开发出对算法的直觉，以便系统构建人员能够进行在实际实现中不可避免的扩展。
在Raft的设计中有许多要点，我们不得不在其它方法中进行选择。在这些情况下，我们根据可理解性来评估备选方案：解释每个备选方案有多困难（例如，其状态空间有多复杂，是否有微妙的含义？）对于读者来说，完全理解这种方法及其含义有多容易？
我们认识到这种分析具有高度的主观性; 尽管如此，我们使用了两种通常适用的技术。第一种技术是众所周知的问题分解方法：只要有可能，我们就将问题分成可以相对独立地解决，解释和理解的单独部分。例如，在Raft中，我们将领导者选举，日志复制，安全性和成员资格更改分开。
我们的第二种方法是通过减少要考虑的状态数来简化状态空间(即有限状态机的状态数量)，使系统更加连贯并尽可能消除不确定性。具体而言，不允许日志有空洞，并且Raft限制了日志彼此不一致的方式。虽然在大多数情况下我们试图消除不确定性，但在某些情况下，非确定性实际上会提高可理解性。特别是，随机方法引入了非确定性，但它们倾向于通过以类似方式处理所有可能的选择来减少状态空间（“选择任何;它无关紧要”）。我们使用随机化来简化Raft领导者选举算法。
5 Raft共识算法 The Raft consensus algorithm
Raft是一种用于管理第2节中描述的形式的复制日志的算法。图2以浓缩形式总结了算法以供参考，图3列出了算法的关键属性;这部分内容的元素将在本节的其余部分进行分段讨论。
Raft通过首先选举一位杰出的领导者，然后让领导者完全负责管理复制的日志来实现共识。领导者接受来自客户端的日志条目，在其他服务器上复制它们，并告诉服务器何时可以安全地将日志条目应用于其状态机。拥有领导者可以简化复制日志的管理。例如，领导者可以在不咨询其他服务器的情况下决定将新条目放在日志中的哪个位置，并且数据以简单的方式从领导者流向其他服务器。领导者可能会失败或与其他服务器断开连接，在这种情况下会选出新的领导者。
鉴于领导者的方法，Raft将共识问题分解为三个相对独立的子问题，这些问题将在下面的小节中讨论：
•领导者选举：当现有领导者失败时，必须选择新的领导者（第5.2节）。
•日志复制：领导者必须接受来自客户端的日志条目并在集群中复制它们，从而强制其它日志与其自己一致（第5.3节）。
•安全性：Raft的关键安全属性是图3中的状态机安全属性：如果任何服务器已将特定日志条目应用于其状态机，则没有其它服务器可以对同一日志索引应用不同的命令。第5.4节描述了Raft如何确保这个属性;解决方案涉及对5.2节中描述的选举机制的额外限制。
图三所示内容： Raft协议保证下面每个属性始终为真
Election Safety 选举安全：一个领导人最多可以在一个任期内当选。§5.2
Leader Append-Only：领导者永远不会覆盖或删除其日志中的条目; 它只附加新条目。第5.3节
Log Matching 日志匹配：如果两个日志包含具有相同日志索引和term的条目，则日志在通过给定索引的所有条目中都是相同的。第5.3节
Leader Completeness 领导者完整性：如果在给定term中提交了日志条目，则该条目将出现在所有更高编号term的领导者日志中。第5.4节
State Machine Safety状态机安全性：如果服务器已将给定索引处的日志条目应用于其状态机，则其他服务器不会为同一索引应用不同的日志条目。§5.4.3
在介绍了一致性算法之后，本节将讨论可用性问题以及计时在系统中的作用。
5.1 Raft基础 Raft basics
Raft集群包含多个服务器; 5是典型的数字，它允许系统容忍2个出现故障。在任何给定时间，每个服务器处于以下三种状态之一：领导者leader，追随者follower或候选者candidate。在正常操作中，只有一个领导者leader，所有其他服务器都是追随者follower。追随者是被动的：他们自己不发出请求，只是简单地回应领导者和候选者的请求。领导者处理所有客户请求（如果客户联系了追随者follower，follower将其重定向到领导者）。第三个状态，候选者，用于选举第5.2节中描述的新领导者。图4显示了状态及其转换;过渡将在下面讨论。
Raft将时间划分为任意长度的terms，如图5所示，term用连续的整数编号。每个term从选举开始，其中一个或多个候选人试图成为第5.2节中描述的领导者。如果候选人赢得选举，那么它将成为此term任期其余时间的领导者。在某些情况下，选举将导致分裂投票(Split Vote)。在这种情况下，该term将以没有领导者结束; 不久将开始一个新的任期（新的选举）。Raft确保在给定的期限内最多只有一个领导者。
不同的服务器可以在不同的时间观察term之间的转换，并且在某些情况下，服务器可能不会观察到选举甚至整个term。term在Raft中充当逻辑时钟[14]，它们允许服务器检测过时的信息，例如陈旧的领导者。每个服务器都存储一个当前的term编号currentterm，该编号随着时间的推移单调递增。当服务器通信时，交换当前term;如果一个服务器的currentterm小于另一个服务器的currentterm，则它将其currentterm更新为更大的值。如果候选人或领导者发现其term已过期，则会立即恢复为追随者follower状态。如果服务器收到带有过期term号的请求，它将拒绝该请求。
Raft服务器使用远程过程调用（RPCs remote procedure calls）进行通信，基本的一致性算法仅需要两种类型的RPC。RequestVote RPCs由候选人在选举期间启动（第5.2节），并且AppendEntries RPCs 由领导者发起以复制日志条目并提供心跳heartbeat形式（第5.3节）。第7节添加了第三个RPC，用于在服务器之间传输快照。如果服务器未及时收到响应，则会重试RPC，并且它们并行发出RPC以获得最佳性能。
5.2 领导者选举Leader election
Raft使用心跳heartbeat机制来触发领导者选举。当服务器启动时，它们以关注者follower的身份开始。只要服务器从领导者leader或候选者candidate接收到有效的RPC，服务器就会保持跟随者follower状态。领导者向所有follower发送定期心跳（不带日志条目的AppendEntriesRPC）以保持其权限。如果追随者在称为选举超时的一段时间内没有收到任何通信，则它假定没有可行的领导者并开始选举以选择新的领导者。
为了开始选举，跟随者follower增加其当前term并转换到候选状态。然后它投票支持自己,并与集群中的每个其它服务器并行发出RequestVoteRPC（投票请求）。候选人candidate继续处于这种状态，直到发生以下三种情况中的一种：（a）它赢得选举，（b）另一个服务器将自己确立为领导者，或（c）一段时间过去而没有获胜者。这些结果将在下面的段落中单独讨论。
（a）如果候选者candidate在相同的term内收到来自完整集群中的大多数服务器的投票，则该候选人将赢得选举。每个服务器将按照先到先得的原则对给定term内的最多一名候选人进行投票（注意：第5.4节增加了对投票的额外限制）。多数规则确保一个候选人最多可以赢得特定任期的选举（图3中的选举安全属性）。一旦候选人赢得选举，它就会成为领导者。然后，它会向所有其他服务器发送心跳消息，以确定其权限并阻止新的选举。
（b）在等待投票时，候选人可能会从声称自己是领导者的另一台服务器收到一个AppendEntries RPC。如果领导者的term（包含在其RPC中）至少与候选人当前term一样大，那么候选人将领导者视为合法并返回到追随者状态。如果RPC中的term小于候选者的当前term，则候选者拒绝RPC并继续处于候选状态。
（c）第三种可能的结果是候选人既不赢也不输选：如果许多follower同时成为候选人，则可以分割投票，以便没有候选人获得多数票。当发生这种情况时，每个候选人将超时time out并通过增加其term启动另一轮RequestVoteRPC来开始新的选举。但是，如果不采取额外措施，分割票数split vote可能会无限期重复。 Raft使用随机选举超时randomized electiontimeouts 来确保分割投票split vote很少出现并且可以快速解决。为了首先防止分割投票splitvote，从固定间隔（例如，150-300ms）随机选择选举超时时长。这会扩展服务器spread out the servers，以便在大多数情况下只有一台服务器会超时; 它赢得了选举并在任何其它服务器超时之前发送心跳。相同的机制用于处理分割投票split vote。每个候选人candidate在选举开始时重新启动其随机选举超时，并在开始下一次选举之前等待超时; 这减少了新选举中另一次分裂投票的可能性。第9.3节表明这种方法可以迅速选出领导者。
选举是可理解性如何指导我们在设计备选方案之间做出选择的一个例子。最初我们计划使用排名系统rankingsystem：每位候选人candidate都被分配了一个唯一的排名，用于在竞争候选人之间进行选择。如果候选人发现了另一个具有更高等级rank的候选人，那么它将返回到追随者follower状态，以便更高等级的候选人candidate可以更容易地赢得下一次选举。我们发现这种方法在可用性方面产生了微妙的问题（如果排名较高的服务器出现故障，排名较低的服务器可能需要超时并再次成为候选者，但如果过早地这样做，它可能会重置选举领导者的进度）。我们对算法进行了多次调整，但在每次调整后都出现了新的角点corner情况。最后我们得出结论，随机重试方法更明显，更容易理解。
5.3日志复制 Log replication
一旦领导者当选，它就开始为客户请求提供服务。每个客户端请求都包含由复制状态机执行的命令command。领导者将命令作为新条目entry附加到其日志中，然后并行地向每个其它服务器发出AppendEntriesRPC以复制条目entry。当条目被安全地复制（并非被全部的server复制）时（如下所述），领导者将条目entry应用于其自己的状态机并将该执行的结果返回给客户端。如果follower崩溃或运行缓慢，或者网络数据包丢失，领导者将无限期地重试AppendEntriesRPC（即使它已经响应了客户端），直到所有关注者follower最终存储所有日志条目。
日志的组织如图6所示。每个日志条目都存储状态机命令以及领导者收到条目时的term编号（一个term中可能会有多个日志实体）。日志条目中的term数字用于检测日志之间的不一致，并确保图3中的某些属性。每个日志条目还有一个整数索引，用于标识其在日志中的位置。
领导者决定何时将日志条目应用于状态机是安全的; 这样的条目称为已提交committed。Raft保证提交的条目是持久的durable，并且最终将由所有可用的状态机执行。一旦创建日志条目的领导者将其复制到大多数服务器上（例如，图6中的条目7），就提交日志条目。这也会提交领导者日志中的所有前面条目，包括由前任领导者创建的条目。第5.4节讨论了在领导者变更后应用此规则时的一些细微之处，并且还表明这种承诺的定义是安全的。领导者跟踪它所知的要提交的最高索引，并在未来的AppendEntries RPC（包括心跳）中包含该索引，以便其它服务器最终找到。一旦关注者follower得知提交了日志条目，它就会将该条目应用于其本地（即follower自己的）状态机（按日志顺序）。
我们设计了Raft日志机制，以保持不同服务器上日志之间的高度一致性。这不仅简化了系统的行为并使其更具可预测性，而且是确保安全性的重要组成部分。 Raft维护以下属性，它们共同构成了图3中的LogMatching属性（Log Matching 日志匹配：如果两个日志包含具有相同日志索引和term的条目，则日志在通过给定索引的所有条目中都是相同的。第5.3节）：
•如果不同日志中的两个条目具有相同的索引index和任期term，则它们存储相同的命令。
•如果不同日志中的两个条目具有相同的索引index和任期term，则所有前面的条目中的日志都相同。
第一个属性遵循以下事实：领导者在给定term中创建最多一个具有给定日志索引的条目，并且日志条目永远不会更改它们在日志中的位置。第二个属性由AppendEntries执行的简单一致性检查保证。当发送AppendEntriesRPC时，领导者在其消息中包含紧接在新日志条目之前日志条目的索引和term。如果关注者follower在其日志中找不到具有相同索引和term的条目，则它拒绝新条目。一致性检查充当归纳步骤：日志的初始空状态满足日志匹配属性，一致性检查会在扩展日志时保留日志匹配属性。因此，只要AppendEntries成功返回，领导者就会知道跟随者的日志与其自己通过新条目的日志相同。
正常操作期间，领导者和追随者follower的日志保持一致，因此AppendEntries一致性检查永远不会失败。但是，领导者崩溃可能会使日志不一致（旧的领导者可能没有完全复制其日志中的所有条目）。这些不一致可能会导致一系列领导者和追随者崩溃。图7说明了关注者的日志可能与新领导者的日志不同的方式。跟随者可能缺少领导者中存在的条目，可能具有领导者不存在的额外条目，或两者都有。日志中缺少和无关的条目可能跨越多个term。
在Raft中，领导者通过强制关注者follower的日志复制自己的日志来处理不一致。这意味着跟随者日志中的冲突条目将被领导者日志中的条目覆盖。第5.4节将表明，当再加上一个限制时，这是安全的。
要使跟随者的日志与其自身保持一致，领导者必须找到两个日志agree的最新日志条目，在该点point之后删除跟随者日志中的所有条目，并在该点之后领导者向跟随者发送自己所有的日志条目。所有这些操作都是在响应AppendEntriesRPC执行的一致性检查时发生的。领导者为每个关注者维护一个nextIndex，这是领导者将发送给该关注者的下一个日志条目的索引。当领导者首次上台时，它会将所有nextIndex值初始化为其日志中最后一个的索引。（图7中的11）。如果跟随者的日志与领导者的日志不一致，则AppendEntries一致性检查将在下一个AppendEntriesRPC中失败。拒绝后，领导者减少nextIndex并重试AppendEntriesRPC。最终nextIndex将达到领导者和追随者日志匹配的点。发生这种情况时，AppendEntries将成功，这将删除跟随者日志中的任何冲突条目，并从领导者的日志中添加条目（如果有）。一旦AppendEntries成功，跟随者的日志与领导者的日志一致，并且在剩余的term中它将保持这种状态。
如果需要，可以优化协议以减少拒绝的AppendEntries RPC的数量。例如，当拒绝AppendEntries请求时，关注者follower的拒绝消息中可以包括冲突条目的term以及它该term存储的第一个日志索引。使用此信息，领导者可以减少nextIndex以绕过该term中的所有冲突条目;每个具有冲突条目的term都需要一个AppendEntries RPC，而不是每个条目一个RPC。在实践中，我们怀疑这种优化是必要的，因为故障不经常发生，并且不太可能存在许多不一致的条目。
使用此机制，领导者在登台时无需采取任何特殊操作来恢复日志一致性。它只是开始正常运行，并且日志会自动收敛以响应AppendEntries一致性检查的失败。领导者永远不会覆盖或删除其自己的日志中的条目（图3中的LeaderAppend-Only属性）。
此日志复制机制展示了第2节中描述的理想共识属性：只要大多数服务器启动，Raft就可以接受，复制和应用新的日志条目;在正常情况下，可以使用单轮RPC将新条目复制到群集的大部分;一个慢的追随者不会影响表现。
5.4 安全性 Safety
前面的部分描述了Raft如何选择领导者并复制日志条目。但是，到目前为止所描述的机制还不足以确保每个状态机以相同的顺序执行完全相同的命令。例如，当领导者提交多个日志条目时，跟随者可能不可用，那么它可以被选为领导者并用新的条目覆盖这些条目;结果，不同的状态机可能执行不同的命令序列。
本节通过添加对可以选择哪个服务器作为领导者的限制来完成Raft算法。该限制确保任何给定term的领导者包含先前term中提交的所有条目（图3中的领导者完整性属性）。鉴于选举限制，我们会使commit规则更加准确。最后，我们提供了Leader完整性属性的校对草图，并展示了它如何实现复制状态机的正确行为。
5.4.1 选举限制（如何投票）Election restriction
在任何基于领导者的一致性算法中，领导者最终必须存储所有提交的日志条目。在一些共识算法中，例如Viewstamped Replication [22]，即使领导者最初不包含所有提交的条目，也可以选出作为领导者。这些算法包含额外的机制来识别丢失的条目，并在选举过程中或之后不久将它们传送给新的领导者。不幸的是，这导致相当大的额外机制和复杂性。 Raft使用一种更简单的方法，它保证从选举之时起，每个新领导者都会出现之前term中的所有已提交条目，而无需将这些条目从follower发送转交给领导者。这意味着日志条目仅在一个方向上流动，从领导者到关注者，并且领导者永远不会覆盖其日志中的现有条目。
Raft使用投票过程来阻止候选人赢得选举，除非其日志包含所有已提交的条目。候选人必须联系群集的大多数才能被选举，这意味着每个committed的条目必须至少存在于其中一个服务器中。如果候选人的日志至少与该多数中的任何其它日志一样是最新的（其中“最新”定义如下），则它将保留所有已提交的条目。RequestVote RPC实现了这一限制：RPC包含有关候选人日志的信息，如果其自己的日志比候选人的日志更新，则选民拒绝其投票。
Raft通过比较日志中最后一个条目的索引index和term来确定两个日志中哪一个更新。如果日志包含具有不同term的最后一个条目，则具有较晚term的日志将更新。如果日志以相同的term结束，则更长的日志更新是更新的。
5.4.2 提交先前任期的条目 Committing entries fromprevious terms
如第5.3节所述，领导者知道一旦该日志条目存储在大多数服务器上，就会提交committed当前term中的条目。如果领导者在提交一个条目entry之前崩溃，未来的领导者将尝试完成复制这个条目entry。但是，一旦领导者存储在大多数服务器上，就无法立即得出上一个条目的提交结论( However, a leader cannot immediately conclude that anentry from a previous term is committed once it is stored on a majority ofservers.)。图8说明了旧的日志条目存储在大多数服务器上但仍可被未来的领导者覆盖的情况。
图8：显示领导者无法使用旧term 中的日志条目确定commitment的时间顺序。在（a）中S1是领导者并且部分地复制索引2处的日志条目。在（b）中S1崩溃; S5是来自S3，S4及其自身的投票的第3 term选举领导者，并且在日志索引2处接受不同的条目。在（c）中S5崩溃; S1重新启动，被选为领导者，并继续复制。此时，来自term 2的日志条目已在大多数服务器上复制，但未提交。如果S1在（d）中崩溃，则S5可以被选为领导者（具有来自S2，S3和S4的投票）并且用来自第3 term的其自己的条目覆盖该条目。但是，如果S1从其当前term复制条目在崩溃之前的大多数服务器，如（e）中，则该条目被提交（S5不能赢得选举）。此时，日志中的所有前面条目也将被提交。
为了消除类似于图8中的问题，Raft从不通过计数先前term的副本数量来提交日志条目（Raftnever commits log entries from previous terms by counting replicas.）。只通过计数副本提供领导者当前term的日志条目;一旦以这种方式提交了当前term的条目，则由于日志匹配属性而间接提交所有先前条目。在某些情况下，领导者可以安全地断定提交了较旧的日志条目（例如，如果该条目存储在每个服务器上），但Raft采用更保守的方法来简化。
Raft在提交commitment规则中引入了这种额外的复杂性，因为当领导者复制先前term中的条目时，日志条目保留其原始term编号。在其它一致性算法中，如果新领导者重新复制先前“term”中的条目，则必须使用其新的“term编号”。而Raft的方法使得推理日志条目更容易，因为它们随着时间的推移保持相同的term编号和跨越日志。此外，Raft中的新领导者从之前的term发送的日志条目少于其它算法（其它算法必须发送冗余日志条目才能在提交之前重新编号）。
5.4.3 安全性讨论 Safety argument
鉴于完整的Raft算法，我们现在可以更准确地论证领导者完整性属性（这个论点基于安全性证明;见9.2节）。我们假设领导者完整性属性不成立，那么我们证明矛盾。假设termT（leaderT）的领导者从其term提交日志条目，但该日志条目不会由未来某个term的领导者存储。考虑最小的U > T，其领导者（leaderU）不存储该条目。
1.在选举时领导者U的日志中必须没有提交的条目（领导者永远不会删除或覆盖条目）。
2. leaderT复制了大多数集群的条目，leaderU从集群的大多数人那里获得了投票。因此，至少一个服务器（“选民”）都接受了来自leaderT的条目并投票给了leaderU，如图9所示。选民是达成矛盾的关键。
3.在投票给领导者U之前，选民必须接受领导者T的committed实体;否则它会拒绝来自leaderT的AppendEntries请求（它的当前term将高于T）。
4.投票人在投票给领导者U时仍然存储该条目，因为每个介入领导者都包含该条目（假设），领导者从不删除条目，并且追随者只有在与领导者发生冲突时才删除条目。
5.选民对领导者U进行投票，因此领导者的日志必须与选民一样最新。这导致了两个矛盾中的一个。
6.首先，如果选民和领导者U共享相同的最后一个日志trem，那么leaderU的日志必须至少与选民的日志一样长，因此其日志包含选民日志中的每个条目。这是一个矛盾，因为选民包含committed的条目，并且领导者U被认为不是。
7.否则，leaderU的最后一个日志term必须大于选民的term。此外，它大于T，因为选民的最后一个日志term至少为T（它包含来自T的committed条目）。创建leaderU的最后一个日志条目的早期领导者必须在其日志中包含已提交的条目（通过假设）。然后，通过LogMatching属性，leaderU的日志还必须包含已提交的条目，这是一个矛盾。
8. 这就完成了矛盾。因此，所有大于T的term的领导者必须包含在termT中提交的termT的所有条目。
9.日志匹配属性Log Matching Property保证未来的领导者还将包含间接提交的条目，例如图8（d）中的索引2。
鉴于领导者完整性属性，我们可以证明图3中的状态机安全属性，该属性表明如果服务器已将给定索引处的日志条目应用于其状态机，则其它服务器将不会为其应用不同的日志条目和相同的索引。 在服务器将日志条目应用于其状态机时，其日志必须与领导者通过该条目的登记相同，并且必须提交该条目。现在考虑任何服务器应用给定日志索引的最低项; 日志完整性属性保证所有较高term的领导者将存储相同的日志条目，因此在以后使用该索引的服务器将应用相同的值。因此，状态机安全属性成立。
最后，Raft要求服务器以日志索引顺序应用日志条目。结合StateMachine安全属性，这意味着所有服务器将以相同的顺序将完全相同的日志条目集应用于其状态机。
5.5 追随者和候选人崩溃 Follower and candidatecrashes
在此之前，我们一直关注领导者的失败。跟随者follower和候选人candidate崩溃比领导者崩溃更容易处理，并且它们都以相同的方式处理。如果关注者或候选者崩溃，则未来发送给它的RequestVote和AppendEntriesRPC将失败。Raft通过无限期重试来处理这些失败; 如果崩溃的服务器重新启动，则RPC将成功完成。如果服务器在完成RPC但在响应之前崩溃，那么它将在重新启动后再次收到相同的RPC。Raft RPCs是幂等的，所以这不会造成任何伤害。例如，如果关注者收到包含其日志中已存在的日志条目的AppendEntries请求，则会忽略新请求中的这些条目。
5.6 时间和可用性 Timing and availability
我们对Raft的一个要求是安全性不能取决于时间timing：系统不能仅仅因为某些事件比预期更快或更慢地发生而产生不正确的结果。但是，可用性（系统及时响应客户端的能力）必然取决于时间。例如，如果消息交换所需的时间超过典型的服务器崩溃时间，则候选人将无法保持足够长的时间来赢得选举;没有稳定的领导者，Raft无法取得推进。
领导选举是Raft的一个方面，时间是最重要的。只要系统满足以下时间要求，Raft就能够选择并保持稳定的领导者：
broadcastTime << electionTimeout << MTBF
在这个不等式中，broadcastTime是服务器并行向群集中的每个服务器发送RPC并接收其响应所花费的平均时间; electionTimeout是第5.2节中描述的选举超时;和MTBF是单个服务器的平均故障间隔时间。广播时间应比选举超时少一个数量级，以便领导者能够可靠地发送保持追随者开始选举所需的心跳消息;鉴于用于选举超时的随机方法，这种不平等也使分裂投票不太可能。选举超时应比MTBF少几个数量级，以便系统稳步前进。当领导者崩溃时，系统将无法进行大致的选举超时;我们希望这只能代表整个时间的一小部分。
广播时间和MTBF是底层系统的属性，而选举超时是我们必须选择的。 Raft的RPC通常要求收件人将信息保存到稳定存储，因此广播时间可能在0.5ms到20ms之间，具体取决于存储技术。因此，选举超时可能介于10毫秒到500毫秒之间。典型的服务器MTBF是几个月或更长时间，很容易满足时序要求。
6 群集成员身份更改 Cluster membership changes
到目前为止，我们假设群集配置（参与协商一致算法的服务器集，即数量）是固定的。实际上，有时需要更改配置，例如在服务器发生故障时更换服务器或更改副本数量。虽然可以通过使整个群集脱机，更新配置文件，然后重新启动群集来完成此操作，但这会在转换期间使群集不可用。此外，如果有任何手动步骤，则存在操作员错误的风险。为了避免这些问题，我们决定自动化实现配置更改并将其合并到Raft一致性算法中。
为了使配置变更机制安全，在过渡期间必须没有任何可以让两位领导人在同一任期内当选的时间点。不幸的是，服务器直接从旧配置切换到新配置的任何方法都是不安全的。不可能一次原子地切换所有服务器，因此在转换期间集群可能会分裂成两个独立的大多数（参见图10）。
为确保安全，配置更改必须使用两阶段方法。有两种方法可以实现这两个阶段。例如，一些系统（例如，[22]）使用第一阶段来禁用旧配置，因此它不能处理客户端请求; 然后第二阶段启用新配置。在Raft中，群集首先切换到过渡配置，我们称之为联合共识joint consensus; 一旦提交了联合共识，系统就会转换到新配置。联合共识结合了新旧配置：
•日志条目将复制到两种配置中的所有服务器。
•任一配置中的任何服务器都可以作为领导者。
•协议（对于选举和进入commitment）要求新旧配置各有多个。
联合共识允许各个服务器在不同时间在配置之间进行转换，而不会影响安全性。此外，联合共识允许集群在整个配置更改期间继续为客户端请求提供服务。
使用复制日志中的特殊条目存储和传送群集配置; 图11说明了配置更改过程。当领导者收到将配置从Cold更改为Cnew的请求时，它将联合共识的配置（图中的Cold,new）存储为日志条目，并使用前面描述的机制复制该条目。一旦给定服务器将新配置条目添加到其日志中，它就会将该配置用于所有将来的决策（服务器始终在其日志中使用最新配置，无论条目是否已提交）。这意味着领导者将使用Cold,new的规则来确定何时提交Cold,new的日志条目。如果领导者崩溃，可以选择新的领导者，无论是Cold 还是 Cold,new，根据获胜候选人是否已经获得Cold,new。无论如何，Cnew在此期间不能做出单方面的决定。
一旦Cold,new被提交，Cold和Cnew都不会在未经另一方批准的情况下做出决定，并且Leader Completeness Property确保只有具有Cold,new日志条目的服务器才能被选为领导者。现在，领导者可以安全地创建描述Cnew的日志条目并将其复制到集群。同样，此配置将在看到每个服务器后立即生效。根据Cnew规则提交新配置时，旧配置无关紧要，可以关闭不在新配置中的服务器。如图11所示，Cold和 Cnew都没有时间做出单方面的决定;这保证了安全。
还有三个问题需要解决以进行重新配置：
第一个问题是新服务器最初可能不会存储任何日志条目。如果它们在此状态下添加到群集中，它们可能需要相当长的时间才能赶上，在此期间可能无法提交新的日志条目。为了避免可用性差距，Raft在配置更改之前引入了一个额外的阶段，其中新服务器作为非投票成员non-votingmembers加入集群（领导者将日志条目复制到它们，但它们不被考虑用于多数）。一旦新服务器赶上了群集的其余部分，重新配置就可以如上所述进行。
第二个问题是集群领导者可能不属于新配置。在这种情况下，领导者一旦提交了Cnew日志条目，就会退出（返回到跟随者状态）。这意味着当领导者管理不包含自身的集群时，会有一段时间（当它提交Cnew时）;它复制了日志条目，但不计入多数。当Cnew被提交时发生领导者转换，因为这是新配置可以独立操作的第一点（总是可以从Cnew中选择一个领导者）。在此之前，可能只有来自Cold的服务器才能被选为领导者。
第三个问题是删除的服务器（不在Cnew中的服务器）可能会破坏集群。这些服务器不会收到心跳，所以他们会超时并开始新的选举。然后，他们将使用新的term编号发送RequestVoteRPC，这将导致当前领导者恢复到跟随者状态。最终将选出一位新的领导者，但删除的服务器将再次超时，并且该过程将重复，导致可用性不佳。 为防止出现此问题，服务器在认为当前的领导者存在时忽略RequestVoteRPC。具体来说，如果服务器在当前领导者的最低选举超时内收到RequestVote RPC，则不会更新其trem或授予其投票权。这不会影响正常选举，其中每个服务器在开始选举之前至少等待最小选举超时。但是，它有助于避免被删除服务器的中断：如果领导者能够获得其群集的心跳，则不会被更大的term号码废弃。
7 日志压缩 Log compaction
Raft的日志在正常操作期间增长以吸收/包含更多客户端请求，但在实际系统中，它无法无限增长。随着日志变长，它占用更多空间并且需要更多时间来重放。不使用某种机制来丢弃日志中累积的过时信息，这最终会导致可用性问题。
快照是最简单的压缩方法。在快照中，整个当前系统状态将写入稳定存储上的快照，然后将丢弃到该点的整个日志。快照在Chubby和ZooKeeper中使用，本节的其余部分描述了Raft中的快照。
压缩的增量方法，例如日志清理[36]和日志结构合并树[30,5]也是可能的。它们同时对一小部分数据进行操作，因此随着时间的推移，它们可以更均匀地分散负荷。他们首先选择已经累积了许多已删除和覆盖的对象的数据区域，然后他们更紧凑地重写该区域中的活动对象并释放该区域。与快照相比，这需要显著的附加机制和复杂性，这通过始终对整个数据集进行操作来简化问题。虽然日志清理需要修改Raft，但状态机可以使用与快照相同的界面实现LSM树。
图12显示了Raft中快照的基本思想。每个服务器独立获取（做）快照，仅覆盖其日志中的已提交committed条目。大部分工作由状态机将其当前状态写入快照。 Raft还在快照中包含少量元数据：最后包含的索引是快照替换的日志中最后一个条目的索引（状态机应用的最后一个条目）号，最后一个包含这个条目的term号。保留这些以支持快照之后的第一个日志条目的AppendEntries一致性检查，因为该条目需要先前的日志索引index和term。要启用集群成员资格更改（第6节），快照还包括日志中包含最后一个包含索引的最新配置。一旦服务器完成写快照，它可能会删除最后一个包含的索引以及任何先前快照的所有日志条目。
虽然服务器通常独立拍摄快照take snapshot，但领导者必须偶尔向落后的追随者发送快照。当领导者已经丢弃了它需要发送给追随者follower的下一个日志条目时，就会发生这种情况。幸运的是，这种情况在正常运作中不太可能：跟随领导者的跟随者已经有了这个条目。但是，一个特别慢的关注者或一个加入集群的新服务器（第6节）不会。让这样的追随者了解最新的方法是让领导者通过网络向其发送快照。
领导者使用一个名为InstallSnapshot的新RPC将快照发送给远远落后的追随者;请参见图13。当关注者使用此RPC接收快照时，它必须决定如何处理其现有日志条目。通常，快照将包含收件人日志中尚未存在的新信息。在这种情况下，跟随者丢弃其整个日志;它全部被快照取代，并且可能包含与快照冲突的未提交条目。相反，如果跟随者收到描述其日志前缀的快照（由于重新传输或错误），则删除快照所涵盖的日志条目，但快照后面的条目仍然有效，必须保留。
这种快照方法背离了Raft强大的领导者（strong leader）原则，因为追随者可以在不知道领导者的情况下拍摄快照。但是，我们认为这种背离是合理的。虽然拥有领导者有助于避免在达成共识时出现相互冲突的决策，但在快照时已经达成了共识，因此没有任何决策冲突。数据仍然只是从领导者流向follower，只是追随者现在可以重新组织它们的数据。
我们考虑了一种替代的基于领导者的方法，其中只有领导者才能创建快照，然后它会将此快照发送给每个追随者。然而，这有两个缺点。首先，将快照发送给每个关注者会浪费网络带宽并减慢快照过程。每个关注者已经拥有了生成自己的快照所需的信息，服务器从本地状态生成快照通常比通过网络发送和接收快照代价更低。其次，领导者的实现将更加复杂。例如，领导者需要并行地向跟随者发送快照，并向它们复制新的日志条目，以便不阻止新的客户端请求。
还有两个问题会影响快照性能。首先，服务器必须决定何时进行快照。如果服务器过于频繁地快照，则会浪费磁盘带宽和能量; 如果它不经常快照，则可能会耗尽其存储容量，并且会增加重启期间重播日志所需的时间。一个简单的策略是在日志达到固定大小（以字节为单位）时拍摄快照。如果将此大小设置为远大于快照的预期大小，则快照的磁盘带宽开销将很小。
第二个性能问题是制作快照可能会花费大量时间，我们不希望这会延迟正常操作。解决方案是使用写时复制copy-on-write技术，以便可以接受新的更新，而不会影响正在写入的快照。例如，使用功能数据结构构建的状态机自然支持这一点。或者，操作系统的写时复制支持（例如，Linux上的fork）可用于创建整个状态机的内存中快照（我们的实现使用此方法）。
8 客户端交动 Client interaction
本节描述了客户端如何与Raft交互，包括客户端如何找到集群领导者以及Raft如何支持线性化语义linearizablesemantics[10]。这些问题适用于所有基于共识的系统，而Raft的解决方案与其它系统类似。
Raft的客户将它们的所有请求发送给领导者。当客户端首次启动时，它会连接到随机选择的服务器。如果客户端的第一选择不是领导者，那么该服务器将拒绝客户端的请求并提供有关其听到的最新领导者的信息（AppendEntries请求包括领导者的网络地址）。如果领导者崩溃，客户端请求将超时; 然后客户端再次尝试随机选择的服务器。
我们对Raft的目标是实现可线性化的语义（每个操作看起来在其调用和响应之间的某个时刻即时执行，恰好一次。但是，如前所述，Raft可以多次执行命令：例如，如果领导者在提交日志条目之后但在响应客户端之前崩溃，则客户端将使用新的领导者重试该命令，从而导致它被执行第二次。解决方案是客户端为每个命令分配唯一的序列号。然后，状态机跟踪为每个客户端处理的最新序列号以及相关的响应。如果它收到序列号已经执行的命令，它会立即响应而不重新执行请求。
无需在日志中写入任何内容即可处理只读Read-only操作。但是，如果没有其它措施，这将有返回陈旧数据的风险，因为响应请求的领导者可能已被其不知道的新领导者所取代。可线性化读取不得返回陈旧数据，并且Raft需要两个额外的预防措施来保证不使用日志。首先，领导者必须拥有关于提交条目的最新信息。领导者完整性属性LeaderCompleteness Property保证领导者拥有所有已提交的条目，但在其term开始时，它可能不知道这些条目。要找出答案，需要从其term中提交一个条目。Raft通过让每个领导者在其term开始时向日志中提交空白的无操作条目来处理此问题。其次，领导者必须在处理只读请求之前检查它是否已被废除（如果选出最近的领导者，其信息可能是陈旧的）。Raft通过让领导者在响应只读请求之前与群集的大部分交换心跳消息来处理此问题。或者，领导者可以依靠心跳机制来提供一种租赁形式[9]，但这将依赖于安全时间（它假设有限的时钟偏差）。
9 实现和评估 Implementation and evaluation
我们已经将Raft作为复制状态机的一部分实现，存储RAMCloud的配置信息[33]并协助RAMCloud协调器的故障转移。Raft的实现包含大约2000行C++代码，不包括测试，注释或空行。源代码是免费提供的[23]。根据本文的草稿，还有大约25个独立的第三方开源实现[34]，它们处于不同的开发阶段。此外，各公司正在部署基于Raft的系统[34]。本节的其余部分使用三个标准评估Raft：可理解性，正确性和性能。
9.1 可理解性 Understandability
为了测量Raft相对于Paxos的可理解性，我们在斯坦福大学的高级操作系统课程和UC伯克利的分布式计算课程中使用高年级本科生和研究生进行了实验研究。我们录制了一个关于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显示了他们的个人得分。一个paired t-test检验表明，在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 正确性 Correctness
我们已经为第5节中描述的共识机制开发了正式的规范和安全证明。形式规范[31]使用TLA+规范语言[17]使图2中总结的信息完全精确。它长约400行，并作为证明的主题。对于任何实施Raft的人来说，它本身也很有用。我们使用TLA证明系统[7]机械地证明了Log完整性。但是，此证明依赖于未经机械检查的不变量（例如，我们尚未证明规范的类型安全性）。此外，我们已经编写了一份完整的状态机安全属性的非正式证明[31]（它仅依赖于规范）并且相对精确（长约3500字）。
9.3 性能/表现 Performance
Raft的表现类似于Paxos等其他共识算法。对性能来说最重要的情况是，已建立的领导者正在复制新的日志条目。使用最少数量的消息（从领导者到集群的一半的单个往返），Raft实现了这一点。还可以进一步改善Raft的性能。例如，它可以轻松支持批处理和流水线操作请求，以实现更高的吞吐量和更低的延迟。已经在文献中提出了针对其它算法的各种优化; 其中许多可以应用于Raft，但我们将其留待未来的工作。
我们使用Raft的实现来测量Raft领导者选举算法的性能并回答两个问题。首先，选举过程是否迅速收敛？第二，领导者崩溃后可以达到的最短停机时间是多少？
为了衡量领导者选举，我们反复崩溃crashed五个服务器集群的领导者，并计算了检测崩溃并选出一位新的领导者（见图16）所需的时间。为了生成最坏情况，每个试验中的服务器具有不同的日志长度，因此一些候选者没有资格成为领导者。此外，为了促成分割投票split vote，我们的测试脚本在终止其（即领导者）进程之前触发了来自领导者的心跳RPC的同步广播（这近似于领导者在崩溃之前复制新日志条目的行为）。领导者在其心跳间隔内随机均匀地崩溃，这是所有测试的最小选举超时的一半。因此，最小可能的停机时间约为最小选举超时的一半。
图16中的顶部图表显示，选举超时中的少量随机化足以避免选举中的分裂投票。在没有随机性的情况下，由于许多分裂选票，在我们的测试中领导者选举持续时间超过10秒。添加仅5ms的随机性有显著帮助，导致中值停机时间为287ms。使用更多随机性改善了最坏情况的行为：随机性为50ms，最差完成时间（超过1000次试验）为513ms。
图16中的底部图表显示可以通过减少选举超时来减少停机时间。选举超时12-24毫秒，平均只需要35毫秒选举领导者（最长的试验耗时152毫秒）。然而，降低超出此时间点的超时违反了Raft的时间要求：领导者在其他服务器开始新的选举之前难以广播心跳。这可能会导致不必要的领导更改并降低整体系统可用性，我们建议使用保守的选举超时，例如150-300ms; 此类超时不太可能导致不必要的领导者更改，并仍将提供良好的可用性。
10 相关工作 Related work
有许多与共识算法相关的出版物，其中许多属于以下类别之一：
•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的ViewstampedReplication（VR），与Paxos同时开发的另一种达成共识的方法。原始描述[29]与分布式事务协议交织在一起，但核心共识协议在最近的更新中已经分开[22]。VR使用基于领导的方法，与Raft有许多相似之处。
Raft和Paxos之间最大的区别在于Raft的strongleadership：Raft使领导者选举作为共识协议的重要组成部分，并且它在领导者中集中尽可能多的功能。这种方法使得算法简单且更容易理解。例如，在Paxos中，领导者选举与基本共识协议正交：它仅用作性能优化，并不是实现共识所必需的。然而，这导致了额外的机制：Paxos既包括基本共识的两阶段协议，也包括领导者选举的单独机制。相比之下，Raft将领导者选举直接纳入共识算法，并将其作为共识的两个阶段中的第一阶段。这导致比Paxos更少的机制。
像Raft一样，VR和ZooKeeper都是以领导者为基础，因此与Paxos相比，Raft拥有许多优势。然而，Raft具有较少的VR或ZooKeeper机制，因为它最小化了非领导者的功能。例如，Raft中的日志条目仅在一个方向上流动：从AppendEntries RPC中的领导者向外流动。在VR日志条目中，双向流动（领导者可以在选举过程中接收日志条目）; 这导致额外的机制和复杂性。已发布的ZooKeeper描述也传输了与领导者之间的日志条目，但实现显然更像是Raft [35]。
与我们所知道的基于共识的日志复制的任何其它算法相比，Raft的消息类型更少。例如，我们计算了消息类型VR和ZooKeeper用于基本共识和成员资格更改（不包括日志压缩和客户端交互，因为它们几乎独立于算法）。VR和ZooKeeper各自定义了10种不同的消息类型，而Raft只有4种消息类型（两个RPC请求及其响应）。Raft的消息比其它算法更密集，但它们更简单。此外，VR和ZooKeeper的描述是在领导者变更期间传输整个日志;将需要其它消息类型来优化这些机制，以便它们是实用的。
Raft的strong leadership方法简化了算法，但它排除了一些性能优化。例如，EgalitarianPaxos（EPaxos）在某些条件下可以通过无领导方法获得更高的性能[27]。EPaxos利用状态机命令的可交换性。只要建议的其它命令与其同时通信，任何服务器都可以提交只有一轮通信的命令。但是，如果同时建议的命令不相互通信，则EPaxos需要进行额外的通信。因为任何服务器都可以提交命令，所以EPaxos可以平衡服务器之间的负载，并且能够在WAN设置中实现比Raft更低的延迟。但是，它为Paxos增加了显着的复杂性。
在其他工作中已经提出或实施了几种不同的集群成员变更方法，包括Lamport的原始提案[15]，VR[22]和SMART[24]。我们为Raft选择了联合共识方法，因为它利用了共识协议的其余部分，因此成员资格变更只需要很少的额外机制。Lamport的基于a-based的方法不是Raft的选择，因为它假定在没有领导者的情况下达成共识。与VR和SMART相比，Raft重新配置算法的优点是可以在不限制正常请求处理的情况下进行成员资格变更;相反，VR在配置更改期间停止所有正常处理，并且SMART对未完成请求的数量施加类似限制。Raft的方法也增加了比VR或SMART更少的机制。
11 结论 Conclusion
算法通常以正确性，效率和/或简洁性为主要目标而设计。虽然这些都是有价值的目标，但我们相信可理解性同样重要。在开发人员将算法实现之前，其它任何目标都无法实现，这将不可避免地偏离并扩展已发布的表单。除非开发人员对算法有深入的了解并且能够对其产生直觉，否则他们很难在实现中保留其理想的属性。
在本文中，我们讨论了分布式共识问题，其中一个被广泛接受但费解的算法Paxos多年来一直挑战学生和开发人员。我们开发了一种新的算法Raft，我们已经证明它比Paxos更容易理解。我们也相信Raft为系统构建提供了更好的基础。使用可理解性作为主要设计目标改变了我们完成Raft设计的方式;随着设计的进步，我们发现自己重复使用了一些技术，例如分解问题和简化状态空间。这些技术不仅提高了Raft的可理解性，而且更容易说服自己的正确性。
12 致谢 Acknowledgments
没有Ali Ghodsi，David Mazi`eres以及Berkeley的CS294-91和斯坦福大学的CS240的学生的支持，用户学习是不可能的。Scott Klemmer帮助我们设计了用户研究，Nelson Ray为我们提供了统计分析方面的建议。用户研究的Paxos幻灯片大量借用了最初由LorenzoAlvisi创建的幻灯片。特别感谢DavidMazi`eres和Ezra Hoch在Raft中发现微妙的错误。许多人对论文和用户学习材料提供了有用的反馈，包括EdBugnion，MichaelChan，HuguesEvrard，DanielGiffin，ArjunGopalan，JonHowell，VimalkumarJeyakumar，Ankita Kejriwal，Aleksandar Kracun，AmitLevy，JoelMartin，SatoshiMatsushita，OlegPesok ，DavidRamos，Robbertvan Renesse，Mendel Rosenblum，Nicolas Schiper，DeianStefan，AndrewStone，RyanStutsman，David Terei，Stephen Yang，MateiZaharia，24位匿名会议评论员（有重复），特别是我们的指导人EddieKohler。Werner Vogels在Twitter上发布了早期草稿的链接，这让Raft有了很大的曝光率。这项工作得到了Gigascale系统研究中心和Multiscale系统中心的支持，这是由MARCO和DARPA赞助的半导体研究公司计划STARnet下的六个研究中心中的两个研发中心资助的，美国国家科学基金会，编号为0963859，来自Facebook，谷歌，Mellanox，NEC，NetApp，SAP和三星。Diego Ongaro由The Junglee Corporation Stanford Graduate Fellowship提供支持。
