Raft: 寻找易于理解的一致性算法<上>

原文地址

摘要

Raft是一个一致性算法，它用于管理相同的日志副本(replicated log)。它可以产生一个和(multi)Paxos相同的结果，和paxos一样有效，但是Raft的结构和Paxos不相同。这使得Raft比Paxos更容易理解，并且为构建实际的系统提供了更好的基础。为了提高理解性，Raft把一致性问题中的几个关键元素分离开来，比如leader选举，日志复制，以及正确性(safety)，Raft加强了内聚性以减少必须考虑的状态数。用户研究案例显示，相比Paxos，学生学习Raft更容易。Raft也引入了一种新的机制来变更集群成员关系，这种机制通过覆盖到集群中的大多数节点来保证正确性。

1. 简介

一致性算法可以使一群机器作为一致的整体工作，能够容忍部分成员故障的情形。由于这个原因，在构建可靠的大规模软件系统中，一致性算法扮演着非常重要的角色。Paxos^{[1] [2]}在过去的十年内主宰着这个领域: 大多数一致性组件的实现是基于Paxos或者受到它的影响，Paxos也成为了一致性算法教学方面的首选。

不幸的是，即使有大量尝试想使它变得更容易，Paxos还是非常难于理解。除此之外，它的算法结构需要经过复杂的改造才能应用于实际的系统中。因此，系统构建者和学生都为Paxos感到头疼。

在经过和Paxos的一番斗争之后，我们开始着手寻找一种新的一致性算法，能够为工程和教学提供一个更好的基础。我们的思路非常不寻常，因为我们的首要目标是容易理解: 我们是否能够找到一个可以用于实际系统的算法，并且能以相对Paxos更简单的方式描述它? 更进一步的，我们期望这个算法能够符合开发的直觉，这对系统构建者非常重要。不仅算法能够工作很重要，能够明显看出为什么能够工作也很重要。

这个工作的结果是一个叫做Raft的算法。在设计Raft的过程中我们使用了特定的技术来增强易懂性，包括解耦(Raft把leader选举，日志复制以及正确性分开处理)和缩减状态空间(相比于Paxos，Raft减少了不确定性以及服务器之间不一致的方式)。一个包括了43个学生的用户调研显示，相比Paxos，Raft更加容易理解: 在学习了这两个算法后，33个学生能够更好的回答关于Raft的问题。

Raft和现存的一致性算法在很多方面都是相似的(特别是Oki和Liskov的Viewstamped Replication^{[3] [4]})，但它也有几个显著的特色:

• Strong leader: Raft使用了比其他算法更强的领导力。比如，日志条目只能从leader流向其他服务器。这简化了日志复制的管理，使Raft更容易理解。
• Leader election: Raft使用随机定时器来选举leader。这只需要在心跳机制上加一点逻辑，却能够简单快速的解决冲突，而心跳机制对每个一致性算法都是必须的。
• Membership changes: Raft中用于更改集群成员的机制使用了一个协同一致的方法，其中在变更的过程中，两个不同集合的大部分是相互覆盖(overlap)的。这使得集群可以在配置变更的过程中继续正常的运作。

我们认为Raft比Paxos以及其他一致性算法要优越，无论是作为教学的目的还是作为实现的基础。相比其他算法，Raft更简单也更容易理解。它被描述的足够完整，以满足一个实际系统的需求。它有几个开源的实现并被几个公司所采用。它的正确性被正确的提出并证明，同时它的性能相比其他算法也是有竞争力的。

本文剩余的部分介绍了复制的状态机问题(第2章)，讨论了Paxos的强项和弱项(第3章)，描述了我们达到易懂性的方法(第4章)，展示Raft算法(第5到8章)，评估Raft算法(第9章)，讨论了相关的工作(第10章)。

2. 复制的状态机

一致性算法一般是在复制的状态机^[5]情景中出现。这种情形下，一组服务器上的状态机计算相同的状态，即使部分服务器宕机，这些状态机也可以继续运作。在分布式系统中，复制的状态机可以用于解决很多容错问题。比如，带有一个leader的大规模系统，如GFS^[6], HDFS^[7], RAMCloud^[8], 经常使用一个单独的复制状态机来管理leader选举，以及存储配置信息。复制状态机的例子包括Chubby^[9], ZooKeeper^[10]。

rsm.jpg

复制状态机往往通过一个复制日志来实现，如图1所示。每个服务器保存一份日志，日志中包含着一系列指令(commands)，状态机按顺序执行这些指令。每个日志文件保存着相同的指令，并且指令按照相同的顺序排列，如此每个状态机就会执行相同的指令序列。由于状态机是确定的，因此每个状态机会计算相同出的状态和相同的输出序列。

保持复制的日志一致是一致性算法的工作。服务器上负责一致性的模块接收客户端的指令并添加到它的日志文件中。它和其他服务器上的一致性模块通信以保证即使部分服务器出现宕机，每份日志文件最终都包含着相同顺序的相同指令。一旦指令被适当的复制，每个服务器上的状态机按照日志中的顺序执行这些指令，并将结果返回给客户端。作为结果，这些服务器看起来就好像单个可靠的状态机。

实际系统中的一致性算法一般包括以下属性:

• 它们保证在非拜占庭条件，包括网络延迟，断开，丢包，重复，以及乱序等情形下，算法的正确性(绝不返回一个错误的结果)。
• 只要服务器的大多数都正常运作，相互之间可以通信，并且可以和客户端通信，算法就是正常工作的(available)。因此，一个包括了5台服务器的集群可以容忍其中2台服务器宕机。这里假设服务器会停机，它们可能在后续通过持久化存储的状态恢复，并重新加入到集群中。
• 它们不依赖时间来保证日志的一致性: 错误的时钟以及极端的消息延迟可能导致可用性问题。
• 一般情况下，当集群中的大多数响应了RPC调用后，就可以认为指令执行完成了。少数响应慢的服务器不会影响系统整体的性能。

3. Paxos的问题

在过去的十年内，Leslie Lamport的Paxos协议几乎成为了一致性的代名词: 它是在课堂上被教学的最多的算法，并且大部分一致性算法的实现都使用它作为起点。Paxos首先定义了一个协议，可以在单个决定上达成一致，比如单个日志条目。我们把这个叫做单个Paxos(single-decree Paxos)。然后Paxos把多个这样的协议组合在一起(multi-Paxos)，确定了一系列决定，比如构建一个日志。Paxos保证正确性和可用性(liveness)， 并且支持成员关系的变动。它的正确性被证明过，并且在一般的情况下足够高效。

不幸的是，Paxos有两个重大缺陷。第一个缺陷是，Paxos及其的难以理解。完整的论文解释^[11]因为晦涩而臭名昭著；少数人成功的理解了它，但也花费了大量努力。作为结果，有几个尝试以简单的方式来解释Paxos的例子 ^{[12] [13] [14]}。这些解释只是集中在单个Paxos上，但仍然很难理解。在NSDI 2012与会者中进行的一个非正式调查显示，很少人会对Paxos满意，其中甚至包括了一些资深的研究人员。我们自己在努力学习Paxos；直到阅读了几个简化版的解释，并且设计了我们自己的替代协议后，我们才理解了完整的Paxos，过程几乎花费了一年。

我们假设Paxos的晦涩难懂是因为它使用单条目Paxos(single-decree)作为它的基础。单条目Paxos稠密(dense)而微妙：它被分为两个无法从直觉上解释的阶段，并且不可能单独理解其中任意一个。因为这个原因，很难从直觉上了解为什么单个Paxos是有效的。多个Paxos的组合更增加了大量的复杂性。我们认为，在多个决定上达成一致的问题可以从整体上进行解耦，以一种更加直接和明显的方式。

Paxos的第二个问题是它没有为构建实际系统给出一个好的基础。其中一个原因是没有一个被广发接收的multi-Paxos算法。Lamport的描述基本上都是关于单条目Paxos的；他大概的描述了可能实现multi-Paxos的方法，但没有提及很多细节。有一些尝试补充和优化Paxos的例子，比如^{[15] [16] [17]}，但是它们各不相同，并且和Lamport的描述也不同。一些系统如Chubby实现了类Paxos算法，但是它们的很多细节都没有公开。

除此之外，Paxos的架构对于构建实际的系统是非常糟糕的；这是使用单条目Paxos的另一个后果。比如，单独的确定很多日志条目然后把它们合并为一个顺序日志，这么做是没有什么好处的，只是增加了复杂程度。更加简单和高效的方式是：围绕一个日志文件设计系统，其中新的条目以某种顺序添加到文件后面。另一个问题是，Paxos在核心架构中使用对称的p2p方式(即使后面它建议使用弱leader的优化方式)。在只需要做一个决定的简单环境中，这可能是有用的，但是很少实际中的系统使用这种方案。如果需要做出一系列的决定，更简单更快的方式是选出一个leader，然后让leader来协调这些决定。

其结果就是，很多实际系统几乎和Paxos没有相似之处。每个实现都是以Paxos开始，然后在过程中发现了困难之处，接着发展出完全不同的另外一套架构。这个过程是耗时而且容易出错的，Paxos的难懂更加剧了这些问题。Paxos的公式可能能够很好的正确它的正确性，但是真实的实现和Paxos如此不同，以至于那些证明几乎没有价值。下面这段对Chubby实现的评论非常典型：

在Paxos算法描述和真实世界系统之间有重大差距...最终这个系统会基于一个没有证明的协议实现。

由于这些问题，我们的结论是Paxos既没有为系统搭建也没有为教学提供一个好的基础。考虑到一致性算法在大规模软件系统中的重要性，我们决定看看我们是否能够设计一个更好的替代Paxos的算法。这个实验的结果就是Raft。

4. 旨在容易理解的设计

在设计Raft的时候我们有几个目标：它必须为构建系统提供一个完整并实际的基础，这样就可以大量减少开发人员需要的设计工作；它必须在任何条件下都是正确的，在典型的操作条件(operating conditions)下是可用的；并且它的一般操作必须是高效的。但是我们最重要的目标--也是最困难的挑战--是容易理解。它必须让大部分人都能够舒服的理解这个算法。它必须能让人对算法建议一种直觉上的认识，这样系统搭建人员就可以在它的基础上开发扩展，在真实世界中这是不可避免的。

设计Raft的过程中，有很多需要在多个替代方案中做出选择则的时刻。在这些情形下，我们都基于易懂性做出了选择：解释每种方案有多困难(例如，它的状态空间是否复杂，它是否有微妙的暗示?)，让一个读者完整的理解它以及它的实现有多简单？

我们认识到，在这样的分析中，有着很高程度的主观因素；尽管如此，我们使用了两种被广泛接受的技术。第一个技术是知名的分治法(problem decomposition): 只要有可能，我们就把问题分解为几个单独的可悲解决的部分，各自独立的解释和理解它。比如，在Raft中我们把leader选举，日志复制，正确性和成员管理分开了。

我们的第二个方法是通过减少需要考虑的状态来简化状态空间，使系统更加连贯，并在可能的时候消除不确定性。尤其是，日志不允许有空洞，Raft限制了各个日志之间不一致的方式。尽管在大多数情况下我们都尽力去消除不确定性，仍然存在一些情形不确定性反而可以增加易懂性。具体的说，随机方案引入了不确定性，但是它可以通过对不同选择做相同处理来减少状态空间("随便算一个，没有影响")。我们使用随机化来简化Raft的leader选举算法。

5. Raft一致性算法

Raft是一个用于管理复制日志的算法，在第二章描述过这个问题。图2简练的总结了算法，用于后面的引用，图3列出了算法的关键属性；图中的元素会在本章后面分开讨论。

Raft首先选举出一个leader，然后由leader来完全管理复制日志，以此来实现一致性。leader接受客户端发送的日志条目，复制到其他服务器，告诉他们什么时候可以安全的把日志条目应用到他们的状态机上。使用leader简化了复制日志的管理。比如，leader能够在不询问其他服务器的情况下决定把日志条目放在哪里，数据流向只能从leader到其他服务器。leader可能会和其他服务器断开连接，这种情况下，新的leader被选举出来。

summary.jpg keys.jpg

使用leader方案，Raft把一致性问题分解为三个相关的子问题，后续章节会分别讨论：

• leader选举：当前leader故障时必须选举出一个新的leader(5.2节)。
• 日志复制：leader必须从客户端接收日志条目并复制到集群中其他服务器上，强制其他日志和它的保持一致(5.3节)。
• 正确性：Raft的关键属性是图3中描述的状态机正确属性：如果一个服务器把一条日志条目应用到了它的状态机上，那么不会有其他服务器在相同的日志偏移处应用一条不同的指令。5.4节描述了Raft如何保证这一点；解决方案包括了5.2节中描述的对选举机制额外的一些限制。

介绍完一致性算法后，本章后续讨论了可用性问题以及时间在系统中扮演的角色。

5.1 Raft基础

一个Raft集群包含了多个服务器；典型的数字是5个，这样的系统可以容忍两台服务器的故障。在任意给定的时刻，每个server都处于三种状态的一种：leader, follower, 或者candidate。在一般情况下，只有一个leader，其他server都是follower。Followers是被动的：他们不会自己发起请求，只会响应来自leader和candidate的请求。leader处理所有的客户端请求(如果客户端请求到一个follower，follower会把请求重定向到leader)。第三种状态，candidate，是用于选举新leader的，在5.2节中会讨论。图4显示了这些状态和它们的之间的转移；转移过程在下面会讨论。

states.jpg

Raft把时间分为任意长度的terms，如图5所示。Terms用连续的数据来标志。每个term都以一个选举开始，其中一个或多个candidate尝试着成为leader。如果一个candidate在选举中胜出，它会成为leader，并在这个term的后续时间中一直保持是leader。在某些情况下，选举可能会导致投票结果分裂开来。这种情况下这个term会以没有leader的状态结束；新的term(新的选举)会接着开始。Raft保证在一个term中只会有一个leader。

terms.jpg

不同的服务器可能会在不同时间段看到terms的转移，某种情况下服务器可能在整个term周期内都不会观察到选举。Terms在Raft中扮演着逻辑时钟[^]的角色，它们使得服务器可以检测到过时的信息，比如一个陈旧的leader。每个服务器都存储着一个当前term数字，这个数字会随着时间单调增加。当前terms会在服务器之间通信时进行交换；如果一个服务器的当前term比其他服务器的小，它会更新自己的当前term为大的值。如果一个candidate或者leader发现它的term过时了，它会立即转移到follower状态。如果一个服务器收到了一个过期的term值，它会拒绝这个请求。

Raft服务器使用RPC来相互通信，基本的一致性算法只需要两种RPC。RequsetVote RPC由candidate在选举中发起(5.2节)，Append-Entries RPC由leader发起，用于复制日志条目，以及提供心跳机制(5.3节)。第7章增加了第三种RPC，用于在服务器之间转移快照。如果在指定时间内没有收到回复，服务器会重试RPC，此外，服务会并行发起RPC以获得更好的性能。

5.2 Leader选举

Raft使用一种心跳机制来触发leader选举。服务器启动时，以follower状态开始。只要它受到来自leader或者candidatea的有效RPC请求，它会保持follower状态。leader会持续周期的发送心跳(没有数据的AppendEntries RPC)给所有的followers，以此维持它的权威。如果一个服务器在一个选举超时的时间内没有收到心跳请求，它会认为没有可用的leader，然后一次选举以选择新的leader。

开始一次选举的方式是：follower增加它的当前term值，并转移到candidate状态。然后它为自己投票，并发起并行的RequestVote RPC给集群中的每一个其他服务器。candidate会持续在这个状态直到以下三种情况之一发生：(a)它赢得了选举，(b)其他服务器赢得了选举，(c)一段时间过去了没有胜出者。下面的段落会分别讨论这几种情况。

如果一个candidate在同一个term中收到了集群中大部分服务器的响应，那么它就在选举中胜出。在指定的term中，每个server只能为一个candidate投票，以先到先得的规则来实现(5.4节增加了额外的限制)。大部分保证了在一个term中最多一个candidate会在选举中胜出(图3中描述的选举正确性属性)。一旦一个candidate赢得了选举，它便成为leader。接下来它会发送心跳消息给所有其他服务器以建立权威并阻止新的选举。

在等待投票结果的时候，candidate可能会收到其他服务器的AppendEntries RPC，声称它自己以及成为了leader。如果这个leader的term值(在RPC中携带)不小于candidate的term值，那么candidate就会承认此leader是合法的并将自己返回到follower状态。如果RPC中的term值比candidate的当前term要小，那么candidate会拒绝RPC并继续保持candidate状态。

第三个可能的结果是一个candidate既没有在选举中胜出也没有失败：如果多个followers同时成为candidate，投票可能会分裂，以至于没有任何candidate能获得大多数的认可。当发生这种情况时，每个candidate都会投票超时，它们会增加自己的term值并发起新一轮的RequestVote RPC。如果不采取额外的措施，投票可能会无限的分裂下去。

Raft使用随机的选举超时值来保证投票分裂很少发生，并能够快速得到解决。为了从源头方式投票分裂的发生，选举超时值会随机的从一段固定范围内选取(比如150-300ms)。这些不同的值分散在服务器中，因此大多数情况下只会有一个服务器会超时；超时的服务器会在其他服务器超时之前赢得选举并发送心跳给其他服务器。这种机制也用来处理投票分裂。每个candidate在一次选举开始的时候会选择一个超时值，等待这个时间过去，然后开始下一次选举；这减少了下次选举出现投票分裂的可能性。9.3节显示使用这种方案来选举leader非常快速。

选举机制作为一个例子展示了在设计过程中易懂性是如何影响我们的选择。最开始我们计划使用一个排名系统：每个candidate被分配一个单独的排名，如果某个candidate发现其他candidate的排名更高，那么它就会转换为follower，这样高排名的candidate就更容易赢得选举。我们发现这种方案对可用性产生了一些微妙的影响(在高排名服务器故障的情形下，低排名的服务器可能要等待超时后才能再次成为candidate，如果它不这么做，就可能重置整个选举的过程)。我们多次调整了算法，但每次调整后都有新的边缘情形出现。最终我们的总结是随机重试方案更加明显和易懂。

5.3 日志复制

一旦leader被选举出来，它开始服务客户端请求。每个客户端请求都包含着一个可被状态机执行的指令。leader将指令添加到日志后面作为一个新条目，然后并行的给其他服务器发起AppendEntries RPC，让它们复制这个条目。当此条目被正确的复制后(下面会讲解)，leader把这个条目应用到它的状态机上，并将结果返回给客户端。如果follower宕机或者运行缓慢，或者出现消息丢失，leader会无限的尝试发送AppendEntries RPC知道所有的follower最终存储了全部的日志条目。

entries.jpg

日志被组织为如图6所示的形式。每一条日志条目都保存着一个状态机指令以及一个term值。term值用来检测日志之间的不一致，并保证图3中的一些属性。每条日志条目都有一个整数索引值来识别它在日志中的位置。

leader决定何时才能安全的把一条日志条目应用到状态机上；这样的条目被称作已提交。Raft保证已提交的条目会持久化，并最终被所有可用的状态机执行。一旦leader把某个条目复制到了大多数户服务器中(比如图6中的条目7)，这个条目就提交了。同时被提交的还有leader日志中之前的所有的条目，包括由之前leader创建的条目。5.4节讨论了在leader更换之后应用这条规则的一些微妙之处，同时也展示了按照这样定义提交的正确性。leader保持追踪它所知道的最高已提交条目的索引，它会在后续的AppendEntries RPC(包括心跳)中带上这个索引值，这样其他的服务器最终也会知道这个值。当follower发现某个条目已经提交了，它会应用这个条目到它自己的状态机上(按照日志的顺序)。

我们设计Raft日志机制，让不同服务器上日志保持高度一致。这套机制不仅简化了系统行为，使系统更加可预测，也是保证正确性的重要组件。Raft维持以下属性，它们共同构成了图3中所示的日志匹配属性(Log Matching Property):

• 如果不同日志中的两个条目有相同的索引值和term值，那么他们保存着相同的指令
• 如果不同日志中的两个条目有相同的索引值和term值，那么他们之前的日志条目全部是相同的

第一个属性可以从如下事实中推演：在指定的term中，leader在日志的某个索引位置只会创建最多一条日志，而且日志条目绝不会改变它们在日志中的位置。第二个属性由AppendEntries RPC所执行的一致性检查来保证。当发送AppendEntries RPC时，leader会带上当前最新添加条目之前的那一条日志条目的term值和index值。如果follower在它的日志的相同位置没有找到相同的条目，它就会拒绝新的条目。这个一致性检查以归纳法的形式运作：最初的空日志符合Log Matching Properry，而一致性检查则保证后续的日志仍然满足Log Matching Property。作为结果，任何时候只要AppendEntries返回成功，leader就能知道，这个follower的日志在和自己的日志，直到最新添加的条目这里，全部是相同的。

在常见操作中，leader和followers的日志保持一致，因此AppendEntries一致性检查不会失败。然而，leader宕机会导致日志不一致(老的leader可能没有把它的日志全部复制完成)。这种不一致可能会在一系列leader和followers的宕机过程中叠加。图7展示了followers日志和新leader不一致的几种可能。follower可能缺少leader的部分日志，也可能有一些leader上面没有的日志，或者同时发生这两种情况。确实和多余的日志条目可能跨域多个term。

logs.jpg

在Raft中，leader通过强制follower复制自己的日志来达到一致。这就是说follower中的冲突日志条目会被leader的日志内容覆盖。5.4节会说明，加上适当的约束，这样做是安全的。

为了让follower的日志和自己的一直，leader必须找到两个日志中相同的最近的那条日志条目，从这个点开始，删除follower日志后面的内容，并把leader自这里开始的日志都发送给follower。这些动作都在AppendEntries RPC的一致性检查中进行。leader对每个follower维护着一个nextIndex值，这个值标志着下一条发送给follower的日志索引。当leader开始工作时，它会把所有的nextIndex初始化为它日志的最后一条后面的位置(图7中的11)。如果某个follower的日志和leader不一致，那么后续的AppendEntries RPC的一致性检查就会失败。在RPC被拒绝之后，leader减小nextIndex的值，然后再次尝试发送AppendEntries RPC。最终会得到一个leader和follower的日志内容匹配的nextIndex。当找到这个点后，AppendEntries会成功，它会删除follower中所有冲突的日志，然后添加上leader的日志内容。一旦AppendEntries成功，follower的日志就和leader一致了，并且会在当前term中保持一致。

如果需要的话，可以优化协议以减少AppendEntries RPC被拒绝的次数。比如，在拒绝AppendEntries时， follower可以在回复中带上冲突的条目以及它所保存的当前term的第一个条目的索引。有了这些信息，leader可以确定一个能够绕过冲突条目的nextIndex；解决冲突条目只需要一次AppendEntries RPC，而不是每个条目一个RPC。在实际中，我们怀疑这个优化的必要性，因为故障不会频繁的发生，不太可能出现很多不一致的条目。

使用这种机制，leader在上任后不需要采取额外的措施来恢复一致性。它仅仅开始常规操作，日志就会在AppendEntries一致性检查中自动的汇合。leader绝不会覆盖或者删除自己的日志(图3中的leaderAppend-Only属性)。

日志复制机制展示了第2章中描述的一致性属性：在大多数服务器正常的情况下，Raft可以接收，复制，应用新的日志条目；在普通情形下，复制一条新条目只需要一轮RPC；单个慢服务器不会影响性能。

5.4 正确性

前面的章节描述了Raft是如何选举leader和复制日志的。然而到目前为止，上述的机制并不能保证每个状态机都按照相同的顺序执行完全一样的指令。比如说，某个follower可能在leader复制日志的时候不可用，然后又被选举为leader并用新的日志条目覆盖了之前leader复制的那些条目；这种情况下，不同状态机就可能会执行不同的指令。

这一小节描述了哪些服务器能被选举为leader的限制，从而完善了Raft算法。这个限制保证了任意term中的leader都包含了在之前term中提交的所有日志条目(图3中的Leader完整属性)。通过这个限制，我们把提交规则变得更精确。最后，我们给出对Leader完整属性的一个概要证明，并展示了它是如何使复制状态机都正确工作。

5.4.1 选举限制

在任何基于leader的一致性算法中，leader最终都必须存储着所有提交的日志条目。在一些算法中，如Viewstamped Replication[^]，一个leader即使在开始没有包含所有提交的条目也能够被选为leader。这些算法包括了额外的机制，用来发现丢失的条目并将它们传输到新leader上，要么在选举过程中，要么在选举后进行。不幸的是，这导致了大量的额外机制和复杂性。Raft使用了一个简单的方案，它保证在选举开始时，所有在之前term中提交的条目都在新leader上，不需要传输这些条目到leader。这意味着日志条目只会在一个方向上流动，从leader到followers，而且leader绝不会覆盖他自己日志中已有的条目。

Raft在投票过程中会防止某个candidate赢得选举，除非它的日志包括了所有提交的条目。为了赢得选举，candidate必须和集群中的大多数服务器进行通信，这意味着每一条提交的条目至少存在这些服务器中的一台上。如果candidate的日志至少和大多数服务器中的日志都是一样新(up-to-date，后面会精确定义)的，那么它就包括了所有提交的条目。RequestVote RPC实现了这个限制：RPC中包含了candidate的日志信息，如果投票者发现它自己的日志比candidate的更新，它会拒绝此次投票。

Raft通过比较日志中最后一个条目的index和term来决定哪个日志更新一些。如果两个日志最后一个条目的term不同，那么term大的更新。如果两个日志最后条目的term相同，那么更长的那个日志更新。

5.4.2 提交之前term的条目

commit.jpg

5.3节中讲过，当一个当前term的条目被存储在集群中大多数服务器上时，leader则认为此条目是已提交了。如果leader在提交某个条目之前崩溃了，新的leader会尝试完成这个条目的复制。然而，leader不能立即断定一个之前term的条目已经提交，即使这个条目存储在大多数服务器上。图8展示了一个情形，其中一个旧的条目存储在大多数服务器上，但仍然可能会被新的leader覆盖。

为了消除图8中的问题，Raft绝不会通过计数副本的数目来提交之前term的日志条目。只有当前term的条目会通过计数来提交；一旦当前term的某个条目通过这种方式提交了，那么之前的所有条目也都提交了，基于Log匹配属性。某些情况下，leader可以安全的断定一个旧的条目以及被提交(比如，每个server上都保存着这个条目)，但是处于简化的考虑，Raft仍然采用一个保守的方式来处理。

Raft在提交规则中引入了这样额外的复杂性，从而使得在leader复制之前的条目时，这些日志条目仍然可以保留他们原始的term值。在其他一致性算法中，当一个新leader复制之前term的条目时，它必须使用一个新的term值。Raft的方案使得理解日志条目更加简单，因为它们总是保持着最初的term值，不管是在不同时间还是不同的日志中。除此之外，相比于其他算法，在Raft中新leader会发送更少的旧条目(其他算法中必须发送冗余的日志条目，并在提交之前进行重新编号)。

5.4.3 正确性讨论

voter.png

给出了完整Raft算法后，我们可以更加精细的证明Leader完整属性是成立的(证明基于正确性证据，查看9.2节)。我们假设Leader完整性不成立，然后得出一个冲突。假设term T的leader_T提交了一个日志条目，但是这个条目不在未来的某个leader中。设定最小的不包含这个条目的leader的term是U，即leader_U中没有这个条目。

1. 在选举的时候，leader_U的日志中就没有这个条目(leader不会删除或者覆盖日志条目)。
2. leader_T将这个条目复制到大多数服务器上，leader_U收到大多数服务器的投票。因此，至少有一个服务器(投票者)即接收了leader_T的日志条目，又给leader_U投票了。如图9所示，这个投票者是证明冲突的关键所在。
3. 投票者必须是在给leader_U投票之前接受了leader_T的日志条目；否则它会拒绝leader_T的AppendEntries请求(它的当前term比T要大)。
4. 当投票者给leader_U投票时，它仍然存储着这个条目，这是因为中间所有的leader都存储着这个条目(基于假设)，而leader不会删除条目，同时follower只会删除它们和leader冲突的条目。
5. 投票者给leader_U投票了，这样的话leader_U的日志必须是和投票者一样新的。这导致了两个冲突。
6. 第一，如果投票者和leader_U的日志term是相同的，那么leader_U的日志至少是和投票者的日志一样长的，因此它会包含投票者日志中的所有条目。这是一个冲突，投票者包括这个条目，而leader_U中没有(基于假设)。
7. 如果他们的term不同，那么leader_U的最后一个日志条目的term必须是比投票者的term大。进一步的，它的term是比T大的，因为投票者的最后一个日志条目的term至少是T(已提交的这个条目是term T的)。创建leader_U的最后一个日志条目的之前leader是包含了这个提交的条目的(基于假设)。根据Log匹配属性，leader_U的日志中必须包含所有的提交条目，这是一个冲突。
8. 这样就完整了整个冲突证明。因此，所有term比T大的leader的日志中，必须包含了term T中提交的所有日志条目。
9. 日志匹配属性保证了后续的leader也会包括被间接提交的日志条目，如同图8(d)中的第2条。

给出了Leader完整属性，我们可以证明图3中的状态机正确性，即如果一个服务器应用了某个index的指令到它的状态机，那么在这个index位置，不会有其他服务器应用不同的指令。当一个服务器应用某个日志条目到状态机时，它的日志和leader的日志直到这个条目为止应该都是相同的，并且这个条目肯定是已提交的。现在考虑一下任意服务器应用的某个index的日志条目中最低的term。leader完整属性保证所有更高term的leader会存储相同的条目，因此应用这个条目的所有服务器都会应用相同的条目。因此，状态机正确性成立。

最后，Raft要求服务器按照日志顺序来应用条目。和状态机正确性结合起来，这意味着所有服务器都会应用完全相同的日志条目到它们的状态机，按照相同的顺序。

5.5 Followers和candidata宕机

到目前为止，我们一直在讨论leader故障的情况。相比leader故障，处理follower和candidate故障要简单的多。如果某个follower或candidate宕机了，那么后续发送给它的RequestVote和AppendEntries RPC请求都会失败。Raft处理这些失败的方式是无限的重试。如果宕机的服务器恢复了，RPC请求就会成功。如果一个服务器在处理完一个RPC请求但是在响应之前宕机了，那么当它重启后，它还会收到相同的请求。Raft RPC请求都是幂等的，因此这没有什么影响。比如说，当一个follower收到了一个AppendEntries请求，其中的内容都是自己日志中已有的日志条目，那么它就忽略这个请求。

5.6 时间和可用性

我们对Raft的要求之一是正确性必须不依赖于时间：系统不能够因为某个事件处理的过快或者过慢而产生不正确的结果。然而，可用性(系统在一定的时间内响应客户端的能力)不可避免的依赖于时间。比如说，如果消息交换花费的时间比典型的两次崩溃之间的时间还要长，那么candidate将不会保持足够的时间来等待赢得选举；没有稳定的leader，Raft没有办法做任何事情。

在leader选举中，时间非常重要。只有在系统满足下面这个时间要求，Raft才能够选举并维持一个稳定的leader：

broadcastTime << electionTimeout << MTBF

在这个不等式中，broadcastTime指的是一个服务器并行的发送RPC给集群中的所有其他服务器并收到回复所花费的平均时间；electionTimeout在5.2节中描述过；MTBF指的是同意个server在两次故障之间间隔时间的平均值。广播时间应该比选举超时要小一个数量级，这样leader就可以可靠的发送心跳消息给follower以防止它们开启一次选举；给出了随机化选举超时的机制，这个不等式也使得投票分裂不太可能。选举超时也应该比MTBF小一个数量级，这样系统才能稳定的运行。当leader宕机后，系统会在一个选举时间内不可用；我们想要这个时间在整体上看只意味着一小段时间。

广播时间和MTBF是底层系统的属性，而选举时间是我们的选择。Raft中的RPC一般都需要接受者将信息持久化到稳定存储，因此广播时间可能在0.5ms到20ms之间，取决于存储技术。作为结论，选举时间可能在10ms到500ms之间。典型的系统MTBF一般都是几个月或者更长，很容易满足时间要求。

---

1. LAMPORTM, L. The part-time parliament. ACM Transactions on Computuer Systems 16,2(May 1998) ↩

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

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 ↩

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) ↩

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 ↩

7. SHVACHKO, K., KUANG, H., RADIA, S., AND CHANSLER, R. The Hadoop distributed file system. In Proc. MSST'10, Symposium on Mass Storage System and Technologies(2010), IEEE Computer Society ↩

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

9. BURROWS, M. The Chubby lock service for loosely- coupled distributed systems. In Proc. OSDI’06, Sympo- sium 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 Con- ference (2010), USENIX, pp. 145–158. ↩

11. LAMPORT, L. The part-time parliament. ACM Transac- tions on Computer Systems 16, 2 (May 1998), 133–169. ↩

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

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

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

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

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

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