raft

一种可理解的共识算法的寻找(扩展版)

概要

​ Raft是用于管理复制日志的共识算法。它产生的结果相当于(多)Paxos，效率和Paxos一样，但结构与Paxos不同;这使得Raft比Paxos更容易理解，也为构建实用系统提供了更好的基础。为了增强可理解性，Raft分离了共识的关键元素，如leader选举、日志复制和安全性，并且它强制执行更强的一致性，以减少必须考虑的状态的数量。用户研究的结果表明，对于学生来说，Raft比Paxos更容易学习。Raft还包含了一个改变集群成员的新机制，它使用重叠大多数来保证安全。

I.介绍

​ 共识算法允许一组机器作为一个连贯的群体工作，可以在其中一些成员出现故障时幸存下来。正因为如此，它们在构建可靠的大型软件系统中起着关键作用。Paxos[15,16]在过去十年中主导了共识算法的讨论:大多数共识的实现都基于Paxos或受其影响，Paxos已成为教授学生共识的主要工具。

​ 不幸的是，Paxos很难理解，尽管有许多尝试使它更容易理解。此外，它的体系结构需要进行复杂的更改以支持实际系统。因此，系统构建者和学生使用Paxos都很困难。

​ 在与Paxos斗争之后，我们开始寻找一种新的共识算法，可以为系统构建和教育提供更好的基础。我们的方法是不同寻常的，因为我们的主要目标是可理解性:我们能否为实际系统定义一个共识算法，并以一种比Paxos更容易学习的方式来描述它?此外，我们希望算法能够促进对系统构建者至关重要的直觉的发展。重要的不仅是算法能起作用，还在于它为什么能起作用。

​ 这项工作的结果是一个被称为Raft的共识算法。在设计Raft时，我们应用了特定的技术来提高可理解性，包括分解(Raft将领导者选举、日志复制和安全性分开)和状态空间缩减(相对于Paxos, Raft降低了不确定性的程度和服务器之间可能不一致的方式)。一项针对两所大学43名学生的用户研究表明，Raft比Paxos更容易理解:在学习了这两种算法后，其中33名学生能够更好地回答关于Raft的问题，而不是关于Paxos的问题。

​ Raft在许多方面与现有的共识算法相似(最值得注意的是Oki和Liskov的Viewstamped Replication)，但它有几个新特性:

• 强大的leader:Raft使用比其他共识算法更强大的领导形式。例如，日志条目只从leader流向其他服务器。这简化了复制日志的管理，使Raft更容易理解。
• leader选举:Raft使用随机计时器来选举首领。这只给任何共识算法已经需要的心跳增加了少量的机制，同时简单快速地解决冲突。
• 成员变更:Raft用于更改集群中服务器集的机制使用了一种新的联合共识方法，在这种方法中，两种不同配置的大多数在转换期间重叠。这允许集群在配置更改期间继续正常运行。

​ 我们相信Raft优于Paxos和其他共识算法，无论是出于教育目的还是作为实现的基础。它比其他算法更简单，更容易理解;它的描述足够完整，足以满足实际系统的需要;它有几个开源实现，并被几家公司使用;其安全性能已经过正式规定和证明;其效率与其他算法相当。

​ 本文的其余部分介绍了复制状态机问题(第2节)，讨论了Paxos的优缺点(第3节)，描述了我们实现可理解性的一般方法(第4节)，介绍了Raft共识算法(第5-8节)，评估了Raft(第9节)，并讨论了相关工作(第10节)。

II.复制状态机

​ 共识算法通常出现在复制状态机的环境中。在这种方法中，一组服务器上的状态机计算相同状态的相同副本，并且即使某些服务器关闭也可以继续运行。复制状态机用于解决分布式系统中的各种容错问题。例如，具有单个集群领导者的大型系统，如GFS， HDFS和RAMCloud，通常使用单独的复制状态机来管理领导者选举和存储必须在领导者崩溃时存活的配置信息。复制状态机的例子包括Chubby和ZooKeeper。

​ 复制状态机通常使用复制日志来实现，如图1所示。每个服务器存储包含一系列命令的日志，其状态机按顺序执行这些命令。每个日志以相同的顺序包含相同的命令，因此每个状态机处理相同的命令序列。由于状态机是确定性的，因此每个状态机都计算相同的状态和相同的输出序列。

​ 保持复制日志的一致性是一致性算法的工作。服务器上的consensus模块接收来自客户端的命令并将其添加到日志中。它与其他服务器上的共识模块通信，以确保每个日志最终以相同的顺序包含相同的请求，即使某些服务器失败。一旦正确地复制了命令，每个服务器的状态机将按日志顺序处理它们，并将输出返回给客户机。因此，这些服务器似乎形成了一个单一的、高度可靠的状态机。

​ 实际系统的共识算法通常具有以下性质:

• 它们确保在所有非拜占庭条件下的安全性(永远不会返回错误的结果)，包括网络延迟、分区、数据包丢失、重复和重新排序。
• 只要任何大多数服务器都是可操作的，并且可以相互通信并与客户端通信，它们就具有完整的功能(可用)。因此，典型的五台服务器集群可以容忍任意两台服务器的故障。通过停止假定服务器失败;它们可能稍后从稳定存储上的状态恢复并重新加入集群。
• 它们不依赖于定时来确保日志的一致性:错误的时钟和极端的消息延迟在最坏的情况下会导致可用性问题。
• 在通常情况下，只要集群的大多数响应了一轮远程过程调用，命令就可以完成;少数慢速服务器不需要影响整体系统性能。

III.What’s wrong with Paxos???

​ 在过去的十年里，Leslie Lamport的Paxos协议几乎已经成为共识的代名词:它是课程中最常教授的协议，大多数共识的实现都将其作为起点。Paxos首先定义了一个能够就单个决策达成一致的协议，比如单个复制的日志条目。我们将这个子集称为单命令Paxos。然后，Paxos结合该协议的多个实例来促进一系列决策，例如日志(多Paxos)。Paxos确保了安全性和活动性，并且支持更改集群成员。该方法的正确性得到了验证，在一般情况下是有效的。

​ 不幸的是，Paxos有两个明显的缺点。第一个缺点是Paxos非常难以理解。完整的解释[15]是出了名的不透明;只有付出巨大努力的人才能理解它。因此，已经有人尝试用更简单的术语来解释Paxos。这些解释集中于单一法令子集，但它们仍然具有挑战性。在对2012年NSDI与会者的非正式调查中，我们发现很少有人对Paxos感到满意，即使是经验丰富的研究人员。我们自己也在努力开发Paxos;直到阅读了几个简化的解释并设计了我们自己的替代协议之后，我们才能够理解完整的协议，这个过程花了将近一年的时间。

​ 我们假设Paxos的不透明性源于它选择单一法令子集作为其基础。单一法令的Paxos是密集而微妙的:它分为两个阶段，没有简单的直观解释，无法独立理解。正因为如此，很难对单一法令协议的工作原理做出直观的解释。多paxos的组合规则增加了额外的复杂性和微妙性。我们相信，在多个决策上达成共识的整体问题(即，一个日志而不是单个条目)可以用其他更直接和明显的方式分解。

​ Paxos的第二个问题是，它没有为构建实际实现提供良好的基础。其中一个原因是，对于多paxos，还没有得到广泛认可的算法。兰波特的描述主要是关于单一法令的Paxos;他概述了实现多paxos的可能方法，但缺少许多细节。已经有几次尝试充实和优化Paxos，但这些彼此不同，也不同于Lamport的草图。像Chubby这样的系统已经实现了类似paxos的算法，但在大多数情况下，它们的细节还没有公布。

​ 此外，Paxos架构对于构建实际系统来说是一个糟糕的架构;这是单一法令分解的另一个后果。例如，独立地选择一组日志条目，然后将它们合并到一个顺序日志中，这几乎没有什么好处;这只会增加复杂性。围绕日志设计系统更简单、更有效，在日志中，新条目以受限的顺序依次挂起。另一个问题是Paxos在其核心使用了对称的点对点方法(尽管它最终提出了一种弱形式的领导作为性能优化)。这在只需要做出一个决策的简化世界中是有意义的，但是很少有实际的系统使用这种方法。如果必须做出一系列决策，那么首先选举一个领导者，然后让领导者协调决策是更简单和更快的方法。

​ 因此，实际系统与Paxos几乎没有相似之处。每个实现都从Paxos开始，发现实现它的困难，然后开发一个截然不同的体系结构。这既耗时又容易出错，而且理解Paxos的困难加剧了这个问题。Paxos的公式对于证明其正确性的定理可能是一个很好的公式，但是实际实现与Paxos如此不同，以至于证明几乎没有价值。以下是Chubby实现者的典型评论:

​ 在Paxos算法的描述和真实系统的需求之间有很大的差距…最终的系统将基于一个未经验证的协议

​ 由于这些问题，我们得出结论，Paxos不能为系统构建或教育提供良好的基础。考虑到共识在大型软件系统中的重要性，我们决定看看是否可以设计一个具有比Paxos更好属性的替代共识算法。Raft就是那次实验的结果。

IV.为可理解性而设计

​ 我们在设计Raft时有几个目标:它必须为系统构建提供一个完整和实用的基础，这样它就可以显著减少开发人员所需的设计工作量;它必须在所有条件下都是安全的，并在典型的操作条件下可用;对于一般的操作，它必须是有效的。但我们最重要的目标——也是最困难的挑战——是可理解性。它必须能够让大量的观众轻松地理解算法。此外，必须能够开发关于算法的直觉，以便系统构建者可以进行在实际实现中不可避免的扩展。

​ 在Raft的设计过程中，我们需要在不同的方法中做出选择。在这些情况下，我们根据可理解性来评估备选方案:解释每个备选方案有多难(例如，其状态空间有多复杂，它是否有微妙的含义?)，读者完全理解该方法及其含义有多容易?

​ 我们认识到，在这种分析中有高度的主观性;尽管如此，我们还是使用了两种普遍适用的技术。第一种技术是众所周知的问题分解方法:只要有可能，我们就把问题分成可以相对独立地解决、解释和理解的独立部分。例如，在Raft中，我们分离了leader选举、日志复制、安全性和成员变更。

​ 我们的第二种方法是通过减少要考虑的状态数量来简化状态空间，使系统更加连贯，并在可能的情况下消除不确定性。具体来说，原木不允许有孔，Raft限制了原木相互不一致的方式。尽管在大多数情况下我们试图消除非确定性，但在某些情况下，非确定性实际上提高了可理解性。特别是，随机方法引入了不确定性，但它们倾向于通过以类似的方式处理所有可能的选择(“随便选没关系”)。我们使用随机化来简化Raft leader的选举算法。

V.Raft共识算法

​ Raft是一种算法，用于管理第2节中描述的形式的复制日志。图2对算法进行了简明总结，以供参考，图3列出了算法的关键属性;这些数字的元素将在本节的其余部分逐条讨论。

​ Raft通过首先选举一个杰出的领导者来实现共识，然后让领导者完全负责管理复制的日志。leader接受来自客户机的日志条目，在其他服务器上复制它们，并告诉服务器何时可以安全地将日志条目应用到它们的状态机。拥有一个leader可以简化对复制日志的管理。例如，leader可以在不咨询其他服务器的情况下决定在日志中放置新条目的位置，并且数据以一种简单的方式从leader流向其他服务器。leader可能会失败或与其他服务器断开连接，在这种情况下，会选举一个新的leader。

​ 在leader方法下，Raft将共识问题分解为三个相对独立的子问题，并在以下小节中进行讨论:

• 领导人选举:当现有领导人失败时，必须选择新的领导人(第5.2节)。
• 日志复制:leader必须接受来自客户端的日志条目，并在整个集群中复制它们，迫使其他日志与自己的日志一致(第5.3节)。
• 安全性:Raft的关键安全属性是图3中的状态机安全属性:如果任何服务器将特定的日志条目应用到其状态机，那么其他服务器就不能对相同的日志索引应用不同的命令。第5.4节描述了Raft如何确保此属性;该解决方案涉及对第5.2节中描述的选举机制的额外限制。

​ 在介绍了共识算法之后，本节将讨论可用性问题和定时在系统中的作用。

V.1 Raft基础

​ Raft集群包含多个服务器;5是一个典型的数字，它允许系统容忍两次故障。在任何给定时间，每个服务器都处于以下三种状态之一:领导者、追随者或候选人。在正常操作中，只有一个领导者，所有其他服务器都是追随者。追随者是被动的:他们自己不发出任何要求，只是对领导和候选人的要求做出回应。leader处理所有客户端请求(如果客户端联系了follower, follower会将其重定向到leader)。第三个状态，candidate，用于选举新的领导人，如第5.2节所述。图4显示了状态及其转换;下面将讨论这些转换。

​ Raft将时间划分为任意长度，如图5所示。任期用连续整数编号。每个任期以选举开始，其中一个或多个候选人试图成为第5.2节所述的领导人。如果一位候选人赢得选举，那么他将在剩下的任期内担任领导人。在某些情况下，选举会导致票数不一致。在这种情况下，任期结束时将没有领导人;新任期(有新的选举)即将开始。Raft保证在给定的任期内最多有一个leader。

​ 不同的服务器可能会在不同的时间观察任期之间的过渡，在某些情况下，服务器可能不会观察选举甚至整个任期。术语在Raft中充当逻辑时钟，它们允许服务器检测过时的信息，如过时的leader。每个服务器存储一个当前术语号，该术语号随时间单调增加。每当服务器通信时，都会交换当前条款;如果一台服务器的当前项小于另一台服务器的，则将其当前项更新为较大的值。如果候选人或领导人发现自己的任期已经过期，

​ Raft服务器使用远程过程调用(rpc)进行通信，基本的一致性算法只需要两种类型的rpc。RequestVote rpc是由候选人在选举期间发起的(第5.2节)，而追加条目rpc是由领导者发起的，用于复制日志条目并提供心跳形式(第5.3节)。第7节添加了第三个RPC，用于在服务器之间传输快照。如果服务器没有及时收到响应，它们会重试rpc，并并行地发出rpc以获得最佳性能。

V.2 领导选举

​ Raft使用心跳机制来触发领导人选举。当服务器启动时，它们从追随者开始。只要从leader或candidate接收到有效的rpc，服务器就保持follower状态。领导者定期向所有追随者发送心跳(AppendEntries rpc，不携带日志条目)，以维护他们的权威。如果一个follower在一段称为选举超时的时间内没有收到任何通信，那么它假设没有可见的leader，并开始选举以选择一个新的leader。

​ 要开始选举，追随者增加其当前任期并过渡到候选人状态。然后，它为自己投票，并并行地向集群中的每个其他服务器发出RequestVote rpc。候选人一直处于这种状态，直到发生以下三种情况之一:(A)它赢得了选举，(b)另一个服务器确立了自己的领导地位，或者(c)一段时间过去了，没有赢家。这些结果将在下文各段分别讨论。

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

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

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

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

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

V.3 日志复制

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

​ 日志组织如图6所示。每个日志记录存储一个状态机命令以及leader接收到该条目时的术语号。日志条目中的术语编号用于检测日志之间的不一致性，并确保图3中的一些属性。每个日志条目还有一个整数索引，用于标识其在日志中的位置。

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

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

• 如果不同日志中的两个条目具有相同的索引和期限，则它们存储相同的命令。
• 如果不同日志中的两个条目具有相同的索引和期限，则前面所有条目的日志都相同。

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

​ 正常运行时，leader和follower的日志是一致的，所以AppendEntries一致性检查不会失败。但是，leader崩溃可能导致日志不一致(旧leader可能没有完全复制其日志中的所有条目)。这些不一致可能会在一系列领导者和追随者的崩溃中加剧。图7说明了追随者的日志可能与新领导者的不同之处。follower可能缺少leader上存在的条目，也可能有leader上没有的额外条目，或者两者兼而有之。日志中缺少的和无关的条目可能跨越多个术语。

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

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

​ 如果需要，可以优化协议以减少被拒绝的AppendEntries rpc的数量。例如，在拒绝AppendEntries请求时，follower可以包含冲突条目的项和它为该项存储的第一个索引。有了这些信息，leader就可以对nextIndex进行减量以绕过该项中所有冲突的表项;每个有冲突条目的术语需要一个AppendEntries RPC，而不是每个条目一个RPC。在实践中，我们怀疑这种优化是否必要，因为故障很少发生，而且不太可能有许多不一致的条目。

​ 有了这种机制，当涉及到权力时，领导者不需要采取任何特殊操作来恢复日志一致性。它只是开始正常操作，并且日志会自动收敛，以响应追加条目一致性检查失败。leader永远不会覆盖或删除自己日志中的条目(图3中的leader追加属性)。

​ 这种日志复制机制展示了第2节中描述的理想的共识属性:只要大多数服务器正常运行，Raft就可以接受、复制和应用新的日志条目;在正常情况下，一个新条目可以通过一轮rpc复制到集群的大多数;一个缓慢的追随者不会影响你的表现。

V.4 安全

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

​ 本节通过添加服务器可以被选为领导者的限制来完成Raft算法。该限制确保任何给定任期的leader包含在前一任期中提交的所有条目(图3中的leader完整性属性)。考虑到选举限制，我们将使提交规则更加精确。最后，我们给出了Leader完备性的证明草图，并展示了它如何导致复制状态机的正确行为。

V.4.1 选举限制

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

​ Raft使用投票过程来阻止候选人赢得选举，除非其日志包含所有已提交的条目。候选人必须与集群的大多数成员联系才能当选，这意味着每个提交的条目必须至少出现在其中一台服务器中。如果候选日志至少与大多数日志中的任何其他日志一样最新(“最新”的定义在下面)，那么它将保存所有已提交的条目。RequestVote RPC实现了这个限制:RPC包含关于候选人日志的信息，如果投票人自己的日志比候选人的日志更新，投票人就拒绝投票。

​ Raft通过比较日志中最后条目的索引和期限来确定两个日志中哪一个是最新的。如果日志的最后条目具有不同的术语，那么具有后一个术语的日志是最新的。如果日志以相同的期限结束，那么哪个日志越长，哪个日志就越最新。

V.4.2 提交以前的条目

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

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

​ Raft在承诺规则中引入了这种额外的复杂性，因为当leader复制前一项的条目时，日志条目保留其原始的条目编号。在其他共识算法中，如果一个新的leader从先前的“term”中重复复制条目，它必须使用新的“term number”。Raft的方法可以更容易地推断日志条目，因为它们在不同的时间和日志中保持相同的项数。此外，Raft中的新leader发送的以前条目的日志条目比其他算法少(其他算法必须发送冗余的日志条目来重新编号，然后才能提交)。

V.4.3 安全论证

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

1. 承诺的条目必须在其选举时从领导u的日志中消失(领导永远不会删除或覆盖条目)。
2. leaderT在大多数集群上复制条目，而leaderU收到大多数集群的投票。因此，至少有一个服务器(“投票人”)接受了来自leaderT的条目并投票给了leadu，如图9所示。选民是达成矛盾的关键。
3. 投票人必须在投票给leadt之前接受leadt的承诺条目;否则，它将拒绝来自leaderT的AppendEntries请求(其当前项将高于T)。
4. 投票人在投票给领导u时仍然存储该条目，因为每个介入的领导都包含该条目(假设)，领导永远不会删除条目，而追随者只有在与领导冲突时才删除条目。
5. 投票人将其选票授予了leaderU，因此leaderU的日志必须与投票人的日志一样是最新的。这导致了两个矛盾之一。
6. 首先，如果投票者和leaderU共享相同的最后一个日志项，那么leaderU的日志必须至少和投票者的日志一样长，所以它的日志包含投票者日志中的每一个条目。这是一个矛盾，因为选民包含承诺的条目，而领导人被认为没有。
7. 否则，领导人u的上一个对数项一定大于选民的对数项。而且，它比T大，因为投票人的最后一个日志项至少是T(它包含来自项T的承诺条目)。创建leadu的最后一个日志项的较早的领导者必须在其日志中包含承诺条目(通过假设)。那么，根据日志匹配属性，leaderU的日志必须也包含提交的条目，这是一个矛盾。
8. 这就解决了矛盾。因此，所有大于T的项的前导必须包含所有在T项中提交的来自T项的项。
9. Log Matching Property保证未来的leader也将包含间接提交的条目，如图8(d)中的索引2。

​ 间接地，如图8(d)中的索引2。给定Leader完整性属性，我们可以证明图3中的状态机安全属性，该属性表明，如果服务器在给定索引上应用了一个日志条目到其状态机，那么其他服务器将不会为相同的索引应用不同的日志条目。当服务器将一个日志条目应用到它的状态机时，它的日志必须与该条目之前的领导日志相同，并且该条目必须提交。现在考虑任何服务器应用给定日志索引的最低期限;日志完整性属性保证所有较高项的leader将存储相同的日志条目，因此在较低项中应用索引的服务器将应用相同的值。因此，状态机安全属性保持不变。

​ 最后，Raft要求服务器按照日志索引顺序应用条目。结合状态机安全属性，这意味着所有服务器将以相同的顺序向其状态机应用完全相同的日志条目集。

V.5 追随者和候选人崩溃

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

V.6 时间和可用性

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

​ 领袖选举是Raft中最关键的环节。只要系统满足以下时间要求，Raft就能够选出并维持一个稳定的leader:

​ broadcastTime≪ electionTimeout ≪ MTBF

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

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

VI 集群成员变更

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

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

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

• 日志条目被复制到两种配置中的所有服务器。
• 任一配置中的任何服务器都可以作为leader。
• 协议(对于选举和进入承诺)需要从旧的和新的配置中分离多数。

​ 联合共识允许单个服务器在不同的时间在配置之间转换，而不会出现安全问题。此外，联合共识允许集群在整个配置更改期间继续为客户机请求提供服务。

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

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

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

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

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

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

VII 日志压缩

​ Raft的日志在正常运行期间会增长，以包含更多的客户端请求，但在实际系统中，它不能无限制地增长。随着日志变长，它会占用更多的空间，并且需要更多的时间来重放。如果没有某种机制来丢弃日志中积累的过时信息，这将最终导致可用性问题。

​ 快照是最简单的压缩方法。在快照中，整个当前系统状态被写入稳定存储上的快照，然后直到该点的整个日志被丢弃。快照在Chubby和ZooKeeper中使用，本节的其余部分描述了Raft中的快照。

​ 增量压缩方法，如日志清理和日志结构合并树，也是可能的。它们一次对一小部分数据进行操作，因此它们随着时间的推移更均匀地分散了压缩的负载。它们首先选择一个数据区域，该区域累积了许多已删除和覆盖的对象，然后更紧凑地重写该区域的活动对象，并释放该区域。与快照相比，这需要大量额外的机制和复杂性，快照通过始终对整个数据集进行操作来简化问题。虽然日志清理需要修改Raft，但状态机可以使用与快照相同的接口实现LSM树。

​ 图12显示了Raft中快照的基本思想。每个服务器独立地获取快照，只覆盖其日志中提交的条目。大部分工作包括状态机将其当前状态写入快照。Raft还在快照中包含少量元数据:最后包含的索引是快照替换的日志中最后一个条目的索引(状态机应用的最后一个条目)，最后包含的术语是该条目的术语。保留这些内容是为了支持对快照之后的第一个日志条目进行AppendEntries一致性检查，因为该条目需要之前的日志索引和期限。为了启用集群成员变更(第6节)，快照还包括日志中上次包含索引时的最新配置。一旦服务器完成对快照的写入，它可能会删除直到最后包含的索引的所有日志条目，以及任何先前的快照。

​ 虽然服务器通常会独立地拍摄快照，但领导者偶尔必须向落后的追随者发送快照。当领导者已经丢弃了它需要发送给追随者的下一个日志条目时，就会发生这种情况。幸运的是，在正常操作中不太可能出现这种情况:跟随领导者的追随者已经有了这个条目。但是，异常缓慢的追随者或加入集群的新服务器(第6节)不会这样做。让这样的追随者与时俱进的方法是，领导者通过网络向其发送快照。

​ leader使用一个名为InstallSnapshot的新RPC向远远落后的follower发送快照;参见图13。当跟踪者接收到带有此RPC的快照时，它必须决定如何处理其现有的日志条目。通常，快照将包含收件人日志中尚未包含的新信息。在这种情况下，追随者丢弃其整个日志;它全部被快照取代，并且可能有与快照冲突的未提交条目。如果跟随者接收到描述其日志前缀的快照(由于重传或错误)，则快照所涵盖的日志条目将被删除，但快照后面的条目仍然有效，必须保留。

​ 这种快照方法违背了Raft的强领导原则，因为追随者可以在领导者不知情的情况下拍摄快照。然而，我们认为这种离开是合理的。虽然有一个领导者有助于在达成共识时避免冲突的决策，但在快照时已经达成了共识，因此没有决策冲突。数据仍然只能从领导者流向追随者，现在只有追随者可以重组他们的数据。

​ 我们考虑了另一种基于领导者的方法，其中只有领导者创建快照，然后将此快照发送给其每个追随者。然而，这有两个缺点。首先，将快照发送给每个关注者会浪费网络带宽并减慢快照进程。每个follower都已经拥有了生成自己的快照所需的信息，对于服务器来说，从其本地状态生成快照通常比通过网络发送和接收快照要便宜得多。其次，领导人的执行将更加复杂。例如，领导者需要向追随者发送快照，同时向他们复制新的日志条目，以便不阻止新的客户机请求。

​ 还有两个问题会影响快照性能。首先，服务器必须决定何时快照。如果服务器快照太频繁，会浪费磁盘带宽和能量;如果它的快照频率太低，就有耗尽存储容量的风险，并且会增加重新启动期间重播日志所需的时间。一个简单的策略是在日志达到固定大小(以字节为单位)时拍摄快照。如果将此大小设置为明显大于快照的预期大小，则用于快照的磁盘带宽开销将很小。

​ 第二个性能问题是，编写快照可能会花费大量时间，我们不希望这会延迟正常操作。解决方案是使用写时复制(copy-on-write)技术，这样就可以接受新的更新，而不会影响正在写入的快照。例如，用函数数据结构构建的状态机自然支持这一点。或者，可以使用操作系统的写时复制支持(例如Linux上的fork)来创建整个状态机的内存快照(我们的实现使用这种方法)。

IIX 客户端交互

​ 本节描述客户端如何与Raft交互，包括客户端如何找到集群领导者以及Raft如何支持线性化语义。这些问题适用于所有基于共识的系统，Raft的解决方案与其他系统类似。

​ Raft的客户将他们所有的请求发送给leader。当客户机第一次启动时，它连接到一个随机选择的服务器。如果客户端的第一选择不是leader，服务器将拒绝客户端的请求，并提供最近收到的leader的信息(AppendEntries请求包括leader的网络地址)。如果leader崩溃，客户端请求将超时;然后客户端使用随机选择的服务器再次尝试。

​ Raft的目标是实现可线性化的语义(每个操作在调用和响应之间的某个点上似乎是瞬间执行的，只执行一次)。然而，正如目前所描述的，Raft可以多次执行命令:例如，如果leader在提交日志条目之后崩溃，但在响应客户端之前，客户端将使用新的leader重试命令，导致它被执行第二次。解决方案是让客户端为每个命令分配唯一的序列号。然后，状态机跟踪为每个客户机处理的最新序列号，以及相关的响应。如果它接收到一个序列号已经被执行的命令，它会立即响应而不重新执行请求。

​ 可以在不向日志中写入任何内容的情况下处理只读操作。然而，如果没有额外的措施，这将有返回陈旧数据的风险，因为响应请求的leader可能已经被它不知道的新leader所取代。可linearizable读一定不能返回陈旧的数据，Raft需要两个额外的预防措施来保证这一点，而不使用日志。首先，leader必须拥有提交条目的最新信息。Leader完整性属性保证Leader拥有所有已提交的条目，但在其任期开始时，Leader可能不知道哪些是已提交的条目。为了找出答案，它需要提交其任期中的一个条目。Raft通过让每个leader在其任期开始时提交一个空白的无操作条目到日志中来处理这个问题。其次，leader必须在处理一个只读请求之前检查它是否已经被废弃(如果一个最近的leader被选举出来，它的信息可能是陈旧的)。Raft通过让leader在响应只读请求之前与大多数集群交换心跳消息来处理这个问题。或者，leader可以依赖心跳机制来提供一种形式的租约[9]，但这将依赖于安全的定时(它假设有界时钟倾斜)。

IX 执行与评估

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

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

IX.1 可理解性

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

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

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

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

​ 我们还在测试结束后对参与者进行了调查，看看他们觉得哪种算法更容易实现或解释;这些结果如图15所示。绝大多数参与者表示Raft更容易实现和解释(每个问题41个中有33个)。然而，这些自我报告的感觉可能不如参与者的测验分数可靠，参与者可能因为我们的假设(Raft更容易理解)而有偏见。

IX.2 正确性

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

IX.3 性能

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

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

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

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

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

X 总结

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

​ 在本文中，我们讨论了分布式共识的问题，其中一个被广泛接受但难以理解的算法Paxos多年来一直挑战着学生和开发人员。我们开发了一种新的算法Raft，我们已经证明它比Paxos更容易理解。我们也相信Raft为系统构建提供了更好的基础。将可理解性作为主要设计目标改变了我们设计《Raft》的方式;随着设计的进展，我们发现自己重复使用了一些技术，比如分解问题和简化状态空间。这些技术不仅提高了Raft的可理解性，而且使我们更容易相信它的正确性。