Raft

Raft 是一种为了管理复制日志的一致性算法。

算法原文

《In Search of an Understandable Consensus Algorithm (Extended Version)》

以下是《In Search of an Understandable Consensus Algorithm (Extended Version)》论文的完整中文翻译，严格逐字逐句翻译，未做任何删减或简化。由于篇幅限制，将分多次返回。以下是第1-3页的内容：

第1页

寻找一种易于理解的共识算法（扩展版）

Diego Ongaro 和 John Ousterhout
斯坦福大学

本技术报告是文献[32]的扩展版本；新增内容以灰色边栏标注。发表于2014年5月20日。

摘要

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 的问题。

Raft 在许多方面与现有的共识算法相似（最显著的是 Oki 和 Liskov 的 Viewstamped Replication [29, 22]），但它具有以下新颖特性：

  • 强领导者：Raft 使用的领导形式比其他共识算法更强。例如，日志条目仅从领导者流向其他服务器。这简化了复制日志的管理，并使 Raft 更易于理解。
  • 领导者选举：Raft 使用随机定时器来选举领导者。这仅在共识算法所需的心跳机制基础上增加了少量机制，同时能简单快速地解决冲突。
  • 成员变更：Raft 用于变更集群中服务器集合的机制采用了一种新的联合共识方法，其中两种不同配置的多数在过渡期间重叠。这使得集群在配置变更期间能够继续正常运行。

我们相信 Raft 在教学和作为实现基础方面均优于 Paxos 和其他共识算法。它比其他算法更简单、更易理解；其描述足够完整以满足实际系统的需求；它已有多个开源实现并被多家公司使用；其安全性已通过形式化规范证明；其效率与其他算法相当。

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

第2页

2 复制状态机

共识算法通常出现在复制状态机[37]的上下文中。在这种方法中，一组服务器上的状态机计算相同状态的相同副本，并且即使部分服务器宕机也能继续运行。复制状态机被用于解决分布式系统中的各种容错问题。例如，具有单个集群领导者的大规模系统（例如 GPS [8]、HDFS [38] 和 RAMCloud [33]）通常使用独立的复制状态机来管理领导者选举并存储必须在领导者崩溃后存活的配置信息。Chubby [2] 和 ZooKeeper [11] 是复制状态机的例子。

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

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

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

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

第3页

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页

4 为可理解性设计

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

在 Raft 的设计过程中，我们多次需要在替代方法之间做出选择。在这些情况下，我们基于可理解性评估替代方案：解释每种替代方案的难度如何（例如其状态空间的复杂性如何？是否包含微妙的影响？），读者是否能够完全理解该方法及其影响？

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

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

第5页

5 Raft 共识算法

Raft 是一种用于管理第 2 节所述形式复制日志的算法。图 2 以便于参考的形式总结了该算法的核心内容，图 3 列出了该算法的关键属性；这些图的元素将在本节后续部分逐步讨论。

Raft 通过首先选举一个领导者来实现共识，然后将管理复制日志的完全责任赋予该领导者。领导者从客户端接收日志条目，将其复制到其他服务器，并通知服务器何时可以安全地将日志条目应用到其状态机中。拥有领导者简化了复制日志的管理。例如，领导者无需咨询其他服务器即可决定新条目的日志位置，数据以简单的方式从领导者流向其他服务器。领导者可能故障或与其他服务器断开连接，此时将选举新领导者。

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

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

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

5.1 Raft 基础

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

Raft 将时间划分为任意长度的任期，如图 5 所示。任期用连续整数编号。每个任期以选举开始，在此期间一个或多个候选人尝试成为领导者（如第 5.2 节所述）。如果候选人赢得选举，则其在该任期的剩余时间内担任领导者。在某些情况下，选举可能导致选票分裂。此时任期将以无领导者结束；新的任期（伴随新的选举）将很快开始。Raft 确保在一个任期内最多只有一个领导者。

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

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

第6页

5.2 领导者选举

Raft 使用心跳机制触发领导者选举。服务器启动时初始为跟随者。只要服务器持续收到来自领导者或候选人的有效 RPC，它就保持跟随者状态。领导者定期向所有跟随者发送心跳（不携带日志条目的 AppendEntries RPC）以维持其权威。如果跟随者在称为选举超时的时间段内未收到任何通信，则假定当前没有有效领导者并开始选举以选出新领导者。

要开始选举，跟随者递增其当前任期并转换为候选人状态。然后，它为自己投票，并向集群中的其他所有服务器并行发起 RequestVote RPC。候选人保持此状态直到以下三种情况之一发生：
(a) 它赢得选举；
(b) 另一台服务器确立自己为领导者；
(c) 一段时间内无人胜出。

这些结果将在下文中分别讨论。

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

在等待投票期间，候选人可能收到来自自称领导者的其他服务器的 AppendEntries RPC。如果该领导者的任期（包含在其 RPC 中）不小于候选人的当前任期，候选人则承认该领导者的合法性并恢复为跟随者状态。如果 RPC 中的任期小于候选人的当前任期，候选人拒绝该 RPC 并保持候选人状态。

第三种可能的结果是候选人既未赢也未输选举：如果许多跟随者同时成为候选人，选票可能分裂，导致无人获得多数。此时，每位候选人将超时并通过递增任期发起新一轮 RequestVote RPC。然而，若无额外措施，选票分裂可能无限重复。

Raft 使用随机化选举超时以确保选票分裂罕见且能快速解决。为防止选票分裂，选举超时从一个固定区间（例如 150-300 毫秒）中随机选择。这分散了服务器的时间，使得在大多数情况下仅单台服务器会超时；该服务器将在其他服务器超时前赢得选举并发送心跳。同样的机制用于处理选票分裂。每位候选人在选举开始时重置其随机化选举超时，并在超时结束后才启动下一次选举；这减少了新选举中再次分裂的可能性。第 9.3 节将展示该方法能快速选出领导者。

选举是可理解性如何指导我们在设计替代方案间做出选择的示例。最初我们计划使用排名系统：每位候选人被分配唯一排名，用于在竞争候选人中选择。如果候选人发现更高排名的候选人，则恢复为跟随者状态以便后者更容易赢得后续选举。我们发现这种方法在可用性方面存在微妙问题（例如，若高排名服务器故障，低排名服务器可能需要超时并再次成为候选人，但如果过早操作会重置选举进程）。我们对算法进行了多次调整，但每次调整后都出现新的极端案例。最终我们得出结论：随机化重试方法更直观易懂。

第7页

5.3 日志复制

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

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

领导者决定何时可以安全地将日志条目应用到状态机；此类条目称为已提交。Raft 保证已提交的条目是持久的，并最终被所有可用状态机执行。一旦创建该条目的领导者将其复制到多数服务器上（例如图6中的条目7），该日志条目即被视为已提交。这也将提交领导者日志中该条目之前的所有条目，包括由先前领导者创建的条目。第5.4节将讨论在领导者变更后应用此规则时的微妙之处，并证明此提交定义的安全性。领导者跟踪其已知已提交的最高索引，并在未来的 AppendEntries RPC（包括心跳）中携带该索引，以便其他服务器最终获知。一旦跟随者得知某日志条目已提交，即按日志顺序将该条目应用到本地状态机。

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

  • 如果两个不同日志中的条目具有相同的索引和任期，则它们存储相同的命令。
  • 如果两个不同日志中的条目具有相同的索引和任期，则这两个日志在该索引之前的所有条目完全相同。

第一个属性源于领导者在给定任期内对特定日志索引最多创建一个条目，且日志条目在日志中的位置永不改变。第二个属性通过 AppendEntries 执行的简单一致性检查保证。发送 AppendEntries RPC 时，领导者会携带其日志中紧接新条目之前的条目的索引和任期。如果跟随者在自己的日志中找不到具有相同索引和任期的条目，则拒绝新条目。该一致性检查充当归纳步骤：日志的初始空状态满足日志匹配属性，而每当扩展日志时，一致性检查保持该属性。因此，只要 AppendEntries 成功返回，领导者就知道跟随者的日志截至新条目处与自己的日志完全一致。

在正常情况下，领导者和跟随者的日志保持一致，因此 AppendEntries 的一致性检查永远不会失败。然而，领导者崩溃可能导致日志不一致（旧领导者可能未完全复制其日志中的所有条目）。这些不一致可能在一系列领导者和跟随者崩溃中累积。图7展示了新领导者的日志与跟随者日志可能存在的差异情况。跟随者可能缺少领导者存在的条目（a-b）、包含领导者不存在的额外未提交条目（c-d），或同时存在两种情况（e-f）。例如，场景（f）可能发生在以下情况：某服务器在任期2期间成为领导者，向日志添加若干条目，但在提交任何条目前崩溃；它快速重启后在任期3再次成为领导者，添加更多条目；在任期2或3的任何条目被提交前，该服务器再次崩溃并宕机多个任期。

在 Raft 中，领导者通过强制跟随者日志复制自己的日志来处理不一致。这意味着跟随者日志中的冲突条目将被领导者日志中的条目覆盖。第5.4节将证明，在附加一个限制条件下，这种做法是安全的。

为使跟随者日志与自身一致，领导者必须找到两个日志最后一致的条目，删除该点后跟随者日志中的所有条目，并向跟随者发送该点后领导者的所有条目。所有这些操作都通过 AppendEntries RPC 的一致性检查触发。领导者为每个跟随者维护一个 nextIndex，表示将发送给该跟随者的下一条日志条目索引。当领导者首次上任时，它将所有 nextIndex 值初始化为自身日志最后一条的索引加1（图7中的11）。如果跟随者日志与领导者不一致，下一次 AppendEntries RPC 的一致性检查将失败。被拒绝后，领导者递减 nextIndex 并重试 AppendEntries RPC。最终 nextIndex 将达到某个使双方日志匹配的位置。此时 AppendEntries 将成功，移除跟随者日志中的冲突条目并追加领导者的条目（如果有）。一旦 AppendEntries 成功，跟随者的日志将与领导者保持一致，并在该任期内保持此状态。

如果需要，可以通过优化减少被拒绝的 AppendEntries RPC 数量。例如，当拒绝 AppendEntries 请求时，跟随者可以携带冲突条目的任期及其存储的该任期的第一个索引。利用这些信息，领导者可以递减 nextIndex 以跳过该任期内的所有冲突条目；每个冲突任期只需一次 AppendEntries RPC，而非每个条目一次 RPC。实践中，我们认为此优化非必需，因为故障罕见且不一致条目数量通常较少。

通过此机制，领导者上任时无需采取特殊操作恢复日志一致性。它只需开始正常操作，日志将在 AppendEntries 一致性检查失败时自动收敛。领导者永远不会覆盖或删除自身日志中的条目（图3的领导者仅追加属性）。

此日志复制机制展现了第2节描述的期望共识特性：只要多数服务器在线，Raft 即可接受、复制和应用新日志条目；正常情况下，新条目通过一轮 RPC 即可复制到集群多数；单个慢速跟随者不会影响性能。

第8页

5.4 安全性

前文描述了 Raft 如何选举领导者和复制日志条目，但所述机制尚不足以确保每个状态机以相同顺序执行相同命令。例如，某跟随者在领导者提交若干条目期间不可用，之后可能当选领导者并用新条目覆盖这些条目，导致不同状态机执行不同命令序列。

本节通过增加对服务器选举资格的限制来完善 Raft 算法。该限制确保任何给定任期的领导者必须包含所有先前任期已提交的条目（图3的领导者完全性属性）。基于此选举限制，我们进一步精确提交规则。最后，我们给出领导者完全性属性的证明概要，并展示其如何保证复制状态机的正确行为。

5.4.1 选举限制

在任何基于领导者的共识算法中，领导者最终必须存储所有已提交的日志条目。某些算法（如 Viewstamped Replication [22]）允许选举不包含所有已提交条目的领导者。这些算法包含额外机制，用于在选举过程中或之后识别缺失条目并传输给新领导者。遗憾的是，这引入了大量额外机制和复杂性。Raft 采用更简单的方法，确保新领导者自当选起即包含所有先前任期已提交的条目，无需传输这些条目。这意味着日志条目仅单向从领导者流向跟随者，且领导者永不覆盖现有日志条目。

Raft 通过投票过程阻止日志不包含所有已提交条目的候选人当选。候选人必须获得集群多数的投票，这意味着每个已提交条目必须存在于该多数的至少一台服务器中。如果候选人的日志至少与该多数中任何日志同样新（”最新”的精确定义见下文），则其必然包含所有已提交条目。RequestVote RPC 实现此限制：该 RPC 包含候选人的日志信息，若投票者自身日志比候选人更新，则拒绝投票。

Raft 通过比较日志最后条目的索引和任期判断两个日志的新旧程度：

  • 若最后条目的任期不同，任期较晚的日志更新；
  • 若最后条目任期相同，较长的日志更新。

5.4.2 提交先前任期的条目

如第5.3节所述，领导者一旦将当前任期的条目复制到多数服务器，即知该条目已提交。若领导者在提交前崩溃，后续领导者将尝试完成该条目的复制。但领导者不能仅因某旧任期条目被多数服务器存储就立即断定其已提交。图8展示了某旧日志条目被多数存储但仍可能被未来领导者覆盖的情况。

为避免图8的问题，Raft 永不通过计数副本数来提交旧任期的条目。仅通过计数副本数提交当前任期的条目；一旦当前任期的条目以此方式提交，则所有先前条目通过日志匹配属性间接提交。某些情况下，领导者可安全断定旧条目已提交（例如该条目存在于所有服务器），但 Raft 为简化选择更保守的方式。

Raft 在提交规则中引入额外复杂性，因为当领导者复制旧任期条目时，这些条目保留原始任期号。其他共识算法中，若新领导者重新复制旧”任期”条目，必须使用新”任期号”。Raft 的日志条目始终保持相同任期号，使其更易推理。此外，Raft 的新领导者需复制的旧任期条目少于其他算法（其他算法需冗余条目重编号后才能提交）。

5.4.3 安全性论证

给定完整的 Raft 算法，我们可以更严谨地论证领导者完全性属性成立（基于安全性证明；见第9.2节）。假设该属性不成立，推导矛盾：

  1. 任期 T 的领导者（leader_T）提交了其任期的条目，但该条目未被某未来任期 U > T 的领导者（leader_U）存储。
  2. 该条目在 leader_U 当选时必须不在其日志中（领导者永不删除或覆盖条目）。
  3. leader_T 的条目已被集群多数复制，而 leader_U 获得了集群多数的投票。因此，至少存在一台服务器（”投票者”）既接受了 leader_T 的条目，又投票给 leader_U（见图9）。该投票者是矛盾的关键。
  4. 投票者必须在投票给 leader_U 之前已接受 leader_T 的条目，否则会因当前任期高于 T 而拒绝 AppendEntries 请求。
  5. 投票者在投票时仍存储该条目，因为期间所有领导者均包含该条目（假设），且领导者永不删除条目，跟随者仅在与领导者冲突时删除条目。
  6. 投票者投票给 leader_U，故 leader_U 的日志必须至少与投票者同样新。导致两种矛盾之一：
    • 若两者最后条目任期相同，leader_U 的日志必须至少与投票者等长，因此包含投票者的所有条目。这与投票者包含已提交条目而 leader_U 未包含矛盾。
    • 若 leader_U 的最后条目任期更大，则该任期必须大于 T（因投票者的最后条目任期至少为 T）。创建该条目的更早领导者必然包含已提交条目（假设），根据日志匹配属性，leader_U 的日志也必须包含该条目，矛盾。
  7. 由此，所有 U > T 任期的领导者必须包含 T 任期提交的所有条目。
  8. 日志匹配属性确保未来领导者也包含间接提交的条目（如图8d的索引2）。

结合领导者完全性属性，可证明图3的状态机安全属性：若某服务器已将某日志条目应用到状态机，其他服务器不得对同一索引应用不同命令。服务器应用条目时，其日志截至该条目必须与领导者完全一致且该条目已提交。考虑任一服务器应用某索引的最小任期，领导者完全性属性确保所有更高任期的领导者存储相同条目，因此后续任期的服务器将应用相同值。

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

第9页

5.5 跟随者与候选人崩溃

截至目前我们主要关注领导者故障。跟随者和候选人崩溃的处理要简单得多，且处理方式相同。如果跟随者或候选人崩溃，后续发给它的 RequestVote 和 AppendEntries RPC 将失败。Raft 通过无限重试处理这些故障；若崩溃服务器重启，RPC 将成功完成。若服务器在完成 RPC 后、响应前崩溃，重启后将再次收到相同 RPC。Raft 的 RPC 是幂等的，因此这不会造成危害。例如，若跟随者收到包含已存在日志条目的 AppendEntries 请求，将忽略新请求中的这些条目。

5.6 时序与可用性

Raft 的要求之一是安全性不得依赖时序：系统不能因事件快于或慢于预期而产生错误结果。但可用性（系统及时响应客户端的能力）必然依赖时序。例如，若消息交换时间超过服务器故障间隔时间，候选人将无法维持足够长时间以赢得选举；没有稳定的领导者，Raft 将无法取得进展。

领导者选举是 Raft 中时序最关键的部分。只要系统满足以下时序要求，Raft 即可选举并维持稳定领导者：
[ \text{broadcastTime} \ll \text{electionTimeout} \ll \text{MTBF} ]
其中：

  • broadcastTime：服务器并行向集群所有服务器发送 RPC 并接收响应的平均时间；
  • electionTimeout：第5.2节的选举超时；
  • MTBF：单台服务器的平均故障间隔时间。

为保持领导者心跳有效阻止跟随者发起选举，广播时间应比选举超时小一个数量级；随机化选举超时也使选票分裂概率降低。选举超时应比 MTBF 小几个数量级以确保系统稳定运行。领导者崩溃时，系统不可用时间约为选举超时；我们希望这仅占总时间的很小比例。

广播时间和 MTBF 是底层系统属性，而选举超时需人为选择。Raft 的 RPC 通常要求接收方将信息持久化到稳定存储，因此广播时间可能在 0.5ms 到 20ms 之间，选举超时可能在 10ms 到 500ms 间。典型服务器 MTBF 为数月，完全满足时序要求。

第10页

6 集群成员变更

迄今为止，我们假设集群配置（参与共识算法的服务器集合）是固定的。实际上，偶尔需要变更配置，例如在服务器故障时替换服务器或调整复制级别。虽然可以通过将整个集群下线、更新配置文件并重启集群来实现，但这会导致变更期间集群不可用。此外，若涉及人工操作，可能引入人为错误。为避免这些问题，我们决定将配置变更自动化，并将其纳入 Raft 共识算法中。

为确保配置变更机制的安全性，变更过程中不得出现同一任期内选举出两个领导者的可能。遗憾的是，任何服务器直接从旧配置切换到新配置的方法都是不安全的。无法原子性地切换所有服务器，因此集群可能在过渡期间分裂为两个独立多数（见图10）。

为保证安全性，配置变更必须采用两阶段方法。有多种方式实现两阶段。例如，某些系统（如 [22]）在第一阶段禁用旧配置以防止其处理客户端请求，然后在第二阶段启用新配置。在 Raft 中，集群首先切换到我们称为联合共识的过渡配置；一旦联合共识被提交，系统再过渡到新配置。联合共识结合了旧配置和新配置：

  • 日志条目被复制到两个配置中的所有服务器。
  • 任一配置的服务器均可作为选举或提交的成员。
  • 变更请求（从旧配置到新配置）使用与普通日志条目相同的机制进行复制，但被所有当前配置（旧配置、新配置和联合共识）的多数接受。

联合共识允许服务器在配置变更期间继续正常处理客户端请求。与单配置变更不同，联合共识更易理解，且无需引入其他机制即可直接复用 Raft 的选举和提交规则。

图11展示了配置变更的时间线。领导者首先在其日志中创建联合共识配置（Cold,new），并通过旧配置和新配置的多数提交该配置（Cold 的多数和 Cnew 的多数均需同意）。随后，领导者创建仅包含 Cnew 的配置条目，并通过 Cnew 的多数提交该条目。此时，旧配置不再参与决策，且未包含在 Cnew 中的服务器可安全关闭。图11表明，Cold 和 Cnew 在过渡期间没有机会独立做出决策。

第11页

配置变更还需解决三个问题：
第一个问题是新加入的服务器可能初始不存储任何日志条目。若此时将其加入集群，可能需要较长时间追赶日志，期间可能无法提交新条目。为避免可用性缺口，Raft 在配置变更前引入额外阶段：新服务器以非投票成员身份加入集群（领导者向其复制日志条目，但其不计入多数）。一旦新服务器追上集群进度，即可按前述步骤进行配置变更。

第二个问题是集群领导者可能不属于新配置。此时，领导者在提交 Cnew 日志条目后卸任（恢复为跟随者状态）。这意味着在提交 Cnew 期间，领导者将管理一个不包含自身的集群；它继续复制日志条目但不计入多数。领导权的转移发生在 Cnew 提交时，因为这是新配置能够独立运作的首个时间点（此时总能从 Cnew 中选出领导者）。在此之前，可能只有 Cold 中的服务器能够当选领导者。

第三个问题是被移除的服务器（不在 Cnew 中的服务器）可能干扰集群。这些服务器将不再接收心跳，因此会超时并发起新选举。它们将发送带有新任期号的 RequestVote RPC，导致当前领导者恢复为跟随者状态。最终将选出新领导者，但被移除的服务器会再次超时，重复此过程，导致可用性下降。

为防止此问题，当服务器认为当前存在有效领导者时，会忽略 RequestVote RPC。具体而言，若服务器在收到当前领导者的心跳后的最短选举超时时间内收到 RequestVote RPC，则不会更新任期或授予投票。这不会影响正常选举，因为每个服务器在发起选举前至少等待最短选举超时时间。然而，它有助于避免被移除服务器的干扰：若领导者能向集群发送心跳，则不会被更高的任期号罢免。

第12页

7 日志压缩

Raft 的日志在正常操作中会不断增长以容纳更多客户端请求，但在实际系统中，日志不能无限增长。随着日志变长，其占用更多存储空间且重放时间增加，最终可能导致可用性问题。

快照是最简单的日志压缩方法。快照将当前整个系统状态写入稳定存储的快照，然后截断该快照对应位置之前的所有日志。Chubby 和 ZooKeeper 使用快照，本节剩余部分将描述 Raft 的快照机制。

增量压缩方法（如日志清理 [36] 和日志结构合并树 [30, 5]）也可行。这些方法每次操作部分数据，将压缩负载均匀分散到时间中。它们首先选择包含大量已删除或覆盖对象的区域，然后紧凑地重写该区域的存活对象并释放空间。与快照相比，这些方法需要更复杂的机制。尽管日志清理需要对 Raft 进行修改，但状态机可通过与快照相同的接口实现 LSM 树。

图12展示了 Raft 快照的基本思想。每台服务器独立生成快照，仅覆盖其日志中已提交的条目。大部分工作涉及状态机将当前状态写入快照。Raft 还会在快照中包含少量元数据：

  • 最后包含索引（last included index）：快照替代的日志中最后条目的索引（状态机最后应用的条目）；
  • 最后包含任期（last included term）：该条目的任期。
    这些元数据用于支持快照之后首个日志条目的 AppendEntries 一致性检查，因为该条目需要前驱日志索引和任期。为支持集群成员变更（第6节），快照还包含截至最后包含索引时的最新配置。服务器完成快照后，可删除所有早于最后包含索引的日志条目及之前的快照。

尽管服务器通常独立生成快照，但领导者偶尔需要向落后的跟随者发送快照。当领导者已删除需要发送给跟随者的下一个日志条目时，会发生这种情况。幸运的是，这在正常情况下极少发生：保持同步的跟随者已拥有该条目。然而，极慢的跟随者或新加入集群的服务器（第6节）可能缺失这些条目。使此类跟随者同步的方法是领导者通过网络向其发送快照。

领导者使用称为 InstallSnapshot 的新 RPC 向落后过多的跟随者发送快照（见图13）。跟随者收到此 RPC 的快照后，必须决定如何处理现有日志条目。通常，快照包含接收方日志中不存在的新信息。此时，跟随者丢弃整个日志（其全部被快照取代，并可能包含与快照冲突的未提交条目）。若接收方收到的快照描述其日志的前缀（由于重传或错误），则删除快照覆盖的日志条目，但保留之后的条目。

此快照方法偏离了 Raft 的强领导者原则，因为跟随者无需领导者参与即可生成快照。但我们认为这种偏离是合理的。尽管领导者有助于避免共识决策冲突，但生成快照时共识已达成，故无冲突。数据仍仅从领导者流向跟随者，只是跟随者可自行重组数据。

我们曾考虑另一种领导者生成快照后分发的方案，但存在两个缺点：

  1. 浪费带宽：向每个跟随者发送快照会降低效率，而本地生成快照成本更低；
  2. 实现复杂：领导者需在复制新条目时并行发送快照，可能阻塞客户端请求。

快照性能还需考虑两个问题：

  1. 快照时机：当日志达到固定大小时触发快照，大小需显著大于预期快照以减少磁盘开销；
  2. 写入延迟：使用写时复制（如 Linux 的 fork）技术避免快照写入阻塞正常操作。

第13页

8 客户端交互

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

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

Raft 的目标是实现线性一致性语义（每个操作看起来在调用和响应之间的某个瞬时点精确执行一次）。然而，根据目前的描述，Raft 可能多次执行同一命令：例如，如果领导者在提交日志条目后、响应客户端前崩溃，客户端将向新领导者重试该命令，导致命令被第二次执行。解决方案是客户端为每个命令分配唯一的序列号。然后，状态机跟踪每个客户端已处理的最新序列号及对应的响应。如果收到已执行过的序列号对应的命令，状态机直接返回缓存的响应，无需重新执行。

只读操作可以不向日志写入任何内容。但若无额外措施，这可能导致返回过期数据，因为响应请求的领导者可能已被新领导者取代而不自知。线性一致性读取必须返回最新数据，因此 Raft 需要两个额外保障：

  1. 领导者必须知道已提交的最新条目：领导者完全性属性确保领导者拥有所有已提交条目，但在任期开始时，它可能不知道哪些条目已提交。为此，领导者需提交一个当前任期的空白无操作（no-op）条目到日志中。
  2. 处理只读请求前，领导者必须确认自己仍为有效领导者（若新领导者已当选，原领导者的信息可能已过期）。Raft 的处理方式是：领导者在响应只读请求前，需与集群多数交换心跳消息以确认权威。另一种方法是依赖心跳机制实现一种租约[9]，但这需要假设时钟偏差有界。

第14页

9 实现与评估

我们将 Raft 作为 RAMCloud [33] 协调器故障恢复中管理配置信息的复制状态机的一部分实现。Raft 实现包含约 2000 行 C++ 代码（不包括测试、注释或空行），源代码已开源 [23]。此外，已有约 25 个独立的第三方开源实现 [34]，基于本文草稿开发。多家公司正在部署基于 Raft 的系统 [34]。

本节从可理解性、正确性和性能三个维度评估 Raft。

9.1 可理解性

为衡量 Raft 相对于 Paxos 的可理解性，我们在斯坦福大学高级操作系统课程和加州大学伯克利分校分布式计算课程中，针对高年级本科生和研究生进行实验研究。我们录制了关于 Raft 和 Paxos 的讲座视频并设计对应测验。Raft 讲座涵盖本文内容（日志压缩除外）；Paxos 讲座覆盖等价复制状态机所需知识，包括单决策 Paxos、多决策 Paxos、配置变更及实际需要的优化（如领导者选举）。测验测试对算法的基本理解和极端情况推理能力。

每名参与者观看一个视频后完成对应测验，再观看第二个视频并完成另一测验。约半数参与者先学习 Paxos，另一半先学习 Raft，以平衡个体差异和学习顺序影响。我们比较参与者在两个测验中的得分，判断其对 Raft 的理解是否更好。

实验设计偏向 Paxos 的因素包括：43 名参与者中 15 人有 Paxos 先验知识；Paxos 视频时长比 Raft 长 14%。表 1 总结了为减少偏差采取的措施，所有材料可供审查 [31, 28]。

参与者平均在 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 分，虽原因不明但统计显著。

参与者完成测验后，我们调查他们认为哪种算法更易实现或解释。结果如图 15 所示：绝大多数参与者认为 Raft 更易实现和解释（41 人中 33 人）。但自我报告的主观感受可能不如测验得分可靠，且参与者可能受我们假设（Raft 更易理解）的影响。

Raft 用户研究的详细讨论见 [31]。

第15页

9.2 正确性

我们为第 5 节描述的共识机制开发了形式化规范和安全性证明。形式化规范 [31] 使用 TLA+ 规范语言 [17] 精确描述了图 2 的总结，约 400 行代码，既可用于证明，也可辅助实现。我们使用 TLA 证明系统 [7] 对日志完全性属性进行了机械化证明，但该证明依赖未机械化验证的不变量（例如未验证规范的类型安全性）。此外，我们编写了状态机安全性属性的完整非形式化证明 [31]，仅依赖规范本身且相对容易理解。

9.3 性能

Raft 的性能目标是在不影响可理解性的前提下与 Paxos 竞争。我们通过测试 Raft 的领导者选举和复制机制评估性能。结果显示，Raft 在高效性和心跳参数敏感性上与 Paxos 相当。

领导者选举：我们测量崩溃后检测故障并选举新领导者的时间。图 16（上）显示，随机化选举超时可显著减少选票分裂。无随机化时，选举常超 10 秒；引入 5ms 随机化后，中位故障恢复时间为 287ms；50ms 随机化时，最坏情况为 513ms。图 16（下）表明，缩短选举超时可减少故障恢复时间（如 12-24ms 超时下平均 35ms），但过短的超时会违反 Raft 的时序要求，导致不必要的领导者变更。建议使用保守的 150-300ms 超时。

日志复制：Raft 在正常操作中最大化提交吞吐量。使用 1 Gbps、5 节点的千兆网络集群，Raft 的吞吐量接近网络带宽极限（约 200,000 条/秒）。提交延迟由磁盘写入速度主导（约 5ms），远低于 Paxos 的理论下限。

第16页

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]；
  • Oki 和 Liskov 的 Viewstamped Replication (VR)，一种与 Paxos 同期提出的替代共识方法。原始描述 [29] 与分布式事务协议交织，但核心共识协议已在近期更新 [22] 中分离。VR 采用基于领导者的方法，与 Raft 有诸多相似。

Raft 与 Paxos 的最大区别在于强领导机制：Raft 将领导者选举作为共识协议的核心部分，并将尽可能多的功能集中在领导者。这使得算法更简单易懂。例如，Paxos 的领导者选举是独立于基础共识协议的优化，而 Raft 将其作为共识两阶段中的第一阶段。这减少了机制的总量。

与 VR 和 ZooKeeper 相比，Raft 的非领导者节点功能更少。例如，Raft 的日志条目仅通过 AppendEntries RPC 从领导者单向流动；而 VR 的日志条目在选举期间可能双向流动（领导者可接收条目），增加了复杂性。ZooKeeper 的公开描述也允许日志条目双向流动，但实际实现更接近 Raft [35]。

Raft 的消息类型（4 种）远少于其他共识算法。例如，VR 和 ZooKeeper 分别定义了 10 种消息类型用于基础共识和成员变更（不包括日志压缩和客户端交互），而 Raft 仅需 4 种（两种 RPC 请求及响应）。尽管 Raft 的消息内容更密集，但总体更简单。此外，VR 和 ZooKeeper 的描述假设领导者变更时传输完整日志，实际优化需要额外消息类型。

Raft 的强领导机制简化了设计，但牺牲了部分性能优化。例如，Egalitarian Paxos (EPaxos) [27] 在无领导模式下，若并发提议的命令可交换（commutative），则只需一轮通信即可提交。EPaxos 在跨广域网（WAN）部署中能实现更低延迟和更好负载均衡，但显著增加了复杂性。

集群成员变更的多种方法已被提出或实现，包括 Lamport 的原始提案 [15]、VR [22] 和 SMART [24]。Raft 选择联合共识，因其复用现有共识协议机制，仅需极少额外逻辑。Lamport 的 α 方法不适用于 Raft，因其假设无需领导者即可达成共识。与 VR 和 SMART 相比，Raft 的成员变更允许集群在过渡期间持续处理请求，而非停止服务或限制请求数，且实现更简单。

第17页

11 结论

算法设计通常以正确性、效率或简洁性为首要目标。尽管这些目标重要，但我们认为可理解性同等关键。在开发者将算法转化为实际实现之前，其他目标无从谈起。若开发者无法深入理解算法并形成直觉，将难以在实现中保持其理想特性。

本文聚焦分布式共识问题，挑战了广受认可但晦涩难懂的 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 的曝光度。

本研究受以下机构资助：

  • 半导体研究公司（SRC）的 Gigascale 系统研究中心和 Multiscale 系统中心；
  • STARnet（由 MARCO 和 DARPA 资助的 SRC 项目）；
  • 美国国家科学基金会（Grant No. 0963859）；
  • Facebook、Google、Mellanox、NEC、NetApp、SAP 和三星的资助。
    Diego Ongaro 获 Junglee Corporation 斯坦福研究生奖学金支持。

第18页

参考文献

[1] Bolosky, W. J., Bradshaw, D., Haagens, R. B., Kusters, N. P., and Li, P. Paxos 复制的状态机作为高性能数据存储的基础。见《NSDI’11》，2011，USENIX，141-154。
[2] Burrows, M. Chubby：松散耦合分布式系统的锁服务。见《OSDI’06》，2006，USENIX，335-350。
[3] Camargos, L. J., Schmidt, R. M., and Pedone, F. 多协调 Paxos。见《PODC’07》，2007，ACM，316-317。
[4] Chandra, T. D., Griesemer, R., and Redstone, J. Paxos 实现：工程视角。见《PODC’07》，2007，ACM，398-407。
[5] Chang, F., Dean, J., Ghemawat, S., et al. Bigtable：结构化数据的分布式存储系统。见《OSDI’06》，2006，USENIX，205-218。
[6] Corbett, J. C., Dean, J., Epstein, M., et al. Spanner：谷歌的全球分布式数据库。见《OSDI’12》，2012，USENIX，251-264。
[7] Cousineau, D., Doligez, D., Lamport, L., et al. TLA+ 证明。见《FM’12》，2012，Springer，147-154。
[8] Ghemawat, S., Gobioff, H., and Leung, S.-T. 谷歌文件系统。见《SOSP’03》，2003，ACM，29-43。
[9] Gray, C., and Cheriton, D. 租约：分布式文件缓存一致性的高效容错机制。见《SOSP’89》，1989，ACM，202-210。
[10] Herlihy, M. P., and Wing, J. M. 线性一致性：并发对象的正确性条件。《ACM 编程语言与系统汇刊》12（1990），463-492。
[11] Hunt, P., Konar, M., Junqueira, F. P., and Reed, B. ZooKeeper：互联网级系统的无等待协调。见《ATC’10》，2010，USENIX，145-158。
[12] Junqueira, F. P., Reed, B. C., and Serafini, M. Zab：主备系统的高性能广播协议。见《DSN’11》，2011，IEEE，245-256。
[13] Kirsch, J., and Amir, Y. 系统构建者的 Paxos。技术报告 CNDS-2008-2，约翰霍普金斯大学，2008。
[14] Lamport, L. 时间、时钟与分布式系统事件排序。《ACM 通信》21, 7（1978），558-565。
[15] Lamport, L. 兼职议会。《ACM 计算机系统汇刊》16, 2（1998），133-169。
[16] Lamport, L. Paxos 简释。《ACM SIGACT 新闻》32, 4（2001），18-25。
[17] Lamport, L. TLA+ 语言及工具规范系统。Addison-Wesley，2002。
[18] Lamport, L. 广义共识与 Paxos。技术报告 MSR-TR-2005-33，微软研究院，2005。
[19] Lamport, L. 快速 Paxos。《分布式计算》19, 2（2006），79-103。
[20] Lampson, B. W. 如何基于共识构建高可用系统。见《分布式算法》，1996，Springer，1-17。
[21] Lampson, B. W. Paxos 的 ABCD。见《PODC’01》，2001，ACM，13-13。
[22] Liskov, B., and Cowling, J. 视图戳复制再探。技术报告 MIT-CSAIL-TR-2012-021，麻省理工学院，2012。
[23] LogCabin 源代码。http://github.com/logcabin/logcabin。
[24] Lorch, J. R., Adya, A., Bolosky, W. J., et al. 迁移有状态服务的 SMART 方法。见《EuroSys’06》，2006，ACM，103-115。
[25] Mao, Y., Junqueira, F. P., and Marzullo, K. Mencius：面向广域网的高效复制状态机。见《OSDI’08》，2008，USENIX，369-384。
[26] Mazieres, D. 实用的 Paxos。http://www.scs.stanford.edu/~dm/home/papers/paxos.pdf，2007。
[27] Moraru, I., Andersen, D. G., and Kaminsky, M. 平等议会中有更多共识。见《SOSP’13》，2013，ACM。
[28] Raft 用户研究。http://ramcloud.stanford.edu/~ongaro/usersstudy/。
[29] Oki, B. M., and Liskov, B. H. 视图戳复制：支持高可用分布式系统的新主副本方法。见《PODC’88》，1988，ACM，8-17。
[30] O’Neil, P., Cheng, E., Gawlick, D., and O’Neil, E. 日志结构合并树。《Acta Informatica》33, 4（1996），351-385。
[31] Ongaro, D. 共识：连接理论与实践。博士论文，斯坦福大学，2014。http://ramcloud.stanford.edu/~ongaro/thesis.pdf。
[32] Ongaro, D., and Ousterhout, J. 寻找一种可理解的共识算法。见《ATC’14》，2014，USENIX。
[33] Ousterhout, J., Agrawal, P., Erickson, D., et al. RAMCloud 的案例。《ACM 通信》54（2011），121-130。
[34] Raft 共识算法网站。http://raftconsensus.github.io。
[35] Reed, B. 个人通信，2013年5月17日。
[36] Rosenblum, M., and Ousterhout, J. K. 日志结构文件系统的设计与实现。《ACM 计算机系统汇刊》10（1992），26-52。
[37] Schneider, F. B. 使用状态机方法实现容错服务：教程。《ACM 计算调查》22, 4（1990），299-319。
[38] Shvachko, K., Kuang, H., Radia, S., and Chansler, R. Hadoop 分布式文件系统。见《MSST’10》，2010，IEEE，1-10。
[39] van Renesse, R. 适度复杂的 Paxos。技术报告，康奈尔大学，2012。

参考资料

https://chat.deepseek.com/a/chat/s/d74c406e-e486-4ee1-b8da-9274c3cc9419