一种更容易理解的共识算法的研究（扩展版）

摘要

Raft是一种用于管理复制日志的共识算法。它产生和Paxos一样的结果，并且和Paxos一样高效，但是它的结构和Paxos不同；这使得Raft比Paxos更容易理解并且为构建使用系统提供了更好的基础。为了增强可理解性，Raft将共识算法的关键元素分开处理，例如：leader选举，日志复制以及安全性，并且执行更强等级的一致性来减少必须考虑的状态的数量。有研究表明Raft相比于Paxos被学生学习。Raft也包括一些新的机制来改变集群成员，它使用重叠的多数派来保证安全性。

Introduction

​ 共识算法允许一组一起作为一个一致的群体一起工作即便是一些成员出现错误。因此，它在构建一个可靠的大规模的软件系统中发挥着重要作用。在过去的十年里，Paxos在共识算法的讨论中占据主导地位，大部分共识算法的实现都是基于Paxos的，或者收到Paxos的影响，并且Paxos已经变成了教授学生共识算法时的主要工具。

不幸的是，Paxos相当难理解，尽管有许多尝试试图使它更容易接受。此外，他的架构需要复杂的改变才能支持实际的系统。结果就是，系统构建者和学生都对Paxos感到困惑。

​ 在我们自己与Paxos斗争之后，我们开始寻找一种新的共识算法可以为系统构建者和教育提供更好的基础。我们的方法有些不寻常，因为我们的主要目标是可理解性：我们是否可以为系统构建定义一种共识算法并且用一种显著地比学习Paxos简单的方式来描述它？此外，我们希望该算法可以促进对于系统构建者所必须的直觉的发展。重点不止是让算法有效，更重要的是让它的工作原理显而易见。

​ 这个工作的结果是一个名叫Raft的共识算法。在设计Raft的时候我们应用了一些特有的技术来提高可理解性，包括分解（Raft将leader选举，日志复制和安全性分开）和状态空间压缩（相较于Paxos，Raft减少了不确定性的程度以及服务器之间不一致的方式）。一个在2所大学的43个学生间展开的用户研究表明Raft显著的比Paxos易于理解：在学习两个算法之后，33个学生可以更好的回答关于Raft的问题而不是Paxos的问题。

​ Raft在许多方面和已经存在的共识算法很相似（最明显的是Oki和Liskov的Viewstamped Replication），但是它也有一些新颖的特点：

  • 强领导者：比起其它共识算法，Raft使用了更强的领导形式。例如，日志条目只从leader流向其它服务。这简化了复制日志的管理并给让Raft更容易理解

  • 领导者的选择：Raft使用随机化的计时器来选举领导者。这只给已经需要的心跳机制添加了一点点，同时简单而快速快速的解决冲突

  • 成员变化：Raft的改变集群中的服务的机制使用了一种新的联合共识方法，其中，两种不同的配置在转换过程中大部分重叠。这允许集群在配置改变期间继续正常的操作

    我们相信Raft比Paxos以及其它的共识算法更加的优越，无论是用于教育目的还是作为一个实现的基础。它比其他算法更加简单和容易理解；它被描述的足够完全，可以满足实际系统的需要；它有几个开源的实现并且被几个公司使用；它的安全属性被形式化的指出和证明；它的效率与其它算法相当。

    论文的剩余部分介绍了复制状态机问题（Section2），讨论了Paxos的优缺点（Section3），描述了我们实现可理解性的一般方法（Section4），表述了Raft共识算法（Section5-8），评估了Raft（Section9），并且讨论了相关工作（Section10）。

复制状态机

image-20231021101149962

图1：复制状态机架构。共识算法管理一个包含一个包含来自Client的状态机命令的复制日志。状态机执行来自日志中的相同的命令序列，所以它们产生相同的输出

​ 共识算法通常出现在复制状态机的背景下。在这种方法中，在一组服务器上的状态机计算同一个状态的相同复制，并且可以继续操作即是服务器宕机。复制状态机被用来解决分布式系统中的很多错误容忍问题。例如：只有一个集群leader的大规模系统，例如GFS，HDFS和RAMCloud，通常使用分开的复制状态机来管理leader的选举并且保存在leader发生冲突时必须保存下来的配置信息。复制状态机的例子包括Chubby和ZooKeeper

​ 共识算法的工作是保持复制日志的一致。服务器上的共识模块从客户端接收命令并将命令添加到它自己的日志中。它和其它服务器上的共识模块交流，确保每一个日志最终都包含相同顺序的相同请求，即便一些服务器失败。当命令被正确的复制，每一个服务器的状态机按照日志中的顺序处理它们，然后将输出返回给客户端。因此，服务器看起来像是一个单一，高可靠的状态机。

​ 实际系统中的共识算法通常有下列几个属性：

  • 它们在所有非拜占庭条件下保证安全性（从不返回不正确的结果），包括网络延迟，分区和数据包丢失，重复和重排序
  • 只要大部分服务器都能正常运行并且可以与其它服务器和客户端通信，它们就能完全发挥作用。因此，一个典型的五个服务器组成的集群可以容忍任何两个服务器的错误。假设服务器是通过停止而失败的，它们可能在稍后从稳定存储的状态上恢复并且重新加入集群
  • 它们不依赖于时钟来确保日志的一致性：错误的时钟和极端的消息延迟最坏只会引起可用性问题
  • 在常见的情况下，当集群中的大部分机器都对一轮远程过程调用产生了响应，一个命令就可以完成。少量的很慢的服务器不会影响整个系统的性能

What’s wrong with Paxos?

​ 在过去的十年中，Leslie Lamport的Paxos协议几乎变得等价于共识这个概念：它是课堂中最常见的协议，大部分共识的实现都以它作为起点。Paxos首先定义了一种能够就单一决策达成一致的协议，例如单个复制的日志条目。我们把这个子集成为single-decree Paxos。Paxos将这个协议的多个实例结合起来，以促进一系列的决策，比如一个日志（多Paxos）。Paxos确保了安全性和活性，并且它支持集群成员的改变。它的正确性已经被证明，并且在正常情况下是有效的。

​ 不幸的是，Paxos有两个显著的缺点。第一个缺点是Paxos特别难理解。完整的解释是出了名的晦涩；很少有人能理解它，除非付出巨大的努力。因此，有些人试图用更简单的术语来解释Paxos。这些解释关注single-decree的子集，但仍然具有挑战性。在2012年NSDI会议的与会者中进行的一次非正式的调查中，我们发现很少有人对Paxos感到舒适，即便是富有经验的研究人员。我们自己也是：我们也不能理解完整的协议直到阅读了几个简化的解释并且设计了我们自己的替代协议，这个过程花了近一年的时间。

​ 我们假设Paxos的晦涩源于它选择single-decree子集作为其基础。Single-decree Paxos是难以理解和微妙的：它被分成两个阶段，这两个阶段没有简单易懂的解释，也不能被单独地理解。因此，很难对single-decree协议为什么有效产生直觉。多Paxos的组合规则增加了显著的额外的复杂性和微妙性。我们相信就多个决策达成共识的整体问题（例如：一个日志而不是单一条目）可以用其它更明显和更直接的方式分解。

​ Paxos的第二个问题是Paxos没有提供一个很好的基础来构建实际的实现。一个原因是对于多Paxos，还没有一个广泛认可的算法。Lamport的描述主要是关于single-decree Paxos的；他勾勒了可能的多Paxos方法，但是许多细节都是缺失的。有许多充实和优化Paxos的尝试。但是它们都互不相同，并且也不同于Lamport的概述。Chubby系统已经实现了类似于Paxos的算法那，但是大部分实现的细节并未公布。

​ 此外，Paxos架构对于构建实际的系统来说是一个糟糕的选择，这也是single-decree分解的另一个结果。例如：独立地选择一组日志条目并且将他们合并为一个顺序的日志几乎没有什么好处，这只会增加复杂性。围绕一个日志设计一个系统更简单，也更有效，其中新的条目按照约束的顺序顺序的追加。另一个问题是Paxos在它的核心使用了一个对称的点对点方法（尽管它最终提出了一种弱形式的领导者作为性能优化）。这在一个简化为只有一个决策会被作出的世界中是有意义的，但是很少有实际的系统使用这个方法。如果一系列决策需要被作出，首先选举一个leader，然后让leader协调这个决策将更简单也更快。

​ 因此，实际系统几乎与Paxos没有相似之处。每一个实现都是从Paxos开始，发现实现它很困难，然后开发一个显著不同于Paxos的架构。这既耗时又容易出错，并且Paxos的难于理解又加剧了这个问题。Paxos的公式可能是证明其定理正确性的一个好的工具，但是真实的实现和Paxos如此的不同，以至于证明毫无意义。Chubby的实现者的以下评论是精彩的：

Paxos的算法描述和真实世界的系统有许多显著的差异······最终系统将会基于一个未被证明的协议

​ 因为这个问题，我们得出结论，Paxos没有给系统构建和教育提供一个好的基础。鉴于共识在大规模系统中的重要性，我们决定看看能够设计一个比Paxos拥有更好的性质的可以替代的共识算法。Raft就是这个实验的结果。

Designing for understandability

​ 我们在设计Raft的时候有几个目标：它必须提供一个完整和实际的基础用于系统构建，以便于显著地减少开发者需要的设计工作；它必须在所有情况下保持安全并且在一般的运行条件下保持可用；它必须对常见的操作高效。但是我们最重要的目标、最大的挑战是可理解性。必须使广大受众可以舒适的理解这个算法。此外，必须使人们对这个算法产生一种直觉，以便于系统构建者可以实现真实世界中不可避免的扩展。

​ 在Raft设计中，有许多点我们需要再不同的方法之间进行选择。在这些情况下，我们根据可理解性来评估这些方法：解释每种方法有多困难（例如：它的状态空间有多复杂，是否有微妙的含义？），对于一个读者来说有多容易可以完全理解这个方法以及它的含义？

​ 我们认识到这种分析中有很高的主观性；尽管如此，我们使用了两种通用的方法。第一种方法是众所周知的问题分解：尽可能的，我们将问题分成一些可以被相对地独立解决、解释和理解的部分。例如：在Raft中，我们将leader选举，日志复制，安全性和成员改变分开。

​ 我们的第二个方法是通过减少需要考虑的状态的数量来简化状态空间，是系统更加清楚易懂并且消除了可能的不确定性。具体来说，日志不允许有空洞，Raft限制了日志间产生不一致的方式。尽管在大部分情况下我们尝试消除不确定性，但是事实上有一些情形下不确定性提高了可理解性。尤其是，随机化的方法引入了不确定性，但是它们通过使用相似的形式来处理所有可能的选择，试图减少状态空间。我们使用随机性来简化Raft的leader选举算法。

The Raft consensus algorithm

​ Raft是一个用来管理Section2中描述的复制日志形式的算法。图2以简明的形式总结了算法，以供参考，图3列出了算法的关键属性；这些图中的元素将在本章的剩余部分逐个讨论。

​ Raft首先选举一个leader，然后将管理复制日志的全部责任给这个leader，以此来实现共识。leader从clients接受日志条目，将它们复制到其它服务器，然后告诉服务器什么时候将日志条目应用到他们的状态机是安全的。拥有leader简化乐复制日志的管理。例如：leader可以决定在日志中的什么位置放置新的条目而不用和其它服务器协商，并且数据流以简单的方式从leader流向其它服务器。一个leader可以失败或者与其它服务器断开连接，在这种情况下会选举一个新的leader。

​ 基于leader的方法，Raft将共识问题分解为三个相对独立的子问题，它们将在下列小节中讨论：

  • Leader election：当一个存在的leader失败了，一个新的leader必须被选择

  • Log replication：leader必须接收来自clients的日志条目并且在集群中复制它们，强迫其它日志与自己拥有的日志一致

  • Safety：Raft的关键的安全属性是图3中的状态机安全属性：如果任何服务器已经将特定的日志条目应用到它的状态机，那么之后就没有其它服务器会对同一个日志索引应用不同的命令。Section5.4描述了Raft如何确保这一属性；解决方案涉及到在Section5.2描述的选举机制上追加的一个额外的限制

    在表述完共识算法之后，这个章节将会讨论可用性的问题以及计时器在系统中的作用。

image-20231022162223361

图2：一个Raft共识算法的简明的总结（不包括成员改变和日志压缩）。左上角框框中的的服务器的行为被描述为一组独立且重复触发的规则。章节数字类似于§5.2指出讨论特定功能的地方。一个形式化的描述（ONGARO, D. Consensus: Bridging Theory and Practice. PhD thesis, Stanford University, 2014 (work in progress).）更精确的描述了算法。

image-20231022163841879

图3：Raft保证在每一时刻每一个这些属性都为真。章节数字指出属性在哪里被讨论。

Raft basics

​ 一个Raft集群包含几个服务器；通常这个数字是5，这允许系统容忍2个错误。在任何给定的时间内，服务器处于三个状态之一：leader，follower，或者是candidate。在正常运行期间，只有一个leader，其它服务器都是followers。Followers是被动的，它们自己不提出请求，只是简单地响应从leaders和candidates来的请求。leader处理所有的客户端请求（如果一个客户端联系一个follower，这个follower会将请求重定向到leader）。第三个状态，candidate，被用来选举一个像Section5.2中描述的那样的新的leader。图4展示了状态和它们的转变；变化过程在下面讨论。

image-20231023120620330

图4：服务器状态。Followers仅仅响应从其它服务器来的请求，如果follower没有接收到任何通信，它会变成candidate并且发起一轮选举。一个candidate收到集群中绝大多数节点的投票之后就会成为新的leader。leaders通常一直运行直到它们失败。

image-20231023121042569

图5：时间被分成任期，米诶一个任期以选举开始。在成功选举之后，一个leader会管理集群直到任期结束。在选举失败的情况下，任期将会结束而没有一个leader。这个任期之间的变化可能在不同的时间被不同的服务器观察到。

​ Raft将时间分成任意长度的任期，就像图5中显示的那样。每个任期都有一个连续的整数编号。每一个任期都以选举开始，一个或者多个候选者尝试变成5.2节中描述的leader。如果候选者赢得了选举，那么它在剩余的任期内将作为leader服务。在一些情形下，选举会产生平票。在这种情况下，这个任期之内就没有leader，不久之后，一个新的任期（伴随着新的选举）将会开始。Raft确保了一个任期内最多有一个leader。

​ 不同服务器也许会在不同的时间观察到任期的转换，在一些情况下一个服务器可能不会观察到一个选举甚至是一整个任期。任期在Raft中充当了逻辑时钟，它们允许服务器检测过时的信息，例如过时的leaders。每一个服务器存储一个当前的任期编号，它随着时间单调地增长。当服务器之间进行交流时会交换任期编号；如果一个服务器当前的任期编号小于其它服务器的，那么它会将自己的当前任期编号更新为较大的那个值。如果一个候选者或者了领导者发现它的任期过时了，它会立刻恢复到follower的状态。如果一个服务器接受到一个带有过时任期编号的请求，那么它会拒绝这个请求。

​ Raft服务器使用远程过程调用（RPCs）来进行交流并且基础的共识算法仅仅需要两种类型的RPCs。RequestVote RPCs由candidates在选取期间（Section5.2）发起，AppendEntries RPCs由leaders发起来复制日志条目并且提供一种心跳机制。Section7添加了第三种RPC用于在服务器之间传输快照。服务器如果没有及时接收到响应，它会重试RPCs。并且为了最佳的性能，他们会并行的发起RPCs。

Leader election

​ Raft使用心跳机制来触发leader选举。当服务器启动时，他们会先变成followers。服务器会保持在follower状态只要它从leader或者candidate收到有效的RPCs。Leaders周期性的发送心跳（不携带日志条目的AppendEntries RPCs）给所有的followers，以便于维持它们的权利。如果一个follower在一段时间内没有收到沟通，这段时间被称为选举超时，它会假定没有可用的leader并开始一轮选举来选择一个新的leader。

​ 在开始一轮选举时，一个follower会增加它当前的任期并且转变到candidate状态。它会投票给它自己然后并行的发送RequsetVote RPCs给集群中的每一个服务器。candidate继续保持在这个状态直到下面三件事中的一件发生（a）它赢得选举，（b）另一个服务器确立它自己是leader，或者（c）一段时间过去了但没有胜利者。这些结果将在下面的段落中逐一讨论。

​ 如果一个candidate在一个任期内接收到来自集群中的绝大多数服务器的投票，那么它赢得选举。每一个服务器会在一个任期内给至多一个candidate投票，按照先到先得的原则（注意：Section5.4添加了对投票的额外限制）。多数规则确保在一个特定的任期内至多一个candidate可以赢的选举，然后它会变成leader。并且它会发送心跳消息给所有其它服务器来确立自己的权威并且阻止新的选举。

​ 在等待投票时，candidate可能会收到来自其它服务器的AppedEntries RPC声称它是leader。如果这个leader的任期（包含在它的RPC中）至少和candidate的当前任期一样大，candidate 就认为这个leader是合法的然后返回到follower状态。如果这个RPC中包含的任期比candidate的当前任期要小，那么candidate拒绝这个RPC然后继续保持在candidate状态。

​ 第三个可能的结果是candidate在选举中既没有获胜也没有输掉：如果许多followers在同一时间变成candidates，那么投票可能会分散导致没有candidate获得大多数投票。当这种情况发生的时候，每个candidate都将超时然后通过增加它们的任期然后发起另一轮RequestVote RPCs，开启一轮新的选举。然而，如果没有额外的措施，分散选票的情况可能会无限期的重复。

​ Raft使用随机化的选举超时来确保分散投票的情况很少，即便发生也可以很快的解决。为了防止投票分散，会从一个固定的区间内随机地选择选举超时时间。这分散了服务器，使得大多数情况下仅仅有一个单一的服务器会超时；它赢的选举并在其它服务器超时之间发送心跳。同样的机制被用来处理投票分散。每一个candidate在选举开始时重新启动它的随机话选举超时，然后等待超时结束之后才开始下一轮选举；这降低了新一轮选举出现投票分散的可能性。Section9.3展示了这种方法可以快速地选出一个leader。

image-20231023205812247

图6：日志由条目组成，并被按顺序编号。每一个条目都包含它创建的任期（盒子里的数字）和一个状态机的命令。一个条目如果可以安全地应用到状态机，那么它被认为是完成提交的。

​ 选举是这个例子显示了可理解性如何引导我们在设计方案之间进行选择。最初我们计划使用一个排名系统：每个candidate被分配一个独特的排名，用于在竞争的候选人之间作出选择。如果一个candidate发现另一个candidate拥有更高的排名，它将会返回到follower状态以便于更高排名的candidate可以更容易的赢的下一次选举。我们发现这种方法会产生一种微妙的可用性问题（更低排名的服务器可能需要超时并再次成为candidate，如果更高排名的服务器失败了的话，但是如果它太早这样做的话，它就可能会重置选举领导者的进度）。我们对算法进行了几次调整，但是在调整之后都会遇到一些新的边界请款。最终，我们得出的结论是随机重试的方法更清晰也更容易裂解。

Log replication

​ 当一个leader被选举出来，它就开始处理客户端的请求。每一个客户端请求包含一个要被复制状态机执行的请求。leader将命令作为一个新的条目添加到它的日志中，然后并行地向其它服务器发起AppendEntries RPCs请求来复制该条目。当一个条目被安全地复制（像下面描述的那样）时，leader将这些条目应用到它的状态机然后将执行的结果返回给client。如果followers产生冲突或者运行很慢，或者是网络包丢失，leader会无限期地重试AppendEntries RPCs（即便它已经响应了client）直到所有的followers最终存储了所有的日志条目。

​ 日志的组织方式如图6所示。每一个日志条目存储一个状态机命令，以及leader接收到这个条目时的任期号。日志条目中的任期号被用来检测日志间的不一致性，并且确保图3中的一些属性。每一个日志条目还有一个整数索引来标识它在日志中的位置。

​ leader决定了什么时候可以安全地将日志条目应用到状态机上；这样的条目称为已经提交的。Raft保证已经提交的条目是持久的并且和最终会被所有可用的状态机执行。当一个创造这个条目的leader已经把它复制到绝大多数服务器上（例如：图6中的条目7），这个日志条目就提交了。这也提交了这个leader的日志中的所有的先前条目，包括又之前的leader创建的条目。Section5.4讨论了在领导者变化之后应用这个规则的一些细节，并且表明了这个对于提交的定义是安全的。leader对它所知道的已经被提交的最大的索引保持记录，并且在未来的AppendEntries RPCs（包含心跳）中包含这个索引，以便于其它服务器最终发现它。一旦一个follower认识到一个日志条目是已经提交的，它会将这个条目应用到它本地的状态机（按照日志的顺序）。

​ 我们设计了Raft的日志机制来使不同服务器的日志保持高一致性。这不仅仅简化了系统的行为并且使得行为更容易预测，它也是确保安全的一个重要的部分。Raft维持着以下性质，它们一起构成了图3中的日志匹配属性：

  • 如果两个不同日志中的条目拥有相同的索引和任期，那么它们存储着相同的命令
  • 如果两个不同日志中的条目有相同的索引和任期，那么日志所有的先前的条目都是一样的

​ 第一个性质来源于一个事实，对于一个给定任期和给定的日志索引，leader最多创建一个条目，并且日志条目永远不会改变它们在日志中的位置。第二个性质由一个由AppendEntries执行的简单的一致性检查保证的。当发送一个AppendEntries RPC，leader包含了日志中位于新条目之前那个条目的索引和任期。如果follower没有没有再它的日志中找到一个有着同样索引和任期的条目，它就拒绝新的条目。一致性检查起到了归纳的步骤：日志的初始空状态满足日志复制属性，并且一致性检查在日志扩增的时候保护了日志复制属性。因此，只要AppendEntries返回成功，leader就知道follower的日志和自己的日志是一样的，除了这个新条目。

​ 在正常运行期间，leader和follower的日志保持一致，所以AppendEntries一致性检查从不失败。然而，leader崩溃可能会导致日志不一致（旧leader可能没有完全复制它日志中的所有条目）。这些不一致性可能在一系列leader和follower崩溃后累积。图7阐述了在什么情况下follower的日志可能与新leader的日志产生差异。Follower可能缺少leader上存在的条目，可能有leader上不存在的条目，或者两种情况都有。日志中缺失和多余条目的问题可能跨越多个任期。

image-20231024095510176

图7：当leader上台时，follower的日志中可能出现任何一种情况（a-f）。每一个框框都代表一个日志条目；框框中的数字是任期。Follower可能会缺失条目（a-b），可能有额外的未提交的条目（c-d），或者都有（e-f）。例如，情况（f）可能发生的情况是，如果服务器是任期2的leader，在自己的日志中添加了额外的几个条目，然后在全部提交日志之间崩溃了；它迅速地重启，变成任期3的leader，并添加了更多条目到自己的日志中；在任期2和任期3中的所有日志都提交之前，服务器再次崩溃了并在后续几个任期中都保持离线。

​ 在Raft中，leader通过强制follower的日志复制自己的来处理不一致性。这意味着follower中冲突的条目将会被leader日志中的条目重写。Section5.4将会显示在加上一个限制之后，这将是安全的。

​ 为了使follower的日志和自己的保持一致，leader必须找到最新一条两个都相同的日志条目，删除在这个点之后的所有的follower日志，并且将这个点之后所有的leader日志发送给follower。所有这些行为都是响应AppendEntries执行的一致性检查而发生的。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 RPCs的数量来进行有优化。例如，当拒绝一个AppendEntries请求的时候，follower可以包含冲突条目的任期以及它为这个任期储存的第一个索引。有了这些信息，leader可以减少nextIndex来跳过该任期内所有的冲突条目；每个有冲突条目的任期只需要一个AppendEntries RPC，而不是每个条目一个RPC。在实践中，我们怀疑这种优化是否有必要，因为失败发生的不频繁并且不太可能存在很多不一致的条目。

​ 有了这种机制，leader在上任时不需要采取任何特殊措施来恢复日志的一致性。它只需要开始正常运行，日志会自动收敛以应对AppendEntries的一致性检查。leader从不重写或者删除它日志中的条目（图3中的Leader Append-Only特性）。

​ 日志复制机制展示了Section2中描述的期望的共识性质：Raft可以接收，复制，应用新的日志条目只要大部分服务器都在运行；在正常情况下一个新的条目可以通过一轮RPCs来复制到大多数集群，并且一个缓慢的follower不会影响性能。

Safety

​ 前面的章节描述了Raft如何选择leaders并且复制日志条目。然而，目前为止描述的机制不足以确保每一个状态机以相同的顺序执行相同的命令。例如，follower可能会在leader提交几个日志条目时不可用，然后它可能会被选为leader并用新的条目来覆盖这些条目；因此，不同的状态机可能执行不同的命令序列。

​ 这个章节通过在leader的选举添加一个额外的限制来完善Raft算法。这个限制确保任意给定一个任期内的leader包含所有之前任期已经提交的所有条目（图3中的Leader Completeness属性）。给定选举的限制，我们又使提交规则更加的精确。最终，我们给出了Leader Completeness属性的大概证明并且说明了它如何引导复制状态机作出正确的行为。

Election restriction

​ 在任何基于leader的共识算法中，leader必须最终存储所有提交的日志条目。在一些共识算法中，例如Viewstamped Replication，leader即使最初不包含所有提交的条目也可以被选举。这些算法包含额外的机制来识别缺失的条目，并将它们传输给新的leader，不论是在选举过程中还是在不久之后。不幸的是，这会导致相当多的额外机制和复杂性。Raft使用更简单的方法，它保证了所有先前的任期内提交的条目在leader被选举的那一刻开始就存在leader上，而不用条目传输给leader。这意味着日志条目是单向流动的，并且leader从来不会重写它们日志中存在的条目。

​ Raft使用投票过程来防止一个candidate赢得选举除非它的日志包含所有提交的日志。candidate必须联系集群中的大多数才能被选举，这意味着每一个提交的条目必须至少存在在一个服务器中。如果candidate的日志至少与联系的这个大多数的日志一样新的话（“新”在下面被准确的定义），它就拥有所有提交的条目。RequestVote RPC实现了这个限制：这个RPC包含关于candidate日志的信息，并且投票者拒绝这个投票如果它的日志比candidate更新的话。

​ Raft决定两个日志中哪个更新是通过比较日志中最后的条目的索引与任期。如果日志的最后一个条目拥有不同的任期，那么拥有更靠后任期的日志是更新的。如果日志以相同的任期结束，那么更长的日志是更新的。

Committing entries from previous terms

image-20231024220328833

图8：一个时间序列展示了为什么leader不能使用旧任期的日志条目来决定提交。在（a）中，S1是leader并且部分复制了索引2处的日志条目。在（b）中，S1崩溃；S5在任期3中通过S3、S4以及它自己的投票被选举为leader，然后在索引2处接受了一个不同的条目。在（c）中，S5崩溃了；S1重启，然后被选举为leader，然后继续复制。此时，从任期2来的日志条目已经被复制到了大多数服务器，但是没有被提交。如果S1像（d）中一样崩溃，S5可以被选举为leader（来自S2，S3，S4的投票）并用它来自任期3的日志条目重写这个条目。然而，如果S1在崩溃之前在它当前的任期从大多数服务上复制一个条目，就像（e）中，然后这个条目被提交（S5不能赢的选举）。此时，日志中所有前面的条目也被提交了。

​ 就像在Section5.3中描述的那样，leader知道来自当前任期的条目，一旦被存储到大多数服务器上就被提交了。如果一个leader在提交条目前崩溃，未来的leader将会尝试完成条目的复制。然而，一旦一条来自先前任期的条目被存储在大多数的服务器上，leader就不能立刻推断出这个条目被提交了。图8阐述了一种情形，在这种情形下旧日志条目被存储在大多数服务器上，但仍然可以被未来的leader重写覆盖。

​ 为了消除像图8中的问题，Raft从不通过统计复制的数量提交来自先前任期的日志条目。只有来自当前任期的日志条目通过统计复制的数量来提交；一旦一个来自当前任期的条目被通过这种方式提交，那么所有先前的条目都已经被间接提交了，因为Log Matching特性。在一些情形下，leader可以安全地推断出一个旧的日志条目被提交了（例如：如果这个条目存储在每一个服务器上），但是为了简单，Raft采用了一个更为保守的方式。

​ Raft在提交规则中引入额外的复杂性，因为当leader复制来自先前任期的条目时，日志条目保存着他们最初的任期数字。在其它共识算法中，如果一个新的leader从先前的任期复制条目，它必须用到它的新任期数字。Raft的方式使得对日志条目进行推理更容易，因为它们随着时间和日志的变化仍然保存着同样的数字。此外，相比于其它算法，Raft中新的leader从前一个任期发送的日志条目更少（其它算法必须发送冗余的日志条目来在他们被提交之前对它们重新编号）。

Safety arguement

​ 给出了完整的Raft算法，我们现在可以更准确地论证Leader Completeness属性（这个论证基于安全属性；参考Section9.2）。我们假设Leader Completeness属性不成立，然后我们来推出矛盾。假设任期T的leader（$leader_T$）在它任期的一个日志条目，但是这个日志条目没有被未来任期的leader存储。考虑一个最小的任期$U > T$，任期的leader($leader_U$没有存储这个条目)。

image-20231025140744341

图9：如果S1（任期T的leader）提交一个它任期内的新的日志条目，并且S5在之后的任期U中被选举为leader，那么至少有一个服务器（S3）接收了这个日志条目并且也给S5投票。

  1. 这个已经提交的条目必须在$leader_U$被选举时不存在于它的日志中（leaders从不删除或者重写条目）。
  2. $leader_T$将条目复制到大多数集群中，$leader_U$接收到大多数集群的投票。因此，至少有一个服务器（投票者）即接受了来自$leader_T$的条目又给$leader_U$投票，就像图9中显示的那样，这个投票者是推出矛盾的关键。
  3. 这个投票者在给$leader_U$投票之前，必须接收了来自$leader_T$的已经提交的条目。否则它会拒绝来自$leader_T$的AppendEntries请求（它当前的任期比T高）。
  4. 这个投票者在投票给$leader_U$时仍然存储着这个条目，因为每个介入的领导者都包含了这个条目（根据假设），leaders从不移除条目，followers仅仅在和leader产生冲突的时候移除条目。
  5. 这个投票者给$leader_U$投票，所以$leader_U$的日志必须和投票者一样新。这会导致两种矛盾中的一个。
  6. 首先，如果投票者和$leader_U$具有相同的最后一个任期，$leader_U$的日志必须至少和投票者一样长，所以它的日志包含着投票者日志中的每一个条目。这是一个矛盾，因为投票者包含已经这个提交的条目但是$leader_U$被假设没有这个条目。
  7. 否则，$leader_U$的最后一个日志的任期必须比投票者的大。而且，它比T大，因为投票者的最后一个日志的任期至少是T（它包含T任期提交的条目）。先前创建了$leader_U$的最后一个日志条目的leader的日志中必须包含这个已经提交的条目（根据假设）。然后，通过Log Matching属性，$leader_U$的日志必须也包含这个已经提交的条目，这也是一个矛盾。
  8. 这推出了矛盾。因此，所有任期T之后的leader必须包含任期T提交的所有条目。
  9. Log Matching属性保证了未来的leaders也包含间接提交的条目，例如图8中的index 2。

​ 根据Leader Completeness属性，我们可以证明图3中的State Machine Safety属性，它表面如果一个服务器将给定的索引上的一个日志条目应用到它的状态机上，那么没有其它服务器会在同样的索引上应用一个不同的日志条目。在一个服务器将一个日志条目应用到它的状态机时，它的日志必须和leader的包含这个条目的日志相同并且这个条目必须被提交了。现在考虑任意服务器应用一个给定索引的最低任期；Log
Completeness属性保证了所有更高任期的leader将会存储同样的日志条目，所以服务器在之后的任期中应用到这个索引的时候也应用的是同样的值。因此，State Machine Safety属性证明完成。

​ 最终，Raft需要服务器按照日志索引的顺序应用条目。结合StateMachine Safety属性，这意味着所有服务器将会以相同的顺序应用完全相同的一组日志条目到自己的状态机中。

Follower and candidate crashes

​ 到目前为止我们聚焦于leader的失败。follower和candidate崩溃处理起来比leader奔溃要简单，并且它们的处理方式相同。如果一个follower或者candidate崩溃，在将来发送给他们的RequestVote和AppendEntries RPCs将会失败。Raft通过无限期的重试来处理这些问题；如果崩溃的服务器重启，那么RPC将会成功地完成。如果一个服务器在完成RPC之后，但响应之前崩溃，那么它会在重启后再次接收到同样的RPC。Raft的RPC是幂等的，所以这没有什么危害。例如，如果一个follower接收到一个AppendEntries请求，其中包含的日志条目已经在它的日志中了，它就会忽略那些新请求中重复出现的条目。

Timing and availability

​ 我们对于Raft的一个要求是它的安全性必须不依赖于时间：系统必须不能仅仅因为一些事件发生的比预期的更快或者更慢而产生不正确的结果。然而，可用性（系统及时响应客户端的能力）不可避免地依赖于时间。例如，如果消息交换花费的时间比通常情况下的服务器崩溃时间要长，candidate就不能存活足够的时间来赢得选举；没有一个稳定的leader，Raft就不能取得进展。

​ 时间再Raft的leader选举中非常重要。Raft将会可以选举并维护一个稳定的leader，只要系统满足下面的时间要求：

​ 在这个不等式中，broadcastTime 是一个服务器并行给集群中的所有服务器发送RPCs并收到响应的平均时间；electionTimeout 是Section5.2描述的选举超时；MTBF 是单个服务器发生故障之间的平均时间。广播时间应该比选举时间小一个量级，以便于leader可以可靠地发送需要的心跳消息来避免follower开始选举；由于给定了一个随机化的方式用于选举时间，这个不等式也使得投票分散不太可能发生。当leader崩溃，系统将会在大概和选举超时差不多长的时间内变得不可用；我们希望这只占用总时间的一小部分。

​ 广播时间和MTBF是底层系统的属性，选举超时是我们必须选择的。Raft的RPCs通常要求接收方将信息持久化到稳定的存储中，所以广播时间通常范围是0.5ms到20ms，这取决于存储技术。因此，选举超时可能大约在10ms到500ms之间。通常服务器MTBF是几个月或者更多，这很容易满足时序要求。

Cluster membership changes

​ 到目前为止我们都假定集群的配置（参与共识算法的一组服务器）是固定的。在实际中，偶尔会需要改变配置，例如在服务器故障时替换服务器或者改变复制的程度。虽然可以通过将整个集群下线，更新配置文件然后重启集群来完成，但是这样在更换期间集群就不可用。此外，如果有任何手动的操作，它们有操作失败的危险。为了避免这些问题，我们决定将配置改变自动化并将它纳入Raft共识算法。

​ 为了配置改变机制的安全，必须在转换期间不能出现两个leader在同一任期被选举的情况。不幸的是，任何直接从就配置切换到新配置的方式都是不安全的。不可能自动化地一次完成所有服务器的切换，所以集群可能潜在地在转变过程中分成两个独立的群体（参考图10）。

图10：直接从一个配置切换到另一个配置是不安全的，因为不同的服务器在不同的时间切换。在这个例子中，集群从3个增长到5个。不幸的是，有一个时间点两个不同的leader可以在同一个任期被选举，一个代表旧配置中的大多数（$C{old}$），一个代表性集群的大多数（$C{new}$）。

​ 为了确保安全，配置改变必须使用两阶段的方式。有许多方式可以实现两阶段。例如L一些系统使用第一阶段使旧配置不可用，所以它不能处理客户端的请求；然后第二节点启用新配置。在Raft中，集群首先切换到一个我们称为联合共识的过渡配置；一旦联合共识被提交，系统就会转换到性配置。联合共识结合了旧配置和新配置：

  • 日志条目被复制到两个配置中的所有服务器上
  • 任何来自于两个配置中的服务器都可能作为leader
  • 认同（对于选举和条目提交）需要分别来自就配置和新配置的大多数

​ 联合共识允许单独的服务器在不同的时间进行配置之间的转变，而不影响安全性。此外，联合共识允许集群在配置改变期间继续服务客户端的请求。

image-20231025200705733

图11：配置改变的时间线。虚线表示创建了但还没有提交的配置条目，实线表示最新提交的配置文件条目。leader首先在它的日志中创建$C{old,new}$配置条目，并把它提交到$C{old,new}$（大部分$C{old}$和大部分$C{new}$）。然后它创建$C{new}$条目并把它提交到$C{new}$的大部分上。没有一个时间点是$C{old}$和$C{new}$可以同时独立决策的。

​ 集群配置使用复制日志中的特殊条目来存储和传递；图11阐述了配置的改变过程。当leader接收到一个将配置从$C{old}$变化到$C{new}$的请求，它将联合共识的配置存储为一个日志条目，然后使用先前描述的机制复制这个条目。一旦一个服务器吧新的配置条目添加到它的日志中，它使用该配置来作出未来的所有决定（服务器总是使用它日志中最新的配置，不管配置条目是否提交）。这意味着leader将会使用$C{old,new}$的规则来决定$C{old,new}$什么时候被提交。如果leader崩溃，一个新的leader也许会在$C{old}$或$C{old,new}$下被选出，这取决于胜利的candidate是否收到$C{old,new}$。在任何情况下，$C{new}$在这个时期不作出单方面的决策。

​ 一旦$C{old,new}$被提交了，$C{old}$和$C{new}$都不能在没有对方批准的情况下作出决策，Leader Completeness Property确保只有有$C{old,new}$的日志条目的服务器可以被选举为leader。现在对于领导者来说，创建一个描述$C{new}$的日志条目并将它复制到集群是安全的。同样，这个配置会在每个服务器看到它的时候立刻生效。当新的配置在$C{new}$规则下被提交，就服务就变得无关了，并且不在新配置中的服务器将会被关闭。就像图11中显示的，没有任何时间$C{old}$和$C{new}$可以同时作出单方面的决策，这保证了安全性。

​ 关于重新配置还有三个问题需要解决。第一个问题是，新的服务器最初可能没有存储任何日志条目。如果它们在这个状态被加入到集群中，它们可能会需要一段时间来追赶，这段时间可能不能提交新的日志条目。为了避免可用性间隙，Raft在配置改变之前引入了一个额外的阶段，在这个阶段新的服务器以非投票成员的方式加入到集群中（leader复制日志条目给它们，但它们不被考虑为大多数）。一旦新的服务器赶上了集群中的其它服务器，重新配置就可以按上述方式进行。

​ 第二个问题是集群的leader也许不是新配置中的一部分。在这种情况下，leader一旦提交了$C{new}$日志条目之后就下台（返回follower状态）。这意味着将会存在一段时间（在提交$C{new}$期间），在这段时间之后leader管理着一个不包含它的集群；它复制日志条目但不把自己计入大多数当中。leader的转换发生在$C{new}$被提交的时候，因为这是第一个时间节点配置可以独立运行（将总是有可能从$C{new}$中选择一个leader）。在这个节点之前，可能只有来自$C_{old}$的服务器可以被选举为leader。

​ 第三个问题是移除的服务器（那些不在$C_{new}$中的）可以影响集群。这些服务器将会接收到心跳，所以它们会超时并且开启新的选举。它们将会以新的任期号发送RequestVote RPCs，这会引起当前的leader重置到follower状态。一个新的leader最终会被选举出来，但是被移除的服务器会再次超时然后这个过程会重复，导致很差的可用性。

​ 为了防止这个问题，当它们相信当前的leader存在的时候，服务器会忽略RequestVote RPCs。具体来说，如果服务器在从当前leader收到消息的最小选举超时内收到一个RequestVote RPC，它不会更新它的任期或者投票。这不影响正常的选举，其中每个服务器在开始一轮选举之前至少等待最小的选举超时时间。然而，这帮助避免了移除的服务器的影响；如果一个leader能够从它的集群获取心跳，，那么它就不会被更大的任期数字罢免。

Log compaction

​ Raft的日志在正常运行期间增长，以包含更多的客户端请求，但是在实际系统中，它不能无限地增长。随着日志越来越长，它会占据更多的空间并且花费更多的时间来重放。如果不采用一些机制来丢弃积累在日志中的过时信息，最终会引起可用性问题。

​ 快照是最简单的方式来进行压缩。在快照方式中，整个当前系统的状态被写入一个快照中，放在一个稳定的存储上，然后该节点之前的整个日志被丢弃。快照被用在Chubby和ZooKeeper中，本章的剩余部分将描述Raft中的快照。

​ 增量的压缩方式，例如日志清理和日志结构合并树也是可能的。它们一次在一部分数据上进行操作，所以它们将压缩的负载随时间分布更均匀。他们首先选择一个积累了许多删除和重写的对象的数据的区域，然后它们更紧凑地重写这个区域的活动对象并且释放这个区域。和快照相比，这需要显著的额外机制和复杂性，快照通过总是在整个数据集上操作简化问题。虽然日志清理需要对Raft进行修改，状态机可以使用与快照相同的接口来实现LSM树。

image-20231026095230804

图12：服务器用新的快照替换它日志中已经提交的条目（index 1 到 5），快照只储存当前状态（例子中时变量x和y）。快照的最后包含索引和任期用于在条目6之前的日志中定位。

​ 图12显示了Raft中的快照的基本思想。每一个服务器独立的进行快照，只覆盖它日志中已经提交的部分。大部分工作由状态机将当前状态写入快照完成。Raft在快照中也包含一小部分元数据：最后包含索引是日志中最后一个被快照替换（最后一个被状态机应用的条目）的条目索引，最后包含任期是这个条目的任期。这些数据被保存以支持快照后第一个日志条目的AppendEntries一致性检查，因为这个条目需要先前的日志的索引和任期。为了使集群成员能够改变（Section6），快照也包含了截止到最后包含索引时日志中的的最新配置。一旦服务器完成了快照的写入，它就会删除直到最后包含索引的所有的日志条目，以及任何先前的快照。

​ 尽管服务器通常独立使用快照，leader必须偶尔给滞后的follower发送快照。这种情况发生在领导者已经丢弃了它需要发送给follower的下一个条目的时候。幸运的是，这种情形在正常运行时是不太可能的：一个跟上leader的follower已经拥有了这个条目。然而，一个意外地慢的follower或者是一个新加入集群的服务器（Section）可能没有。让这样的follower更新的方法是leader通过网络给它发送一个快照。

image-20231026104658855

图13：InstallSnapshot RPC的总结。快照被分成块进行传输；这给了follower每个块的生命记号，所以它可以重置它的选举计时器。

​ leader使用一个新的RPC，叫做InstallSnapshot，来给落后太多的follower发送快照；参考图13。当一个follower从这个RPC接收到一个快照，它必须决定如何处理现在存在的日志条目。通常快照包含不存在于接受者的日志中的新信息。在这种情况下，follower丢弃它的整个日志；它将全部被快照取代并且可能有未提交的条目和快照冲突。如果相反，follower接收到描述它的日志前缀的快照（由于重传或者错误），那么被快照覆盖的日志条目被删除，但是快照之后的日志条目依然有效并且需要被保存。

​ 这种快照方法偏离了Raft的强leader原则，因为follower可以在leader不知情的情况下进行快照。然而，我们认为这种偏离是合理的。leader帮助避免冲突的决策来达到共识，但是在快照的时候共识已经达到了，所以没有决策冲突。数据依旧从leader流向follower，只是follower现在可以重新组织它们的数据。

​ 我们考虑了一种基于leader的替代方案，在这种方案中只有leader可以创建快照，然后它会把快照发送给每个follower。然而，这有两个缺点。第一，给每个follower发送快照浪费网络带宽并且减慢了快照处理。每一个follower都已经有产生它自己的快照需要的信息，通常服务器从本地状态中产生快照要比它通过网络发送和接收一个的花销要小。第二，leader的实现会更复杂。例如，leader需要再并行地将快照复制给follower时并行地发送快照，以免阻塞客户端的新请求。

​ 有两个问题影响快照性能。第一，服务器必须决定什么时候进行快照。如果服务器太频繁地进行快照，会消耗磁盘带宽和能源；如果快照太少，就有可能耗尽存储容量，并且增加了重启时需要重放日志的时间。一个简单的策略是当日志达到固定的字节数是进行快照。如果这个大小被设置的比预计的快照大小显著地大很多，那么用于快照的磁盘带宽的开销就会很小。

​ 第二个性能问题是写快照可能需要大量时间，我们不希望这耽误正常的操作。解决办法是使用写时复制技术，这样可以在不影响写入的快照的情况下接收新的更新。例如，使用函数式数据结构构建的状态机自然地支持这一点。或者，可以使用操作系统的写时复制支持（例如，Linux中的fork）来创建整个状态机的内存快照（我们的实现使用这种方式）。

Client interaction

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

​ Raft的客户端将所有的请求发送到leader。当客户端第一次启动，它连接到一个随机选择的服务器。如果客户端的第一个选择不是leader，那么连接的服务器就会拒绝客户端的请求并且提供它最近听说的leader的信息（AppendEntries请求，包括leader的网络地址）。如果leader崩溃。客户端请求将会超时；然后客户端会再次尝试连接一个随机选择的服务器。

​ 我们对Raft的目标是让它实现线性化语义（每个操作看起来是瞬间执行的，只执行一次，在调用和响应之间的某个时刻）。然而，就像目前为止描述的，Raft可以一个命令执行多次：例如，如果leader在提交日志条目之后，响应客户端之前崩溃，客户端将会与新的leader重试这个命令，导致它被执行两次。解决的办法是让客户端为每个命令分配一个独特的序列号。然后，状态机会追踪为每一个客户端最后处理处理过的序列号，以及对应的响应。如果它收到一个命令，这个命令的序列号已经被执行过了，它会立刻响应而不是重新执行请求。

​ 只读操作可以被处理，而不用向日志中写入任何东西。然而，如果没有额外的措施，将会存在返回陈旧数据的风险，因为响应这个请求的leader可能已经被一个新的leader取代，而这件事可能并未被察觉到。线性化读取必须不能返回过时的数据，Raft需要两种额外的预防措施来保证在不使用日志的情况下做到这一点。第一，领导者必须有最新的信息，知道哪些条目是已提交的。Leader Completeness原则保证leader拥有所有已经提交的条目，但是在它任期开始的时候，它可能不知道它可能不知道它们是哪些。为了弄清楚，它需要提交它任期的一个条目。Raft通过在任期开始的时候让每一个leader向日志中提交一个空白的no-op条目来处理这个问题。第二，在处理一个只读请求之前，leader必须检查它是否已经被罢免（它的信息可能过时，如果已经选出了更近期的leader）。Raft通过让leader在响应一个只读请求之前和集群中的大多数交换心跳消息来处理这个问题。或者，leader可以依靠心跳机制来提供一种租约形式，但这将会依赖于时间来保证安全性（它假设时钟偏差有限）。

Conclusion

​ 算法的设计通常以正确性，效率，以及简洁作为主要的目标。尽管这些都是很有价值的目标，但是我们相信可理解性同样重要。在开发者将这个算法应用于实际的实现之前，其它目标都是无法实现的，因为它们都会不可避免地偏离和扩展已经发布的形式。除非开发者对于算法有很深的理解并且创建了一种关于它的直觉，否则对于它们来说，在实现中保留它们渴望的属性是困难的。

​ 在这篇文章中，我们讨论了分布式共识问题，其中一个广泛接受但难以理解的算法，Paxos，多年以来一直困扰着学生和开发者。我们开发了一种新的算法，Raft，我们已经证明了它比Paxos更容易理解。我们也相信Raft也为系统构建提供了一个更好的基础。使用可理解性作为主要的设计目标这件事改变了我们设计Raft的方法；随着设计的进行，我们发现我们重复使用了一些技术，例如分解问题和简化状态空间。这些技术不仅提升了Raft的可理解性，也使我们更容易证明它的正确性。