(六)漫谈分布式之一致性算法上篇：用二十六张图一探Raft共识算法奥妙之处！

  (六)漫谈分布式之一致性算法上篇：用二十六张图一探Raft共识算法奥妙之处！

======================================

引言

—

本文为稀土掘金技术社区首发签约文章，30天内禁止转载，30天后未获授权禁止转载，侵权必究！

在上篇文章里，对Paxos这个大多数一致性算法的“老祖宗”做了全面阐述，在上章最后，提到了Multi-Paxos这个变种算法，相较于Basic-Paxos，Multi-Paxos提到了Leader的概念，在系统运行的大部分时间里，只允许一个Proposer提出提案，这种方式能有效提高共识收敛速度和减少通信延迟。

但Multi-Paxos算法在脑裂情况下，又有可能退化成Basic-Paxos模式，遇到极端场景，会陷入Prepare的死循环问题，从而导致多个Leader失去活性。正因如此，Multi-Paxos的思想虽然在许多地方沿用，不过很少有地方直接实现Multi-Paxos算法，现如今，大多数分布式存储系统都投向了Raft算法的怀抱，而本文就来聊聊大名鼎鼎的Raft算法/协议！

PS：个人编写的《技术人求职指南》小册已完结，其中从技术总结开始，到制定期望、技术突击、简历优化、面试准备、面试技巧、谈薪技巧、面试复盘、选Offer方法、新人入职、进阶提升、职业规划、技术管理、涨薪跳槽、仲裁赔偿、副业兼职……，为大家打造了一套“从求职到跳槽”的一条龙服务，同时也为诸位准备了七折优惠码：3DoleNaE，在为找工作而困扰的小伙伴可以点击：s.juejin.cn/ds/USoa2R3/了解详情！

一、Raft协议的基本概述

对存储型系统来说，为了消除单点故障、提高可用性，系统会用集群方案部署，而数据则则以副本形式存储在多个节点，那多个节点间的数据如何保证一致？答案是共识算法，而之前聊的Paxos算法，几乎就是所有共识算法的根儿，它即可以保证分布式系统中的一致性，又能保证在小部分节点（半数减一）发生故障时，系统依旧能够正常对外服务。

可由于Paxos算法实在难以理解，Raft横空出世！Raft算法的立意就是为了推出一个更容易理解的共识算法，这一点从它的论文名字就能看出：《In Search of an Understandable Consensus Algorithm》。

实际上，Raft也可以看作是Multi-Paxos的一种派生实现（Multi-Paxos本身只有思想，论文里没有给出实现细节），它沿用了Multi-Paxos单Proposer的思想，保证了运行期间内只会存在一个Leader节点，而且是强Leader模式，宁愿让系统没有Leader陷入瘫痪，也不允许出现脑裂现象，对外服务的任意时刻都只能存在一个Leader。

Raft和Paxos的设计理念相同，都是为了解决分布式系统的一致性问题，可Raft为了更易于理解，主要做了两方面的工作：问题分解、状态简化，下面展开聊聊。

1.1、问题分解

刚刚提到过Raft的显著特点：强Leader特性，使用Raft算法的集群，必须存在一个主节点才能工作，因为客户端的所有操作，都会先交给Leader节点处理。既然如此，我们能保证运行期间主节点一直不挂掉吗？显然不能，在网络故障、宕机等问题随时都有可能发生的分布式系统里，Leader节点也不例外。

既然Leader有发生故障的风险，而Raft集群又重度依赖于Leader节点完成工作，那么Raft算法的第一个核心问题就是：领导者选举（Leader Election），只有时刻保证Leader节点的可靠性，才能让Raft集群正常处理外部请求。

通过选主机制保证了Leader的稳定性后，因为客户端的操作都会交由主节点处理，所以要实现集群副本之间的一致性，只需要将主节点上的数据操作，同步给集群内其他节点即可，而这就是Raft算法第二个核心问题：日志复制（Log Replication）。

依靠同步机制保证了副本间的一致性后，由于Leader节点责任重大，在选举时必须要慎之又慎！比如一个新节点刚加入集群，此时Leader节点刚好宕机，于是集群触发选举机制，巧合之下，刚加入的新节点成为了新Leader，这是否合理？No，毕竟刚加入集群的新节点，连客户端原先写入的数据都不具备……。正因如此，Raft在做领导者选举、日志复制时，必须要有一定的限制，这对应着Raft算法第三个核心问题：安全性（Safety）。

综上所述，Raft对共识算法进行了拆解，从中分解出领导者选举、日志复制、安全性这三个子问题，围绕这三个子问题展开，构成了Raft算法的核心内容，而这三部分的具体内容，我们放到后面一起讨论。

1.2、状态简化

Raft除开将共识算法分解成三个子问题外，还简化了Paxos中的状态，在Paxos算法中定义了Proposer、Acceptor、Learner三种角色，并且这些角色并不会固化在某个节点上，Paxos集群中的任意节点，即可能是Proposer提案者，也有可能是Acceptor接受者或Learner学习者。

因为节点的角色会动态变化，所以集群内的状态流转会额外复杂，相同时间的任意节点，都能发起提案、批准提案、学习提案，这也说明Paxos是一种P2P算法，集群每个节点的地位、能力都是平等的！Paxos这种思想十分先进，可实现起来额外困难，而Raft算法中则简化了集群内的状态。

Raft算法通过选举出Leader节点，从而将Paxos的Proposer角色固化在一个节点上，在运行期间内，只允许一个节点发出提案，剩余节点只能被动接受、学习提案，来看这张摘自Raft论文里的原图：

在同一时刻，Raft集群的各节点会固化一种角色，即一个节点只会属于Leader、Follower、Candidate其中一种角色！相较于Paxos，这种模式就极大程度上减少了算法的状态数量，及可能产生的状态变动，毕竟Raft只需要考虑选举期间发生的角色切换，而不需要像Paxos那样考虑多种角色的共存和互相造成的影响。

关于Raft协议的三个核心内容，以及几种角色之间的切换，聊到这里暂且打住，Raft本质是基于“状态机”工作的一种算法，而究竟什么叫状态机呢？一起来看看。

1.3、复制状态机

Replicated State Machine复制状态机是一种抽象的概念，主要目的是用于确保分布式系统中各节点其副本状态的一致性。Raft复制状态机由多个复制单元组成，每个复制单元存储一个包含一系列指令的日志，来看论文中给出���示意图：

上面层叠的黄色卡片，就是一个个复制单元，说人话就是Raft集群里的一个个节点。当客户端向Raft服务集群发起请求时，Raft会将对应的操作封装成日志（Log），如果存在多个操作，则会将不同的操作封装成一个个Entry节点放入到日志里。正如上图所示，Log由多个Entry组成，x←3，表示将x这个变量赋值为3，而客户端一系列操作对应的Log，最终会被放到Leader节点的State Machine状态机中。

状态机其实是个用于描述程序行为的数学模型，属于学术界的名词，举例说明，假设目前x=1，当客户端向服务端发起一个x←3的操作后，服务端存储的x值，就会从初始态（1）变成结束态（3），这就是一种状态机的表现，而Raft中的复制状态机，即是指将Leader节点的状态机，应用到所有复制单元（每个节点）上，在分布式系统中：

如果一开始所有节点的副本数据都一致（状态相同），执行同样的操作指令后，最终的副本状态肯定也一致。

当然，这里说的“同样的操作指令”，指的是执行顺序也要一致！如上图中的案例，在Leader节点依次执行x←3、y←1、y←9指令后，剩余节点也依次执行这三个指令，那么最终所有节点的数据必然是x=3、y=9，因此，只要实现了复制状态机，就能够保证分布式系统的数据一致性，客户端不管从哪个节点读取，都能看到相同的结果。

1.4、Raft角色与转变

简单理解复制状态机的概念后，接着来看看Raft定义的三种节点角色/状态：

大家暂时先别看图中的箭头，先看看图中的三种角色：

• Leader领导者：负责处理客户端的所有操作，并将操作封装成日志同步给集群其他节点；
• Follower追随者：负责接收Leader节点封装好的日志，并应用于自身的状态机里；
• Candidate候选者：当集群中没有Leader节点时，追随者会转变成候选者，尝试成为新Leader。

如果对分布式技术有所掌握的小伙伴，对这三个概念并不陌生，这是所有主流技术栈中都存在的概念，只不过某些地方叫法不同罢了。不过值得说明的一点是，Follower追随者本身并不具备处理任何客户端请求的能力，当Follower接收到外部请求时，会将客户端请求重定向到Leader处理，只是在有些技术栈里，为了充分利用空闲资源，会允许Follower处理读类型的操作，毕竟读操作并不会引起状态变化。

简单了解三种节点角色后，各位再把目光聚焦到图中的箭头上，这是指集群节点的角色转变过程，在集群启动时，所有节点都为Follower类型，而根据起初的定论，Raft集群必须要有一个Leader节点来处理外部的所有操作，为此，在集群启动后就会出现第一轮选主过程。Raft中为了区分每一轮选举，定义了一个概念：term（任期）。

每一轮新的选举，都被称为一个任期，每个term都有一个唯一标识来区分，这个标识就叫做任期编号，并且与Paxos的提案编号具备相同属性，必须要保证严格的递增性！即第二轮选举对应的任期编号，一定会大于第一轮选举的任期编号。

集群启动会触发第一轮选举，对应的任期编号为1，选举的过程也不难理解，当一个Follower节点发现没有Leader存在时，自己会转变为Candidate节点，先投自己一票，接着向其他节点发起拉票请求，如果得到了大多数节点（半数以上）的节点支持，此Follower节点就会成为本轮任期中的Leader节点。

上面这个过程，就完成了Follower、Candidate、Leader三种角色的转变，听起来似乎很简单，可是却存在很多细节，如：

• Follower是如何感知到没有Leader存在的？
• Candidate是怎么向其他节点拉票的？
• 如果多个Follower一起转变成Candidate拉票怎么办？
• 新Leader上线，其他节点是如何成为其追随者的？
• ……

这些细节就构成了Raft选举的核心知识，下面来展开聊下Raft算法的领导者选举机制。

二、Raft领导者选举（Leader Election）

开始一轮新选举的前提是要感知到没有Leader存在，具体是如何实现的呢？很简单，就是之前提过无数次的心跳机制，心跳机制建立在通信的基础之上，所以Raft也是一种基于消息传递的共识算法。

在Raft协议中，心跳包、日志复制、拉票/投票等消息的传递，都依赖RPC来做通信，主要分为两大类：

• RequestVote RPC：用于选举阶段的拉票/投票通信；
• AppendEntries RPC：用于存在Leader时期的日志复制、发送心跳。

Raft依托这两类RPC完成集群工作，不管是哪类RPC，在通信时都会携带自己的任期编号，通过附带的任期号，就能将所有节点收敛到一致状态，如Leader、Candidate收到一个RPC时，发现大于自己的编号，说明自身处于过期的任期中，此时就会自动转变到Follower角色。

不过这些细节先不展开，我们先来看下前面给出的第一个疑惑：Follower是如何感知到没有Leader的？答案是心跳机制。

2.1、Raft心跳机制

Raft中的心跳包只能由Leader发出，作用主要有两点，其一是帮助Leader节点维持领导者地位，持续向集群内宣布自己还“活着”，防止其他节点再次发起新一轮的选举；其二是帮助Leader确认其他节点的状态，如果某个节点收到心跳包后未作回复，Leader就会认为该节点已下线或陷入故障了。

结合上述知识来看前面的问题，集群只要有Leader存在，就一定会有心跳包发出，刚启动时，因为所有节点的角色都是Follower，这意味着不会有节点收到心跳包，因此，Follower会认为领导者已经离线（不存在）或故障，接着就会发起一轮新的选举过程。

PS：一轮选举/一个term中，一个节点只能投出一票！

再来看个问题，最开始所有节点都是Follower，如果同时检测到Leader不存在，一起转变成Candidate开始拉票怎么办？

上图中，五个节点都持有自己的一票，没有任何节点胜出，本轮选举就会陷入僵局，而Raft自然考虑到了这种局面，所以对term任期附加了一个条件：一轮任期在规定时间内，还未票选出Leader节点，就会开始下一轮term！不过仅这一个条件还不够，毕竟新的一轮选举中，各节点再次一起拉票，又会回到互相僵持的局面……

如果一直处于这种情况，会导致Raft选主的过程额外低效，因此，为了跳出这个死循环，Raft给每个节点加了随机计时器，当一个节点的计时器走完时，依旧未收到心跳包，就会转变成Candidate开始拉票，因为这个计时器的值存在随机性，所以不可能全部节点一起转变成Candidate节点，这就从根源上解决了前面的僵持性问题。

PS：这个随机计时器，也会成为一轮选举的超时限制，Raft论文给出的建议是150~300ms，后续再做展开。

不过就算加上随机计时器后，也不一定能100%保证同时不出现多个Candidate，Raft接受多个Candidate同时拉票，但只允许一轮选举中只有一个节点胜出！咋做到的？依靠集群大多数节点的共识，只有拿到半数以上节点的投票，对应的Candidate才有资格成为本轮任期中的Leader。

Candidate过多会导致票数过于分散，比如由九个节点组成的集群，同时出现四个Candidate拉票，各自的票数为2、3、1、3，没有任何节点的票数满足“半数以上”这个条件，因此本轮term不会有Leader产生：

Raft的一轮任期只会存在一个Leader，当出现票数过于分散的场景时，允许一轮没有Leader的term存在，经过一定时间的推移后，整个集群会自动进入下一轮选举。当然，关于如何推进到下一轮选举，下面详细聊聊。

2.2、Raft选举过程

我们先从集群启动开始，对Raft几种领导者选举过程进行展开，为了便于理解，这里用到了一个Raft动画网站，大家感兴趣可以自行点开探索。

2.2.1、集群启动选举过程

先看下图：

上图是由S1~S5五个节点组成的集群，大家会发现每个圆圈中间有个数字1，它代表着当前的term编号；其次，还可以发现，每个圆圈周围都有不规则的“圆形进度条”，这则对应着前面所说的随机计时器！

因为目前刚刚启动，不存在Leader节点，所以集群内不会有任何节点发送心跳包。当集群节点的进度条走完时，如果还未收到心跳，它就会认为Leader离线，而后转变成Candidate节点，投自己一票并开始拉票。Raft为不同节点的计时器，其倒计时数值加入了一定的随机性，从而避免多个节点一起拉票造成票数分散，集群迟迟无法选出Leader的情况。

上图中，S2节点的倒计时最短，它会成为第一个发现Leader离线、并发起拉票的节点，如下：

S2节点发现Leader离线后会开始拉票，来看图中的几种变化：首先S2节点转变了颜色，意味着角色从Follower转变成了Candidate；其次，S2中间的数值从1变为2，代表S2推动了一轮新选举，集群进入第二轮term；同时，S2内部出现了五个小圈，这代表集群各节点的投票状态，其中有一个全黑的小圈则是自己的一票；最后，S2发出四个绿色箭头，这就是发往其他节点的拉票请求。

具体的过程算法过程，就是S2发现领导者离线，先从追随者转变为候选人，接着自增自身的任期编号，然后投自己一票，最后向集群其他节点发出RequestVote-RPC，在该RPC对应的数据包里，会携带S2自增后的任期编号（2）。

随着拉票的RPC到达S3节点，S3节点会先对比RPC里携带的任期编号，如果比自身的编号要大，说明发出RPC的S2节点，其任期要比自己新，S3就会将自己的票投给S2，同时将自身的任期编号更新成2，并重置自己的计时器（再次获取一个固定范围内的随机超时时间）。

尽管S5的投票还未抵达S2，但当S2收到半数节点以上的投票后，就说明它获得了大多数节点的“拥戴”。观察上图，S2的名字变为红色，说明它从Candidate转变成了Leader节点；同时，它又发出了四个橙色箭头，这就是成为Leader后发出的心跳包，S2会依靠心跳维持自己的领导地位，避免其余节点再次开启新一轮选举。

好了，上面便是集群启动后，第一轮选举的正常流程，接着再探讨两个细节问题：

• S2的拉票请求未到达某个节点（如S4）时，S4也感知到Leader掉线发起选举怎么办？
• S2发出拉票请求后立马宕机，或S2收到部分节点的票数后宕机怎么办？

细节一：多个节点同时发起选举怎么办？

先看第一个问题，各节点的计数器都存在随机性，但也无法避免两个相邻的随机时间产生，如S1=51ms、S2=50ms。在这种情况下，S2会率先感知到Leader离线，在其一毫秒后，S1也会感知到Leader离线，两者感知到Leader离线的时间很接近。因此，在S2拉票请求抵达S1之前，S1也有可能变为Candidate开始拉票，这时谁会成为Leader呢？答案是不确定，需要看谁的RPC先抵达其余节点。

其他节点在投票时，因为会先对比自身的任期号，如果RPC携带的编号比自己大，就会更新自身的任期号，并把票投给对应的节点。比如S2的请求先到S5，S5对比发现自己小，就会把任期号从1变成2，然后给S2投票。随后，S1的拉票请求也来到S5，这时对比S1携带的编号（2），发现自身编号不比它小，为此就会忽略S1的拉票请求。

结合“半数节点以上的票选”这个条件，目前集群总共五个节点，S1、S2双方各自持有自身的票数，而剩下的S3、S4、S5，要么投给S1、要么投给S3。由于只剩下了三票，只有S1、S2两个候选人，笛卡尔积的结果也只能是0:3、3:0、1:2、2:1，不管是哪种结果，加上S1、S2自身持有的一票，最终都能满足“半数以上”这个条件，反正总会有一个节点胜出。

PS：现在大家应该明白为何集群节点数都推荐奇数了吧？因为节点数量为奇数的集群，在同一轮选举出现两个候选人的情况下，可以避免相互僵持的局面发生，保证一轮就能选出Leader节点。当然，如果出现两个以上的候选人，还是有可能因为票数过于分散，从而没有任何节点胜出，迫不得已开启新一轮选举。

细节二：节点发起选举后宕机怎么办？

好了，再来看第二个问题，S2开始拉票后、未正式成为Leader前宕机咋办？其实没关系，大家还记得节点投票的动作嘛？先更新任期编号，再给对方投票，然后再次获取一个固定范围内的随机超时时间，重置自己的计时器！

因为投票后会刷新自己的计时器，如果节点投票后，新的一轮倒计时结束，还未收到来自Leader的心跳，意味着前面拉票的节点已经掉线，第一个感知到此现象的节点，又会率先开启新的一轮选举。将此说法套入前面的案例中，假设S2发出拉票RPC后就宕机，S5率先感知到S2掉线，于是它发起新一轮选举，请问对应的term编号是几？

答案是3，因为当S5投票给S2后，就会将自身的任期编号变成拉票RPC中的2，如果发起新的一轮选举，任期号是在自身编号的基础上+1，所以S5这轮选举对应的任期则为3。

至此，集群启动后的第一轮选举过程，包括Raft的大致选举流程就阐述完毕了，下面看看后续Leader掉线后的选举过程。

2.2.2、Leader掉线选举过程

当集群启动选出Leader后，正常情况下，该Leader节点会持续发送心跳维持自己的领导者地位，可天有不测风云，谁也无法保障Leader节点一直健康，比如运行期间Leader所在的机器发生故障，又或者所在的分区网络出现问题，这时就需要选出新的Leader继续带领集群！

还是原来的问题，运行期间Follower节点如何感知到Leader掉线？其实这个问题和上阶段的细节二类似，Follower节点除开在投票后会重置自己的计时器之外，在收到领导者心跳RPC后亦是如此！

如上图所示，左图是Leader节点S2向其余节点发出心跳，右图是Follower节点回应S2的心跳包，注意观察S1、S3、S4、S5周边的进度条变化，大家可明显观察出被重置了！基于此特性，当Follower节点回复一次心跳后，计数器走完还未收到下一次心跳，这时对应的节点就会认为Leader掉线，从而发起新一轮的选举。

Raft动画网站概述

为了模拟运行期间Leader宕机的场景，可以借助前面所说的Raft动画网站，这里可以快速介绍一下，图中总共四块区域，左上的几个圆圈区域，代表组成集群的节点；右边的方块区域，代表选举和日志复制的状态（后续会用到）。下面两根进度条，第一根是时间回溯，可以拖拽来回放集群的“历史”；第二根是时速控制，可以拖拽来控制时间的倍速（快或慢）。

同时，在集群节点上右键，还会出现一个选项列表，对应着有五个功能：

• stop：让选中的节点立马宕机，用于模拟节点发生故障；
• resume：重置选中节点的计时器（重新获取指定范围内的超时时间）；
• restart：重启选中的节点；
• time out：让选中的节点其计时器立马跑完。用于模拟超时；
• request：模拟客户端向节点发出操作请求（适用于Leader节点）。

好了，大概对此网站的功能有基本认知后，下面一起来用它模拟运行期间的各种问题。

运行期间Leader掉线

左图是通过stop手动模拟S2宕机，宕机后S2不再会发出心跳，于是，随着时间推移，S5节点率先超时，此时就会将term编号自增到3，发起新一轮的选举过程：

S3发出的拉票RPC，由于携带着最大的任期编号，不出意外，S5成为了新Leader接替了之前S2的工作。看完之前的内容后，这个过程大家应该都能理解，这里不做过多展开，下面看看其他情况。

旧Leader节点复活

S2宕机、S5经过一轮选举后，成为集群内当之无愧的新Leader，可是S2掉线时，是带着Leader身份宕机的，如果旧主S2节点此时“复活”，它会不会与S5展开一场“夺嫡大戏”呢？我们来重启S2（restart）模拟一下：

观察上图，答案很显然，旧主S2成为了新主S5的追随者！Why？还记得之前说到的RPC嘛？每个节点在发出RPC时，都会携带自身的任期编号。上面左图中，S5发出心跳会带上自己的编号3，当旧主S2收到心跳后，一对比自身的编号，发现自己是2，就会认识到自己处于“过期的Term”，于是，就会将自身编号改为对方的编号，并改变身份成为对方的追随者。

PS：其实运行过程中还会有许多其他状况，比如Leader如果在发出心跳后，由于某个节点网络较差，导致接收心跳包出现延迟，从而导致自己的计时器走完，然后发起一轮新选举怎么办？又好比由五个节点组成的集群，在宕机三个的情况下，还能否正常工作及选出新Leader？这些问题靠前面的知识很难讲明白，因此暂时不聊，放到后面讲述。

2.3、Raft选举小结

经过前面两个阶段，我们分析了多种选举的状态，可不管怎么说，一轮选举的核心就两点：一是发现Leader离线，二是票选出新Leader。当一个节点开始拉票后，能够出现的结果就三种：

• 胜出：收到大多数节点的投票，成为新Leader；
• 平局：多个节点一起拉票，导致票数分散，开启下一轮选举；
• 失败：在自己之前有其他节点成为了新Leader，收到对方RPC后转变成追随者。

理解这三种情况，其实就不难理解Raft算法的领导者选举过程了，接着来看看日志复制。

三、Raft日志复制（Log Replication）

Raft是一种强Leader型的一致性算法，上阶段聊到的领导者选举，就是为了让分布式集群选出一个节点来担任集群的领导者。当Leader节点上任后，除开要定期向集群发出心跳外，更重要是承接并处理客户端的操作，然后将其同步给集群其他Follower节点。

最初曾提到，Raft算法向Follower节点同步数据依靠状态机实现，集群启动时，所有节点的数据（状态机）都处于一致，随着集群持续运行，所有节点经过同样的操作后，最终的数据（状态机）也一定能够达成一致，而这个过程就是所谓的同步状态机。

为了实现同步状态机，Leader会把所有客户端的操作（一般泛指写操作），封装成Log并加入自己的日志序列，然后再将Log同步给所有Follower节点。因为Log决定着集群的一致性，所以Raft只允许日志从Leader流向Follower节点，从而避免Paxos那种并发提案冲突造成的不一致现象。

PS：Raft中Leader具备绝对的统治力，这种模式被成为Strong Leader。

日志只能从Leader流向Follower，这会引发一个新的问题：Raft中的领导者随时可能变更，客户端如何知道Leader是谁？方案有好几种：

• ①轮询方案：客户端每次执行写操作时，遍历所有节点，能操作成功就是Leader；
• ②重定向方案：集群实现重定向方案，当操作发到Follower时，就重定向到最新的Leader；
• ③健康检查方案：客户端定期向集群发起一次探测，在客户端维护最新的Leader地址。

这三种方案究竟用哪种？这取决于不同的技术栈，Raft作为分布式系统的基石，并未对此进行限制。好了，下面进入正题，来聊聊日志复制。

3.1、日志复制过程

Leader负责承接所有客户端的操作，而后会封装成日志同步给其余节点，先来看张流程图：

如上图所示，当一个写操作抵达S2（Leader）后，S2会将该操作封装成Log-Entry（日志条目），并加入到自身的日志序列，然后会通过AppendEntries-RPC发往集群其余节点，其他节点收到RPC后，也会将Log加入到各自的日志序列，同时给Leader返回响应。

当Leader收到集群大多数节点的响应后，意味着客户端本次操作对应的Log已同步至大部分节点，于是，Leader会将该日志应用（Apply）到自身的状态机，即把数据写入到当前节点，最后身为领导者的S2就会向客户端返回“操作成功”。

上述即是完整的日志复制流程，很简单对吧？随着时间推移，整个集群所有节点的日志序列，就会变为成这样：

先来简单解释下图中的每个Log，前面说到，客户端的操作会被封装成Log-Entry，但Log除开包含客户端的操作外，还会包含当前的任期编号，以及一个在日志序列里唯一的索引下标（日志号）。图中方块里的数字，就代表是对应Log所处的任期（图中颜色相同的日志任期也相同），同理，既然多个日志的任期号相同，说明这些日志都由同一个Leader产生。

PS：通过任期号+日志下标，可以表示图中任何一个日志，如term3、index6，即代表a←1这个操作。

将目光集中到最下面的committed Entries（已提交日志），这是什么含义？诸位回想下前面的日志复制流程：当Log同步给大多数Follower节点后，Leader会将对应的日志应用于自身状态机，接着向客户端返回操作成功，而这些成功返回的客户端操作，对应的日志则视为“已提交日志”，还记得事务ACID原则里的持久性吗？

事务一旦被提交，它将永远生效，即使系统发生故障、出现宕机，也不会影响已提交的事务。

同理，Raft中已提交过的日志也具备持久性，Raft可以保证提交过的日志永不丢失（即提交的日志一定会被所有节点Apply），不过如何实现的，会在后面的安全性章节讲述，这里看下，为何图中最后term5、index12这条日志未提交？原因很简单，因为它还未复制到大多数节点，所以无法提交（所谓的提交，即是指Leader将日志应用到状态机）。

综上，在Raft协议中，如果客户端想要成功完成一个操作，则至少需要等到大多数节点成功同步日志、且领导者节点成功将日志Apply。不过值得注意的是，日志同步给大多数Follower节点后，Follower并没有立刻将日志应用于状态机，为啥？因为Follower无法确定当前的Log，是否已经同步给大多数节点。

集群中唯一能确认Log是否可提交的节点是Leader，因此，Follower节点必须接收到Leader的通知后，才能将前面同步的Log应用于状态机（commit），可Leader何时会告知Follower节点可以提交日志呢？为了更好的说明该问题，下面依旧基于之前的动画网站，模拟演示Raft集群同步日志的全流程。

3.2、Raft日志复制动画过程

上图是一个刚启动的Raft集群，目前的Leader节点为S5，首先我们通过request模拟客户端发起操作：

当请求到达S5后，大家会发现右侧的表格多出了一个蓝色方块，该方块则应着一个Log，中间的2代表当前集群的Term，为此，此日志可以表示为term2、index1。观察下来，会发现该方块位于S5这一栏，这代表着此日志已加入到S5的日志序列，按照之前讲述的流程，接下来S5会向其余节点发起AppendEntries RPC：

S3率先收到了追加日志条目的RPC，于是，S3也会将对应的日志加入到自己的日志序列里，接着给S5返回响应，随着时间推移，其他节点也会陆续收到RPC，将日志追加到各自的序列并返回响应：

上图中，S1~S4节点都已成功响应S5，可值得注意的是，此时图中五个蓝色方块，其边框都为黑色虚线，意味着本次日志只是追加到了日志序列，并未应用于状态机（未Commit）！何时会提交呢？

如上图所示，S1、S2的响应还未抵达S5，可S3、S4的响应已经被S5收到了，S3、S4再加上S5自身，数量已经满足集群大多数的要求，此时身为领导者的S5就能确认：本次客户端操作对应的日志条目已成功复制给大多数节点，本条日志可以应用状态机，所以，图中S5对应方块边框，变成了黑色实线，意味着S5上的日志已提交。

从这里就能看到前面说的问题，Leader上提交日志后，S3、S4并未提交，何时提交呢？

在《领导者选举》章节提到过，Leader为了维持其领导者地位，正常运行期间会不断发出心跳包，而在Leader发出的心跳RPC中，就会塞进一个额外的信息：Leader上已应用于状态机的日志索引，即S5节点已提交（Committed）的日志索引，图中S5发出的心跳包，其AppendEntriesRPC对应的伪结构体如下：

public class AppendEntriesBody {
    // 任期编号
    private Integer termId;

    // 提交的日志索引（下标）
    private Integer commitIndex;

    // 省略其他字段……
}

当然，实际AppendEntriesRPC的结构体并不会这么简单，具体会在后面的章节进行展开。好了，继续往下看：

当S5发出的心跳包，被S1~S4节点收到后，S1~S4会对比RPC中携带的commitIndex，这时就能得知前面复制的日志，究竟能否应用于状态机。案例中，S5心跳包的数据可以简述为term2、commitIndex1，S1~S4发现Leader已经提交了索引为1的日志，同样会陆续提交前面追加到各自序列中的日志（图中各节点的方块边框都变为了实线）。

综上，我们完整阐述了Raft日志复制的完整流程，也解答了上面提出的疑惑，简单总结下，其实整体流程有点类似于两阶段提交，第一阶段将客户端的操作先封装成Log，而后同步给所有节点并追加到序列；第二阶段再让所有Follower节点Apply前面复制的日志。

3.3、Raft的一致性保证

上阶段通过动画演示了Raft日志复制的全流程，通过这套机制，在集群通信正常、所有节点不出意外的前提下，就能保证所有节点最终的的日志序列与状态机一致且完整。在此基础上，Raft保证不同节点的日志序列中、term，index相同的日志，存储的操作指令也完全相同，即S1节点的term1，index1存储着x←1，S2、S3节点的日志序列，相同位置一定也存储着该指令。

PS：Raft协议中，Leader针对同一个Index只能创建一条日志，并且永远不允许修改，意味着term+index可以形成“全局唯一”的特性。

不过网络总是不可靠的，不同节点间的网络状况不同，任意时刻、任意节点都可能会发生延迟、丢包、故障、分区、乱序等问题，来看个抖动重发造成的乱序场景：

上图中，客户端先向身为Leader的S2节点，发出了x←1的操作，接着又发出了一个x←2的操作，按照前面的推导，S2会按先后顺序、几乎“同时”处理者两个客户端操作（因为Raft支持多决策），接着向其他节点同步对应的日志，假设S2和S5之间网络出现抖动，导致x←1对应的日志重发，这意味着x←2会比x←1的日志先抵达S5。

此时注意观察上图中各节点的日志序列，S5的日志序列就与其他节点的日志序列存在差异，其index为2的位置，存放的是x←1，这代表最终应用到状态机里的x=1！这时，当客户端从集群读取x，S1~S4读到的为2，而S5读到的则为1，造成数据的不一致现象。

为了解决这类问题，Raft要求Leader在发出AppendEntries-RPC时，需要额外附带上一条日志的term，index，如果Follower收到RPC后，在本地找不到相同的term，index，则会拒绝接收这次RPC！套进前面的例子再来分析。

S2先处理x←1操作，在此之前没有日志，所以上一条日志的信息为空，对应的RPC伪信息如下：

{
    "previousTerm": null,
    "previousIndex": null,
    ……
}

接着S2处理x←2操作，Leader对应的序列中，在此操作之前有个x←1，所以对应的RPC类似这样：

{
    "previousTerm": 2,
    "previousIndex": 1,
    ……
}

在这种情况下，如果S5先收到x←2对应的RPC，在本地序列找不到term2，index1这个日志，就能得知该日志顺序不对，为此会拒绝掉本次RPC，并返回自己需要的日志（term2，index1）。等到x←1对应的日志抵达后，才会接受对应追加日志条目的PRC。

PS：这种机制被成为一致性检查机制，也可以用来帮助掉线恢复后的节点，补全断线期间错过的日志（细节会在后续展开）。

通过这种机制，只要Follower没有陷入故障状态，通过不断归纳验证，就一定能和Leader的日志序列保持一致，因此，Raft也能保证：不同节点日志序列的某个日志（term，index）相同，那么在此之前的所有日志也全部相同，比如S3的term2、index78是a←5，S2也有term2、index78这个日志，那么它们的值肯定一样，并且前面77个日志也完全相同！

四、Raft小结

好了，到目前为止，我们大致将Raft分解出的三个核心子问题讲述完毕，但这仅仅只是Raft的基础知识，如果只是这样，其实Raft并不能被称之为一致性算法，因为它还有很多可能造成不一致问题出现的风险，比如同步乱序、集群脑裂等。不过由于本文篇幅较长，剩下的内容放在下篇中进下阐述：

• 《一致性算法下篇：一文从根上儿理解大名鼎鼎的Raft共识算法！》

所有文章已开始陆续同步至微信公众号：竹子爱熊猫，想在微信上便捷阅读的小伙伴可搜索关注~

原文链接: https://juejin.cn/post/7365833245956866083