raft 寻找可理解的一致性算法

概要

raft是一种管理副本一致性的共识算法。它产生和（multi-）paxos相同的结果，它和paxos一样高效，但是和paxos的结构不同；这让它相比起paxos更容易理解，并且也提供了更好的特性以构建一个使用的系统。为了提高可理解性，raft分离了共识中的关键元素，比如leader选举，日志复制，以及安全，它加强了连贯性以减少必须考虑的状态数量。用户的结果表明，raft比paxos算法更容易学习，raft对于修改集群的身份也包含了新的机制，它使用重叠的大多数去保证安全

1 概要

共识算法允许机器集合如同一致的群体一样工作，它可以在一些用户失败的情况下存活下来。因此，它在大尺度的软件系统中扮演了关键的角色。paxos在过去十几年中已经主导了一致性算法的讨论：大部分一致性的实现是基于paxos或者被它影响的，Paxos已经变为了一个主要的工具去教导学生什么是一致性。

实话说，paxos有点难以理解，尽管有许多次尝试让它变得更加平易近人。此外，它的结构需要复杂的改变以支持真实的系统。因此，系统构建者和学生都对paxos感到吃力。

在我们对paxos奋斗之下，我们开始寻找一个能提能够更好的供建设系统和教学的心的共识算法。我们的方法是不同寻常的，因为我们的主要目标是可理解性：我们能定义一个真实的系统并且用一种比paxos更加简单的方法描述它吗？进一步，我们想要算法更符合直觉的开发，这对于系统构建者是很必要的。它的重要不止于算法是如何工作的，还在于它为什么能起作用。

这个工作产生的算法叫做raft。在raft的设计中，我们应用了特别的技术以增强易懂性，包括分解（raft 分开了leader选举，日志复制和安全）和状态空间的简化（相对于paxos，raft减少了非确定性程度和服务器不一致的方式）。对于俩所学校43个学生的研究表示了raft对比paxos非常容易理解：在学习了俩个算法之后，33个能回答问题的学生回答的问题中paxos的回答都是由于paxos的。

raft在很多方面和现有的共识算法相似（值得注意的是，Oki和Liskov’s Viewstamped Replication）它是它还是有几个少量新特性。

• 强leader：raft使用了相比其他共识算法更强的leader。例如，日志条目只从leader留向其他服务器。这简化了对于复制日志的管理，并且让raft更容易被理解。
• leader选举：raft使用了最饥渴选举leader。这只是为共识算法所需的心跳增加了少量的机制，同时简单而又迅速的减少了冲突。
• 身份的改变：raft用于更改集群中服务器集的机制使用了一种新的共识方法，其中俩个不同的配置在大多数的转换期间重叠。这允许集群在配置变化正常的继续执行操作。

我们相信raft比paxos和其他的共识算法更强，无论是教育意义还是基础实现上。它比其他算法更加简单更加易懂；它描述的足够完成去应对所需的真实系统；它已经有了几个实现被用在了几个公司；它的安全特性已经被定义和证明；它的比其他算法都有效。

本文的其余部分将介绍状态机问题（章节2），讨论Paxos的优势和劣势（章节3），描述我们的可理解性的一搬反复噶（章节4），提出了raft共识算法（章节5-8），评估raft（章节9）讨论相关工作（章节10）。

2 复制状态机

共识算法通常出现在复制状态机的上下文中。在这个方法中，服务集合的状态机客户端计算相同状态的相同副本，并且可以在一些服务掉线的情况下继续操作时间。副本状态机被用来处理分布式系统重多样的错误问题。例如，大型系统只有一个集群的主，比如GFS，HDFS，RAMCloud，通常使用单独的复制状态机，以管理leader选举和存储必须在主崩溃时存活的配置信息。一个关于副本状态机的例子包括了Chubby和Zookeeper。

图1： 复制状态机结构。一致性算法管理了复制日志包括了来自客户端的状态机命令。状态机处理完全相同的日志中的命令行序列，以产生相同是输出。

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

保持副本日志的一致性是共识算法的工作。服务上的一致性模块接受来自客户端的命令，并追加它到日志中。它和其他服务上的一致性模块进行交流，以确保每个日志最终以相同顺序包含了相同的请求，即便一些服务失败了。一旦命令被正确的复制，每个服务状态机按照日志顺序进行处理，输出被返回到客户端。因此，服务似乎形成了一个整体，高可用的状态机。

特定系统的共识算法通常遵循以下性质。

• 它们确保所有非拜占庭条件下的安全（从不返回错误的结果），包括网络延迟，分区和包丢失，复制和重排序。
• 它们足够使用（可用性）只要任何的大多数的服务可以和其他的服务与客户端进行共同。因此，五个服务的通常集群就可以容忍任何俩个服务的失败。通过停止假定服务失败；它们以后可能从存储状态中恢复过来并再次加入集群。
• 它们不依赖于时间来确保日志的一致性：错误的时钟和极大的消息延迟在最坏情况下导致可用性的问题。
• 通常情况下，一旦集群的大多数响应了一轮远程过程调用；少数慢速的服务器将不会影响整个系统的性能。

3 paxos有什么问题吗？

在过去的十年Leslie Lamport的paxos协议已经几乎成为了共识的同义词：它几乎最常在课堂上被教授。paxos首先定义了一个就单个协议能达成一致的决策，比如单个复制的日志条目。我们将这个子集称为但命令paxos。然后，paxos将协议的多个实例组合以促进一些列决策，如日志（multi-paxos）。paxos同时保证了安全和存活，它支持集群中角色的改变。该方法的准确性得到了验证，在一般情况下是有效的。

不幸的是，paxos有俩个明显的缺点。第一个缺点是paxos机器难以理解。完整的解释是出了名的不透明；少数的人花了大量的时间才理解它。因此，有几次尝试用更简单的属于来解释paxos。这一些解释集中在单一法令的子集上，然而这仍然是挑战。此外在NSDI2012中的与出席者的非正式调查中，我们发现少数的人对paxos满意，即使是经验丰富的研究员。直到阅读了几个简化的解释并设计了我们自己的替代协议之后，我们才能够理解完整的协议，这个过程花了将近一年的时间。

我们假设paxos的不晦涩性源于它选择单一的决策子集作为其基础。单一决策的paxos是密集而又微妙的：它划分了俩个阶段，不能被简单直觉的解释不能被独立的理解。正因如此，很难直观理解单法令协议为什么有效。multi-paxos的构成规则添加了额外的复杂度和差别。

我们相信，就多项决定达成一致性的所有问题（也就是说，一个日志而不是单个条目）可以被分解成另一种更加直接和直观的方式。paxos的第二个问题是它没有提供一个构建真实实现的好的基础。一个原因是对于multi-paxos还没有一个广泛商定的算法。Lamport描述大部分是关于单词决定的paxos；对multi-paxos只做了简单的勾画，但是一些细节丢失了。已经有了几次尝试去充实和优化paxos。但是它不同于Lamport的描绘。如Chubby这样的系统已经实现了类似paxos的算法，但是大部分的例子中细节都没有公开。

此外，paxos架构对于实际的系统构建来说是糟糕的架构；它是一个单一决策分解的后果。例如，独立地选择一组日志条目，然后将它们合并到一个顺序日志中，这样做几乎没有什么好处；这只是增加了复杂度。围绕日志设计的系统更加的简单有效，其中新的条目按约束的顺序依次追加。另一个问题是paxos采用了对等方法作为方法作为核心（尽管它最终表明弱leadership是一种性能优化）。这在简化了世界是有意义的，其中只会做出一个决定，但是很少的真实系统使用这种方法。如果必须做出一些列决定，它比首先选举领导人在让领导人进行协调更简单更快。

因此，实际的系统与paxos几乎没有相似之处。每个实现都从paxos开始，发现实现它及其困难，然后发展处一个完全不同的架构。这是耗时和易错的，并且paxos的难以理解加剧了这个问题。Paxos的公式可能是证明其正确性的一个很好的公式，但是实际的实现和paxos的协议有很大不同以至于这些证明几乎没有价值。以下是chubby实现者的经典评论。

• 在paxos算法的描述和真实的系统中存在着巨大的空缺。。。最终的系统是基于未证实的协议。

正是因为这些问题，我们推断paxos不提好的基础，无论是在构建系统还是在学习方面。考虑到共识在大型软件系统中的重要性，我们决定去看看能否我们能够设计出一种有比paxos更好的共识算法。raft就是这个经历的产物。

4 为了可理解性而设计

我们已经有了几个raft的设计目标：它必须给系统构建提供完整的使用的基础，因此它开发者所需的工作量；它必须在所有的条件下案件和在典型的操作条件下可用。但是我们最重要的目标--也是最大的挑战--易于理解。算法必须被庞大的受众轻松的理解。此外，它必须符合关于算法开发的直接，因此系统构建者可以在实际应用中进行不可避免的扩展。

raft有很多设计要点，我们需要在不同的方法中进行选择。在这个情况下我们基于可理解性来评估方案：每种选择的解释有多难（假如，它的状态空间有多复杂，它是否有晦涩的含义？），以及堵着了理解它的方法和内涵有多容易。

我们认识到在这个分析中是高度主观的；然而，我们使用俩个一般的适当技术。第一个技术是众所周知的分解问题的方法：尽可能的，我们将问题分割到几个能被解决和解释的片，相对独立的理解。例如，在raft中我们分开了leader选举，日志复制，安全和成员角色的改变。

我们的第二个方法通过减少考虑的状态来简化状态空间，尽可能的让系统更加合理排除了不确定性。具体来说，日志不允许出现空洞，raft限制了日志相互不一样的情况。算法在大多数情况下尝试消除非确定性，一些情况下的非确定性实际上提高了可理解性。在现实中，随机的方法引入了非确定性，但是它倾向于通过类似的方式处理所有可能的选择来减少状态空间（选择任何都是没有问题）。我们使用随机简化raft的leader选举算法。

5 raft共识算法

图2：raft共识算法的浓缩摘要（排除了成员修改和日志压缩）。服务的行为在左上角的盒子中，描述了一组独立和反复触发的规则。章节编号，如§5.2表示讨论特定特征的地方。正式规范更详细的描述了算法。

这些文字就是图3已经翻好了

• 选举安全：最多一个leader可以在一个任期内被选中§5.2
• leader只追加：leader从来不删除它之中的日志条目；它只追加新的条目§5.3
• log匹配：如果俩个日志包含了相同的索引和日期，那么日志在所给定的条目中是完全相同的§5.3
• leader完备：如果给定期限内提交了日志条目，那么这些条目将出现在所有更高编号下leader的日志条目下§5.4
• 状态机安全：如果服务已将给定索引处的日志条目应用于其状态机，没有其他的服务可以应用相同索引下的不同的日志条目§5.4.3

图3：raft保证了每个特性在任何时候都是正确的。转接号表明了讨论的每个属性位置

raft是一个管理章节2描述的副本日志的算法。图2简单的总结了算法以供参考，图3列出了关键的算法特性；这些数字元素将在本解其余部分逐条讨论。

raft通过首先选举指定的leader实现一致性，然后给leader完全的责任以管理日志的复制。leader接受来自客户端的日志条目，在其他服务上复制他们，当它安全的日志日志条目到其他转机时，告诉服务。拥有一个leader简化了日志复制的管理。例如，leader可以决定在日志中放置新条目的位置，而无需咨询其他服务器，数据流以一种简单的方式从leader流向其他服务器。leader可以失败或者与其他的服务分离，在这个例子中新的leader将会被选出。

给定leader方法，raft解耦了一致性问题导三个独立的子问题，这些将在下面的小节中讨论：

• leader选举：当已经存在leader故障时，新的leader必须被选出（章节5.2）
• 日志迁移：leader必须接受来自客户端的日志条目并且在整个集群中复制它，让其他的日志接受自己的（章节5.3）
• 安全：raft的关键的安全特性是图3中的状态机特性：如果任何的服务应用了特定的日志条目到它们的状态机中，那么没有其他服务会在相同的日志索引中应用不同的条目。章节5.4描述了raft如何保证这个特性；该方案涉及了对5.2节中描述的选举机制的额外限制。

在提出公式算法后，这一章讨论可用性问题和系统中的时间规则。

5.1 raft基础

图4：服务状态，follower只响应来自其他服务的请求。如果follower接受不到连接，它将会变为candidate并开始选举。candidate接受了来自及群众大多数的选票后将会变为新leader。leader通常一直工作直到失败。

raft集群包括了几个服务；5是一个特殊的数字，它允许系统容错俩个失败。在任何给定的时间，系统的每个服务都处于三种状态之一：leader，follower，candidate。在通常的操作中只会存在一个leader，其他的所有服务都是follower。follower是被动的：它们自己不发出请求，但是简单的回应来自leader和candidate的请求。leader处理所有客户端请求（如果客户端包括了follower，follower会将其重定向到leader）。第三种状态candidate，它被用来选择新的leader就如章节5.2中图4展示的状态和它的转换，下面将讨论这些转换。

图5：时间被分为几个任期，每个任期伴随着选举开始。在成功的选举后，单个leader管理集群直到任期结束。一些选举失败，在这种情况下没有选出领导人。在不同的服务器上，可以在不同的时间观察到不同任期之间的转换。

raft划分了时间到任意长度的任期中，如图5所示。任期被用连续的证书编号。每个任期从选举开始，一个或多个选举人试图成为leader如5.2章描述。如果候选者赢得了选举，然后在剩下的任期内会担任领导人。在一些情况下选举将导致分裂投票。在这个情况下，任期结束时，将会没有领导人；一个新任期（伴随着新选举）将会马上开始。raft确保在给定的任期中最多有一个leader。

不同的服务可能在不同时间观察到任期之间的转换，在一些情况下，服务器可能不会观察到选举甚至整个任期。raft中任期就像一个逻辑时钟，它允许服务探测淘汰的数据，如过时的leader。每个服务存储当前任期的数字，它们会随着时间自动增长。每当服务通信时，都会交换当前任期；如果一个服务当前任期比其他服务更短，那么它更新当前的任期为那个更大的值。如果candidate或者leader发现自己的任期已经过去了，它立刻回复到follower状态。如果服务接受到旧的任期号请求，它将拒绝该请求。

raft服务交流使用远程过程调用（RPC），基础的共识算法只需要俩中类型的RPC。RequestVote RPC由candidates在选举期间发起（章节5.2），AppendEntries RPC由leader发起以日志日志条目和提供心跳（章节5.3）。章节7添加了第三种RPC以传输不同服务之间的快照。如果没有收到响应他们会及时重新发起RPC，它们并行发布RPC以获得最好的性能。

5.2leader 选举

raft使用了心跳机制以触发leader选举。一旦服务启动，它们就会变为followers的身份开始。只要它接收到了来自leader或者candidate的有效RPC请求，那么这个服务保持follower状态。leader发送周期心跳（AppendEntries RPC不携带日志条目）到所有的follower以维护它的授权。如果follower在整个选举超时时间内没有收到任何通信，那么它假设没有可行的leader并开始选举新的leader。

为了开始选举，follower增加当前的任期并且转换到candidate状态。之后它投自己一票并且并行发出RequestVote RPC到每个集群中的其他服务。candidate继续处于此状态，知道三件事情发生（a）它赢下了选举（b）另一个服务将自己视作leader（c）一段时间过去了，没有赢家。这些结果将在下文各段分别讨论。

如果在相同的任期中接受到了整个集群中大部分服务的投票，那么candidate赢得了选举。每个服务在给定的任期内最多投票一次给指定的后选人，基于先到先得（注:第5.4条增加了对投票的额外限制）。一旦candidate赢得了选举，它将成为leader。然后他发送信息到所有的其他服务以确定它的权利并且防止新的任期。

在等待投票时，candidate可以接受来自其他服务的AppendEntries RPC声称是leader。如果leader的任期（包括在其RPC中）只少与candidate当前的任期一样长，那么candidate承认leader是合法的并且回到follower状态。如果RPC中的任期小于candidate当前的任期，那么candidate拒绝RPC继续处于候选状态。

第三种可能的结果是candidate不赢也不输：如果一些追随者同时成为后选人，选票可能被分割，导致没有candidate获得多数。当它发生了，每个candidate将会超时并通过增加人气开始新的选举启动另一轮RequestVote RPC。然而，如果不采取额外措施，分裂投票会无限期的重复。

raft使用了随机选举超时以确保分裂投票非常少见并且会被快速的解决。为了放置选票分裂，选举超时从固定间隔中随机选择（eg 150-300ms）。它分散了服务因此，在大部分的时间只有一个server会超时；它赢得了选举在任何服务器超时之前发送心跳。每个candidate在选举开始时重新启动随机选举超时，在开始下一次选举之前，它等待这个暂停过去；这降低了新选举中再次出现分裂投票的可能性。章节9.3展示了这种方法可以迅速选出领导人。

选举解释了如何易懂的指导我们如何在设计方案中做出选择。开始我们计划使用排名系统：每个candidate被设计为一个独立的排名。如果candidate发现另一个candidate的排名更高，他讲返回follwer状态因此，更高排名的candidate将会更容易的赢下选举。我们发现这种方法在可用性方面产生了微妙的问题（如果排名比较高的服务器失败，排名较低的服务器可能需要超时并再次成为候选服务器，但是如果它做的太块，它可以重置选举领导人的进程）。我们对算法做了几次调整，但是每次调整后都会出现新的极端情况。最终，我们得到了结论，随机重试方法更直观和易于理解。

5.3 日志复制

一旦一个leader当选，它就开始服务于客户端请求。每个客户端请求包含一个要被复制状态机执行的命令。leader将该命令作为日志条目追加到其日志中，然后并行的发送AppendEntries RPC给每一个其他的服务以复制条目。一旦条目已经被安全的复制了（如下面所属），leader应用日志到它的状态机并且返回它的执行结果给客户端。如果follower崩溃或者运行过慢或者网络包丢失了，leader无限期的重新尝试AppendEntries RPC（即便它已经响应给客户端了）知道所有的follower最终存储了所有的日志条目。

图6：日志由条目组成，是按顺序的编号。每个条目包含了它创建时的任期和（每个盒子中的编号)和状态机的命令。如果该条目应用于状态机是安全的，则认为该条目已提交。

日志的组织如图6所示。当条目被leader接受时，每一个日志条目沿着任期存储了状态机命令。日志条目中的任期数字用来探测日志之间的不一致，以确保图3中的一些特性。每个日志条目也有证书索引辨认它在日志中的位置。

当它安全的利用日志条目到状态机，leader做出决策；这样的条目被称作committed（已提交）。raft、保证了已提交的日志条目是可靠的，最终将被所有可用的状态机执行。一旦leader它创建的条目已经被大多数服务复制，那么日志条目就是已提交的。这也会提交全部先前的leader日志中的条目，包括被之前leader创建的条目。第5.4章展示了当在leader改变之后应用这个规则时的微妙之处，这也表明了这种提交的定义是安全的。leader保持它知道的要提交的最高索引的轨迹，并且包括了它在将来AppendEntries RPC中的索引（包括心跳），因此其他服务最终会发现他。一旦follower知道日志已经被提交，它应用条目到它的本地状态机（按照日志的顺序）。

我们设计了raft日志机制以在日志和不同服务之间维护高水平的连接。不仅简化了系统的行为和让它更可预测，它也是保证安全的重要组件。raft维护了以下特征，它们共同构成了日志匹配属性，如图3：

• 如果俩个条目在不同的日志中有相同的索引和任期，那么它们存储了相同的命令。
• 如果俩个条目在不同的日志中有相同的索引和任期，那么前面所有条目的日志都相同。

第一个特征遵循一个事实，在给定任期的给定日志索引下，leader最多创建一个条目，并且日志条目从不改变它们在日志中的位置。第二个特征是使用AppendEntries执行简单的一致性检查来保证的。当发出AppendEntriesRPC，leader包含了紧接在新条目之前的它日志中条目的索引和任期。如果follower不能找到日志中相同索引和任期的条目，那么拒绝新的条目。一致性检查作为一个归纳步骤：日志初始的空状态满足日志的状态机属性，一致性检查在每当日志扩展时保证了日志匹配属性。因此，每当AppendEntries返回成功，leader通过新条目知道了follower日志和它拥有的日志完全相同。

图7：当leader掌权时，可能出现（a-f）的任何一种情况，可能发生在follower日志中。每个盒子代表一个日志条目；盒子中的数字是任期。follower可能遗失（a-b）条目，可能有额外未提交的条目（c-d），或者俩者都有（e-f）。例如，如果该服务器是term2的leader，则可能发生场景（f），在它的日志中添加了几个条目，然后在提交任何一个之前崩溃。如果重启很快，成为第三任期的领导者，并且在它的日志中添加了更多新的条目；在任何在第2项或第3项的任何条目提交之前， 服务再次崩溃并且在几个任期内一直下线。

在一般操作中，leader的日志和follower保持一致，所以AppendEntries一致性检查永远不会失败。然而，leader的崩溃可能导致日志不一致（旧的leader可能没有复制它日志中的所有条目）。这些不一致可能会在一系列领导者和追随者的崩溃中加剧。图7描述了follower的日志可能不同于新leader的情况。跟随者可能丢失了出现在leader上的条目，它可能有leader上不存在的额外条目，或者俩者都有。日志中丢失和外来的条目可能跨越多个任期。

在raft中，leader通过强迫follower的日志复制成自己的日志来处理不一致。这意味着follower日志中冲突的条目，将会被leader中的条目复写。章节5.4将会展示如果加上另一个限制，这样做是安全的。

为了让追随者的日志和自己的一致，leader必须在俩个日志一致的地方找到最近的日志条目，删除任何在那个之后的在follower中的日志条目，并且发送follower所有在那个点之后的的leader的条目。所有的这些操作都是对AppendEntries RPC执行一致性检查的响应。leader为每一个follower维护下一个索引（nextIndex），这是leader发送给follower的下一个日志的索引。当一个leader掌权时，它将所有nextIndex的值初始化为日志最后一个值之后的索引（图7中的11）。如果follower的日志和leader的日志不一致，AppendEntries 一致性检查将会在下一次AppendEntries RPC失败。被拒绝后，leader减少nextIndex并重试AppendEntries RPC。最终nextIndex将会达到那个leader和follower匹配的那个点。当它发生了AppendEntries就成功了，它删除follower中任何冲突的条目，并且从leader的日志中添加条目（如果有的话）。一旦AppendEntries成功，follower的日志就和leader一致了，并且且会在剩下的任期都保持这样。

如果需要协议可以被优化以减少AppendEntries RPC的数量。例如，当拒绝了AppendEntries请求，follower可以包含冲突项的日期，它存储的第一个索引是这一项。有了这些信息，leader可以增加下一个索引以绕过任期中所有的冲突；每个有冲突的条目的任期都需要一个AppendEntries RPC，而不是每个条目一个RPC。现实中我们怀疑这种优化是否有必要，因为失败很少发生，并且不太可能有太多不一致的条目。

随着这种机制，leader在当选时不需要进行任何特殊的操作去维护日志一致性。它只需要开始普通的操作，当AppendEntries一致性检查失败时，日志自动收敛。leader从不重写或者删除它自己所持有的日志。（leader只追加的数学如图3所示）。

日志复制机制展示了合适的一致性属性，如章节2所描述的：一旦大多数服务正常运行raft可以接受复制和使用新的日志条目；在正常情况下，新的项可以通过一轮RPC复制到大多数集群；并且少数较慢的follower将不会影响性能。

5.4安全

之前的章节描述了raft如何选举和进行日志条目复制。然而，被描述的机制目前不足以确保每个状态机执行精确的相同顺序的相同命令。例如，一个follower可能在leader提交几个日志条目时变得不可用，那么它可能被选举为leader并且用新的条目覆盖这些条目；这导致了，不同的状态机可能执行不同的命令序列。

这一章完整的raft算法通过在这些可能被选举为leader的服务上添加限制。这个限制保证了leader对于任何给定的任期包含了所有的在上一个任期已经提交的条目（leader的完整特性在图3中）。考虑到选举的限制，我们指定更精确的提交规则。最终，我们提出了leader完整特性的证明概述，并且展示了它是如何领导复制状态机中的正确行为的。

5.4.1 选举限制

在任何基于leader的学习共识算法中leader必须最终存储所有的被提交的日志条目。在一些共识算法中，如Viewstamped Replication，leader可以被选举，即便它没有维护任何的提交的条目。在个算法包含了额外的机制去定义丢失的条目并且传输他们到新的leader，要么在选举过程中要么在选举之后。不幸的是，这导致了相当多的额外机制和复杂性，raft使用简单的方法保证所有之前任期被提交的日志会存在于每个新的leader在当选那一刻起，不需要传输这些条目到leader，并且leader从不重写已经存在的在它日志中的条目。

raft使用投票程序以防止后选人赢得选举，除非其日志包含所有已提交的条目。candidate为了选举必须包含大多数的集群中的日志，这意味着，每个提交的条目必须在最少一个节点中存在。如果candidate的日志最少和其他的大多数日志一样是最新的（下面会定义最新的定义），然后它将保存所有提交的条目。RequestVote RPC实现了约束：RPC包含有关candidate的日志的信息，如果它自己的日志比候选的日志更新，投票者拒绝投票给它。

raft通过比较最后一个日志中条目的index和任期来确定俩个日志哪一个是最新的。如果最后的日志有不同的任期，那么最后一个任期的日志更新一些。如果日志结尾是相同的任期，那么那个日志越长，那个日志就越新。

5.4.2 提交之前任期的日志

图8：时间序列展示了为什么leader不能使用旧的任期的日志条目确定提交结果。在（a）中S1是leader部分复制索引2中的日志条目。在（b）中S1故障了；S5是在任期中被S3，S4和它本身投票后选举出来的leader，在日志索引2出接受不同的条目。在（c）S5异常时；S1重启了，被选举为leader，并且继续复制。在这个点，来自第二任期的日志条目已经被复制到了大部分的服务上，但是它并没有被提交。如果S1和（d）一样崩溃了，S5将会被选举为新的leader（被S2，S3，S4投票）并且使用第三任期的条目覆盖自己持有的条目。但是，如果S1崩溃之前在大多服务器上复制当前任期的条目，如（e）所示，那么这个条目将会被提交（S5不能赢得选举)。在这个点所有的之前日志中的的条目是也会被提交。

如同5.3章的描述，leader知道当前期限的条目一旦在大多数节点上被存储，就会被提交。如果leader在提交之前崩溃，则未来的leader将会尝试完成该条目的复制。然而，leader不能立即断定那个条目是来自之前任期已经被提交过一次的，而且被存储在大多数服务中了。如8所示了一种情况，其中老的日志条目被存储在大部分的服务上，但仍然可以被未来的leader取代。

简单来说，不能直接提交上一轮的日志，而是和下一个日志一起提交，这样就能保证已经被大多数提交的日志永远不会被新leader擦除。因为新提交的日志已经有了更大的任期。不会产生一致性问题。

为了消除图8中展示的问题，raft从来不会通过计算副本来提交前一个任期的日志记录。只提交leader单签任期内的日志条目；一旦来自当前任期的条目被以这种方式提交，那么所有之前的条目都会被间接的提交，因为日志匹配属性。在某些情况下，leader可以安全的得出一个日志教旧的日志已经提交的结论（例如，如果日志被存储在每一个服务中），但是raft为了简单使用了更保守的方法。

当leader复制来自上一个任期的条目时，raft导致了在提交规则上额外的复杂度，因为日志条目保留原始的任期编号。在其他复制算法中，如果新的leader重新复制先前任期的条目，它必须用新的term number这样做。raft的方法使得对日志条目的推理更加容易，因此它在不同的时间和日志中保持相同的任期。此外，raft中新leader发送以前任期的日志条目比其他算法少（其他算法必须在它们能被提交之前，发送冗余的日志条目去再编号他们。）

5.4.3 安全论证

给定完整的raft算法，我们现在可以更加精确的论证leader完备性成立（这个轮着是基于安全证明，简9.2章）。我们假设leader的完整性特性不成立，那么我们证明一个矛盾。假设任期T的leader（leaderT）提交了一个来自其任期的条目，但是该日志条目不是由某个未来任期的leader存储的。考虑到最小的任期U>T，leader（leaderU）不存储该条目。

图9：如果S1（任期T的leader）提交了来自它任期的新的日志记录，S5是被宣威任期U之后的leader，那么它必须只少有一个服务S3接受日志条目并投票给S5。

1. 已经提交的条目必须在leader的日志中缺席（leader 不能删除或者重写日志）。
2. leaderT复制了在大多数集群上的条目，并且leaderU收到了来自大多数集群的投票。因此，只少一个服务（“票”）同时接受LeaderT和来自LeaderU的投票，如图9所示。投票者是达成矛盾的关键。
3. 投票者在投leaderU之前，已经接受了已提交的来自leaderT日志条目；否则它将拒绝来自leaderT的AppendEntries请求（当当前任期将会比T高）。
4. 当它投票给leaderU时，投票者仍然存储了条目，因此所有的leader包含了条目（根据假设），leader从不删除条目，follower只删除和leader冲突的条目。
5. 投票者因为投给了leaderU，所以leaderU的日志必须和投票者的一样新。这导致了俩个矛盾之一。
6. 首先，如果投票者和leaderU分享相同最后日志任期，那么leaderU的日志必须必须和投票者一样长，所以它的日志包含了每个投票者的日志。这是一个矛盾，因为投票者包含了已提交的日志，但是leaderU被认为没有。
7. 否则，leaderU最后的日志任期一定大于投票者。此外，它必T更大，因为投票者最后日志任期只少为T（它包括了任期T中已提交的日志）。更早的leader创建了leaderU的最后日志条目必须包含了在那个leader中已经提交的日志（根据假设）。那么，通过日志匹配特性，leaderU的日志必须也包含已被提交的日志，这是矛盾的。
8. 这就解决了矛盾。因此所有大于T的任期必须包含所有的来自T任期中提交的来自T的任期。
9. 日志匹配机制特性奥正了未来的leader将会也包含被间接提交的日期，比如图8d中的索引2

有了leader完备的特性，我们可以证明来自图3的状态机的安全特性，它指出，如果服务已将给定索引出的日志条目用于状态机，没有其他服务将会能应用不同的日志条目到它的状态机上，它的日志必须是与该条目的leader的日志相同，并且该条目必须被提交。现在考虑服务器应用给定日志索引的最低期限；日志完整性属性保证了所有更高任期的leader将会被存储到相同的日志条目中，所以在之后的任期中应用了索引的服务器将应用相同的值。因此状态机安全特征被保证了。

最后raft需要服务应用日志索引顺序中的条目。结合状态机的安全特性，这意味着所有的服务将应用完全相同的日志条目集合以相同的顺序到他们的状态机中。

5.5 follower和candidate崩溃

到目前为止我们关注的是leader的失败，follwer和candidate失败是更易于处理的相比于leader崩溃，它们的处理方式是一样的。如果follwer或者candidate崩溃了，未来的RequestVote和AppendEntriesRPC将会发送失败。raft通过无限期的重试，处理这些失败；如果崩溃的服务重启了，RPC将会请求将会被成功完成。如果服务在完成RPC但是在响应之前失败了，那么他将在重新启动后接收到相同的RPC。raft的RPC是幂等的所以不会造成问题。例如，如果一个follower接受了包括已存在于其日志条目中的AppendEntries请求，它在新的请求中忽略这个条目。

5.6 时间和可用性

我们对于raft的其中一个需求是安全不需要以来时间：系统不能因为一些事件的发生更快或者更慢产生不一致的结果。然而，可用性（系统即时响应客户端的能力）必须不可避免的依赖时间。例如，如果消息交换花费的时间比服务器崩溃时的时间还长，leader就不会坚持足够长的时间来选举；没有稳定的leader，raft就无法前进。

leader选举是raft的一个方面，其中时间是非常关键的。raft能够选举和保持平稳的leader，只要系统满足一下的时间条件：

$$ 广播时间\ll 选举时间\ll 平均故障间隔时间（MTBF） $$

在这个不等式中，广播时间是它想一个服务器并行地向集群中每个服务器发送RPC并接受他们的响应的平均时间；electionTimeout是选举超时时间在5.2章中描述；MTBF是单个机器的平均故障隔离时间。广播时间应该比选举超时时间少一个数量级，因此leader可以可靠的发送心跳信息来阻止follower开始选举；给定用于选举超时的随机方法，它们的不同也导致了分裂投票不太可能。选举超时将会比MTBF少几个数量级，因此系统能够平稳进行。当leader崩溃了，系统将会不可用持续到大约选举超时的时间；我们希望这只是代表时间的一小部分。

广播时间和MTBF是底层系统的特性，其中选举超时是我们必须选择的。raft的RPC通常需要接受方持久化信息到稳态的存储中，所以广播时间可能在0.5ms-20ms之间，依赖于存储逻辑。这导致了，选举超时时间可以在10ms-500ms之间。典型的MTBF是几个月或者更长时间，这很容易满足需求。

6 集群成员身份变化

到目前为止，我们已经假设了集群的配置（参与共识算法的一组服务）是固定的。事实上，需要偶尔改动配置，例如当一个服务失败了或者去修改复制程度。虽然这可以通过让整个集群脱机，修改配置文件，然后重启服务来实现，这会让集群在修改结束之前不可用。此外，如果有任何手动的步骤，则操作员有出错的风险。为了避免这个问题，我们决定自动配置修改并且合并他们到raft共识算法中。

为了配置改变机制的安全，在过渡期间，任何时候都不应该可能选举出两位leader担任同一任期。不幸的是，任何服务器直接从老配置切换到新配置的方法都是不安全的。一起自动切换所有的服务是不可能的，所以集群可能在过渡期间切换成俩个独立的集群（见图10）

图10：直接的从一个配置切换到另一个配置是不安全的，因为不同的服务有不同的切换时间。在这个例子中，集群从3增长到5.不幸的是，在这个点俩个不同的leader可以在同一个任期内被选出，一个具有大多数的旧配置，另一个具有大多数的新配置。

为了保证安全，配置修改必须使用俩阶段方法。有多重方法实现俩阶段。比如，一些系统使用第一阶段以禁用老的配置所以不能处理客户端请求；然后第二阶段启用新的配置。在raft中集群首先切换到过渡配置我们叫他联合共识joint consensus；一旦联合共识被提交了，然后系统就变换到新的配置。联合共识结合了新老配置。

• 日志条目被复制到了俩种配置中的所有的服务。
• 任意来自俩个配置都可以作为leader
• 协议（对于选举和条目提交）要求新旧配置都获得多数

联合共识允许独立的服务在不同时间的配置之间进行变换，而不牺牲安全性。而且，联合共识允许在配置修改时集群继续服务客户端请求。

图11：配置修改的时间线。虚线展示了已经被创建但是没有被提交的配置条目，实线展示了最后被提交的配置条目。leader首先在它的日志中创建了$C_{old,new}$配置条目，并且提交给$C_{old,new}$（$C_{old}的大多数和C_{new}的大多数$)。然后它创建$C_{new}$条目并且把他提交到$C{new}$大多数。在任何时间点上，$C_{old}$和$C{new}$都不可能同时独立做出决定。

集群配置使用复制日志中的特殊条目进行存储和通信；如图11描述了配置修改过程。当leader接受请求将配置从Cold修改到Cnew时，它存储了联合共识的配置（在图中的Cold,new ）作为日志条目，并且使用上文描述的机制复制条目。一旦有服务器添加了新的配置条目到它的日志中，它使用这个配置应对将来的所有决策（服务总是使用在其日志中最后的配置，不管条目是否被提交）。这意味着leader将使用Cold,new去确定何时提交Cold,new的日志条目。如果leader崩溃了，新的leader也许会在Cold或者Cold,new，取决于获胜的candidate是否收到了Cold,new。无论如何，在此期间Cnew不能做出单方面的决定。

一旦Cold,new已经被提交了，无论是Cold还是Cnew都帮你在对方没有同意的情况下做出决定，并且leader完备特性确保了只有具有Cold,new日志条目的服务器可以被选举为leader。（拒绝比自己日志记录小的拉票）。现在leader创建日志条目表示Cnew和复制它到集群中是安全的。同样，这个配置在被每个服务器看到后会立马生效。当新的配置已经被提交到Cnew的规则下，旧的配置是不相关的，不在新配置中的服务器可以被关闭。如图11所示，Cold和Cnew不可能单方面做出决定。这保证了安全。

重新配置还要三个问题需要解决。第一个问题是新的服务可能没有存储任何日志条目。如果他们在这个状态下被添加到集群，它们可能需要相当一段时间才能赶上，在这段时间中他可能不能提交新的日志条目。为了避免可用性缺口，raft在配置修改前引入了额外的阶段，新服务器做评委无投票成员加入集群（leader复制日志条目到它们，但是它们不被试做大多数）。一旦新的服务赶上了其余的集群，可以执行如上文描述的重配置。

第二个问题是集群leader可能不是新配置的一部分。（想把一个机器下线，但是这个机器恰好是leader）在这个例子中，leader一旦提交了Cnew日志条目，将会退出（返回follower状态）。这意味着将会有一段时间（包括提交Cnew时）leader正在管理一个不包括自己的集群。它复制日志条目但是不认为自己占多数。当Cnew被提交时leader发生转换，因为这是新配置可以独立运行的第一个点（总有可能会从Cnew中选出一个leader）。在这个点之前，只可能有来自Cold的服务可以被选为leader。

第三个问题是删除服务（那些不在Cnew）可以破坏集群。这些服务将不会接受心跳，所以他们将会超时并且开始新的任期。之后他们将发送RequestVote RPC和新的任期号一起。这将会导致当前的leader恢复到follower状态。新的leader最终将会被选中，但是被删除的服务将会再次超时并且过程将被重复，导致了可用性差。

为了避免这个问题，当他们相信当前的leader存在时，服务无视RequestVote RPC。特别的，如果服务器在当前leader的最小选举超时内服务接受了RequestVote RPC，它不更新其任期或对他投票。它不会影响正常选举，其中每个服务在开始选举之前最少等待最小的选举超时。然而，它帮助避免了删除服务的破坏：如果leader能够获取到它集群的心跳，那么它不会被更大的任期号所罢免。

7 日志压缩

raft日志在常规操作时增长以合并更多客户端的请求，但是在真实系统中，它不能没有边界的增长。随着日志的变成，它占用更多的空间，需要更长的时间来重放。这将最终导致可用性问题，没有 一些机制去扔掉过时的在日志中累计的信息。快照是最简单的方法进行压缩。使用快照，整个当前系统状态被写入稳态存储的快照中，然后整个日志不超过丢弃的点。快照被用在Chubby和Zookeeper中，该章节的剩余部分描述raft中的快照。

增量压缩的方法，如日志清理和日志结构合并树，也是可能的。它们一次对数据的一小部分进行操作，因此，随着时间的推移，它们会更均匀的分布压实的负荷。它们首选选择一个数据区域，这个区域已经积累了许多被删除或者被重写的对象，然后他重写来自哪个区块的存活数据并释放该区域。对比快照，这需要明显的额外的机制和复杂度，快照通过在整个数据集上进行操作简化了问题。虽然日志清理需要修改raft，但状态机可以使用与快照相同的接口实现LSM树。

图12：一个服务使用新的快宅替换在它日志中已提交的条目（索引1-5)，快照只存储当前的数据（例子中的变量x和y)。快照最后包含了index和任期用于在日志条目6之前定位快照

图12展示了raft中基础的快照方式，每个服务独自进行快照，只覆盖日志中已经提交的条目。大部分的工作包含状态机写入当前的工作到快照。raft也包含了快照中少量的元数据：最后一个被包含的索引是快照所题卷的日志中最后一个条目的索引（状态机应用的最后一个条目），并且最后包含的任期是这个条目的任期。这些被保留以支持快照后第一个的条目的AppendEntries一致性检查，因为这个条目需要之前的日志索引和任期。为了启用集群成员变换（章节6），快照也包含了最后一次记录的索引的日志中最后的配置。一旦服务完成写入快照，它可以删除直到最后一个被记录索引的所有日志条目，以及之前的快照。

虽然服务通常独立的进行快照，但是leader必须给落后的follower发送快照。当leader已经丢弃了他需要发送给follower的下一个日志条目这件事就会发生。幸运的是，这种场景不太可能发生：一个和leader保持同步的follower已经有了这个条目。

以下是翻译好的图3

InstallSnapshot RPC

通过leader发送快照块到follower进行执行.Leader总是按顺序发送快照

参数

Term：leader的任期

leaderId：所以follower可以重新重定向到客户端

lastIncludedTerm（最后被包含的索引）：快照包含了此条目在内的所有条目所有条目

lastIncludedTerm：被最后包含索引包含的任期

offset：块文件中的位置的字节偏移量

data[]：快照块的原始字节，在偏移量处开始

done：如果这是最后一个区块的话为真

结果

任期：当前任期，为了leader自己进行更新

接受者实现

1. 如果任期<当前任期 立即进行回复
2. 如果是第一个块，创建新的快照文件（offset为0）
3. 在给定的偏移量写入数据到快照文件
4. 如果done是false，关联和等待更多的数据块
5. 保存快照文件，放弃任何已经存在的或者索引比较小的快照
6. 如果已经存在的日志条目和快照的最后包含的条目相同的索引和任期，保留它后面的日志条目并回复
7. 抛弃整个日志
8. 使用快照的内容重置状态（并且加载快照的集群配置）

图13：InstallSnapshot RPC的摘要。快照被切成信息块；这给了follower一个每个区块的存活信号，所以它可以重置它的选举时间。

leader使用新的RPC叫做InstallSnapshot已发送快照到那个落后太多的follower，如图13。当follower接受到了这个快照的RPC，他必须决定如何处理现在存在的日志条目。通常快照包含接受者日志中没有包含的日志。在这个例子中，follower丢弃了这个日志；完全被快照所取代，并且可能存在与快照冲突的未提交条目。相反，如果follower接受到描述其日志前缀的快照（由于重传或者错误），那么删除快照所覆盖的条目，但是快照之后的条目仍然有效必须保留。

这个方式背离了raft的强leader原则，因为follower可以在leader不知情的情况下快照。然而，我们认为这个背离是合理的。有一个leader有助于避免进行共识时的冲突决定，当快照进行时一致性已经被保证了，所以没有决策冲突。数据仍然遵循从leader到follwer，只不过follower可以整顿这些数据。

我们考虑了另一种基于leader的方法，其中只有leader能创建快照，然后他会将快照发送到每一个节点上。然而这有俩个劣势。首先，发送快照到每个follower将会浪费网络带块并且拖慢快照进程。每个follower已经有了所需的信息去战胜自己的快照，并且服务产生自己本地状态的快照相比与从网络上接受快照更加廉价。其次，leader实现将会更加复杂。例如，leader将需要发送快，同时向他们复制新的条目，以免组织新的请求。

这里有俩个问题会影响快照的性能。第一，服务必须定时提供快照。如果服务快照过于频繁，它浪费了磁盘带宽和性能；如果它的快照过于不频繁，它增加了存储容量耗尽的危险，并且增加了在启动时重放日志需要的时间。一个简单的策略是当日志到固定的字节时进行快照。如果此大小明显大于快照的预期大小，那么磁盘带宽将会被明显的缩小。

第二个性能问题是写入快照可能花费显著的时间，并且我们不想让它延迟日常操作。解决方法是使用copy-on-write技术，因此新的更新可以被接受而不用受到写入快照的影响。例如，使用函数式据结构的状态机自然支持这一点。或者操作系统的copy-on-write支持（即 Linux的分治）可以被用来创建整个状态机的内存快照（我们使用这个方法实现）。

8 客户端交流

这个章节描述了客户端在raft中的交流，包括了客户端如何找到集群leader和raft如何支持线性的语义，并且raft的方案比其他系统更为简单。

raft客户端发送它所有的请求到leader。当客户端第一次启动，它随机选择一个服务连接。如果客户端的第一次选择的不是leader，那个服务将会拒绝客户端请求并且提供最新leader的信息（AppendEntries请求包含了leader的网络地址）。如果leader崩溃，客户端请求将会超时，然后客户端尝试做一次随机选择服务。

我们raft的目标是实现线性化的语义（每个操作看起来都是线性执行的，在调用和响应的某个点准确的一次。）然而，如同描述过的，raft到目前为止可能将一个命令执行多次。：例如，如果leader在提交日志条目后崩溃，但是响应到给了其他客户端，客户端将使用新的leader执行该命令，导致它会被执行俩次。解决方案是让客户端为每个命令分配唯一的序列号。然后状态机跟踪为每个客户端处理的最新序列号，以及相关的响应。如果得到了一个序列号已经被执行的命令，它立即响应而不重新执行请求。

只读操作可以在不写入任何日志的情况下处理。然而，没有额外的措施，这可能有返回旧数据的风险，因此leader可能已经被它不知道的新leader所取代。线性化读取必须不返回过时数据，而Raft需要采取两个额外的预防措施，以在不使用日志的情况下保证这一点。首先leader必须有已提交条目的最新信息。leader 完备特性保证了leader拥有所有提交的条目，但是任期开始时，它可能不知道哪些条目已提交。为了找到它，需要提交来自它任期的条目。raft通过每个leader在它们的任期开始提交空的no-op条目到日志来处理。其次，leader在处理只读请求之前，leader必须检查它是否被删除（如果出现了更新的leader被选上了，那它的信息可能是旧的）。raft通过让leader响应只读请求之前与大多数集群交换心跳消息来处理这个问题。或者，leader可以依赖某种程度的心跳机制提供租约，但这将依赖于安全的时机（它假设了有限的时钟偏移）。