Raft共识算法 – 世子之争，素来如此

中文翻译

寻找可理解的一致性算法（扩展版）

迭戈·昂加罗和约翰·奥斯特豪斯斯坦福大学

摘要

raft 是一种用于管理复制日志的共识算法。它产生的结果等同于（多）Paxos，而且效率与 Paxos 相同，但是它的结构不同于 Paxos；这让 raft 比 Paxos 更容易理解，并且为构建实际系统提供了更好的基础。为了提高可理解性，raft 将共识的关键元素（如选举、日志复制和安全性）分离开来，并强制执行更强的一致性以减少必须考虑的状态数。用户研究的结果表明，raft比 Paxos 更容易让学生学习。raft 还包括一个更改集群成员的新机制，该机制使用重叠多数来保证安全。

1. 简介

共识算法允许一组机器作为一个协调一致的群体运行，即使其中一些成员失败也能存活。正因为如此，它们在构建可靠的大型软件系统方面发挥着关键作用。近十年来，Paxos [15,16]主导了对共识算法的讨论：大多数实现基于Paxos或受其影响，而Paxos已成为教授学生理解共识的主要工具。不幸的是，尽管有很多使它更易于理解的努力，但 Paxos 仍然很难理解。此外，它的架构需要复杂的变化来支持实际系统。因此，系统构建者和学生都难以掌握 Paxos。在亲自体验了 Paxos 之后，我们开始寻找一个新共识算法，它可以为系统构建和教育提供更好的基础。我们的方法与众不同，因为我们的首要目标是可理解性：我们能否定义一种针对实际系统的共识算法，并以比 Paxos 更容易学习的方式描述它？此外，我们希望该算法能够促进对系统构建者来说至关重要的直觉的发展。算法不仅需要有效，而且必须清楚地说明为什么有效。这项工作的结果是一个名为raft的共识算法。在设计raft时，我们应用了特定的技术来提高可理解性，包括分解（raft将领导者选举、日志复制和安全性分开）和相对于Paxos，Raft减少了不确定性，并且服务器之间不一致的方式也更少。一项对两所大学的 43 名学生进行的研究表明，与Paxos相比，Raft更容易理解：在学习这两种算法后，这些学生中有 33 人能够更好地回答有关Raft的问题，而不是关于Paxos的问题。 Raft 在许多方面与现有的共识算法（尤其是 Okasaki 和 Liskov 的视图复制[29,22]）相似，但它有以下几个新颖的特点： • 强势领导者：Raft使用比其他共识算法更强大的领导形式。例如，日志条目只从领导者流向其他服务器。这简化了复制日志的管理，并使 Raft 更容易理解。 • 领导者选举：Raft 使用随机时间戳来选举领导者。这仅仅增加了少量的机制，用于已有的任何共识算法所需的心跳，同时以简单且迅速的方式解决冲突。 • 成员关系变更：Raft 提供了一种新的联合一致性方法来改变集群中的服务器集，该方法在转换过程中使两个不同配置的多数重叠。这使得集群能够在配置更改期间继续正常运行。我们相信，Raft 优于 Paxos 和其他共识算法，无论是用于教育目的还是作为实现的基础。它比其他算法更简单、更容易理解；它的描述足够详细，可以满足实际系统的需求；已经有几个开源实现，并被几家公司使用；其安全性得到了正式定义并得到证明；其效率与其他算法相当。本文接下来的部分会介绍复制状态机问题（第 2 节），讨论 Paxos 的优缺点（第 3 节），描述我们理解 Raft 协议的一般方法（第 4 节），展示 Raft 算法（第 5~8 节），评估 Raft（第 9 节）并讨论相关工作（第 10 节）。

2. 复制状态机

共识算法通常在复制状态机的上下文中出现。[37]在这种方法中，一组服务器上的状态机计算出相同状态的副本，并且可以在某些服务器宕机的情况下继续运行。复制状态机是

用于解决分布式系统中的各种容错问题。例如，拥有单个集群领导者的大型系统（如GFS[8]、HDFS[38]和RAMCloud[33]）通常使用单独的复制状态机来管理领导者选举并存储必须在领导者崩溃时存活下来的配置信息。复制状态机的例子包括Chubby[2]和ZooKeeper[11]。复制状态机通常使用复制日志来实现，如图 1 所示。每个服务器都存储一个包含一系列命令的日志，这些命令按顺序由其状态机执行。每条日志中的命令以相同的顺序包含相同的命令，因此每个状态机都会处理相同的一系列命令。由于状态机是确定性的，所以每个状态机都会计算出相同的状态和输出序列。保持复制日志的一致性是共识算法的工作。服务器上的共识模块接收来自客户端的命令，并将其添加到其日志中。它与其它服务器上的共识模块进行通信，以确保每个日志最终包含相同顺序的请求，即使某些服务器失败也是如此。一旦命令正确复制，每个服务器的状态机按日志顺序处理它们，然后将输出返回给客户端。因此，服务器似乎形成一个单一的、高度可靠的状态机。实用系统的共识算法通常具有以下特性： • 他们保证在所有非拜占庭条件下安全（永远不会返回错误的结果），包括网络延迟、分区、包丢失、复制和重新排序。 • 只要大多数服务器能够正常工作并相互通信，它们就能完全发挥作用。因此，一个典型的由五台服务器组成的集群可以容忍两台服务器故障。假设服务器会因为停止而失败；随后可以从稳定的存储空间中恢复并重新加入群集。 • 他们不依赖时间来确保一致性日志记录的内容：故障时钟和极端消息延迟可能导致可用性问题。 • 在一般情况下，一个命令只要集群中的大多数节点响应了单轮远程过程调用就可完成；少量慢服务器不会影响整体系统性能。

3. Paxos有什么问题？

在过去的十年里，Leslie Lamport 的 Paxos 协议 [15] 已经几乎成为共识的代名词：它是课程中最常教授的协议，大多数共识实现都以它为基础。Paxos 首先定义了一个能够就单一决策达成一致的协议，例如一个单一复制日志条目。我们称这个子集为单命令 Paxos。然后，Paxos 将多个这样的协议组合在一起，以便进行一系列决策，如多 Paxis。Paxos 确保了安全性和活性，并支持集群成员资格的变化。它的正确性得到了证明，在正常情况下也是高效的。不幸的是，Paxos有两个显著的缺点。第一个缺点是Paxos 非常难以理解。完整的解释[15]臭名昭著地晦涩难懂；很少有人能成功理解它，而且需要付出很大的努力。因此，人们尝试用更简单的术语来解释 Paxos [16, 20, 21]。这些解释侧重于单个决定子集，但仍然具有挑战性。在对 2012 年 NSDI 与会者的非正式调查中，我们发现即使是在经验丰富的研究人员中，也很少有人对 Paxos 感到舒服。我们自己也一直在努力解决 Paxos 的问题；我们在阅读了几个简化版本的解释并设计了自己的替代协议之后才最终理解了整个协议，这一过程几乎花费了一年的时间。我们假设 Paxos 的不透明性来自于它选择单命令子集作为其基础。单命令 Paxos 密集而微妙：它分为两个阶段，这两个阶段没有简单的直觉解释，也不能独立理解。因此很难对为什么单命令协议有效产生直观的理解。多 Paxos 的组合规则增加了显著的复杂性和微妙性。我们认为整体问题——就多个决策达成共识（即日志而不是单个条目）可以以更直接、明显的方式分解。 Paxos 的第二个问题是它没有为构建实际实现提供良好的基础。一个原因是多Paxos 没有被广泛接受的算法。Lamport 的描述主要是关于单级Paxos；他勾勒了可能的方法来处理多级Paxos，但许多细节缺失。已经有几次尝试扩展和优化 Paxos，如 [26]、[39] 和 [13]，但是这些都不同从彼此和Lamport的草图中。Chubby [4] 等系统实现了类似 Paxos 的算法，但在大多数情况下尚未公开其细节。此外，Paxos 架构对于构建实用系统来说是一种糟糕的方式；这是单一命令分解的另一个后果。例如，独立选择一组日志条目并将它们合并为一个顺序日志几乎没有好处；这只会增加复杂性。围绕着一个日志设计一个系统要简单得多，有效地在受约束的顺序中按顺序追加新的条目。另一个问题是 Paxos 在核心使用了对称的点对点方法（尽管它最终建议了一种软化的领导形式作为性能优化）。在一个只做唯一决策的简化世界里，这种方法是有意义的，但很少有实际系统使用这种方法。如果必须做出一系列决定，那么首先选举出领导者，然后让领导者协调决定会更简单、更快捷。因此，实际系统与Paxos相差甚远。每个实现都从Paxos开始，发现实施它的困难，然后开发出一个大不相同的架构。这既费时又容易出错，理解Paxos的困难使问题更加严重。Paxos的公式可能对于证明其正确性是有用的，但实际情况与Paxos有很大的不同，证明几乎没有什么价值。Chubby 实现者的以下评论具有代表性： Paxos 算法的描述与现实世界系统的需求之间存在重大差距……最终的系统将基于未经验证的协议。[4] 由于这些问题，我们得出结论认为，Paxos 既不适合系统构建也不适合教育。鉴于共识在大规模软件系统中的重要性，我们决定研究能否设计出比 Paxos 更好的替代算法。Raft 就是这个实验的结果。

4 设计易理解性

在设计 raft 时，我们有好几个目标：它必须为系统构建提供一个完整且实用的基础，这样可以显著减少对开发人员的设计工作量；它必须在所有情况下都是安全的，并且在典型操作条件下可用；它必须对常见操作有效。但最重要的目标——也是最困难的挑战——是可理解性。算法必须能够让广大受众轻松理解。此外，还必须能够发展出对算法的直觉，这样系统构建者才能在现实世界中做出不可避免的扩展。在 Raft 的设计中，有许多需要我们在不同的方法之间进行选择的地方。在这种情况下，我们根据可理解性对备选方案进行了评估：解释每个替代方案有多难（例如，它的状态空间有多复杂？它是否隐含着微妙的意义?）以及读者完全理解该方法及其含义会有多容易？我们认识到这种分析具有高度主观性；尽管如此，我们还是使用了两种普遍适用的技术。第一种技术是众所周知的问题分解方法：只要可能，我们就把问题分成可以相对独立地解决、解释和理解的部分。例如，在 Raft 中，我们分离出了领导者选举、日志复制、安全性以及成员更改。我们的第二种方法是通过减少需要考虑的状态数量来简化状态空间，从而使系统更加连贯，并在可能的情况下消除不确定性。具体来说，日志不允许有空洞，raft 限制了日志之间可能出现不一致的方式。尽管在大多数情况下，我们试图消除不确定性，但在某些情况下，不确定性实际上确实提高了可理解性。特别是，随机化方法引入了不确定性，但它们倾向于通过以相似的方式处理所有可能的选择（“选择任何；这并不重要”）来减少状态空间。我们使用随机化来简化 raft 领导者选举算法。

5. Raft 共识算法

raft 是一种用于管理复制品日志的形式，如第 2 节所述。图 2 概述了算法的简明形式以供参考，图 3 列出了该算法的关键属性；本节其余部分按顺序讨论这些图中的元素。 raft 通过首先选举一个特出的领袖，然后赋予领袖对复制日志的完全管理职责来实现共识。领袖接受来自客户端的日志条目，在其他服务器上进行复制，并在应用到它们的状态机时告诉服务器何时是安全的。有一个领袖可以简化复制日志的管理。例如，领袖可以在不咨询其他服务器的情况下决定在哪里为日志添加新条目，数据从领袖流向其他服务器。领袖可能会失败或与其它服务器断开连接，在这种情况下会重新选择一个新的领袖。鉴于领导者的方法，raft 将共识问题分解为三个相对独立的子问题，接下来的子部分讨论了这些问题： • 领导选举：当现任领导人失败时，必须选择新的领导人（第5.2节）。 • 日志复制：领导者必须接受日志条目 AppendEntries RPC

服务器规则

图 2：Raft 共识算法的简要总结（不包括成员更改和日志压缩）。上左角框中服务器的行为被描述为一组独立重复触发的规则。例如，§5.2 中的编号指示了特定功能的讨论位置。形式化规格说明 [31] 更精确地描述了该算法。选举安全：在一个任期内最多只能选出一位领导人。第5.2条只写式领导者：领导者永远不会重写或删除其日志中的条目；它只会添加新的条目。第 5.3 节日志匹配：如果两个日志包含具有相同索引和术语的条目，则这些日志在给定索引之前的所有条目中都是相同的。§ 5.3 领导者完整性：如果在给定术语中提交了日志条目，则该条目将在所有高编号术语的日志中出现。§ 5.4 状态机安全：如果一个服务器在给定索引处对其状态机应用了日志条目，则其他任何服务器都不应为其应用不同的日志条目。§ 5.4.3 图3：Raft 确保这些属性在任何时候都是正确的。各部分编号表示每个属性的讨论位置。从客户端复制它们到整个集群，强制其他日志与自己的相匹配（第5.3节）。 • 安全性：Raft 的关键安全属性是图 3 中的状态机安全性属性：如果任何服务器已将其应用于状态机，则其他服务器不得为同一日志索引应用不同的命令。第 5.4 节描述了 Raft 如何保证此属性；解决方案涉及对第 5.2 节中描述的选举机制施加额外限制。在介绍一致性算法之后，这一部分讨论了可用性问题以及系统中时间的作用。

5.1 raft 基础知识

一个 raft 集群包含多个服务器；五个是最常见的数量，使得系统能够容忍两个故障。在任何时候，每个服务器都处于三种状态之一：领导者、追随者或候选人。在正常运行时，恰好有一个领导者，其他所有服务器都是追随者。追随者是被动的：它们不会自行发出请求，而是只响应来自领导者和候选人的请求。领导者处理所有客户端请求（如果客户端连接到追随者，则由追随者将其重定向到领导者）。第三个状态“候选人”用于选举新的领导者，如第 5.2 节所述。图 4 显示了状态及其转换；下面讨论这些转换。 raft 将时间划分为任意长度的术语，如图 5 所示。术语按连续整数编号。每个术语都以选举开始，在第 5.2 节中描述了其中一个或多个候选人试图成为领导者的过程。如果一个候选人在选举中获胜，则在该术语其余时间内担任领导。在某些情况下，选举会导致投票分歧。在这种情况下，该术语将在没有领袖的情况下结束；一个新的术语（以及新的选举）将开始。

稍后开始。Raft 确保在给定术语中最多有一个领导者。不同的服务器可能会在不同的时间观察到任期之间的过渡，而在某些情况下，服务器甚至可能不会观察到选举或整个任期。任期在Raft中充当逻辑时钟，它们允许服务器检测过时的信息，例如过时的领导者。每个服务器存储一个当前任期编号，随着时间单调递增。每当服务器进行通信时，都会交换当前任期。如果一个服务器的当前任期比另一个小，则会将其更新为较大的值。如果候选人或领导者发现其任期已过期，则会立即将其状态重置为 follower 。如果服务器收到带有过时任期号的请求，则会拒绝该请求。 raft服务器通过远程过程调用(RPC)进行通信，而基本共识算法只需要两种类型的RPC。在选举期间（第5.2节），候选者会发起 RequestVote RPC 调用，领导者会发起 Append-Entries RPC 调用来复制日志条目并提供心跳信号（第5.3节）。第7节添加了一个用于在服务器之间传输快照的第三个RPC。如果服务器没有及时收到响应，它们会重试RPC，并为最佳性能并发发出RPC。

5.2 领导选举

raft 使用心跳机制来触发 leader 选举。服务器启动时，会从跟随者状态开始。只要服务器接收到有效的来自领袖或候任者的 RPC。为了维护他们的权威，领袖会定期向所有追随者发送心跳（不包含日志条目的 AppendEntries RPC）。如果跟随者在选举超时(一段时间内没有收到任何通信）后开始认为没有有效的领导者，那么它就会发起选举以选择新的领导者。选举开始时，一个跟随者会增加它的当前任期，并转换为候选状态。然后它为自己投票，并向集群中的每个服务器并行发出 RequestVote 请求。候选人在这种状态下继续下去，直到发生三种情况之一：(a) 它赢得了选举，(b) 另一台服务器宣布自己为主机，或者 (c) 一段时间过去了但没有赢家。这些结果将在下面的段落中分别讨论。候选者在完整集群中获得多数服务器的支持时，就赢得了选举。每个服务器在一个给定任期中最多只投一票（注意：第 5.4 节为投票增加了额外限制）。多数表决确保了某个任期中至多一个候选者能够赢得选举（图 3 中的选举安全性）。候选人一旦赢得选举，就会成为领导者。然后它会向所有其他服务器发送心跳消息以建立权威并防止新的选举。在等待投票时，候选者可能会收到另一个声称是领导者服务器的 AppendEntries RPC。如果领导者任期（包含在它的RPC中）至少与候选者的当前任期一样大，则候选人将承认该领导者为合法，并返回跟随状态。如果 RPC 中的任期小于候选者的当前任期，则候选人会拒绝该 RPC 并继续处于候选状态。第三种可能的结果是候选人既没有赢得选举也没有输掉选举：如果许多追随者同时成为候选人，选票可能会分散，使任何候选人都无法获得多数票。当这种情况发生时，每个候选人都会超时并开始新一轮选举，通过增加任期并发起另一轮 RequestVote RPC。然而，如果没有额外措施来分割选票，它们可能会无限重复。 raft 使用随机选举超时来确保分裂投票的发生频率较低，并且能够快速解决。为了防止发生分裂投票，选举超时从一个固定的间隔（例如，150-300毫秒）中随机选择。这使得服务器分散开来，因此在大多数情况下只有一个服务器会过期；它赢得选举并在其他任何服务器过期之前发送心跳。使用相同的机制处理分裂投票。每个候选人在选举开始时重新启动其随机选举超时，并等待该超时过去才开始下一次选举；这降低了新选举中再次发生分裂投票的可能性。第9.3节显示这种方法可以迅速选出领导者。选举是理解性指导我们从设计选择中进行选择的一个例子。最初，我们计划使用排名系统：每个候选人分配一个独特的排名，该排名用于在竞争者之间进行选择。如果一个候选人发现另一个候选人的排名更高，它会返回跟随状态，以便于排名更高的候选人更容易赢得下一次选举。我们发现这种方法会在可用性方面引起微妙的问题（当排名较高的服务器失败时，排名较低的服务器可能需要超时并再次成为候选人，但如果过早这样做，则可能会重置选举领导者的进度）。我们对算法进行了多次调整，但每次调整后都会出现新的特殊情况。最终，我们认为随机重试方法更直观、更容易理解。

5.3 日志复制

一旦选举出领导者，它就开始为客户端请求提供服务。每个客户端请求都包含一个要由复制状态机执行的操作。领导者将其作为日志中的新条目附加，并并发地向其他服务器发出 AppendEntries RPC 以复制该条目。当条目安全复制（如上所述）后，领导者会将其应用于其状态机并返回给用户执行结果。如果跟随者崩溃或运行缓慢，或者网络包丢失，那么领导者将无限期地重试 AppendEntries RPC （即使已经响应了客户端），直到所有跟随者最终存储所有日志条目为止。日志以图 6 所示的方式进行组织。每个日志条目都存储了一个状态机命令，以及该条目被领导接收时的日志项号。在日志条目中的日志项号用于检测不一致，并确保图 3 中的一些性质。每个日志条目还有一个整数索引标识符，即在日志中标识位置。领导者决定何时将日志条目应用到状态机；这样的条目称为提交。Raft保证提交的日志条目持久且最终会被所有可用的状态机执行。一旦创建条目的领导者在多数服务器上复制了该条目（例如，图 6 中的条目 7），就会提交一个日志条目。这也会提交领导者事务日志中的所有前驱条目，包括由之前的领导者创建的条目。第 5.4 节讨论在领导者更改后应用此规则的一些细微之处，并证明这个提交定义是安全的。领导者会跟踪它知道的已提交的最高索引，并将其包含在未来的 AppendEntries RPC（包括心跳消息）中以便其他服务器最终得知。一旦从跟随者学习到日志条目已提交，它就在本地状态机（按日志顺序）中应用该条目。我们设计了raft日志机制来维护不同服务器上的日志之间的高一致性。这不仅简化了系统的操作并使其更具可预测性，而且它是确保安全的重要组成部分。Raft维护以下属性，这些属性共同构成了图3中的Log Matching Property： • 如果两个不同日志中的条目具有相同的索引和术语，则它们存储相同的操作。 • 如果两个不同日志中的条目具有相同的索引和术语，则这些日志在所有先前的条目中都是相同的。第一个性质源于领导者在一个术语中最多只创建一个具有给定日志索引的条目，而日志条目永远不会改变它们在日志中的位置。第二个性质是由 AppendEntries 执行的一个简单的一致性检查确保的。当发送 AppendEntries 请求时，领导者会包括其日志中紧接新条目前面的条目的索引和术语。如果追随者在其日志中找不到具有相同索引和术语的条目，则它拒绝新条目。一致性检查充当归纳步骤：初始的日志为空状态满足日志匹配属性，并且无论何时扩展日志，一致性检查都会保留该属性。因此，只要 AppendEntries 成功返回，领导者就知道追随者的日志与自己的日志一致，直到新的条目为止。在正常运行时，领导者和追随者的日志保持一致，因此 AppendEntries 的一致性检查永远不会失败。然而，领导者崩溃可能会导致日志不一致（旧的领导者可能没有完全复制其日志中的所有条目）。这些不一致可能会在一系列的领导者和追随者的崩溃中不断累积。图 7 描述了追随者日志与新领导者的日志如何不同。一个追随者可以图7：当顶层领导者上台时，追随者日志中可能会发生任何一种情况（a-f）。每个方框代表一个日志条目；方框中的数字表示任期。追随者可能缺少条目（a-b），可能有额外未提交的条目（c-d），或者两者兼而有之（e-f）。例如，如果该服务器在任期 2 下是领导者，向其日志添加了几个条目，然后在提交其中任何一个之前崩溃；它很快重新启动并成为任期 3 的领导者，并向其日志添加了一些额外的条目；在任何任期 2 或任期 3 条目都提交之前，服务器再次崩溃并保持关闭状态好几次任期。它可能缺少领导者上的条目，也可能包含领导者上没有的额外条目，或者两者都有。日志中的缺失或多余条目可能会跨越多个任期。在 Raft 中，领导者通过强制从者日志复制自身来处理不一致。这意味着从者日志中的冲突条目将被覆盖为来自领导者日志的条目。第 5.4 节会说明，当与另一个限制条件结合使用时，这是安全的。为了使追随者的日志与自己的保持一致，领导者必须找到两个日志都同意的最新日志条目，然后删除追随者日志中该点之后的所有条目，并向追随者发送该点之后的所有领导者的条目。所有这些操作都是对 AppendEntries RPC 执行的一致性检查的响应。领袖维护每个追随者的 nextIndex，即领袖将要发送给该追随者的下一个日志条目的索引。当领导者第一次上任时，它会将所有 nextIndex 值初始化为其日志中的最后一个条目前的一个索引（图 7 中的 11）。如果追随者的日志与领导者的不一致，则 AppendEntries 一致性检查将在下一条 AppendEntries RPC 中失败。在拒绝后，领导者会递减 nextIndex 并重试 AppendEntries RPC。最终，nextIndex 将达到一个领导者和追随者日志匹配的位置。这发生时，AppendEntries 将成功，这将消除任何冲突的追随者日志条目并附加来自领导者日志的条目（如果有的话）。一旦 AppendEntries 成功完成，追随者的日志就会与其领导者相同，并且在本任期其余时间里也会保持这种状态。如果需要，可以优化协议以减少拒绝 AppendEntries RPC 的数量。例如，在拒绝 AppendEntries 请求时，追随者可以包括冲突项的期限以及它为该术语存储的第一个索引。有了这些信息，领导者就可以通过减小子项的nextIndex来跳过所有与该术语相关的冲突条目；每个具有冲突条目的术语需要一个 AppendEntries RPC 而不是每个条目一个 RPC。在实践中，我们怀疑这种优化是必要的，因为失败很少发生，并且不太可能有大量不一致的条目。通过这个机制，当一个领导者失去权力时，它不需要采取任何特殊的措施来恢复日志一致性。它只需开始正常运行，并且在追加条目一致检查失败的情况下，日志会自动收敛。领导者永远不会覆盖或删除其自身的日志（图 3 中的 Leader Append-Only 属性）。这种日志复制机制体现了第 2 节中描述的理想一致性属性：Raft 只要大多数服务器处于活动状态，就可以接受、复制并应用新的日志条目；在正常情况下，可以使用单个远程过程调用 (RPC) 将新条目复制到集群中的大多数节点；一个缓慢的追随者不会影响性能。

5.4 安全性

前面几节描述了 Raft 如何选举 leader 和复制日志条目。然而，到目前为止所描述的机制并不足以确保每个状态机以完全相同的方式执行相同的命令顺序。例如，在 leader 提交多个日志条目时，一个后进者可能无法访问，然后它可能会被选为 leader 并用新的条目覆盖这些条目；因此，不同的状态机可能会执行不同的命令序列。这一部分通过限制哪些服务器可以被选为领导者来完成 Raft 算法。这种限制确保了对于任何给定任期，该任期的领导者包含了所有先前任期中提交的所有条目（参见图 3 中的“领导者完备性”）。考虑到选举限制，我们进一步明确了提交规则。最后，我们给出了一个关于领导者完备性的证明概述，并展示了它如何导致复制状态机的正确行为。

5.4.1 禁选限制

在任何基于领导者的共识算法中，领导者最终必须存储所有已提交的日志条目。在某些共识算法中，例如带视图的时间复制 [22]，即使最初不包含所有已提交的条目，也可以选择领导者。这些算法包含额外的机制来识别缺失的条目，并在选举过程中或稍后将其传输到新的领导者。不幸的是，这会导致相当大的附加机制和复杂性。 Raft 使用一种更简单的方法，在这种方法中，它保证来自先前的图8：展示为什么一个领导者不能使用来自旧术语的日志条目来确定承诺。 (a)中，S1 是领导者，并部分复制了索引为 2 的日志条目。在 (b) 中，S1 崩溃；S5 在来自 S3、S4 和自身的投票中被选为第 3 轮的领导者，并接受了一个不同的条目，该条目的索引为 2。在 (c) 中，S5 崩溃；S1 重启并当选为领导者，并继续复制。此时，来自第 2 轮的条目已在大多数服务器上复制，但尚未提交。如果 S1 崩溃如 (d)，则 S5 可能会被选举为领导者（通过来自 S2、S3 和 S4 的投票），并用它自己的来自第 3 轮的条目覆盖该条目。但是，如果 S1 在崩溃之前在大多数服务器上复制了来自其当前轮次的条目，如 (e) 所示，则该条目已提交（S5 无法赢得选举）。此时，所有之前的日志条目也都已提交。每个新当选的领导人自当选之日起就会出现这些条款，无需将这些条目转移到领导人。这意味着日志条目只流向一个方向，从领导者到追随者，领导者永远不会在他们的日志中覆盖现有的条目。 raft 使用投票过程来防止候选人在日志中不包含所有提交条目时赢得选举。候选人必须联系集群中的大多数节点才能当选，这意味着每个已提交的条目都至少出现在其中的一个服务器上。如果候选人的日志与该多数派中的任何其他日志一样新（“新”在此处定义为明确的），则它将包含所有提交的条目。 RequestVote RPC 实现了这个限制：RPC 包含有关候选者日志的信息，如果投票者的日志比候选者的更新，则投票者会拒绝其投票。 raft 通过比较日志中最后条目（ entry ）的索引和术语来确定两个日志哪个更接近最新。如果日志有不同术语的最后条目，那么术语较新的日志较新。如果日志以相同的术语结尾，则哪个日志较长哪个就更近最新。

5.4.2 将上一阶段的条目提交

如第 5.3 节所述，当一个 leader 确认其当前任期的一个条目已存储在大多数服务器上时，它就会知道该条目已被提交。如果 leader 在提交一个条目前发生故障，那么未来的 leader 将尝试完成对该条目的复制。但是，一旦大多数服务器上都有了来自先前任期的一条记录，leader 不会立即得出结论认为该条目已被提交。图图9：如果S1（任期T的领导者）提交了任期T的新日志条目，而S5在以后的任期U中被选为领导者，则必须至少有一个服务器（S3）接受该日志条目并投票给S5。图 8 描述了这样一种情况，即旧的日志条目存储在大多数服务器上，但仍然可以被未来的领导者覆盖。为了消除图8中所示的问题，Raft 不会通过计数复制因子来提交前一个任期的日志条目。只有来自当前任期领导者日志条目的提交才通过计数复制因子进行；一旦当前术语中的条目以这种方式提交，则由于日志匹配属性，所有以前的条目都会间接提交。在某些情况下，可以安全地断定较旧的日志条目已被提交（例如，如果该条目存储在每个服务器上），但是出于简单起见，Raft 采取了更加保守的方法。 raft 通过承诺规则增加了这种复杂性，因为当领导者复制来自先前任期的日志条目时，日志条目保留其原始任期编号。在其他共识算法中，如果新的领导者重新复制来自以前“任期”的条目，则必须使用它的新“任期编号”来完成。 raft 的方法使推理日志条目更容易，因为它们会随着时间的推移以及跨越日志保持相同的任期编号。此外，在 raft 中，新的领导者比其他算法发送更少的来自前一个任期的日志条目（其他算法需要在提交之前发送冗余的日志条目以重命名）。

5.4.3 安全性论证

有了完整的Raft算法，我们现在可以更准确地论证领导者完备性属性成立（该论证基于安全证明；请参阅第9.2节）。我们假设领导者完备性属性不成立，然后证明一个矛盾。假设任期为termT的领导者（leaderT）提交了任期为termT的日志条目，但该日志条目未被未来任期的领导者（leaderU）存储。考虑任期最小的任期U> T，其中leaderU不存储该条目。

在其选举时，已提交的条目必须不存在于leaderU的日志中（领导者永远不会删除或覆盖条目）。
领导者T在集群中的大多数节点上复制了条目，而领导者U从集群中大多数节点收到了投票。因此，至少一个服务器（即，“选民”）既接受了来自领导者T的条目，又对图9中展示了 leaderU。选民是实现矛盾的关键。
投票者必须在投票给 leaderU 之前，已经接受 leaderT 的提交条目；否则它会拒绝 leaderT 的 AppendEntries 请求（它的当前术语将会高于 T）。
由于每个参与的领导者（根据假设）都包含该条目，因此投票者在投票给领导人 U 时仍然存储该条目。领导者永远不会删除条目，而追随者只有在与领导者冲突时才会删除条目。
投票者将其投票权授予了领袖 U，因此领袖 U 的日志必须与投票者的日志一样是最新的。这导致了两个矛盾中的一个。
首先，如果投票者和领导者 U 共享相同的最后一个日志条目，那么领导者 U 的日志必须至少与投票者的日志一样长，因此它包含了投票者日志中的每一项。这是矛盾的，因为投票者包含了一个承诺条目，而假定领导者 U 没有。
否则，leaderU 的最后一个日志项必须大于投票者的。此外，它也必须大于T，因为投票者最后的日志项至少为T（包含从任期T开始提交的条目）。创建leaderU 最后一个日志项的早期 leader 必须在其日志中包含提交的条目（假设）。然后，根据日志匹配性质，leaderU 的日志也必须包含提交的条目，这与前面得出的结论相矛盾。
这就完成了矛盾。因此，所有大于T的术语的领导必须包含在术语T中承诺的所有术语T中的条目。
日志匹配属性保证未来的 leader 也会包含间接提交的日志条目，比如图 8 (d) 中的索引 2。有了领导者完整性属性，我们可以从图 3 中证明状态机安全性属性，该属性指出，如果服务器应用于给定索引的状态机日志条目，则不会有任何其他服务器为该相同索引应用不同的日志条目。当服务器将其日志条目应用于其状态机时，它的日志必须与领导者在该条目前的日志完全一致，并且该条目必须被提交。现在考虑任何服务器应用于给定日志索引的最低术语；日志完备性保证所有更高术语的领导者都将存储相同的日志条目，因此以后应用于该指数的服务器将应用相同值。因此，状态机安全性属性成立。最后，Raft 要求服务器按日志索引顺序应用条目。结合状态机安全属性，这意味着所有服务器将以相同的顺序向其状态机应用完全相同的一组日志条目。

5.5 跟踪者和候选者的碰撞

到目前为止，我们关注的是领导者失败。跟随者或候选人的崩溃比领导者的崩溃要简单得多，它们由相同的过程处理。如果一个跟随者或候选人崩溃了，以后发送给它的 RequestVote 和 AppendEntries 请求都将失败。 raft 通过无限重试来处理这些故障；如果发生崩溃的服务器重新启动，则该请求将成功完成。如果在响应之前，服务器在完成 RPC 后崩溃，则在重新启动后，它将再次收到相同的 RPC。 raft RPC 是幂等的，因此不会造成任何伤害。例如，如果一个追随者接收到一个包含日志条目的 AppendEntries 请求，这些条目已经在它的日志中，那么它会忽略新请求中的这些条目。

5.6 时间安排和可用性

我们对 Raft 的要求之一是，安全性不能依赖于时间：系统不能仅仅因为某些事件发生得比预期更快或更慢就产生不正确的结果。然而，可用性（系统及时响应客户端的能力）必然取决于时间。例如，如果消息交换的时间超过服务器崩溃之间的典型时间，候选人将无法坚持足够长的时间来赢得选举；如果没有稳定的领导者，Raft 将无法取得进展。 Raft 中最重要的时间点就是 leader 选举。只要系统满足以下的时间要求，Raft 就能够选举并维护一个稳定的 leader：

广播时间 < 选举超时 < 失败平均时间间隔

在不等式中，broadcastTime 是服务器向集群中的每个服务器并行发送远程过程调用 (RPC) 并接收响应所需的平均时间；electionTimeout 是第 5.2 节中描述的选举超时；MTBF 是单个服务器之间发生故障的平均时间。广播时间应小于选举超时几个数量级，以便领导者可以可靠地发送心跳消息，防止追随者启动选举；考虑到用于选举超时的随机方法，该不等式也使拆分投票不太可能。选举超时应比 MTBF 小几个数量级，以便系统可以稳定地取得进展。当领导者崩溃时，系统将在大约选举超时的时间内无法访问；我们希望这仅占总时间的一小部分。广播时间和平均无故障时间是底层系统属性，而选举超时是我们必须选择的。 Raft 的远程过程调用 (RPC) 通常要求接收者将信息持久化到稳定存储中，因此广播时间可能在 0.5 毫秒到 20 毫秒之间，具体取决于存储技术。因此，选举超时可能会在 10 毫秒到 500 毫秒之间。典型地

服务器的平均无故障时间是几个月甚至更长，很容易满足时间要求。

6. 聚类成员变化

到目前为止，我们一直假设集群配置（参与共识算法的服务器集合）是固定的。在实践中，偶尔需要更改配置，例如在服务器故障时替换服务器或更改副本数。虽然可以通过将整个群集下线、更新配置文件，然后重新启动群集来完成此操作，但这将使群集在转换期间不可用。此外，如果涉及任何手动步骤，则可能会出现操作员错误的风险。为了避免这些问题，我们决定自动进行配置更改，并将其纳入raft共识算法中。为了使配置更改机制安全，必须确保在转换过程中不可能同时选举出两个任期相同的领导人。不幸的是，任何直接从旧配置切换到新配置的方法都是不安全的。不能原子地同时切换所有服务器，因此在转换期间集群可能会分裂为两个独立的主要多数派（参见图 10）。为了保证安全性，配置更改必须使用两阶段方法。实现这两个阶段有多种方式。例如，一些系统（如[22]）使用第一阶段来禁用旧配置，使其无法处理客户端请求；然后在第二阶段启用新配置。在 Raft 中，集群首先切换到一个称为联合共识的过渡配置；一旦联合共识被提交，系统就会转换为新的配置。联合共识结合了旧的和新的配置： • 两种配置中的日志条目都会复制到所有服务器。

• 两种配置中的任一服务器都可以作为领导者。 • 选举协议（以及进入承诺）需要来自旧配置和新配置的单独多数票。联合共识允许服务器在不牺牲安全性的前提下，在不同的时间转换配置。此外，联合共识还允许群集在整个配置更改期间继续为客户端请求提供服务。集群配置存储在复制日志中的特殊条目中，并通过它们进行通信；图 11 中展示了配置更改流程。当领导者收到一个从 Cold 到 Cnew 的配置更改请求时，它会将联合一致性协议 (Cold, new 在图中表示为 Cold, new) 的配置存储为日志条目并使用之前描述的机制来复制该条目。一旦某个服务器将其新的配置条目添加到其日志中，它就会一直使用该配置（无论条目是否提交）来进行后续决策。（服务器总是使用其日志中的最新配置，不管条目是否已提交）。这意味着，领导者将根据 Cold, new 条目是否已提交来决定何时应用 Cold, new 规则。如果领导者崩溃了，可能会根据获胜者是否收到了 Cold, new 来选择一个新的领导者。无论如何，在此期间，Cnew 都不能单方面做出决定。一旦Cold和Cnew都被提交，Cold和Cnew都不能在未经对方批准的情况下做出决定，并且领导者完整性属性确保只有带有Cold或Cnew日志条目的服务器才能被选为领导者。现在，领导者可以安全地创建一个描述Cnew的日志条目并将其复制到群集中。再次强调，只要看到这个配置，它就会立即生效。当根据Cnew的规则提交新配置时，旧配置不再相关，不在新配置中的服务器可以关闭。如图 11 所示，在任何时候，Cold 和 Cnew 都不能单独做出决定；这保证了安全性。重新配置还有三个问题需要解决。第一个问题是，新的服务器可能最初不存储任何日志条目。如果它们在这种状态下被添加到群集中，那么它们可能需要相当长的时间才能跟上进度，在此期间可能无法提交新的日志条目。为了防止可用性中断，raft 引入了一个在配置更改之前的额外阶段，在这个阶段中，新服务器以非投票成员的身份加入集群（领导者将日志条目复制给它们，但不会考虑它们是否为多数）。当新服务器追上了群集中的其他节点后，就可以按照上面描述的方式进行重新配置了。第二个问题是，集群领导者可能不会成为新配置的一部分。在这种情况下，一旦领导者提交了新的日志条目Cnew，它就会降级（返回跟随者状态）。这意味着在提交Cnew时（即，在它独立操作之前），有一段时间（它正在复制日志条目但不计入多数）领袖管理一个不包括自己的集群；它复制日志条目，但不计入多数。当Cnew被提交时会发生领导者转换，因为这是新配置可以独立运行的第一个时间点（始终可以从Cnew中选择领导者）。在此之前，只有来自Cold的服务器才能被选为领导者。第三个问题是，已删除的服务器（不在Cnew中的服务器）可能会破坏集群。这些服务器不会接收到心跳信息，所以它们会超时并开始新的选举。然后，它们会发送带有新任期编号的 RequestVote RPC请求，这会导致当前的领导者恢复为跟随者状态。最终会选出一个新的领导者，但是已删除的服务器又会超时，从而导致重复这个过程，造成可用性低下。为了防止这个问题，服务器在认为当前存在领导者时会忽略 RequestVote RPC。具体来说，如果服务器在从当前领导者那里听到最小选举超时时接收到一个 RequestVote RPC，则不会更新自己的任期或授予投票权。这不影响正常的选举，每个服务器在开始选举之前至少等待最小选举超时。但是，它有助于避免被移除的服务器导致的中断：如果领导者能够向其集群发送心跳，则不会因更大的任期数而被罢免。

7. 日志压缩

在正常运行期间，raft日志会增长以包含更多的客户端请求。但在实际系统中，日志不能无限制地增长。随着日志的增长，它占用的空间也会增加，并且重演所花费的时间也会增加。如果没有某种机制来丢弃已经积累的日志中的过时信息，这最终会导致可用性问题。快照是最简单的压缩方法。在快照中，整个当前系统状态被写入到一个稳定的存储中的快照，然后所有日志都 1 2 3 4 5 6 7 log 指数图12：服务器用一个快照（这里仅包含当前状态，即变量x和y）替换掉日志中已经提交的部分（索引为1到5）。这个快照的最后一个已包括的索引和术语用来定位该快照在前一条记录之前的日志中的位置。这一点被丢弃了。快照用于 Chubby 和 ZooKeeper，本节其余部分描述了在 Raft 中使用快照。增量式压缩方法，如日志清理[36] 和日志结构合并树[30,5] 也是可能的。它们一次只操作数据的一部分，因此随着时间的推移，它们会更均匀地分散压缩负载。首先选择一个包含大量已删除和覆盖的对象的数据区域，然后重新编写该区域中的活动对象，并释放该区域。这比快照需要更多的额外机制和复杂性，因为快照总是对整个数据集进行操作来简化问题。虽然日志清理需要修改raft，但状态机可以使用与快照相同的接口实现LSM树。图 12 展示了 Raft 中快照的基本思路。每个服务器独立地创建快照，只包含其日志中已提交的部分条目。大部分工作都由状态机将其当前状态写入快照来完成。Raft 还在快照中包含少量元数据：最后一个包含的索引是替换掉该快照的日志中的最后一条记录（即状态机应用的最后一条记录）的索引，最后一个包含的时间戳是该记录的时间戳。为了支持在快照之后的第一个日志条目的追加操作（AppendEntries），这些信息会被保留下来，因为第一个日志条目需要一个先前的日志索引和时间戳。为了实现集群成员变化（第 6 节所述），该快照还包括从最后一个包含的索引开始的日志中的最新配置。一旦服务器完成了对快照的写入，它可以删除所有其索引小于或等于最后一个包含索引的日志条目，以及任何更早的快照。尽管服务器通常独立地取快照，但领导者偶尔必须向落后于其的追随者发送快照。这发生在当领导者已经丢弃了它需要发送给追随者的下一个日志条目时。幸运的是，在正常操作中不太可能发生这种情况：一个能够跟上的追随者图13：InstallSnapshot RPC 的摘要。快照被分割为块以进行传输；这样跟随者可以在每个块中看到心跳，从而可以重置选举定时器。领导者已经具备了这个条目。然而，一个极其缓慢的追随者或新加入集群的服务器（第 6 部分）则不具备。让这样的追随者跟上进度的方法是，让领导者通过网络向它发送快照。领导者使用一种新的远程过程调用 (RPC) 称为 InstallSnapshot 将快照发送给落后太多的追随者；参见图 13。当一个追随者通过这个 RPC 接收到一个快照时，它必须决定如何处理自己的现有日志条目。通常情况下，快照会包含接收方的日志中不存在的新信息。在这种情况下，追随者会丢弃其整个日志；它都被快照所取代，并且可能有未提交的条目与快照冲突。如果相反，由于重传或错误，追随者接收到描述其日志前缀的快照，则受该快照影响的日志条目将被删除，但位于快照之后的条目仍然有效并需要保留。这种快照方法偏离了raft的强领导原则，因为追随者可以在不知道领导者的情况下进行快照。然而，我们认为这个分歧是有道理的。虽然拥有一个领导者有助于避免在达成共识时产生冲突的决定，但当进行快照时已经达成了共识，因此没有冲突的决定。数据仍然只从领导者流向现在，低阶用户可以重新组织他们的数据。我们考虑了另一种基于领导者的方案，其中只有领导者会创建快照，然后将其发送给每个追随者。然而，这有两个缺点。首先，向每个追随者发送快照会浪费网络带宽并降低快照过程的速度。每个追随者已经拥有生成自己快照所需的信息，而且对于服务器来说，从本地状态生成快照通常比通过网络传播和接收要便宜得多。其次，领导者的实现会更复杂。例如，领导者需要在复制新的日志条目到它们时并行地向追随者发送快照，以免阻塞新的客户端请求。影响快照性能的其他两个因素。首先，服务器必须决定何时进行快照。如果服务器频繁地创建快照，那么它会浪费磁盘带宽和能源；如果服务器很少创建快照，那么它的存储容量可能会耗尽，并且在重启时重放日志所需的时间也会增加。一个简单的策略是在日志达到固定大小（以字节为单位）时进行快照。如果这个大小被设置得显著大于预期的快照大小，那么快照所花费的磁盘带宽开销就会很小。第二个性能问题是写快照可能需要很长时间，我们不希望这会延迟正常操作。解决办法是使用写时复制技术，这样可以接受新的更新而不影响正在写的快照。例如，基于函数式数据结构构建的状态机自然地支持这一点。或者，可以使用操作系统对写时复制的支持（例如 Linux 中的 fork）来创建整个状态机在内存中的快照（我们的实现采用了这种方法）。

8. 客户互动

这一部分描述了客户端如何与 Raft 交互，包括客户端如何找到集群中的领导者以及 Raft 如何支持原子语义。这些问题适用于所有基于共识的系统，而 Raft 的解决方案与其他系统类似。 Raft 客户端将所有请求发送到领导者。当客户端启动时，它会连接到一个随机选择的服务器。如果客户端第一次选择的不是领导者，那么该服务器将会拒绝客户端的请求，并提供最近一次听到的领导者的信息（AppendEntries 请求包括领导者的网络地址）。如果领导者崩溃了，客户端请求将会超时；然后客户端会尝试连接到随机选择的服务器。我们对 Raft 的目标是实现可串行化的语义（每个操作似乎在调用到响应之间执行一次，仅执行一次）。然而，如前所述，Raft 可以多次执行命令：例如，如果领导者如果在提交日志条目但尚未响应客户端时崩溃，客户端将使用新的领导者重试该命令，导致它被第二次执行。解决方案是让客户端为每个命令分配唯一的序列号。然后，状态机跟踪每个客户端处理的最新序列号以及相关联的响应。如果它接收到一个已经执行过的序号的命令，它会立即将请求作为响应返回，而不重新执行该请求。只读操作可以处理，而不写入任何日志。但是，如果没有额外措施，这可能会导致返回过时的数据，因为响应请求的领导者可能已经被一个它不知道的新领导者所取代。线程安全的读取必须防止返回过时的数据，而Raft需要两个额外的预防措施来保证在不使用日志的情况下实现这一点。首先，领导者必须知道哪些条目已提交。领导者完整性属性保证了领导者拥有所有已提交的条目，但在其任期开始时，它可能还不知道这些条目是什么。为了找到这些条目，它需要从它的任期开始提交一条条目。Raft通过让每个领导者在其任期开始时向日志中提交一个空白的空操作来处理此问题。第二，领导者必须在处理只读请求之前检查它是否已被弹劾（如果最近选举出一个新的领导者，则其信息可能已过时）。Raft通过在响应只读请求之前让领导者与集群中的大多数进行心跳消息交换来处理此问题。或者，领导者可以依赖心跳机制提供一种租约[9]形式，但这依赖于时间安全性（它假设时钟偏移是受界的）。

9. 实施与评估

我们实现了Raft，作为存储RAMCloud [33] 配置信息并协助 RAMCloud 主节点故障转移的复制状态机的一部分。 Raft 实现包含大约 2000 行不包括测试、注释或空行的 C++ 代码。源代码可以自由获取[23] 。此外，根据本文的草稿，还有大约 25 个独立的第三方开源实现[34] ，处于 Raft 的不同开发阶段。各种公司也在部署基于 Raft 的系统[34] 。本节其余部分使用可理解性、正确性和性能三个标准来评估 raft。

9.1 可理解性

为了衡量Raft相对于Paxos的理解性，我们在斯坦福大学的高级操作系统课程中使用了高年级本科生和研究生，在加州大学伯克利分校的分布式计算课程中也进行了实验研究。我们录制了Raft 和 Paxos 的视频讲座，并制作了相应的测验。Raft 讲座涵盖了本文的内容，除了日志压缩；Paxos

讲座涵盖了足够的材料来创建一个等效的复制状态机，包括单级投票、多级投票、重新配置以及实践中需要的一些优化（如选举领导者）。测验测试了学生对算法的基本理解，并要求他们考虑特殊情况。每个学生观看一段视频，完成相应的测验，然后观看第二段视频并完成第二个测验。大约一半的学生先做Paxos部分，另一半先做Raft部分，以考虑到个体在性能上的差异和从第一部分研究中获得的经验。我们比较了参与者在每次测验中的得分，以确定参与者是否更好地理解了Raft。我们试图使 Paxos 和 Raft 的比较尽可能公平。实验以两种方式偏向 Paxos：43 名参与者中有 15 人报告称他们之前使用过 Paxos，Paxos 视频比 Raft 视频长 14%。如表 1 所述，我们已采取措施来缓解潜在的偏见来源。我们的所有材料都可供审查[28, 31]。平均而言，参与者在 Raft 测试中的得分为 Paxos 测试中得分的 4.9 分（满分为 60 分时，Raft 的平均得分为 25.7 分，Paxos 的平均得分为 20.8 分）；图 14 显示了他们的个人分数。配对 t 检验表明，在 95% 的置信度下，Raft 分数的真实分布比 Paxos 分数的真实分布至少高 2.5 分。我们还创建了一个线性回归模型，根据三个因素预测新学生的测验分数：他们参加了哪个测验、他们的先修课程经验以及

他们学习算法的顺序。模型预测选择测验会产生一个有利于Raft 的12.5 分差异。这比观察到的4.9 分要高得多，因为许多实际的学生有先验的Paxos 经验，这对Paxos 帮助很大，而对Raft的帮助较少。有趣的是，模型还预测已经通过了Paxos 测验的人在Raft 上得分会低6.3 分；虽然我们不知道为什么，但这似乎在统计上是显著的。我们还对测验后的参与者进行了调查，以了解他们认为哪种算法更容易实现或解释；结果如图 15 所示。绝大多数参与者表示raft 更容易实现和解释（每个问题的 33 个中的 41 个）。然而，这些自我报告的感受可能不如参与者的测验分数可靠，而且参与者可能会受到我们假设 raft 更易理解的知识的影响。有关 Raft 用户研究的详细讨论，请参阅 [31]。

9.2 正确性

我们为第 5 节中描述的一致性机制开发了一个形式化规范和安全证明。该形式化规范 [31] 使用 TLC 语言 [17] 完全精确地表达了图 2 中总结的信息。它大约有 400 行，用作证明的主题。它本身对于任何实现 Raft 的人都有用。我们使用 TLC 证明系统 [7] 机械地证明了日志完备性属性。然而，这个证明依赖于尚未经过机械验证的不变式（例如，我们没有证明规范类型的类型安全性）。此外，我们还编写了一个非正式的证明 [31]，其中包含了状态机安全性属性的完整内容（它只依赖于规范）并且与规范相对应。

表1：研究中可能对Paxos存在偏见的关注点、针对每个关注点采取的措施以及可用的其他材料。

相对精确（大约有3500字）。

9.3 性能

Raft 的性能与其他共识算法（如 Paxos）类似。性能最重要的情况是当一个已建立的领导者复制新的日志条目时。Raft 通过最少的消息数来实现这一点（从领导者到集群一半节点的单轮）。还可以进一步提高 Raft 的性能。例如，它可以轻松地支持批量处理和按管道处理请求以获得更高的吞吐量和更低的延迟。文献中已经为其他算法提出了各种优化；其中许多可以应用于 Raft，但我们将留给未来的工作。我们使用 raft 实现来衡量 raft 领导者选举算法的性能，并回答两个问题。首先，选举过程是否能快速收敛？其次，在领导者崩溃后，最小停机时间是多少？为了测量领导者选举，我们反复崩溃了一组由五个服务器组成的集群中的领导者，并记录检测到崩溃并选择新领导者的所花费的时间（见图 16）。为了生成最坏情况，每个试验中的服务器具有不同的日志长度，因此一些候选者不能成为领导者。此外，为了鼓励分裂投票，我们的测试脚本在终止其进程之前从领导者触发了一个同步心跳RPC广播（这近似于领导者在崩溃之前复制新的日志条目）在所有测试中，领导者在心跳间隔内随机均匀地崩溃了。心跳间隔是所有测试中最少选举超时的一半。因此，最小可能的停机时间大约是最低选举超时的一半。图16中的顶部图表显示，选举超时中的一小部分随机性足以避免选举中的分裂投票。在没有随机性的情况下，在我们的测试中，由于许多分裂投票，领导选举始终需要超过10秒的时间。仅添加5毫秒的随机性大大有助于减少停机时间中位数为287毫秒。使用更多的随机性可以改善最坏情况的行为：在50毫秒的随机性下，最坏情况下完成（超过1000次试验）为513毫秒。图16中底部的图表显示，通过减少选举超时时间可以降低停机时间。当选举超时为12-24毫秒时，平均只需要35毫秒就可以选出一个领导者（最长试验时间为152毫秒）。然而，在此点之后降低超时会违反raft的时间要求：在其他服务器开始新选举之前，领导者很难广播心跳信息。这可能会导致不必要的领导者更改并降低整体系统的可用性。我们建议使用保守的选举超时，例如150-300毫秒；这样的超时不太可能导致不必要的领导者更改，并且仍然能够提供良好的可用性。

10 相关工作

关于共识算法有许多出版物，其中许多属于以下类别之一： • Lamport 的 Paxos 原始描述 [15]，以及试图更清楚地解释它 [16, 20, 21]。 Paxos 算法的改进版本，其中填补了缺失的细节，并修改算法以提供更好的实现基础。[26, 39, 13] • 实现共识算法的系统，如 Chubby[2, 4]、ZooKeeper[11, 12] 和 Spanner[6]。Chubby 和 Spanner 的算法尚未公开发表，尽管它们都声称基于 Paxos。ZooKeeper 的算法已经发表，但与 Paxos 相比有很大不同。 • 可用于 Paxos 的性能优化 [18, 19, 3, 25, 1, 27]。 • Okidisk 的 Viewstamped Replication (VR)，这是与 Paxos 同时开发的一种共识替代方法。最初的描述 [29] 与分布式事务协议交织在一起，但最近的更新[22] 将核心共识协议分离开来。VR 使用基于领导者的方法，与 Raft 具有很多相似之处。 Raft 和 Paxos 之间最大的区别在于 Raft 强大的领导力：Raft 将领导者选举作为一致性协议的重要组成部分，它关注—— 在领导者中实现尽可能多的功能。这种方法导致一个更简单的算法，更容易理解。例如，在 Paxos 中，领导者选举与基本共识协议正交：它仅用于性能优化，并且不需要达成共识。然而，这会导致额外的机制：Paxos 包含了对基本共识的两阶段协议以及单独的领导者选举机制。相比之下，Raft 直接将领导者选举纳入共识算法并将其作为共识的两个阶段之一使用。这就比 Paxos 更少的机制。与Raft一样，VR 和 ZooKeeper 也是基于领导者模式，因此共享许多Raft相对于Paxos的优点。然而，由于Raft减少了非领导者的功能，所以它比VR或ZooKeeper少了一些机制。例如，在Raft中，日志条目只在一个方向流动：在 AppendEntries RPC 中从领导者向外流动。而在VR中，日志条目双向流动（在选举过程中，领导者可以接收日志条目）；这导致了额外的机制和复杂性。ZooKeeper 的公开描述也涉及向领导者发送和接收日志条目，但实现显然更接近于Raft [35]。我们所知道的所有基于共识的日志复制算法中，raft 的消息类型最少。例如，我们计算了 VR 和 ZooKeeper 在基本共识和成员更改(排除日志压缩和客户端交互，因为这些几乎与算法无关)时使用的消息类型。VR 和 ZooKeeper 每个定义了 10 种不同的消息类型，而 raft 只有 4 种消息类型（两个远程过程调用请求及其响应）。raft 的消息比其他算法稍显密集，但总体上更简单。此外，VR 和 ZooKeeper 描述的是在领导者变更期间传输整个日志；需要额外的消息类型来优化这些机制使其可行。 Raft 的强大的领导方法简化了算法，但排除了一些性能优化。例如，在某些情况下，平等主义 Paxos（EPaxos）可以实现更高的性能，而无需领导者的方法。[27] EPaxos 利用了状态机命令的可交换性。只要其他并发提出的命令与之可交换，任何服务器都可以通过仅一轮通信来提交一个命令。然而，如果同时提出的所有命令彼此不可交换，则 EPaxos 需要额外的一轮通信。由于任何服务器都可能提交命令，因此 EPaxos 在服务器之间很好地平衡负载，并且能够比 Raft 在广域网设置中实现更低的延迟。但是，它给 Paxos 增加了显著的复杂性。在其他工作中，已经提出了或实现了几种不同的方法来处理成员关系的变化，包括Lamport最初的提议[15]、VR [22] 和SMART [24]。我们选择Raft使用联合共识的方法，因为它利用了其余的共识协议，因此对成员关系变化所需的额外机制很少。Lamport基于α的方法不是Raft的选择，因为它假设可以在没有领导者的情况下达成共识。与VR和SMART相比，Raft的重新配置算法的优势在于可以进行成员关系更改而不限制正常请求的处理；相反，VR在配置更改期间停止所有正常处理，而SMART对未决请求数量施加类似于α的限制。Raft的方法也比VR或SMART添加更少的机制。

11 结论

算法通常以正确性、效率或简洁性为主要目标来设计。虽然这些都是值得追求的目标，但我们认为可理解性也同样重要。在开发人员将算法转化为实际实现之前，这些都不是可以达到的目标，而这种实现必然与已发表的形式相偏离并对其进行扩展。除非开发人员对算法有深入的理解，并能为其创建直觉，否则他们很难在其实现中保留其令人愉悦的特性。在这篇论文中，我们讨论了分布式共识的问题，这是一个广为接受但难以理解的算法 Paxos 已经挑战学生和开发人员多年。我们设计了一个新的算法，Raft，并证明它比 Paxos 更容易理解。我们还认为，Raft 为系统构建提供了更好的基础。使用可理解性作为主要设计目标改变了我们对 Raft 设计的方法；随着设计的发展，我们发现自己反复重用了一些技术，例如分解问题和简化状态空间。这些技术不仅提高了 Raft 的可理解性，而且使我们更容易相信它的正确性。

12 致谢

The user study would not have been possible with-out the support of Ali Ghodsi, David Mazieres, and the students of CS 294-91 at Berkeley and CS 240 at Stan-ford. Scott Klemmer helped us design the user study, and Nelson Ray advised us on statistical analysis. The Paxos slides for the user study borrowed heavily from a slide deck originally created by Lorenzo Alvisi. Spe-cial thanks go to David Mazieres and Ezra Hoch for finding subtle bugs in Raft. Many people provided help-ful feedback on the paper and user study materials, including Ed Bugnion, Michael Chan, Hugues Evrard,Daniel Giffin, Arjun Gopalan, Jon Howell, Vimalkumar Jeyakumar, Ankita Kejriwal, Aleksandar Kracun, Amit Levy, Joel Martin, Satoshi Matsushita, Oleg Pesok, David Ramos, Robbert van Renesse, Mendel Rosenblum, Nico-las Schiper, Deian Stefan, Andrew Stone, Ryan Stutsman, David Terei, Stephen Yang, Matei Zaharia, 24 anony-mous conference reviewers(with duplicates), and espe-cially our shepherd Eddie Kohler. Werner Vogels tweeted a link to an earlier draft, which gave Raft significant ex-posure. This work was supported by the Gigascale Sys-tems Research Center and the Multiscale Systems Cen-ter, two of six research centers funded under the Fo-cus Center Research Program, a Semiconductor Research Corporation program, by STARnet, a Semiconductor Re-search Corporation program sponsored by MARCO and DARPA, by the National Science Foundation under Grant No. 0963859, and by grants from Facebook, Google, Mel-lanox, NEC, NetApp, SAP, and Samsung. Diego Ongaro is supported by The Junglee Corporation Stanford Gradu-ate Fellowship.

参考文献

[1] BOLOSKY, W. J., BRADSHAW, D., HAAGENS, R. B., KUSTERS, N. P., AND LI, P. Paxos replicated state machines as the basis of a high-performance data store. In Proc. NSDI’11, USENIX Conference on Networked Systems Design and Implementation(2011), USENIX, pp. 141–154.

[2] BURROWS, M. The Chubby lock service for loosely-coupled distributed systems. In Proc. OSDI’06, Sympo-sium on Operating Systems Design and Implementation(2006), USENIX, pp. 335–350.

[3] CAMARGOS, L. J., SCHMIDT, R. M., AND PEDONE, F. Multicoordinated Paxos. In Proc. PODC’07, ACM Sym-posium on Principles of Distributed Computing(2007), ACM, pp. 316–317.

[4] CHANDRA, T. D., GRIESEMER, R., AND REDSTONE, J. Paxos made live: an engineering perspective. In Proc. PODC’07, ACM Symposium on Principles of Distributed Computing(2007), ACM, pp. 398–407.

[5] CHANG, F., DEAN, J., GHEMAWAT, S., HSIEH, W. C., WALLACH, D. A., BURROWS, M., CHANDRA, T., FIKES, A., AND GRUBER, R. E. Bigtable: a distributed storage system for structured data. In Proc. OSDI’06, USENIX Symposium on Operating Systems Design and Implementation(2006), USENIX, pp. 205–218.

[6] CORBETT, J. C., DEAN, J., EPSTEIN, M., FIKES, A., FROST, C., FURMAN, J. J., GHEMAWAT, S., GUBAREV, A., HEISER, C., HOCHSCHILD, P., HSIEH, W., KAN-THAK, S., KOGAN, E., LI, H., LLOYD, A., MELNIK, S., MWAURA, D., NAGLE, D., QUINLAN, S., RAO, R., ROLIG, L., SAITO, Y., SZYMANIAK, M., TAYLOR, C., WANG, R., AND WOODFORD, D. Spanner: Google’s globally-distributed database. In Proc. OSDI’12, USENIX Conference on Operating Systems Design and Implemen-tation(2012), USENIX, pp. 251–264.

[7] COUSINEAU, D., DOLIGEZ, D., LAMPORT, L., MERZ, S., RICKETTS, D., AND VANZETTO, H. TLA+ proofs. In Proc. FM’12, Symposium on Formal Methods(2012), D. Giannakopoulou and D. Me´ry, Eds., vol. 7436 of Lec-ture Notes in Computer Science, Springer, pp. 147–154.

[8] GHEMAWAT, S., GOBIOFF, H., AND LEUNG, S.-T. The Google file system. In Proc. SOSP’03, ACM Symposium on Operating Systems Principles(2003), ACM, pp. 29–43.

[9] GRAY, C., AND CHERITON, D. Leases: An efficient fault-tolerant mechanism for distributed file cache consistency. In Proceedings of the 12th ACM Ssymposium on Operating Systems Principles(1989), pp. 202–210.

[10] HERLIHY, M. P., AND WING, J. M. Linearizability: a correctness condition for concurrent objects. ACM Trans-actions on Programming Languages and Systems 12(July1990), 463–492.

[11] HUNT, P., KONAR, M., JUNQUEIRA, F. P., AND REED, B. ZooKeeper: wait-free coordination for internet-scale systems. In Proc ATC’10, USENIX Annual Technical Con-ference(2010), USENIX, pp. 145–158.

[12] JUNQUEIRA, F. P., REED, B. C., AND SERAFINI, M. Zab: High-performance broadcast for primary-backup sys-tems. In Proc. DSN’11, IEEE/IFIP Int’l Conf. on Depend-able Systems& Networks(2011), IEEE Computer Society, pp. 245–256.

[13] KIRSCH, J., AND AMIR, Y. Paxos for system builders. Tech. Rep. CNDS-2008-2, Johns Hopkins University,2008.

[14] LAMPORT, L. Time, clocks, and the ordering of events in a distributed system. Commununications of the ACM 21, 7(July 1978), 558–565.

[15] LAMPORT, L. The part-time parliament. ACM Transac-tions on Computer Systems 16, 2(May 1998), 133–169.

[16] LAMPORT, L. Paxos made simple. ACM SIGACT News32, 4(Dec. 2001), 18–25.

[17] LAMPORT, L. Specifying Systems, The TLA+ Language and Tools for Hardware and Software Engineers. Addison-Wesley, 2002.

[18] LAMPORT, L. Generalized consensus and Paxos. Tech. Rep. MSR-TR-2005-33, Microsoft Research, 2005.

[19] LAMPORT, L. Fast paxos. Distributed Computing 19, 2(2006), 79–103.

[20] LAMPSON, B. W. How to build a highly available system using consensus. In Distributed Algorithms, O. Baboaglu and K. Marzullo, Eds. Springer-Verlag, 1996, pp. 1–17.

[21] LAMPSON, B. W. The ABCD’s of Paxos. In Proc. PODC’01, ACM Symposium on Principles of Distributed Computing(2001), ACM, pp. 13–13.

[22] LISKOV, B., AND COWLING, J. Viewstamped replica-tion revisited. Tech. Rep. MIT-CSAIL-TR-2012-021, MIT, July 2012.

[23] LogCabin source code. http://github.com/logcabin/logcabin.

[24] LORCH, J. R., ADYA, A., BOLOSKY, W. J., CHAIKEN, R., DOUCEUR, J. R., AND HOWELL, J. The SMART way to migrate replicated stateful services. In Proc. Eu-roSys’06, ACM SIGOPS/EuroSys European Conference on Computer Systems(2006), ACM, pp. 103–115.

[25] MAO, Y., JUNQUEIRA, F. P., AND MARZULLO, K. Mencius: building efficient replicated state machines for WANs. In Proc. OSDI’08, USENIX Conference on Operating Systems Design and Implementation(2008), USENIX, pp. 369–384.

[26] MAZIE`RES, D. Paxos made practical. http://www.scs.stanford.edu/˜dm/home/papers/paxos.pdf, Jan. 2007.

[27] MORARU, I., ANDERSEN, D. G., AND KAMINSKY, M. There is more consensus in egalitarian parliaments. In Proc. SOSP’13, ACM Symposium on Operating System Principles(2013), ACM.

[28] Raft user study. http://ramcloud.stanford. edu/˜ongaro/userstudy/.

[29] OKI, B. M., AND LISKOV, B. H. Viewstamped replication: A new primary copy method to support highly-available distributed systems. In Proc. PODC’88, ACM Symposium on Principles of Distributed Computing(1988), ACM, pp. 8–17.

[30] O’NEIL, P., CHENG, E., GAWLICK, D., AND ONEIL, E. The log-structured merge-tree(LSM-tree). Acta Informat-ica 33, 4(1996), 351–385.

[31] ONGARO, D. Consensus: Bridging Theory and Practice. PhD thesis, Stanford University, 2014(work in progress).

http://ramcloud.stanford.edu/˜ongaro/thesis.pdf.

[32] ONGARO, D., AND OUSTERHOUT, J. In search of an understandable consensus algorithm. In Proc ATC’14, USENIX Annual Technical Conference(2014), USENIX.

[33] OUSTERHOUT, J., AGRAWAL, P., ERICKSON, D., KOZYRAKIS, C., LEVERICH, J., MAZIE`RES, D., MI-TRA, S., NARAYANAN, A., ONGARO, D., PARULKAR, G., ROSENBLUM, M., RUMBLE, S. M., STRATMANN, E., AND STUTSMAN, R. The case for RAMCloud. Com-munications of the ACM 54(July 2011), 121–130.

[34] Raft consensus algorithm website. http://raftconsensus.github.io.

[35] REED, B. Personal communications, May 17, 2013.

[36] ROSENBLUM, M., AND OUSTERHOUT, J. K. The design and implementation of a log-structured file system. ACM Trans. Comput. Syst. 10(February 1992), 26–52.

[37] SCHNEIDER, F. B. Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Com-puting Surveys 22, 4(Dec. 1990), 299–319.

[38] SHVACHKO, K., KUANG, H., RADIA, S., AND CHANSLER, R. The Hadoop distributed file system. In Proc. MSST’10, Symposium on Mass Storage Sys-tems and Technologies(2010), IEEE Computer Society, pp. 1–10.

[39] VAN RENESSE, R. Paxos made moderately complex. Tech. rep., Cornell University, 2012.