Diego Ongaro and John Ousterhout
Stanford University

摘要

Raft 是一种用于管理复制日志的共识算法。它能够产生与(多)Paxos 相同的结果，并且效率与 Paxos 相当，但其结构与 Paxos 不同。这种结构上的差异使得 Raft 比 Paxos 更容易理解，同时也为构建实际系统提供了更好的基础。为了提升可理解性，Raft 将共识的关键要素进行了分离，如领导者选举、日志复制和安全性保证等，并且强化了一致性要求以减少需要考虑的状态数量。用户研究的结果表明，相比 Paxos，学生们更容易掌握 Raft。此外，Raft 还引入了一种新的集群成员变更机制，该机制通过使用重叠的多数派来保证安全性。

1 引言

共识算法使得一组机器能够作为一个连贯的整体工作，并且能够在部分成员发生故障时继续运行。正因如此，这类算法在构建可靠的大规模软件系统中发挥着关键作用。在过去的十年里，Paxos1 2主导了关于共识算法的讨论：大多数共识算法的实现要么基于 Paxos，要么受到它的影响，而且 Paxos 已经成为向学生教授共识知识的主要载体。

不幸的是，尽管已经有许多让它变得更容易理解的尝试，Paxos 仍然非常难以理解。此外，它的架构需要进行复杂的改动才能支持实际系统。因此，系统构建者和学生都在与 Paxos 作斗争。

在我们自己也经历过与 Paxos 搏斗之后，我们着手寻找一种新的共识算法，希望它能为系统构建和教育提供更好的基础。我们采用了一种不同寻常的方式，即将 可理解性（understandability） 作为首要目标：我们能否定义一个用于实际系统的共识算法，并以一种比 Paxos 容易得多的方式来描述它？此外，我们希望这个算法能够帮助系统构建者形成必要的直观认识。重要的不仅是算法能够工作，更重要的是能够清楚地理解为什么它能工作。

这项工作的成果就是一个称为 Raft 的共识算法。在设计 Raft 时，我们应用了特定的技术来提高可理解性，包括分解（Raft 将领导者选举、日志复制和安全性分开）和状态空间简化（相比 Paxos，Raft 减少了不确定性的程度以及服务器之间可能产生不一致的方式）。在两所大学进行的涉及 43 名学生的用户研究表明，Raft 比 Paxos 更容易理解:在学习了这两种算法之后，其中 33 名学生对 Raft 的相关问题回答得比 Paxos 的问题要好。

Raft 在许多方面与现有的共识算法相似（最值得注意的是 Oki 和 Liskov 的 Viewstamped Replication 3 4），但它有几个新颖的特点：

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

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

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

2 复制状态机

Figure 1

共识算法通常出现在 复制状态机（replicated state machines） 的背景下5。在这种方法中，一组服务器上的状态机计算相同状态的相同副本，即使某些服务器宕机也能继续运行。复制状态机用于解决分布式系统中的各种容错问题。例如，具有单个集群领导者的大规模系统，如 GFS6、HDFS7 和 RAMCloud8，通常使用单独的复制状态机来管理领导者选举并存储必须在领导者崩溃时存活的配置信息。复制状态机的例子包括 Chubby9 和 ZooKeeper10。

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

保持复制日志一致是共识算法的任务。服务器上的共识模块从客户端接收命令并将其添加到日志中。它与其他服务器上的共识模块通信，以确保每个日志最终包含相同顺序的相同请求，即使某些服务器发生故障。一旦命令被正确复制，每个服务器的状态机按日志顺序处理它们，并将输出返回给客户端。因此，服务器看起来像是形成了一个高度可靠的状态机。

实际系统的共识算法通常具有以下属性：

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

3 Paxos有什么问题？

在过去的十年中，Leslie Lamport 的 Paxos 协议几乎成了共识的代名词：它是课程中最常教授的协议1，大多数共识实现也以它为起点。Paxos 首先定义了一个能够就单一决策（如单个复制日志条目）达成一致的协议，我们称之为 单一决策 Paxos（single-decree Paxos）。然后，Paxos 结合该协议的多个实例来促进一系列决策，如日志（多决策 Paxos（multi-Paxos））。Paxos 确保了安全性和活性，并支持集群成员的变更。其正确性已被证明，在正常情况下也很高效。

不幸的是，Paxos 有两个显著的缺点。第一个缺点是 Paxos 极其难以理解。完整的解释1非常晦涩，极少有人能理解它，而且需要付出极大的努力。因此，有几次尝试用更简单的术语2 11 12来解释 Paxos，但这些解释仍然具有挑战性。在 2012 年 NSDI 会议的非正式调查中，我们发现即使在经验丰富的研究人员中，也很少有人对 Paxos 感到舒适。我们自己也在与 Paxos 斗争；直到阅读了几篇简化的解释并设计了我们自己的替代协议后，我们才理解了完整的协议，这个过程花费了将近一年的时间。

我们假设 Paxos 的晦涩难懂源于其选择了单一决策子集作为基础。单一决策 Paxos 非常密集且微妙：它分为两个阶段，这两个阶段没有简单直观的解释，且不能独立理解。因此，很难形成关于为什么单一决策协议有效的直觉。多决策 Paxos 的组合规则显著增加了额外的复杂性和微妙性。我们认为，达成多个决策共识的整体问题（即日志而不是单个条目）可以通过其他更直接和明显的方式来分解。

Paxos 的第二个问题是它没有为构建实际实现提供良好的基础。一个原因是没有广泛认可的多决策 Paxos 算法。Lamport 的描述主要是关于单一决策 Paxos；他勾画了多决策 Paxos 的可能方法，但缺少许多细节。有几次尝试充实和优化 Paxos，例如13，14和15，但这些尝试彼此之间以及与 Lamport 的草图都有所不同。像 Chubby16 这样的系统实现了类似 Paxos 的算法，但在大多数情况下，它们的细节没有被公布。

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

因此，实际系统与 Paxos 几乎没有相似之处。每个实现都从 Paxos 开始，发现实现它的困难，然后开发出一个显著不同的架构。这既耗时又容易出错，而理解 Paxos 的困难加剧了这个问题。Paxos 的形式化可能是一个证明其正确性的好方法，但实际实现与 Paxos 相差甚远，以至于这些证明几乎没有价值。以下是 Chubby 实现者的典型评论：

Paxos 算法的描述与实际系统的需求之间存在重大差距…最终系统将基于未经证实的协议 16。

由于这些问题，我们得出结论，Paxos 没有为系统建设或教育提供良好的基础。鉴于共识在大规模软件系统中的重要性，我们决定看看是否可以设计一种比 Paxos 具有更好特性的替代共识算法。Raft 是该实验的结果。

4 为可理解性而设计

我们在设计 Raft 时有几个目标：它必须为系统构建提供一个完整且实用的基础，从而显著减少开发人员所需的设计工作量；它必须在所有条件下都是安全的，并且在典型的操作条件下是可用的；它必须对常见操作高效。但我们最重要的目标——也是最困难的挑战——是 可理解性（understandability）。必须让广大受众能够轻松理解该算法。此外，必须能够对该算法形成直觉，以便系统构建者在实际实现中进行不可避免的扩展。

在 Raft 的设计中，我们不得不在多种替代方法之间进行选择。在这些情况下，我们基于可理解性来评估替代方案：解释每种替代方案有多难（例如，其状态空间有多复杂，是否有微妙的影响？），以及读者完全理解该方法及其影响有多容易？

我们认识到这种分析具有高度的主观性；尽管如此，我们使用了两种普遍适用的技术。第一种技术是众所周知的问题分解方法：在可能的情况下，我们将问题分解成可以相对独立地解决、解释和理解的部分。例如，在 Raft 中，我们将领导者选举、日志复制、安全性和成员变更分开。

我们的第二种方法是通过减少需要考虑的状态数量来简化状态空间，使系统更加一致，并尽可能消除不确定性。具体来说，不允许日志有空洞，并且 Raft 限制了日志之间变得不一致的方式。尽管在大多数情况下我们试图消除不确定性，但在某些情况下，不确定性实际上提高了可理解性。特别是，随机化方法引入了不确定性，但它们倾向于通过以类似方式处理所有可能的选择来减少状态空间（“选择任何一个；这无关紧要”）。我们使用随机化来简化 Raft 的领导者选举算法。

5 Raft 共识算法

Figure 2
图 2：Raft 共识算法的精简摘要（不包括成员资格更改和日志压缩）。左上角框中的服务器行为描述为一组独立且重复触发的规则。节编号（如 §5.2）表示讨论特定功能的位置。正式规范 [^31] 更精确地描述了该算法。

Figure 3
State
所有服务器上的持久性状态（在响应 RPC 之前更新稳定存储）currentTerm服务器见过的最新任期（首次启动时初始化为 0，单调增加）
votedFor在当前任期内获得投票的候选者的ID（如果没有则为 null）
log[]日志条目；每个条目包含状态机命令以及领导者收到条目时的任期（第一个索引为 1）
所有服务器上的易失状态commitIndex已知已提交的最高日志条目的索引（初始化为 0，单调增加）
lastApplied应用于状态机的最高日志条目的索引（初始化为 0，单调增加）
领导者服务器上的易失状态（选举后重新初始化）nextIndex[]对于每个服务器，发送到该服务器的下一个日志条目的索引（初始化为领导者最后一个日志索引 + 1）
matchIndex[]对于每个服务器，已知在服务器上复制的最高日志条目的索引（初始化为 0，单调增加）
AppendEntries RPC
由领导者调用来复制日志条目（§5.3）；也用作心跳（§5.2）。
参数：term领导者的任期
learderID这样跟随者就可以重定向客户端
prevLogIndex紧邻新日志条目之前的日志条目的索引
prevLogTermprevLogIndex条目的任期
entries[]要存储的日志条目（心跳为空；为了提高效率，可以发送多个条目）
leaderCommit领导者的 commitIndex
结果：termcurrentTerm，用于领导者自我更新
success如果跟随者包含与 prevLogIndex 和 prevLogTerm 匹配的条目，则为 true
接收者实现：
  1. 如果 term < currentTerm 就返回 false
  2. 如果日志在 prevLogIndex 处不匹配，则返回 false
  3. 如果现有条目与新条目冲突（索引相同但任期不同），则删除现有条目及其后的所有条目
  4. 附加日志中尚未存在的任何新条目
  5. 如果 leaderCommit > commitIndex，将 commitIndex 设置为 leaderCommit 和新条目索引的较小值
RequestVote RPC
由候选者调用来收集选票（§5.2）。
参数：term候选者的任期
candidateID正在请求投票的候选者
lastLogIndex候选者最后一个日志条目的索引（§5.4）
lastLogTerm候选者最后一次日志条目的任期（§5.4）
结果：termcurrentTerm，供候选者自行更新
voteGrantedtrue 表示候选者获得选票
接收者实现：
  1. 如果 term < currentTerm 就返回 false
  2. 如果 votedFor 为空或为 candidateId，并且候选者的日志至少和接收者一样新，就投票给候选者（§5.2, §5.4）
Rules for Servers
所有服务器：
  • 如果 commitIndex > lastApplied：增加 lastApplied，将 log[lastApplied] 应用到状态机（§5.3）
  • 如果RPC请求或响应包含的任期 T > currentTerm：设置currentTerm = T，转换为跟随者（§5.1）。
跟随者（§5.2）:
  • 回应候选者和领导者的 RPC
  • 如果选举超时后没有收到来自当前领导者的 AppendEntries RPC 或向候选者授予投票：转换为候选者
候选者（§5.2）:
  • 转换为候选者后，开始选举：
    • 增加 currentTerm
    • 为自己投票
    • 重置选举计时器
    • 向所有其他服务器发送 RequestVote RPC
  • 如果从大多数服务器收到选票：成为领导者
  • 如果从新领导者收到 AppendEntries RPC：转换为跟随者
  • 如果选举超时：开始新的选举
领导者：
  • 当选后：向每个服务器发送初始的空 AppendEntries RPC（心跳）；在空闲期间重复以防止选举超时（§5.2）
  • 如果从客户端收到命令：将条目附加到本地日志，在条目应用到状态机后响应（§5.3）
  • 如果 lastLogIndex ≥ 跟随者的 nextIndex：发送包含从 nextIndex 开始的日志条目的 AppendEntries RPC
    • 如果成功：更新跟随者的 nextIndex 和 matchIndex（§5.3）
    • 如果 AppendEntries 因日志不一致而失败：递减 nextIndex 并重试（§5.3）
  • 如果存在一个 N 使得 N > commitIndex，且大多数 matchIndex[i] ≥ N，并且 log[N].term == currentTerm：设置 commitIndex = N（§5.3，§5.4）。
选举安全性在给定任期内最多只能选举出一个领导者。(§5.2)
领导者仅追加领导者从不覆盖或删除其日志中的条目；它只追加新的条目。(§5.3)
日志匹配如果两个日志包含一个具有相同索引和任期的条目，那么这两个日志在该索引之前的所有条目都是相同的。(§5.3)
领导者完整性如果一个日志条目在某个任期内被提交，那么该条目将出现在所有更高任期号的领导者的日志中。(§5.4)
状态机安全性如果某个服务器已经将某个特定索引位置的日志条目应用到其状态机中，那么其他服务器永远不会在相同的索引位置应用不同的日志条目。(§5.4.3)

Raft 是一种用于管理复制日志的算法，如第2节所述。图2简要总结了该算法以供参考，图3列出了该算法的关键属性；这些图中的元素将在本节的其余部分逐一讨论。

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

鉴于领导者的方法，Raft 将共识问题分解为三个相对独立的子问题，这些子问题将在以下小节中讨论：

  • 领导者选举：当现有领导者失效时，必须选择一个新的领导者（第5.2节）。
  • 日志复制：领导者必须接受来自客户端的日志条目并将它们复制到整个集群中，强制其他日志与其自身一致（第5.3节）。
  • 安全性：Raft 的关键安全属性是图3中的状态机安全属性：如果任何服务器已将特定日志条目应用到其状态机，则其他服务器不得为相同的日志索引应用不同的命令。第5.4节描述了 Raft 如何确保这一属性；解决方案涉及对第5.2节中描述的选举机制的额外限制。

在介绍了共识算法之后，本节讨论了可用性问题以及时间在系统中的作用。

5.1 Raft 基础

Figure 4
图 4：服务器状态。跟随者仅响应来自其他服务器的请求。如果跟随者没有收到任何通信，它将成为候选者并发起选举。获得整个群集中大多数选票的候选者将成为新的领导者。领导者通常会一直工作到失败。

一个 Raft 集群包含多个服务器；五个是一个典型的数量，这允许系统容忍两个故障。在任何给定时间，每个服务器处于三种状态之一：领导者（leader）、跟随者（follower）或候选者（candidate）。在正常操作中，恰好有一个领导者，所有其他服务器都是跟随者。跟随者是被动的：它们不主动发出请求，只是响应来自领导者和候选者的请求。领导者处理所有客户端请求（如果客户端联系跟随者，跟随者会将其重定向到领导者）。第三种状态，候选者，用于选举新领导者，如第5.2节所述。图4显示了状态及其转换；转换将在下文讨论。

Figure 5
图 5：时间分为多个任期，每个任期都从一次选举开始。选举成功后，单个 leader 将管理集群，直到任期结束。一些选举失败，在这种情况下，任期结束，没有选择领导者。任期之间的转换可能会在不同时间在不同的服务器上观察到。

Raft 将时间划分为任意长度的 任期（term），如图5所示。任期用连续的整数编号。每个任期以 选举（election） 开始，其中一个或多个候选者尝试成为领导者，如第5.2节所述。如果候选者赢得选举，那么它将在剩余的任期内担任领导者。在某些情况下，选举会导致票数平分。在这种情况下，任期将以没有领导者结束；一个新的任期（伴随新的选举）将很快开始。Raft 确保在给定的任期内最多只有一个领导者。

不同的服务器可能在不同时间观察到任期之间的转换，在某些情况下，服务器可能不会观察到选举甚至整个任期。任期在 Raft 中充当逻辑时钟17，它们允许服务器检测过时的信息，如过期的领导者。每个服务器存储一个 当前任期（current term） 号，该任期号随时间单调递增。每当服务器通信时，当前任期号都会交换；如果一个服务器的当前任期号小于另一个服务器的任期号，它会将其当前任期号更新为较大的值。如果候选者或领导者发现其任期过期，它会立即恢复为跟随者状态。如果服务器收到带有过期任期号的请求，它会拒绝该请求。

Raft 服务器使用远程过程调用（RPC）进行通信，基本的共识算法只需要两种类型的 RPC。RequestVote RPC 由候选者在选举期间发起（第5.2节），AppendEntries RPC 由领导者发起以复制日志条目并提供心跳（第5.3节）。第7节增加了第三种用于在服务器之间传输快照的 RPC。如果服务器没有及时收到响应，它们会重试 RPC，并且为了最佳性能，它们会并行发出 RPC。

5.2 领导者选举

Raft 使用心跳机制来触发领导者选举。当服务器启动时，它们首先作为跟随者。只要从领导者或候选者那里接收到有效的 RPC，服务器就会保持在跟随者状态。领导者定期向所有跟随者发送心跳（不携带日志条目的 AppendEntries RPC）以维持其权威。如果跟随者在一段时间内（称为 选举超时（election timeout））没有收到任何通信，它就会假设没有可行的领导者，并开始选举以选择新的领导者。

要开始选举，跟随者会增加其当前任期并转换为候选者状态。然后，它会为自己投票，并并行向集群中的其他服务器发出 RequestVote RPC。候选者会继续保持在这种状态，直到发生以下三种情况之一：（a）它赢得选举，（b）另一台服务器确立自己为领导者，或（c）经过一段时间没有赢家。以下段落将分别讨论这些结果。

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

在等待投票期间，候选者可能会收到来自另一台服务器的 AppendEntries RPC，该服务器声称自己是领导者。如果领导者的任期（包含在其 RPC 中）至少与候选者的当前任期一样大，那么候选者会承认该领导者的合法性并返回到跟随者状态。如果 RPC 中的任期小于候选者的当前任期，那么候选者会拒绝该 RPC 并继续保持候选者状态。

第三种可能的结果是候选者既没有赢得也没有输掉选举：如果许多跟随者同时成为候选者，投票可能会分裂，以至于没有候选者获得多数票。当这种情况发生时，每个候选者都会超时并通过增加其任期并启动新一轮的 RequestVote RPC 来开始新的选举。然而，如果没有额外的措施，分裂投票可能会无限期地重复。

Raft 使用随机化的选举超时来确保分裂投票很少发生并能迅速解决。为了防止分裂投票，选举超时从一个固定的区间（例如 150-300 毫秒）中随机选择。这使得服务器的超时分散开来，在大多数情况下，只有一个服务器会超时；它赢得选举并在其他服务器超时之前发送心跳。相同的机制用于处理分裂投票。每个候选者在选举开始时重新启动其随机化的选举超时，并等待该超时结束后再开始下一次选举；这减少了新选举中再次发生分裂投票的可能性。第9.3节表明这种方法能够快速选出领导者。

选举是一个例子，说明了可理解性如何指导我们在设计替代方案之间做出选择。最初，我们计划使用一个排名系统：每个候选者被分配一个唯一的排名，用于在竞争候选者之间进行选择。如果一个候选者发现另一个排名更高的候选者，它会返回到跟随者状态，以便排名更高的候选者更容易赢得下一次选举。我们发现这种方法在可用性方面产生了微妙的问题（如果排名较高的服务器失败，排名较低的服务器可能需要超时并再次成为候选者，但如果它太早这样做，可能会重置选举领导者的进程）。我们多次调整了算法，但每次调整后都会出现新的边缘情况。最终，我们得出结论，随机重试的方法更明显且更易理解。

5.3 日志复制

Figure 6

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

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

领导者决定何时将日志条目安全地应用到状态机；这样的条目称为 已提交（commited） 条目。Raft 保证已提交的条目是持久的，并且最终会被所有可用的状态机执行。一个日志条目一旦被创建它的领导者在大多数服务器上复制，就被认为是已提交的（例如，图6中的条目7）。这也会提交领导者日志中的所有前面的条目，包括以前领导者创建的条目。第5.4节讨论了在领导者更换后应用此规则时的一些细微差别，并且还表明这种提交定义是安全的。领导者跟踪它知道的最高已提交索引，并在未来的 AppendEntries RPC（包括心跳）中包含该索引，以便其他服务器最终得知。一旦跟随者得知一个日志条目已提交，它就会将该条目按日志顺序应用到其本地状态机。

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

  • 如果不同日志中的两个条目具有相同的索引和任期号，那么它们存储相同的命令。
  • 如果不同日志中的两个条目具有相同的索引和任期号，那么这些日志在所有前面的条目中都是相同的。

第一个属性源于这样一个事实：领导者在给定任期内最多创建一个具有给定日志索引的条目，并且日志条目在日志中的位置永远不会改变。第二个属性通过 AppendEntries 执行的简单一致性检查来保证。当发送 AppendEntries RPC 时，领导者会包含其日志中紧接在新条目之前的条目的索引和任期号。如果跟随者在其日志中没有找到具有相同索引和任期号的条目，那么它会拒绝新的条目。这个一致性检查起到了归纳步骤的作用：日志的初始空状态满足日志匹配属性，并且一致性检查在日志扩展时保持日志匹配属性。因此，每当 AppendEntries 成功返回时，领导者知道跟随者的日志与其自身日志在新条目之前是相同的。

Figure 7

在正常操作期间，领导者和跟随者的日志保持一致，因此 AppendEntries 的一致性检查从未失败。然而，领导者崩溃可能会导致日志不一致（旧领导者可能没有完全复制其日志中的所有条目）。这些不一致可能会在一系列领导者和跟随者崩溃中加剧。图7说明了跟随者的日志可能与新领导者的日志不同的方式。跟随者可能缺少领导者上存在的条目，可能有领导者上不存在的额外条目，或者两者都有。日志中的缺失和多余条目可能跨越多个任期。

在 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中的领导者完整性属性）。在给定选举限制的情况下，我们将提交规则更加精确化。最后，我们提供领导者完整性属性的证明草图，并展示它如何导致复制状态机的正确行为。

5.4.1 选举限制

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

Raft 使用投票过程来防止候选者在其日志不包含所有已提交条目的情况下赢得选举。候选者必须联系集群中的大多数服务器才能当选，这意味着每个已提交的条目必须至少存在于这些服务器中的一个。如果候选者的日志至少和大多数服务器中的任何一个日志一样新（“最新”的定义如下），那么它将包含所有已提交的条目。RequestVote RPC 实现了这一限制：RPC 包含关于候选者日志的信息，如果投票者的日志比候选者的日志更新，它将拒绝投票。

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

5.4.2 提交来自先前任期的条目

Figure 8
图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无法赢得选举，因为日志不完整）。此时，日志中所有先前的条目也都被提交。

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

为了消除图8中类似的问题，Raft 从不通过计算副本数来提交前一个任期的日志条目。只有领导者当前任期的日志条目通过计算副本数来提交；一旦当前任期的条目以这种方式提交，那么由于日志匹配属性，所有之前的条目也间接提交。有些情况下，领导者可以安全地得出结论，认为旧的日志条目已提交（例如，如果该条目存储在每个服务器上），但为了简化，Raft 采取了更保守的方法。

Raft 在提交规则中引入了额外的复杂性，因为当领导者复制前一个任期的条目时，日志条目保留其原始的任期号。在其他共识算法中，如果新领导者重新复制前一个“任期”的条目，它必须使用其新的“任期号”来进行复制。Raft 的方法使得推理日志条目更容易，因为它们在时间和日志之间保持相同的任期号。此外，Raft 中的新领导者发送的前一个任期的日志条目比其他算法少（其他算法必须发送冗余的日志条目以重新编号，然后才能提交它们）。

5.4.3 安全性论证

Figure 9
图 9：如果 S1（任期 T 的领导者）在其任期中提交新的日志条目，并且 S5 被选为后续任期 U 的领导者，则必须至少有一个服务器 （S3） 接受日志条目并投票支持 S5。

给定完整的 Raft 算法，我们现在可以更精确地论证 Leader 完备性属性成立（该论证基于安全性证明；参见第 9.2 节）。我们假设 Leader 完备性属性不成立，然后我们证明矛盾。假设任期 T 的领导者（$leader_T$）提交了其任期内的日志条目，但该日志条目未被某个未来任期的领导者存储。考虑最小任期 U > T，其领导者（$leader_U$）不存储该条目。

  1. 已提交的条目在 $leader_U$ 当选时必须不存在于其日志中（领导者从不删除或覆盖条目）。
  2. $leader_T$ 在集群的大多数服务器上复制了该条目，而 $leader_U$ 获得了集群大多数服务器的投票。因此，至少有一台服务器（“投票者”）既接受了 $leader_T$ 的条目又投票给了 $leader_U$，如图9所示。投票者是得出矛盾的关键。
  3. 投票者必须在投票给 $leader_U$ 之前接受了 $leader_T$ 的已提交条目；否则，它会拒绝 $leader_T$ 的 AppendEntries 请求（其当前任期会高于 T）。
  4. 投票者在投票给 $leader_U$ 时仍然存储该条目，因为每个中间领导者都包含该条目（假设如此），领导者从不删除条目，跟随者只有在与领导者冲突时才会删除条目。
  5. 投票者将其票投给了 $leader_U$，因此 $leader_U$ 的日志必须与投票者的日志一样新。这导致了两个矛盾之一。
  6. 首先，如果投票者和 $leader_U$ 共享相同的最后一个日志任期，那么 $leader_U$ 的日志必须至少与投票者的日志一样长，因此其日志包含投票者日志中的每个条目。这是一个矛盾，因为投票者包含已提交的条目，而假设 $leader_U$ 不包含。
  7. 否则，$leader_U$ 的最后一个日志任期必须大于投票者的任期。此外，它大于 T，因为投票者的最后一个日志任期至少是 T（它包含来自 T 任期的已提交条目）。创建 $leader_U$ 最后一个日志条目的早期领导者必须在其日志中包含已提交的条目（假设如此）。然后，根据日志匹配属性，$leader_U$ 的日志也必须包含已提交的条目，这是一个矛盾。
  8. 这完成了矛盾。因此，所有大于 T 任期的领导者必须包含 T 任期中提交的所有条目。
  9. 日志匹配属性保证未来的领导者也将包含间接提交的条目，例如图8(d)中的索引2。

鉴于领导者完整性属性，我们可以证明图3中的状态机安全性属性，该属性指出，如果服务器在给定索引处将日志条目应用到其状态机，则没有其他服务器会为相同索引应用不同的日志条目。当服务器将日志条目应用到其状态机时，其日志必须与领导者的日志在该条目之前完全相同，并且该条目必须已提交。现在考虑任何服务器在给定日志索引处应用条目的最低任期；日志完整性属性保证所有更高任期的领导者将存储相同的日志条目，因此在后续任期中应用该索引的服务器将应用相同的值。因此，状态机安全性属性成立。

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

5.5 跟随者和候选者崩溃

到目前为止，我们一直关注领导者故障。追随者和候选者的崩溃比领导者崩溃更容易处理，而且处理方式相同。如果追随者或候选者崩溃，那么发送给它的未来 RequestVote 和 AppendEntries RPC 将失败。Raft 通过无限期重试来处理这些故障；如果崩溃的服务器重新启动，则 RPC 将成功完成。如果服务器在完成 RPC 后但在响应之前崩溃，则它将在重新启动后再次收到相同的 RPC。Raft RPC 是幂等的，因此不会造成任何损害。例如，如果追随者收到包含其日志中已存在的日志条目的 AppendEntries 请求，它将在新请求中忽略这些条目。

5.6 时间与可用性

我们对 Raft 的一个要求是安全性不能依赖于时间：系统不能因为某些事件发生得比预期更快或更慢而产生错误结果。然而，可用性（系统及时响应客户端的能力）不可避免地必须依赖于时间。例如，如果消息交换的时间比服务器崩溃之间的典型时间更长，候选者将无法保持足够长的时间来赢得选举；没有稳定的领导者，Raft 无法取得进展。

领导者选举是 Raft 中时间最关键的方面。只要系统满足以下时间要求，Raft 就能够选举并维持一个稳定的领导者：

$$ broadcastTime \ll electionTimeout \ll MTBF $$

在这个不等式中，广播时间（broadcastTime） 是服务器并行向集群中的每个服务器发送 RPC 并接收其响应的平均时间；选举超时（electionTimeout） 是第5.2节中描述的选举超时；MTBF 是单个服务器的平均故障间隔时间。广播时间应比选举超时小一个数量级，以便领导者能够可靠地发送心跳消息，防止跟随者启动选举；鉴于选举超时使用的随机化方法，这个不等式也使得分裂投票不太可能发生。选举超时应比 MTBF 小几个数量级，以便系统能够稳步前进。当领导者崩溃时，系统将大约在选举超时期间不可用；我们希望这只占总时间的一小部分。

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

6 集群成员身份变化

Figure 10
图 10： 直接从一种配置切换到另一种配置是不安全的，因为不同的服务器会在不同的时间切换。在此示例中，集群从三台服务器增长到五台。不幸的是，在某个时间点，可以选出两个不同的领导者担任同一任期，一个拥有旧配置的多数席位（Cold），另一个拥有新配置的多数席位（Cnew）。

到目前为止，我们一直假设集群配置（configuration）（参与共识算法的服务器集合）是固定不变的。但在实践中，偶尔需要改变配置，例如在服务器发生故障时替换服务器，或者改变副本的数量。虽然可以通过使整个集群离线、更新配置文件、然后重启集群的方式来完成这些改变，但这种方式会导致集群在变更期间不可用。此外，如果存在任何手动步骤，就会有操作员出错的风险。为了避免这些问题，我们决定将配置变更自动化，并将其整合到 Raft 共识算法中。

对于配置变更机制来说，必须确保在转换过程中的任何时刻都不可能出现在同一任期内选举出两个领导者的情况。不幸的是，任何让服务器直接从旧配置切换到新配置的方法都是不安全的。由于无法让所有服务器同时原子性地切换，在转换过程中集群可能会分裂成两个独立的多数派（如图10所示）。

为了确保安全性，配置变更必须采用两阶段的方法。实现这两个阶段有多种方式。例如，一些系统（如4）在第一阶段禁用旧配置使其无法处理客户端请求；然后在第二阶段启用新配置。在 Raft 中，集群首先切换到一个称为“联合共识”的过渡配置；一旦联合共识被提交，系统就会转换到新配置。联合共识将新旧配置结合在一起：

  • 日志条目会复制到两种配置中的所有服务器。
  • 任一配置的任何服务器都可以充当领导者。
  • 在达成一致（包括选举和日志条目提交）时，需要同时获得旧配置和新配置中的多数派同意。

联合共识允许各个服务器在不同时间点进行配置转换，同时不影响安全性。此外，联合共识使集群能够在整个配置变更过程中持续处理客户端请求。

Figure 11
图 11：配置更改的时间表。虚线表示已创建但未提交的配置条目，实线表示最新提交的配置条目。领导者首先在其日志中创建 Cold,new 配置条目并将其提交给 Cold,new（大部分 Cold 和大部分 Cnew）。然后它创建 Cnew 条目并将其提交给大多数 Cnew。 Cold 和 Cnew 不存在可以同时独立做出决策的时间点。

集群配置通过复制日志中的特殊条目来存储和传输；图11展示了配置变更的过程。当领导者收到将配置从 $C_{old}$ 改变为 $C_{new}$ 的请求时，它会将联合共识的配置（图中的 $C_{old,new}）$作为一个日志条目存储，并使用之前描述的机制复制该条目。一旦某个服务器将新的配置条目添加到其日志中，它就会将该配置用于所有后续的决策（服务器总是使用其日志中最新的配置，无论该条目是否已提交）。这意味着领导者将使用 $C_{old,new}$ 的规则来确定 $C_{old,new}$,new 的日志条目何时被提交。如果领导者崩溃，新的领导者可能根据 $C_{old}$ 或 $C_{old,new}$被选出，这取决于获胜的候选者是否已收到 $C_{old,new}$。在任何情况下，$C_{new}$ 在此期间都不能单方面做出决策。

一旦 $C_{old,new}$ 被提交，如果没有对方的认可，$C_{old}$ 和 $C_{new}$ 都不能做出决策，并且领导者完整性属性确保只有具有 $C_{old,new}$ 日志条目的服务器才能被选举为领导者。此时，领导者就可以安全地创建描述 $C_{new}$ 的日志条目并将其复制到集群中。同样，这个配置在每个服务器看到时就会立即生效。当新配置在 $C_{new}$ 规则下被提交后，旧配置就变得无关紧要了，不在新配置中的服务器可以被关闭。如图11所示，不存在 $C_{old}$ 和 $C_{new}$ 都能单方面做出决策的时间点；这保证了安全性。

对于重新配置，还有三个问题需要解决。第一个问题是新服务器最初可能不存储任何日志条目。如果在这种状态下将它们加入集群，它们可能需要相当长的时间才能赶上进度，在此期间可能无法提交新的日志条目。为了避免可用性中断，Raft 在配置变更之前引入了一个额外的阶段，在这个阶段中，新服务器以非投票成员的身份加入集群（领导者会向它们复制日志条目，但不将它们计入多数派）。一旦新服务器赶上了集群的其余部分，就可以按照上述方式进行重新配置。

第二个问题是集群领导者可能不属于新配置。在这种情况下，一旦领导者提交了 $C_{new}$ 日志条目，就会主动退位（返回追随者状态）。这意味着会有一段时间（在提交 $C_{new}$ 期间）领导者在管理一个不包含自己的集群；它会复制日志条目，但在计算多数派时不将自己计算在内。领导者交接发生在 $C_{new}$ 被提交时，因为这是新配置能够独立运作的第一个时间点（从 $C_{new}$ 中总能选出一个领导者）。在此之前，可能只有来自 $C_{old}$ 的服务器才能被选举为领导者。

第三个问题是被移除的服务器（不在 $C_{new}$ 中的服务器）可能会扰乱集群。这些服务器将收不到心跳，因此它们会超时并开始新的选举。然后它们会发送带有新任期号的 RequestVote RPC，这将导致当前领导者退回到追随者状态。最终会选出新的领导者，但被移除的服务器会再次超时，这个过程会重复发生，导致可用性降低。

为了防止这个问题，当服务器认为存在当前领导者时，会忽略 RequestVote RPC。具体来说，如果服务器在最小选举超时时间内收到过当前领导者的消息，那么当它收到 RequestVote RPC 时，既不会更新自己的任期号，也不会投票。这不会影响正常的选举，因为在正常选举中，每个服务器都会至少等待最小选举超时时间才开始选举。然而，这有助于避免被移除服务器的干扰：如果领导者能够向其集群发送心跳，那么它就不会因为更大的任期号而被废黜。

7 日志压缩

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

快照是最简单的压缩方法。在快照机制中，整个当前系统状态被写入稳定存储中的 快照（snapshot） 文件，然后该时间点之前的所有日志都可以被丢弃。快照机制在 Chubby 和 ZooKeeper 中都有使用，本节的剩余部分将描述 Raft 中的快照机制。

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

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

图12展示了Raft中快照的基本概念。每个服务器独立地进行快照，只覆盖其日志中的已提交条目。大部分工作由状态机将其当前状态写入快照中完成。Raft还在快照中包含少量元数据：最后包含的索引（last included index） 是快照替换的日志中最后一个条目的索引（状态机已应用的最后一个条目），最后包含的任期（last included term） 是该条目的任期。这些数据被保留以支持快照后第一个日志条目的AppendEntries一致性检查，因为该条目需要前一个日志索引和任期。为了支持集群成员变更（第6节），快照还包括截至最后包含索引的最新配置。一旦服务器完成快照写入，它可以删除所有通过最后包含索引的日志条目以及任何先前的快照。

虽然服务器通常独立进行快照，但领导者有时必须向落后的追随者发送快照。当领导者已经丢弃了需要发送给追随者的下一个日志条目时，就会发生这种情况。幸运的是，这种情况在正常操作中不太可能发生：一个跟上领导者的追随者已经拥有这个条目。然而，一个异常缓慢的追随者或一个新加入集群的服务器（第6节）则不会。使这样的追随者更新的方法是领导者通过网络向其发送快照。

Figure 13
图 13：InstallSnapshot RPC 的总结。快照被分割成块进行传输；这为追随者提供了每个块的生命迹象，因此它可以重置其选举计时器。

InstallSnapshot RPC
由领导者调用以将快照块发送给追随者。领导者总是按顺序发送块。
参数：term领导者的任期
leaderID正在请求投票的候选者
lastIncludedIndex快照将替换该索引之前的所有条目（包括该索引）
lastIncludedTermlastIncludedIndex的任期
offset快照文件中块所在的字节偏移量
data[]快照块的原始字节，从偏移量开始
done如果这是最后一个块则为 true
结果：termcurrentTerm，供领导者自我更新
voteGrantedtrue 表示候选者获得选票
接收者实现：
  1. 如果 term < currentTerm 则立即回复
  2. 如果是第一个块（偏移量为 0）则创建新的快照文件
  3. 将数据写入给定偏移量的快照文件
  4. 如果 done 为 false，则回复并等待更多数据块
  5. 保存快照文件，丢弃任何现有的或索引较小的部分快照
  6. 如果现有日志条目与快照最后包含的条目具有相同的索引和任期，则保留其后面的日志条目并回复
  7. 丢弃整个日志
  8. 使用快照内容重置状态机（并加载快照的集群配置）

领导者使用一个称为InstallSnapshot的新RPC来向落后太多的跟随者发送快照，如图13所示。当跟随者通过这个RPC接收到快照时，它必须决定如何处理其现有的日志条目。通常情况下，快照会包含接收者日志中尚未存在的新信息。在这种情况下，跟随者会丢弃其全部日志，因为这些日志都被快照取代了，并且可能包含与快照相冲突的未提交条目。如果跟随者接收到的快照描述的是其日志的前缀部分（由于重传或错误导致），那么被快照覆盖的日志条目会被删除，但快照之后的条目仍然有效且必须保留。

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

我们考虑了一种基于领导者的替代方法，即只有领导者创建快照，然后将此快照发送给每个追随者。然而，这有两个缺点。首先，将快照发送给每个追随者会浪费网络带宽并减慢快照过程。每个追随者已经拥有生成其自身快照所需的信息，通常服务器从其本地状态生成快照比通过网络发送和接收快照所消耗的代价小得多。其次，领导者的实现会更加复杂。例如，领导者需要在向追随者复制新的日志条目的同时并行发送快照，以免阻塞新的客户端请求。

还有两个问题会影响快照性能。首先，服务器必须决定何时进行快照。如果服务器快照过于频繁，会浪费磁盘带宽和能源；如果快照过于不频繁，则有耗尽存储容量的风险，并且在重启时重放日志所需的时间会增加。一种简单的策略是在日志达到固定字节大小时进行快照。如果这个大小设置得明显大于预期的快照大小，那么快照的磁盘带宽开销将很小。

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

8 客户端交互

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

Raft的客户端将所有请求发送给领导者。当客户端首次启动时，它会连接到一个随机选择的服务器。如果客户端的第一个选择不是领导者，该服务器将拒绝客户端的请求并提供其所知的最近领导者的信息（AppendEntries请求包括领导者的网络地址）。如果领导者崩溃，客户端请求将超时；客户端然后尝试与随机选择的服务器重新连接。

我们对Raft的目标是实现线性化语义（每个操作看起来像是在其调用和响应之间的某个点瞬时执行且仅执行一次）。然而，如前所述，Raft可能会多次执行一个命令：例如，如果领导者在提交日志条目后但在响应客户端之前崩溃，客户端将会重试该命令并与新的领导者联系，导致该命令被再次执行。解决方案是客户端为每个命令分配唯一的序列号。然后，状态机跟踪每个客户端处理的最新序列号及其关联的响应。如果它收到一个序列号已经执行过的命令，它会立即响应而不重新执行该请求。

只读操作可以在不写入日志的情况下处理。然而，如果没有额外的措施，这将有返回过时数据的风险，因为响应请求的领导者可能已经被一个它不知道的新领导者取代。线性化读取不能返回过时数据，Raft需要两个额外的预防措施来保证这一点而不使用日志。首先，领导者必须拥有最新的已提交条目信息。领导者完整性属性保证了领导者拥有所有已提交的条目，但在其任期开始时，它可能不知道这些条目是什么。为了找出这些条目，它需要提交一个来自其任期的条目。Raft通过在每个领导者任期开始时提交一个空的无操作条目到日志中来处理这一点。其次，领导者在处理只读请求之前必须检查它是否已被罢免（如果选出了一个更新的领导者，它的信息可能已经过时）。Raft通过让领导者在响应只读请求之前与集群的大多数节点交换心跳消息来处理这一点。或者，领导者可以依赖心跳机制提供一种租约形式22，但这将依赖于时间的安全性（假设时钟偏差是有界的）。

9 实现与评估

我们将 Raft 实现为复制状态机的一部分，该状态机存储 RAMCloud 8 的配置信息并协助 RAMCloud 协调器进行故障转移。 Raft 实现包含大约 2000 行 C++ 代码，不包括测试、注释或空行。源代码可以免费获得23。根据本文的草稿，还有大约 25 个处于不同开发阶段的 Raft 独立第三方开源实现 24。此外，多家公司正在部署基于 Raft 的系统 24。本节的其余部分使用三个标准评估 Raft：可理解性、正确性和性能。

9.1 可理解性

为了测量Raft相对于Paxos的可理解性，我们在斯坦福大学的高级操作系统课程和加州大学伯克利分校的分布式计算课程中，以高年级本科生和研究生为对象进行了一项实验研究。我们录制了一个关于Raft的视频讲座和一个关于Paxos的视频讲座，并制作了相应的测验。Raft讲座涵盖了本论文的内容（除了日志压缩）；Paxos讲座涵盖了足够多的内容来创建一个等效的复制状态机，包括单决策Paxos、多决策Paxos、重新配置，以及在实践中需要的一些优化（如领导者选举）。这些测验考察了对算法的基本理解，还要求学生对边界情况进行推理。每个学生观看一个视频，完成相应的测验，然后观看第二个视频，完成第二个测验。为了考虑个人表现差异和从研究第一部分获得的经验，大约一半的参与者先学习Paxos部分，另一半先学习Raft部分。我们比较了参与者在每个测验中的得分，以确定参与者是否对Raft表现出更好的理解。

Table 1
表 1：研究中对 Paxos 可能存在的偏见的担忧、针对每种偏见采取的措施以及可用的其他材料。

担忧为减少偏见而采取的措施供审查的材料 2526
同等的授课质量两者的讲师相同。 Paxos 讲座基于几所大学使用的现有材料并对其进行了改进。 Paxos 讲座时间延长了 14%。视频
同等的测验难度问题按难度分组并在考试中配对。测验
公平评分使用的标题。按随机顺序评分，测验之间交替进行。标题

我们尽量使Paxos和Raft之间的比较尽可能公平。实验在两个方面偏向了Paxos：43名参与者中有15人报告说他们有一些Paxos的先前经验，并且Paxos视频比Raft视频长14%。如表1所示，我们采取了措施来减轻潜在的偏见来源。我们所有的材料都可供审查25 26。

Figure 14
图 14：比较 43 名参与者在 Raft 和 Paxos 测验中表现的散点图。对角线上方的点 (33) 代表 Raft 得分较高的参与者。

平均而言，参与者在Raft测验中的得分比在Paxos测验中高4.9分（满分60分，Raft的平均得分为25.7分，Paxos的平均得分为20.8分）；图14显示了他们的个人得分。配对t检验表明，在95%的置信水平下，Raft得分的真实分布的均值至少比Paxos得分的真实分布高2.5分。

我们还创建了一个线性回归模型，根据三个因素预测新学生的测验得分：他们参加的测验、他们的先前Paxos经验程度以及他们学习算法的顺序。该模型预测测验的选择会导致Raft得分高出12.5分。这显著高于观察到的4.9分差异，因为许多实际学生有先前的Paxos经验，这大大帮助了Paxos，而对Raft的帮助稍小一些。有趣的是，该模型还预测已经参加过Paxos测验的人在Raft测验中的得分会低6.3分；虽然我们不知道为什么，但这似乎在统计上显著。

Figure 15
图 15：使用 5 分制，参与者被问到（左）他们认为哪种算法更容易在功能正常、正确且高效的系统中实现，以及（右）哪种算法更容易向计算机科学研究生解释。

我们还在测验后对参与者进行了调查，了解他们认为哪种算法更容易实现或解释；这些结果如图15所示。绝大多数参与者报告说Raft更容易实现和解释（每个问题41人中有33人）。然而，这些自我报告的感受可能不如参与者的测验得分可靠，并且参与者可能因为知道我们的假设是Raft更容易理解而存在偏见。

关于Raft用户研究的详细讨论，请参见26。

9.2 正确性

我们已经开发了一个正式规范和一个关于第5节中描述的共识机制的安全性证明。正式规范26使用TLA+规范语言27使图2中总结的信息完全精确。它大约有400行长，并作为证明的主题。对于任何实现Raft的人来说，它本身也很有用。我们使用TLA证明系统28机械地证明了日志完整性属性。然而，这个证明依赖于尚未机械检查的不变量（例如，我们尚未证明规范的类型安全性）。此外，我们还撰写了一份关于状态机安全性属性的非正式证明26，该证明是完整的（仅依赖于规范）且相对精确（大约3500字长）。

9.3 性能

Raft的性能与其他共识算法（如Paxos）相似。性能最重要的情况是当一个已建立的领导者正在复制新的日志条目时。Raft通过使用最少数量的消息（从领导者到集群一半节点的单次往返）来实现这一点。还可以进一步提高Raft的性能。例如，它可以轻松支持批处理和流水线请求，以实现更高的吞吐量和更低的延迟。文献中提出了各种针对其他算法的优化；其中许多可以应用于Raft，但我们将其留待未来工作。

我们使用Raft的实现来测量Raft的领导者选举算法的性能，并回答两个问题。首先，选举过程是否快速收敛？其次，在领导者崩溃后可以实现的最小停机时间是多少？

Figure 16
图 16：检测和更换崩溃的领导者的时间。上图改变了选举超时的随机性，下图则缩放了最小选举超时。每行代表 1000 次试验（“150-150ms”的 100 次试验除外），并对应于选举超时的特定选择；例如，“150–155ms”表示选举超时在150ms到155ms之间随机且均匀地选择。测量是在由 5 台服务器组成的集群上进行的，广播时间约为 15 毫秒。由九台服务器组成的集群的结果类似。

为了测量领导者选举，我们反复使五个服务器组成的集群的领导者崩溃，并计时检测到崩溃和选举新领导者所需的时间（见图16）。为了生成最坏情况场景，每次测试中的服务器都有不同的日志长度，因此某些候选人没有资格成为领导者。此外，为了促使选票分散，我们的测试脚本在终止领导者进程之前触发了一次同步的心跳RPC广播（这近似于领导者在崩溃前复制新日志条目的行为）。领导者在其心跳间隔内随机均匀地崩溃，该间隔是所有测试中最小选举超时时间的一半。因此，最短可能的停机时间约为最小选举超时时间的一半。

图16的上部图显示，选举超时时间的少量随机化就足以避免选举中的选票分散。在没有随机性的情况下，由于许多选票分散，我们的测试中领导者选举始终需要超过10秒。仅添加5毫秒的随机性就能显著改善，使中位停机时间降至287毫秒。增加更多随机性可以改善最坏情况下的表现：使用50毫秒的随机性时，最坏情况下的完成时间（超过1000次测试）为513毫秒。

图16的下部图显示，通过减少选举超时时间可以减少停机时间。当选举超时时间为12-24毫秒时，选举领导者平均只需要35毫秒（最长的测试花费152毫秒）。然而，将超时时间降低到这个点以下会违反Raft的时间要求：领导者在其他服务器开始新的选举之前难以广播心跳。这可能导致不必要的领导者更换并降低整体系统可用性。我们建议使用较为保守的选举超时时间，如150-300毫秒；这样的超时时间不太可能导致不必要的领导者更换，同时仍能提供良好的可用性。

10 相关工作

有许多关于共识算法的出版物，其中许多可以归入以下几类之一：

  • Lamport对Paxos的原始描述1，以及试图更清晰地解释它的尝试2 11 12。
  • 对Paxos的详细阐述，填补了缺失的细节并修改了算法，以提供更好的实现基础13 14 15。
  • 实现共识算法的系统，如Chubby9 16、ZooKeeper10 [^12]和Spanner29。虽然Chubby和Spanner的算法没有详细发表，但它们都声称基于Paxos。ZooKeeper的算法已更详细地发表，但它与Paxos有很大不同。
  • 可以应用于Paxos的性能优化30 31 32 33 34 35。
  • Oki和Liskov的Viewstamped Replication (VR)，这是与Paxos同时期开发的另一种共识方法。原始描述3与分布式事务协议交织在一起，但核心共识协议在最近的更新中已被分离出来4。VR使用了一种基于领导者的方法，与Raft有许多相似之处。

Raft和Paxos之间最大的区别在于Raft的强领导性：Raft将领导者选举作为共识协议的一个基本部分，并尽可能多地将功能集中在领导者身上。这种方法产生了一个更简单且更易于理解的算法。例如，在Paxos中，领导者选举与基本共识协议是正交的：它仅作为性能优化，不是实现共识所必需的。然而，这导致了额外的机制：Paxos包括一个用于基本共识的两阶段协议和一个单独的领导者选举机制。相比之下，Raft将领导者选举直接纳入共识算法，并将其作为共识的两个阶段中的第一个。这导致了比Paxos更少的机制。

与Raft类似，VR和ZooKeeper也是基于领导者的，因此它们与Raft相比具有许多优势。然而，Raft的机制比VR或ZooKeeper更少，因为它最小化了非领导者的功能。例如，Raft中的日志条目只在一个方向上流动：通过AppendEntries RPC从领导者向外流动。在VR中，日志条目在两个方向上流动（领导者在选举过程中可以接收日志条目）；这导致了额外的机制和复杂性。ZooKeeper的已发布描述也显示日志条目在领导者之间双向传输，但其实现显然更像Raft36。

Raft的消息类型比我们所知的任何其他基于共识的日志复制算法都要少。例如，我们统计了VR和ZooKeeper用于基本共识和成员变更的消息类型（不包括日志压缩和客户端交互，因为这些几乎与算法无关）。VR和ZooKeeper各定义了10种不同的消息类型，而Raft只有4种消息类型（两个RPC请求及其响应）。Raft的消息比其他算法的消息更密集一些，但总体上更简单。此外，VR和ZooKeeper在领导者变更期间传输整个日志；为了使这些机制实用，还需要额外的消息类型来优化这些机制。

Raft的强领导方法简化了算法，但它排除了某些性能优化。例如，Egalitarian Paxos (EPaxos)在某些条件下可以通过无领导方法实现更高的性能35。EPaxos利用状态机命令的可交换性。只要并发提出的其他命令与其可交换，任何服务器都可以通过一轮通信提交一个命令。然而，如果并发提出的命令彼此不可交换，EPaxos需要额外一轮通信。由于任何服务器都可以提交命令，EPaxos在服务器之间很好地平衡了负载，并且在广域网环境中能够实现比Raft更低的延迟。然而，这增加了Paxos的复杂性。

在其他工作中提出或实现了几种不同的集群成员变更方法，包括Lamport的原始提议1、VR4和SMART37。我们为Raft选择了联合共识方法，因为它利用了其余的共识协议，因此成员变更所需的额外机制非常少。Lamport的基于α的方法不适用于Raft，因为它假设可以在没有领导者的情况下达成共识。与VR和SMART相比，Raft的重新配置算法的优势在于成员变更可以在不限制正常请求处理的情况下进行；相反，VR在配置变更期间停止所有正常处理，而SMART对未完成请求的数量施加了类似α的限制。Raft的方法也比VR或SMART增加了更少的机制。

11 结论

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

在本文中，我们解决了分布式共识问题，其中一个广泛接受但难以理解的算法Paxos多年来一直困扰着学生和开发人员。我们开发了一种新算法Raft，并证明它比Paxos更易于理解。我们还认为Raft为系统构建提供了更好的基础。将可理解性作为主要设计目标改变了我们设计Raft的方法；随着设计的进展，我们发现自己反复使用一些技术，例如分解问题和简化状态空间。这些技术不仅提高了Raft的可理解性，还使我们更容易确信其正确性。

12 致谢

用户研究得到了Ali Ghodsi、David Mazie`res以及伯克利大学CS 294-91课程和斯坦福大学CS 240课程学生的支持，才得以进行。Scott Klemmer帮助我们设计了用户研究，Nelson Ray在统计分析方面提供了建议。用户研究的Paxos幻灯片大量借用了Lorenzo Alvisi最初创建的幻灯片。特别感谢David Mazie`res和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的支持，这两个中心是半导体研究公司项目Focus Center Research Program资助的六个研究中心之一，还得到了由MARCO和DARPA赞助的半导体研究公司项目STARnet的支持，国家科学基金会的资助（资助号0963859），以及来自Facebook、Google、Mellanox、NEC、NetApp、SAP和三星的资助。Diego Ongaro得到了The Junglee Corporation Stanford Graduate Fellowship的支持。

参考文献

  1. LAMPORT, L. The part-time parliament. ACM Transactions on Computer Systems 16, 2 (May 1998), 133–169. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎

  2. LAMPORT, L. Paxos made simple. ACM SIGACT News 32, 4 (Dec. 2001), 18–25. ↩︎ ↩︎ ↩︎

  3. 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. ↩︎ ↩︎

  4. LISKOV, B., AND COWLING, J. Viewstamped replication revisited. Tech. Rep. MIT-CSAIL-TR-2012-021, MIT, July 2012. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎

  5. SCHNEIDER, F. B. Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Computing Surveys 22, 4 (Dec. 1990), 299–319. ↩︎

  6. 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. ↩︎

  7. 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. ↩︎

  8. OUSTERHOUT, J., AGRAWAL, P., ERICKSON, D., KOZYRAKIS, C., LEVERICH, J., MAZIE` RES, 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. ↩︎ ↩︎

  9. 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. ↩︎ ↩︎

  10. 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. ↩︎ ↩︎

  11. 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. ↩︎ ↩︎

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

  13. MAZIE` RES, D. Paxos made practical. http: //www.scs.stanford.edu/ ̃dm/home/ papers/paxos.pdf, Jan. 2007. ↩︎ ↩︎

  14. VAN RENESSE, R. Paxos made moderately complex. Tech. rep., Cornell University, 2012. ↩︎ ↩︎

  15. KIRSCH, J., AND AMIR, Y. Paxos for system builders. Tech. Rep. CNDS-2008-2, Johns Hopkins University, 2008. ↩︎ ↩︎

  16. 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. ↩︎ ↩︎ ↩︎

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

  18. 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. ↩︎

  19. O’NEIL, P., CHENG, E., GAWLICK, D., AND ONEIL, E. The log-structured merge-tree (LSM-tree). Acta Informatica 33, 4 (1996), 351–385. ↩︎

  20. 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. ↩︎

  21. 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. ↩︎

  22. 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. ↩︎

  23. LogCabin source code. http://github.com/logcabin/logcabin. ↩︎

  24. Raft consensus algorithm website. http://raftconsensus.github.io. ↩︎ ↩︎

  25. Raft user study. http://ramcloud.stanford. edu/ ̃ongaro/userstudy/. ↩︎ ↩︎

  26. ONGARO, D. Consensus: Bridging Theory and Practice. PhD thesis, Stanford University, 2014 (work in progress). http://ramcloud.stanford.edu/ ̃ongaro/ thesis.pdf. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎

  27. LAMPORT, L. Specifying Systems, The TLA+ Language and Tools for Hardware and Software Engineers. AddisonWesley, 2002. ↩︎

  28. 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. ↩︎

  29. 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. ↩︎

  30. LAMPORT, L. Generalized consensus and Paxos. Tech. Rep. MSR-TR-2005-33, Microsoft Research, 2005. ↩︎

  31. LAMPORT, L. Fast paxos. Distributed Computing 19, 2 (2006), 79–103. ↩︎

  32. 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. ↩︎

  33. 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. ↩︎

  34. 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. ↩︎

  35. 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. ↩︎ ↩︎

  36. REED, B. Personal communications, May 17, 2013. ↩︎

  37. 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. ↩︎