1. 首页
  2. 后端

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

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

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

引言

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

在上篇文章里,对Paxos这个大多数一致性算法的“老祖宗”做了全面阐述,在上章最后,提到了Multi-Paxos这个变种算法,相较于Basic-PaxosMulti-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-PaxosProposer的思想,保证了运行期间内只会存在一个Leader节点,而且是强Leader模式,宁愿让系统没有Leader陷入瘫痪,也不允许出现脑裂现象,对外服务的任意时刻都只能存在一个Leader

RaftPaxos的设计理念相同,都是为了解决分布式系统的一致性问题,可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节点,从而将PaxosProposer角色固化在一个节点上,在运行期间内,只允许一个节点发出提案,剩余节点只能被动接受、学习提案,来看这张摘自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就会认为该节点已下线或陷入故障了。

Raft心跳

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

PS:一轮选举/一个term中,一个节点只能投出一票!

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

选举僵持

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

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

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

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

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

term

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

2.2、Raft选举过程

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

2.2.1、集群启动选举过程

先看下图:

集群启动

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

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

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

S2拉票

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

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

S3投票

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

S2胜出

尽管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的请求先到S5S5对比发现自己小,就会把任期号从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动画网站概述

Raft动画网站

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

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

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

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

运行期间Leader掉线

S2宕机

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

S5胜出

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

旧Leader节点复活

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

S2复活

观察上图,答案很显然,旧主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:RaftLeader具备绝对的统治力,这种模式被成为Strong Leader

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

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

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

3.1、日志复制过程

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

日志同步

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

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

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

日志序列

先来简单解释下图中的每个Log,前面说到,客户端的操作会被封装成Log-EntryLog除开包含客户端的操作外,还会包含当前的任期编号,以及一个在日志序列里唯一的索引下标(日志号)。图中方块里的数字,就代表是对应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集群

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

客户端请求Leader

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

RPC抵达S3

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

响应RPC

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

Leader提交

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

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

S5心跳

在《领导者选举》章节提到过,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、commitIndex1S1~S4发现Leader已经提交了索引为1的日志,同样会陆续提交前面追加到各自序列中的日志(图中各节点的方块边框都变为了实线)。

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

3.3、Raft的一致性保证

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

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

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

重发乱序

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

此时注意观察上图中各节点的日志序列,S5的日志序列就与其他节点的日志序列存在差异,其index2的位置,存放的是x←1,这代表最终应用到状态机里的x=1!这时,当客户端从集群读取xS1~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)相同,那么在此之前的所有日志也全部相同,比如S3term2、index78a←5S2也有term2、index78这个日志,那么它们的值肯定一样,并且前面77个日志也完全相同!

四、Raft小结

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

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

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

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

文章收集整理于网络,请勿商用,仅供个人学习使用,如有侵权,请联系作者删除,如若转载,请注明出处:http://www.cxyroad.com/16992.html

QR code