寻找⼀一种易易于理理解的⼀一致性算法（扩展版）

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

1 介绍⼀一致性算法允许⼀一组机器器像⼀一个整体⼀一样⼯工作，即使其中⼀一些机器器出现故障也能够继续⼯工作下去。正因为如此，⼀一致性算法在构建可信赖的⼤大规模软件系统中扮演着重要的⻆角⾊色。在过去的 10 年年⾥里里，Paxos 算法统治着⼀一致性算法这⼀一领域：绝⼤大多数的实现都是基于 Paxos 或者受其影响。同时 Paxos 也成为了了教学领域⾥里里讲解⼀一致性问题时的示例例。但是不不幸的是，尽管有很多⼯工作都在尝试降低它的复杂性，但是 Paxos 算法依然⼗十分难以理理解。并且，Paxos ⾃自身的算法结构需要进⾏行行⼤大幅的修改才能够应⽤用到实际的系统中。这些都导致了了⼯工业界和学术界都对 Paxos 算法感到⼗十分头疼。和 Paxos 算法进⾏行行过努⼒力力之后，我们开始寻找⼀一种新的⼀一致性算法，可以为构建实际的系统和教学提供更更好的基础。我们的做法是不不寻常的，我们的⾸首要⽬目标是可理理解性：我们是否可以在实际系统中定义⼀一个⼀一致性算法，并且能够⽐比 Paxos 算法以⼀一种更更加容易易的⽅方式来学习。此外，我们希望该算法⽅方便便系统构建者的直觉的发展。不不仅⼀一个算法能够⼯工作很重要，⽽而且能够显⽽而易易⻅见的知道为什什么能⼯工作也很重要。Raft ⼀一致性算法就是这些⼯工作的结果。在设计 Raft 算法的时候，我们使⽤用⼀一些特别的技巧来提升它的可理理解性，包括算法分解（Raft 主要被分成了了领导⼈人选举，⽇日志复制和安全三个模块）和减少状态机的状态（相对于 Paxos，Raft 减少了了⾮非确定性和服务器器互相处于⾮非⼀一致性的⽅方式）。⼀一份针对两所⼤大学 43 个学⽣生的研究表明 Raft 明显⽐比 Paxos 算法更更加容易易理理解。在这些学⽣生同时学习了了这两种算法之后，和 Paxos ⽐比起来，其中 33 个学⽣生能够回答有关于 Raft 的问题。Raft 算法在许多⽅方⾯面和现有的⼀一致性算法都很相似（主要是 Oki 和 Liskov 的 Viewstamped Replication），但是它也有⼀一些独特的特性：

• 强领导者：和其他⼀一致性算法相⽐比，Raft 使⽤用⼀一种更更强的领导能⼒力力形式。⽐比如，⽇日志条⽬目只从领导者发送给其他的服务器器。这种⽅方式简化了了对复制⽇日志的管理理并且使得 Raft 算法更更加易易于理理解。

• 领导选举：Raft 算法使⽤用⼀一个随机计时器器来选举领导者。这种⽅方式只是在任何⼀一致性算法都必须实现的⼼心跳机制上增加了了⼀一点机制。在解决冲突的时候会更更加简单快捷。

• 成员关系调整：Raft 使⽤用⼀一种共同⼀一致的⽅方法来处理理集群成员变换的问题，在这种⽅方法下，处于调整过程中的两种不不同的配置集群中⼤大多数机器器会有重叠，这就使得集群在成员变换的时候依然可以继续⼯工作。

我们相信，Raft 算法不不论出于教学⽬目的还是作为实践项⽬目的基础都是要⽐比 Paxos 或者其他⼀一致性算法要优异的。它⽐比其他算法更更加简单，更更加容易易理理解；它的算法描述⾜足以实现⼀一个现实的系统；它有好多开源的实现并且在很多公司⾥里里使⽤用；它的安全性已经被证明；它的效率和其他算法⽐比起来也不不相上下。接下来，这篇论⽂文会介绍以下内容：复制状态机问题（第 2 节），讨论 Paxos 的优点和缺点（第 3 节），讨论我们为了了可理理解性⽽而采取的⽅方法（第 4 节），阐述 Raft ⼀一致性算法（第 5-8 节），评价 Raft 算法（第 9 节），以及⼀一些相关的⼯工作（第 10 节）。

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

复制状态机通常都是基于复制⽇日志实现的，如图 1。顺序执⾏行行相同指令序列列导致结果⼀一致。所以我们要保证⽇日志相同并且顺序⼀一致实际系统中使⽤用的⼀一致性算法通常含有以下特性：

• 安全性保证（绝对不不会返回⼀一个错误的结果）：在⾮非拜占庭错误情况下，包括⽹网络延迟、分区、丢包、冗余和乱序等错误都可以保证正确。

• 可⽤用性：集群中只要有⼤大多数的机器器可运⾏行行并且能够相互通信、和客户端通信，就可以保证可⽤用。因此，⼀一个典型的包含 5 个节点的集群可以容忍两个节点的失败。服务器器被停⽌止就认为是失败。他们当有稳定的存储的时候可以从状态中恢复回来并重新加⼊入集群。

• 不不依赖时序来保证⼀一致性：物理理时钟错误或者极端的消息延迟只有在最坏情况下才会导致可⽤用性问题。

• 通常情况下，⼀一条指令可以尽可能快的在集群中⼤大多数节点响应⼀一轮远程过程调⽤用时完成。⼩小部分⽐比较慢的节点不不会影响系统整体的性能。

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

不不幸的是，Paxos 有两个明显的缺点。第⼀一个缺点是 Paxos 算法特别的难以理理解。我们假设 Paxos 的不不透明性来⾃自它选择单决策问题作为它的基础。单决策 Paxos 是晦涩微妙的，它被划分成了了两种没有简单直观解释和⽆无法独⽴立理理解的情景。因此，这导致了了很难建⽴立起直观的感受为什什么单决策 Paxos 算法能够⼯工作。构成多决策 Paxos 增加了了很多错综复杂的规则。我们相信，在多决策上达成⼀一致性的问题（⼀一份⽇日志⽽而不不是单⼀一的⽇日志记录）能够被分解成其他的⽅方式并且更更加直接和明显。Paxos算法的第⼆二个问题就是它没有提供⼀一个⾜足够好的⽤用来构建⼀一个现实系统的基础。⼀一个原因是还没有⼀一种被⼴广泛认同的多决策问题的算法。Lamport 的描述基本上都是关于单决策 Paxos 的；他简要描述了了实施多决策 Paxos 的⽅方法，但是缺乏很多细节。当然也有很多具体化 Paxos 的尝试，但是他们都互相不不⼀一样，和 Paxos 的概述也不不同。例例如 Chubby 这样的系统实现了了⼀一个类似于 Paxos 的算法，但是⼤大多数的细节并没有被公开。⽽而且，Paxos 算法的结构也不不是⼗十分易易于构建实践的系统；单决策分解也会产⽣生其他的结果。例例如，独⽴立的选择⼀一组⽇日志条⽬目然后合并成⼀一个序列列化的⽇日志并没有带来太多的好处，仅仅增加了了不不少复杂性。围绕着⽇日志来设计⼀一个系统是更更加简单⾼高效的；新⽇日志条⽬目以严格限制的顺序增添到⽇日志中去。另⼀一个问题是，Paxos 使⽤用了了⼀一种对等的点对点的⽅方式作为它的核⼼心（尽管它最终提议了了⼀一种弱领导⼈人的⽅方法来优化性能）。在只有⼀一个决策会被制定的简化世界中是很有意义的，但是很少有现实的系统使⽤用这种⽅方式。如果有⼀一系列列的决策需要被制定，⾸首先选择⼀一个领导⼈人，然后让他去协调所有的决议，会更更加简单快速。因此，实际的系统中很少有和 Paxos 相似的实践。每⼀一种实现都是从 Paxos 开始研究，然后发现很多实现上的难题，再然后开发了了⼀一种和 Paxos 明显不不⼀一样的结构。这样是⾮非常费时和容易易出错的，并且理理解 Paxos 的难度使得这个问题更更加糟糕。Paxos 算法在理理论上被证明是正确可⾏行行的，但是现实的系统和 Paxos 差别是如此的⼤大，以⾄至于这些证明没有什什么太⼤大的价值。下⾯面来⾃自 Chubby 实现⾮非常典型：在Paxos算法描述和实现现实系统中间有着巨⼤大的鸿沟。最终的系统建⽴立在⼀一种没有经过证明的算法之上。由于以上问题，我们认为 Paxos 算法既没有提供⼀一个良好的基础给实践的系统，也没有给教学很好的帮助。基于⼀一致性问题在⼤大规模软件系统中的重要性，我们决定看看我们是否可以设计⼀一个拥有更更好特性的替代 Paxos 的⼀一致性算法。Raft算法就是这次实验的结果。

4 为了了可理理解性的设计

设计 Raft 算法我们有⼏几个初衷：它必须提供⼀一个完整的实际的系统实现基础，这样才能⼤大⼤大减少开发者的⼯工作；它必须在任何情况下都是安全的并且在⼤大多数的情况下都是可⽤用的；并且它的⼤大部分操作必须是⾼高效的。但是我们最重要也是最⼤大的挑战是可理理解性。它必须保证对于普遍的⼈人群都可以⼗十分容易易的去理理解。另外，它必须能够让⼈人形成直观的认识，这样系统的构建者才能够在现实中进⾏行行必然的扩展。在设计 Raft 算法的时候，有很多的点需要我们在各种备选⽅方案中进⾏行行选择。在这种情况下，我们评估备选⽅方案基于可理理解性原则：解释各个备选⽅方案有多⼤大的难度（例例如，Raft 的状态空间有多复杂，是否有微妙的暗示）？对于⼀一个读者⽽而⾔言，完全理理解这个⽅方案和暗示是否容易易？我们意识到对这种可理理解性分析上具有⾼高度的主观性；尽管如此，我们使⽤用了了两种通常适⽤用的技术来解决这个问题。第⼀一个技术就是众所周知的问题分解：只要有可能，我们就将问题分解成⼏几个相对独⽴立的，可被解决的、可解释的和可理理解的⼦子问题。例例如，Raft 算法被我们分成领导⼈人选举，⽇日志复制，安全性和⻆角⾊色改变⼏几个部分。我们使⽤用的第⼆二个⽅方法是通过减少状态的数量量来简化需要考虑的状态空间，使得系统更更加连贯并且在可能的时候消除不不确定性。特别的，所有的⽇日志是不不允许有空洞洞的，并且 Raft 限制了了⽇日志之间变成不不⼀一致状态的可能。尽管在⼤大多数情况下我们都试图去消除不不确定性，但是也有⼀一些情况下不不确定性可以提升可理理解性。尤其是，随机化⽅方法增加了了不不确定性，但是他们有利利于减少状态空间数量量，通过处理理所有可能选择时使⽤用相似的⽅方法。我们使⽤用随机化去简化 Raft 中领导⼈人选举算法。

5 Raft ⼀一致性算法Raft 是⼀一种⽤用来管理理章节 2 中描述的复制⽇日志的算法。图 2 为了了参考之⽤用，总结这个算法的简略略版本，图 3 列列举了了这个算法的⼀一些关键特性。图中的这些元素会在剩下的章节逐⼀一介绍。Raft 通过选举⼀一个⾼高贵的领导⼈人，然后给予他全部的管理理复制⽇日志的责任来实现⼀一致性。领导⼈人从客户端接收⽇日志条⽬目，把⽇日志条⽬目复制到其他服务器器上，并且当保证安全性的时候告诉其他的服务器器应⽤用⽇日志条⽬目到他们的状态机中。拥有⼀一个领导⼈人⼤大⼤大简化了了对复制⽇日志的管理理。例例如，领导⼈人可以决定新的⽇日志条⽬目需要放在⽇日志中的什什么位置⽽而不不需要和其他服务器器商议，并且数据都从领导⼈人流向其他服务器器。⼀一个领导⼈人可以宕机，可以和其他服务器器失去连接，这时⼀一个新的领导⼈人会被选举出来。通过领导⼈人的⽅方式，Raft 将⼀一致性问题分解成了了三个相对独⽴立的⼦子问题，这些问题会在接下来的⼦子章节中进⾏行行讨论：

• 领导选举：⼀一个新的领导⼈人需要被选举出来，当现存的领导⼈人宕机的时候（章节 5.2）

• ⽇日志复制：领导⼈人必须从客户端接收⽇日志然后复制到集群中的其他节点，并且强制要求其他节点的⽇日志保持和⾃自⼰己相同。

• 安全性：在 Raft 中安全性的关键是在图 3 中展示的状态机安全：如果有任何的服务器器节点已经应⽤用了了⼀一个确定的⽇日志条⽬目到它的状态机中，那么其他服务器器节点不不能在同⼀一个⽇日志索引位置应⽤用⼀一个不不同的指令。章节 5.4 阐述了了 Raft 算法是如何保证这个特性的；这个解决⽅方案涉及到⼀一个额外的选举机制（5.2 节）上的限制。

在展示⼀一致性算法之后，这⼀一章节会讨论可⽤用性的⼀一些问题和计时在系统的作⽤用。状态：

状态 较⻓长时间不不变的

currentTerm

服务器器最后⼀一次知道的任期号（初始化为 0，持续递增）

votedFor 在当前获得选票的候选⼈人的 Id

log[]⽇日志条⽬目集；每⼀一个条⽬目包含⼀一个⽤用户状态机执⾏行行的指令，和收到时的任期号

状态 经常改变的

commitIndex 已知的最⼤大的已经被提交的⽇日志条⽬目的索引值

lastApplied

最后被应⽤用到状态机的⽇日志条⽬目索引值（初始化为 0，持续递增）

状态 在领导⼈人⾥里里经常改变的 （选举后重新初始化）

nextIndex[]

对于每⼀一个服务器器，需要发送给他的下⼀一个⽇日志条⽬目的索引值（初始化为领导⼈人最后索引值加⼀一）

附加⽇日志 RPC：由领导⼈人负责调⽤用来复制⽇日志指令；也会⽤用作heartbeat

接收者实现：1. 如果 term < currentTerm 就返回 false （5.1 节）2. 如果⽇日志在 prevLogIndex 位置处的⽇日志条⽬目的任期号和 prevLogTerm 不不匹配，则返回 false （5.3 节）

3. 如果已经存在的⽇日志条⽬目和新的产⽣生冲突（索引值相同但是任期号不不同），删除这⼀一条和之后所有的 （5.3 节）

4. 附加⽇日志中尚未存在的任何新条⽬目5. 如果 leaderCommit > commitIndex，令 commitIndex 等于

leaderCommit 和 新⽇日志条⽬目索引值中较⼩小的⼀一个

matchIndex[]

对于每⼀一个服务器器，已经复制给他的⽇日志的最⾼高索引值

参数 解释

term 领导⼈人的任期号

leaderId 领导⼈人的 Id，以便便于跟随者重定向请求

prevLogIndex 新的⽇日志条⽬目紧随之前的索引值

prevLogTerm prevLogIndex 条⽬目的任期号

entries[]准备存储的⽇日志条⽬目（表示⼼心跳时为空；⼀一次性发送多个是为了了提⾼高效率）

leaderCommit 领导⼈人已经提交的⽇日志的索引值

返回值 解释

term 当前的任期号，⽤用于领导⼈人去更更新⾃自⼰己

success

跟随者包含了了匹配上 prevLogIndex 和 prevLogTerm 的⽇日志时为真

请求投票 RPC：由候选⼈人负责调⽤用⽤用来征集选票（5.2 节）

接收者实现：1. 如果term < currentTerm返回 false （5.2 节）2. 如果 votedFor 为空或者为 candidateId，并且候选⼈人的⽇日志⾄至少和⾃自⼰己⼀一样新，那么就投票给他（5.2 节，5.4 节）

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

• 如果commitIndex > lastApplied，那么就 lastApplied 加⼀一，并把log[lastApplied]应⽤用到状态机中（5.3 节）

• 如果接收到的 RPC 请求或响应中，任期号T > currentTerm，那么就令 currentTerm 等于 T，并切换状态为跟随者（5.1 节）

跟随者（5.2 节）：• 响应来⾃自候选⼈人和领导者的请求• 如果在超过选举超时时间的情况之前都没有收到领导⼈人的⼼心跳，或者是候选⼈人请求投票的，就⾃自⼰己变成候选⼈人

候选⼈人（5.2 节）：• 在转变成候选⼈人后就⽴立即开始选举过程

◦ ⾃自增当前的任期号（currentTerm）◦ 给⾃自⼰己投票◦ 重置选举超时计时器器

参数 解释

term 候选⼈人的任期号

candidateId 请求选票的候选⼈人的 Id

lastLogIndex 候选⼈人的最后⽇日志条⽬目的索引值

lastLogTerm 候选⼈人最后⽇日志条⽬目的任期号

返回值 解释

term当前任期号，以便便于候选⼈人去更更新⾃自⼰己的任期号

voteGranted 候选⼈人赢得了了此张选票时为真

◦ 发送请求投票的 RPC 给其他所有服务器器• 如果接收到⼤大多数服务器器的选票，那么就变成领导⼈人• 如果接收到来⾃自新的领导⼈人的附加⽇日志 RPC，转变成跟随者• 如果选举过程超时，再次发起⼀一轮选举领导⼈人：

• ⼀一旦成为领导⼈人：发送空的附加⽇日志 RPC（⼼心跳）给其他所有的服务器器；在⼀一定的空余时间之后不不停的重复发送，以阻⽌止跟随者超时（5.2 节）

• 如果接收到来⾃自客户端的请求：附加条⽬目到本地⽇日志中，在条⽬目被应⽤用到状态机后响应客户端（5.3 节）

• 如果对于⼀一个跟随者，最后⽇日志条⽬目的索引值⼤大于等于 nextIndex，那么：发送从 nextIndex 开始的所有⽇日志条⽬目：◦ 如果成功：更更新相应跟随者的 nextIndex 和 matchIndex◦ 如果因为⽇日志不不⼀一致⽽而失败，减少 nextIndex 重试

• 如果存在⼀一个满⾜足N > commitIndex的 N，并且⼤大多数的matchIndex[i] ≥ N成⽴立，并且log[N].term == currentTerm成⽴立，那么令 commitIndex 等于这个 N （5.3 和 5.4 节）

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

特性 解释

选举安全特性

对于⼀一个给定的任期号，最多只会有⼀一个领导⼈人被选举出来（5.2 节）

领导⼈人只附加原则

领导⼈人绝对不不会删除或者覆盖⾃自⼰己的⽇日志，只会增加（5.3 节）

⽇日志匹配原则

如果两个⽇日志在相同的索引位置的⽇日志条⽬目的任期号相同，那么我们就认为这个⽇日志从头到这个索引位置之间全部完全相同（5.3 节）

领导⼈人完全特性

如果某个⽇日志条⽬目在某个任期号中已经被提交，那么这个条⽬目必然出现在更更⼤大任期号的所有领导⼈人中（5.4 节）

状态机安全特性

如果⼀一个领导⼈人已经在给定的索引值位置的⽇日志条⽬目应⽤用到状态机中，那么其他任何的服务器器在这个索引位置不不会提交⼀一个不不同的⽇日志（5.4.3 节）

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

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

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

图 5：时间被划分成⼀一个个的任期，每个任期开始都是⼀一次选举。在选举成功后，领导⼈人会管理理整个集群直到任期结束。有时候选举会失败，那么这个任期就会没有领导⼈人⽽而结束。任期之间的切换可以在不不同的时间不不同的服务器器上观察到。Raft 把时间分割成任意⻓长度的任期，如图 5。任期⽤用连续的整数标记。每⼀一段任期从⼀一次选举开始，就像章节 5.2 描述的⼀一样，⼀一个或者多个候选⼈人尝试成为领导者。如果⼀一个候选⼈人赢得选举，然后他就在接下来的任期内充当领导⼈人的职责。在某些情况下，⼀一次选举过程会造成选票的⽠瓜分。在这种情况下，这⼀一任期会以没有领导⼈人结束；⼀一个新的任期（和⼀一次新的选举）会很快重新开始。Raft 保证了了在⼀一个给定的任期内，最多只有⼀一个领导者。

不不同的服务器器节点可能多次观察到任期之间的转换，但在某些情况下，⼀一个节点也可能观察不不到任何⼀一次选举或者整个任期全程。任期在 Raft 算法中充当逻辑时钟的作⽤用，这会允许服务器器节点查明⼀一些过期的信息⽐比如陈旧的领导者。每⼀一个节点存储⼀一个当前任期号，这⼀一编号在整个时期内单调的增⻓长。当服务器器之间通信的时候会交换当前任期号；如果⼀一个服务器器的当前任期号⽐比其他⼈人⼩小，那么他会更更新⾃自⼰己的编号到较⼤大的编号值。如果⼀一个候选⼈人或者领导者发现⾃自⼰己的任期号过期了了，那么他会⽴立即恢复成跟随者状态。如果⼀一个节点接收到⼀一个包含过期的任期号的请求，那么他会直接拒绝这个请求。Raft 算法中服务器器节点之间通信使⽤用远程过程调⽤用（RPCs），并且基本的⼀一致性算法只需要两种类型的 RPCs。请求投票（RequestVote） RPCs 由候选⼈人在选举期间发起（章节 5.2），然后附加条⽬目（AppendEntries）RPCs 由领导⼈人发起，⽤用来复制⽇日志和提供⼀一种⼼心跳机制（章节 5.3）。第 7 节为了了在服务器器之间传输快照增加了了第三种 RPC。当服务器器没有及时的收到 RPC 的响应时，会进⾏行行重试， 并且他们能够并⾏行行的发起 RPCs 来获得最佳的性能。

5.2 领导⼈人选举Raft 使⽤用⼀一种⼼心跳机制来触发leader选举。当服务器器程序启动时，他们都是跟随者身份。如果从领导⼈人或者候选者处接收到有效的 RPCs，那么就⼀一直是跟随者。领导者周期性的向所有跟随者发送⼼心跳包（即不不包含⽇日志项内容的附加⽇日志项 RPCs）来维持⾃自⼰己的权威。如果⼀一个跟随者在⼀一段时间⾥里里没有接收到任何消息，也就是选举超时，那么他就会认为系统中没有可⽤用的领导者,并且发起选举以选出新的领导者。要开始⼀一次选举过程，跟随者先要增加⾃自⼰己的当前任期号并且转换到候选⼈人状态。然后他会并⾏行行的向集群中的其他服务器器节点发送请求投票的 RPCs 来给⾃自⼰己投票。候选⼈人会继续保持着当前状态直到以下三件事情之⼀一发⽣生：(a) 他⾃自⼰己赢得了了这次的选举，(b) 其他的服务器器成为领导者，(c) ⼀一段时间之后没有任何⼀一个获胜的⼈人。这些结果会分别的在下⾯面的段落⾥里里进⾏行行讨论。当⼀一个候选⼈人从整个集群的⼤大多数服务器器节点获得了了针对同⼀一个任期号的选票，那么他就赢得了了这次选举并成为领导⼈人。每⼀一个服务器器最多会对⼀一个任期号投出⼀一张选票，按照先来先服务的原则（注意：5.4 节在投票上增加了了⼀一点额外的限制）。要求⼤大多数选票的规则确保了了最多只会有⼀一个候选⼈人赢得此次选举（图 3 中的选举安全性）。⼀一旦候选⼈人赢得选举，他就⽴立即成为领导⼈人。然后他会向其他的服务器器发送⼼心跳消息来建⽴立⾃自⼰己的权威并且阻⽌止新的领导⼈人的产⽣生。在等待投票的时候，候选⼈人可能会从其他的服务器器接收到声明它是领导⼈人的附加⽇日志项 RPC。如果这个领导⼈人的任期号（包含在此次的 RPC中）不不⼩小于候

选⼈人当前的任期号，那么候选⼈人会承认领导⼈人合法并回到跟随者状态。 如果此次 RPC 中的任期号⽐比⾃自⼰己⼩小，那么候选⼈人就会拒绝这次的 RPC 并且继续保持候选⼈人状态。第三种可能的结果是候选⼈人既没有赢得选举也没有输：如果有多个跟随者同时成为候选⼈人，那么选票可能会被⽠瓜分以⾄至于没有候选⼈人可以赢得⼤大多数⼈人的⽀支持。当这种情况发⽣生的时候，每⼀一个候选⼈人都会超时，然后通过增加当前任期号来开始⼀一轮新的选举。然⽽而，没有其他机制的话，选票可能会被⽆无限的重复⽠瓜分。Raft 使⽤用随机超时时间的⽅方法来确保很少会发⽣生选票持平的情况，就算发⽣生也能很快的解决。为了了阻⽌止选票起初就被持平，选举超时时间是从⼀一个固定的区间（例例如 150-300 毫秒）随机选择。这样可以把服务器器都分散开以⾄至于在⼤大多数情况下只有⼀一个服务器器会选举超时；然后他赢得选举并在其他服务器器超时之前发送⼼心跳包。同样的机制被⽤用在选票持平的情况下。每⼀一个候选⼈人在开始⼀一次选举的时候会重置⼀一个随机的选举超时时间，然后在超时时间内等待投票的结果；这样减少了了在新的选举中另外的选票持平的可能性。9.3 节展示了了这种⽅方案能够快速的选出⼀一个领导⼈人。领导⼈人选举这个例例⼦子，体现了了可理理解性原则是如何指导我们进⾏行行⽅方案设计的。起初我们计划使⽤用⼀一种排名系统：每⼀一个候选⼈人都被赋予⼀一个唯⼀一的排名，供候选⼈人之间竞争时进⾏行行选择。如果⼀一个候选⼈人发现另⼀一个候选⼈人拥有更更⾼高的排名，那么他就会回到跟随者状态，这样⾼高排名的候选⼈人能够更更加容易易的赢得下⼀一次选举。但是我们发现这种⽅方法在可⽤用性⽅方⾯面会有⼀一点问题（如果⾼高排名的服务器器宕机了了，那么低排名的服务器器可能会超时并再次进⼊入候选⼈人状态。⽽而且如果这个⾏行行为发⽣生得⾜足够快，则可能会导致整个选举过程都被重置掉）。我们针对算法进⾏行行了了多次调整，但是每次调整之后都会有新的问题。最终我们认为随机重试的⽅方法是更更加明显和易易于理理解的。

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

图 6：⽇日志由有序序号标记的条⽬目组成。每个条⽬目都包含创建时的任期号（图中框中的数字），和⼀一个状态机需要执⾏行行的指令。⼀一个条⽬目当可以安全的被应⽤用到状态机中去的时候，就认为是可以提交了了。⽇日志以图 6 展示的⽅方式组织。每⼀一个⽇日志条⽬目包括：1.状态机指令2.从领导⼈人收到这条指令时的任期号⽇日志中的任期号⽤用来检查是否出现不不⼀一致的情况，同时也⽤用来保证图 3 中的某些性质。每⼀一条⽇日志条⽬目同时也都有⼀一个整数索引值来表明它在⽇日志中的位置。领导⼈人来决定什什么时候把⽇日志条⽬目应⽤用到状态机中是安全的；这种⽇日志条⽬目被称为已提交。Raft 算法保证所有已提交的⽇日志条⽬目都是持久化的并且最终会被所有可⽤用的状态机执⾏行行。在领导⼈人将创建的⽇日志条⽬目复制到⼤大多数的服务器器上的时候，⽇日志条⽬目就会被提交（例例如在图 6 中的条⽬目 7）。同时，领导⼈人的⽇日志中之前的所有⽇日志条⽬目也都会被提交，包括由其他领导⼈人创建的条⽬目。5.4 节会讨论某些当在领导⼈人改变之后应⽤用这条规则的隐晦内容，同时他也展示了了这种提交的定义是安全的。领导⼈人跟踪了了最⼤大的将会被提交的⽇日志项的索引，并且索引值会被包含在未来的所有附加⽇日志 RPCs （包括⼼心跳包），这样其他的服务器器才能最终知道领导⼈人的提交位置。⼀一旦跟随者知道⼀一条⽇日志条⽬目已经

被提交，那么他也会将这个⽇日志条⽬目应⽤用到本地的状态机中（按照⽇日志的顺序）。我们设计了了 Raft 的⽇日志机制来维护⼀一个不不同服务器器的⽇日志之间的⾼高层次的⼀一致性。这么做不不仅简化了了系统的⾏行行为也使得更更加可预计，同时他也是安全性保证的⼀一个重要组件。Raft 维护着以下的特性，这些同时也组成了了图 3 中的⽇日志匹配特性：

• 如果在不不同的⽇日志中的两个条⽬目拥有相同的索引和任期号，那么他们存储了了相同的指令。

• 如果在不不同的⽇日志中的两个条⽬目拥有相同的索引和任期号，那么他们之前的所有⽇日志条⽬目也全部相同。

第⼀一个特性来⾃自这样的⼀一个事实，领导⼈人最多在⼀一个任期⾥里里在指定的⼀一个⽇日志索引位置创建⼀一条⽇日志条⽬目，同时⽇日志条⽬目在⽇日志中的位置也从来不不会改变。第⼆二个特性由附加⽇日志 RPC 的⼀一个简单的⼀一致性检查所保证。在发送附加⽇日志 RPC 的时候，领导⼈人会把新的⽇日志条⽬目紧接着之前的条⽬目的索引位置和任期号包含在⾥里里⾯面。如果跟随者在它的⽇日志中找不不到包含相同索引位置和任期号的条⽬目，那么他就会拒绝接收新的⽇日志条⽬目。⼀一致性检查就像⼀一个归纳步骤：⼀一开始空的⽇日志状态肯定是满⾜足⽇日志匹配特性的，然后⼀一致性检查保护了了⽇日志匹配特性当⽇日志扩展的时候。因此，每当附加⽇日志 RPC 返回成功时，领导⼈人就知道跟随者的⽇日志⼀一定是和⾃自⼰己相同的了了。在正常的操作中，领导⼈人和跟随者的⽇日志保持⼀一致性，所以附加⽇日志 RPC 的⼀一致性检查从来不不会失败。然⽽而，领导⼈人崩溃的情况会使得⽇日志处于不不⼀一致的状态（⽼老老的领导⼈人可能还没有完全复制所有的⽇日志条⽬目）。这种不不⼀一致问题会在领导⼈人和跟随者的⼀一系列列崩溃下加剧。图 7 展示了了跟随者的⽇日志可能和新的领导⼈人不不同的⽅方式。跟随者可能会丢失⼀一些在新的领导⼈人中有的⽇日志条⽬目，他也可能拥有⼀一些领导⼈人没有的⽇日志条⽬目，或者两者都发⽣生。丢失或者多出⽇日志条⽬目可能会持续多个任期。

图 7：当⼀一个领导⼈人成功当选时，跟随者可能是任何情况（a-f）。每⼀一个盒⼦子表示是⼀一个⽇日志条⽬目；⾥里里⾯面的数字表示任期号。跟随者可能会缺少⼀一些⽇日志条⽬目（a-b），可能会有⼀一些未被提交的⽇日志条⽬目（c-d），或者两种情况都存在（e-f）。例例如，场景 f 可能会这样发⽣生，某服务器器在任期 2 的时候是领导⼈人，已附加了了⼀一些⽇日志条⽬目到⾃自⼰己的⽇日志中，但在提交之前就崩溃了了；很快这个机器器就被重启了了，在任期 3 重新被选为领导⼈人，并且⼜又增加了了⼀一些⽇日志条⽬目到⾃自⼰己的⽇日志中；在任期 2 和任期 3 的⽇日志被提交之前，这个服务器器⼜又宕机了了，并且在接下来的⼏几个任期⾥里里⼀一直处于宕机状态。在 Raft 算法中，领导⼈人处理理不不⼀一致是通过强制跟随者直接复制⾃自⼰己的⽇日志来解决了了。这意味着在跟随者中的冲突的⽇日志条⽬目会被领导⼈人的⽇日志覆盖。5.4 节会阐述如何通过增加⼀一些限制来使得这样的操作是安全的。要使得跟随者的⽇日志进⼊入和⾃自⼰己⼀一致的状态，领导⼈人必须找到最后两者达成⼀一致的地⽅方，然后删除从那个点之后的所有⽇日志条⽬目，发送⾃自⼰己的⽇日志给跟随者。所有的这些操作都在进⾏行行附加⽇日志 RPCs 的⼀一致性检查时完成。领导⼈人针对每⼀一个跟随者维护了了⼀一个 nextIndex，这表示下⼀一个需要发送给跟随者的⽇日志条⽬目的索引地址。当⼀一个领导⼈人刚获得权⼒力力的时候，他初始化所有的 nextIndex 值为⾃自⼰己的最后⼀一条⽇日志的index加1（图 7 中的 11）。如果⼀一个跟随者的⽇日志和领导⼈人不不⼀一致，那么在下⼀一次的附加⽇日志 RPC 时的⼀一致性检查就会失败。在被跟随者拒绝之后，领导⼈人就会减⼩小 nextIndex 值并进⾏行行重试。

最终 nextIndex 会在某个位置使得领导⼈人和跟随者的⽇日志达成⼀一致。当这种情况发⽣生，附加⽇日志 RPC 就会成功，这时就会把跟随者冲突的⽇日志条⽬目全部删除并且加上领导⼈人的⽇日志。⼀一旦附加⽇日志 RPC 成功，那么跟随者的⽇日志就会和领导⼈人保持⼀一致，并且在接下来的任期⾥里里⼀一直继续保持。如果需要的话，算法可以通过减少被拒绝的附加⽇日志 RPCs 的次数来优化。例例如，当附加⽇日志 RPC 的请求被拒绝的时候，跟随者可以包含冲突的条⽬目的任期号和⾃自⼰己存储的那个任期的最早的索引地址。借助这些信息，领导⼈人可以减⼩小 nextIndex 越过所有那个任期冲突的所有⽇日志条⽬目；这样就变成每个任期需要⼀一次附加条⽬目 RPC ⽽而不不是每个条⽬目⼀一次。在实践中，我们⼗十分怀疑这种优化是否是必要的，因为失败是很少发⽣生的并且也不不⼤大可能会有这么多不不⼀一致的⽇日志。通过这种机制，领导⼈人在获得权⼒力力的时候就不不需要任何特殊的操作来恢复⼀一致性。他只需要进⾏行行正常的操作，然后⽇日志就能⾃自动的在回复附加⽇日志 RPC 的⼀一致性检查失败的时候⾃自动趋于⼀一致。领导⼈人从来不不会覆盖或者删除⾃自⼰己的⽇日志（图 3 的领导⼈人只附加特性）。⽇日志复制机制展示出了了第 2 节中形容的⼀一致性特性：Raft 能够接受，复制并应⽤用新的⽇日志条⽬目只要⼤大部分的机器器是⼯工作的；在通常的情况下，新的⽇日志条⽬目可以在⼀一次 RPC 中被复制给集群中的⼤大多数机器器；并且单个的缓慢的跟随者不不会影响整体的性能。

5.4 安全性前⾯面的章节⾥里里描述了了 Raft 算法是如何选举和复制⽇日志的。然⽽而，到⽬目前为⽌止描述的机制并不不能充分的保证每⼀一个状态机会按照相同的顺序执⾏行行相同的指令。例例如，⼀一个跟随者可能会进⼊入不不可⽤用状态同时领导⼈人已经提交了了若⼲干的⽇日志条⽬目，然后这个跟随者可能会被选举为领导⼈人并且覆盖这些⽇日志条⽬目；因此，不不同的状态机可能会执⾏行行不不同的指令序列列。这⼀一节通过在领导选举的时候增加⼀一些限制来完善 Raft 算法。这⼀一限制保证了了任何的领导⼈人对于给定的任期号，都拥有了了之前任期的所有被提交的⽇日志条⽬目（图 3 中的领导⼈人完整特性）。增加这⼀一选举时的限制，我们对于提交时的规则也更更加清晰。最终，我们将展示对于领导⼈人完整特性的简要证明，并且说明领导⼈人是如何领导复制状态机的做出正确⾏行行为的。

5.4.1 选举限制在任何基于领导⼈人的⼀一致性算法中，领导⼈人都必须存储所有已经提交的⽇日志条⽬目。在某些⼀一致性算法中，例例如 Viewstamped Replication，某个节点即使是⼀一开始并没有包含所有已经提交的⽇日志条⽬目，它也能被选为领导者。这些算法

都包含⼀一些额外的机制来识别丢失的⽇日志条⽬目并把他们传送给新的领导⼈人，要么是在选举阶段要么在之后很快进⾏行行。不不幸的是，这种⽅方法会导致相当⼤大的额外的机制和复杂性。Raft 使⽤用了了⼀一种更更加简单的⽅方法，它可以保证所有之前的任期号中已经提交的⽇日志条⽬目在选举的时候都会出现在新的领导⼈人中，不不需要传送这些⽇日志条⽬目给领导⼈人。这意味着⽇日志条⽬目的传送是单向的，只从领导⼈人传给跟随者，并且领导⼈人从不不会覆盖⾃自身本地⽇日志中已经存在的条⽬目。Raft 使⽤用投票的⽅方式来阻⽌止⼀一个候选⼈人赢得选举除⾮非这个候选⼈人包含了了所有已经提交的⽇日志条⽬目。候选⼈人为了了赢得选举必须联系集群中的⼤大部分节点，这意味着每⼀一个已经提交的⽇日志条⽬目在这些服务器器节点中肯定存在于⾄至少⼀一个节点上。如果候选⼈人的⽇日志⾄至少和⼤大多数的服务器器节点⼀一样新（这个新的定义会在下⾯面讨论），那么他⼀一定持有了了所有已经提交的⽇日志条⽬目。请求投票 RPC 实现了了这样的限制： RPC 中包含了了候选⼈人的⽇日志信息，然后投票⼈人会拒绝掉那些⽇日志没有⾃自⼰己新的投票请求。Raft 通过⽐比较两份⽇日志中最后⼀一条⽇日志条⽬目的索引值和任期号定义谁的⽇日志⽐比较新。如果两份⽇日志最后的条⽬目的任期号不不同，那么任期号⼤大的⽇日志更更加新。如果两份⽇日志最后的条⽬目任期号相同，那么⽇日志⽐比较⻓长的那个就更更加新。

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

图 8：如图的时间序列列展示了了为什什么领导⼈人⽆无法决定对⽼老老任期号的⽇日志条⽬目进⾏行行提交。在 (a) 中，S1 是领导者，部分的复制了了索引位置 2 的⽇日志条⽬目。在 (b) 中，S1 崩溃了了，然后 S5 在任期 3 ⾥里里通过 S3、S4 和⾃自⼰己的选票赢得选举，然后从客户端接收了了⼀一条不不⼀一样的⽇日志条⽬目放在了了索引 2 处。然后到 (c)，S5 ⼜又崩溃了了；S1 重新启动，选举成功，开始复制⽇日志。在这时，来⾃自任期 2 的那条⽇日志已经被复制到了了集群中的⼤大多数机器器上，但是还没有被提交。如果 S1 在 (d) 中⼜又崩溃了了，S5 可以重新被选举成功（通过来⾃自 S2，S3 和 S4 的选票），然后覆盖了了他们在索引 2 处的⽇日志。反之，如果在崩溃之前，S1 把⾃自⼰己主导的新任期⾥里里产⽣生的⽇日志条⽬目复制到了了⼤大多数机器器上，就如 (e) 中那样，那么在后⾯面任期⾥里里⾯面这些新的⽇日志条⽬目就会被提交（因为S5 就不不可能选举成功）。 这样在同⼀一时刻就同时保证了了，之前的所有⽼老老的⽇日志条⽬目就会被提交。为了了消除图 8 ⾥里里描述的情况，Raft 永远不不会通过计算副本数⽬目的⽅方式去提交⼀一个之前任期内的⽇日志条⽬目。只有领导⼈人当前任期⾥里里的⽇日志条⽬目通过计算副本数⽬目可以被提交；⼀一旦当前任期的⽇日志条⽬目以这种⽅方式被提交，那么由于⽇日志匹配特性，之前的⽇日志条⽬目也都会被间接的提交。在某些情况下，领导⼈人可以安全的知道⼀一个⽼老老的⽇日志条⽬目是否已经被提交（例例如，该条⽬目是否存储到所有服务器器上），但是 Raft 为了了简化问题使⽤用⼀一种更更加保守的⽅方法。当领导⼈人复制之前任期⾥里里的⽇日志时，Raft 会为所有⽇日志保留留原始的任期号, 这在提交规则上产⽣生了了额外的复杂性。在其他的⼀一致性算法中，如果⼀一个新的领导⼈人要重新复制之前的任期⾥里里的⽇日志时，它必须使⽤用当前新的任期号。Raft 使⽤用的⽅方法更更加容易易辨别出⽇日志，因为它可以随着时间和⽇日志的变化对⽇日志维护着同⼀一个任期编号。另外，和其他的算法相⽐比，Raft 中的新领导⼈人只需要发送更更少⽇日志条⽬目（其他算法中必须在他们被提交之前发送更更多的冗余⽇日志条⽬目来为他们重新编号）。

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

图 9：如果 S1 （任期 T 的领导者）提交了了⼀一条新的⽇日志在它的任期⾥里里，然后 S5 在之后的任期 U ⾥里里被选举为领导⼈人，然后⾄至少会有⼀一个机器器，如 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 要求服务器器按照⽇日志中索引位置顺序应⽤用⽇日志条⽬目。和状态机安全特性结合起来看，这就意味着所有的服务器器会应⽤用相同的⽇日志序列列集到⾃自⼰己的状态机中，并且是按照相同的顺序。

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

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

领导⼈人选举是 Raft 中对时间要求最为关键的⽅方⾯面。Raft 可以选举并维持⼀一个稳定的领导⼈人,只要系统满⾜足下⾯面的时间要求：⼴广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）在这个不不等式中，⼴广播时间指的是从⼀一个服务器器并⾏行行的发送 RPCs 给集群中的其他服务器器并接收响应的平均时间；选举超时时间就是在 5.2 节中介绍的选举的超时时间限制；然后平均故障间隔时间就是对于⼀一台服务器器⽽而⾔言，两次故障之间的平均时间。⼴广播时间必须⽐比选举超时时间⼩小⼀一个量量级，这样领导⼈人才能够发送稳定的⼼心跳消息来阻⽌止跟随者开始进⼊入选举状态；通过随机化选举超时时间的⽅方法，这个不不等式也使得选票持平的情况变得不不可能。选举超时时间应该要⽐比平均故障间隔时间⼩小上⼏几个数量量级，这样整个系统才能稳定的运⾏行行。当领导⼈人崩溃后，整个系统会⼤大约相当于选举超时的时间⾥里里不不可⽤用；我们希望这种情况在整个系统的运⾏行行中很少出现。⼴广播时间和平均故障间隔时间是由系统决定的，但是选举超时时间是我们⾃自⼰己选择的。Raft 的 RPCs 需要接收⽅方将信息持久化的保存到稳定存储中去，所以⼴广播时间⼤大约是 0.5 毫秒到 20 毫秒，取决于存储的技术。因此，选举超时时间可能需要在 10 毫秒到 500 毫秒之间。⼤大多数的服务器器的平均故障间隔时间都在⼏几个⽉月甚⾄至更更⻓长，很容易易满⾜足时间的需求。

6 集群成员变化到⽬目前为⽌止，我们都假设集群的配置（加⼊入到⼀一致性算法的服务器器集合）是固定不不变的。但是在实践中，偶尔是会改变集群的配置的，例例如替换那些宕机的机器器或者改变复制级别。尽管可以通过暂停整个集群，更更新所有配置，然后重启整个集群的⽅方式来实现，但是在更更改的时候集群会不不可⽤用。另外，如果存在⼿手⼯工操作步骤，那么就会有操作失误的⻛风险。为了了避免这样的问题，我们决定⾃自动化配置改变并且将其纳⼊入到 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 的规则下被提交，旧的配置就变得⽆无关紧要，同时不不使⽤用新的配置的服务器器就可以被关闭了了。如图 11，C-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，他不不会更更新当前的任期号或者投出选票。这不不会影响正常的选举，每个服务器器在开始⼀一次选举之前，⾄至少等待⼀一个最⼩小选举超时时间。然⽽而，这有利利于避免被移除的服务器器扰乱：如果领导⼈人能够发送⼼心跳给集群，那么他就不不会被更更⼤大的任期号废黜。

7 ⽇日志压缩Raft 的⽇日志在正常操作中不不断的增⻓长，但是在实际的系统中，⽇日志不不能⽆无限制的增⻓长。随着⽇日志不不断增⻓长，他会占⽤用越来越多的空间，花费越来越多的时间来重置。如果没有⼀一定的机制去清除⽇日志⾥里里积累的陈旧的信息，那么会带来可⽤用性问题。快照是最简单的压缩⽅方法。在快照系统中，整个系统的状态都以快照的形式写⼊入到稳定的持久化存储中，然后到那个时间点之前的⽇日志全部丢弃。快照技术被使⽤用在 Chubby 和 ZooKeeper 中，接下来的章节会介绍 Raft 中的快照技术。增量量压缩的⽅方法，例例如⽇日志清理理或者⽇日志结构合并树，都是可⾏行行的。这些⽅方法每次只对⼀一⼩小部分数据进⾏行行操作，这样就分散了了压缩的负载压⼒力力。⾸首先，他们先选择⼀一个已经积累的⼤大量量已经被删除或者被覆盖对象的区域，然后重写那个区域还活跃的对象，之后释放那个区域。和简单操作整个数据集合的快照相⽐比，需要增加复杂的机制来实现。状态机可以实现 LSM tree 使⽤用和快照相同的接⼝口，但是⽇日志清除⽅方法就需要修改 Raft 了了。

图 12：⼀一个服务器器⽤用新的快照替换了了从 1 到 5 的条⽬目，快照值存储了了当前的状态。快照中包含了了最后的索引位置和任期号。图 12 展示了了 Raft 中快照的基础思想。每个服务器器独⽴立的创建快照，只包括已经被提交的⽇日志。主要的⼯工作包括将状态机的状态写⼊入到快照中。Raft 也包含⼀一些少量量的元数据到快照中：最后被包含索引指的是被快照取代的最后的条⽬目在⽇日志中的索引值（状态机最后应⽤用的⽇日志），最后被包含的任期指的是该条⽬目的任期号。保留留这些数据是为了了⽀支持快照后紧接着的第⼀一个条⽬目的附加⽇日志请求时的⼀一致性检查，因为这个条⽬目需要前⼀一⽇日志条⽬目的索引值和任期号。为了了⽀支持集群成员更更新（第 6 节），快照中也将最后的⼀一次配置作为最后⼀一个条⽬目存下来。⼀一旦服务器器完成⼀一次快照，他就可以删除最后索引位置之前的所有⽇日志和快照了了。尽管通常服务器器都是独⽴立的创建快照，但是领导⼈人必须偶尔的发送快照给⼀一些落后的跟随者。这通常发⽣生在当领导⼈人已经丢弃了了下⼀一条需要发送给跟随者的⽇日志条⽬目的时候。幸运的是这种情况不不是常规操作：⼀一个与领导⼈人保持同步的跟随者通常都会有这个条⽬目。然⽽而⼀一个运⾏行行⾮非常缓慢的跟随者或者新加⼊入集群的服务器器（第 6 节）将不不会有这个条⽬目。这时让这个跟随者更更新到最新的状态的⽅方式就是通过⽹网络把快照发送给他们。安装快照 RPC：由领导⼈人调⽤用以将快照的分块发送给跟随者。领导者总是按顺序发送分块。

接收者实现：1. 如果term < currentTerm就⽴立即回复2. 如果是第⼀一个分块（offset 为 0）就创建⼀一个新的快照3. 在指定偏移量量写⼊入数据4. 如果 done 是 false，则继续等待更更多的数据5. 保存快照⽂文件，丢弃具有较⼩小索引的任何现有或部分快照6. 如果现存的⽇日志条⽬目与快照中最后包含的⽇日志条⽬目具有相同的索引值和任期号，则保留留其后的⽇日志条⽬目并进⾏行行回复

7. 丢弃整个⽇日志8. 使⽤用快照重置状态机（并加载快照的集群配置）

参数 解释

term 领导⼈人的任期号

leaderId 领导⼈人的 Id，以便便于跟随者重定向请求

lastIncludedIndex 快照中包含的最后⽇日志条⽬目的索引值

lastIncludedTerm 快照中包含的最后⽇日志条⽬目的任期号

offset 分块在快照中的字节偏移量量

data[] 原始数据

done 如果这是最后⼀一个分块则为 true

结果 解释

term 当前任期号（currentTerm），便便于领导⼈人更更新⾃自⼰己

图 13：⼀一个关于安装快照的简要概述。为了了便便于传输，快照都是被分成分块的；每个分块都给了了跟随者⽣生命的迹象，所以跟随者可以重置选举超时计时器器。在这种情况下领导⼈人使⽤用⼀一种叫做安装快照的新的 RPC 来发送快照给太落后的跟随者；⻅见图 13。当跟随者通过这种 RPC 接收到快照时，他必须⾃自⼰己决定

对于已经存在的⽇日志该如何处理理。通常快照会包含没有在接收者⽇日志中存在的信息。在这种情况下，跟随者丢弃其整个⽇日志；它全部被快照取代，并且可能包含与快照冲突的未提交条⽬目。如果接收到的快照是⾃自⼰己⽇日志的前⾯面部分（由于⽹网络重传或者错误），那么被快照包含的条⽬目将会被全部删除，但是快照后⾯面的条⽬目仍然有效，必须保留留。这种快照的⽅方式背离了了 Raft 的强领导⼈人原则，因为跟随者可以在不不知道领导⼈人情况下创建快照。但是我们认为这种背离是值得的。领导⼈人的存在，是为了了解决在达成⼀一致性的时候的冲突，但是在创建快照的时候，⼀一致性已经达成，这时不不存在冲突了了，所以没有领导⼈人也是可以的。数据依然是从领导⼈人传给跟随者，只是跟随者可以重新组织他们的数据了了。我们考虑过⼀一种替代的基于领导⼈人的快照⽅方案，即只有领导⼈人创建快照，然后发送给所有的跟随者。但是这样做有两个缺点。第⼀一，发送快照会浪费⽹网络带宽并且延缓了了快照处理理的时间。每个跟随者都已经拥有了了所有产⽣生快照需要的信息，⽽而且很显然，⾃自⼰己从本地的状态中创建快照⽐比通过⽹网络接收别⼈人发来的要经济。第⼆二，领导⼈人的实现会更更加复杂。例例如，领导⼈人需要发送快照的同时并⾏行行的将新的⽇日志条⽬目发送给跟随者，这样才不不会阻塞新的客户端请求。还有两个问题影响了了快照的性能。⾸首先，服务器器必须决定什什么时候应该创建快照。如果快照创建的过于频繁，那么就会浪费⼤大量量的磁盘带宽和其他资源；如果创建快照频率太低，他就要承受耗尽存储容量量的⻛风险，同时也增加了了从⽇日志重建的时间。⼀一个简单的策略略就是当⽇日志⼤大⼩小达到⼀一个固定⼤大⼩小的时候就创建⼀一次快照。如果这个阈值设置的显著⼤大于期望的快照的⼤大⼩小，那么快照对磁盘压⼒力力的影响就会很⼩小了了。第⼆二个影响性能的问题就是写⼊入快照需要花费显著的⼀一段时间，并且我们还不不希望影响到正常操作。解决⽅方案是通过写时复制的技术，这样新的更更新就可以被接收⽽而不不影响到快照。例例如，具有函数式数据结构的状态机天然⽀支持这样的功能。另外，操作系统的写时复制技术的⽀支持（如 Linux 上的 fork）可以被⽤用来创建完整的状态机的内存快照（我们的实现就是这样的）。

8 客户端交互这⼀一节将介绍客户端是如何和 Raft 进⾏行行交互的，包括客户端如何发现领导⼈人和 Raft 是如何⽀支持线性化语义的。这些问题对于所有基于⼀一致性的系统都存在，并且 Raft 的解决⽅方案和其他的也差不不多。Raft 中的客户端发送所有请求给领导⼈人。当客户端启动的时候，他会随机挑选⼀一个服务器器进⾏行行通信。如果客户端第⼀一次挑选的服务器器不不是领导⼈人，那么那个服务器器会拒绝客户端的请求并且提供他最近接收到的领导⼈人的信息（附加条⽬目

请求包含了了领导⼈人的⽹网络地址）。如果领导⼈人已经崩溃了了，那么客户端的请求就会超时；客户端之后会再次重试随机挑选服务器器的过程。我们 Raft 的⽬目标是要实现线性化语义（每⼀一次操作⽴立即执⾏行行，只执⾏行行⼀一次，在他调⽤用和收到回复之间）。但是，如上述，Raft 是可以执⾏行行同⼀一条命令多次的：例例如，如果领导⼈人在提交了了这条⽇日志之后，但是在响应客户端之前崩溃了了，那么客户端会和新的领导⼈人重试这条指令，导致这条命令就被再次执⾏行行了了。解决⽅方案就是客户端对于每⼀一条指令都赋予⼀一个唯⼀一的序列列号。然后，状态机跟踪每条指令最新的序列列号和相应的响应。如果接收到⼀一条指令，它的序列列号已经被执⾏行行了了，那么就⽴立即返回结果，⽽而不不重新执⾏行行指令。只读的操作可以直接处理理⽽而不不需要记录⽇日志。但是，在不不增加任何限制的情况下，这么做可能会冒着返回脏数据的⻛风险，因为领导⼈人响应客户端请求时可能已经被新的领导⼈人作废了了，但是他还不不知道。线性化的读操作必须不不能返回脏数据，Raft 需要使⽤用两个额外的措施在不不使⽤用⽇日志的情况下保证这⼀一点。⾸首先，领导⼈人必须有关于被提交⽇日志的最新信息。领导⼈人完全特性保证了了领导⼈人⼀一定拥有所有已经被提交的⽇日志条⽬目，但是在他任期开始的时候，他可能不不知道那些是已经被提交的。为了了知道这些信息，他需要在他的任期⾥里里提交⼀一条⽇日志条⽬目。Raft 中通过领导⼈人在任期开始的时候提交⼀一个空⽩白的没有任何操作的⽇日志条⽬目到⽇日志中去来实现。第⼆二，领导⼈人在处理理只读的请求之前必须检查⾃自⼰己是否已经被废黜了了（他⾃自⼰己的信息已经变脏了了如果⼀一个更更新的领导⼈人被选举出来）。Raft 中通过让领导⼈人在响应只读请求之前，先和集群中的⼤大多数节点交换⼀一次⼼心跳信息来处理理这个问题。可选的，领导⼈人可以依赖⼼心跳机制来实现⼀一种租约的机制，但是这种⽅方法依赖时间来保证安全性（假设时间误差是有界的）。

9 算法实现和评估我们已经为 RAMCloud 实现了了 Raft 算法作为存储配置信息的复制状态机的⼀一部分，并且帮助 RAMCloud 协调故障转移。这个 Raft 实现包含⼤大约 2000 ⾏行行 C++ 代码，其中不不包括测试、注释和空⾏行行。这些代码是开源的。同时也有⼤大约 25 个其他独⽴立的第三⽅方的基于这篇论⽂文草稿的开源实现，针对不不同的开发场景。同时，很多公司已经部署了了基于 Raft 的系统。这⼀一节会从三个⽅方⾯面来评估 Raft 算法：可理理解性、正确性和性能。

9.1 可理理解性为了了和 Paxos ⽐比较 Raft 算法的可理理解能⼒力力，我们针对⾼高层次的本科⽣生和研究⽣生，在斯坦福⼤大学的⾼高级操作系统课程和加州⼤大学伯克利利分校的分布式计算课程上，进⾏行行了了⼀一次学习的实验。我们分别拍了了针对 Raft 和 Paxos 的视频课

程，并准备了了相应的⼩小测验。Raft 的视频讲课覆盖了了这篇论⽂文的所有内容除了了⽇日志压缩；Paxos 讲课包含了了⾜足够的资料料来创建⼀一个等价的复制状态机，包括单决策 Paxos，多决策 Paxos，重新配置和⼀一些实际系统需要的性能优化（例例如领导⼈人选举）。⼩小测验测试⼀一些对算法的基本理理解和解释⼀一些边⻆角的示例例。每个学⽣生都是看完第⼀一个视频，回答相应的测试，再看第⼆二个视频，回答相应的测试。⼤大约有⼀一半的学⽣生先进⾏行行 Paxos 部分，然后另⼀一半先进⾏行行 Raft 部分，这是为了了说明两者从第⼀一部分的算法学习中获得的表现和经验的差异。我们计算参加⼈人员的每⼀一个⼩小测验的得分来看参与者是否在 Raft 算法上更更加容易易理理解。我们尽可能的使得 Paxos 和 Raft 的⽐比较更更加公平。这个实验偏爱 Paxos 表现在两个⽅方⾯面：43 个参加者中有 15 个⼈人在之前有⼀一些 Paxos 的经验，并且 Paxos 的视频要⻓长 14%。如表格 1 总结的那样，我们采取了了⼀一些措施来减轻这种潜在的偏⻅见。我们所有的材料料都可供审查。

表 1：考虑到可能会存在的偏⻅见，对于每种情况的解决⽅方法，和相应的材料料。参加者平均在 Raft 的测验中⽐比 Paxos ⾼高 4.9 分（总分 60，那么 Raft 的平均得分是 25.7，⽽而 Paxos 是 20.8）；图 14 展示了了每个参与者的得分。配置t-检验（⼜又称student\'s t-test）表明，在 95% 的可信度下，真实的 Raft 分数分布⾄至少⽐比 Paxos ⾼高 2.5 分。

关⼼心 缓和偏⻅见采取的⼿手段可供查看的材料料

相同的讲课质量量

两者使⽤用同⼀一个讲师。Paxos 使⽤用的是现在很多⼤大学⾥里里经常使⽤用的。Paxos 会⻓长 14%。

视频

相同的测验难度

问题以难度分组，在两个测验⾥里里成对出现。

⼩小测验

公平评分

使⽤用评价量量规。随机顺序打分，两个测验交替进⾏行行。

评价量量规（rubric）

图 14：⼀一个散点图表示了了 43 个学⽣生在 Paxos 和 Raft 的⼩小测验中的成绩。在对⻆角线之上的点表示在 Raft 获得了了更更⾼高分数的学⽣生。我们也建⽴立了了⼀一个线性回归模型来预测⼀一个新的学⽣生的测验成绩，基于以下三个因素：他们使⽤用的是哪个⼩小测验，之前对 Paxos 的经验，和学习算法的顺序。模型预测，对⼩小测验的选择会产⽣生 12.5 分的差别。这显著的⾼高于之前的 4.9 分，因为很多学⽣生在之前都已经有了了对于 Paxos 的经验，这相当明显的帮助 Paxos，对 Raft 就没什什么太⼤大影响了了。但是奇怪的是，模型预测对于先进⾏行行 Paxos ⼩小测验的⼈人⽽而⾔言，Raft的得分低了了6.3分; 虽然我们不不知道为什什么，这似乎在统计上是有意义的。我们同时也在测验之后调查了了参与者，他们认为哪个算法更更加容易易实现和解释；这个的结果在图 15 上。压倒性的结果表明 Raft 算法更更加容易易实现和解释（41 ⼈人中的 33个）。但是，这种⾃自⼰己报告的结果不不如参与者的成绩更更加可信，并且参与者可能因为我们的 Raft 更更加易易于理理解的假说⽽而产⽣生偏⻅见。

图 15：通过⼀一个 5 分制的问题，参与者（左边）被问哪个算法他们觉得在⼀一个⾼高效正确的系统⾥里里更更容易易实现，右边被问哪个更更容易易向学⽣生解释。关于 Raft ⽤用户学习有⼀一个更更加详细的讨论。

9.2 正确性在第 5 节，我们已经制定了了正式的规范，和对⼀一致性机制的安全性证明。这个正式规范使⽤用 TLA+ 规范语⾔言使图 2 中总结的信息⾮非常清晰。它⻓长约400⾏行行，并作为证明的主题。同时对于任何想实现 Raft 的⼈人也是⼗十分有⽤用的。我们通过 TLA 证明系统⾮非常机械的证明了了⽇日志完全特性。然⽽而，这个证明依赖的约束前提还没有被机械证明（例例如，我们还没有证明规范的类型安全）。⽽而且，我们已经写了了⼀一个⾮非正式的证明关于状态机安全性是完备的，并且是相当清晰的（⼤大约 3500 个词）。

9.3 性能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 毫秒；这样的时间不不⼤大可能导致没有意义的领导⼈人改变，⽽而且依然提供不不错的可⽤用性。

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

• 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 ⽐比较⽽而⾔言。