CONSENSUS:BRIDGING THEORY AND PRACTICE(第0~3章)

译者序

本文是对Raft论文《CONSENSUS:BRIDGING THEORY AND PRACTICE》Raft相关内容的翻译。其中不包含前言介绍、算法证明、教学/学习方法以及不同一致性算法间的比较章节，只包含了Raft本身以及相关优化章节的部分。之前已经有人翻译了Raft小论文，可以参考https://github.com/maemual/raft-zh_cn ，本文第0章中的内容就是引用自小论文，其他章节也是如果是大小论文中重复的内容就会引用小论文中的翻译。此外所有图片、表格中的内容均没有翻译，一是重新制作表格图片麻烦，二是看完段落翻译读者自己看那么点英文应该也很简单了(我这英语水平都能爬着看懂，还有谁能看不懂)。

大小论文的差别在于细节和优化，大论文提到了非常多的更深入的问题以及更详细的讨论，工程实现上真想做好必须参考大论文。

本系列是在先通读一遍(部分章节可能重复看了好几遍)的情况下开始的，其中对难以理解的部分都加上了译者注方便读者阅读，有的时候大神些东西就是不屑于说的太清楚，为了方便读者以及自己以后可能得回看我写出自己的理解。

本人也在之前看完小论文之后在github创建了一个项目实现完整的raft，由于知道大论文便开始看大论文停止了开发，等翻译完大论文就会继续开发，欢迎一起，项目为C++开发的ccraft。

第0章 引用小论文

摘要

Raft 是一种为了管理复制日志的一致性算法。它提供了和 Paxos 算法相同的功能和性能，但是它的算法结构和 Paxos 不同，使得 Raft 算法更加容易理解并且更容易构建实际的系统。为了提升可理解性，Raft 将一致性算法分解成了几个关键模块，例如*选举、日志复制和安全性。同时它通过实施一个更强的一致性来减少需要考虑的状态的数量。从一个用户研究的结果可以证明，对于学生而言，Raft 算法比 Paxos 算法更加容易学习。Raft 算法还包括一个新的机制来允许集群成员的动态改变，它利用重叠的大多数来保证安全性。

介绍

一致性算法允许一组机器像一个整体一样工作，即使其中一些机器出现故障也能够继续工作下去。正因为如此，一致性算法在构建可信赖的大规模软件系统中扮演着重要的角色。在过去的 10 年里，Paxos 算法统治着一致性算法这一领域：绝大多数的实现都是基于 Paxos 或者受其影响。同时 Paxos 也成为了教学领域里讲解一致性问题时的示例。

但是不幸的是，尽管有很多工作都在尝试降低它的复杂性，但是 Paxos 算法依然十分难以理解。并且，Paxos 自身的算法结构需要进行大幅的修改才能够应用到实际的系统中。这些都导致了工业界和学术界都对 Paxos 算法感到十分头疼。

和 Paxos 算法进行过努力之后，我们开始寻找一种新的一致性算法，可以为构建实际的系统和教学提供更好的基础。我们的做法是不寻常的，我们的首要目标是可理解性：我们是否可以在实际系统中定义一个一致性算法，并且能够比 Paxos 算法以一种更加容易的方式来学习。此外，我们希望该算法方便系统构建者的直觉的发展。不仅一个算法能够工作很重要，而且能够显而易见的知道为什么能工作也很重要。

Raft 一致性算法就是这些工作的结果。在设计 Raft 算法的时候，我们使用一些特别的技巧来提升它的可理解性，包括算法分解（Raft 主要被分成了*选举，日志复制和安全三个模块）和减少状态机的状态（相对于 Paxos，Raft 减少了非确定性和服务器互相处于非一致性的方式）。一份针对两所大学 43 个学生的研究表明 Raft 明显比 Paxos 算法更加容易理解。在这些学生同时学习了这两种算法之后，和 Paxos 比起来，其中 33 个学生能够回答有关于 Raft 的问题。

Raft 算法在许多方面和现有的一致性算法都很相似（主要是 Oki 和 Liskov 的 Viewstamped Replication），但是它也有一些独特的特性：

强领导者：和其他一致性算法相比，Raft 使用一种更强的领导能力形式。比如，日志条目只从领导者发送给其他的服务器。这种方式简化了对复制日志的管理并且使得 Raft 算法更加易于理解。
领导选举：Raft 算法使用一个随机计时器来选举领导者。这种方式只是在任何一致性算法都必须实现的心跳机制上增加了一点机制。在解决冲突的时候会更加简单快捷。
成员关系调整：Raft 使用一种共同一致的方法来处理集群成员变换的问题，在这种方法下，处于调整过程中的两种不同的配置集群中大多数机器会有重叠，这就使得集群在成员变换的时候依然可以继续工作。
我们相信，Raft 算法不论出于教学目的还是作为实践项目的基础都是要比 Paxos 或者其他一致性算法要优异的。它比其他算法更加简单，更加容易理解；它的算法描述足以实现一个现实的系统；它有好多开源的实现并且在很多公司里使用；它的安全性已经被证明；它的效率和其他算法比起来也不相上下。

复制状态机

一致性算法是从复制状态机的背景下提出的。在这种方法中，一组服务器上的状态机产生相同状态的副本，并且在一些机器宕掉的情况下也可以继续运行。复制状态机在分布式系统中被用于解决很多容错的问题。例如，大规模的系统中通常都有一个集群领导者，像 GFS、HDFS 和 RAMCloud，典型应用就是一个独立的的复制状态机去管理领导选举和存储配置信息并且在*宕机的情况下也要存活下来。比如 Chubby 和 ZooKeeper。

复制状态机通常都是基于复制日志实现的，如图2.1。每一个服务器存储一个包含一系列指令的日志，并且按照日志的顺序进行执行。每一个日志都按照相同的顺序包含相同的指令，所以每一个服务器都执行相同的指令序列。因为每个状态机都是确定的，每一次执行操作都产生相同的状态和同样的序列。

保证复制日志相同就是一致性算法的工作了。在一台服务器上，一致性模块接收客户端发送来的指令然后增加到自己的日志中去。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求，尽管有些服务器会宕机。一旦指令被正确的复制，每一个服务器的状态机按照日志顺序处理他们，然后输出结果被返回给客户端。因此，服务器集群看起来形成一个高可靠的状态机。

实际系统中使用的一致性算法通常含有以下特性：

安全性保证（绝对不会返回一个错误的结果）：在非拜占庭错误情况下，包括网络延迟、分区、丢包、冗余和乱序等错误都可以保证正确。
可用性：集群中只要有大多数的机器可运行并且能够相互通信、和客户端通信，就可以保证可用。因此，一个典型的包含 5 个节点的集群可以容忍两个节点的失败。服务器被停止就认为是失败。他们当有稳定的存储的时候可以从状态中恢复回来并重新加入集群。
不依赖时序来保证一致性：物理时钟错误或者极端的消息延迟在可能只有在最坏情况下才会导致可用性问题。
通常情况下，一条指令可以尽可能快的在集群中大多数节点响应一轮远程过程调用时完成。小部分比较慢的节点不会影响系统整体的性能。

第3章 Raft基础

这章讲述Raft算法。我们设计Raft使其尽可能容易理解；第一段描述我们对易理解性的设计方法。后面的段落描述算法本身并包含了我们为了易理解性而设计选择的范例。

3.1 易理解性设计

我们设计Raft有几个目标：它要能为系统构建提供完整的、可实施的方案，因此显著减少了开发者的设计工作量；它要在各种条件下保证安全性，在典型的操作下保证可用性；并且要对各种通用的操作是有效的。但我们最重要的目标也是最大的挑战就是易理解性，要尽可能的保证对于大部分读者理解这个算法是舒服的。此外，要尽可能的使得开发这个算法是直观的，以便系统构建者可以方便的制作现实世界中难以避免的扩展。

在Raft的设计中我们不得不在多个可供选择的方法中做选择。这种情况下我们通过易用性对可供选择的方案作出评估：解释每个可供选择的方法有多难（例如它的状态空间有多复杂，并且它是不是有精妙的实现？），并且对于读者来说完整的理解方法和实现容易吗？

我们承认这样的分析有很高程度的主观性；但是我们使用了两个通常适用的技术。第一个技术是众所周知的问题分解的方法：我们尽可能的分解问题为分离的可解决的、可解释的、容易理解的相对不互相依赖的方面。例如在Raft中我们分离*选举、日志复制和安全性。

我们的第二种方法是通过减少要考虑的状态的数量来简化状态空间，使得系统更加清晰，并尽可能消除不确定性。特别地，日志不允许有洞(holes)，Raft限制了节点间会导致日志不一致的可能。尽管在大多数的情况下我们尝试消除不确定性，还是有一些场景不确定性的引入会提高易理解性。特别地，随机的方法引入了不确定性，但是通过处理所有可能的选择的方案(类似于随便选择吧，都不重要)引入它会减少状态空间。我们使用随机的方式去简化Raft*选举算法。

3.2 Raft概览

Raft是一个管理复制log组的算法。图3.1概要地总结了算法以供参考，图3.2列举了算法的关键属性；
这些元素都会在本章剩余的部分讨论。

Raft通过选举一个*，然后给予他全部的管理复制日志的责任来实现一致性。*从客户端接收日志条目，把日志条目复制到其他服务器上，并且当保证安全性的时候告诉其他的服务器应用日志条目到他们的状态机中。拥有一个*大大简化了对复制日志的管理。例如，*可以决定新的日志条目需要放在日志中的什么位置而不需要和其他服务器商议，并且数据都从*流向其他服务器。一个*可以宕机，可以和其他服务器失去连接，这时一个新的*会被选举出来。

通过*的方式，Raft 将一致性问题分解成了三个相对独立的子问题，这些问题会在接下来的子章节中进行讨论：

• 领导选举：一个新的*需要被选举出来，当现存的*宕机的时候（章节 3.4）
• 日志复制：*必须从客户端接收日志然后复制到集群中的其他节点，并且强制要求其他节点的日志保持和自己相同(3.5)。
• 安全性：在 Raft 中安全性的关键是在图 3.2 中展示的状态机安全：如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中，那么其他服务器节点不能在同一个日志索引位置应用一个不同的指令。章节 3.6 阐述了 Raft 算法是如何保证这个特性的；这个解决方案涉及到一个额外的选举机制（3.4 节）上的限制。

3.3 Raft基础

一个 Raft 集群包含若干个服务器节点；通常是 5 个，这允许整个系统容忍 2 个节点的失效。在任何时刻，每一个服务器节点都处于这三个状态之一：*、跟随者或者候选人。在通常情况下，系统中只有一个*并且其他的节点全部都是跟随者。跟随者都是被动的：他们不会发送任何请求，只是简单的响应来自领导者或者候选人的请求。*处理所有的客户端请求（如果一个客户端和跟随者联系，那么跟随者会把请求重定向给*）。第三种状态，候选人，是用来在 3.4 节描述的选举新*时使用。图 3.3 展示了这些状态和他们之前转换关系；这些转换关系会在接下来进行讨论。

Raft 把时间分割成任意长度的任期，如图3.4。任期用连续的整数标记。每一段任期从一次选举开始，就像章节3.4描述的一样，一个或者多个候选人尝试成为领导者。如果一个候选人赢得选举，然后他就在接下来的任期内充当*的职责。在某些情况下，一次选举过程会造成选票的瓜分。在这种情况下，这一任期会以没有*结束；一个新的任期（和一次新的选举）会很快重新开始。Raft 保证了在一个给定的任期内，最多只有一个领导者。

不同的服务器节点可能多次观察到任期之间的转换，但在某些情况下，一个节点也可能观察不到任何一次选举或者整个任期全程。任期在 Raft 算法中充当逻辑时钟的作用，这会允许服务器节点查明一些过期的信息比如陈旧的领导者。每一个节点存储一个当前任期号，这一编号在整个时期内单调的增长。当服务器之间通信的时候会交换当前任期号；如果一个服务器的当前任期号比其他人小，那么他会更新自己的编号到较大的编号值。如果一个候选人或者领导者发现自己的任期号过期了，那么他会立即恢复成跟随者状态。如果一个节点接收到一个包含过期的任期号的请求，那么他会直接拒绝这个请求。

Raft 算法中服务器节点之间通信使用远程过程调用（RPCs），并且基本的一致性算法只需要两种类型的 RPCs。请求投票（RequestVote） RPCs 由候选人在选举期间发起（章节3.4），然后附加条目（AppendEntries）RPCs 由*发起，用来复制日志和提供一种心跳机制（章节3.5）。*转换(章节3.10)机制在子章节中描述，介绍了一个两个一致性算法核心RPC之外的一个新的RPC。

我们选择结构化的RPC交流以简化服务见的沟通。每个请求类型有相应的响应类型。Raft假定RPC的请求和响应会丢；请求者负责对没有及时收到响应的RPC进行重试。服务为了最好的性能并发的发起RPC请求，Raft并不会假定网络保留了RPC的顺序。

3.4 *选举

Raft 使用一种心跳机制来触发*选举。当服务器程序启动时，他们都是跟随者身份。一个服务器节点继续保持着跟随者状态直到他从*或者候选者处接收到有效的 RPCs。领导者周期性的向所有跟随者发送心跳包（即不包含日志项内容的附加日志项 RPCs）来维持自己的权威。如果一个跟随者在一段时间里没有接收到任何消息，也就是选举超时，那么他就会认为系统中没有可用的领导者,并且发起选举以选出新的领导者。

要开始一次选举过程，跟随者先要增加自己的当前任期号并且转换到候选人状态。然后他会并行的向集群中的其他服务器节点发送请求投票的 RPCs 来给自己投票。候选人会继续保持着当前状态直到以下三件事情之一发生：(a) 他自己赢得了这次的选举，(b) 其他的服务器成为领导者，(c) 一段时间之后没有任何一个获胜的人。这些结果会分别的在下面的段落里进行讨论。

当一个候选人从整个集群的大多数服务器节点获得了针对同一个任期号的选票，那么他就赢得了这次选举并成为*。每一个服务器最多会对一个任期号投出一张选票，按照先来先服务的原则（注意：3.6 节在投票上增加了一点额外的限制）。要求大多数选票的规则确保了最多只会有一个候选人赢得此次选举（图3.2中的选举安全性）。一旦候选人赢得选举，他就立即成为*。然后他会向其他的服务器发送心跳消息来建立自己的权威并且阻止新的*的产生。

在等待投票的时候，候选人可能会从其他的服务器接收到声明它是*的附加日志项 RPC。如果这个*的任期号（包含在此次的 RPC中）不小于候选人当前的任期号，那么候选人会承认*合法并回到跟随者状态。 如果此次 RPC 中的任期号比自己小，那么候选人就会拒绝这次的 RPC 并且继续保持候选人状态。

第三种可能的结果是候选人既没有赢得选举也没有输：如果有多个跟随者同时成为候选人，那么选票可能会被瓜分以至于没有候选人可以赢得大多数人的支持。当这种情况发生的时候，每一个候选人都会超时，然后通过增加当前任期号来开始一轮新的选举。然而，没有其他机制的话，选票可能会被无限的重复瓜分。

Raft 算法使用随机选举超时时间的方法来确保很少会发生选票瓜分的情况，就算发生也能很快的解决。为了阻止选票起初就被瓜分，选举超时时间是从一个固定的区间（例如 150-300毫秒）随机选择。这样可以把服务器都分散开以至于在大多数情况下只有一个服务器会选举超时；然后他赢得选举并在其他服务器超时之前发送心跳包。同样的机制被用在选票瓜分的情况下。每一个候选人在开始一次选举的时候会重置一个随机的选举超时时间，然后在超时时间内等待投票的结果；这样减少了在新的选举中另外的选票瓜分的可能性。9.3 节展示了这种方案能够快速的选出一个*。

*选举这个例子,体现了可理解性原则是如何指导我们进行方案设计的。起初我们计划使用一种排名系统：每一个候选人都被赋予一个唯一的排名，供候选人之间竞争时进行选择。如果一个候选人发现另一个候选人拥有更高的排名，那么他就会回到跟随者状态，这样高排名的候选人能够更加容易的赢得下一次选举。但是我们发现这种方法在可用性方面会有一点问题（如果高排名的服务器宕机了，那么低排名的服务器可能会超时并再次进入候选人状态。而且如果这个行为发生得足够快，则可能会导致整个选举过程都被重置掉）。我们针对算法进行了多次调整，但是每次调整之后都会有新的问题。最终我们认为随机重试的方法是更加明显和易于理解的。

3.5 日志复制

一旦一个*被选举出来，他就开始为客户端提供服务。客户端的每一个请求都包含一条被复制状态机执行的指令。*把这条指令作为一条新的日志条目附加到日志中去，然后并行的发起附加条目 RPCs 给其他的服务器，让他们复制这条日志条目。当这条日志条目被安全的复制（下面会介绍），*会应用这条日志条目到它的状态机中然后把执行的结果返回给客户端。如果跟随者崩溃或者运行缓慢，再或者网络丢包，*会不断的重复尝试附加日志条目 RPCs （尽管已经回复了客户端）直到所有的跟随者都最终存储了所有的日志条目。

日志以图3.5展示的方式组织。每一个日志条目存储一条状态机指令和从*收到这条指令时的任期号。日志中的任期号用来检查是否出现不一致的情况，同时也用来保证图3.2中的某些性质。每一条日志条目同时也都有一个整数索引值来表明它在日志中的位置。

*来决定什么时候把日志条目应用到状态机中是安全的；这种日志条目被称为已提交。Raft 算法保证所有已提交的日志条目都是持久化的并且最终会被所有可用的状态机执行。在*将创建的日志条目复制到大多数的服务器上的时候，日志条目就会被提交（例如在图3.5中的条目 7）。同时，*的日志中之前的所有日志条目也都会被提交，包括由其他*创建的条目。3.6节会讨论某些当在*改变之后应用这条规则的隐晦内容，同时他也展示了这种提交的定义是安全的。*跟踪了最大的将会被提交的日志项的索引，并且索引值会被包含在未来的所有附加日志 RPCs （包括心跳包），这样其他的服务器才能最终知道*的提交位置。一旦跟随者知道一条日志条目已经被提交，那么他也会将这个日志条目应用到本地的状态机中（按照日志的顺序）。

我们设计了 Raft 的日志机制来维护一个不同服务器的日志之间的高层次的一致性。这么做不仅简化了系统的行为也使得更加可预计，同时他也是安全性保证的一个重要组件。Raft 维护着以下的特性，这些同时也组成了图3.2中的日志匹配特性：

如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。
如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。
第一个特性来自这样的一个事实，*最多在一个任期里在指定的一个日志索引位置创建一条日志条目，同时日志条目在日志中的位置也从来不会改变。第二个特性由附加日志 RPC 的一个简单的一致性检查所保证。在发送附加日志 RPC 的时候，*会把新的日志条目紧接着之前的条目的索引位置和任期号包含在里面。如果跟随者在它的日志中找不到包含相同索引位置和任期号的条目，那么他就会拒绝接收新的日志条目。一致性检查就像一个归纳步骤：一开始空的日志状态肯定是满足日志匹配特性的，然后一致性检查保护了日志匹配特性当日志扩展的时候。因此，每当附加日志 RPC 返回成功时，*就知道跟随者的日志一定是和自己相同的了。

在正常的操作中，*和跟随者的日志保持一致性，所以附加日志 RPC 的一致性检查从来不会失败。然而，*崩溃的情况会使得日志处于不一致的状态（老的*可能还没有完全复制所有的日志条目）。这种不一致问题会在*和跟随者的一系列崩溃下加剧。图3.6展示了跟随者的日志可能和新的*不同的方式。跟随者可能会丢失一些在新的*中有的日志条目，他也可能拥有一些*没有的日志条目，或者两者都发生。丢失或者多出日志条目可能会持续多个任期。

在 Raft 算法中，*处理不一致是通过强制跟随者直接复制自己的日志来解决了。这意味着在跟随者中的冲突的日志条目会被*的日志覆盖。3.6节会阐述如何通过增加一些限制来使得这样的操作是安全的。

要使得跟随者的日志进入和自己一致的状态，*必须找到最后两者达成一致的地方，然后删除从那个点之后的所有日志条目，发送自己的日志给跟随者。所有的这些操作都在进行附加日志 RPCs 的一致性检查时完成。*针对每一个跟随者维护了一个 nextIndex，这表示下一个需要发送给跟随者的日志条目的索引地址。当一个*刚获得权力的时候，他初始化所有的 nextIndex 值为自己的最后一条日志的index加1（图3.6中的 11）。如果一个跟随者的日志和*不一致，那么在下一次的附加日志 RPC 时的一致性检查就会失败。在被跟随者拒绝之后，*就会减小 nextIndex 值并进行重试。最终 nextIndex 会在某个位置使得*和跟随者的日志达成一致。当这种情况发生，附加日志 RPC 就会成功，这时就会把跟随者冲突的日志条目全部删除并且加上*的日志。一旦附加日志 RPC 成功，那么跟随者的日志就会和*保持一致，并且在接下来的任期里一直继续保持。

一旦*发现它和跟随者的日志一样了，*就会发送空条目的AppendEntries以节省带宽。然后一旦matchIndex小于了nextIndex，则*应该发送实际的条目。

如果需要的话，算法可以通过减少被拒绝的附加日志 RPCs 的次数来优化。例如，当附加日志 RPC 的请求被拒绝的时候，跟随者可以包含冲突的条目的任期号和自己存储的那个任期的最早的索引地址。借助这些信息，*可以减小 nextIndex 越过所有那个任期冲突的所有日志条目；这样就变成每个任期需要一次附加条目 RPC 而不是每个条目一次。可供选择的，*可以使用二分查找的方法找到跟随者与自己不同的第一个日志条目，这么做有比较好的最坏情况下的表现。在实践中，我们十分怀疑这种优化是否是必要的，因为失败是很少发生的并且也不大可能会有这么多不一致的日志。

通过这种机制，*在获得权力的时候就不需要任何特殊的操作来恢复一致性。他只需要进行正常的操作，然后日志就能自动的在回复附加日志 RPC 的一致性检查失败的时候自动趋于一致。*(leader)从来不会覆盖或者删除自己的日志（图3.2的*只附加特性）。

这种日志复制机制展现了2.1节所描述的期望的共识特性，Raft能够接受、复制并根据法定集合(majority of the cluster)应用日志条目；正常情况下一个新的条目(entry)能通过一轮RPC发送到法定集合，一个慢的成员并不会影响性能。

由于AppendEntries请求大小是可管理的(leader从来不需要通过传送超过一个entry去赶进度)，日志复制算法也是容易落实实现的。译者注：后文会提到快照(snapshot)机制，不过也提到了通过batch的方式优化此RPC，那就是一次多个entries了，不过前面说的是不需要而不是不会。一些其他的一致性算法的描述中需要通过网络发送整个日志，这对开发者优化此点是一个负担。

3.6 安全性

前面的章节里描述了 Raft 算法是如何选举和复制日志的。然而，到目前为止描述的机制并不能充分的保证每一个状态机会按照相同的顺序执行相同的指令。例如，一个跟随者可能会进入不可用状态同时*已经提交了若干的日志条目，然后这个跟随者可能会被选举为*并且覆盖这些日志条目；因此，不同的状态机可能会执行不同的指令序列。

这一节通过在领导选举的时候增加一些限制来完善 Raft 算法。这一限制保证了任何的*对于给定的任期号，都拥有了之前任期的所有被提交的日志条目（图3.2中的*完整特性）。增加这一选举时的限制，我们对于提交时的规则也更加清晰。最终，我们将展示对于*完整特性的简要证明译者注：此处忽略，本译文不做证明部分的翻译，并且说明*是如何领导复制状态机的做出正确行为的。

3.6.1 选举限制

在任何基于*的一致性算法中，*都必须存储所有已经提交的日志条目。在某些一致性算法中，例如 Viewstamped Replication，某个节点即使是一开始并没有包含所有已经提交的日志条目，它也能被选为领导者。这些算法都包含一些额外的机制来识别丢失的日志条目并把他们传送给新的*，要么是在选举阶段要么在之后很快进行。不幸的是，这种方法会导致相当大的额外的机制和复杂性。Raft 使用了一种更加简单的方法，它可以保证所有之前的任期号中已经提交的日志条目在选举的时候都会出现在新的*中，不需要传送这些日志条目给*。这意味着日志条目的传送是单向的，只从*传给跟随者，并且*从不会覆盖自身本地日志中已经存在的条目。

Raft 使用投票的方式来阻止一个候选人赢得选举除非这个候选人包含了所有已经提交的日志条目。候选人为了赢得选举必须联系集群中的大部分节点，这意味着每一个已经提交的日志条目在这些服务器节点中肯定存在于至少一个节点上。如果候选人的日志至少和大多数的服务器节点一样新（这个新的定义会在下面讨论），那么他一定持有了所有已经提交的日志条目。请求投票 RPC 实现了这样的限制： RPC 中包含了候选人的日志信息，然后投票人会拒绝掉那些日志没有自己新的投票请求。

Raft 通过比较两份日志中最后一条日志条目的索引值和任期号定义谁的日志比较新。如果两份日志最后的条目的任期号不同，那么任期号大的日志更加新。如果两份日志最后的条目任期号相同，那么日志比较长的那个就更加新。

3.6.2 提交之前任期内的日志条目

如同3.5节介绍的那样，*知道一条当前任期内的日志记录是可以被提交的，只要它被存储到了大多数的服务器上。如果一个*在提交日志条目之前崩溃了，未来后续的*会继续尝试复制这条日志记录。然而，一个*不能断定一个之前任期里的日志条目被保存到大多数服务器上的时候就一定已经提交了。图3.7展示了一种情况，一条已经被存储到大多数节点上的老日志条目，也依然有可能会被未来的*覆盖掉。

为了消除图3.7里描述的情况，Raft 永远不会通过计算副本数目的方式去提交一个之前任期内的日志条目。只有*当前任期里的日志条目通过计算副本数目可以被提交；一旦当前任期的日志条目以这种方式被提交，那么由于日志匹配特性，之前的日志条目也都会被间接的提交。在某些情况下，*可以安全的知道一个老的日志条目是否已经被提交（例如，该条目是否存储到所有服务器上），但是 Raft 为了简化问题使用一种更加保守的方法。

当*复制之前任期里的日志时，Raft 会为所有日志保留原始的任期号, 这在提交规则上产生了额外的复杂性。在其他的一致性算法中，如果一个新的*要重新复制之前的任期里的日志时，它必须使用当前新的任期号。Raft 使用的方法更加容易辨别出日志，因为它可以随着时间和日志的变化对日志维护着同一个任期编号。另外，和其他的算法相比，Raft 中的新*只需要发送更少日志条目（其他算法中必须在他们被提交之前发送更多的冗余日志条目来为他们重新编号）。

3.6.3 安全性论证

证明过程参考小论文翻译，这里就不写出来了。

通过*完全特性，我们就能证明图3.2中的状态机安全特性，即如果已经服务器已经在某个给定的索引值应用了日志条目到自己的状态机里，那么其他的服务器不会应用一个不一样的日志到同一个索引值上。在一个服务器应用一条日志条目到他自己的状态机中时，他的日志必须和*的日志，在该条目和之前的条目上相同，并且已经被提交。现在我们来考虑在任何一个服务器应用一个指定索引位置的日志的最小任期；日志完全特性保证拥有更高任期号的*会存储相同的日志条目，所以之后的任期里应用某个索引位置的日志条目也会是相同的值。因此，状态机安全特性是成立的。

最后，Raft 要求服务器按照日志中索引位置顺序应用日志条目。和状态机安全特性结合起来看，这就意味着所有的服务器会应用相同的日志序列集到自己的状态机中，并且是按照相同的顺序。

3.7 跟随者和候选人崩溃

到目前为止，我们都只关注了*崩溃的情况。跟随者和候选人崩溃后的处理方式比*要简单的多，并且他们的处理方式是相同的。如果跟随者或者候选人崩溃了，那么后续发送给他们的 RPCs 都会失败。Raft 中处理这种失败就是简单的通过无限的重试；如果崩溃的机器重启了，那么这些 RPC 就会完整的成功。如果一个服务器在完成了一个 RPC，但是还没有响应的时候崩溃了，那么在他重新启动之后就会再次收到同样的请求。Raft 的 RPCs 都是幂等的，所以这样重试不会造成任何问题。例如一个跟随者如果收到附加日志请求但是他已经包含了这一日志，那么他就会直接忽略这个新的请求

3.8 持久化状态和服务重启

Raft服务(server)必须持久化足够的信息保证服务安全的重启。特别地，每一个服务需要持久化当前的任期(term)和投票(vote)，这是必要的，以防止服务器在相同的期限内投票两次，或者将来自新领导者的日志条目替换为来自已废弃领导者的日志条目。每一个服务也要在统计日志提交状态之前持久化该日志，这会防止已提交的日志丢失或者当服务重启的时候实际情况变成了未提交了。

其他状态变量在重启之后丢失是安全的，因为他们都可以被重建。比如说commit index，可以在重启后被安全的初始化为0。即使每一个服务同时重启了，commit index也只会暂时的落后于真正的值。一旦leader被选出来它就会提交新的entry 译者注：比如no-op entry，它的commit index就会向前，并且立刻就会把commit index传播给跟随者(followers)。

状态机持不持久化都可以。一个易变的(volatile)状态机可以在重启之后通过重放日志来恢复(在应用了最后的快照之后，参见第5章内容)。一个持久化的状态机重启之后就已经应用的大多数的entries，可以避免重放这一部分，它的last applied index也需要被持久化。

如果一个服务丢失了某些持久化的状态，它就不能以之前的标识安全的重新加入集群了。这样的服务通常是通过调用集群成员关系改变(membership change，参见第4章)以新的标识加回集群的。如果集群的法定集合都丢失了它们持久化的信息，日志信息就无效了，通过membership change处理是不可能的。这就需要系统管理员介入了，不得不面对可能的数据丢失。

3.9 时间和可用性

Raft 的要求之一就是安全性不能依赖时间：整个系统不能因为某些事件运行的比预期快一点或者慢一点就产生了错误的结果。但是，可用性（系统可以及时的响应客户端）不可避免的要依赖于时间。例如，如果消息交换在服务器崩溃时花费更多的时间，候选人将不会等待太长的时间来赢得选举；没有一个稳定的*，Raft 将无法工作。

*选举是 Raft 中对时间要求最为关键的方面。Raft 可以选举并维持一个稳定的*,只要系统满足下面的时间要求：

广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）

在这个不等式中，广播时间指的是从一个服务器并行的发送 RPCs 给集群中的其他服务器并接收响应的平均时间；选举超时时间就是在3.4节中介绍的选举的超时时间限制；然后平均故障间隔时间就是对于一台服务器而言，两次故障之间的平均时间。广播时间必须比选举超时时间小一个量级，这样*才能够发送稳定的心跳消息来阻止跟随者开始进入选举状态；通过随机化选举超时时间的方法，这个不等式也使得选票瓜分的情况变得不可能。选举超时时间应该要比平均故障间隔时间小上几个数量级，这样整个系统才能稳定的运行。当*崩溃后，整个系统会大约相当于选举超时的时间里不可用；我们希望这种情况在整个系统的运行中很少出现。

广播时间和平均故障间隔时间是由系统决定的，但是选举超时时间是我们自己选择的。Raft 的 RPCs 需要接收方将信息持久化的保存到稳定存储中去，所以广播时间大约是 0.5 毫秒到 20 毫秒，取决于存储的技术。因此，选举超时时间可能需要在 10 毫秒到 500 毫秒之间。大多数的服务器的平均故障间隔时间都在几个月甚至更长，很容易满足时间的需求。

3.10 领导力转让(Leadership transfer)

这一章描述了Raft可选的Leader转换领导关系到另一个server的扩展。Leadership transfer可能在下面这两种场景下很有用：

1. 有的时候leader必须*。例如为了维护需要重启，或者server需要从集群中移除(见第四章)。当它*之后，集群会处于限制状态直到其他server达到选举超时触发选主并且成功选出主了。这个短暂的不可用是可以通过在leader*之前转换领导关系来避免的。
2. 在某些情况下，一个或者其他server可能更适合做*。例如，某个服务可能处于高负载之下，它并不适合做一个好的leader，或者在广域网下，在主数据中心的server可能更适合作为leader以减小和client之间的latency。其他一致性算法可能能够在领导者选举期间处理适应偏好，但Raft需要的是一个具有up-to-date日志的服务器成为领导者，这可能不是最优选的。相反，Raft leader可以周期的检查最优选择，并把领导能力转换给它(要是像人类的*如此优雅多好啊)。

想要在Raft中转换领导关系，当前的leader先把它的log发送给目标server，然后目标server不等待选举超时就直接触发选举。当前的领导者因此确保了目标server在其任期开始时具有所有已提交的条目，并且如同正常选举一样，多数投票的特性维护了安全性(例如*完全特性)。下面的步骤对这个过程做了一个更详细的描述：

1. 当前*停止接收客户端请求
2. 当前*完整的更新目标server的日志以使得其匹配自己的日志，使用3.5节中描述的常规的日志复制机制

3. 当前*发送一个 TimeoutNow 请求到目标server。这个请求对于目标server来说和它触发了选举超时定时器是等效的：目标server开始新一轮选举(增加其term然后成为候选人(candidate))

   一旦目标server收到了TimeoutNow请求，它有极大的可能性先于其他server超时前发起选举并在下一个term成为leader。它会发送给之前leader带着新term信息的心跳，这样会触发之前的leader*。到此，领导力转换完成。

目标server也有可能失败了，这种情况下集群必须恢复客户端操作。如果领导力转换在一个选举超时周期内没有完成，当前的leader需要终止转换并恢复接收客户端请求。如果当前leader出错了并且目标server实际上是可用的，那么最差的情况是会导致一次额外的选举，之后客户端操作就会恢复。

这种方法通过正常的操作保证了Raft集群的安全性。例如Raft已经保证了时钟不通步情况下的安全性(term才是真正的raft逻辑时钟)，当目标server收到了TimeoutNow请求的时候，相当于server的时钟跳跃了，这是安全的。然而，我们目前(LogCabin中)并没有实现和评估这种leadership transfer方法。

3.11 讨论

这一章讲述了一致性基础系统的所有核心问题。Raft没有通过像在Paxos中single-degree那样在一个值上达成一致，而是通过增长的操作日志来实现一致性，这需要建立一个复制状态机。一旦达成一致就会传播这个信息，这样其他servers就会直到log条目已经提交了。Raft通过实用有效的方法实现了一致性：选举一个独自做决定的leader并且通过leader传送必要的日志信息。我们已经在LogCabin中实现了Raft和一个复制状态机(第10章中有描述)。

Raft使用少量的机制来解决完全一致问题。例如Raft近视用两个RPCs(RequestVote和AppendEntries)。也许令人惊讶的是，创建一个紧凑的算法/实现那并不是Raft的明确目标。相反，这是我们为了可理解性而设计的结果，每一个机制必须充分激发积极性和具有可理解性。我们发现冗余曲折的机制很难激发积极性，所以在设计中自然的会被清除。

除非我们明确感到某个特定的问题会对Raft开发造成较大影响，否则我们不会在Raft中提及。结果就是Raft有的部分看起来很天真。例如server通过等待选举超时的机制来检测选票是否被瓜分，原则上通常可以通过统计投票情况来更早的检测到。我们选择不在Raft中对此做优化，因为这会引入复杂而且可能对实践来说没有任何好处：配置合理的情况下选票瓜分是非常罕见的。Raft的其他某部分实现看起来是保守的。比如leader只能提交当前任期的条目，即使在某些场景下提交之前任期内的条目也是安全的。采用一个更复杂的提交规则会有损易理解性并且可能没有显著的性能优化。只有当前规则下(leader没有当前term内的日志但是有之前term的日志时采用的上述规则)才会出现提交被短暂的延迟。当同其他人讨论raft时，我们发先许多人不禁想到类似这样的优化并提出来，但是当目标是易理解性的时候，应该排除掉过早的优化。

不可避免地，这章可能剩下了一些特性或者优化，这些可能在实践中是非常有意义的。随着实施者获得更多的Raft经验，他们将了解何时以及为什么某些附加功能可能会有用，并且他们可能需要为某些实际部署而实现这些功能。通篇来说，我们描述了一些可选的扩展，我们当前觉得没必要，但是可能在需要的时候帮助实现着。由于关注于易理解性，我们希望提供可靠的基础以便实现者根据经验调整Raft。由于Raft在我们的测试环境运行着，我们期望这些是直截了当的扩展而非基础的改变。