全面解读Raft共识算法

备注1：本系列内容由站长北侠撰写，内容来源于论文以及网上他人精品内容的参考，再此表示感谢！除此以外，站长北侠增加了很多个人的理解和思考，并在必有地方给以醒目提示，方便大家的阅读。好的架构是修改出来的，好的内容也是修改出来的，所以本系列内容不会写完了事，而是会不断地修订，提醒各位读者记得收藏和回访。一个人的理解角度总是有限的，欢迎更多的人提出自己的想法，让我们把这个系列内容构建的更完美一点，从而帮助更多的人。本系列内容的最后更新日期为：2021年6月20日。

备注2：Raft是一种共识算法，其源自于论文《In Search of an Understandable Consensus Algorithm》，需要注意两点：（1）Raft属于算法，而非协议（2）共识描述的是算法过程，而一致性描述的多副本的读取结果。共识和一致性是两个不同的概念和术语。很多人存在混用。

Raft是一种共识算法，其设计思路非常容易理解，但是它在容错性和性能上相当于Paxos。不同之处在于，Raft把共识难题分解成相对独立的子问题，从而分而治之，最终非常容易被人理解，并便于工程实现。

Raft本意是木筏，几根原木捆扎在一起便是木筏，寓意着集群管理的简单和便捷。其logo如下所示：

《全面解读Raft共识算法》
第一节：Raft是什么？
第二节：Raft算法论文
第三节：Raft算法应用场景
第四节：状态机复制与分布式系统的容错性
第五节：Raft共识算法的核心组件
第六节：Raft算法实现过程
第七节：Raft算法的独有特性
第八节：Raft算法的独有特性
第九节：Raft RPC简介
第十节：Raft日志复制
第十一节：Raft日志不一致的解决方案
第十二节：Raft算法中成员变更过程解析

第一节：Raft是什么？

Raft是一种共识算法，其设计非常容易理解。它在容错性和性能上相当于Paxos。不同之处在于，它被分解成相对独立的子问题，并且清晰地处理了实际系统所需的所有主要部分。Raft的作者希望Raft能够容易理解，并希望人们能够立足于Raft算法开发出比目前更高质量的共识系统。以目前的发展来看，Raft作者的初衷已然实现，在大数据生态圈子，Raft算法得到了广泛的应用。

第二节：Raft算法论文

Raft 算法的官方网站：https://raft.github.io/

Raft算法论文：https://raft.github.io/raft.pdf

第三节：Raft算法应用场景

随着互联网时代数据规模的爆发式增长，传统的单机系统在性能和可用性上已经无法胜任，分布式系统具有扩展性强，可用性高，廉价高效等优点，得以广泛应用。

分布式系统是指一组独立的计算机，通过网络协同工作的系统，客户看来就如同单台机器在工作。但与单机系统相比，分布式系统在实现上要复杂很多。CAP原则是分布式系统的理论基石。

2000 年的时候，Eric Brewer 教授提出了 CAP 猜想，2年后被 Seth Gilbert 和 Nancy Lynch 从理论上证明了猜想的可能性，从此，CAP 理论正式在学术上成为了分布式计算领域的公认定理，并深深的影响了分布式计算的发展。

CAP 理论告诉我们，一个分布式系统不可能同时满足一致性（Consistency)，可用性（Availability）和分区容错性（Partition tolerance）这三个基本需求，最多只能同时满足其中的2个。

• 一致性（Consistence）：指数据在多个副本之间能够保持一致的特性（严格的一致性）。
• 可用性（Availability）：指系统提供的服务必须一直处于可用的状态，每次请求都能获取到正确的响应，但是不保证获取的数据为最新数据。
• 分区容错性（Partition tolerance）：分布式系统在遇到任何网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务，除非整个网络环境都发生了故障。

对于分布式系统而言，P显然是必不可少的，那么只能在AP和CP之间权衡：
（1）AP系统牺牲了强一致性，这在某些业务场景下（如金融类）是不可接受的。
（2）CP系统可以满足强一致性这类需求，但是却牺牲了可用性。例如，传统的主备强同步模式虽然可以保证一致性，但一旦机器故障系统将变得不可用。

Paxos和Raft等共识算法的提出，弥补了这一缺陷。它们在保证CP的前提下，只要求大多数节点可以正常互联，系统便可以一直处于可用状态，可用性上显著提高。

Paxos的理论性偏强，开发者需要自己处理很多细节，这也是它有很多变种的原因，相对而言Raft更易理解和工程化，一经提出便广受欢迎。

有读者存在疑问：根据CAP理论，在分布式系统中一致性和可用性只能选一个，那Paxos、Raft等共识算法是如何做到在保证一定的可用性的同时，对外提供强一致性呢？

这个疑问的根源在于没有明白CAP理论后期的发展。在CAP理论提出十二年之后，其作者又出来辟谣：“三选二”的公式一直存在着误导性，它会过分简单化各性质之间的相互关系。

首先，由于分区很少发生，那么在系统不存在分区的情况下没什么理由牺牲C或A。

其次，C与A之间的取舍可以在同一系统内以非常细小的粒度反复发生，而每一次的决策可能因为具体的操作，乃至因为牵涉到特定的数据或用户而有所不同。

最后，这三种性质都可以在程度上衡量，并不是非黑即白的有或无。可用性显然是在0%到100%之间连续变化的，一致性分很多级别，连分区也可以细分为不同含义，如系统内的不同部分对于是否存在分区可以有不一样的认知。所以，一致性和可用性并不是水火不容，非此即彼的。

综之，Paxos、Raft等分布式共识算法就是在一致性和可用性之间做到了很好的平衡的见证。

第四节：状态机复制与分布式系统的容错性

1、什么是状态机？

“状态机”属于计算机理论方面的专业词汇，其定义是：状态机是有限状态自动机的简称，是现实事物运行规则抽象而成的一个数学模型。

“状态机”是个高大上的字眼，与之类似的还有“空间”。关于“空间”理解，我之前专门写过这样一段话：

我们知道，内存分为两部分，一部分被用户占用，一部分被操作系统占用，这个道理学过计算机的人都知道。但是，内存这个概念太土了，科学家们聚到一起开会的时候，总不能你一句内存，我一句内存的讨论问题吧，这不是成了电脑维修了。为了显示清高，科学家们随后就想了一个更高大上的字眼：空间。人类的世界就是由空间和时间构成的，而在计算机世界里面，也有了“空间”之说，立马是不是觉得变得高大上了呢。

同样道理，一群科学家围在一起，一口一个状态，变来变去，肯定把大家都绕晕了，使用状态机，不仅简单明了，更显得高大上。对于程序员来说，它还是一个抽象的数学模型。抽象在哪里呢？请君往下看：

先来解释什么是“状态”（ State ）。现实事物是有不同状态的，例如一个自动门，就有 open 和 closed 两种状态。我们通常所说的状态机是有限状态机，也就是被描述的事物的状态的数量是有限个，例如自动门的状态就是两个 open 和 closed 。

状态机，也就是 State Machine ，不是指一台实际机器，而是指一个数学模型。说白了，一般就是指一张状态转换图。例如，根据自动门的运行规则，我们可以抽象出下面这么一个图：

自动门有两个状态，open 和 closed ，closed 状态下，如果读取开门信号，那么状态就会切换为 open 。open 状态下如果读取关门信号，状态就会切换为 closed 。

状态机的全称是有限状态自动机，自动两个字也是包含重要含义的。给定一个状态机，同时给定它的当前状态以及输入，那么输出状态时可以明确的运算出来的。例如，对于自动门，给定初始状态 closed ，给定输入“开门”，那么下一个状态时可以运算出来的。

这样状态机的基本定义我们就介绍完毕了。重复一下：状态机是有限状态自动机的简称，是现实事物运行规则抽象而成的一个数学模型。

2、状态机的四大部分

状态机是一个抽象的数学模型，其分为四大部分组成。如下所示：

第一个是 State 状态。一个状态机至少要包含两个状态。例如上面自动门的例子，有 open 和 closed 两个状态。

第二个是 Event 事件。事件就是执行某个操作的触发条件或者口令。对于自动门，“按下开门按钮”就是一个事件。

第三个是 Action 动作。事件发生以后要执行动作。例如事件是“按开门按钮”，动作是“开门”。编程的时候，一个 Action 一般就对应一个函数。

第四个是 Transition 变换。也就是从一个状态变化为另一个状态。例如“开门过程”就是一个变换。

编写代码的时候，有时会遇见较为复杂的swith...case...和if...else...语句。这一刻有时会想到状态机，用有限状态机替换swith...case...和if...else...

3、容错性

容错性是个令人容易产生歧义的术语。从字面上来看，是“容忍错误”之意，非也。请看下文来自百度百科的介绍：

故障容许度（英语：Fault tolerance）也称容错、容错性，是使系统在部分组件（一个或多个）发生故障时仍能正常运作的能力。

故障容许度即是Fault Tolerance，确切地说是容故障（Fault），而并非容错误（Error）。

例如在双机容错系统中，一台机器出现问题时，另一台机器可以取而代之，从而保证系统的正常运行。在早期计算机硬件不是特别可靠的情况下，这种情形比较常见。现在的硬件虽然较之从前稳定可靠得多，但是对于那些不允许出错的系统，硬件容错仍然是十分重要的途径。

4、状态机复制

共识是分布式系统中的一个基本问题。共识就是多个服务器就某个值而言，最终达成一致的决策过程。一旦它们对一个值做出决定，这个决定就是最终决定。一般情况下，共识算法只要满足“多数存活”的原则即可，例如，一个由5台服务器组成的集群，即使有2台服务器出现故障也可以继续运行。如果有更多的服务器出现故障，它们将停止工作，但永远不会返回错误的结果。

共识算法通常依赖于状态机复制，这是构建容错系统的通用做法。所谓“容错性”指的是，分布式系统在遇到任何网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务，除非整个网络环境都发生了故障。

如果我们要让一个服务具有容错能力，那么最常用最直接的办法就是让一个服务的多个副本同时运行在不同的节点上。但是，当一个服务的多个副本都在运行的时候，我们如何保证它们的状态都是同步的呢，或者说，如果让客户端看起来无论请求发送到哪一个服务副本，最后都能得到相同的结果。实现这种同步方法就是所谓的状态机复制（State Machine Replication）。

状态机复制的理论基础是：如果集群里的每一个节点上都运行着相同的确定性状态机S，并且所有的状态机刚开始都处于同样的初始状态s0，那么给予这些状态机相同的输入序列：

{i1, i2, i3, i4, i5, i6, …, in}

这些状态机必然会经过相同的状态转换路径：

s0->s1->s2->s3->…->sn

最终达到相同的状态sn，同时生成相同的输出序列：

{o1(s1), o2(s2), o3(s3), …, on(sn)}

状态机复制在实际应用中的一个例子就是MySQL集群。我们知道，MySQL集群中的master会把所有的操作记录到binlog中，这里的操作就是输入序列I，然后slave会把master上的binlog复制到自己的relaylog中，然后再把relaylog里的操作回放一遍（相当于执行了一遍输入序列I）。所以，如果master和slave里的状态机是完全相同的，并且在执行序列I之前都处于相同的状态下，那么执行完序列I后，它们的状态依旧是相同的（一致性）。

在执行输入序列I的过程中，根据同步方式的不同，系统就有了强一致性和最终一致性。如果我们要求对于序列I中的每一个in， 都需要所有的服务副本确认成功执行了in，才能执行in+1，那么这个系统就是强一致性的系统。如果我们取消掉这个限制，仅仅要求所有的服务副本执行相同的输入序列I，但是完全各自独立执行，而不需要在中间同步，那么就有了最终一致性（各服务都会达到相同的最终状态，但是达到的时间不确定）。

所有一致性算法都会涉及到状态机，而状态机保证系统从一个一致的状态开始，以相同的顺序执行一些列指令最终会达到另一个一致的状态。

第五节：Raft共识算法的核心组件

Raft共识算法的核心设计包括两大部分：状态机与日志。

状态机的介绍，请看上文，而对于日志的理解，常常是初学者容易迷惑的地方。在Raft语境下，我们所说的“日志”并不是系统运行的警告，错误等信息等，而是指操作记录。例如，set x to 3等。

每台服务器都有一个状态机和一个日志。状态机本质就是一个具有容错性的组件。在客户机看来，即使集群中的少数服务器出现故障，它们也会与单个可靠的状态机进行交互。每个状态机处理相同的命令序列，从而产生相同的结果序列并到达相同的状态序列。

第六节：Raft算法实现过程

Raft算法主要包括选举和日志同步两部分：

• 第一阶段：选举。从集群中选出一个合适的节点作为Leader。
• 第二阶段：日志同步。选举出的Leader接收客户端请求，将其转为Raft日志。Leader将日志同步到其他节点，当大多数节点写入成功后，日志变为Committed，一经Committed日志便不会再被篡改。Leader故障时，切换到第一阶段，重新选举。

第七节：Raft算法的独有特性

Raft算法是专门针对Paxos算法难以理解的缺陷而重新设计的新算法，为使算法容易理解，采用了模块化设计方法，将整个过程划分为若干子问题，逐一解决，这些问题包括Leader选举，日志分发，日志一致性等。

Raft算法和已有的其他共识算法有很多相似之处，但也有自己独特的特性：

（1）高度集权的Leader。相对其他共识算法，Raft的Leader权利更集中，例如，只有Leader可以接受客户请求，所有日志都是通过Leader分发给其他服务器。这一特性简化了日志管理，也让算法容易理解。

（2）非常简单的Leader选举。Leader选举过程采用随机时间计时器，谁先完成沙漏倒计时谁就最有可能成为Leader，做法简单粗暴但异常好用，快速地解决了Leader选举过程中的各种冲突。

（3）成员变化，系统不罢工。当集群的成员发生变化，例如增加或减少服务器时，Raft采用新的联合一致性方法来进行处理，可以保证成员变化过程中系统正常工作。

第八节：Raft算法的独有特性

1、选举思想

在Raft算法中，充斥着“君主高度集权，立储简单明了”的思想。首先，Raft集群会选举出一个唯一的Leader，该Leader负责管理日志(日志，即操作记录日志)，并且所用对日志的添加和修改等操作都通过Leader完成。Leader接受用户的日志请求并将日志分发给系统中其他节点，并告知其他节点何时可以安全地将日志应用到状态机上。这种方式简化了多副本日志的管理，日志的数据流向是从Leader到其他节点，而其他节点不会发送日志给Leader，职责分明，非常简单。Leader宕机之后，Raft集群会选出一个新的Leader。

通过采用高度集权的Leader，Raft把一致性问题分解为相互独立的3个子问题：

（1）Leader选举：系统初始化时需要选出Leader，Leader当掉时选出新的Leader。
（2）日志分发：Leader接受日志请求并分发给其他节点。
（3）确保日志的一致性：确保所有日志副本是一致的。

2、节点的状态

在Raft集群中，任何一个节点在任何一个时刻都处于三种状态之一：Leader, Follower, Candidate。

在系统正常运行的绝大部分时间，系统中会有一个Leader, 其他都是Follower。Follower是被动的，只接受来自Leader和Candidate的请求，自己不会发出任何请求。Candidate状态是在Leader选举过程中的临时状态。为了更好的深刻的掌握这三种状态，我将它们起名叫：群众，夺权者，当权者。下图描述了三种状态之间的转换关系：

对于初学者来说，上面的状态转换令人眼花缭乱，我给大家简单的说一下。假设集群中有一台服务器A，最初(starts up)的状态为follower，沙漏耗尽之后开始了选举，它有一个不安分的心，它想当leader，此时它的状态变为candidate，然后它向集群中其他服务器发送“选我”信息，如果收到大多数成员的同意之后，则成功当选为leader，反之，如果没有收到大多数成员的同意而收到了新leader的消息，则灰头土脸的继续当“庶民”，状态还原为follower。其实，即便当上了leader，也是高处不胜寒的，有一天也会被他人篡权夺位，而变为庶民的。

3、任期的理解

Raft把时间分为连续的任期(Term)，每个任期可以是任意时长，任期用连续的整数进行标号。每个任期首先进行Leader选举，选举时，多个Candidate竞争成为Leader,一旦某个节点成为Leader，其他节点则变回Follower，成为Leader的节点将在该任期内一直担任Leader，如果该Leader节点发生故障，其他节点会在新的任期内进行选举。任何一个任期内都不会有多个Leader。Raft系统中，任期是一个及其重要的概念，每个节点都维护着当前任期的值，每次节点间的通信都包含任期信息，每个节点在检测到自己的任期值低于其他节点，都会更新自己的任期值，设置为检测到的较高的值。当Leader和Candidate发现自己的任期低于别的节点，则立即把自己转换为Follower。

注意：任期与计时器是绑定到一起的。任何新任期的启动，必然伴随一个新计时器的启动。

4、远程调用RPC

Raft节点间的通信采用RPC调用， Raft算法核心部分只需要用到两个RPC: RequestVote和AppendEntries。

RequestVote RPC由Candidate发起用于Leader选举。AppendEntries RPC由Leader发起，用于心跳和日志复制。而Follower不会发起任何RPC。

5、Leader选举过程

Raft采用心跳机制触发Leader选举。当系统启动时，所有节点初始化为Follower状态，设置任期为0，并启动计时器，计时器超时后，Follower节点转化为Candidate节点，一旦转化为Candidate节点，立即开始做以下几件事情：

（1）增加自己的任期数
（2）启动一个新的计时器
（3）给自己投一票
（4）向所有其他节点发送RequestVote RPC请求，并等待其他节点回复。

如果在计时器超时前接收到多数节点的同意投票，则转换为Leader。如果接受到其他节点的AppendEntries心跳RPC，说明其他节点已经被选为Leader, 则转换为Follower。如果计时器超时的时候还没有接受到以上两种信息中的任何一种，则重复步骤1-4，进行新的选举。

节点在接受到多数节点的投票成为Leader后，会立即向所有节点发送AppendEntries 心跳RPC。所有Candidate收到心跳RPC后，转换为Follower，选举结束。

每个Follower在一个任期内只能投一票，采取先到先得的策略。每个Follower有一个计时器，在计时器超时时仍然没有接受到来自Leader的心跳RPC, 则转换为Candidate, 开始请求投票。也就是在当期Leader当掉后，就会有Follower开始转换为Candidate开始投票。

如果多个节点同时发起投票，每个节点都没有拿到多数票（这种情况成为Split Vote），则增加任期数，在新的任期内重新进行投票。有没有可能Split Vote反复发生，永远都选不出Leader呢？不会的。因为Raft采取随机超时时间，Raft系统有一个选举超时配置项，Follower和Candidate的计时器超时时间每次重新计算，随机选取配置时间的1倍到2倍之间。即使所有节点同时启动，由于随机超时时间的设置，各个节点一般不会同时转为Candidate，先转为Candidate的节点会先发起投票，从而获得多数票。因而在每个任期内，多个节点同时请求投票并且都只获得少数票的几率很小，连续多次发生这种情况几率更小，实际上可以认为完全不可能发生。一般情况下，基本上都在1-2个任期内选出Leader。

第九节：Raft RPC简介

通过上面的内容我们可以得知，Raft核心部分只需要用到2个RPC：RequestVote和AppendEntries。每个Raft节点将会根据自己节点的状态数据来对这两种RPC请求进行处理。

RequestVote RPC是由Candidate发送给其他节点，请求其他节点为自己投票，如果一个Candidate获得了多数节点的投票，则该Candidate转变为Leader。

AppendEntries RPC是由Leader节点发送给其他节点，有两个作用，当其entries域为空时，该RPC作为Leader的心跳；当entries域不为空时，请求其他节点将entries域中的日志添加到自己的日志中。

第十节：Raft日志复制

1、日志复制的过程

Leader选出后，就开始接收客户端的请求。Leader把请求作为日志条目（Log entries）加入到它的日志中，然后并行地向其他服务器发起 AppendEntries RPC 复制日志条目。当这条日志被复制到大多数服务器上，Leader将这条日志应用到它的状态机并向客户端返回执行结果。

客户端的每一个请求都包含被复制状态机执行的指令。Leader把这个指令作为一条新的日志条目添加到日志中，然后并行发起 RPC 给其他的服务器，让它们复制这条信息。假如这条日志被安全的复制，Leader就应用这条日志到自己的状态机中，并返回给客户端。如果Follower宕机或者运行缓慢或者丢包，Leader会不断的重试，直到所有的Follower最终都复制了所有的日志条目。

2、日志的组成

日志由有序编号（log index）的日志条目组成。每个日志条目包含它被创建时的任期号（term）和用于状态机执行的命令。如果一个日志条目被复制到大多数服务器上，就被认为可以提交（commit）了。

上图显示，共有 8 条日志，提交了 7 条。提交的日志都将通过状态机持久化到磁盘中，防止宕机。

3、日志复制的详细介绍

当Leader接收到由客户端发送的请求(请求中包含可以被复制状态机执行的命令)时，Leader将会把该请求作为新的内容添加到日志中(任期号为当前Leader所处的任期号，索引号为当前Leader本地存储的日志集合中的日志的最高索引号加1)。然后将该日志通过AppendEntries RPC消息发送到网络中其他的服务器(以下简称Follower)，从而复制该日志。在网络中Follower接收到该日志消息后则会返回复制成功的回复。

在Leader接收到网络中大部分的Follower的成功复制的回复之后，Leader便认为该日志可以被提交。此时Leader将会同时做三件事：

（1）将该日志应用到Leader本地的复制状态机
（2）向所有Follower发送消息通知所有接收到该日志的Follower将该日志进行提交，然后应用到各自本地的复制状态机
（3）将执行结果通知客户端

当该日志消息成功在网络中大部分Follower本地的复制状态机执行过后，则可认为该日志已被提交。在当前日志被提交的过程中，如果Leader先前的某些日志还没有被提交，则将会一同提交。而网络中有些Follower可能由于网络状态原因反应缓慢或者崩溃，那么Leader将会无限次地尝试重复发送AppendEntries RPC消息到该Follower。直到成功为止。

4、Leader切换导致日志的不一致性

5、日志的一致性检查

如上所述，Follower在接收到AppendEntries RPC消息后则会返回复制成功的回复。实际上在接收到消息后会首先进行日志的一致性检查(正常情况下Leader与Follower的日志会保持一致，所以一致性检查不会失败)，一致性检查内容如下：

在Leader创建AppendEntries RPC消息时，消息中将会包含当前日志之前日志条目的任期号与索引号。Follower在接受到AppendEntries RPC消息后，将会检查之前日志的任期号与索引号是否匹配到。如果匹配则说明和Leader之前的日志是保持一致的，否则，如果没有匹配则会拒绝AppendEntries RPC消息。

一致性检查是一个归纳的过程。正常情况下，网络中第一条日志一定满足日志的一致性检查，然后第二条日志中包含第一条日志的任期号与索引号，所以只要Leader与Follower的第一条日志保持一致，那么第二条日志也会满足一致性检查，从而之后的每一条日志都会满足一致性检查。

从而得出了日志匹配属性:

（1）如果两个不同的日志实体具有相同的索引和任期号，那么它们存储有相同的命令。
（2）如果两个不同的日志实体具有相同的索引和任期号，则所有先前条目中的日志都相同。(由一致性检查结果得出)

第十一节：Raft日志不一致的解决方案

1、日志不一致的三种情况

网络不可能一直处于正常情况，因为Leader或者某个Follower有可能会崩溃，从而导致日志不能一直保持一致，因此存在以下三种情况：

（1）Follower缺失当前Leader上存在的日志条目。

（2）Follower存在当前Leader不存在的日志条目。

比如，旧的Leader仅仅将AppendEntries RPC消息发送到一部分Follower就崩溃掉，然后新当选Leader的服务器恰好是没有收到该AppendEntries RPC消息的服务器)

（3）Follower即缺失当前Leader上存在的日志条目，也存在当前Leader不存在的日志条目。

为了更好的说明这三种情况，请看下面的图示。

备注：

（1）图中最上方是日志的索引号(1-12)，每个方块代表一条日志信息，方块内数字代表该日志所处的任期号。

（2）图中当前Leader(图中最上方一行日志代表当前Leader日志)处于任期号为8的时刻。

分析说明

下面，以此图分析说明以上三种情况存在的原因：

（1）Follower a、Follower b满足以上说明的第一种情况：Follower崩溃没有接收到Leader发送的AppendEntries RPC消息。

（2）Follower c在任期为6的时刻，Follower d在任期为7的时刻为Leader，但没有完全完成日志的发送便崩溃了，满足以上说明的第二种情况：Follower存在当前Leader不存在的日志条目。

（3）Follower e在任期为4的时刻，Follower f在任期为2、3的时刻为Leader，但没有完全完成日志的发送便崩溃了，同时在其他服务器当选Leader时刻也没有接收到新的Leader发送的AppendEntries RPC消息，满足第三种情况：Follower即缺失当前Leader上存在的日志条目，也存在当前Leader不存在的日志条目。

备注： 如上文所示，根据日志的任期数目来判断节点是否为Leader，再次印证了任期的关键作用。

2、日志不一致的解决方案

Leader通过强迫Follower的日志重复自己的日志来处理不一致之处，这意味着Follower日志中的冲突日志将被Leader日志中的条目覆盖。这个过程如下所示：

首先，Leader找到与Follower最开始日志发生冲突的位置，然后删除掉Follower上所有与Leader发生冲突的日志，最后将自己的日志发送给Follower以解决冲突。需要注意的是：Leader不会删除或覆盖自己本地的日志条目。

当发生日志冲突时，Follower将会拒绝由Leader发送的AppendEntries RPC消息，并返回一个响应消息告知Leader日志发生了冲突。

Leader为每一个Follower维护一个nextIndex值。该值用于确定需要发送给该Follower的下一条日志的位置索引。该值在当前服务器成功当选Leader后会重置为本地日志的最后一条索引号+1。

当Leader了解到日志发生冲突之后，便递减nextIndex值，并重新发送AppendEntries RPC到该Follower，不断重复这个过程，一直到Follower接受该消息。

一旦Follower接受了AppendEntries RPC消息，Leader则根据nextIndex值可以确定发生冲突的位置，从而强迫Follower的日志重复自己的日志以解决冲突问题。

情况a：如上图，服务器S1在任期为2的时刻仅将日志<index:2,term:2>发送到了服务器S2便崩溃掉。

情况b：服务器S5在任期为3的时刻当选Leader(S5的计时器率先超时，递增任期号为3，高于服务器S3和S4，因此可以当选Leader)，但没来得及发送日志便崩溃掉。

情况c：服务器S1在任期为4的时刻再次当选Leader(S1重启时，任期仍然为2，收到新的Leader S5发送的心跳信息后更新任期为3，而在Leader S5崩溃后，服务器S1为第一个计时器超时的，因此发起投票，任期更新为4，大于网络中其他服务器任期，成功当选Leader)，同时将日志<index:2,term:2>发送到了服务器S2和S3，但还没有通知服务器对日志进行提交便崩溃掉。

情况d：情况(a->d)如果在任期为2时服务器S1作为Leader崩溃掉，S5在任期为3的时刻当选Leader，由于日志<index:2,term:2>还没有被复制到大部分服务器上，并没有被提交，所以S5可以通过自己的日志<index:2,term:3>覆盖掉日志<index:2,term:2>。

情况e：情况(a->e)如果在任期为2时服务器S1作为Leader，并将<index:2,term:2>发送到S2和S3，成功复制到大多数成员服务器上。S1成功提交了该日志，那么即便S1崩溃掉，S5也无法成功当选Leader，因为S5不具备网络中最新的已被提交的日志条目，S5只有term为1的日志。

第十二节：Raft算法中成员变更过程解析

在Raft论文中，成员变更属于难点，但这一部分相比于论文其他部分，确实讲解最不详细，让人读完之后很迷惑。

1、什么是成员变更？

成员变更指的是系统成员变化，即服务器节点的上下线，这和由于宕机故障导致的上下线是不同的。宕机或者重启导致的上下线，是不会影响系统的注册的成员数量的，也就不会影响到一致性判断所依据的“多数派”的生成，众所周知，“多数派”是所有一致性的基础。成员变更时，会修改注册的成员数量，比如在实际应用中，为了提高安全等级，就很可能出现需要把备机数量由三台扩充到五台，在这种情况下，就发生了成员变更。

另外，还有一个十分需要注意的地方：成员变更意味着大家都还活着，并不像宕机那样，立即死亡，无法再做“交接工作”。被变更的成员是需要完成“交接工作”的。所谓的“交接工作”，就是下文中提到的“做决策”。

2、直接变更存在的问题

在成员变更时，因为无法做到在同一个时刻使所有的节点从旧配置转换到新配置，那么直接从就配置向新配置切换就可能存在一个节点同时满足新旧配置的“超过半数”原则。

如下图，原集群由Server1、Server2、Server3，现在对集群做变更，增加Server4、Server5。如果采用直接从旧配置到新配置的切换，那么有一段时间存在两个不想交的“超过半数的集群”。

上图，中在中间位置Server1可以通过自身和Server2的选票成为Leader（满足旧配置下收到大多数选票的原则）；Server3可以通过自身和Server4、Server5的选票成为Leader（满足新配置线，即集群有5个节点的情况下的收到大多数选票的原则）；此时整个集群可能在同一任期中出现了两个Leader，这和协议是违背的。

3、Raft的成员变更实现方案：分阶段变更

Raft提出了通过一个中间过渡阶段，即联合共识（joint consensus），逐步把数据写入的新的集群中。其具体做法是2阶段提交式的：

第一阶段：Leader收到C-old到C-new的配置变更请求时，创建C-old-new的日志并开始复制给其他节点，此日志和普通日志复制没有区别。此时做决策的仍然是C-old集群。

第二阶段：当只有C-old-new复制到大多数节点后，Leader以这个配置做决定，这个时候处于一个共同决定的过程，因为此时做决策的是C-old-new集群。

由于两阶段变更不存在一个阶段C-old和C-new可以同时根据自己的配置做出决定，所以不会出现上文描述的情况。

备注：虽然自己是Leader，但是做决策的可不是Leader，它要根据多数派的原则进行拍板定方案，所以归根结底，做决策的还是集群中的其他Follower成员。

4、Raft论文解读

论文里面的这张图片看起来让人头大，个人感觉有点凌乱。虚线表示已创建但尚未提交的配置项，实线表示已经提交的配置项。最难以理解的地方在于最上面的“豁口”，其表示中间过渡阶段，即联合共识（joint consensus），其开始于C-old-new复制到大多数节点后，而结束于C-new提交之后，因为C-old-new与C-new的配置内容虽不相同但是一致，两者是等价的，所以可以视为C-new能够单独做决定。当C-new被复制到大多数节点的时候，如果Leader不在C-new之内，则自己做下线处理，C-new集群开始进行新的选主操作。