Raft算法是可以用来替代Paxos算法的分布式一致性算法，而且raft算法比Paxos算法更易懂且更容易实现。本文对raft论文进行翻译，希望能有助于读者更方便地理解raft的思想。
摘要
Raft是用来管理复制日志（replicatedlog）的一致性协议。它跟multi-Paxos作用相同，效率也相当，但是它的组织结构跟Paxos不同。这使得Raft比Paxos更容易理解并且更容易在工程实践中实现。为了使Raft协议更易懂，Raft将一致性的关键元素分开，如leader选举、日志复制和安全性，并且它实施更强的一致性以减少必须考虑的状态的数量。用户研究的结果表明，Raft比Paxos更容易学习。Raft还包括一个用于变更集群成员的新机制，它使用重叠的大多数（overlappingmajorities）来保证安全性。
1介绍
一致性算法允许多台机器作为一个集群协同工作，并且在其中的某几台机器出故障时集群仍然能正常工作。正因为如此，一致性算法在建立可靠的大规模软件系统方面发挥了关键作用。在过去十年中，Paxos[15,16]主导了关于一致性算法的讨论：大多数一致性的实现都是基于Paxos或受其影响，Paxos已成为用于教授学生一致性相关知识的主要工具。
不幸的是，Paxos实在是太难以理解，尽管许多人一直在努力尝试使其更易懂。此外，其架构需要复杂的改变来支持实际系统。结果是，系统开发者和学生都在与Paxos斗争。
在我们自己与Paxos斗争之后，我们开始着手寻找一个新的一致性算法，可以为系统开发和教学提供更好的基础。我们的方法是不寻常的，因为我们的主要目标是可理解性：我们可以为实际系统定义一个一致性算法，并以比Paxos更容易学习的方式描述它吗？在该算法的设计过程中，重要的不仅是如何让该算法起作用，还有清晰地知道该算法为什么会起作用。
这项工作的结果是一个称为Raft的一致性算法。在设计Raft时，我们使用了特定的技术来提高可理解性，包括分解（Raft分离leader选举，日志复制和安全）和状态空间减少（相对于Paxos，Raft减少了不确定性程度和服务器之间彼此不一致的方式）。一项针对两个大学的43名学生的用户研究表明，Raft比Paxos更容易理解：在学习两种算法后，其中33名学生能够更好地回答关于Raft的问题。
Raft在许多方面类似于现有的一致性算法（尤其是Oki和Liskov的ViewstampedReplication[29,22]），但它有几个新特性：
Strongleader：在Raft中，日志条目（logentries）只从leader流向其他服务器。这简化了复制日志的管理，使得raft更容易理解。
Leader选举：Raft使用随机计时器进行leader选举。这只需在任何一致性算法都需要的心跳（heartbeats）上增加少量机制，同时能够简单快速地解决冲突。
成员变更：Raft使用了一种新的联合一致性方法，其中两个不同配置的大多数在过渡期间重叠。这允许集群在配置更改期间继续正常运行。
我们认为，Raft优于Paxos和其他一致性算法，不仅在教学方面，在工程实现方面也是。它比其他算法更简单且更易于理解;它被描述得十分详细足以满足实际系统的需要;它有多个开源实现，并被多家公司使用;它的安全性已被正式规定和验证;它的效率与其他算法相当。
本文的剩余部分介绍了复制状态机问题（第2节），讨论了Paxos的优点和缺点（第3节），描述了我们实现易理解性的方法（第4节），提出了Raft一致性算法（第5-8节），评估Raft（第9节），并讨论了相关工作（第10节）。
2复制状态机（Replicatedstatemachines）
一致性算法是在复制状态机[37]的背景下产生的。在这种方法中，一组服务器上的状态机计算相同状态的相同副本，并且即使某些服务器宕机，也可以继续运行。
复制状态机用于解决分布式系统中的各种容错问题。例如，具有单个leader的大规模系统，如GFS[8]，HDFS[38]和RAMCloud[33]，通常使用单独的复制状态机来进行leader选举和存储leader崩溃后重新选举需要的配置信息。Chubby[2]和ZooKeeper[11]都是复制状态机。
复制状态机通常使用复制日志实现，如图1所示。每个服务器存储一个包含一系列命令的日志，其状态机按顺序执行日志中的命令。每个日志中命令都相同并且顺序也一样，因此每个状态机处理相同的命令序列。这样就能得到相同的状态和相同的输出序列。
图1
一致性算法的工作就是保证复制日志的一致性。每台服务器上的一致性模块接收来自客户端的命令，并将它们添加到其日志中。它与其他服务器上的一致性模块通信，以确保每个日志最终以相同的顺序包含相同的命令，即使有一些服务器失败。一旦命令被正确复制，每个服务器上的状态机按日志顺序处理它们，并将输出返回给客户端。这样就形成了高可用的复制状态机。
实际系统中的一致性算法通常具有以下属性：
它们确保在所有非拜占庭条件下（包括网络延迟，分区和数据包丢失，重复和乱序）的安全性（不会返回不正确的结果）。
只要任何大多数（过半）服务器都可以运行，并且可以相互通信和与客户通信，一致性算法就可用。因此，五台服务器的典型集群可以容忍任何两台服务器的故障。假设服务器突然宕机;它们可以稍后从状态恢复并重新加入群集。
它们不依赖于时序来确保日志的一致性：错误的时钟和极端消息延迟可能在最坏的情况下导致可用性问题。
在通常情况下，只要集群的大部分（过半服务器）已经响应了单轮远程过程调用，命令就可以完成;少数（一半以下）慢服务器不需要影响整个系统性能。
3Paxos存在的问题
在过去十年里，LeslieLamport的Paxos协议[15]几乎成为一致性的同义词：它是课堂上教授最多的一致性协议，并且大多数一致性的实现也以它为起点。Paxos首先定义了能够在单个决策（例如单个复制日志条目）上达成一致的协议。我们将这个子集称为single-decreePaxos。然后Paxos组合该协议的多个实例以促进一系列决策，例如日志（multi-Paxos）。Paxos能够确保安全性和活性，并且支持集群成员的变更。它的正确性已被证明，并且在正常情况下是高效的。
不幸的是，Paxos有两个显著的缺点。第一个缺点是Paxos非常难以理解。Paxos的描述晦涩难懂，臭名昭著（译者注：《ThePart-timeParliament》比较晦涩难懂，但是《PaxosMadeSimple》就比较容易理解）;很少有人成功地理解它，即使能理解也必须付出巨大的努力。因此，已有几个尝试以更简单的方式来描述Paxos[16,20,21]。这些描述集中在single-degreePaxos，但它们仍然具有挑战性。在对NSDI参会者的非正式调查中，我们发现很少有人喜欢Paxos，即使是经验丰富的研究人员。我们自己也跟Paxos进行了艰苦的斗争;我们也无法完全理解整个协议，直到阅读了几个更简单的描述和自己设计替代Paxos的协议，整个过程花了将近一年。
Paxos晦涩难懂的原因是作者选择了single-degreePaxos作为基础。Single-decreePaxos分成两个阶段，这两个阶段没有简单直观的说明，并且不能被单独理解。因此，很难理解为什么该算法能起作用。Multi-Paxos的合成规则又增加了许多复杂性。我们相信，对多个决定（日志而不是单个日志条目）达成一致的总体问题可以用其他更直接和更明显的方式进行分解。
Paxos的第二个问题是它不能为构建实际的实现提供良好的基础。一个原因是没有针对multi-Paxos的广泛同意的算法。Lamport的描述主要是关于single-decreePaxos;他描述了multi-Paxos的可能方法，但缺少许多细节。已经有几个尝试来具体化和优化Paxos，例如[26]，[39]和[13]，但这些彼此各不相同并且跟Lamport描述的也不同。像Chubby[4]这样的系统已经实现了类Paxos（Paxos-like）算法，但大多数情况下，它们的细节并没有公布。
此外，Paxos的架构对于构建实际系统来说是一个糟糕的设计，这是single-decree分解的另一个结果。例如，独立地选择日志条目集合，然后再将它们合并到顺序日志中几乎没有任何好处，这只会增加复杂性。围绕日志设计系统是更简单和有效的方法，新日志条目按照约束顺序地添加到日志中。Paxos的做法适用于只需要做一次决策的情况，如果需要做一系列决策，更简单和快速的方法是先选择一个leader，然后让该leader协调这些决策。
因此，实际的系统跟Paxos相差很大。几乎所有的实现都是从Paxos开始，然后发现很多实现上的难题，接着就开发了一种和Paxos完全不一样的架构。这样既费时又容易出错，而且Paxos本身晦涩难懂使得该问题更加严重。Paxos的公式可能可以很好地证明它的正确性，但是现实的系统和Paxos差别是如此之大，以至于这些证明并没有什么太大的价值。下面来自Chubby作者的评论非常典型：
在Paxos算法描述和实现现实系统中间有着巨大的鸿沟。最终的系统往往建立在一个还未被证明的协议之上。
由于以上问题，我们得出的结论是Paxos算法没有为系统实践和教学提供一个良好的基础。考虑到一致性问题在大规模软件系统中的重要性，我们决定尝试设计一个能够替代Paxos并且具有更好特性的一致性算法。Raft算法就是这次实验的结果。
4为可理解性而设计
在设计Raft算法过程中我们有几个目标：它必须提供一个完整的实际的系统实现基础，这样才能大大减少开发者的工作；它必须在任何情况下都是安全的并且在典型的应用条件下是可用的；并且在正常情况下是高效的。但是我们最重要的目标也是最大的挑战是可理解性。它必须保证能够被大多数人容易地理解。另外，它必须能够让人形成直观的认识，这样系统的构建者才能够在现实中进行扩展。
在设计Raft算法的时候，很多情况下我们需要在多个备选方案中进行选择。在这种情况下，我们基于可理解性来评估备选方案：解释各个备选方案的难道有多大（例如，Raft的状态空间有多复杂，是否有微妙的含义）？对于一个读者而言，完全理解这个方案和含义是否容易？
我们意识到这样的分析具有高度的主观性；但是我们使用了两种通用的技术来解决这个问题。第一个技术就是众所周知的问题分解：只要有可能，我们就将问题分解成几个相对独立的，可被解决的、可解释的和可理解的子问题。例如，Raft算法被我们分成leader选举，日志复制，安全性和成员变更几个部分。
我们使用的第二个方法是通过减少状态的数量来简化状态空间，使得系统更加连贯并且尽可能消除不确定性。特别的，所有的日志是不允许有空洞的，并且Raft限制了使日志之间不一致的方式。尽管在大多数情况下我们都试图去消除不确定性，但是在某些情况下不确定性可以提高可理解性。特别是，随机化方法虽然引入了不确定性，但是他们往往能够通过使用相近的方法处理可能的选择来减少状态空间。我们使用随机化来简化Raft中的leader选举算法。
5Raft一致性算法
Raft是一种用来管理第2节中描述的复制日志的算法。图2是该算法的浓缩，可用作参考，图3列举了该算法的一些关键特性。图中的这些内容将在剩下的章节中逐一介绍。
图2
图3
Raft通过首先选举一个distinguishedleader，然后让它全权负责管理复制日志来实现一致性。Leader从客户端接收日志条目，把日志条目复制到其他服务器上，并且在保证安全性的时候通知其他服务器将日志条目应用到他们的状态机中。拥有一个leader大大简化了对复制日志的管理。例如，领导人可以决定新的日志条目需要放在日志中的什么位置而不需要和其他服务器商议，并且数据都是从leader流向其他服务器。leader可能宕机，也可能和其他服务器断开连接，这时一个新的leader会被选举出来。
通过选举一个leader的方式，Raft将一致性问题分解成了三个相对独立的子问题，这些问题将会在接下来的子章节中进行讨论：
Leader选举：当前的leader宕机时，一个新的leader必须被选举出来。（章节5.2）
日志复制：Leader必须从客户端接收日志条目然后复制到集群中的其他节点，并且强制要求其他节点的日志和自己的保持一致。
安全性：Raft中安全性的关键是图3中状态机的安全性：如果有任何的服务器节点已经应用了一个特定的日志条目到它的状态机中，那么其他服务器节点不能在同一个日志索引位置应用一条不同的指令。章节5.4阐述了Raft算法是如何保证这个特性的；该解决方案在选举机制（5.2节）上增加了额外的限制。
在展示一致性算法之后，本章节将讨论可用性的一些问题以及时序在系统中的作用。
5.1Raft基础
一个Raft集群包含若干个服务器节点；通常是5个，这样的系统可以容忍2个节点的失效。在任何时刻，每一个服务器节点都处于这三个状态之一：leader、follower或者candidate。在正常情况下，集群中只有一个leader并且其他的节点全部都是follower。Follower都是被动的：他们不会发送任何请求，只是简单的响应来自leader和candidate的请求。Leader处理所有的客户端请求（如果一个客户端和follower通信，follower会将请求重定向给leader）。第三种状态，candidate，是用来选举一个新的leader（章节5.2）。图4展示了这些状态和他们之间的转换关系；这些转换关系在接下来会进行讨论。
图4
Raft把时间分割成任意长度的任期（term），如图5所示。任期用连续的整数标记。每一段任期从一次选举开始，一个或者多个candidate尝试成为leader。如果一个candidate赢得选举，然后他就在该任期剩下的时间里充当leader。在某些情况下，一次选举无法选出leader。在这种情况下，这一任期会以没有leader结束；一个新的任期（包含一次新的选举）会很快重新开始。Raft保证了在任意一个任期内，最多只有一个leader。
图5
不同的服务器节点观察到的任期转换的次数可能不同，在某些情况下，一个服务器节点可能没有看到leader选举过程或者甚至整个任期全程。任期在Raft算法中充当逻辑时钟的作用，这使得服务器节点可以发现一些过期的信息比如过时的leader。每一个服务器节点存储一个当前任期号，该编号随着时间单调递增。服务器之间通信的时候会交换当前任期号；如果一个服务器的当前任期号比其他的小，该服务器会将自己的任期号更新为较大的那个值。如果一个candidate或者leader发现自己的任期号过期了，它会立即回到follower状态。如果一个节点接收到一个包含过期的任期号的请求，它会直接拒绝这个请求。
Raft算法中服务器节点之间使用RPC进行通信，并且基本的一致性算法只需要两种类型的RPC。请求投票（RequestVote）RPC由candidate在选举期间发起（章节5.2），追加条目（AppendEntries）RPC由leader发起，用来复制日志和提供一种心跳机制（章节5.3）。第7节为了在服务器之间传输快照增加了第三种RPC。当服务器没有及时的收到RPC的响应时，会进行重试，并且他们能够并行的发起RPC来获得最佳的性能。
5.2Leader选举
Raft使用一种心跳机制来触发leader选举。当服务器程序启动时，他们都是follower。一个服务器节点只要能从leader或candidate处接收到有效的RPC就一直保持follower状态。Leader周期性地向所有follower发送心跳（不包含日志条目的AppendEntriesRPC）来维持自己的地位。如果一个follower在一段选举超时时间内没有接收到任何消息，它就假设系统中没有可用的leader，然后开始进行选举以选出新的leader。
要开始一次选举过程，follower先增加自己的当前任期号并且转换到candidate状态。然后投票给自己并且并行地向集群中的其他服务器节点发送RequestVoteRPC（让其他服务器节点投票给它）。Candidate会一直保持当前状态直到以下三件事情之一发生：(a)它自己赢得了这次的选举（收到过半的投票），(b)其他的服务器节点成为leader，(c)一段时间之后没有任何获胜者。这些结果会在下面的章节里分别讨论。
当一个candidate获得集群中过半服务器节点针对同一个任期的投票，它就赢得了这次选举并成为leader。对于同一个任期，每个服务器节点只会投给一个candidate，按照先来先服务（first-