寻找一种易于理解的共识算法

迭戈·翁加罗（Diego Ongaro）、约翰·奥斯特豪特（John Ousterhout）
斯坦福大学

<https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro>

摘要

Raft是一种用于管理复制日志的共识算法。它的最终效果与（多）Paxos等价，效率也与Paxos相当，但架构与Paxos不同；这使得Raft比Paxos更易于理解，也为构建实际系统提供了更好的基础。为了提升可理解性，Raft将共识的核心要素（如领导者选举、日志复制、安全性）拆分，并通过更强的一致性约束来减少需要考虑的状态数量。用户研究结果表明，Raft比Paxos更易于学生学习。Raft还包含一种全新的集群成员变更机制，该机制利用重叠多数派来保证安全性。

1 引言

共识算法能够让一组机器作为一个协同的整体工作，并且可以在部分成员故障的情况下继续运行。正因如此，共识算法在构建可靠的大规模软件系统中扮演着核心角色。在过去十年中，Paxos[13,14]主导了共识算法的讨论：大多数共识实现都基于Paxos或受其影响，Paxos也成为向学生教授共识知识的主要载体。

不幸的是，尽管人们多次尝试让Paxos更易于理解，但它依然十分晦涩难懂。此外，Paxos的架构需要进行复杂的改造才能支撑实际系统。因此，系统构建者和学生都对Paxos感到头疼。在我们自己也深受Paxos困扰之后，我们决定着手寻找一种新的共识算法，既能为系统构建提供更好的基础，也能更好地服务于教学。

我们的思路不同寻常：我们的首要目标是可理解性——我们能否为实际系统设计一种共识算法，并且用一种比Paxos容易理解得多的方式来描述它？此外，我们希望这种算法能够帮助系统构建者建立直觉认知。不仅算法本身要能正确运行，更要让它的工作原理显而易见。

这项工作的成果就是名为Raft的共识算法。在设计Raft的过程中，我们运用了多种提升可理解性的技术，包括问题分解（Raft将领导者选举、日志复制和安全性拆分）和状态空间约简（与Paxos相比，Raft减少了非确定性程度，也降低了服务器之间状态不一致的可能性）。

针对两所大学43名学生的用户研究显示，Raft的可理解性显著优于Paxos：在学习完两种算法后，其中33名学生回答Raft相关问题的表现优于Paxos。

Raft与现有的共识算法（最著名的是Oki和Liskov提出的视图戳复制（Viewstamped Replication）[27,20]）在很多方面相似，但它具备几个新颖的特性：

强领导者：与其他共识算法相比，Raft采用了更强的领导模式。例如，日志条目仅从领导者流向其他服务器。这简化了复制日志的管理，也让Raft更易于理解。
领导者选举：Raft使用随机计时器来选举领导者。这种方式只在任何共识算法都必需的心跳机制基础上增加了少量机制，却能简单快速地解决选举冲突。
成员变更：Raft的集群服务器集合变更机制采用了一种全新的联合共识方法，在过渡期间，新旧两种配置的多数派相互重叠。这使得集群在配置变更期间仍能正常运行。

我们相信，无论是用于教学还是作为实现基础，Raft都优于Paxos和其他共识算法。它比其他算法更简单、更易理解；它的描述足够完整，能够满足实际系统的需求；它已有多个开源实现，也被多家公司采用；它的安全属性已经过形式化描述和证明；它的效率也与其他算法相当。

本文余下部分安排如下：第2节介绍复制状态机问题；第3节讨论Paxos的优缺点；第4节阐述我们设计可理解性算法的总体思路；第5-7节详细介绍Raft共识算法；第8节对Raft进行评估；第9节讨论相关工作。由于篇幅限制，Raft算法的部分内容未在本文中呈现，可在扩展技术报告[29]中查阅。补充内容包括客户端如何与系统交互，以及如何回收Raft日志的存储空间。

2 复制状态机

共识算法通常诞生于复制状态机[33]的场景下。在这种架构中，一组服务器上的状态机计算出完全相同的状态副本，即使部分服务器宕机，系统仍能继续运行。复制状态机被用于解决分布式系统中的各类容错问题。例如，GFS[7]、HDFS[34]和RAMCloud[30]这类拥有单个集群领导者的大规模系统，通常会使用独立的复制状态机来管理领导者选举，并存储领导者宕机后仍需保留的配置信息。复制状态机的典型例子包括Chubby[2]和ZooKeeper[9]。

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

保证复制日志的一致性是共识算法的核心任务。服务器上的共识模块接收客户端的命令，将其添加到本地日志中。它与其他服务器上的共识模块通信，确保即使部分服务器故障，每份日志最终都会以相同的顺序包含相同的请求。一旦命令被正确复制，每台服务器的状态机就会按日志顺序执行这些命令，并将结果返回给客户端。这样一来，从客户端视角看，这组服务器就像一台单一的、高可靠的状态机。

面向实际系统的共识算法通常具备以下特性：

在所有非拜占庭故障场景下（包括网络延迟、分区、丢包、重复和乱序）都能保证安全性（永远不会返回错误结果）。
只要集群中多数服务器正常运行，且能互相通信、能与客户端通信，系统就完全可用。因此，典型的5服务器集群可以容忍任意2台服务器故障。服务器以停止运行的方式发生故障；它们之后可以从稳定存储中恢复状态，重新加入集群。
不依赖时序来保证日志的一致性：时钟错误和极端的消息延迟最坏只会导致可用性问题，不会影响一致性。
在常规场景下，只要集群多数节点响应了一轮远程过程调用，命令就可以完成；少数慢服务器不会影响整体系统性能。

图1：复制状态机架构。共识算法管理包含客户端状态机命令的复制日志。状态机按日志处理相同的命令序列，因此产生相同的输出。

3 Paxos的问题何在？

在过去十年里，莱斯利·兰伯特（Leslie Lamport）提出的Paxos协议[13]几乎成了共识的代名词：它是课堂上最常教授的协议，也是大多数共识实现的起点。

Paxos首先定义了一种可就单个决策达成一致的协议，比如单条复制日志条目。我们将这一子集称为“单决议Paxos”。然后Paxos通过组合多个该协议实例，来支持一系列决策（比如一整条日志），即“多Paxos”。Paxos既能保证安全性，也能保证可用性，还支持集群成员变更。它的正确性已被证明，常规场景下效率也很高。

不幸的是，Paxos有两个显著的缺陷。
第一个缺陷是，Paxos极其难以理解。完整的原始描述[13]出了名的晦涩难懂；很少有人能完全理解它，即便费尽心力也很难。因此，人们多次尝试用更简单的方式解释Paxos[14,18,19]。这些解释都聚焦于单决议Paxos子集，但依然很难掌握。在2012年NSDI会议参会者的非正式调查中，我们发现即使是资深研究者，也很少有人能熟练掌握Paxos。

我们自己也深受Paxos之苦：直到读了多篇简化解释、并且设计出自己的替代协议之后，我们才理解了完整的协议，这个过程花了将近一年。我们认为，Paxos的晦涩源于它选择了单决议子集作为基础。单决议Paxos内容密集且逻辑微妙：它分为两个阶段，既没有简单直观的解释，也无法独立理解。因此，人们很难建立起“单决议协议为什么能工作”的直觉。而多Paxos的组合规则又带来了大量额外的复杂度和微妙之处。我们相信，针对多决策（即一整条日志而非单个条目）达成共识的整体问题，可以用其他更直接、更清晰的方式分解。

Paxos的第二个问题是，它没有为实际系统的实现提供良好的基础。原因之一是，目前没有被广泛认可的多Paxos算法。Lamport的描述大多围绕单决议Paxos；他勾勒了多Paxos的可能思路，但很多细节都缺失了。人们多次尝试完善和优化Paxos，比如[24][35][11]，但这些实现之间、以及与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节的选举机制增加额外限制。

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

5.1 Raft基础

一个Raft集群包含多台服务器；典型配置是5台，这样系统可以容忍2台故障。在任意时刻，每台服务器都处于三种状态之一：领导者（leader）、跟随者（follower）或候选者（candidate）。正常运行时，有且仅有一个领导者，其余所有服务器都是跟随者。

跟随者是被动的：它们自己不发起任何请求，只是响应领导者和候选者的请求。领导者处理所有客户端请求（如果客户端联系了跟随者，跟随者会将其重定向到领导者）。第三种状态——候选者，用于选举新的领导者，详见第5.2节。图4展示了服务器的状态及其转换关系，下文将讨论这些转换。

Raft将时间划分为任意长度的任期（term），如图5所示。任期用连续的整数编号。每个任期都以选举开始，在选举中，一个或多个候选者尝试成为领导者，如第5.2节所述。如果候选者赢得选举，它就在该任期余下的时间里担任领导者。在某些情况下，选举会出现平票，此时该任期会在没有领导者的情况下结束；很快就会开启新的任期（进行新的选举）。Raft保证在任意一个任期中，最多只有一个领导者。

不同的服务器可能在不同的时间观察到任期转换，在某些场景下，一台服务器可能没有观察到某次选举，甚至整个任期。任期在Raft中充当逻辑时钟[12]的角色，它让服务器能够识别过时的信息，比如过期的领导者。

每台服务器都存储一个当前任期号，该编号随时间单调递增。服务器之间通信时会交换当前任期号；如果一台服务器的当前任期号比另一台小，它就会将自己的当前任期号更新为较大的值。如果候选者或领导者发现自己的任期已经过期，它会立即退回跟随者状态。如果服务器收到一个带有过期任期号的请求，它会拒绝该请求。

Raft服务器通过远程过程调用（RPC）进行通信，而共识算法只需要两种RPC。选举期间由候选者发起RequestVote RPC（第5.2节）；领导者发起AppendEntries RPC，用于复制日志条目，同时也用作心跳（第5.3节）。如果服务器没有及时收到RPC响应，就会重试；为了获得最佳性能，服务器会并行发起RPC。

图2：Raft共识算法精简总结（不包含成员变更和日志压缩）。左上角框中的服务器行为描述为一组独立、可重复触发的规则。§5.2这类章节号表示对应特性的讨论位置。形式化规范[28]对算法的描述更精确。

RequestVote RPC
由候选者调用，用于收集选票（§5.2）。

参数：
- term：候选者的任期
- candidateId：请求选票的候选者ID
- lastLogIndex：候选者最后一条日志条目的索引（§5.4）
- lastLogTerm：候选者最后一条日志条目的任期（§5.4）

返回值：
- term：当前任期，供候选者更新自身
- voteGranted：为true表示候选者获得了选票

接收方执行逻辑：
1. 如果 term < currentTerm，返回false（§5.1）
2. 如果 votedFor 为空或者等于 candidateId，并且候选者的日志至少和接收方的日志一样新，则投出赞成票（§5.2、§5.4）

AppendEntries RPC
由领导者调用，用于复制日志条目（§5.3）；也用作心跳（§5.2）。

参数：
- term：领导者的任期
- leaderId：领导者ID，供跟随者重定向客户端
- prevLogIndex：新条目之前紧邻的那条日志条目的索引
- prevLogTerm：prevLogIndex对应条目的任期
- entries[]：要存储的日志条目（心跳时为空；为了效率可以批量发送多条）
- leaderCommit：领导者的提交索引

返回值：
- term：当前任期，供领导者更新自身
- success：为true表示跟随者包含匹配prevLogIndex和prevLogTerm的条目

接收方执行逻辑：
1. 如果 term < currentTerm，返回false（§5.1）
2. 如果日志中不存在索引为prevLogIndex且任期匹配prevLogTerm的条目，返回false（§5.3）
3. 如果现有条目与新条目冲突（索引相同但任期不同），删除该条目及其之后的所有条目（§5.3）
4. 追加日志中没有的新条目
5. 如果 leaderCommit > commitIndex，令 commitIndex = min(leaderCommit, 最后一条新条目的索引)

所有服务器上的持久化状态：
（响应RPC前更新到稳定存储）
- currentTerm：服务器见过的最新任期（首次启动初始化为0，单调递增）
- votedFor：当前任期中获得选票的候选者ID（无则为null）
- log[]：日志条目；每个条目包含状态机命令，以及领导者接收该条目的任期（第一条索引为1）

所有服务器上的易失状态：
- commitIndex：已知已提交的最高日志条目的索引（初始化为0，单调递增）
- lastApplied：已应用到状态机的最高日志条目的索引（初始化为0，单调递增）

领导者上的易失状态：
（选举后重新初始化）
- nextIndex[]：针对每台服务器，下一个要发送给该服务器的日志条目的索引（初始化为领导者最后一条日志索引+1）
- matchIndex[]：针对每台服务器，已知已复制到该服务器的最高日志条目的索引（初始化为0，单调递增）

服务器行为规则
所有服务器：
- 如果 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）
- 如果最后一条日志索引 ≥ 某跟随者的nextIndex：向该跟随者发送AppendEntries RPC，携带从nextIndex开始的日志条目
  - 如果成功：更新该跟随者的nextIndex和matchIndex（§5.3）
  - 如果AppendEntries因日志不一致失败：递减nextIndex并重试（§5.3）
- 如果存在N满足：N > commitIndex，且多数matchIndex[i] ≥ N，且 log[N].term == currentTerm：设置 commitIndex = N（§5.3、§5.4）

图3：Raft保证以下所有属性始终成立。章节号表示每个属性的讨论位置。

选举安全性：在给定任期中，最多只能选出一个领导者。§5.2
领导者只追加：领导者永远不会覆盖或删除自己日志中的条目，只会追加新条目。§5.3
日志匹配性：如果两份日志中存在索引和任期都相同的条目，那么这两份日志在该索引之前的所有条目都完全相同。§5.3
领导者完备性：如果某条日志条目在给定任期中被提交，那么该条目一定会出现在所有更高任期领导者的日志中。§5.4
状态机安全性：如果一台服务器已经将给定索引的日志条目应用到其状态机，那么其他服务器永远不会在同一索引位置应用不同的日志条目。§5.4.3

图4：服务器状态。跟随者只响应其他服务器的请求。如果跟随者收不到任何通信，它就会成为候选者并发起选举。获得集群多数选票的候选者成为新的领导者。领导者通常会一直运行，直到发生故障。

图5：时间被划分为任期，每个任期都以选举开始。选举成功后，单个领导者管理集群直到任期结束。有些选举会失败，此时任期结束时没有选出领导者。不同服务器可能在不同时间观察到任期转换。

5.2 领导者选举

Raft用心跳机制来触发领导者选举。服务器启动时初始状态都是跟随者。只要能收到来自领导者或候选者的有效RPC，服务器就会保持跟随者状态。领导者会周期性地向所有跟随者发送心跳（不携带日志条目的AppendEntries RPC），以维持自己的权威。

如果跟随者在一段时间（称为选举超时）内没有收到任何通信，它就会认为当前没有可用的领导者，然后发起选举来选出新的领导者。

发起选举时，跟随者先递增自己的当前任期，转为候选者状态。然后它给自己投一票，并向集群中所有其他服务器并行发送RequestVote RPC。候选者会保持该状态，直到发生以下三种情况之一：
(a) 它赢得了选举；
(b) 另一台服务器成为了领导者；
(c) 一段时间过去，没有选出领导者。

下文将分别讨论这几种结果。

候选者如果获得了集群中多数服务器针对同一任期的选票，就赢得了选举。在一个任期中，每台服务器最多只能给一个候选者投票，遵循先到先得的原则（注意：第5.4节对投票增加了额外限制）。多数派原则保证了，在特定任期中最多只有一个候选者能赢得选举（即图3中的选举安全性）。

候选者赢得选举后，就成为领导者。然后它向所有其他服务器发送心跳消息，确立自己的权威，阻止新的选举。

在等待选票的过程中，候选者可能会收到另一台自称领导者的服务器发来的AppendEntries RPC。如果该领导者的任期（包含在RPC中）大于等于候选者的当前任期，那么候选者会承认该领导者的合法性，退回跟随者状态。如果RPC中的任期号小于候选者的当前任期，候选者会拒绝该RPC，继续保持候选者状态。

第三种可能的结果是，候选者既没有赢得选举，也没有输掉选举：如果很多跟随者同时成为候选者，选票就会分散，没有候选者能获得多数。发生这种情况时，每个候选者都会超时，然后通过递增任期、发起新一轮RequestVote RPC来开始新的选举。但是，如果不采取额外措施，平票可能会无限重复下去。

Raft使用随机选举超时来确保平票很少发生，并且能快速解决。为了从根源上避免平票，选举超时时间会在固定区间内随机选择（例如150-300ms）。这样服务器的超时时间就会错开，大多数情况下只有一台服务器会先超时；它赢得选举后，在其他服务器超时之前就会发出心跳。

同样的机制也用于解决平票。每个候选者在选举开始时都会重启随机选举超时，等待超时结束后再开始下一轮选举；这降低了新一轮选举再次出现平票的概率。第8.3节将展示，这种方法可以快速选出领导者。

选举是体现“可理解性如何指导设计选择”的一个例子。最初我们计划使用排名系统：每个候选者被分配一个唯一的排名，用于在竞争的候选者之间做选择。如果一个候选者发现另一个排名更高的候选者，它就退回跟随者状态，这样排名更高的候选者就能更容易赢得下一次选举。但我们发现这种方法会带来一些微妙的可用性问题（排名较低的服务器如果发现排名更高的服务器故障，可能需要超时再次成为候选者，但如果它超时太早，就会重置选举进程）。我们多次调整算法，但每次调整后都会出现新的边界情况。最终我们得出结论，随机重试的方法更直观、更易理解。

5.3 日志复制

选出领导者之后，它就开始处理客户端请求。每个客户端请求都包含一个要由复制状态机执行的命令。领导者将该命令作为新条目追加到自己的日志中，然后向其他每台服务器并行发送AppendEntries RPC来复制该条目。当条目被安全复制后（如下文所述），领导者就会将该条目应用到自己的状态机，并将执行结果返回给客户端。

如果跟随者崩溃、运行缓慢，或者网络丢包，领导者会无限重试AppendEntries RPC（即使已经响应了客户端），直到所有跟随者最终都存储了所有日志条目。

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

领导者决定何时可以安全地将日志条目应用到状态机；这样的条目被称为已提交（committed）。Raft保证已提交的条目是持久的，并且最终会被所有可用的状态机执行。

当创建条目的领导者将该条目复制到了多数服务器上，该日志条目就被提交了（例如图6中的第7条）。这同时也提交了领导者日志中该条目之前的所有条目，包括之前的领导者创建的条目。第5.4节将讨论领导者变更后应用这一规则的一些微妙之处，也会证明这种提交定义是安全的。

领导者会追踪已知已提交的最高索引，并且会在后续的AppendEntries RPC（包括心跳）中携带这个索引，这样其他服务器最终都会得知。一旦跟随者得知某条日志条目已提交，它就会按日志顺序将该条目应用到本地状态机。

我们设计Raft日志机制的目标，是在不同服务器的日志之间维持高度的一致性。这不仅简化了系统行为、让结果更可预测，也是保证安全性的重要组成部分。

Raft维持以下属性，它们共同构成了图3中的日志匹配属性：

如果不同日志中的两个条目拥有相同的索引和任期，那么它们存储的是相同的命令。
如果不同日志中的两个条目拥有相同的索引和任期，那么它们之前的所有条目都完全相同。

第一个属性源于这样一个事实：领导者在一个任期中，针对一个日志索引最多只会创建一个条目，并且日志条目在日志中的位置永远不会改变。

第二个属性由AppendEntries执行的简单一致性检查来保证。领导者发送AppendEntries RPC时，会带上新条目之前紧邻的那条日志条目的索引和任期。如果跟随者在自己的日志中找不到相同索引和任期的条目，它就会拒绝新的条目。

一致性检查相当于归纳步骤：日志的初始空状态满足日志匹配属性，而每次扩展日志时，一致性检查都会保持日志匹配属性。因此，只要AppendEntries返回成功，领导者就知道跟随者的日志与自己的日志，在新条目之前的部分是完全一致的。

在正常运行中，领导者和跟随者的日志保持一致，因此AppendEntries的一致性检查永远不会失败。但是，领导者崩溃可能会导致日志不一致（旧领导者可能没有完全复制完它日志中的所有条目）。经过多次领导者和跟随者崩溃后，这些不一致可能会累积。图7展示了跟随者的日志与新领导者的日志可能存在差异的各种情况。跟随者可能缺少领导者有的条目，也可能有领导者没有的多余条目，或者两者都有。日志中缺失和多余的条目可能跨越多个任期。

在Raft中，领导者通过强制跟随者复制自己的日志，来处理不一致问题。这意味着跟随者日志中冲突的条目会被领导者日志中的条目覆盖。第5.4节将说明，结合另一条限制，这种做法是安全的。

图6：日志由按顺序编号的条目组成。每个条目包含它被创建时的任期（每个方框中的数字），以及一条状态机命令。如果某条日志条目可以安全地应用到状态机，就称它是已提交的。

图7：当顶部的领导者上台时，跟随者的日志可能出现(a-f)中的任意一种情况。每个方框代表一条日志条目，方框内的数字是它的任期。跟随者可能缺少条目(a-b)，可能有多余的未提交条目(c-d)，或者两者兼有(e-f)。例如，场景(f)可能是这样发生的：该服务器在任期2时是领导者，向日志中添加了几条条目，还没来得及提交就崩溃了；它很快重启，在任期3又成为领导者，又向日志添加了几条条目；在任期2和任期3的条目都还没提交时，服务器再次崩溃，并且宕机了好几个任期。

为了让跟随者的日志与自己的一致，领导者必须找到两份日志最新的一致位置，删除跟随者日志中该位置之后的所有条目，然后将自己该位置之后的所有条目发送给跟随者。这些操作都是在响应AppendEntries RPC的一致性检查时自动完成的。

领导者为每个跟随者维护一个nextIndex，表示下一个要发送给该跟随者的日志条目的索引。领导者刚上台时，会将所有nextIndex值初始化为自己日志最后一条的下一个索引（图7中是11）。如果跟随者的日志与领导者不一致，下一次AppendEntries RPC的一致性检查就会失败。遭到拒绝后，领导者会递减nextIndex，然后重试AppendEntries RPC。最终nextIndex会降到领导者和跟随者日志匹配的位置。此时AppendEntries就会成功，同时移除跟随者日志中冲突的条目，并追加领导者日志中的条目（如果有的话）。一旦AppendEntries成功，跟随者的日志就与领导者的一致了，并且在该任期余下的时间里都会保持一致。

该协议可以优化，减少被拒绝的AppendEntries RPC次数；详见[29]。

有了这种机制，领导者上台时不需要采取任何特殊操作来恢复日志一致性。它只需要开始正常运行，日志就会在AppendEntries一致性检查失败的驱动下自动收敛。领导者永远不会覆盖或删除自己日志中的条目（图3中的领导者只追加属性）。

这种日志复制机制具备第2节所述的理想共识特性：只要多数服务器正常运行，Raft就可以接收、复制和应用新的日志条目；常规场景下，只需要一轮RPC就能将新条目复制到集群多数节点；单个慢跟随者不会影响整体性能。

5.4 安全性

前面几节介绍了Raft如何选举领导者、如何复制日志条目。但是，目前描述的机制还不足以保证每个状态机都按完全相同的顺序执行完全相同的命令。例如，某个跟随者可能在领导者提交多条日志条目期间不可用，之后它被选为领导者，用新的条目覆盖了这些已提交条目；结果就是不同的状态机可能执行不同的命令序列。

本节通过对“哪些服务器可以被选为领导者”增加限制，来完善Raft算法。该限制保证了，任意任期的领导者都包含了之前所有任期提交的所有条目（即图3中的领导者完备性）。有了选举限制之后，我们再进一步明确提交规则。最后，我们给出领导者完备性的证明概要，并说明它如何保证复制状态机的正确行为。

5.4.1 选举限制

在任何基于领导者的共识算法中，领导者最终必须存储所有已提交的日志条目。在某些共识算法中，比如视图戳复制[20]，即使领导者最初不包含所有已提交条目，也可以被选出来。这些算法有额外的机制来识别缺失的条目，并在选举过程中或选举后不久将其传输给新领导者。不幸的是，这会带来大量额外的机制和复杂度。

Raft采用了一种更简单的方法：它保证从选举产生的那一刻起，每个新领导者就包含了之前所有任期的已提交条目，不需要再向领导者传输这些条目。这意味着日志条目只朝一个方向流动，从领导者流向跟随者，并且领导者永远不会覆盖自己日志中已有的条目。

Raft通过投票流程来实现这一点：除非候选者的日志包含了所有已提交条目，否则它无法赢得选举。候选者必须联系集群中的多数节点才能当选，这意味着每个已提交条目都至少存在于这些节点中的某一台上。如果候选者的日志至少和该多数派中任意一台的日志一样新（“最新”的精确定义见下文），那么它就包含了所有已提交条目。

RequestVote RPC实现了这一限制：RPC中包含候选者的日志信息，如果投票者自己的日志比候选者的更新，它就会拒绝投票。

Raft通过比较两份日志最后条目的索引和任期，来判断哪份日志更新。

如果两份日志的最后条目任期不同，那么任期更大的日志更新。
如果两份日志最后条目的任期相同，那么日志更长的那个更新。

5.4.2 提交之前任期的日志条目

如第5.3节所述，领导者只要将当前任期的条目复制到多数服务器上，就知道该条目已提交。如果领导者在提交条目之前崩溃，未来的领导者会尝试继续完成该条目的复制。但是，领导者不能仅凭“之前任期的条目被复制到了多数服务器上”，就断定该条目已提交。

图8展示了一种情况：一条旧的日志条目已经存储在多数服务器上，但仍然可能被未来的领导者覆盖。为了避免这类问题，Raft永远不会通过统计副本数的方式来提交之前任期的日志条目。只有领导者当前任期的条目，才通过统计副本数来提交；一旦当前任期的条目以这种方式提交，那么由于日志匹配属性，它之前的所有条目都会被间接提交。

在某些情况下，领导者可以安全地断定旧日志条目已提交（例如，该条目存储在所有服务器上），但Raft为了简单起见，采用了更保守的方式。

Raft的提交规则之所以有这种额外复杂度，是因为领导者复制之前任期的条目时，会保留条目的原始任期号。在其他共识算法中，如果新领导者重新复制之前“任期”的条目，必须使用新的“任期号”。Raft的方法让日志条目更容易推理，因为它们在不同时间、不同服务器的日志中都保持相同的任期号。此外，与其他算法相比，Raft中的新领导者需要发送的旧任期日志条目更少（其他算法必须重新发送冗余条目并重编号，才能提交它们）。

图8：时序图说明为什么领导者不能用旧任期的日志条目来判定提交。在(a)中，S1是领导者，部分复制了索引2的日志条目。在(b)中，S1崩溃；S5在S3、S4和自己的投票下当选为任期3的领导者，并在索引2位置接收了一条不同的条目。在(c)中，S5崩溃；S1重启后当选为领导者，继续复制。此时，任期2的日志条目已经复制到了多数服务器上，但它并没有被提交。如果S1像(d)中那样崩溃，S5可以当选为领导者（获得S2、S3、S4的选票），并用自己任期3的条目覆盖该条目。但是，如果S1在崩溃前，将当前任期的条目复制到了多数服务器上，如(e)所示，那么该条目就被提交了（此时S5无法赢得选举）。到这时，日志中该条目之前的所有条目也都被提交了。

5.4.3 安全性论证

有了完整的Raft算法，我们现在可以更严谨地论证领导者完备性成立（该论证基于安全性证明，见第8.2节）。我们采用反证法：假设领导者完备性不成立，然后推导出矛盾。

假设任期T的领导者（leaderT）提交了一条本任期的日志条目，但该条目没有出现在某个未来任期的领导者日志中。设U是大于T的最小任期，其领导者（leaderU）的日志中不包含该条目。

该已提交条目在leaderU当选时，一定不在它的日志中（领导者永远不会删除或覆盖条目）。
leaderT将该条目复制到了集群的多数节点，而leaderU获得了集群多数节点的选票。因此，至少有一台服务器（“投票者”）既接受了leaderT的该条目，又投票给了leaderU，如图9所示。这台投票者是导出矛盾的关键。
投票者一定是在投票给leaderU之前，就接受了leaderT的已提交条目；否则它会拒绝leaderT的AppendEntries请求（因为它的当前任期会比T更高）。
投票者在投票给leaderU时，仍然存储着该条目；因为根据假设，中间所有任期的领导者都包含该条目，而领导者永远不会移除条目，跟随者只会在与领导者冲突时才移除条目。
投票者把票投给了leaderU，因此leaderU的日志一定至少和投票者的日志一样新。这会导出两种矛盾情况之一。
第一种情况：如果投票者和leaderU的最后日志任期相同，那么leaderU的日志至少和投票者的一样长，因此它的日志包含投票者日志中的所有条目。这就矛盾了，因为投票者包含该已提交条目，而假设leaderU不包含。
另一种情况：leaderU的最后日志任期一定比投票者的大。而且，它比T大，因为投票者的最后日志任期至少是T（它包含任期T的已提交条目）。创建leaderU最后那条日志条目的前任领导者，根据假设一定包含该已提交条目。那么根据日志匹配属性，leaderU的日志也一定包含该已提交条目，这就矛盾了。
至此矛盾得证。因此，所有任期大于T的领导者，都一定包含任期T中提交的所有条目。
日志匹配属性保证了，未来的领导者也会包含间接提交的条目，比如图8(d)中的索引2。

有了领导者完备性，就很容易证明图3中的状态机安全属性，以及所有状态机都会按相同顺序执行相同的日志条目（见[29]）。

图9：如果任期T的领导者S1提交了一条新的日志条目，而S5当选为更晚任期U的领导者，那么至少有一台服务器（S3）既接受了该日志条目，又投票给了S5。

5.5 跟随者与候选者崩溃

到目前为止，我们都在讨论领导者故障。跟随者和候选者崩溃的处理比领导者崩溃简单得多，并且两者的处理方式相同。

如果跟随者或候选者崩溃，那么之后发给它的RequestVote和AppendEntries RPC都会失败。Raft通过无限重试来处理这些故障；如果崩溃的服务器重启了，RPC就会成功完成。如果服务器在完成RPC之后、响应之前崩溃，那么它重启后会再次收到相同的RPC。Raft的RPC都是幂等的，因此这不会造成任何问题。例如，如果跟随者收到的AppendEntries请求中包含已经存在于日志中的条目，它会忽略新请求中的这些条目。

5.6 时序与可用性

我们对Raft的要求之一是，安全性不能依赖时序：系统不会因为事件发生得比预期更快或更慢，就产生错误结果。但是，可用性（系统及时响应客户端的能力）必然依赖于时序。例如，如果消息交换的时间比服务器故障的平均间隔还长，候选者就来不及赢得选举；没有稳定的领导者，Raft就无法推进工作。

领导者选举是Raft中时序最关键的部分。只要系统满足以下时序要求，Raft就能选出并维持稳定的领导者：

广播时间 ≪ 选举超时 ≪ 平均故障间隔时间

其中：

广播时间：服务器向集群中所有服务器并行发送RPC并收到响应的平均时间；
选举超时：第5.2节所述的选举超时时间；
平均故障间隔时间（MTBF）：单台服务器的平均故障间隔时间。

广播时间应该比选举超时小一个数量级，这样领导者才能可靠地发送心跳消息，避免跟随者发起选举；考虑到选举超时的随机化机制，这个不等式也能降低平票的可能性。选举超时应该比平均故障间隔时间小几个数量级，这样系统才能稳定推进工作。领导者崩溃时，系统会在大约一个选举超时的时间内不可用；我们希望这段时间只占总运行时间的很小一部分。

广播时间和平均故障间隔时间是底层系统的属性，而选举超时是我们可以选择的参数。Raft的RPC通常需要接收方将信息持久化到稳定存储中，因此广播时间根据存储技术不同，可能在0.5ms到20ms之间。因此，选举超时通常设置在10ms到500ms之间。典型的服务器平均故障间隔时间是数月甚至更久，很容易满足时序要求。

6 集群成员变更

到目前为止，我们都假设集群配置（参与共识算法的服务器集合）是固定的。但在实际中，偶尔需要变更配置，比如服务器故障时替换，或者改变副本数量。

虽然可以通过让整个集群下线、更新配置文件、再重启集群的方式来做，但这样会导致变更期间集群不可用。此外，如果存在人工步骤，还会有操作失误的风险。为了避免这些问题，我们决定将配置变更自动化，并融入Raft共识算法中。

要保证配置变更机制的安全，过渡期间不能出现同一任期选出两个领导者的情况。不幸的是，任何让服务器直接从旧配置切换到新配置的方案都是不安全的。不可能让所有服务器同时原子切换，因此过渡期间集群可能分裂成两个独立的多数派，如图10所示。

为了保证安全，配置变更必须采用两阶段方案。实现两阶段的方式有很多种。例如，有些系统（比如[20]）在第一阶段禁用旧配置，让它无法处理客户端请求；然后第二阶段启用新配置。

在Raft中，集群首先切换到一种过渡配置，我们称之为联合共识（joint consensus）；一旦联合共识被提交，系统再切换到新配置。

联合共识结合了新旧两种配置：

日志条目会被复制到两种配置的所有服务器。
两种配置中的任意服务器都可以担任领导者。
选举和条目提交需要同时得到旧配置和新配置的各自多数派同意。

联合共识允许各服务器在不同时间切换配置，且不会牺牲安全性。此外，联合共识让集群在整个配置变更期间都能继续处理客户端请求。

集群配置通过复制日志中的特殊条目来存储和传递；图11展示了配置变更的流程。当领导者收到将配置从Cold变更为Cnew的请求时，它将联合共识配置（图中的Cold,new）作为日志条目存储起来，并用前述的机制复制该条目。

一旦某台服务器将新的配置条目追加到自己的日志中，它就会使用该配置来进行所有后续决策（服务器总是使用日志中最新的配置，不管该条目是否已提交）。这意味着，领导者会使用Cold,new的规则来判断Cold,new这条日志条目何时被提交。

如果领导者崩溃，新领导者可能是在Cold配置下选出的，也可能是在Cold,new配置下选出的，这取决于赢得选举的候选者是否已经收到了Cold,new条目。无论如何，在这个阶段，Cnew都不能单方面做出决策。

一旦Cold,new被提交，Cold和Cnew都无法在不经对方同意的情况下做出决策，并且领导者完备性保证了，只有拥有Cold,new日志条目的服务器才能当选为领导者。此时，领导者就可以创建描述Cnew的日志条目，并复制到集群中。同样，该配置一旦被服务器看到就立即生效。当新配置在Cnew的规则下被提交后，旧配置就不再相关，不在新配置中的服务器可以关闭。

如图11所示，不存在Cold和Cnew都能独立做出决策的时间点；这保证了安全性。

图10：直接从一种配置切换到另一种是不安全的，因为不同服务器切换的时间不同。本例中，集群从3台服务器扩容到5台。不幸的是，在某个时间点，可能会有两个不同的领导者在同一任期当选，一个基于旧配置（Cold）的多数派，另一个基于新配置（Cnew）的多数派。

图11：配置变更时间线。虚线表示已创建但未提交的配置条目，实线表示最新的已提交配置条目。领导者首先在日志中创建Cold,new配置条目，并将其提交到Cold,new（需要Cold的多数派和Cnew的多数派）。然后它创建Cnew条目，并提交到Cnew的多数派。整个过程中，不存在Cold和Cnew都能独立决策的时间点。

配置变更还有三个问题需要解决。

第一个问题是，新加入的服务器可能初始没有任何日志条目。如果它们以这种状态加入集群，可能需要很长时间才能追上，在此期间可能无法提交新的日志条目。为了避免可用性缺口，Raft在配置变更之前引入了一个额外阶段：新服务器以非投票成员的身份加入集群（领导者向它们复制日志条目，但计算多数派时不考虑它们）。一旦新服务器追上了集群的其他服务器，就可以按上述流程进行配置变更。

第二个问题是，集群领导者可能不在新配置中。这种情况下，领导者在提交Cnew日志条目后，就会卸任（退回跟随者状态）。这意味着，在提交Cnew的这段时间里，领导者管理着一个不包含自己的集群；它复制日志条目，但计算多数派时不算自己。领导者会在Cnew提交时完成交接，因为这是新配置可以独立运行的第一个时间点（此时总能从Cnew中选出领导者）。在此之前，可能只有Cold中的服务器才能当选为领导者。

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

为了解决这个问题，当服务器认为当前存在领导者时，会忽略RequestVote RPC。具体来说，如果服务器在收到领导者心跳后的最小选举超时时间内收到RequestVote RPC，它不会更新自己的任期，也不会投票。

这不会影响正常选举，因为正常选举中每台服务器至少会等待一个最小选举超时时间才会发起选举。但它能有效避免被移除服务器的干扰：只要领导者能给集群发送心跳，就不会被更高的任期号推翻。

7 客户端与日志压缩

由于篇幅限制，本节内容已省略，相关材料可在论文扩展版[29]中查阅。该部分描述了客户端如何与Raft交互，包括客户端如何找到集群领导者，以及Raft如何支持线性化语义[8]。扩展版还描述了如何通过快照方式回收复制日志的存储空间。这些问题适用于所有基于共识的系统，Raft的解决方案与其他系统类似。

8 实现与评估

我们将Raft实现为一个复制状态机的一部分，该状态机用于存储RAMCloud[30]的配置信息，并协助RAMCloud协调器的故障转移。Raft实现包含大约2000行C++代码，不包括测试、注释和空行。源代码开源可获取[21]。此外，基于本文草稿，还有约25个独立的第三方开源实现[31]，处于不同的开发阶段。多家公司也在部署基于Raft的系统[31]。

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

8.1 可理解性

为了衡量Raft相对于Paxos的可理解性，我们用斯坦福大学高级操作系统课程和加州大学伯克利分校分布式计算课程的高年级本科生和研究生进行了实验研究。

我们录制了Raft和Paxos的教学视频，并制作了对应的测试题。Raft的视频涵盖了本文的内容；Paxos的视频涵盖了构建等效复制状态机所需的足够内容，包括单决议Paxos、多决议Paxos、配置变更，以及一些实际中需要的优化（比如领导者选举）。测试题既考察对算法的基本理解，也要求学生分析边界情况。

每个学生先观看一个视频，完成对应的测试，再观看第二个视频，完成第二个测试。大约一半参与者先学Paxos部分，另一半先学Raft部分，这样既可以区分个体能力差异，也可以控制学习顺序带来的经验影响。我们比较参与者在两项测试中的得分，判断他们是否对Raft理解得更好。

我们尽可能让Paxos和Raft的对比公平。实验在两方面对Paxos更有利：43名参与者中有15人表示有一定的Paxos使用经验，并且Paxos的视频比Raft的长14%。如表1所示，我们采取了多种措施来降低潜在的偏差。所有材料都可以公开查阅[26,28]。

平均而言，参与者的Raft测试得分比Paxos高4.9分（满分60分，Raft平均25.7分，Paxos平均20.8分）；图12展示了每个人的得分情况。配对t检验显示，在95%置信度下，Raft得分的真实均值至少比Paxos高2.5分。

我们还建立了一个线性回归模型，基于三个因素预测学生的测试得分：测试的算法类型、之前的Paxos经验程度、学习算法的顺序。模型预测，仅算法选择这一项，Raft就比Paxos高出12.5分。这个数值比观测到的4.9分差异大很多，因为很多实际学生有Paxos经验，这大幅提升了他们的Paxos成绩，而对Raft的提升较小。有意思的是，模型还预测，先学过Paxos的人，Raft得分会低6.3分；虽然我们不清楚原因，但这一结果在统计上是显著的。

我们还在测试后调查了参与者，询问他们觉得哪种算法更容易实现或解释；结果如图13所示。绝大多数参与者认为Raft更容易实现和解释（两个问题分别都是41人中的33人）。不过，这种自我报告的感受可能不如测试得分可靠，而且参与者可能因为知道我们“Raft更易理解”的假设而产生偏差。关于Raft用户研究的详细讨论见[28]。

表1：研究中可能对Paxos不利的偏差顾虑、对应的缓解措施，以及可查阅的补充材料。

顾虑	采取的缓解措施	可查阅材料
讲解质量一致	两个算法由同一位讲师讲解。Paxos的讲解基于多所大学使用的现有材料并做了改进。Paxos视频时长更长14%。	视频[26,28]
测试难度相当	题目按难度分组，在两份试卷中配对。	测试题[26,28]
评分公平	使用评分标准。随机顺序批改，两份试卷交替批改。	评分标准[26,28]

图12：43名参与者在Raft和Paxos测试中得分的散点图。对角线上方的点（33个）代表Raft得分更高的参与者。

图13：使用5分量表，参与者被问及（左）哪种算法更容易在一个功能正常、正确且高效的系统中实现，（右）哪种更容易向计算机科学研究生解释。

8.2 正确性

我们为第5节描述的共识机制建立了形式化规范和安全性证明。形式化规范[28]使用TLA+规范语言[15]，将图2总结的信息完全精确化。规范大约400行，本身也是证明的主体。对于实现Raft的人来说，它本身也很有参考价值。

我们使用TLA证明系统[6]，机械证明了日志完备性属性。不过，该证明依赖的一些不变量还没有经过机械检查（例如，我们还没有证明规范的类型安全性）。此外，我们还撰写了状态机安全属性的非形式化证明[28]，证明是完整的（仅依赖规范本身），也相对严谨（大约3500词）。

8.3 性能

Raft的性能与Paxos等其他共识算法相近。性能最重要的场景是，稳定的领导者复制新的日志条目。Raft仅用最少的消息数就能完成（领导者到集群半数节点的一轮往返）。

Raft的性能还有进一步提升的空间。例如，它可以很容易地支持请求批处理和流水线，以获得更高吞吐量和更低延迟。文献中提出了很多针对其他算法的优化，其中很多都可以应用到Raft上，我们将在未来工作中展开。

我们用自己的Raft实现测试了领导者选举算法的性能，回答两个问题：第一，选举过程收敛快吗？第二，领导者崩溃后的最小停机时间是多少？

为了测试领导者选举，我们反复让5节点集群的领导者崩溃，计时检测崩溃并选出新领导者的时间（见图14）。为了构造最坏情况，每次实验中服务器的日志长度都不同，因此有些候选者没有资格成为领导者。此外，为了增加平票的可能性，我们的测试脚本在终止领导者进程前，会让它同步广播一次心跳RPC（这近似于领导者在崩溃前正在复制新日志条目的行为）。领导者在其心跳间隔内均匀随机崩溃，而心跳间隔是所有测试中最小选举超时的一半。因此，最小的停机时间大约是最小选举超时的一半。

图14的上图显示，选举超时中加入少量随机性，就足以避免选举平票。在没有随机性的情况下，由于多次平票，领导者选举的耗时始终超过10秒。仅增加5ms的随机性就有显著效果，中位停机时间降到287ms。增加更多随机性可以改善最坏情况：随机性为50ms时，（1000次实验中）最坏情况的完成时间是513ms。

图14的下图显示，缩短选举超时可以减少停机时间。选举超时为12-24ms时，平均仅需35ms就能选出领导者（最长的实验用了152ms）。但是，超时时间再缩短就会违反Raft的时序要求：领导者还没来得及广播心跳，其他服务器就开始新的选举了。这会导致不必要的领导者变更，降低整体系统可用性。

我们建议使用保守的选举超时，比如150-300ms；这样的超时时间不太可能导致不必要的领导者变更，同时也能提供很好的可用性。

图14：检测并替换崩溃领导者的时间。上图改变选举超时的随机程度，下图调整最小选举超时。每条线代表1000次实验（“150–150ms”为100次），对应一种选举超时配置；例如“150–155ms”表示选举超时在150ms到155ms之间随机均匀选取。测试在5台服务器的集群上进行，广播时间约为15ms。9台服务器的集群结果类似。

9 相关工作

已经有大量关于共识算法的研究，很多都属于以下几类：

Lamport对Paxos的原始描述[13]，以及尝试更清晰解释它的工作[14,18,19]。
Paxos的细化工作，补充缺失的细节并修改算法，为实现提供更好的基础[24,35,11]。
实现共识算法的系统，比如Chubby[2,4]、ZooKeeper[9,10]和Spanner[5]。Chubby和Spanner的算法没有详细公开，但都声称基于Paxos。ZooKeeper的算法公开得更详细，但与Paxos差异很大。
可应用于Paxos的性能优化[16,17,3,23,1,25]。
Oki和Liskov的视图戳复制（VR），一种与Paxos同期提出的共识替代方案。原始描述[27]与分布式事务协议结合在一起，但核心共识协议在最近的更新中被独立出来[20]。VR采用基于领导者的方法，与Raft有很多相似之处。

Raft与Paxos最大的区别在于Raft的强领导模式：Raft将领导者选举作为共识协议的核心部分，并且尽可能多地将功能集中到领导者身上。这种方法带来了更简单、更易理解的算法。

例如，在Paxos中，领导者选举与基本共识协议是正交的：它只是性能优化，并不是达成共识的必要条件。但这带来了额外的机制：Paxos既包含用于基本共识的两阶段协议，也包含独立的领导者选举机制。相比之下，Raft将领导者选举直接融入共识算法，作为共识的两个阶段中的第一阶段。这使得整体机制比Paxos更少。

和Raft一样，VR和ZooKeeper也是基于领导者的，因此具备很多Raft相对于Paxos的优势。但是，Raft的机制比VR或ZooKeeper更少，因为它最小化了非领导者节点的功能。例如，Raft中的日志条目只朝一个方向流动：通过AppendEntries RPC从领导者向外流出。而在VR中，日志条目是双向流动的（领导者在选举过程中也可以接收日志条目）；这带来了额外的机制和复杂度。ZooKeeper的公开描述中，日志条目也是双向传输的，但它的实际实现显然更接近Raft[32]。

据我们所知，在所有基于共识的日志复制算法中，Raft的消息类型最少。例如，VR和ZooKeeper都定义了10种不同的消息类型，而Raft只有4种（两种RPC请求和它们的响应）。Raft的单条消息信息量比其他算法稍大，但整体更简单。此外，VR和ZooKeeper的描述中，领导者变更时需要传输完整日志；要优化这些机制使其实用，还需要额外的消息类型。

其他研究中提出或实现了多种集群成员变更方法，包括Lamport的原始方案[13]、VR[20]和SMART[22]。我们为Raft选择联合共识方法，是因为它可以复用共识协议的其余部分，因此成员变更只需要很少的额外机制。Lamport的基于α的方法不适用于Raft，因为它假设不需要领导者也能达成共识。

与VR和SMART相比，Raft的重配置算法的优势在于，成员变更期间不会限制正常请求的处理；相比之下，VR在配置变更期间会停止所有正常处理，而SMART对未完成请求的数量施加了类似α的限制。Raft的方法也比VR或SMART增加的机制更少。

10 结论

算法设计通常以正确性、效率和/或简洁性为首要目标。尽管这些都是值得追求的目标，但我们认为可理解性同样重要。在开发者将算法落地为实际实现之前，所有其他目标都无从谈起，而实际实现不可避免地会偏离并扩展公开的算法描述。除非开发者对算法有深刻理解、能建立起直觉，否则很难在实现中保留算法的优良特性。

本文针对分布式共识问题展开研究——在这个领域，Paxos作为被广泛接受却晦涩难懂的算法，已经困扰了学生和开发者很多年。我们开发了一种新的算法Raft，并证明它比Paxos更易于理解。我们也相信，Raft为系统构建提供了更好的基础。

将可理解性作为首要设计目标，改变了我们设计Raft的思路；在设计过程中，我们反复用到了一些技术，比如问题分解和状态空间简化。这些技术不仅提升了Raft的可理解性，也让我们更容易确信它的正确性。

11 致谢

如果没有Ali Ghodsi、David Mazières，以及伯克利CS 294-91课程和斯坦福CS 240课程的同学们，用户研究不可能完成。Scott Klemmer帮助我们设计了用户研究，Nelson Ray为统计分析提供了建议。用户研究中使用的Paxos幻灯片大量借鉴了Lorenzo Alvisi最初创建的演示文稿。特别感谢David Maziè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获得了大量关注。

本研究得到了千兆级系统研究中心和多尺度系统中心的支持——这两个中心是聚焦中心研究计划（半导体研究公司项目）下设的六个研究中心之二；同时也得到了STARnet（由MARCO和DARPA赞助的半导体研究公司项目）、美国国家科学基金会（资助号0963859），以及Facebook、Google、Mellanox、NEC、NetApp、SAP、三星的资助。Diego Ongaro得到了Junglee公司斯坦福研究生奖学金的支持。

参考文献

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

[2] BURROWS, M. The Chubby lock service for loosely-coupled distributed systems. In Proc. OSDI’06, 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] 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.

[6] 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éry, Eds., vol. 7436 of Lecture Notes in Computer Science, Springer, pp. 147–154.

[7] 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.

[8] 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.

[9] 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.

[10] 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.

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

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

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

[14] LAMPORT, L. Paxos made simple. ACM SIGACT News 32, 4 (Dec. 2001), 18–25.

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

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

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

[18] 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.

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

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

[21] LogCabin source code. <http://github.com/logcabin/logcabin>.

[22] 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.

[23] 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.

[24] MAZIÈRES, D. Paxos made practical. <http://www.scs.stanford.edu/~dm/home/papers/paxos.pdf>, Jan. 2007.

[25] 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.

[26] Raft user study. <http://ramcloud.stanford.edu/~ongaro/userstudy/>.

[27] 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.

[28] ONGARO, D. Consensus: Bridging Theory and Practice. PhD thesis, Stanford University, 2014 (work in progress). <http://ramcloud.stanford.edu/~ongaro/thesis.pdf>.

[29] ONGARO, D., AND OUSTERHOUT, J. In search of an understandable consensus algorithm (extended version). <http://ramcloud.stanford.edu/raft.pdf>.

[30] OUSTERHOUT, J., AGRAWAL, P., ERICKSON, D., KOZYRAKIS, C., LEVERICH, J., MAZIÈ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.

[31] Raft consensus algorithm website. <http://raftconsensus.github.io>.

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

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

[34] 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.

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

【转载】寻找一种易于理解的共识算法