掘金 后端 ( ) • 2024-05-17 10:12
【翻译】(Raft) In search of an Understandable Consensus Algorithm（寻找一种易于理解的一致性算法）
Understandable Consensus Algorithm 一致性 算法 翻译

摘要

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名学生中进行的用户研究表明，Raft比Paxos更容易理解：在学习了两种算法之后，这些学生中有33人能够更好地回答关于Raft的问题而不是关于Paxos的问题。
  • Raft在许多方面与现有的一致性算法相似（最著名的是Oki和Liskov的Viewstamped Replication [29, 22]），但它具有几个新颖的特点：
    • 强领导者：Raft使用比其他一致性算法更强的领导形式。例如，日志条目仅从领导者流向其他服务器。这简化了复制日志的管理，并使Raft更易于理解。
    • 领导者选举：Raft使用随机定时器来选举领导者。这仅为任何一致性算法所需的心跳添加了少量机制，同时简单快速地解决了冲突。
    • 成员变更：Raft用于更改集群中服务器集合的机制使用了一种新的联合一致性方法，在转换期间两个不同配置的大多数重叠。这允许集群在配置更改期间继续正常运行。
  • 我们认为，Raft相对于Paxos和其他一致性算法，在教育目的和作为实现基础方面都更加优越。它比其他算法更简单、更易于理解；它的描述足够完整，以满足实际系统的需求；它有几个开源实现，并被几家公司使用；它的安全性质已经被正式指定和证明；它的效率与其他算法相当。
  • 本文的其余部分介绍了复制状态机问题（第2节），讨论了Paxos的优点和缺点（第3节），描述了我们的可理解性的一般方法（第4节），介绍了Raft一致性算法（第5-8节），评估了Raft（第9节），并讨论了相关工作（第10节）。

2. 复制状态机

  • 一致性算法通常出现在复制状态机的背景下[37]。在这种方法中，一组服务器上的状态机计算相同状态的相同副本，并且即使其中一些服务器宕机，它们也可以继续运行。复制状态机用于解决分布式系统中的各种容错问题。例如，具有单个集群领导者的大型系统，例如GFS [8]，HDFS [38]和RAMCloud [33]，通常使用单独的复制状态机来管理领导者选举并存储必须在领导者崩溃后存活的配置信息。复制状态机的示例包括Chubby [2]和ZooKeeper [11]。 1.jpg
    • 图1：复制状态机架构。一致性算法管理一个包含来自客户端的状态机命令的复制日志。状态机从日志中处理相同的命令序列，因此它们产生相同的输出。
  • 复制状态机通常使用复制日志来实现，如图1所示。每个服务器存储一个包含一系列命令的日志，其状态机按顺序执行这些命令。每个日志包含相同的命令，以相同的顺序，因此每个状态机处理相同的命令序列。由于状态机是确定性的，因此每个状态机计算相同的状态和相同的输出序列。
  • 保持复制日志的一致性是一致性算法的工作。服务器上的一致性模块接收来自客户端的命令并将其添加到其日志中。它与其他服务器上的一致性模块通信，以确保每个日志最终包含相同的请求，以相同的顺序，即使某些服务器失败。一旦命令被正确复制，每个服务器的状态机按日志顺序处理它们，并将输出返回给客户端。因此，服务器似乎形成了一个单一的、高度可靠的状态机。
  • 实际系统的一致性算法通常具有以下特性：
    • 它们在所有非拜占庭条件下确保安全性（永远不会返回错误结果），包括网络延迟、分区、数据包丢失、重复和重新排序
      • 【注】拜占庭问题(non-Byzantine conditions)，在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的
    • 只要大多数服务器正常运行并且可以相互通信和与客户端通信，它们就是完全功能的（可用）。因此，一个典型的五个服务器的集群可以容忍任何两个服务器的故障。假定服务器通过停止来失败；它们可以稍后从稳定存储器上的状态恢复并重新加入集群。
    • 它们不依赖于时间来确保日志的一致性：错误的时钟和极端的消息延迟最多会导致可用性问题。
    • 在常见情况下，只要集群的大多数响应了一轮远程过程调用，一个命令就可以完成；少数慢速服务器不需要影响整个系统的性能。

3. Paxos 算法存在哪些问题？

  • 在过去的十年中，Leslie Lamport的Paxos协议[15]几乎成为一致性的代名词：这是课程中最常教授的协议，大多数一致性的实现都以它为起点。Paxos首先定义了一个协议，能够就单个决策达成一致，例如单个复制的日志条目。我们将这个子集称为单决策Paxos。然后，Paxos将多个实例的这个协议组合起来，以便进行一系列决策，例如日志（多Paxos）。Paxos确保了安全性和活性，并支持集群成员的更改。它的正确性已经得到证明，并且在正常情况下效率很高。
  • 不幸的是，Paxos有两个显著的缺点。第一个缺点是Paxos非常难以理解。完整的解释[15]是出了名的晦涩难懂；很少有人能够理解它，而且需要付出巨大的努力。因此，已经有几次尝试用更简单的术语解释Paxos[16, 20, 21]。这些解释集中在单决策子集上，但仍然具有挑战性。在对NSDI 2012的参与者进行的非正式调查中，我们发现即使是经验丰富的研究人员中也很少有人能够熟练掌握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节）。
    • 日志复制： 领导者必须接受来自客户端的日志条目并在整个集群中复制它们，强制其他日志与其自己保持一致（第5.3节）。
    • 安全性： Raft的关键安全属性是图3中的状态机安全属性：如果任何服务器已将特定的日志条目应用于其状态机，则其他服务器不得为相同的日志索引应用不同的命令。第5.4节描述了Raft如何确保此属性；解决方案涉及对第5.2节中描述的选举机制的附加限制。 2.jpg
    • 图2：Raft是一种一致性算法，用于在分布式系统中维护一致的日志。Raft通过将一组服务器划分为领导者、跟随者和候选者来实现一致性。领导者负责复制日志并处理客户端请求。跟随者只是被动地响应领导者和候选者的请求。候选者用于发起领导者选举。Raft使用随机化选举超时来避免选举冲突。一旦选出领导者，它将处理客户端请求并向跟随者复制日志。Raft的关键安全属性是状态机安全属性，它确保如果任何服务器已将特定的日志条目应用于其状态机，则其他服务器不得为相同的日志索引应用不同的命令。Raft还包括一些优化，例如预先投票和心跳超时。Raft的完整规范可以在[31]中找到。 3.jpg
    • 图3：Raft保证这些属性始终为真，每个属性在规范的哪个部分讨论由括号中的章节号表示。
      • 选举安全性： 在给定的任期内最多只能选举出一个领导者。§5.2
      • 领导者追加日志： 领导者永远不会覆盖或删除其日志中的条目，只会追加新条目。§5.3
      • 日志匹配： 如果两个日志包含相同索引和任期的条目，则这些日志在给定索引之前的所有条目都是相同的。§5.3
      • 领导者完整性： 如果在给定任期中提交了一个日志条目，则该条目将出现在所有更高任期的领导者的日志中。§5.4
      • 状态机安全性： 如果服务器已将特定索引处的日志条目应用于其状态机，则其他服务器将永远不会为相同索引应用不同的日志条目。§5.4.3
  • 在介绍一致性算法之后，本节讨论了可用性问题以及时间在系统中的作用。
5.1 Raft 基础
  • 一个Raft集群包含多个服务器，通常是五个，这样可以容忍两个故障。在任何给定时间，每个服务器都处于三种状态之一：领导者、跟随者或候选人。在正常操作中，恰好有一个领导者，所有其他服务器都是跟随者。跟随者是被动的：它们不会主动发出请求，而只是响应领导者和候选人的请求。领导者处理所有客户端请求（如果客户端联系跟随者，则跟随者将其重定向到领导者）。第三种状态，候选人，用于选举新的领导者，如第5.2节所述。图4显示了这些状态及其转换；下面将讨论这些转换。 4.jpg
    • 图4：服务器状态。跟随者只响应来自其他服务器的请求。如果跟随者没有收到通信，则成为候选人并发起选举。从完整集群中获得多数票的候选人成为新领导者。领导者通常在失败之前一直运行。
  • Raft将时间分成任意长度的任期，如图5所示。任期用连续的整数编号。每个任期都以选举开始，在选举中，一个或多个候选人试图成为领导者，如第5.2节所述。如果候选人赢得选举，那么它将在剩余的任期中担任领导者。在某些情况下，选举将导致投票分裂。在这种情况下，任期将在没有领导者的情况下结束；不久将开始一个新任期（带有新的选举）。Raft确保在给定任期中最多只有一个领导者。 5.jpg
    • 图5：时间被分成任期，每个任期都以选举开始。成功选举后，单个领导者管理集群直到任期结束。有些选举会失败，在这种情况下，任期将在没有选择领导者的情况下结束。任期之间的转换可能在不同的服务器上在不同的时间观察到。
  • 不同的服务器可能在不同的时间观察到任期之间的转换，在某些情况下，服务器甚至可能无法观察到选举或整个任期。在Raft中，任期充当逻辑时钟[14]，它们允许服务器检测过时的信息，例如过时的领导者。每个服务器存储一个当前任期编号，该编号随时间单调递增。当前任期在服务器通信时进行交换；如果一个服务器的当前任期小于另一个服务器的当前任期，则它将其当前任期更新为较大的值。如果候选人或领导者发现其任期已过时，则立即恢复为follower状态。如果服务器收到具有过时任期编号的请求，则拒绝该请求。
  • Raft服务器使用远程过程调用（RPC）进行通信，基本的一致性算法仅需要两种类型的RPC。RequestVote RPC由候选人在选举期间发起（第5.2节），而AppendEntries RPC由领导者发起，用于复制日志条目并提供一种心跳形式（第5.3节）。第7节添加了第三个RPC，用于在服务器之间传输快照。如果服务器没有及时收到响应，则会重试RPC，并且它们会并行发出RPC以获得最佳性能。
5.2 领导者选举
  • Raft使用心跳机制来触发领导者选举。当服务器启动时，它们作为跟随者开始。只要跟随者从领导者或候选人接收到有效的RPC，服务器就会保持跟随者状态。领导者定期向所有跟随者发送心跳（不携带日志条目的AppendEntries RPC），以维护其权威性。如果跟随者在一段称为选举超时的时间内没有收到通信，则它会认为没有可行的领导者，并开始选举选择新的领导者。
  • 为了开始选举，跟随者会增加其当前任期并转换为候选人状态。然后，它会为自己投票，并并行向集群中的每个其他服务器发出RequestVote RPC。候选人会一直保持这种状态，直到发生以下三种情况之一：(a)它赢得了选举，(b)另一个服务器成为领导者，或者(c)一段时间过去了，没有获胜者。这些结果将在下面的段落中分别讨论。
  • 如果候选人在同一任期内从全集群中获得了大多数服务器的投票，则候选人赢得选举。每个服务器在给定任期内最多只能为一个候选人投票，按先到先得的顺序进行投票（注意：第5.4节对投票增加了额外的限制）。多数规则确保最多只有一个候选人可以赢得特定任期的选举（图3中的选举安全性属性）。一旦候选人赢得选举，它就成为领导者。然后，它向所有其他服务器发送心跳消息，以建立其权威并防止新的选举。
  • 在等待投票时，候选人可能会收到来自另一台服务器的AppendEntries RPC，声称自己是领导者。如果领导者的任期（包含在其RPC中）至少与候选人的当前任期一样大，则候选人将认可领导者为合法，并返回跟随者状态。如果RPC中的任期小于候选人的当前任期，则候选人将拒绝RPC并继续保持候选人状态。
  • 第三种可能的结果是，候选人既没有赢得选举也没有输掉选举：如果许多跟随者同时成为候选人，则投票可能会分裂，以至于没有候选人获得多数票。当这种情况发生时，每个候选人都会超时并通过增加其任期并启动另一轮RequestVote RPC来开始新的选举。然而，如果没有额外的措施，分裂的投票可能会无限期地重复。
  • Raft使用随机选举超时来确保分裂的投票很少发生，并且它们能够迅速解决。为了防止分裂的投票，选举超时从一个固定的时间间隔（例如150-300ms）中随机选择。这样可以将服务器分散开来，以便在大多数情况下只有一个服务器会超时；它赢得选举并在其他任何服务器超时之前发送心跳。相同的机制用于处理分裂的投票。每个候选人在选举开始时重新启动其随机选举超时，并等待该超时时间到期后再开始下一轮选举；这减少了新选举中发生另一次分裂投票的可能性。第9.3节展示了这种方法如何快速选举出领导者。
5.3 日志复制
  • 一旦选出领导者，它就开始处理客户端请求。每个客户端请求都包含一个由复制状态机执行的命令。领导者将命令作为新条目附加到其日志中，然后并行向每个其他服务器发出AppendEntries RPC以复制该条目。当该条目已经被安全地复制（如下所述）后，领导者将该条目应用于其状态机，并将该执行结果返回给客户端。如果跟随者崩溃或运行缓慢，或者网络数据包丢失，领导者将无限期地重试AppendEntries RPC（即使它已经响应了客户端），直到所有跟随者最终存储所有日志条目。
  • 日志的组织方式如图6所示。每个日志条目都存储了一个状态机命令以及该条目被领导者接收时的任期号。日志条目中的任期号用于检测日志之间的不一致性，并确保图3中的某些属性。每个日志条目还具有一个整数索引，用于标识其在日志中的位置。 6.jpg
    • 图6：日志由条目组成，这些条目按顺序编号。每个条目包含创建它的任期（每个框中的数字）和状态机的命令。如果可以安全地将条目应用于状态机，则认为该条目已提交。
  • 领导者决定何时将日志条目应用于状态机，这样的条目称为已提交。Raft保证已提交的条目是持久的，并最终将由所有可用状态机执行。一旦创建条目的领导者在大多数服务器上复制了该条目（例如，图6中的条目7），则日志条目已提交。这也提交了领导者日志中的所有先前条目，包括由先前领导者创建的条目。第5.4节讨论了在领导者更改后应用此规则时的一些细微差别，并且还表明这种承诺的定义是安全的。领导者跟踪它知道已提交的最高索引，并将该索引包括在未来的AppendEntries RPC（包括心跳）中，以便其他服务器最终找到。一旦跟随者了解到日志条目已提交，它将按照日志顺序将该条目应用于其本地状态机。
  • 我们设计了Raft日志机制，以在不同服务器上维护日志之间的高度一致性。这不仅简化了系统的行为并使其更可预测，而且是确保安全的重要组成部分。Raft维护以下属性，这些属性共同构成图3中的日志匹配属性：
    • 如果不同日志中的两个条目具有相同的索引和任期，则它们存储相同的命令。
    • 如果不同日志中的两个条目具有相同的索引和任期，那么前面所有的日志都是相同的条目。
  • 第一个属性源于领导者在给定任期内最多创建一个具有给定日志索引的条目，而日志条目永远不会改变其在日志中的位置。第二个属性由AppendEntries执行的简单一致性检查保证。在发送AppendEntries RPC时，领导者在其日志中包括立即在新条目之前的条目的索引和任期。如果跟随者在其日志中找不到具有相同索引和任期的条目，则拒绝新条目。一致性检查充当归纳步骤：日志的初始空状态满足日志匹配属性，并且每当日志被扩展时，一致性检查都会保持日志匹配属性。因此，每当AppendEntries成功返回时，领导者都知道跟随者的日志与其自己的日志在新条目之前是相同的。
  • 在正常操作期间，领导者和跟随者的日志保持一致，因此AppendEntries一致性检查永远不会失败。然而，领导者崩溃可能会使日志不一致（旧领导者可能没有完全复制其日志中的所有条目）。这些不一致性可能会在一系列领导者和跟随者崩溃中累积。图7说明了跟随者的日志可能与新领导者的日志不同的方式。跟随者可能缺少领导者存在的条目，可能存在领导者不存在的额外条目，或者两者都有。日志中缺少和多余的条目可能跨越多个任期。 7.jpg
    • 图7：当顶部的领导者上台时，跟随者日志中可能发生(a-f)中的任何一种情况。每个框表示一个日志条目；框中的数字是其任期。跟随者可能缺少条目（a-b），可能有额外的未提交条目（c-d），或者两者都有（e-f）。例如，如果该服务器是第2个任期的领导者，在其日志中添加了几个条目，然后在提交任何条目之前崩溃；它很快重新启动，成为第3个任期的领导者，并在其日志中添加了几个条目；在提交第2个或第3个任期中的任何条目之前，该服务器再次崩溃，并保持关闭状态数个任期。
  • 在Raft中，领导者通过强制跟随者的日志复制自己的日志来处理不一致性。这意味着跟随者日志中的冲突条目将被领导者日志中的条目覆盖。第5.4节将展示，当与另一个限制相结合时，这是安全的。
  • 为了使跟随者的日志与自己的日志保持一致，领导者必须找到两个日志中最新的一条条目，使它们达成一致，删除该点之后跟随者日志中的所有条目，并将该点之后的所有领导者条目发送给跟随者。所有这些操作都是响应于AppendEntries RPC执行的一致性检查。领导者为每个跟随者维护一个nextIndex，它是领导者将要发送给该跟随者的下一个日志条目的索引。当领导者首次上台时，它将所有nextIndex值初始化为其日志中最后一个条目之后的索引（图7中的11）。如果跟随者的日志与领导者的日志不一致，则下一个AppendEntries RPC中的一致性检查将失败。在拒绝之后，领导者会减少nextIndex并重试AppendEntries RPC。最终，nextIndex将达到领导者和跟随者日志匹配的点。当这种情况发生时，AppendEntries将成功，这将删除跟随者日志中的任何冲突条目，并附加领导者日志中的条目（如果有）。一旦AppendEntries成功，跟随者的日志就与领导者的日志保持一致，并将在该任期的其余时间内保持一致。
  • 如果需要，可以优化协议以减少被拒绝的AppendEntries RPC的数量。例如，当拒绝一个AppendEntries请求时，跟随者可以包括冲突条目的任期和它存储该任期的第一个索引。有了这些信息，领导者可以将nextIndex减少以跳过该任期中的所有冲突条目；每个具有冲突条目的任期将需要一个AppendEntries RPC，而不是每个条目一个RPC。在实践中，我们怀疑这种优化是不必要的，因为故障发生得很少，而且不太可能存在许多不一致的条目。
  • 有了这个机制，当领导者重新上台时，它不需要采取任何特殊的措施来恢复日志一致性。它只需开始正常操作，日志将自动在响应AppendEntries一致性检查失败时收敛。领导者从不覆盖或删除其自己日志中的条目（图3中的领导者追加属性）。
  • 这种日志复制机制展现了第2节中描述的理想一致性属性：只要大多数服务器处于运行状态，Raft就可以接受、复制和应用新的日志条目；在正常情况下，一个新条目可以通过向大多数集群进行一轮RPC来复制；单个缓慢的跟随者不会影响性能。
5.4 安全性
  • 前面的章节描述了Raft如何选举领导者并复制日志条目。然而，到目前为止描述的机制还不足以确保每个状态机按相同的顺序执行完全相同的命令。例如，当领导者提交多个日志条目时，跟随者可能不可用，然后它可能被选为领导者并用新的条目覆盖这些条目；结果，不同的状态机可能执行不同的命令序列。
  • 本节通过对哪些服务器可以被选为领导者的限制来完善Raft算法。该限制确保任何给定任期的领导者都包含在之前任期中提交的所有条目（图3中的Leader Completeness Property）。在给定选举限制的情况下，我们进一步明确了提交规则。最后，我们提供了Leader Completeness Property的证明概述，并展示了它如何导致复制状态机的正确行为。
5.4.1 选举限制
  • 在任何基于领导者的一致性算法中，领导者最终必须存储所有已提交的日志条目。在某些一致性算法中，例如Viewstamped Replication [22]，即使领导者最初不包含所有已提交的条目，也可以选举出领导者。这些算法包含其他机制来识别缺失的条目并将它们传输到新的领导者，无论是在选举过程中还是之后不久。不幸的是，这会导致相当大的额外机制和复杂性。Raft使用了一种更简单的方法，它保证了每个新领导者从选举时刻起就包含了之前任期中所有已提交的条目，而无需将这些条目传输到领导者。这意味着日志条目只在一个方向上流动，即从领导者到跟随者，领导者从不覆盖其日志中的现有条目。
  • Raft使用投票过程来防止候选人赢得选举，除非其日志包含所有已提交的条目。候选人必须联系集群中的大多数节点才能当选，这意味着每个已提交的条目必须至少存在于其中一个服务器中。如果候选人的日志至少与大多数节点中的任何其他日志一样新（其中“最新”在下面被精确定义），那么它将包含所有已提交的条目。RequestVote RPC实现了这个限制：RPC包括有关候选人日志的信息，如果投票者自己的日志比候选人的日志更为最新，则投票者会拒绝投票。
  • Raft通过比较日志中最后一个条目的索引和任期来确定哪个日志更为最新。如果日志的最后一个条目具有不同的任期，则具有较晚任期的日志更为最新。如果日志以相同的任期结束，则较长的日志更为最新。
5.4.2 提交先前任期的日志条目
  • 正如第5.3节所述，领导者知道只有在其当前任期的条目存储在大多数服务器上时，该条目才被提交。如果领导者在提交条目之前崩溃，则未来的领导者将尝试完成复制该条目的工作。然而，领导者不能立即得出结论，即一条来自先前任期的条目一旦存储在大多数服务器上就被提交。图8说明了这样一种情况：旧的日志条目存储在大多数服务器上，但仍然可以被未来的领导者覆盖。 8.jpg
    • 图8：这个时序展示了为什么领导者不能使用旧任期的日志条目确定提交。在（a）中，S1是领导者，并部分复制了索引2处的日志条目。在（b）中，S1崩溃；S5被选为第3个任期的领导者，获得了S3、S4和自己的选票，并接受了日志索引2处的不同条目。在（c）中，S5崩溃；S1重新启动，被选为领导者，并继续复制。此时，来自第2个任期的日志条目已经在大多数服务器上复制，但尚未提交。如果S1像（d）中那样崩溃，S5可以被选为领导者（获得S2、S3和S4的选票），并用其自己的第3个任期的条目覆盖该条目。但是，如果S1在崩溃之前在大多数服务器上复制了来自其当前任期的条目，如（e）中所示，则该条目已提交（S5无法赢得选举）。此时，日志中所有先前的条目都已提交。
  • 为了消除像图8中的问题，Raft不会通过计算副本来提交来自先前任期的日志条目。只有来自领导者当前任期的日志条目通过计算副本被提交；一旦以这种方式提交了当前任期的条目，那么所有先前的条目都间接地因为日志匹配属性而被提交。有些情况下，领导者可以安全地得出结论，即旧的日志条目已提交（例如，如果该条目存储在每个服务器上），但为了简单起见，Raft采取了更为保守的方法。
  • Raft在提交规则中增加了这种额外的复杂性，因为当领导者复制来自先前任期的条目时，日志条目保留其原始任期号。在其他一致性算法中，如果新领导者重新复制来自先前任期的条目，则必须使用其新的任期号进行复制。Raft的方法使得对日志条目进行推理更加容易，因为它们随着时间和日志的变化而保持相同的任期号。此外，在Raft中，新领导者从先前任期发送的日志条目比其他算法少（其他算法必须发送冗余的日志条目以重新编号它们，然后才能提交）。
5.4.3 安全性论证
  • 假设我们已经有了完整的Raft算法，现在我们可以更加精确地证明Leader Completeness Property的成立（这个证明基于安全性证明，请参见第9.2节）。我们假设Leader Completeness Property不成立，然后证明一个矛盾。假设在任期T中的领导者（leaderT）提交了一个日志条目，但是这个日志条目没有被某个未来任期的领导者存储。考虑最小的任期U > T，其领导者（leaderU）没有存储该条目。
    1. 在选举leaderU时，已提交的条目必须不在其日志中（领导者永远不会删除或覆盖条目）。
    2. leaderT在大多数集群中复制了该条目，并且leaderU收到了大多数集群的选票。因此，至少有一个服务器（“投票者”）既接受了来自leaderT的条目，又投票给了leaderU，如图9所示。投票者是达成矛盾的关键。
    3. 投票者必须在投票给leaderU之前从leaderT接受了提交的条目；否则，它将拒绝来自leaderT的AppendEntries请求（其当前任期将高于T）。
    4. 投票者在投票给leaderU时仍存储该条目，因为每个中间领导者都包含该条目（根据假设），领导者永远不会删除条目，而跟随者仅在与领导者冲突时删除条目。
    5. 投票者授予其选票给leaderU，因此leaderU的日志必须与投票者的日志一样最新。这导致了两个矛盾之一。
    6. 首先，如果投票者和leaderU共享相同的最后一个日志任期，则leaderU的日志必须至少与投票者的日志一样长，因此其日志包含投票者日志中的每个条目。这是一个矛盾，因为投票者包含已提交的条目，而leaderU则被假定没有。
    7. 否则，leaderU的最后一个日志任期必须大于投票者的。此外，它必须大于T，因为投票者的最后一个日志任期至少为T（它包含来自任期T的已提交条目）。创建leaderU的最后一个日志条目的早期领导者必须在其日志中包含已提交的条目（根据假设）。然后，根据日志匹配属性，leaderU的日志必须也包含已提交的条目，这是一个矛盾。
    8. 这完成了矛盾。因此，所有大于T的任期的领导者必须包含在T期间提交的所有已提交条目。
    9. 日志匹配属性保证未来的领导者也将包含间接提交的条目，例如图8（d）中的索引2。
  • 根据Leader Completeness Property，我们可以证明图3中的State Machine Safety Property，该属性指出，如果服务器已将日志条目应用于其状态机的给定索引，则不会有其他服务器为相同索引应用不同的日志条目。在服务器将日志条目应用于其状态机时，其日志必须与领导者的日志相同，直到该条目，并且该条目必须被提交。现在考虑任何服务器应用给定日志索引的最低任期；Log Completeness Property保证所有更高任期的领导者将存储相同的日志条目，因此在后续任期中应用索引的服务器将应用相同的值。因此，State Machine Safety Property成立。
  • 最后，Raft要求服务器按日志索引顺序应用条目。结合State Machine Safety Property，这意味着所有服务器将按相同的顺序将完全相同的日志条目应用于其状态机。
5.5 跟随者和候选人崩溃
  • 到目前为止，我们已经关注了领导者的故障。相比领导者的故障，跟随者和候选人的崩溃要简单得多，并且它们的处理方式相同。如果跟随者或候选人崩溃，则发送到它的未来的RequestVote和AppendEntries RPC将失败。Raft通过无限重试来处理这些故障；如果崩溃的服务器重新启动，则RPC将成功完成。如果服务器在完成RPC但在响应之前崩溃，则在重新启动后它将再次接收到相同的RPC。Raft的RPC是幂等的，因此这不会造成任何伤害。例如，如果跟随者收到一个包含其日志中已经存在的日志条目的AppendEntries请求，则它会在新请求中忽略这些条目。
5.6 时间和可用性
  • 我们对Raft的要求之一是，安全性不能依赖于时间：系统不能因为某些事件发生得比预期快或慢而产生不正确的结果。然而，可用性（系统及时响应客户的能力）必然取决于时间。例如，如果消息交换所需的时间比服务器崩溃之间的时间长，候选者将无法保持足够长的时间来赢得选举；没有稳定的领导者，Raft无法取得进展。
  • 领导者选举是Raft中时间最关键的方面。只要系统满足以下时间要求，Raft就能够选举并维护稳定的领导者：broadcastTime ≪ electionTimeout ≪ MTBF
  • 在这个不等式中，broadcastTime是一个服务器并行向集群中的每个服务器发送RPC并接收它们的响应所需的平均时间；electionTimeout是第5.2节中描述的选举超时时间；MTBF是单个服务器故障之间的平均时间。广播时间应该比选举超时时间小一个数量级，以便领导者可以可靠地发送心跳消息，以防止跟随者开始选举；考虑到选举超时使用的随机化方法，这个不等式也使得分裂投票的可能性很小。选举超时应该比MTBF小几个数量级，以便系统可以稳定地前进。当领导者崩溃时，系统将在大约选举超时时间内不可用；我们希望这只代表总时间的一小部分。
  • 广播时间和MTBF是底层系统的属性，而选举超时是我们必须选择的。Raft的RPC通常需要接收方将信息持久化到稳定存储中，因此广播时间可能在0.5毫秒到20毫秒之间，具体取决于存储技术。因此，选举超时很可能在10毫秒到500毫秒之间。典型的服务器MTBF为几个月或更长时间，这很容易满足时间要求。

6. 集群成员变更

  • 到目前为止，我们假设集群配置（参与一致性算法的服务器集合）是固定的。实际上，偶尔需要更改配置，例如在服务器故障时替换服务器或更改副本数量。虽然可以通过将整个集群脱机、更新配置文件，然后重新启动集群来完成此操作，但这将在更改期间使集群不可用。此外，如果有任何手动步骤，它们会存在操作员错误的风险。为了避免这些问题，我们决定自动化配置更改并将其纳入Raft一致性算法中。
  • 为了使配置更改机制安全，必须在整个过渡期间不存在两个领导者被选为同一任期的可能性。不幸的是，任何直接从旧配置切换到新配置的方法都是不安全的。不可能一次性原子地切换所有服务器，因此在过渡期间集群可能会分裂成两个独立的多数派（参见图10）。 10.jpg
    • 图10：直接从一种配置切换到另一种配置是不安全的，因为不同的服务器将在不同的时间切换。在这个例子中，集群从三个服务器增长到五个。不幸的是，在某个时间点上，可能会选举出两个不同的领导者，一个具有旧配置（Cold）的多数派，另一个具有新配置（Cnew）的多数派，它们的任期相同。
  • 为了确保安全，配置更改必须采用两阶段方法。有多种方法可以实现这两个阶段。例如，一些系统（例如[22]）使用第一阶段禁用旧配置，以便它无法处理客户端请求；然后第二阶段启用新配置。在Raft中，集群首先切换到我们称之为联合一致性的过渡配置；一旦联合一致性被提交，系统就会转换到新配置。联合一致性结合了旧配置和新配置：
    • 日志条目在两个配置中都被复制到所有服务器。
    • 任何一个配置中的服务器都可以作为领导者。
    • 达成协议（用于选举和条目提交）需要来自旧配置和新配置的分别多数。
  • 联合一致性允许单个服务器在不妨碍安全性的情况下在不同的时间之间进行配置转换。此外，联合一致性允许集群在配置更改期间继续为客户端请求提供服务。
  • 集群配置使用复制日志中的特殊条目进行存储和通信；图11说明了配置更改的过程。当领导者收到从Cold到Cnew的更改配置请求时，它将联合一致性的配置（在图中为Cold,new）作为日志条目存储并使用先前描述的机制复制该条目。一旦给定的服务器将新配置条目添加到其日志中，它将在所有未来的决策中使用该配置（服务器始终使用其日志中的最新配置，无论该条目是否已提交）。这意味着领导者将使用Cold,new的规则来确定Cold,new的日志条目何时被提交。如果领导者崩溃，则可能在Cold或Cold,new下选择新的领导者，具体取决于获胜的候选人是否已收到Cold,new。在此期间，Cnew不能做出单方面的决定。 11.jpg
    • 图11：配置更改的时间轴。虚线显示已创建但未提交的配置条目，实线显示最新提交的配置条目。领导者首先在其日志中创建Cold,new配置条目并将其提交给Cold,new（Cold的大多数和Cnew的大多数）。然后它创建Cnew条目并将其提交给Cnew的大多数。在任何时候，Cold和Cnew都不能独立做出决策。
  • 一旦Cold,new已提交，Cold和Cnew都不能在未经对方批准的情况下做出决策，而Leader Completeness Property确保只有具有Cold,new日志条目的服务器才能被选为领导者。现在，领导者可以安全地创建描述Cnew的日志条目并将其复制到集群中。同样，只要看到它，这个配置将在每个服务器上生效。当新配置根据Cnew的规则提交时，旧配置将变得无关紧要，不在新配置中的服务器可以关闭。如图11所示，Cold和Cnew没有时间可以做出单方面的决策；这保证了安全性。
  • 重新配置还需要解决三个问题。第一个问题是新服务器最初可能不会存储任何日志条目。如果它们以这种状态添加到集群中，可能需要相当长的时间才能追赶上来，在此期间可能无法提交新的日志条目。为了避免可用性间隙，Raft在配置更改之前引入了一个额外的阶段，在此阶段中，新服务器作为非投票成员加入集群（领导者将日志条目复制到它们，但它们不被视为多数）。一旦新服务器赶上了集群的其他部分，就可以按照上述描述进行重新配置。
  • 第二个问题是集群领导者可能不是新配置的一部分。在这种情况下，领导者在提交Cnew日志条目后步下（返回到跟随者状态）。这意味着在提交Cnew时会有一段时间（当时它正在管理不包括自己的集群）；它复制日志条目但不计入多数。领导者的转换发生在提交Cnew时，因为这是新配置可以独立运行的第一个点（始终可以从Cnew中选择领导者）。在此之前，可能只有来自Cold的服务器可以被选为领导者。
  • 第三个问题是已删除的服务器（不在Cnew中）可能会破坏集群。这些服务器将不会接收到心跳信号，因此它们将超时并开始新的选举。然后，它们将使用新的任期号发送RequestVote RPC，这将导致当前领导者返回到跟随者状态。最终将选举出一个新的领导者，但已删除的服务器将再次超时，这个过程将重复，导致可用性差。
  • 为了防止这个问题，当服务器认为当前存在领导者时，它们会忽略RequestVote RPC。具体来说，如果一个服务器在最小选举超时时间内收到一个RequestVote RPC，它不会更新其任期或授予其投票。这不会影响正常的选举，每个服务器在开始选举之前都会等待至少最小选举超时时间。然而，它有助于避免已删除的服务器引起的干扰：如果一个领导者能够向其集群发送心跳信号，那么它将不会被更大的任期号所推翻。

7. 日志压缩

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

8. 客户端交互

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

9. 实施与评估

  • 我们已经将Raft实现为复制状态机的一部分，该状态机存储RAMCloud [33]的配置信息，并协助RAMCloud协调器的故障转移。Raft实现包含大约2000行C++代码，不包括测试、注释或空行。源代码可自由获取[23]。还有大约25个独立的第三方开源Raft实现[34]处于不同的开发阶段，基于本文的草案。此外，各种公司正在部署基于Raft的系统[34]。
  • 本节的其余部分使用三个标准来评估Raft：可理解性、正确性和性能。
9.1 易理解性
  • 为了衡量Raft相对于Paxos的可理解性，我们进行了一项实验研究，使用斯坦福大学的高年级本科生和研究生的高级操作系统课程以及加州大学伯克利分校的分布式计算课程。我们录制了Raft和Paxos的视频讲座，并创建了相应的测验。Raft讲座涵盖了本文的内容，但不包括日志压缩；Paxos讲座涵盖了足够的材料来创建一个等效的复制状态机，包括单决策Paxos、多决策Paxos、重新配置以及实践中需要的一些优化（如领导者选举）。测验测试了算法的基本理解，并要求学生推理边角情况。每个学生观看一个视频，参加相应的测验，观看第二个视频，参加第二个测验。约一半的参与者首先进行了Paxos部分，另一半首先进行了Raft部分，以考虑个体差异和从研究的第一部分获得的经验。我们比较了每个测验的参与者得分，以确定参与者是否对Raft有更好的理解。
  • 我们试图尽可能公平地比较Paxos和Raft。实验在两个方面有利于Paxos：43名参与者中有15名报告有一些先前的Paxos经验，而Paxos视频比Raft视频长14%。如表1所总结的，我们已经采取措施来减轻潜在的偏见来源。我们所有的材料都可以供审查[28，31]。
  • 表格1：可能存在偏见反对Paxos的研究的关注点，采取的对策以及可用的额外材料。
项目 为减少偏见而采取的措施 审查材料 [28, 31] 同等的授课质量 同一位讲师授课。Paxos讲座基于并改进了多个大学使用的现有材料。Paxos讲座的长度比原讲座长14%。 视频 同等的测验难度 问题按难度分组，并在考试中成对出现。 测验 公平评分 使用评分表进行评分，并随机交替评分不同的测验。 评分表
  • 平均而言，参与者在Raft测验上的得分比Paxos测验高4.9分（满分60分，Raft平均得分为25.7分，Paxos平均得分为20.8分）；图14显示了他们的个人得分。成对t检验表明，在95％的置信水平下，Raft得分的真实分布至少比Paxos得分的真实分布高2.5分。 14.jpg
    • 图14：比较43名参与者在Raft和Paxos测验中的表现的散点图。在对角线（33）上方的点表示在Raft测验中得分更高的参与者。
  • 我们还创建了一个线性回归模型，根据三个因素预测新学生的测验成绩：他们参加的测验，他们之前的Paxos经验程度以及他们学习算法的顺序。该模型预测，选择测验会产生12.5分的差异，有利于Raft。这比观察到的4.9分差异显著高，因为许多实际学生具有先前的Paxos经验，这对Paxos有很大帮助，而对Raft的帮助略微较少。有趣的是，该模型还预测，已经参加了Paxos测验的人Raft的得分会低6.3分；虽然我们不知道原因，但这似乎是具有统计学意义的。
  • 我们还在测验后对参与者进行了调查，以了解他们认为哪种算法更容易实现或解释；这些结果显示在图15中。绝大多数参与者报告说Raft更容易实现和解释（每个问题的41个参与者中有33个）。然而，这些自我报告的感受可能不如参与者的测验成绩可靠，参与者可能会受到我们的假设影响，即Raft更容易理解。 15.jpg
    • 图15：使用5分制，参与者被问及（左）哪个算法在一个功能齐全、正确、高效的系统中更容易实现，以及（右）哪个算法更容易向计算机科学研究生解释。
  • Raft用户研究的详细讨论可在[31]中找到。
9.2 正确性
  • 我们已经开发了一个正式的规范和安全证明，用于描述第5节中描述的一致性机制。正式规范[31]使用TLA+规范语言使图2中总结的信息完全精确。它大约有400行，作为证明的主题。对于任何实现Raft的人来说，它本身也是有用的。我们已经使用TLA证明系统[7]机械地证明了日志完整性属性。然而，这个证明依赖于尚未机械检查的不变量（例如，我们尚未证明规范的类型安全性）。此外，我们已经编写了一个非正式的证明[31]，证明了状态机安全属性，它是完整的（仅依赖于规范）和相对精确的（大约有3500个单词）。
9.3 性能
  • Raft算法的性能与Paxos等其他一致性算法相似。性能最重要的情况是当已建立的领导者正在复制新的日志条目时。Raft通过使用最少的消息（从领导者到一半的集群的单个往返）来实现这一点。还可以进一步改进Raft的性能。例如，它可以轻松支持批处理和流水线请求，以实现更高的吞吐量和更低的延迟。文献中提出了各种优化算法的方法，其中许多可以应用于Raft，但我们将这留给未来的工作。
  • 我们使用我们的Raft实现来测量Raft的领导者选举算法的性能，并回答两个问题。首先，选举过程是否快速收敛？其次，在领导者崩溃后可以实现的最短停机时间是多少？
  • 为了测量领导者选举，我们反复崩溃了一个由五个服务器组成的集群的领导者，并计时检测崩溃并选举新领导者所需的时间（见图16）。为了生成最坏情况，每个试验中的服务器具有不同的日志长度，因此有些候选人不符合成为领导者的条件。此外，为了鼓励分裂投票，我们的测试脚本在终止进程之前触发了来自领导者的心跳RPC的同步广播（这近似于领导者在崩溃之前复制新的日志条目的行为）。领导者在其心跳间隔内均匀随机崩溃，该间隔为所有测试的最小选举超时的一半。因此，最小可能的停机时间约为最小选举超时的一半。 16.jpg
    • 图16：检测和替换崩溃领导者所需的时间。顶部图表变化选举超时的随机性，底部图表缩放最小选举超时。每条线代表1000次试验（除了“150-150ms”的100次试验），对应于特定的选举超时选择；例如，“150-155ms”表示选举超时在150ms和155ms之间随机均匀选择。这些测量是在具有大约15ms广播时间的五个服务器的集群上进行的。九个服务器的集群的结果类似。
  • 图16中的顶部图表显示，选举超时的少量随机化足以避免选举中的分裂投票。在没有随机性的情况下，由于许多分裂投票，领导者选举在我们的测试中始终需要超过10秒的时间。只需添加5ms的随机性即可显着改善，导致中位停机时间为287ms。使用更多的随机性可以改善最坏情况的行为：使用50ms的随机性，最坏完成时间（在1000次试验中）为513ms。
  • 图16中的底部图表显示，通过减少选举超时可以减少停机时间。使用12-24ms的选举超时，平均只需要35ms就可以选举出领导者（最长的试验需要152ms）。然而，将超时时间降低到这个点以下会违反Raft的时间要求：领导者在其他服务器开始新的选举之前难以广播心跳。这可能会导致不必要的领导者更改并降低整个系统的可用性。我们建议使用保守的选举超时，例如150-300ms；这样的超时不太可能导致不必要的领导者更改，并且仍将提供良好的可用性。

10. 相关工作

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

11. 结论

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

12. 致谢

  • 本研究的用户研究得到了Ali Ghodsi、David Mazieres以及伯克利大学CS 294-91和斯坦福大学CS 240的学生的支持。Scott Klemmer帮助我们设计了用户研究，Nelson Ray为我们提供了统计分析方面的建议。用户研究中的Paxos幻灯片大量借鉴了Lorenzo Alvisi最初创建的幻灯片。特别感谢David Mazieres和Ezra Hoch在Raft中发现了微妙的错误。许多人对论文和用户研究材料提供了有益的反馈，包括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、Nicolas Schiper、Deian Stefan、Andrew Stone、Ryan Stutsman、David Terei、Stephen Yang、Matei Zaharia、24位匿名会议评审人（有重复），特别是我们的指导Eddie Kohler。Werner Vogels在推特上发布了早期草稿的链接，为Raft带来了重要的曝光。本研究得到了Gigascale Systems Research Center和Multiscale Systems Center的支持，这是半导体研究公司计划下资助的六个研究中心之一，得到了由MARCO和DARPA赞助的半导体研究公司计划STARnet的支持，得到了国家科学基金会的0963859号资助，以及来自Facebook、Google、Mellanox、NEC、NetApp、SAP和Samsung的资助。Diego Ongaro得到了The Junglee Corporation Stanford Graduate 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 looselycoupled distributed systems. In Proc. OSDI’06, Symposium 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 Symposium 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., KANTHAK, 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 Implementation (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. M´ery, Eds., vol. 7436 of Lecture 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 faulttolerant 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 Transactions on Programming Languages and Systems 12 (July 1990), 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 Conference (2010), USENIX, pp. 145–158.
  • [12] JUNQUEIRA, F. P., REED, B. C., AND SERAFINI, M. Zab: High-performance broadcast for primary-backup systems. In Proc. DSN’11, IEEE/IFIP Int’l Conf. on Dependable 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 Transactions on Computer Systems 16, 2 (May 1998), 133–169.
  • [16] LAMPORT, L. Paxos made simple. ACM SIGACT News 32, 4 (Dec. 2001), 18–25.
  • [17] LAMPORT, L. Specifying Systems, The TLA+ Language and Tools for Hardware and Software Engineers. AddisonWesley, 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 replication 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. EuroSys’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] MAZIERES ` , 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 Informatica 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., MAZIERES ` , D., MITRA, S., NARAYANAN, A., ONGARO, D., PARULKAR, G., ROSENBLUM, M., RUMBLE, S. M., STRATMANN, E., AND STUTSMAN, R. The case for RAMCloud. Communications 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 Computing 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 Systems and Technologies (2010), IEEE Computer Society, pp. 1–10.
  • [39] VAN RENESSE, R. Paxos made moderately complex. Tech. rep., Cornell University, 2012.