《云计算技术系列丛书 云原生分布式存储基石： etcd深入解析》—1.4Raft协议：为可理解性而生

1.4　Raft协议：为可理解性而生

       上文中提到过，Raft算法的提出是为了改变Paxos算法垄断分布式一致性协议的局面。可以说，可理解性是系统工程师从Paxos算法切换到Raft算法的主要原因。Raft的作者在他的论文中也特别提到Raft算法在教学方面比Paxos算法的效果更好。

       为了比较Paxos和Raft算法的可理解性能，Raft算法的作者特地在斯坦福大学和加州大学伯克利分校的课堂上，对总共43名学生进行了一次教学实验。他们分别为每个学生讲授Raft和Paxos算法，并针对每个算法准备了相应的随堂测验，通过计算每个学生的测验得分来衡量学生对哪种算法理解得更好。

       测验总分为60，Raft算法测验的平均得分是25.7，Paxos算法的平均得分是20.8，Raft比Paxos平均高出4.9分。图1-6展示了43个学生在Paxos和Raft测验中的成绩，对角线之上的点表示在Raft算法测验中获得更高分数的学生。

图1-6　Paxos与Raft测验对比

       同时在测验之后采访参与学生，询问他们认为哪个算法更容易解释和实现。压倒性的结果表明Raft算法更加容易解释和实现。图1-7展示了这个采访结果。

图1-7　Paxos与Raft算法实现难易程度调查

        在图1-7中，左侧柱形图表示的是哪个算法在工程上更容易实现的统计结果，右边表示的是哪个算法更容易解释的统计结果。

        Raft算法主要使用两种方法来提高可理解性。

      （1）问题分解

        尽可能地将问题分解成为若干个可解决的、更容易理解的小问题—这是众所周知的简化问题的方法论。例如，Raft算法把问题分解成了领袖选举（leader election）、日志复制（log replication）、安全性（safety）和成员关系变化（membership changes）这几个子问题。

        领袖选举：在一个领袖节点发生故障之后必须重新给出一个新的领袖节点。

        日志复制：领袖节点从客户端接收操作请求，然后将操作日志复制到集群中的其他服务器上，并且强制要求其他服务器的日志必须和自己的保持一致。

        安全性：Raft关键的安全特性是下文提到的状态机安全原则（State Machine Safety）—如果一个服务器已经将给定索引位置的日志条目应用到状态机中，则所有其他服务器不会在该索引位置应用不同的条目。下文将会证明Raft是如何保证这条原则的。

成员关系变化：配置发生变化的时候，集群能够继续工作。

     （2）减少状态空间

       Raft算法通过减少需要考虑的状态数量来简化状态空间。这将使得整个系统更加一致并且能够尽可能地消除不确定性。需要特别说明的是，日志条目之间不允许出现空洞，并且还要限制日志出现不一致的可能性。尽管在大多数情况下，Raft都在试图消除不确定性以减少状态空间。但在一种场景下（选举），Raft会用随机方法来简化选举过程中的状态空间。

       Raft算法与现有的一些Paxos协议的变种（主要是Oki和Liskov的Viewsta-mped Replication[6]）存在一些相似的地方，但是Raft还有几点重要的创新。

       强领导人。Raft使用一种比其他算法更强的领导形式。例如，日志条目只从领导人发向其他服务器。这样就简化了对日志复制的管理，提高了Raft的可理解性。

       领袖选举。Raft使用随机定时器来选举领导者。这种方式仅仅是在所有算法都需要实现的心跳机制上增加了一点变化，就使得冲突解决更加简单和快速。

成员变化。Raft在调整集群成员关系时使用了新的一致性（joint consensus，联合一致性）方法。使用这种方法，使得集群配置在发生改变时，集群依旧能够正常工作。

       下文将对Raft算法展开详细的讨论。

       1.4.1　Raft一致性算法

       Raft算法是基于复制状态机模型推导的，所以在开始Raft算法的探秘之前，建议大家回顾一下1.2.3节有关复制状态机的内容。下文将从Raft算法的4个子问题：领袖选举、日志复制、安全性和成员关系变化出发，采取各个击破的策略，直击Raft算法的本质。不过，在此之前，先让我们简单了解下Raft算法的几个基本概念。

       当Paxos协议的读者还在抱怨Lamport没有给出一个形式化的、可实现的工程方法时，Diego在论文中就已经明确告诉他的读者只要实现2个远端过程调用，就能构建一个基于Raft协议的分布式系统。

       Raft集群中的节点通过远端过程调用（RPC）来进行通信，Raft算法的基本操作只需2种RPC即可完成。RequestVote RPC是在选举过程中通过旧的Leader触发的，AppendEntries RPC是领导人触发的，目的是向其他节点复制日志条目和发送心跳（heartbeat）。下文还会介绍Raft算法的第3种RPC，用于领导人向其他节点传输快照（snapshot）。如果节点没有及时收到RPC的响应，就会重试。而且，RPC可以并行地发出，以获得最好的性能。

       1. Raft算法的基本概念

       一般情况下，分布式系统中存在如下两种节点关系模型。

       对称。所有节点都是平等的，不存在主节点。客户端可以与任意节点进行交互。

非对称。基于选主模型，只有主节点拥有决策权。任意时刻有且仅有一个主节点，客户端只与主节点进行交互。

       基于简化操作和效率等因素考虑，Raft算法采用的是非对称节点关系模型。

       在一个由Raft协议组织的集群中，一共包含如下3类角色。

Leader（领袖）

Candidate（候选人）

Follower（群众）

       联系实际的民主社会，领袖由群众投票选举得出。刚开始时没有领袖，民主社会的所有参与者都是群众。首先开启一轮大选，大选期间所有的群众都能参与竞选，即所有群众都可以成为候选人。一旦某位候选人得到了半数以上群众的选票，就出任那一届的领袖，开始一个新的任期。领袖产生后，将由领袖昭告天下，结束选举。于是，除领袖之外的所有候选人又都回到了群众的身份并接受领袖的领导。

       上文提到一个概念—“任期”，其在Raft算法中对应一个专门的术语—“Term”。

       如图1-8所示，Raft算法将时间划分成为任意个不同长度的任期，任期是单调递增的，用连续的数字（1，2，3……）表示。在Raft的世界里，每一个任期的开始都是一次领导人的选举。正如上文所描述的那样，一个或多个候选人会试图成为领导人。如果一个候选人赢得了选举，那么它就会在该任期的剩余时间内担任领导人。在某些情况下，选票会被瓜分，导致没有哪位候选人能够得到超过半数的选票，这样本次任期将以没有选出领导人而结束。那么，系统就会自动进入下一个任期，开始一次新的选举。Raft算法保证在给定的一个任期内最多只有一个领导人。某些Term会由于选举失败，存在没有领导人的情况。

图1-8　Raft算法任期示意图

       众所周知，分布式环境下的“时间同步”是一个大难题，但是有时为了识别“过期信息”，时间信息又是必不可少的。于是，任期在Raft中起着逻辑时钟的作用，同时也可用于在Raft节点中检测过期信息—比如过期的领导人。每个Raft节点各自都在本地维护一个当前任期值，触发这个数字变化（增加）主要有两个场景：开始选举和与其他节点交换信息。当节点之间进行通信时，会相互交换当前的任期号。如果一个节点（包括领导人）的当前任期号比其他节点的任期号小，则将自己本地的任期号自觉地更新为较大的任期号。如果一个候选人或者领导人意识到它的任期号过时了（比别人的小），那么它会立刻切换回群众状态；如果一个节点收到的请求所携带的任期号是过时的，那么该节点就会拒绝响应本次请求。

       需要注意的是，由于分布式系统中节点之间无法做到在任意时刻完全同步，因此不同的Raft节点可能会在不同的时刻感知到任期的切换。甚至在出现网络分区或节点异常的情况下，某个节点可能会感知不到一次选举或者一个完整的任期。这也是Raft强制使用较新的Term更新旧的Term的原因。

       好了，Raft协议的核心概念和术语就这么多—领袖、候选人、群众和任期，而且这些术语与现实民主制度也非常匹配，因此也很好理解。下面就开始讨论Raft算法的领导人选举流程。

       2.领导人选举

       Raft通过选举一个权力至高无上的领导人，并采取赋予他管理复制日志重任的方式来维护节点间复制日志的一致性。领导人从客户端接收日志条目，再把日志条目复制到其他服务器上，并且在保证安全性的前提下，告诉其他服务器将日志条目应用到它们的状态机中。强领导人的存在大大简化了复制日志的管理。例如，领导人可以决定新的日志条目需要放在日志文件的什么位置，而不需要和其他服务器商议，并且数据都是单向地从领导人流向其他服务器。当然，在这种方式下，领导人自身的日志正确性显得尤为重要，下文的“4.安全性Q & A”一节会着重说明Raft使用怎样的策略来保证日志的正确性。

       Raft集群三类角色的有限状态机图如图1-9所示，后面的具体选举过程可以结合图1-9来进行理解。

图1-9　Raft集群三类角色切换示意图

       观察图1-9可以很容易地看出，有一个“times out”（超时）条件，这是触发图1-9有限状态自动机发生状态迁移的一个重要条件。在Raft的选举中，有两个概念非常重要：心跳和选举定时器。每个Raft节点都有一个选举定时器，所有的Raft节点最开始以Follower角色运行时，都会启动这个选举定时器。不过，每个节点的选举定时器时长均不相等。

       Leader在任期内必须定期向集群内的其他节点广播心跳包，昭告自己的存在。Follower每次收到心跳包后就会主动将自己的选举定时器清零重置（reset）。因此如果Follower选举定时器超时，则意味着在Raft规定的一个选举超时时间周期内，Leader的心跳包并没有发给Follower（或者已经发送了但在网络传输过程中发生了延迟或被丢弃了），于是Follower就假定Leader已经不存在或者发生了故障，于是会发起一次新的选举。

       对此，我们可以很形象地理解为每个Raft的Follower都有一颗不安分的“野心”，只是碍于Leader的心跳广播不敢“造反”。而Follower从最后一次接收到Leader的心跳包算起，最长的“蛰伏”时间就是Raft协议为每个节点规定的选举超时时间，超过这个时间，大家就都“蠢蠢欲动”了。

       因此，要求Leader广播心跳的周期必须要短于选举定时器的超时时间，否则会频繁地发生选举，切换Leader。

       如果一个Follower决定开始参加选举，那么它会执行如下步骤。

       1）将自己本地维护的当前任期号（current_term_id）加1。

       2）将自己的状态切换到候选人（Candidate），并为自己投票。也就是说每个候选人的第一张选票来自于他自己。

       3）向其所在集群中的其他节点发送RequestVote RPC（RPC消息会携带“current_term_id”值），要求它们投票给自己。

       从图1-9也可以看出，一个候选人有三种状态迁移的可能性。

       1）得到大多数节点的选票（包括自己），成为Leader。

       2）发现其他节点赢得了选举，主动切换回Follower。

       3）过了一段时间后，发现没有人赢得选举，重新发起一次选举。

       下文将逐一分析这些情形。

       第一种场景：一个候选人如果在一个任期内收到了集群中大多数Follower的投票，就算赢得了选举。在一个任期内，一个Raft节点最多只能为一个候选人投票，按照先到先得的原则，投给最早来拉选票的候选人（注意：下文的“安全性”针对投票添加了一个额外的限制）。“选举安全性原则”使得在一个任期内最多有一个候选人能够赢得选举。一旦某个候选人赢得了选举，它就会向其他节点发送心跳信息来建立自己的领导地位。

       第二种场景：当一个候选人在等待其他人的选票时，它有可能会收到来自其他节点的，声称自己是领导人的心跳包（其实就是一个空内容的AppendEntries RPC）或AppendEntries RPC（下文会详细说明）。此时，这个候选人会将信将疑地检查包含在这位“领导人”RPC中的任期号：如果比自己本地维护的当前任期要大，则承认该领导人合法，并且主动将自己的状态切换回Follower；反之，候选人则认为该“领导人”不合法，拒绝此次RPC，并且返回当前较新的那个任期号，以便让“领导人”意识到自己的任期号已经过时了，该节点将继续保持候选人状态不变。

       第三种场景：一个候选人既没有赢得选举也没有输掉选举。如果多个Follower在同一时刻都成了候选人，那么选票可能会被多个候选人平分，这就使得没有哪个候选人能够获得超过半数的选票。当这种情形发生时，显然不能一直这样“僵持下去”，于是Raft的每一个候选人又都设置了超时时间（类似于选举超时时间，区别是选举超时时间是针对Follower的），发生超时后，每个候选人自增任期号（Term++）并且发起新一轮的拉选票活动。然而，如果没有其他手段来分配选票的话，选票均分的情况可能会无限循环下去（理论上存在这种可能性，还记得FLP不可能性定理吗）。为了避免发生这种问题，Raft采用了一种非常简单的方法—随机重试。例如，设置一个区间（150～300ms），超时时间将从这个区间内随机选择。错开发起竞选的时间窗口，可以使得在大多数情况下只有一个节点会率先超时，该节点会在其他节点超时之前赢得选举，并且向其他节点发送心跳信息。要知道，在每次选票打平时都会采用这种随机的方式，因此连续发生选票被均分的概率非常小。1.4.5节将展示通过这种方法如何才能够快速、有效地选出一个领导人。

      “随机重试”就是“可理解性”在Raft算法设计过程中起决定性作用的一个非常生动的例子。据Raft算法的作者回忆，最开始时他们计划使用一种排名系统：为每一个候选人分配一个独一无二的排名，用于在候选人竞争时根据排名的高低选择领导人。如果发现一个候选人的排名比另一个候选人的排名高，排名较低的就会切换回Follower的状态，这样排名高的候选人就会轻而易举地赢得选举。但是他们马上就发现这种方法在可用性方面存在一些问题—低排名的节点在高排名的节点发生故障后，需要等待超时才能再次成为候选人，但是如果进行得太快，就有可能会中断领导人选举的过程。在对算法进行了多次调整之后，最终他们认为随机重试的方法是更明确并且更易于理解的。

       以上“拉票”过程使用Raft算法预定义的RPC—RequestVote RPC就能描述。RequestVote RPC的发起/调用方是候选人，接收方是集群内所有的其他节点（包括Leader、Follower和Candidate）。RequestVote RPC有4个参数，2个返回值，具体如表1-1和表1-2所示。

       RPC接收方需要实现的逻辑具体如下。

       1）如果term < currentTerm，即RPC的第一个参数term的值小于接收方本地维护的term（currentTerm）值，则返回（currentTerm, false），以提醒调用方其term过时了，并且明确地告诉这位候选人这张选票不会投给他；否则执行步骤2。

       2）如果之前没把选票投给任何人（包括自己）或者已经把选票投给当前候选人了，并且候选人的日志和自己的日志一样新，则返回（term, true），表示在这个任期，选票都投给这位候选人。如果之前已经把选票投给其他人了，那么很遗憾，这张选票还是不能投给他，这时就会返回（term, false）。

       3.日志复制

       一旦某个领导人赢得了选举，那么它就会开始接收客户端的请求。每一个客户端请求都将被解析成一条需要复制状态机执行的指令。领导人将把这条指令作为一条新的日志条目加入它的日志文件中，然后并行地向其他Raft节点发起AppendEntries RPC，要求其他节点复制这个日志条目。当这个日志条目被“安全”地复制之后（下文会详细论述符合什么样的条件才算安全），Leader会将这条日志应用（apply，即执行该指令）到它的状态机中，并且向客户端返回执行结果。如果Follower发生错误，运行缓慢没有及时响应AppendEntries RPC，或者发生了网络丢包的问题，那么领导人会无限地重试AppendEntries RPC（甚至在它响应了客户端之后），直到所有的追随者最终存储了和Leader一样的日志条目。

       在图1-10中，日志由有序编号的日志条目组成。每一个日志条目一般均包含三个属性：整数索引（log index）、任期号（term）和指令（command）。每个条目所包含的整数索引即该条目在日志文件中的槽位。term是指其被领导人创建时所在的任期号，对应到图1-10中就是每个方块中的数字，用于检测在不同的服务器上日志的不一致性问题。指令即用于被状态机执行的外部命令（对应到图1-10中就是x←3，y←1等）。如果某个日志条目能够被状态机安全执行，就认为是可以被提交（committed）了。

图1-10　Raft协议追加日志示意图

       领导人决定什么时候将日志条目应用到状态机是安全的，即可被提交的。Raft算法保证可被提交的日志条目是持久化的，并且最终是会被所有状态机执行的。一旦领导人创建的条目已经被复制到半数以上的节点上了，那么这个条目就称为可被提交的。例如，图1-10中的7号条目在其中3个节点（一共是5个节点）上均有复制，所以7号条目是可被提交的；但条目8只在其中2个节点上有复制，因此8号条目不是可被提交的。

       领导人日志中的所有条目都是可被提交的，包括之前的领导人创建的日志条目。这种提交方式是安全的—我们将会在下文详细讨论领导人更替之后这条规则应用的细节。领导人跟踪记录他所知道的被提交日志条目的最大索引值，并且这个索引值会包含在他向其他节点发送的AppendEntries RPC中，目的就是让其他节点知道该索引值对应的日志条目已经被提交。由于领导人广播的心跳包就是一个内容为空的AppendEntries RPC，因此其他节点也能通过领导人的心跳包获悉某个日志条目的提交情况。一旦Follower得知某个日志条目已经被提交，那么它会将该条日志应用至本地的状态机（按照日志顺序）。

       Raft算法设计了以下日志机制来保证不同节点上日志的一致性。

       1）如果在不同的日志中两个条目有着相同的索引和任期号，则它们所存储的命令是相同的。

       2）如果在不同的日志中两个条目有着相同的索引和任期号，则它们之前的所有条目都是完全一样的。

       第一条特性的满足条件在于，领导人在一个任期里在给定的一个日志索引位置上最多创建一条日志条目，同时该条目在日志文件中的槽位永远也不会改变。

       第二条特性的满足条件在于，AppendEntries RPC有一个简单的一致性检查。领导人在发送一个AppendEntries RPC消息试图向其他节点追加新的日志条目时，会把这些新日志条目之前一个槽位的日志条目的任期号和索引位置包含在消息体中。如果Follower在它的日志文件中没有找到相同的任期号和索引的日志，它就会拒绝该AppendEntries RPC，即拒绝在自己的状态机中追加新日志条目。

       用归纳法证明：初始化时空日志文件一定是满足日志匹配原则的，一致性检查保证了向日志文件追加新日志条目时的日志匹配原则。因此，只要某个Follower成功返回AppendEntries RPC，那么领导人就能放心地认为他的日志与该Follower的已经保持一致了。

       当一个新的Leader被选举出来时，它的日志与其他的Follower的日志可能是不一样的。这时就需要一个机制来保证日志是一致的。产生一个新Leader时，集群状态可能如图1-11所示。

图1-11　新Leader产生时集群可能的一个状态图

       在图1-11所示的例子中，一个格子代表一个日志条目，格子中的数字是它对应的任期号。假设最上面的那个是领导人，a～f是可能出现的Follower的日志，那么a～f 所代表的场景分别如下。

       a和b表示Follower丢失一些日志条目的场景。

       c和d表示Follower可能多出来一些未提交的条目的场景。

       e和f表示上述两种情况都有的场景。

       丢失的或者多出来的条目可能会持续多个任期。举个例子，场景f会在如下情况下发生：如果一台服务器在任期2时是领导人，并且其向他自己的日志文件中追加了一些日志条目，然而在将这些日志条目提交之前系统出现了故障。但是他很快又重启了，选举成功继续成为任期3的领导人，而且又向他自己的日志文件中追加了一些日志条目。但是很不幸的是，在任期2和任期3中创建的日志条目在被提交之前又出现了故障，并且在后面几个任期内也一直处于故障状态。

       一般情况下，Leader和Follower的日志都是保持一致的，因此Append-Entries RPC的一致性检查通常不会失败。然而，如果领袖节点在故障之前没有向其他节点完全复制日志文件中的所有条目，则会导致日志不一致的问题。在Raft算法中，Leader通过强制Follower复制它的日志来处理日志不一致的问题。这就意味着，Follower上与Leader的冲突日志会被领导者的日志强制覆写。这在添加了一个额外的限制之后其实是安全的，下文会详细说明其中的原因。

       为了让Follower的日志同自己的保持一致，Leader需要找到第一个Follower与它的日志条目不一致的位置，然后让Follower连续删除该位置之后（包括该位置）所有的日志条目，并且将自己在该位置（包括该位置）之后的日志条目发送给Follower。

       那么，Leader是如何精准地找到每个Follower与其日志条目不一致的那个槽位的呢？这些操作都会在AppendEntries RPC进行一致性检查时完成。Leader为每一个Follower维护了一个nextIndex，它表示领导人将要发送给该追随者的下一条日志条目的索引。当一个Leader赢得选举时，它会假设每个Follower上的日志都与自己的保持一致，于是先将nextIndex初始化为它最新的日志条目索引数+1。在图1-11所示的例子中，由于Leader最新的日志条目index为10，所以nextIndex的初始值是11。

       当Leader向Follower发送AppendEntries RPC时，它携带了（term_id, next-Index-1）二元组信息，term_id即nextIndex-1这个槽位的日志条目的term。Follower接收到AppendEntries RPC消息后，会进行一致性检查，即搜索自己的日志文件中是否存在这样的日志条目，如果不存在，就向Leader返回AppendEntries RPC失败。如果返回失败信息，就意味着Follower发现自己的日志与领导人的不一致。在失败之后，领导人会将nextIndex递减（nextIndex--），然后重试AppendEntries RPC，直到AppendEntries RPC返回成功为止。这才表明在nextIndex位置的日志条目中领导人与追随者的保持一致。这时，Follower上nextIndex位置之前的日志条目将全部保留，在此之后（与Leader有冲突）的日志条目将被Follower全部删除，并且从该位置起追加Leader上在nextIndex位置之后的所有日志条目。因此，一旦AppendEntries RPC返回成功，Leader和Follower的日志就可以保持一致了。

       以上即Raft日志的一致性检查的全过程，下面将以图1-11中的Leader和b节点为例，举例说明日志一致性检查Leader和Follower之间的交互过程。

       首先，Leader的nextIndex的初始值为11，Leader向b发送AppendEntries RPC(6,10)。然而，b在自己日志文件的10号位置没有找到term为6的日志记录（因为b根本就没有10号日志项），于是b向Leader返回了一个拒绝消息。接着，Leader将nextIndex减1，变成10，然后继续向b发送AppendEntries RPC(6,9)，b在自己日志文件的9号位置同样没有找到term为6的日志记录。(6,8)，(5,7)，(5,6)，(4,5)这样依次循环下去都没有找到相应的日志记录，直到发送了(4,4)，b才在自己日志文件的第4号位置找到了term为4的日志记录，于是接受了Leader的AppendEntries RPC请求，并将自己的日志文件中从5号位置开始的日志记录全部删除。随后，Leader就从5号位置开始把余下的所有日志条目一次性推送给b（5~10）。

       如果需要的话，在Raft算法的实现上还可以优化AppendEntries RPC失败的次数。例如，当Follower拒绝了一个AppendEntries RPC时，Follower可以在自己本地的日志文件中找到该任期号内所有日志条目索引（index）值最小的那个，然后反馈给Leader。于是，领导人就可以跳跃式递减nextIndex，跨过那个任期内所有的冲突条目。通过这种方式，一个冲突的任期只需要一次Append-Entries RPC检查，而无须为每个冲突条目都做一次AppendEntries RPC检查。

       Raft算法的日志复制机制，使得Leader和Follower只需要调用和响应AppendEntries RPC即可让集群内节点的各复制状态机的日志逐渐地趋于一致，而无须再采取额外的措施。一个领导人从来不会删除自己的日志（包括前任领导人创建的日志），也不会被别人覆盖日志。

       Raft算法的日志复制机制表明：只要集群中的大部分节点是正常的，那么Raft算法就能接受客户端复制日志的请求，并将其复制到各节点上且应用（Apply）到各节点的复制状态机上。通常情况下，一次AppendEntries RPC就能完成一条新的日志条目在集群内的大多数节点上的复制。而且Raft只要求日志条目在大多数节点上完成复制就算提交成功，因此速度较慢的Follower并不会影响整体的日志复制性能。

       以下步骤总结了一次正常的Raft日志的复制流程。

       1）客户端向Leader发送写请求。

       2）Leader将写请求解析成操作指令追加到本地日志文件中。

       3）Leader为每个Follower广播AppendEntries RPC。

       4）Follower通过一致性检查，选择从哪个位置开始追加Leader的日志条目。

       5）一旦日志项提交成功，Leader就将该日志条目对应的指令应用（apply）到本地状态机，并向客户端返回操作结果。

       6）Leader后续通过AppendEntries RPC将已经成功（在大多数节点上）提交的日志项告知Follower。

       7）Follower收到提交的日志项之后，将其应用至本地状态机。

       从上面的步骤可以看出，针对Raft日志条目有两个操作，提交（commit）和应用（apply），应用必须发生在提交之后，即某个日志条目只有被提交之后才能被应用到本地状态机上。

       Raft算法的作者在论文中就已经描述了AppendEntries RPC的实现细节。AppendEntries RPC的调用方是Leader，接收方是Follower。AppendEntries RPC有6个参数，2个返回值，分别如表1-3和表1-4所示。AppendEntries RPC除了用于复制日志之外，还可以用于广播Leader的心跳包。

       RPC接收者需要实现如下操作步骤。

       1）如果term < currentTerm，即领导人的任期号小于Follower本地维护的当前任期号，则返回(currentTerm, false)；否则继续步骤2）。

       2）如果Follower在prevLogIndex位置的日志的任期号与prevLogTerm不匹配，则返回(term, false)；否则继续步骤3）。

       3）Follower进行日志一致性检查。

       4）添加任何在已有的日志中不存在的条目，删除多余的条目。

       5）如果leaderCommit > commitIndex，则将commitIndex（Follower自己维护的本地已提交的日志条目索引值）更新为min{leaderCommit, Follower本地最新日志条目索引}。即信任Leader的数据，乐观地将本地已提交日志的索引值“跃进”到领导人为该Follower跟踪记录的那个值（除非leaderCommit比本地最新的日志条目索引值还要大）。这种场景通常发生在Follower刚从故障中恢复过来的场景。

       4.安全性Q&A

       Raft算法是强领导人模型，一旦Follower与Leader发生了冲突，就将无条件服从Leader。因此，Leader选举是Raft算法中非常重要的一环，如果选举出来的Leader其自身的日志就是不正确的，那么将会直接影响到Raft算法正确稳定的运行。

       之前的章节讨论了Raft算法是如何进行领导选举和日志复制的。然而，到目前为止这个机制还不能保证每一个状态机都能够按照相同的顺序执行同样的指令。例如，当领导人正在复制日志条目时一个Follower发生了故障，且故障发生之前没有复制领导人的日志，之后该Follower重启并且当选为领导人，那么它在产生了一些新的日志条目后，会用自己的日志覆盖掉其他节点的日志。这就会导致不同的状态机可能执行不同的指令序列。

      下文将介绍如何在领导人选举部分加入一个限制规则来保证—任何的领导人都拥有之前任期提交的全部日志条目。有了这一限制，就不会发生上面例子所描述的情形了。

Q：怎样才能具有成为领导人的资格？

A：在所有以领导人选举为基础的一致性算法中，领导人最终必须要存储全部已经提交的日志条目。在一些一致性算法中，例如，Viewstamped Replication中，即使一开始没有包含全部已提交的条目也可以当选为领导人。这些算法都包含一些另外的机制来保证找到丢失的条目并将它们传输给新的领导人，这个过程要么在选举过程中完成，要么在选举之后立即开始。毫无疑问的是，这种方式显著增加了算法的复杂性。

       Raft算法使用的是一种更简单的方式来保证新当选的领导人，之前任期已提交的所有日志条目都已经出现在了上面，而不需要将这些条目传送给***人。这种方式隐含了以下两点内容。

       没有包含所有已提交日志条目的节点成为不了领导人。

       日志条目只有一个流向：从Leader流向Follower。领导人永远不会覆盖已经存在的日志条目。

       Raft算法使用投票的方式来阻止那些没有包含所有已提交日志条目的节点赢得选举。一个候选人为了赢得选举必须要与集群中的大多数节点进行通信，这就意味着每一条已经提交的日志条目都会出现在至少其中一个与之通信的节点上（可以用反证法证明）。如果候选人的日志比集群内的大多数节点上的日志更加新（或至少一样新），那么它一定包含所有已经提交的日志条目。因此，RequestVote RPC的接收方有一个检查：如果他自己的日志比RPC调用方（候选人）的日志更加新，就会拒绝候选人的投票请求。

       那么，如何比较两份日志哪个更加新呢？比较的依据是日志文件中最后一个条目的索引和任期号：如果两个日志条目的任期号不同，则任期号大的更加新；如果任期号相同，则索引值更大（即日志文件条目更多）的日志更加新。

Q：如何判断日志已经提交？

A：上文在“选举机制”中已经谈到过，领导人当前任期的某条日志条目只要存储在大多数节点上，就认为该日志记录已经被提交（committed）了。如果领导人在提交某个日志条目之前崩溃了，那么未来后继的领导人会让其他节点继续复制这条日志条目。

       然而，一个领导人不能因为由之前领导人创建（即之前任期）的某条日志存储在大多数节点上了，就笃定该日志条目已经被提交了。图1-12中的时序a～d展示了这种情况，一条已经被存储到大多数节点上的日志条目，也依然有可能会被未来的领导人覆盖掉。

图1-12　Raft算法某一时刻日志状态图

       时刻a，S1是任期2的领导人并且向部分节点（S1和S2）复制了2号位置的日志条目，然后宕机。

       时刻b，S5获得了S3、S4（S5的日志与S3和S4的一样新，最新的日志的任期号都是1）和自己的选票赢得了选举，成了3号任期的领导人，并且在2号位置上写入了一条任期号为3的日志条目。在新日志条目复制到其他节点之前，S5宕机了。

       时刻c，S1重启，并且通过S2、S3、S4和自己的选票赢得了选举，成了4号任期的领导人，并且继续向S3复制2号位置的日志。此时，任期2的日志条目已经在大多数节点上完成了复制。

       时刻d，S1发生故障，S5通过S2、S3、S4的选票再次成为领导人（因为S5最后一条日志条目的任期号是3，比S2、S3、S4中任意一个节点上的日志都更加新），任期号为5。然后S5用自己的本地日志覆写了其他节点上的日志。

       上面这个例子生动地说明了，即使日志条目被半数以上的节点写盘（复制）了，也并不代表它已经被提交（commited）到Raft集群了—因为一旦某条日志被提交，那么它将永远没法被删除或修改。这个例子同时也说明了，领导人无法单纯地依靠之前任期的日志条目信息判断它的提交状态。

       因此，针对以上场景，Raft算法对日志提交条件增加了一个额外的限制：要求Leader在当前任期至少有一条日志被提交，即被超过半数的节点写盘。

       正如图1-12中e描述的那样，S1作为Leader，在崩溃之前，将3号位置的日志（任期号为4）在大多数节点上复制了一条日志条目（指的是条目3，term         4），那么即使这时S1宕机了，S5也不可能赢得选举—因为S2和S3的最新日志条目的任期号为4，比S5的3要大，S3无法获得超过半数的选票。S5无法赢得选举，这就意味着2号位置的日志条目不会被覆写。

       将上面的描述归纳一下，可以总结为如下几点。

       1）只要一个日志条目被存在了大多数的服务器上，领导人就知道当前任期可以提交该条目了。

       2）如果领导人在提交日志之前就崩溃了，之后的领导人会试着继续完成对日志的复制。但是，新任领导人无法断定存储在大多数服务器上的日志条目一定在之前的任期中被提交了（即使日志保存在大部分的服务器上，也有可能没来得及提交）。