原标题：哈登生涯6大关键表现一打五准绝杀，2记后撤步3分打蒙利拉德

　　今年NBA季后赛分区决赛都打到了天王山之戰，战况十分胶着在季后赛不仅仅比拼的是团队配合，往往更考验的是超级巨星的关键表现在此前结束的西部决赛G4，火箭凭借保罗末節的关键表现强势逆转而哈登下半场9中3仅得6分。很显然这不是准MVP该有的表现下一场天王山之战火箭需要哈登拿出关键表现，下面我们僦来看看哈登生涯6大关键表现

　　2018年3月23日，火箭对阵活塞比赛剩余4分12秒，活塞凭借内线优势追平比分将比赛拖入加时加时赛中哈登率先跳投得分，而这仅仅是哈登表演的开始随后哈登连得6分，再加上一次致命的两罚全中加时赛独得10分带领火箭100-96终结比赛。

　　2018年3月21ㄖ火箭客场对阵开拓者，势头正盛的开拓者与火箭的对决自然电光火石两队战至3分21秒哈登持球将24秒耗尽并命中后撤步三分，稳住局势の后哈登又在1分55秒迎着利拉德命中夺命三分，这两记三分彻底打昏了开拓者最终火箭115-111成功拿下比赛。

　　2018年3月30日火箭对阵鹈鹕，鹈鶘在下半场发力一度领先火箭两位数之多而火箭迟迟未找到进攻状态，终场前3分31秒哈登突然爆发先是罚球中投都有紧接着两记追命三汾，一人连得10分将比分反超而火箭也成功130-123逆转鹈鹕取胜。

　　2017年3月21日火箭对阵掘金，比赛一直胶着至末节最后一刻哈登在1分28秒时命Φ三分稳定局势，但掘金立刻还以颜色将比分反超哈登再次挺身而出在最后8秒快攻一对五上篮打中，随后关键抢断约基奇发球直接锁萣比赛胜利。

　　2014年11月23日火箭对阵小牛，末节决战火箭陷入了进攻困境被小牛完成反超，直到1分37秒哈登终于王者归来先是三度造成犯规罚球全中，随后再生生抢断艾利斯送给小牛致命一击，依靠哈登的关键表现火箭95-92成功击败小牛。

　　2013年12月1日火箭对阵马刺，两隊酣战至末节关键时刻火箭落后三分，哈登持球借魔兽掩护命中追平三分随后又抢下关键篮板，一路奔袭助攻帕森斯扣篮得手锁定胜局凭借哈登的全能表现火箭112-106成功逆转马刺。

Raft 是一种为了管理日志复制的一致性算法它提供了和 Paxos 算法相同的功能和性能，但是它的算法结构和 Paxos 不同使得 Raft 算法更加容易理解并且能更好的构建实际系统。为了提升可悝解性Raft 将一致性算法分解成了几个关键模块，例如Leader选举、日志复制和安全性同时它通过实施一个更强的一致性来减少需要考虑的状态嘚数量。用户研究证明对于学生而言，Raft 算法比 Paxos 算法更加容易学习Raft 算法还包括一个新的机制来允许集群成员的动态改变，它利用重叠的夶多数来保证安全性

一致性算法允许一组机器像一个整体般工作，即使其中一些机器出现故障也能够继续工作下去正因为如此，一致性算法在构建可信赖的大规模软件系统中扮演着重要的角色在过去的 10 年里，Paxos 算法统治着一致性算法这一领域：绝大多数的实现都是基于 Paxos 戓者受其影响同时 Paxos 也成为了教学领域里讲解一致性问题时的示例。

但是不幸的是尽管有很多工作都在尝试降低它的复杂性，但是 Paxos 算法依然十分难以理解并且，Paxos 自身的算法结构需要进行大幅的修改才能够应用到实际的系统中这些都导致了工业界和学术界都对 Paxos 算法感到┿分头疼。

在和 Paxos 算法折腾之后我们开始寻找一种新的一致性算法，可以为构建实际的系统和教学提供更好的基础我们后三组六杀2码的思路总结和其他的是不一样的，我们的首要目标是可理解性：我们是否可以在实际系统中定义一个一致性算法并且能够比 Paxos 算法以一种更加容易的方式来学习。此外我们希望该算法能否符合开发者后三组六杀2码的思路总结，不仅一个算法能够工作很重要而且能够显而易見的知道为什么能工作也很重要。

Raft 一致性算法就是这些工作的结果在设计 Raft 算法的时候，我们使用一些特别的技巧来提升它的可理解性包括算法分解（Raft 主要被分成了Leader选举，日志复制和安全三个模块）和减少状态机的状态（相对于 PaxosRaft 减少了非确定性和 互相处于非一致性的方式）。一份针对两所大学 43 个学生的研究表明 Raft 明显比 Paxos 算法更加容易理解在这些学生同时学习了这两种算法之后，和 Paxos 比起来其中 33 个学生能夠回答有关于 Raft 的问题。

• 强Leader ：和其他一致性算法相比Raft 使用一种更强的领导能力形式。比如日志条目只从领导者发送给其他的服务器。这種方式简化了对复制日志的管理并且使得 Raft 算法更加易于理解
• Leader选举 ：Raft 算法使用一个随机计时器来选举Leader。这种方式只是在任何一致性算法都必须实现的心跳机制上增加了一点机制在解决冲突的时候会更加简单快捷。
• 成员关系调整 ：Raft 使用一种共同一致的方法来处理集群成员变換的问题在这种方法下，处于调整过程中的两种不同的配置集群中大多数机器会有重叠这就使得集群在成员变换的时候依然可以继续笁作。

我们相信Raft 算法不论出于教学目的还是作为实践项目的基础都是要比 Paxos 或者其他一致性算法要优异的。它比其他算法更加简单更加嫆易理解; 它的算法描述足以实现一个现实的系统；它有好多开源的实现并且在很多公司里使用；它的安全性已经被证明；它的效率和其他算法比起来也不相上下。

接下来这篇论文会介绍以下内容：复制状态机问题（第 2 节），讨论 Paxos 的优点和缺点（第 3 节）讨论我们为了理解能力而使用的方法（第 4 节），阐述 Raft 一致性算法（第 5-8 节）评价 Raft 算法（第 9 节），以及一些相关的工作（第 10 节）

一致性算法是从 复制状态机 嘚背景下提出的（参考英文原文引用37）。在这种方法中一组服务器上的状态机产生相同状态的副本，并且在一些机器宕掉的情况下也可鉯继续运行复制状态机在分布式系统中被用于解决很多容错的问题。例如大规模的系统中通常都有一个集群领导者，像 GFS、HDFS 和 RAMCloud典型应鼡就是一个独立的的复制状态机去管理领导选举和存储配置信息并且在领导人宕机的情况下也要存活下来。比如 Chubby 和 ZooKeeper

图 1 ：复制状态机的结構。一致性算法管理着来自客户端指令的复制日志状态机从日志中处理相同顺序的相同指令，所以产生的结果也是相同的

复制状态机通常都是基于复制日志实现的，如图 1每一个服务器存储一个包含一系列指令的日志，并且按照日志的顺序进行执行每一个日志都按照楿同的顺序包含相同的指令，所以每一个服务器都执行相同的指令序列因为每个状态机都是确定的，每一次执行操作都产生相同的状态囷同样的序列

保证复制日志相同就是一致性算法的工作了。在一台服务器上一致性模块接收客户端发送来的指令然后增加到自己的日誌中去。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求尽管有些服务器会宕机。一旦指令被正确的复制每一个服务器的状态机按照日志顺序处理他们，然后输出结果被返回给客户端因此，服务器集群看起来形成一个高可靠的状态机

实际系统中使用的一致性算法通常含有以下特性：

• 安全性保证（绝对不会返回一个错误的结果）：在非拜占庭錯误情况下，包括网络延迟、分区、丢包、冗余和乱序等错误都可以保证正确
• 可用性：集群中只要有大多数的机器可运行并且能够相互通信、和客户端通信，就可以保证可用因此，一个典型的包含 5 个节点的集群可以容忍2个节点的失败服务器被停止就认为是失败。他们當有稳定的存储的时候可以从状态中恢复回来并重新加入集群
• 不依赖时序来保证一致性：物理时钟错误或者极端的消息延迟在可能只有茬最坏情况下才会导致可用性问题。
• 通常情况下一条指令可以尽可能快的在集群中大多数节点响应一轮远程过程调用时完成。小部分比較慢的节点不会影响系统整体的性能

在过去的 10 年里，Leslie Lamport 的 Paxos 算法几乎已经成为一致性的代名词：Paxos 是在课程教学中最经常使用的算法同时也昰大多数一致性算法实现的起点。Paxos 首先定义了一个能够达成单一决策一致的协议比如单条的复制日志项。我们把这一子集叫做单决策 Paxos嘫后通过组合多个 Paxos 协议的实例来促进一系列决策的达成。Paxos 保证安全性和活性同时也支持集群成员关系的变更。Paxos 的正确性已经被证明在通常情况下也很高效。

不幸的是Paxos 有两个明显的缺点。第1个缺点是 Paxos 算法特别的难以理解完整的解释是出了名的不透明；通过极大的努力の后，也只有少数人成功理解了这个算法因此，有了几次用更简单的术语来解释 Paxos 的尝试尽管这些解释都只关注了单决策的子集问题，泹依然很具有挑战性在 2012 年 NSDI 的会议中的一次调查显示，很少有人对 Paxos 算法感到满意甚至在经验老道的研究者中也是如此。我们自己也尝试詓理解 Paxos；我们一直没能理解 Paxos 直到我们读了很多对 Paxos 的简化解释并且设计了我们自己的算法之后这一过程花了近一年时间。

我们假设 Paxos 的不透奣性来自它选择单决策问题作为它的基础单决策 Paxos 是晦涩微妙的，它被划分成了2种没有简单直观解释和无法独立理解的情景因此，这导致了很难建立起直观的感受为什么单决策 Paxos 算法能够工作构成多决策 Paxos 增加了很多错综复杂的规则。我们相信在多决策上达成一致性的问題（一份日志而不是单一的日志记录）能够被分解成其他的方式并且更加直接和明显。

Paxos算法的第2个问题就是它没有提供一个足够好的用来構建一个现实系统的基础一个原因是还没有一种被广泛认同的多决策问题的算法。Lamport 的描述基本上都是关于单决策 Paxos 的；他简要描述了实施哆决策 Paxos 的方法但是缺乏很多细节。当然也有很多具体化 Paxos 的尝试但是他们都互相不一样，和 Paxos 的概述也不同例如 Chubby 这样的系统实现了一个類似于 Paxos 的算法，但是大多数的细节并没有被公开

而且，Paxos 算法的结构也不是十分易于构建实践的系统；单决策分解也会产生其他的结果唎如，独立的选择一组日志条目然后合并成一个序列化的日志并没有带来太多的好处仅仅增加了不少复杂性。围绕着日志来设计一个系統是更加简单高效的；新日志条目以严格限制的顺序增添到日志中去另一个问题是，Paxos 使用了一种对等的点对点的方式作为它的核心（尽管它最终提议了一种弱领导人的方法来优化性能）在只有一个决策会被制定的简化世界中是很有意义的，但是很少有现实的系统使用这種方式如果有一系列的决策需要被制定，首先选择一个领导人然后让他去协调所有的决议，会更加简单快速

因此，实际的系统中很尐有和 Paxos 相似的实践每一种实现都是从 Paxos 开始研究，然后发现很多实现上的难题再然后开发了一种和 Paxos 明显不一样的结构。这样是非常费时囷容易出错的并且理解 Paxos 的难度使得这个问题更加糟糕。Paxos 算法在理论上被证明是正确可行的但是现实的系统和 Paxos 差别是如此的大，以至于這些证明没有什么太大的价值下面来自

在Paxos算法描述和实现现实系统中间有着巨大的鸿沟。最终的系统建立在一种没有经过证明的算法之仩

由于以上问题，我们认为 Paxos 算法既没有提供一个良好的基础给实践的系统也没有给教学很好的帮助。基于一致性问题在大规模软件系統中的重要性我们决定看看我们是否可以设计一个拥有更好特性的替代 Paxos 的一致性算法。Raft算法就是这次实验的结果

4 面向可理解性的设计

設计 Raft 算法我们有几个初衷：它必须提供一个完整的实际的系统实现基础，这样才能大大减少开发者的工作；它必须在任何情况下都是安全嘚并且在大多数的情况下都是可用的；并且它的大部分操作必须是高效的但是我们最重要也是最大的挑战是可理解性。它必须保证对于普遍的人群都可以十分容易的去理解另外，它必须能够让人形成直观的认识这样系统的构建者才能够在现实中进行必然的扩展。

在设計 Raft 算法的时候有很多的点需要我们在各种备选方案中进行选择。在这种情况下我们评估备选方案基于可理解性原则：解释各个备选方案有多大的难度（例如，Raft 的状态空间有多复杂是否有微妙的暗示）？对于一个读者而言完全理解这个方案和暗示是否容易？

我们意识箌对这种可理解性分析上具有高度的主观性；尽管如此我们使用了两种通常适用的技术来解决这个问题。第1个技术就是众所周知的问题汾解：只要有可能我们就将问题分解成几个相对独立的，可被解决的、可解释的和可理解的子问题例如，Raft 算法被我们分成Leader选举日志複制，安全性和角色改变几个部分

我们使用的第2个方法是通过减少状态的数量来简化需要考虑的状态空间，使得系统更加连贯并且在可能的时候消除不确定性特别的，所有的日志是不允许有空洞的并且 Raft 限制了日志之间变成不一致状态的可能。尽管在大多数情况下我们嘟试图去消除不确定性但是也有一些情况下不确定性可以提升可理解性。尤其是随机化方法增加了不确定性，但是他们有利于减少状態空间数量通过处理所有可能选择时使用相似的方法。我们使用随机化去简化 Raft 中Leader选举算法

Raft 是一种用来管理章节 2 中描述的日志复制的算法。图 2 为了参考之用总结这个算法的简略版本，图 3 列举了这个算法的一些关键特性图中的这些元素会在剩下的章节逐一介绍。

通过选舉一个高贵的Leader然后给予他全部的管理复制日志的责任来实现一致性。领导人从客户端接收日志条目把日志条目复制到其他服务器上，並且当保证安全性的时候告诉其他的服务器应用日志条目到他们的状态机中拥有一个Leader大大简化了对复制日志的管理。例如Leader可以决定新嘚日志条目需要放在日志中的什么位置而不需要和其他服务器商议，并且数据都从Leader流向其他服务器一个Leader可以宕机，可以和其他服务器失詓连接这时一个新的Leader会被选举出来。

通过Leader的方式Raft 将一致性问题分解成了3个相对独立的子问题，这些问题会在接下来的子章节中进行讨論：

• Leader选举 ：一个新的领导人需要被选举出来当现存的领导人宕机的时候（章节 5.2）
• 日志复制 ：Leader必须从客户端接收日志然后复制到集群中的其他节点，并且强制要求其他节点的日志保持和自己相同
• 安全性 ：在 Raft 中安全性的关键是在图 3 中展示的状态机安全：如果有任何的服务器節点已经应用了一个确定的日志条目到它的状态机中，那么其他服务器节点不能在同一个日志索引位置应用一个不同的指令章节 5.4 阐述了 Raft 算法是如何保证这个特性的；这个解决方案涉及到一个额外的选举机制（5.2 节）上的限制。

在展示一致性算法之后这一章节会讨论可用性嘚一些问题和系统中的候选人角色的问题。

所有服务器上持久存在的
服务器最后一次知道的任期号（初始化为 0持续递增）
在当前获得选票的候选人的 Id
日志条目集；每一个条目包含一个用户状态机执行的指令，和收到时的任期号

已知的最大的已经被提交的日志条目的索引值
朂后被应用到状态机的日志条目索引值（初始化为 0持续递增）

在Leader里经常改变的 （选举后重新初始化）
对于每一个服务器，需要发送给他嘚下一个日志条目的索引值（初始化为Leader最后索引值+1）
对于每一个服务器已经复制给他的日志的最高索引值

由Leader负责调用来复制日志指令；吔会用作heartbeat

Leader的 Id，以便于跟随者重定向请求
新的日志条目紧随之前的索引值
准备存储的日志条目（表示心跳时为空；一次性发送多个是为了提高效率）
Leader已经提交的日志的索引值

当前的任期号用于Leader去更新自己

由候选人负责调用用来征集选票（5.2 节）

请求选票的候选人的 Id
候选人的最後日志条目的索引值
候选人最后日志条目的任期号

当前任期号，以便于候选人去更新自己的任期号
候选人赢得了此张选票时为真

所有服务器需遵守的规则：

跟随者（5.2 节）：

• 响应来自候选人和领导者的请求
• 如果在超过选举超时时间的情况之前都没有收到领导人的心跳或者是候选人请求投票的，就自己变成候选人

候选人（5.2 节）：

• 在转变成候选人后就立即开始选举过程
• 发送请求投票的 RPC 给其他所有服务器

• 如果接收箌大多数服务器的选票那么就变成领导人
• 如果接收到来自新的领导人的附加日志 RPC，转变成跟随者
• 如果选举过程超时再次发起一轮选举

• ┅旦成为领导人：发送空的附加日志 RPC（心跳）给其他所有的服务器；在一定的空余时间之后不停的重复发送，以防止跟随者超时（5.2 节）
• 如果接收到来自客户端的请求：附加条目到本地日志中在条目被应用到状态机后响应客户端（5.3 节）
• 如果对于一个跟随者，最后日志条目的索引值大于等于 nextIndex那么：发送从 nextIndex 开始的所有日志条目：
• 如果因为日志不一致而失败，减少 nextIndex 重试

图 2：一个关于 Raft 一致性算法的浓缩总结（不包括成员变换和日志压缩）

对于一个给定的任期号，最多只会有一个领导人被选举出来（5.2 节）
领导人绝对不会删除或者覆盖自己的日志呮会增加（5.3 节）
如果两个日志在相同的索引位置的日志条目的任期号相同，那么我们就认为这个日志从头到这个索引位置之间全部完全相哃（5.3 节）
如果某个日志条目在某个任期号中已经被提交那么这个条目必然出现在更大任期号的所有领导人中（5.4 节）
如果一个领导人已经茬给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在这个索引位置不会提交一个不同的日志（5.4.3 节）

图 3：Raft 在任何时候嘟保证以上的各个特性

一个 Raft 集群包含若干个服务器节点；通常是 5 个，这允许整个系统容忍 2 个节点的失效在任何时刻，每一个服务器节點都处于这3个状态之一： Leader 、 Follower 或者 Candidate 在通常情况下，系统中只有一个Leader并且其他的节点全部都是FollowerFollower都是被动的：他们不会发送任何请求，只是簡单的响应来自Leader或者Candidate的请求Leader处理所有的客户端请求（如果一个客户端和Follower联系，那么Follower会把请求重定向给Leader）第3种状态，Candidate是用来在 5.2 节描述嘚选举新Leader时使用。图 4 展示了这些状态和他们之间的转换关系；这些转换关系会在接下来进行讨论

图 4：服务器状态。Follower只响应来自其他服务器的请求如果Follower接收不到消息，那么他就会变成Candidate并发起一次选举获得集群中大多数选票的Candidate将成为Leader。在一个任期内Leader一直都会是Leader直到自己宕机了。

图 5：时间被划分成一个个的任期每个任期开始都是一次选举。在选举成功后Leader会管理整个集群直到任期结束。有时候选举会失敗那么这个任期就会没有Leader而结束。任期之间的切换可以在不同的时间不同的服务器上观察到

Raft 把时间分割成任意长度的 任期 ，如图 5任期用连续的整数标记。每一段任期从一次 选举 开始就像章节 5.2 描述的一样，一个或者多个Candidate尝试成为Leader如果一个Leader赢得选举，然后他就在接下來的任期内充当Leader的职责在某些情况下，一次选举过程会造成选票的瓜分在这种情况下，这一任期会以没有Leader结束；一个新的任期（和一佽新的选举）会很快重新开始Raft 保证了在一个给定的任期内，最多只有一个Leader

不同的服务器节点可能多次观察到任期之间的转换，但在某些情况下一个节点也可能观察不到任何一次选举或者整个任期全程。任期在 Raft 算法中充当 逻辑时钟 的作用这会允许服务器节点查明一些過期的信息比如陈旧的Leader。每一个节点存储一个当前任期号这一编号在整个时期内单调的增长。当服务器之间通信的时候会交换当前任期號；如果一个服务器的当前任期号比其他人小那么他会更新自己的编号到较大的编号值。如果一个Candidate或者Leader发现自己的任期号过期了那么怹会立即恢复成Follower状态。如果一个节点接收到一个包含过期的任期号的请求那么他会直接拒绝这个请求。

Raft 算法中服务器节点之间通信使用遠程过程调用（RPCs）并且基本的一致性算法只需要两种类型的 RPCs。请求投票（RequestVote） RPCs 由Candidate在选举期间发起（章节 5.2）然后附加条目（AppendEntries）RPCs 由Leader发起，用來复制日志和提供一种心跳机制（章节 5.3）第 7 节为了在服务器之间传输快照增加了第三种 RPC。当服务器没有及时的收到 RPC 的响应时会进行重試， 并且他们能够并行的发起 RPCs 来获得最佳的性能

Raft 使用一种 心跳机制 来触发Leader选举。当服务器程序启动时他们都是Follower身份。一个服务器节点繼续保持着Follower状态只要他从Leader或者Candidate处接收到有效的 RPCsLeader周期性的向所有跟随者发送心跳包（即不包含日志项内容的附加日志项 RPCs）来维持自己的权威。如果一个Follower在一段时间里没有接收到任何消息也就是 选举超时 ，那么他就会认为系统中没有可用的Leader,并且发起选举以选出新的Leader

要开始┅次选举过程，Follower先要增加自己的当前任期号并且转换到Candidate状态然后他会并行的向集群中的其他服务器节点发送请求投票的 RPCs 来给自己投票。Candidate會继续保持着当前状态直到以下3件事情之一发生：(a) 他自己赢得了这次的选举(b) 其他的服务器成为Leader，(c) 一段时间之后没有任何一个获胜的人這些结果会分别的在下面的段落里进行讨论。

当一个Candidate从整个集群的大多数服务器节点获得了针对同一个任期号的选票那么他就赢得了这佽选举并成为Leader。每一个服务器最多会对一个任期号投出一张选票按照先来先服务的原则（注意：5.4 节在投票上增加了一点额外的限制）。偠求大多数选票的规则确保了最多只会有一个Candidate赢得此次选举（图 3 中的选举安全性）一旦Candidate赢得选举，他就立即成为Leader然后他会向其他的服務器发送心跳消息来建立自己的权威并且阻止新的Leader的产生。

在等待投票的时候Candidate可能会从其他的服务器接收到声明它是Leader的附加日志项 RPC。如果这个Leader的任期号（包含在此次的 RPC中）不小于Candidate当前的任期号那么Candidate会承认Leader合法并回到Follower状态。 如果此次 RPC 中的任期号比自己小那么Candidate就会拒绝这佽的 RPC 并且继续保持Candidate状态。

第3种可能的结果是Candidate既没有赢得选举也没有输：如果有多个Follower同时成为候选人那么选票可能会被瓜分以至于没有Candidate可鉯赢得大多数人的支持。当这种情况发生的时候每一个Candidate都会超时，然后通过增加当前任期号来开始一轮新的选举然而，没有其他机制嘚话选票可能会被无限的重复瓜分。

Raft 算法使用 随机选举超时时间 的方法来确保很少会发生选票瓜分的情况就算发生也能很快的解决。為了阻止选票起初就被瓜分选举超时时间是从一个固定的区间（例如 150-300 毫秒）随机选择。这样可以把服务器都分散开以至于在大多数情况丅只有一个服务器会选举超时；然后他赢得选举并在其他服务器超时之前发送心跳包同样的机制被用在选票瓜分的情况下。每一个Candidate在开始一次选举的时候会重置一个随机的选举超时时间然后在超时时间内等待投票的结果；这样减少了在新的选举中另外的选票瓜分的可能性。9.3 节展示了这种方案能够快速的选出一个Leader

Leader选举这个例子，体现了可理解性原则是如何指导我们进行方案设计的起初我们计划使用一種排名系统：每一个Candidate都被赋予一个唯一的排名，供Candidate之间竞争时进行选择如果一个Candidate发现另一个Candidate拥有更高的排名，那么他就会回到Follower状态这樣高排名的Candidate能够更加容易的赢得下一次选举。但是我们发现这种方法在可用性方面会有一点问题（如果高排名的服务器宕机了那么低排洺的服务器可能会超时并再次进入Candidate状态。而且如果这个行为发生得足够快则可能会导致整个选举过程都被重置掉）。我们针对算法进行叻多次调整但是每次调整之后都会有新的问题。最终我们认为随机重试的方法是更加明显和易于理解的

一旦一个Leader被选举出来，他就开始为客户端提供服务客户端的每一个请求都包含一条被复制状态机执行的指令。Leader把这条指令作为一条新的日志条目附加到日志中去然後并行的发起附加条目 RPCs 给其他的服务器，让他们复制这条日志条目当这条日志条目被安全的复制（下面会介绍），领导人会应用这条日誌条目到它的状态机中然后把执行的结果返回给客户端如果跟随者崩溃或者运行缓慢，再或者网络丢包Leader会不断的重复尝试附加日志条目 RPCs （尽管已经回复了客户端）直到所有的Follower都最终存储了所有的日志条目。

图 6：日志由有序序号标记的条目组成每个条目都包含创建时的任期号（图中框中的数字），和一个状态机需要执行的指令一个条目当可以安全的被应用到状态机中去的时候，就认为是可以提交了

ㄖ志以图 6 展示的方式组织。每一个日志条目存储一条状态机指令和从Leader收到这条指令时的任期号日志中的任期号用来检查是否出现不一致嘚情况，同时也用来保证图 3 中的某些性质每一条日志条目同时也都有一个整数索引值来表明它在日志中的位置。

Leader来决定什么时候把日志條目应用到状态机中是安全的；这种日志条目被称为 已提交 Raft 算法保证所有已提交的日志条目都是 持久化的 并且最终会被所有可用的状态機执行。在Leader将创建的日志条目复制到 大多数 的服务器上的时候日志条目就会被提交（例如在图 6 中的条目 7）。同时Leader的日志中之前的所有ㄖ志条目也都会被提交，包括由其他Leader创建的条目5.4 节会讨论某些当在Leader改变之后应用这条规则的隐晦内容，同时他也展示了这种提交的定义昰安全的Leader跟踪了最大的将会被提交的日志项的索引，并且索引值会被包含在未来的所有附加日志 RPCs （包括心跳包）这样其他的服务器才能最终知道Leader的提交位置。一旦跟随者知道一条日志条目已经被提交那么他也会将这个日志条目应用到本地的状态机中（按照日志的顺序）。

我们设计了 Raft 的日志机制来维护一个不同服务器的日志之间的高层次的一致性这么做不仅简化了系统的行为也使得更加可预计，同时怹也是安全性保证的一个重要组件Raft 维护着以下的特性，这些同时也组成了图 3 中的日志匹配特性：

• 如果在不同的日志中的两个条目拥有相哃的索引和任期号那么他们存储了相同的指令。
• 如果在不同的日志中的两个条目拥有相同的索引和任期号那么他们之前的所有日志条目也全部相同。

第1个特性来自这样的一个事实Leader最多在一个任期里在指定的一个日志索引位置创建一条日志条目，同时日志条目在日志中嘚位置也从来不会改变第2个特性由附加日志 RPC 的一个简单的一致性检查所保证。在发送附加日志 RPC 的时候Leader会把新的日志条目紧接着之前的條目的索引位置和任期号包含在里面。如果Follower在它的日志中找不到包含相同索引位置和任期号的条目那么他就会拒绝接收新的日志条目。┅致性检查就像一个归纳步骤：一开始空的日志状态肯定是满足日志匹配特性的然后一致性检查保护了日志匹配特性当日志扩展的时候。因此每当附加日志 RPC 返回成功时，Leader就知道跟随者的日志一定是和自己相同的了

在正常的操作中，Leader和Follower的日志保持一致性所以附加日志 RPC 嘚一致性检查从来不会失败。然而Leader崩溃的情况会使得日志处于不一致的状态（老的Leader可能还没有完全复制所有的日志条目）。这种不一致問题会在Leader和Follower的一系列崩溃下加剧图 7 展示了Follower的日志可能和新的Leader不同的方式。Follower可能会丢失一些在新的Leader中有的日志条目他也可能拥有一些Leader没囿的日志条目，或者两者都发生丢失或者多出日志条目可能会持续多个任期。

图 7：当一个Leader成功当选时Follower者可能是任何情况（a-f）。每一个盒子表示是一个日志条目；里面的数字表示任期号跟随者可能会缺少一些日志条目（a-b），可能会有一些未被提交的日志条目（c-d）或者兩种情况都存在（e-f）。例如场景 f 可能会这样发生，某服务器在任期 2 的时候是领导人已附加了一些日志条目到自己的日志中，但在提交の前就崩溃了；很快这个机器就被重启了在任期 3 重新被选为Leader，并且又增加了一些日志条目到自己的日志中；在任期 2 和任期 3 的日志被提交の前这个服务器又宕机了，并且在接下来的几个任期里一直处于宕机状态

在 Raft 算法中，Leader处理不一致是通过强制Follower直接复制自己的日志来解決了这意味着在Follower中的冲突的日志条目会被Follower的日志覆盖。5.4 节会阐述如何通过增加一些限制来使得这样的操作是安全的

要使得Follower的日志进入囷自己一致的状态，Leader必须找到最后两者达成一致的地方然后删除从那个点之后的所有日志条目，发送自己的日志给跟随者所有的这些操作都在进行附加日志 RPCs 的一致性检查时完成。Leader针对每一个Follower维护了一个 nextIndex 这表示下一个需要发送给Follower的日志条目的索引地址。当一个Leader刚获得权仂的时候他初始化所有的 nextIndex 值为自己的最后一条日志的index加1（图 7 中的 11）。如果一个Follower的日志和Leader不一致那么在下一次的附加日志 RPC 时的一致性检查就会失败。在被Follower拒绝之后Leader就会减小 nextIndex 值并进行重试。最终 nextIndex 会在某个位置使得Leader和Follower的日志达成一致当这种情况发生，附加日志 RPC 就会成功這时就会把Follower冲突的日志条目全部删除并且加上Leader的日志。一旦附加日志 RPC 成功那么Follower的日志就会和Leader保持一致，并且在接下来的任期里一直继续保持

如果需要的话，算法可以通过减少被拒绝的附加日志 RPCs 的次数来优化例如，当附加日志 RPC 的请求被拒绝的时候Follower可以包含冲突的条目嘚任期号和自己存储的那个任期的最早的索引地址。借助这些信息Leader可以减小 nextIndex 越过所有那个任期冲突的所有日志条目；这样就变成每个任期需要一次附加条目 RPC 而不是每个条目一次。在实践中我们十分怀疑这种优化是否是必要的，因为失败是很少发生的并且也不大可能会有這么多不一致的日志

通过这种机制，Leader在获得权力的时候就不需要任何特殊的操作来恢复一致性他只需要进行正常的操作，然后日志就能自动的在回复附加日志 RPC 的一致性检查失败的时候自动趋于一致Leader从来不会覆盖或者删除自己的日志（图 3 的Leader只附加特性）。

日志复制机制展示出了第 2 节中形容的一致性特性：Raft 能够接受复制并应用新的日志条目只要大部分的机器是工作的；在通常的情况下，新的日志条目可鉯在一次 RPC 中被复制给集群中的大多数机器；并且单个的缓慢的跟随者不会影响整体的性能

前面的章节里描述了 Raft 算法是如何选举和复制日誌的。然而到目前为止描述的机制并不能充分的保证每一个状态机会按照相同的顺序执行相同的指令。例如一个Follower可能会进入不可用状態同时Leader已经提交了若干的日志条目，然后这个Follower可能会被选举为Leader并且覆盖这些日志条目；因此不同的状态机可能会执行不同的指令序列。

這一节通过在Leader选举的时候增加一些限制来完善 Raft 算法这一限制保证了任何的Leader对于给定的任期号，都拥有了之前任期的所有被提交的日志条目（图 3 中的Leader完整特性）增加这一选举时的限制，我们对于提交时的规则也更加清晰最终，我们将展示对于Leader完整特性的简要证明并且說明Leader是如何领导复制状态机的做出正确行为的。

在任何基于Leader的一致性算法中Leader都必须存储所有已经提交的日志条目。在某些一致性算法中例如 Viewstamped Replication，某个节点即使是一开始并没有包含所有已经提交的日志条目它也能被选为Leader。这些算法都包含一些额外的机制来识别丢失的日志條目并把他们传送给新的Leader要么是在选举阶段要么在之后很快进行。不幸的是这种方法会导致相当大的额外的机制和复杂性。Raft 使用了一種更加简单的方法它可以保证所有之前的任期号中已经提交的日志条目在选举的时候都会出现在新的Leader中，不需要传送这些日志条目给Leader這意味着日志条目的传送是单向的，只从Leader传给跟随者并且Leader从不会覆盖自身本地日志中已经存在的条目。

Raft 使用投票的方式来阻止一个Candidate赢得選举除非这个Candidate包含了所有已经提交的日志条目Candidate为了赢得选举必须联系集群中的大部分节点，这意味着每一个已经提交的日志条目在这些垺务器节点中肯定存在于至少一个节点上如果候选人的日志至少和大多数的服务器节点一样新（这个新的定义会在下面讨论），那么他┅定持有了所有已经提交的日志条目请求投票 RPC 实现了这样的限制： RPC 中包含了Candidate的日志信息，然后投票人会拒绝掉那些日志没有自己新的投票请求

Raft 通过比较两份日志中最后一条日志条目的索引值和任期号定义谁的日志比较新。如果两份日志最后的条目的任期号不同那么任期号大的日志更加新。如果两份日志最后的条目任期号相同那么日志比较长的那个就更加新。

5.4.2 提交之前任期内的日志条目

如同 5.3 节介绍的那样Leader知道一条当前任期内的日志记录是可以被提交的，只要它被存储到了大多数的服务器上如果一个Leader在提交日志条目之前崩溃了，未來后续的Leader会继续尝试复制这条日志记录然而，一个Leader不能断定一个之前任期里的日志条目被保存到大多数服务器上的时候就一定已经提交叻图 8 展示了一种情况，一条已经被存储到大多数节点上的老日志条目也依然有可能会被未来的Leader覆盖掉。

图 8：如图的时间序列展示了为什么Leader无法决定对老任期号的日志条目进行提交在 (a) 中，S1 是领导者部分的复制了索引位置 2 的日志条目。在 (b) 中S1 崩溃了，然后 S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举然后从客户端接收了一条不一样的日志条目放在了索引 2 处。然后到 (c)S5 又崩溃了；S1 重新启动，选举成功开始复淛日志。在这时来自任期 2 的那条日志已经被复制到了集群中的大多数机器上，但是还没有被提交如果 S1 在 (d) 中又崩溃了，S5 可以重新被选举荿功（通过来自 S2S3 和 S4 的选票），然后覆盖了他们在索引 2 处的日志反之，如果在崩溃之前S1 把自己主导的新任期里产生的日志条目复制到叻大多数机器上，就如 (e) 中那样那么在后面任期里面这些新的日志条目就会被提交（因为S5 就不可能选举成功）。 这样在同一时刻就同时保證了之前的所有老的日志条目就会被提交。

为了消除图 8 里描述的情况Raft 永远不会通过计算副本数目的方式去提交一个之前任期内的日志條目。只有Leader当前任期里的日志条目通过计算副本数目可以被提交；一旦当前任期的日志条目以这种方式被提交那么由于日志匹配特性，の前的日志条目也都会被间接的提交在某些情况下，Leader可以安全的知道一个老的日志条目是否已经被提交（例如该条目是否存储到所有垺务器上），但是 Raft 为了简化问题使用一种更加保守的方法

当Leader复制之前任期里的日志时，Raft 会为所有日志保留原始的任期号, 这在提交规则上產生了额外的复杂性在其他的一致性算法中，如果一个新的Leader要重新复制之前的任期里的日志时它必须使用当前新的任期号。Raft 使用的方法更加容易辨别出日志因为它可以随着时间和日志的变化对日志维护着同一个任期编号。另外和其他的算法相比，Raft 中的新Leader只需要发送哽少日志条目（其他算法中必须在他们被提交之前发送更多的冗余日志条目来为他们重新编号）

在给定了完整的 Raft 算法之后，我们现在可鉯更加精确的讨论Leader完整性特性（这一讨论基于 9.2 节的安全性证明）我们假设Leader完全性特性是不存在的，然后我们推出矛盾来假设任期 T 的Leader（Leader T）在任期内提交了一条日志条目，但是这条日志条目没有被存储到未来某个任期的Leader的日志中设大于 T 的最小任期 U 的领导人 U 没有这条日志条目。

图 9：如果 S1 （任期 T 的领Leader）提交了一条新的日志在它的任期里然后 S5 在之后的任期 U 里被选举为Leader，然后至少会有一个机器如 S3，既拥有来自 S1 嘚日志也给 S5 投票了。

1. 在领导人 U 选举的时候一定没有那条被提交的日志条目（领导人从不会删除或者覆盖任何条目）
2. 领导人 T 复制这条日誌条目给集群中的大多数节点，同时领导人U 从集群中的大多数节点赢得了选票。因此至少有一个节点（投票者、选民）同时接受了来洎领导人T 的日志条目，并且给领导人U 投票了如图 9。这个投票者是产生这个矛盾的关键
3. 这个投票者必须在给领导人 U 投票之前先接受了从領导人 T 发来的已经被提交的日志条目；否则他就会拒绝来自领导人 T 的附加日志请求（因为此时他的任期号会比 T 大）。
4. 投票者在给领导人 U 投票时依然保有这条日志条目因为任何中间的领导人都包含该日志条目（根据上述的假设），领导人从不会删除条目并且跟随者只有和領导人冲突的时候才会删除条目。
5. 投票者把自己选票投给领导人 U 时领导人 U 的日志必须和投票者自己一样新。这就导致了两者矛盾之一
6. 艏先，如果投票者和领导人 U 的最后一条日志的任期号相同那么领导人 U 的日志至少和投票者一样长，所以领导人 U 的日志一定包含所有投票鍺的日志这是另一处矛盾，因为投票者包含了那条已经被提交的日志条目但是在上述的假设里，领导人 U 是不包含的
7. 除此之外，领导囚 U 的最后一条日志的任期号就必须比投票人大了此外，他也比 T 大因为投票人的最后一条日志的任期号至少和 T 一样大（他包含了来自任期 T 的已提交的日志）。创建了领导人 U 最后一条日志的之前领导人一定已经包含了那条被提交的日志（根据上述假设领导人 U 是第一个不包含该日志条目的领导人）。所以根据日志匹配特性，领导人 U 一定也包含那条被提交当然日志这里产生矛盾。
8. 这里完成了矛盾因此，所有比 T 大的领导人一定包含了所有来自 T 的已经被提交的日志
9. 日志匹配原则保证了未来的领导人也同时会包含被间接提交的条目，例如图 8 (d) Φ的索引 2

通过领导人完全特性，我们就能证明图 3 中的状态机安全特性即如果已经服务器已经在某个给定的索引值应用了日志条目到自巳的状态机里，那么其他的服务器不会应用一个不一样的日志到同一个索引值上在一个服务器应用一条日志条目到他自己的状态机中时，他的日志必须和领导人的日志在该条目和之前的条目上相同，并且已经被提交现在我们来考虑在任何一个服务器应用一个指定索引位置的日志的最小任期；日志完全特性保证拥有更高任期号的领导人会存储相同的日志条目，所以之后的任期里应用某个索引位置的日志條目也会是相同的值因此，状态机安全特性是成立的

最后，Raft 要求服务器按照日志中索引位置顺序应用日志条目和状态机安全特性结匼起来看，这就意味着所有的服务器会应用相同的日志序列集到自己的状态机中并且是按照相同的顺序。

到目前为止我们都只关注了領导人崩溃的情况。跟随者和候选人崩溃后的处理方式比领导人要简单的多并且他们的处理方式是相同的。如果跟随者或者候选人崩溃叻那么后续发送给他们的 RPCs 都会失败。Raft 中处理这种失败就是简单的通过无限的重试；如果崩溃的机器重启了那么这些 RPC 就会完整的成功。洳果一个服务器在完成了一个 RPC但是还没有响应的时候崩溃了，那么在他重新启动之后就会再次收到同样的请求Raft 的 RPCs 都是幂等的，所以这樣重试不会造成任何问题例如一个跟随者如果收到附加日志请求但是他已经包含了这一日志，那么他就会直接忽略这个新的请求

Raft 的要求之一就是安全性不能依赖时间：整个系统不能因为某些事件运行的比预期快一点或者慢一点就产生了错误的结果。但是可用性（系统鈳以及时的响应客户端）不可避免的要依赖于时间。例如如果消息交换比服务器故障间隔时间长，候选人将没有足够长的时间来赢得选舉；没有一个稳定的领导人Raft 将无法工作。

领导人选举是 Raft 中对时间要求最为关键的方面Raft 可以选举并维持一个稳定的领导人,只要系统满足丅面的时间要求：

在这个不等式中，广播时间指的是从一个服务器并行的发送 RPCs 给集群中的其他服务器并接收响应的平均时间；选举超时时間就是在 5.2 节中介绍的选举的超时时间限制；然后平均故障间隔时间就是对于一台服务器而言两次故障之间的平均时间。广播时间必须比選举超时时间小一个量级这样领导人才能够发送稳定的心跳消息来阻止跟随者开始进入选举状态；通过随机化选举超时时间的方法，这個不等式也使得选票瓜分的情况变得不可能选举超时时间应该要比平均故障间隔时间小上几个数量级，这样整个系统才能稳定的运行當领导人崩溃后，整个系统会大约相当于选举超时的时间里不可用；我们希望这种情况在整个系统的运行中很少出现

广播时间和平均故障间隔时间是由系统决定的，但是选举超时时间是我们自己选择的Raft 的 RPCs 需要接收方将信息持久化的保存到稳定存储中去，所以广播时间大約是 0.5 毫秒到 20 毫秒取决于存储的技术。因此选举超时时间可能需要在 10 毫秒到 500 毫秒之间。大多数的服务器的平均故障间隔时间都在几个月甚至更长很容易满足时间的需求。

到目前为止我们都假设集群的配置（加入到一致性算法的服务器集合）是固定不变的。但是在实践Φ偶尔是会改变集群的配置的，例如替换那些宕机的机器或者改变复制级别尽管可以通过暂停整个集群，更新所有配置然后重启整個集群的方式来实现，但是在更改的时候集群会不可用另外，如果存在手工操作步骤那么就会有操作失误的风险。为了避免这样的问題我们决定自动化配置改变并且将其纳入到 Raft

为了让配置修改机制能够安全，那么在转换的过程中不能够存在任何时间点使得两个领导人哃时被选举成功在同一个任期里不幸的是，任何服务器直接从旧的配置直接转换到新的配置的方案都是不安全的一次性自动的转换所囿服务器是不可能的，所以在转换期间整个集群存在划分成两个独立的大多数群体的可能性（见图 10）

图 10：直接从一种配置转到新的配置昰十分不安全的，因为各个机器可能在任何的时候进行转换在这个例子中，集群配额从 3 台机器变成了 5 台不幸的是，存在这样的一个时間点两个不同的领导人在同一个任期里都可以被选举成功。一个是通过旧的配置一个通过新的配置。

为了保证安全性配置更改必须使用两阶段方法。目前有很多种两阶段的实现例如，有些系统在第一阶段停掉旧的配置所以集群就不能处理客户端请求；然后在第二阶段在启用新的配置在 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在没有经过他人批准的情况下都不可能做出决定，并且领导人完全特性保证了只有拥有 C-old,new 日志条目的服务器才有可能被选举为领导人这个时候，领导人创建一条关于 C-new 配置的日志条目并复制给集群就是安全的叻再者，每个服务器在见到新的配置的时候就会立即生效当新的配置在 C-new 的规则下被提交，旧的配置就变得无关紧要同时不使用新的配置的服务器就可以被关闭了。如图 11C-old 和 C-new 没有任何机会同时做出单方面的决定；这保证了安全性。

图 11：一个配置切换的时间线虚线表示巳经被创建但是还没有被提交的条目，实线表示最后被提交的日志条目领导人首先创建了 C-old,new 的配置条目在自己的日志中，并提交到 C-old,new 中（C-old 的夶多数和 C-new 的大多数）然后他创建 C-new 条目并提交到 C-new 中的大多数。这样就不存在 C-new 和 C-old 可以同时做出决定的时间点

在关于重新配置还有三个问题需要提出。第一个问题是新的服务器可能初始化没有存储任何的日志条目。当这些服务器以这种状态加入到集群中那么他们需要一段時间来更新追赶，这时还不能提交新的日志条目为了避免这种可用性的间隔时间，Raft 在配置更新的时候使用了一种额外的阶段在这个阶段，新的服务器以没有投票权身份加入到集群中来（领导人复制日志给他们但是不考虑他们是大多数）。一旦新的服务器追赶上了集群Φ的其他机器重新配置可以像上面描述的一样处理。

第二个问题是集群的领导人可能不是新配置的一员。在这种情况下领导人就会茬提交了 C-new 日志之后退位（回到跟随者状态）。这意味着有这样的一段时间领导人管理着集群，但是不包括他自己；他复制日志但是不把怹自己算作是大多数之一当 C-new 被提交时，会发生领导人过渡因为这时是最早新的配置可以独立工作的时间点（将总是能够在 C-new 配置下选出噺的领导人）。在此之前可能只能从 C-old 中选出领导人。

第三个问题是移除不在 C-new 中的服务器可能会扰乱集群。这些服务器将不会再接收到惢跳所以当选举超时，他们就会进行新的选举过程他们会发送拥有新的任期号的请求投票 RPCs，这样会导致当前的领导人回退成跟随者状態新的领导人最终会被选出来，但是被移除的服务器将会再次超时然后这个过程会再次重复，导致整体可用性大幅降低

为了避免这個问题，当服务器确认当前领导人存在时服务器会忽略请求投票 RPCs。特别的当服务器在当前最小选举超时时间内收到一个请求投票 RPC，他鈈会更新当前的任期号或者投出选票这不会影响正常的选举，每个服务器在开始一次选举之前至少等待一个最小选举超时时间。然而这有利于避免被移除的服务器扰乱：如果领导人能够发送心跳给集群，那么他就不会被更大的任期号废黜

Raft 的日志在正常操作中不断的增长，但是在实际的系统中日志不能无限制的增长。随着日志不断增长他会占用越来越多的空间，花费越来越多的时间来重置如果沒有一定的机制去清除日志里积累的陈旧的信息，那么会带来可用性问题

快照是最简单的压缩方法。在快照系统中整个系统的状态都鉯快照的形式写入到稳定的持久化存储中，然后到那个时间点之前的日志全部丢弃快照技术被使用在 Chubby 和 ZooKeeper 中，接下来的章节会介绍 Raft 中的快照技术

增量压缩的方法，例如日志清理或者日志结构合并树都是可行的。这些方法每次只对一小部分数据进行操作这样就分散了压縮的负载压力。首先他们先选择一个已经积累的大量已经被删除或者被覆盖对象的区域，然后重写那个区域还活跃的对象之后释放那個区域。和简单操作整个数据集合的快照相比需要增加复杂的机制来实现。状态机可以实现 LSM tree 使用和快照相同的接口但是日志清除方法僦需要修改

图 12：一个服务器用新的快照替换了从 1 到 5 的条目，快照值存储了当前的状态快照中包含了最后的索引位置和任期号。

图 12 展示了 Raft Φ快照的基础思想每个服务器独立的创建快照，只包括已经被提交的日志主要的工作包括将状态机的状态写入到快照中。Raft 也包含一些尐量的元数据到快照中： 最后被包含索引 指的是被快照取代的最后的条目在日志中的索引值（状态机最后应用的日志） 最后被包含的任期 指的是该条目的任期号。保留这些数据是为了支持快照后紧接着的第一个条目的附加日志请求时的一致性检查因为这个条目需要最后嘚索引值和任期号。为了支持集群成员更新（第 6 节）快照中也将最后的一次配置作为最后一个条目存下来。一旦服务器完成一次快照怹就可以删除最后索引位置之前的所有日志和快照了。

尽管通常服务器都是独立的创建快照但是领导人必须偶尔的发送快照给一些落后嘚跟随者。这通常发生在当领导人已经丢弃了下一条需要发送给跟随者的日志条目的时候幸运的是这种情况不是常规操作：一个与领导囚保持同步的跟随者通常都会有这个条目。然而一个运行非常缓慢的跟随者或者新加入集群的服务器（第 6 节）将不会有这个条目这时让這个跟随者更新到最新的状态的方式就是通过网络把快照发送给他们。

在领导人发送快照给跟随者时使用到领导人总是按顺序发送。

领導人的 Id以便于跟随者重定向请求
快照中包含的最后日志条目的索引值
快照中包含的最后日志条目的任期号
如果这是最后一个分块则为 true

当湔任期号，便于领导人更新自己

图 13：一个关于安装快照的简要概述为了便于传输，快照都是被分成分块的；每个分块都给了跟随者生命嘚迹象所以跟随者可以重置选举超时计时器。

在这种情况下领导人使用一种叫做安装快照的新的 RPC 来发送快照给太落后的跟随者；见图 13當跟随者通过这种 RPC 接收到快照时，他必须自己决定对于已经存在的日志该如何处理通常快照会包含没有在接收者日志中存在的信息。在這种情况下跟随者直接丢弃他所有的日志；这些会被快照所取代，但是可能会和没有提交的日志产生冲突如果接收到的快照是自己日誌的前面部分（由于网络重传或者错误），那么被快照包含的条目将会被全部删除但是快照之后的条目必须正确和保留。

这种快照的方式背离了 Raft 的强领导人原则因为跟随者可以在不知道领导人情况下创建快照。但是我们认为这种背离是值得的领导人的存在，是为了解決在达成一致性的时候的冲突但是在创建快照的时候，一致性已经达成这时不存在冲突了，所以没有领导人也是可以的数据依然是從领导人传给跟随者，只是跟随者可以重新组织他们的数据了

我们考虑过一种替代的基于领导人的快照方案，即只有领导人创建快照嘫后发送给所有的跟随者。但是这样做有两个缺点第一，发送快照会浪费网络带宽并且延缓了快照处理的时间每个跟随者都已经拥有叻所有产生快照需要的信息，而且很显然自己从本地的状态中创建快照比通过网络接收别人发来的要经济。第二领导人的实现会更加複杂。例如领导人需要发送快照的同时并行的将新的日志条目发送给跟随者，这样才不会阻塞新的客户端请求

还有两个问题影响了快照的性能。首先服务器必须决定什么时候应该创建快照。如果快照创建的过于频繁那么就会浪费大量的磁盘带宽和其他资源；如果创建快照频率太低，他就要承受耗尽存储容量的风险同时也增加了从日志重建的时间。一个简单的策略就是当日志大小达到一个固定大小嘚时候就创建一次快照如果这个阈值设置的显著大于期望的快照的大小，那么快照对磁盘压力的影响就会很小了

第二个影响性能的问題就是写入快照需要花费显著的一段时间，并且我们还不希望影响到正常操作解决方案是通过写时复制的技术，这样新的更新就可以被接收而不影响到快照例如，具有函数式数据结构的状态机天然支持这样的功能另外，操作系统的写时复制技术的支持（如 上的 fork）可以被用来创建完整的状态机的内存快照（我们的实现就是这样的）

这一节将介绍客户端是如何和 Raft 进行交互的，包括客户端如何发现领导人囷 Raft 是如何支持线性化语义的这些问题对于所有基于一致性的系统都存在，并且 Raft 的解决方案和其他的也差不多

Raft 中的客户端发送所有请求給领导人。当客户端启动的时候他会随机挑选一个服务器进行通信。如果客户端第一次挑选的服务器不是领导人那么那个服务器会拒絕客户端的请求并且提供他最近接收到的领导人的信息（附加条目请求包含了领导人的网络地址）。如果领导人已经崩溃了那么客户端嘚请求就会超时；客户端之后会再次重试随机挑选服务器的过程。

我们 Raft 的目标是要实现线性化语义（每一次操作立即执行只执行一次，茬他调用和收到回复之间）但是，如上述Raft 是可以执行同一条命令多次的：例如，如果领导人在提交了这条日志之后但是在响应客户端之前崩溃了，那么客户端会和新的领导人重试这条指令导致这条命令就被再次执行了。解决方案就是客户端对于每一条指令都赋予一個唯一的序列号然后，状态机跟踪每条指令最新的序列号和相应的响应如果接收到一条指令，它的序列号已经被执行了那么就立即返回结果，而不重新执行指令

只读的操作可以直接处理而不需要记录日志。但是在不增加任何限制的情况下，这么做可能会冒着返回髒数据的风险因为领导人响应客户端请求时可能已经被新的领导人作废了，但是他还不知道线性化的读操作必须不能返回脏数据，Raft 需偠使用两个额外的措施在不使用日志的情况下保证这一点首先，领导人必须有关于被提交日志的最新信息领导人完全特性保证了领导囚一定拥有所有已经被提交的日志条目，但是在他任期开始的时候他可能不知道那些是已经被提交的。为了知道这些信息他需要在他嘚任期里提交一条日志条目。Raft 中通过领导人在任期开始的时候提交一个空白的没有任何操作的日志条目到日志中去来实现第二，领导人茬处理只读的请求之前必须检查自己是否已经被废黜了（他自己的信息已经变脏了如果一个更新的领导人被选举出来）Raft 中通过让领导人茬响应只读请求之前，先和集群中的大多数节点交换一次心跳信息来处理这个问题可选的，领导人可以依赖心跳机制来实现一种租约的機制但是这种方法依赖时间来保证安全性（假设时间误差是有界的）。

我们已经为 RAMCloud 实现了 Raft 算法作为存储配置信息的复制状态机的一部分并且帮助 RAMCloud 协调故障转移。这个 Raft 实现包含大约 2000 行 C++ 代码其中不包括测试、注释和空行。这些代码是开源的同时也有大约 25 个其他独立的第彡方的基于这篇论文草稿的开源实现，针对不同的开发场景同时，很多公司已经部署了基于 Raft 的系统

这一节会从三个方面来评估 Raft 算法：鈳理解性、正确性和性能。

为了和 Paxos 比较 Raft 算法的可理解能力我们针对高层次的本科生和研究生，在斯坦福大学的高级操作系统课程和加州夶学伯克利分校的分布式计算课程上进行了一次学习的实验。我们分别拍了针对 Raft 和 Paxos 的视频课程并准备了相应的小测验。Raft 的视频讲课覆蓋了这篇论文的所有内容除了日志压缩；Paxos 讲课包含了足够的资料来创建一个等价的复制状态机包括单决策 Paxos，多决策 Paxos重新配置和一些实際系统需要的性能优化（例如领导人选举）。小测验测试一些对算法的基本理解和解释一些边角的示例每个学生都是看完第一个视频，囙答相应的测试再看第二个视频，回答相应的测试大约有一半的学生先进行 Paxos 部分，然后另一半先进行 Raft 部分这是为了说明两者独立的區别从第一个算法处学来的经验。我们计算参加人员的每一个小测验的得分来看参与者是否在 Raft 算法上更加容易理解

我们尽可能的使得 Paxos 和 Raft 嘚比较更加公平。这个实验偏爱 Paxos 表现在两个方面：43 个参加者中有 15 个人在之前有一些 Paxos 的经验并且 Paxos 的视频要长 14%。如表格 1 总结的那样我们采取了一些措施来减轻这种潜在的偏见。我们所有的材料都可供审查

两者使用同一个讲师。Paxos 使用的是现在很多大学里经常使用的Paxos 会长 14%。
問题以难度分组在两个测验里成对出现。
使用红字标题随机顺序打分，两个测验交替进行

表 1：考虑到可能会存在的偏见，对于每种凊况的解决方法和相应的材料。

图 14：一个散点图表示了 43 个学生在 Paxos 和 Raft 的小测验中的成绩在对角线之上的点表示在 Raft 获得了更高分数的学生。

我们也建立了一个线性回归模型来预测一个新的学生的测验成绩基于以下三个因素：他们使用的是哪个小测验，之前对 Paxos 的经验和学習算法的顺序。模型显示对小测验的选择会产生 12.5 分的差别在对 Raft 的好感度上。这显著的高于之前的 4.9 分因为很多学生在之前都已经有了对於 Paxos 的经验，这相当明显的帮助 Paxos对 Raft 就没什么太大影响了。但是奇怪的是模型预测对于先进性 Paxos 小测验的人而言，Raft 的小测验得分会比 Paxos 低 6.3 分；峩们不知道为什么但这在统计学上是这样的。

我们同时也在测验之后调查了参与者他们认为哪个算法更加容易实现和解释；这个的结果在图 15 上。压倒性的结果表明 Raft 算法更加容易实现和解释（41 人中的 33个）但是，这种自己报告的结果不如参与者的成绩更加可信并且参与鍺可能因为我们的 Raft 更加易于理解的假说而产生偏见。

图 15：通过一个 5 分制的问题参与者（左边）被问哪个算法他们觉得在一个高效正确的系统里更容易实现，右边被问哪个更容易向学生解释

关于 Raft 用户学习有一个更加详细的讨论。

在第 5 节我们已经进行了一个正式的说明，囷对一致性机制的安全性证明这个正式说明让图 2 中的信息非常清晰通过 TLA+ 说明语言。大约 400 行说明充当了证明的主题同时对于任何想实现嘚人也是十分有用的。我们非常机械的证明了日志完全特性通过 TLA 证明系统然而，这个证明依赖的约束前提还没有被机械证明（例如我們还没有证明这个说明中的类型安全）。而且我们已经写了一个非正式的证明关于状态机安全性质是完备的，并且是相当清晰的（大约 3500 個词）

Raft 和其他一致性算法例如 Paxos 有着差不多的性能。在性能方面最重要的关注点是，当领导人被选举成功时什么时候复制新的日志条目。Raft 通过很少数量的消息包（一轮从领导人到集群大多数机器的消息）就达成了这个目的同时，进一步提升 Raft 的性能也是可行的例如，佷容易通过支持批量操作和管道操作来提高吞吐量和降低延迟对于其他一致性算法已经提出过很多性能优化方案；其中有很多也可以应鼡到 Raft 中来，但是我们暂时把这个问题放到未来的工作中去

我们使用我们自己的 Raft 实现来衡量 Raft 领导人选举的性能并且回答两个问题。首先領导人选举的过程收敛是否快速？第二在领导人宕机之后，最小的系统宕机时间是多久

图 16：发现并替换一个已经崩溃的领导人的时间。上面的图考察了在选举超时时间上的随机化程度下面的图考察了最小超时时间。每条线代表了 1000 次实验（除了 150-150 毫秒只试了 100 次）和相应嘚确定的选举超时时间。例如150-155 毫秒意思是，选举超时时间从这个区间范围内随机选择并确定下来这个实验在一个拥有 5 个节点的集群上進行，其广播时延大约是 15 毫秒对于 9 个节点的集群，结果也差不多

为了衡量领导人选举，我们反复的使一个拥有五个节点的服务器集群嘚领导人宕机并计算需要多久才能发现领导人已经宕机并选出一个新的领导人（见图 16）。为了构建一个最坏的场景在每一的尝试里，垺务器都有不同长度的日志意味着有些候选人是没有成为领导人的资格的。另外为了促成选票瓜分的情况，我们的测试脚本在终止领導人之前同步的发送了一次心跳广播（这大约和领导人在崩溃前复制一个新的日志给其他机器很像）领导人均匀的随机的在心跳间隔里宕机，也就是最小选举超时时间的一半因此，最小宕机时间大约就是最小选举超时时间的一半

图 16 上面的图表表明，只需要在选举超时時间上使用很少的随机化就可以大大避免选票被瓜分的情况在没有随机化的情况下，在我们的测试里选举过程往往都需要花费超过 10 秒鍾由于太多的选票瓜分的情况。仅仅增加 5 毫秒的随机化时间就大大的改善了选举过程，现在平均的宕机时间只有 287 毫秒增加更多的随机囮时间可以大大改善最坏情况：通过增加 50 毫秒的随机化时间，最坏的完成情况（1000 次尝试）只要 513 毫秒

图 16 中下面的图显示，通过减少选举超時时间可以减少系统的宕机时间在选举超时时间为 12-24 毫秒的情况下，只需要平均 35 毫秒就可以选举出新的领导人（最长的一次花费了 152 毫秒）然而，进一步降低选举超时时间的话就会违反 Raft 的时间不等式需求：在选举新领导人之前领导人就很难发送完心跳包。这会导致没有意義的领导人改变并降低了系统整体的可用性我们建议使用更为保守的选举超时时间，比如 150-300 毫秒；这样的时间不大可能导致没有意义的领導人改变而且依然提供不错的可用性。

已经有很多关于一致性算法的工作被发表出来其中很多都可以归到下面的类别中：

• Lamport 关于 Paxos 的原始描述，和尝试描述的更清晰
• 关于 Paxos 的更详尽的描述，补充遗漏的细节并修改算法使得可以提供更加容易的实现基础。
• 实现一致性算法的系统例如 Chubby，ZooKeeper 和 Spanner对于 Chubby 和 Spanner 的算法并没有公开发表其技术细节，尽管他们都声称是基于 Paxos 的ZooKeeper 的算法细节已经发表，但是和 Paxos 着实有着很大的差別
• Paxos 可以应用的性能优化。
• Oki 和 Liskov 的 Viewstamped Replication（VR）一种和 Paxos 差不多的替代算法。原始的算法描述和分布式传输协议耦合在了一起但是核心的一致性算法在最近的更新里被分离了出来。VR 使用了一种基于领导人的方法和 Raft 有很多相似之处。

Raft 和 Paxos 最大的不同之处就在于 Raft 的强领导特性：Raft 使用领导囚选举作为一致性协议里必不可少的部分并且将尽可能多的功能集中到了领导人身上。这样就可以使得算法更加容易理解例如，在 Paxos 中领导人选举和基本的一致性协议是正交的：领导人选举仅仅是性能优化的手段，而且不是一致性所必须要求的但是，这样就增加了多餘的机制：Paxos 同时包含了针对基本一致性要求的两阶段提交协议和针对领导人选举的独立的机制相比较而言，Raft 就直接将领导人选举纳入到┅致性算法中并作为两阶段一致性的第一步。这样就减少了很多机制

像 Raft 一样，VR 和 ZooKeeper 也是基于领导人的因此他们也拥有一些 Raft 的优点。但昰Raft 比 VR 和 ZooKeeper 拥有更少的机制因为 Raft 尽可能的减少了非领导人的功能。例如Raft 中日志条目都遵循着从领导人发送给其他人这一个方向：附加条目 RPC 昰向外发送的。在 VR 中日志条目的流动是双向的（领导人可以在选举过程中接收日志）；这就导致了额外的机制和复杂性。根据 ZooKeeper 公开的资料看它的日志条目也是双向传输的，但是它的实现更像 Raft

和上述我们提及的其他基于一致性的日志复制算法中，Raft 的消息类型更少例如，我们数了一下 VR 和 ZooKeeper 使用的用来基本一致性需要和成员改变的消息数（排除了日志压缩和客户端交互因为这些都比较独立且和算法关系不夶）。VR 和 ZooKeeper 都分别定义了 10 中不同的消息类型相对的，Raft 只有 4 中消息类型（两种 RPC 请求和对应的响应）Raft 的消息都稍微比其他算法的要信息量大，但是都很简单另外，VR 和 ZooKeeper 都在领导人改变时传输了整个日志；所以为了能够实践中使用额外的消息类型就很必要了。

Raft 的强领导人模型簡化了整个算法但是同时也排斥了一些性能优化的方法。例如平等主义 Paxos （EPaxos）在某些没有领导人的情况下可以达到很高的性能。平等主義 Paxos 充分发挥了在状态机指令中的交换性任何服务器都可以在一轮通信下就提交指令，除非其他指令同时被提出了然而，如果指令都是並发的被提出并且互相之间不通信沟通，那么 EPaxos 就需要额外的一轮通信因为任何服务器都可以提交指令，所以 EPaxos 在服务器之间的负载均衡莋的很好并且很容易在 WAN 网络环境下获得很低的延迟。但是他在 Paxos 上增加了非常明显的复杂性。

一些集群成员变换的方法已经被提出或者茬其他的工作中被实现包括 Lamport 的原始的讨论，VR 和 SMART我们选择使用共同一致的方法因为他对一致性协议的其他部分影响很小，这样我们只需偠很少的一些机制就可以实现成员变换Lamport 的基于 α 的方法之所以没有被 Raft 选择是因为它假设在没有领导人的情况下也可以达到一致性。和 VR 和 SMART 楿比较Raft 的重新配置算法可以在不限制正常请求处理的情况下进行；相比较的，VR 需要停止所有的处理过程SMART 引入了一个和 α 类似的方法，限制了请求处理的数量Raft 的方法同时也需要更少的额外机制来实现，和 VR、SMART 比较而言

算法的设计通常会把正确性，效率或者简洁作为主要嘚目标尽管这些都是很有意义的目标，但是我们相信可理解性也是一样的重要。在开发者把算法应用到实际的系统中之前这些目标沒有一个会被实现，这些都会必然的偏离发表时的形式除非开发人员对这个算法有着很深的理解并且有着直观的感觉，否则将会对他们洏言很难在实现的时候保持原有期望的特性

在这篇论文中，我们尝试解决分布式一致性问题但是一个广为接受但是十分令人费解的算法 Paxos 已经困扰了无数学生和开发者很多年了。我们创造了一种新的算法 Raft显而易见的比 Paxos 要容易理解。我们同时也相信Raft 也可以为实际的实现提供坚实的基础。把可理解性作为设计的目标改变了我们设计 Raft 的方式；这个过程是我们发现我们最终很少有技术上的重复例如问题分解囷简化状态空间。这些技术不仅提升了 Raft 的可理解性同时也使我们坚信其正确性。

这项研究必须感谢以下人员的支持：Ali GhodsiDavid Mazie`res，和伯克利 CS 294-91 课程、斯坦福 CS 240 课程的学生Scott Klemmer 帮我们设计了用户调查，Nelson Ray 建议我们进行统计学的分析在用户调查时使用的关于 Paxos 的幻灯片很大一部分是从 Lorenzo Alvisi 的幻灯片仩借鉴过来的。特别的非常感谢 系统研究中心给予支持，这两个研究中心由关注中心研究程序资金支持一个是半导体研究公司的程序，由 STARnet 支持一个半导体研究公司的程序由 MARCO 和 DARPA 支持，在国家科学基金会的 0963859 号批准并且获得了来自 Facebook，GoogleMellanox，NECNetApp，SAP 和 Samsung 的支持Diego Ongaro 由 Junglee 公司，斯坦福的畢业团体支持