Raft论文手译（上）

摘要

????????Raft是一种管理日志一致性的算法。它可以产生和Paxos一样的结果，和Paxos一样高效，但其结构与Paxos有所不同。相对于Paxos，Raft更通俗易懂也更容易实现其系统功能。为了更利于理解，Raft将领导者选举、日志复制、安全性等重要要素进行分离，并大幅提升它们的相关性以减少原来需考虑的状态类型。根据用户的使用反馈，相对于Paxos，Raft更易于学生学习使用。Raft还包含一种改变簇成员的全新机制，它通过冗余技术来保证安全性。

1、介绍

????????一致性算法能使多台机器即使在部分成员宕机的情况下依然像一个整体一样工作。因此，它们在建立大规模可靠软件系统中扮演着重要角色。Paxos在过去十年都占据着主导地位，大多的一致性功能实现都是基于Paxos或受之启发的。Paxos也因此成为一致性算法教学的主要资料。

????????不幸的是，尽管不少人曾尝试去简化Paxos的实现，但它还是非常复杂的。此外，为了支持各种系统，它在结构上也需要做出不少的调整。这也就让系统工程师和学生费了不少功夫去解决这些问题。

????????在饱受Paxos的折磨后，我们设计出了一种全新的一致性算法，它更易于功能实现和教学。对于易于理解这个主要目标，我们做出了不同寻常的努力：我们能不能为实际的系统定义一种一致性算法，并通过一种比Paxos更通俗易懂的方式描述出来呢？此外，我们还希望这种算法能够为系统开发者们带来便利。重要的不仅仅是让算法跑通，更是要让大家理解它是怎么跑通的。

????????这种一致性算法叫Raft。在设计Raft算法的过程中，我们使用了几种技术来提升它的可读性，包括功能拆分（Raft分离了领导者选举、日志复制和安全性）和减少状态的种类（相对于Paxos，Raft减少了不确定性和功能耦合）。两所大学43名学生的学习的结果表明Raft比Paxos更通俗易懂：在学习了这两种算法后，相比于Paxos算法，33名学生能更好地回答Raft的问题。

Raft和许多现有的一致性算法类似，但它也有自己的创新点。

更可靠的领导者：相比于其他一致性算法，Raft采用的是更强大可靠的领导者。举个例子，日志条目只能从领导者流向其他服务器。这大大简化了日志复制管理，也使得Raft更利于理解。

领导者选举：Raft采用随机定时器来选举领导者。Raft简单地实现了一致性算法都需要的心跳机制，处理冲突的方式也简单迅速。

成员变动：在服务器集群变动上，Raft采用的是一种新的共同一致的机制，即多数一致覆盖少数差异。这就能让集群在配置发生改变时继续正常运行。

????????我们相信Raft在无论是在教学目的还是功能实现都比Paxos及其他一致性算法优秀。它比其他同类算法都简洁且易懂。该算法的描述十分完整，达到了实际系统的需求。它提供了几种开源实现方式，并被数家公司采用。它详细讲述并证实了其安全性。其效率也能与其他同类算法相提并论。

????????本篇论文讲述了复制状态机所遇到的问题（第二部分），讨论Paxos的优缺点（第三部分），讲述我们对该算法的理解（第四部分），展示Raft一致性算法（第五到第八部分），评价Raft算法（第九部分），并讨论相关的工作流程（第十部分）。

2、复制状态机

????????一致性算法是在复制状态机这个大背景下诞生的。通过一致性算法，服务器集群共同计算一致的数据，即便在少数几个服务器宕机的情况下整个集群仍能继续工作。分布式系统通过复制状态机来解决容错问题。举一个例子，典型的单簇首大型系统集群，比如GFS、HDFS和RAMCloud，使用的是分离复制状态机来进行领导者选举和存储宕机领导者的配置数据。而实现复制状态机的例子有有Chubby和Zookeeper。

????????复制状态机实现了日志复制，如图一所示。每个服务器都存储着一连串的命令日志。状态机就是这么一条条执行命令的。每条日志都记录着同一命令的同一步骤，状态机都在执行同样的命令步骤。那是因为状态机是不能进行回退操作的，它们状态保持一致，输出同样的结果。

????????保持日志同步是一致性算法的需完成的任务。服务器的同步模块会接收客户端请求并保存该条日志。它还会与其他服务器的同步模块保持通信，以确保每条日志即便在少数服务器失败的情况下最终依然包含同样的命令、同样的步骤。一旦命令完成复制，各服务器的同步模块就会按照日志顺序运行命令步骤，结果也会返回给客户端。如此一来，服务器集群就构成了一个非常可靠的状态机了。

在实际的系统中使用的一致性算法通常包含以下几点内容。

1、系统集群在所有非拜占庭错误的条件下能保证安全性（不会返回一个错误的结果），包括网络延迟、连接断开、丢包、重复包、重复命令。

2、只要服务器集群主体仍在运作并能够彼此间及和客户端通信，集群的所有功能都能使用。因此五个服务器组成的集群能够接受其中两个服务器失效。前提是服务器宕机重启后还能够恢复数据并重新加入原集群。

3、为了能够保证日志的完整，服务器集群没有时间依赖性，也就是错误的时钟和极端的消息延迟会引起可靠性问题。

4、通常情况下，只要集群中大多数服务器通过远程调用回复簇首，一条命令就算是完成了。少数服务器较慢响应并不会对集群整体的性能造成很大的影响。

3、Paxos的问题所在

????????在过去的十年里，Leslie Lamport的Paxos协议几乎成了”一致”的代名词。它是大学课堂所教的最常见的一致性协议。大多一致性功能的实现一开始都使用它。Paxos定义了一个通过单一决策达成一致的协议，例如单一的日志条目。我们把这样的分组称为单一决策的Paxos。之后Paxos把好几种这样的协议实例结合起来便形成了一连串的决策，例如日志（多重Paxos）。Paxos能保证安全性和集群活跃性，它还支持集群成员变化。它能够有效应对大多数情况，其可靠性也得到了证明。

????????不幸的是，Paxos有两个很明显的缺点。第一，Paxos非常复杂难懂。完整的Paxos解释本身并不透明。很少有人真正把Paxos弄清楚。因此大家简化Paxos上做了不少尝试。这些尝试聚焦于单一决策的集群，即便如此，这项工作还是充满挑战的。在2012年NSDA对现场参与者的非正式调查中，我们发现大多人觉得Paxos并不友好，即便经验丰富的研究人员也是如此。我们被Paxos弄得晕头转向，我们很难对Paxos有完整的理解，直到我们等来Paxos的简化版本并改用替代协议，整个过程花了我们将近一年的时间。

????????我们假设Paxos内容的不透明是由它采用单一决策集群机制造成的。单一决策的Paxos内部错综复杂。它分成了两个部分，但其内部说明并不简洁，且这两部分的解释是耦合在一起的。正因如此，解读这种单一决策协议的工作流程就变得尤为困难。而多决策者的Paxos添加了新的规定，这更是大大增加了其复杂性。我们相信多决策者一致性的问题能够通过其他更简单直接的方法解决。

????????第二，Paxos并没有为实际的功能实现提供很好的函数。其中一个原因是现在并没有大家一致认同的多决策者Paxos算法。Lamport的描述大多针对的是单一决策者的Paxos。他构想过多决策者Paxos可能的实现方案，但是许多细节现在都缺失了。有些人尝试过优化Paxos，但这些优化版本和Lamport当初的构想差异很大。一些系统，例如Chubby，采用了和Paxos很像的算法，但是大多细节都没有公开。

????????此外，Paxos的结构对于实际构建系统来说非常糟糕。这就是另一个单一决策者Paxos带来的结果。举个例子，把一堆相互独立的日志条目合成一条日志串并不能带来什么好处，这只会增加复杂性。日志系统按严格顺序附加日志，这样设计更简单也更高效。还有一个问题是Paxos将点对点对称通信作为其核心（尽管最后称弱化领导者地位是在优化性能）。尽管在简化的场景下单一决策者机制是合理的，但很少有系统会采用这种方法。如果非要产生一连串的决策，那么先选举出一个领导者，然后让领导者来处理这些决策，这么做既简单有迅速。

????????如此一来，实际的系统和Paxos看上去一点也不沾边。系统的功能实现一开始采用Paxos算法，实现过程中才发现一堆问题，而后开发出来的系统结构和原构想相差甚远。这既费时间又容易出错，而Paxos本身复杂难懂又把问题弄得更难处理。Paxos的公式对于改善定理验证也许有些帮助，但要实现Paxos是非常困难的，这也证明了其价值甚微。以下是Chubby的开发者的常见观点。
????????Paxos算法内容描述和现实中系统需求之间有着很明显的鸿沟…最终的系统将基于一个还未证明有效的协议。

????????基于这些问题，我们认为Paxos并没能为系统开发和一致性算法教学提供好的方法。考虑到一致性算法对大型软件系统的重要性，我们决定看看能不能设计出取代Paxos更好的一致性算法。Raft便是我们的实验成果。

4、通俗易懂的设计

????????我们设计Raft有几个目标：它必须为系统开发提供完整且实际的方法，进而明显减少开发者设计工作。它必须在各种条件下都具备安全性，在通常情况下可高效运行。但我们最主要的目标兼最大的挑战是通俗易懂。必须能让大多使用者都能理解此算法。此外，必须尽可能让使用者能对算法有直观的认识，这样系统开发者才能真正实现其功能。

????????在设计Raft算法时，有几个地方我们采用了替代方案。在这种情况下，替代方案都是出于方便理解。在各种替代方案中做选择究竟有多难呢（例如，状态空间复杂性，实现方式是否简便）？要怎样才能让读者更容易理解原理、实现功能？

????????我们知道这项研究是带有很大程度的主观因素的。即便如此，我们使用了两种合适的技巧。第一个是大家熟知的问题分解。我们尽可能把大问题分解成易解决、能解释、易理解的独立子问题。例如，我们把Raft这个整体拆分成领导者选举、日志复制、安全性和成员变动四个部分。

????????第二是通过减少状态种类来简化状态空间，让系统变得更加简单，消除可能带来的不确定性。特别注意的是，Raft的日志不允许一个萝卜多个坑，限制了日志不完整的产生途径。虽然大多时候我们都在努力消除不确定性，但在个别情况下，不确定性确实能提高算法的可读性。特别是带有随机性的方法，它们带来了程序运行的不确定性，但是因为涵盖了所有可能发生的情况（随机选择，无伤大雅），因此它们往往可以减少一些不必要的状态。我们利用随机性来简化Raft的领导者选举算法。

5、Raft一致性算法

????????Raft是一种管理复制日志的算法，它在论文第二部分的图2讲述。接着概述此一致性算法，可供参考。第三部分列出了关键的组成部分，它们会在后面的内容中一一讲述。

????????为实现一致性这个功能，Raft首先会选出一个领导者，让其负责管理复制日志。领导者从客户端那里接收日志条目，将日志分发给其他服务器，并在环境安全的时候通知它们把日志提交至状态机。有了领导者，管理复制日志的工作就简单多了。举个例子，领导者不需要询问其他服务器，自行决定新日志条目存放的位置，接着数据流会立刻从领导者发往其他服务器。领导者可能会出错或断连，而这时集群就会选举新的领导者。

考虑到领导者的职能，Raft把整个一致性问题分解成三个相互独立的子问题，我们会在下面的标题中讨论。

领导者选举：一旦出现领导者出错，就必须选出新的领导者。

日志复制：领导者必须能够接收客户端日志条目并分发给集群的其他成员，强制它们与自己保持一致。

安全性：Raft安全性的关键是状态机安全，正如图3所示。如果有服务器向状态机提交日志，那么其他服务器就不会在相同的日志标记下发出不同的命令。5.4部分会讲述如何实现这种安全性。解决的方法包括5.2部分提讲到的加强选举机制。

讲完一致性算法后，本节还会讨论可用性的问题以及定时器在系统中所充当的角色。

5.1、Raft的基础

????????Raft集群包含了若干个服务器，常见的是5个，在这种情况下集群最多能容忍2个服务器出错。在任何时候，各服务器都会扮演三种角色中的其中一种：领导者、追随者或竞选者。正常情况下，只会有一个领导者，而剩下的全都是追随者。追随者的工作是被动的：它们不会主动发出自己请求，只会对领导者或竞选者的请求做出响应。只有领导者才能处理所有的客户端请求（如果客户端和追随者通信，追随者会将其引导至领导者）。第三种角色是竞选者，它是用来选举领导者的，节5.2的图4说明了这种角色和它的切换过程。下面会讲述它的切换过程。

????????Raft将一个一个的任期作为时间单位，正如图5所示。任期值用连续的整数表示。每个任期首先进行领导者选举，会有一个或多个竞选者试着推举自己成为领导者，节5.2会讲到。如果竞选者竞选成功，那么它就会切换为本任期的领导者。在某些情况下，会出现选票分散在多个竞选者手上，没能选出领导者于是本任期结束。集群会很快开始下一轮任期（开始新一轮的投票选举），Raft会保证每一轮任期最多出现一个领导者。

????????各个服务器在不同时候可能会察觉出数次角色切换，而在某些情况下，有的服务器可能察觉不出集群正在进行选举，甚至没有经历完整的任期。在Raft中，任期扮演着逻辑时钟的角色。服务器能够察觉出过时信息，例如任期时间很长的领导者。每个服务器都保存着当前的任期号，任期号是单调递增的。只要服务器还能通信，它们就会交换任期号。如果某个服务器的任期号小于其他服务器的任期号，它就把任期号更新为更大的那个。如果领导者或竞选者发现自己的任期号已经过时，就会立刻将自己切换为追随者。如果领导者接收到一个带旧任期号的请求，则会拒绝该请求，

????????Raft通信服务是通过远程调用完成的，而基本的一致性算法只需要两种远程调用。竞选者会在竞选期间使用选票请求这种远程调用（节5.2），而领导者会使用附加信息这种远程调用来分发日志，同时也将其作为心跳通信（节5.3）。节7还新增了一种三方的远程调用用于传输服务器快照。如果服务器没能及时收到响应，就会重复该远程调用。服务器并行使用远程调用已达到最佳性能。

5.2、领导者选举

????????Raft通过心跳机制来触发领导者选举。各服务器启动后会成为追随者。服务器会保持追随者的状态直到收到领导者或者竞选者的有效远程调用。领导者会周期性地向所有追随者发送心跳包（不带任何条目的远程调用）以维护其控制。如果一个追随者在一段时间内（叫选举超时）没能收到通信数据包，则它认为没有领导者了，并开始新一轮的领导者选举。

????????为开始选举，一个追随者会自增自己的任期号并转换为竞选者。接着它会投自己一票并向集群的其它服务器发出投票请求的远程调用。竞选者会保持当前的状态直到以下三种情况发生：（a）它赢得了本次选举，（b）其他服务器将自己转换成领导者，或（c）在一段时间内没有赢家。这些情况会在后面的文段中单独讨论。

????????如果一个竞选者在同一个任期内收到大多来自集群其他服务器的选票，则它竞选成功。每个服务器按照先来先投的原则在一个任期内最多投一张票给竞选者（5.4部分在选票中增加了额外的限制）。过半原则确保在一个任期内最多一个竞选者能赢得竞选。一旦竞选者赢得选举，它就转换成领导者。接着它会向其它所有服务器发送心跳包来建立自己的管理和阻止新的竞选。

????????在竞选者等待选票的时候，它可能受到其他服务器的“添加条目”的远程调用，声称自己是领导者。如果这个领导者的任期号（包含在这个远程调用里）比这个竞选者的大，则这个竞选者转换回追随者。如果这个远程调用的任期号小于竞选者的任期号，则它拒绝此远程调用并继续维持竞选者状态。

????????第三种情况是竞选者在竞选中既没胜出也没失败：如果很多追随者都同时转换成竞选者，选票就会很分散，也就没有哪个竞选者获得过半的选票。如果这种情况发生了，所有竞选者都会超时并增加任期号并再次启动“请求投票”的远程调用，开始新一轮的选举。然而，如果不采取额外的措施，选票分散的情况不断地出现。

????????Raft采用随机选举超时机制来确保选票分散的情况少于发生并且快速解决这种问题。首先为了避免选票分散，选举超时选择一个固定的随机值（例如150到300毫秒）。这样分布服务器的超时时间就可以在大多数情况下只出现一个服务器超时。它会赢得选举并在其他服务器超时前发送心跳包。各竞选者会再选举开始时重置随机超时定时器，并且它会在新一轮选举到了前等待超时；这样能减少在新一轮选举中选票分散的情况再次发生的可能性。9.3节表明这种方法可以很快推选出领导者。

????????选举机制就是一个例子，它解释了可理解性是怎么让我们在备选方案中做选择的。一开始我们计划采用一种等级机制，每个竞选者都会被赋予一个级别，这些等级用于竞选者之间竞争。如果一个竞选者发现另一个竞选者的等级更高，则它会转换会追随者好让这个竞选者更容易赢得竞选。我们发现这种方法会在可用性上产生很难发现的问题（低级别的服务器可能需要超时并在高等级的服务器失败时再次成为竞选者，但如果这进行地太快，就会重置选举领导者的进程）我们在算法上做了几次调整，可每当调整后，新的极端情况又出现了。最后，我们得出结论，随机重试的方法更直观、更好理解。

5.3、日志复制

????????一旦选举出领导者，它便开始向客户端提供服务。每个客户请求包含着一条复制状态机执行命令。领导者将这条命令作为一个条目加入到日志中，接着向其他服务器发送“添加条目”的远程调用来复制这个条目。当这个条目被安全复制后（下面会讲述），领导者会将这个条目添加到自己的状态机去并把执行结果返回给客户端。如果追随者宕机或运行缓慢或着网络数据包丢失，领导者会一直重试“添加条目”这个远程调用（即便它已经回复客户端了）直到所有的追随者最终存储所有的日志条目。


????????日志的组织如图6所示。每条日志条目在被领导者接收时都存储着一个带有任期号的状态机命令。日志条目的任期号用来检测日志是否不一致以及确保图3中的某些适当性。每条日志条目也是一个整型的下标，用来标识它在日志中的位置。

????????什么时候向状态机提交日志条目安全由领导者决定；这种条目叫做“已提交”条目。Raft能够保证已提交的条目是可靠存储的并最终让所有的可运行的状态机都执行。一旦领导者创建一个日志条目并将其复制到大多数状态机，这个日志条目就算是提交了（例如，图6的日志7）。它还提交了这个领导者之前创建的所有条目，包括前任领导者创建的条目。节5.4讲述了在领导者变更时这个规定的巧妙之处，也表明这么定义“提交”是安全的。领导者会紧跟它所知的最高已提交日志条目的下标，它包括以后的“添加条目”的远程调用（包括心跳包），好让其它服务器最终发现。一旦追随者发现日志条目已提交，它会将这个条目添加到本地状态机中去（按照日志的顺序）。

????????我们设计出Raft日志机制用来维护不同服务器日志的高度一致性。不仅简化了系统行为还使其更具可预测性，而这却又是安全性的重要保障。Raft遵循以下三点，它们一起构成了图3的日志匹配属性。
????????如果两个在不同日志的条目具有相同的下标和任期，则它们存储相同的命令。
????????如果两个在不同日志的条目具有相同的下标和任期，则之前所有的条目中的日志是相同的。

????????第一个性质遵循一个事实，那就是领导者在一个任期内最多创建一个带有日志下标的条目，而日志条目在日志中的位置是绝不会改变的。第二个性质是由“添加条目”实现的一种一致性检查来保证的。当发送一个“添加条目”的远程调用时，领导者会把条目的下标和任期写进日志中，日志会立即生成新的条目。如果追随者没有在自己的日志中找到相同下标和任期的条目，它就会拒绝这个新条目。这种一致性检查是个开始：日志的初始空状态满足日志匹配性质，而无论日志什么时候增加了，一致性检查都会保留这种日志匹配机制。结果就是，无论什么时候“添加日志”远程调用返回成功，领导者都能察觉到追随者的日志即便添加了新的日志条目也能和它的日志相一致。

????????在进行一般操作时，领导者和追随者的日志保持一致，所以“添加日志”远程调用的一致性检查是绝对不会失败的。然而，领导者宕机会导致日志不一致（往届领导者的日志可能并没有完全复制所有的条目）。这些不一致现象会随着一连串领导者和追随者崩溃而加剧。图7说明了追随者和新领导者日志不一致的可能情况。领导者有的条目，追随者可能没有。有些额外的条目可能领导者没有，又或者领导者追随者都没有。


????????图7：当上面的领导者当权，（a到f）任何一种情况都有可能出现在追随者中。每个盒子代表一个日志条目；盒子上的数字代表任期。追随者可能错过了一些条目（a和b），也可能有额外几个没提交的条目（c和d），又或者二者都有（e和f）。举一个例子，如果服务器领导者的任期号是2，它添加了几个条目到自己的日志里，接着在提交前就崩溃了；它很快重启，成为任期号为3的领导者，接着往日志里添加稍微更多的条目；在任期2或任期3提交前又崩溃了，接下来几个任期也是这么如此的话，那么就会出现f的情况。

????????在Raft中，领导者通过强制追随者复制它的日志来解决不一致问题。这就意味着追随者中冲突的条目会被领导者的日志覆盖掉。节5.4会说明在应对更多限制的时候，这是安全的。

????????为了让追随者的日志和领导者保持一致，领导者必须找到二者最近一次日志相同的位置，删除追随者这个位置之后的日志，并向所有追随者发送领导者在这个位置之后的条目。所有这些操作会在响应“添加条目”远程调用进行一致性检查时发生。领导者会为每一个追随者维护一个叫“nextIndex”的变量，它表示领导者发给追随者下一个条目的下标。当一个领导者刚掌权，它会把所有的“nextIndex”值初始为它的最新日志下标值（如图7的11）。如果追随者的日志和领导者的不一致，“添加条目”操作的一致性检查会在下一次远程调用时失败。追随者拒绝远程调用，则领导者就会让“nextIndex”自减并重试“添加条目”远程调用。最终，“nextIndex”就会到达领导者和追随者日志相同的位置。此时，“添加条目”就会成功，它消除了追随者的冲突条目并添加了领导者的日志。一旦“添加条目”成功，追随者和领导者的日志就一致了，它会继续在当前任期下保持现状。


????????需要的话，这个协议可以优化以减少拒绝“添加条目”远程调用的次数。举个例子，当追随者发送拒绝“添加条目”远程调用的请求时，它可以包含这个冲突条目的任期号和第一个同样是这个任期号的条目。有了这个信息，领导者在自减“nextIndex”时，就能跳过所有带这个任期号的条目了；“添加条目”远程调用要求每一任期的冲突条目都这么做，而不是每个条目都使用一次远程调用。实际上，我们对这种优化的必要性是带有质疑的，因为失败不常发生而且不太可能出现大量条目不一致。

????????有了这种机制，领导者就不必在掌权的时候做任何特殊的恢复日志一致性操作了。领导者开始常规操作，而日志会在“添加条目”的一致性检查失败时自动响应。而领导者是绝不会覆盖或删除自己的日志的（图3的领导者“只会添加”性质）。

????????这种日志复制机制展示了节2所说的一致性性质的可实现性：Raft能够在大多数服务器还在运作时，接收、复制和添加新的条目；一般情况下，一个新的条目能在一轮远程调用后复制到集群的大多数追随者；而稍微慢一点的追随者不会影响总体性能。

最后

由于Raft论文篇幅较长，论文后半部分翻译可以在下一篇进行。