点击上方疾风先生可以订阅哦
本文主要以分析Raft算法核心原理流程为主,简述Raft算法运作流程,分别从Raft基础,核心原理以及细节问题出发作一个归纳性总结,如想深入Raft算法可以查看Raft算法论文,关注公众号回复“raft”即可获取Raft算法论文.
Raft算法简述
Raft算法是一种用于管理Replicated Log的共识算法,其算法结果与效率与Multi-Paxos一致,但是在算法的设计结构上与Paxos算法是不同的,Raft算法更加便于理解和实现,主要有以下两点:
Raft算法核心原理
所有的键值服务节点都属于follower节点,在Raft算法中,follower节点会存在两个核心属性,即等待leader节点心跳检测的超时时间timeout以及任期编号term.在初始状态下,键值服务集群不存在leader节点,此时任期term为0,同时为了保证集群每个follower节点都能够有机会发起投票以及避免投票冲突带来的性能问题,于是采取心跳检测的超时时间作为随机数.即如下:
在上述集群的初始状态中,我们可以看到followerA节点等待leader节点的ping心跳率先超时,于是followerA节点成为候选节点Candidate,同时默认为自己的任期term进行+1的投票,此时节点A会更新当前的任期编号term为1(初始状态为0),接着再向集群服务节点B以及C发起RPC投票请求,即如下:
当候选服务节点A发起RPC投票请求的时候,会在当前的服务节点设置一个等待选举结果的随机超时时间timeout,那么存在两种情况:
当候选节点A在超时的时间内获得到集群半数以上的节点给予的投票响应,于是会晋升成为leader节点,并周期性地向follower节点发起类似ping的心跳响应,并在当前任期内维持ping心跳检测的超时时间timeout,即如下:
日志项属性
由上图可知,日志实体(log Entry)主要包含以下几个属性:
Raft算法的日志复制是基于优化之后的2PC(减少一半的消息往返)提交来实现客户端事务操作的共识与数据的一致性,其具体过程如下:
set x=10
,即:RPC-AppendEntries&Heartbeat
会携带当前最大的且即将提交的index
到follower节点,follower节点会进行一致性检查流程并将日志项提交到本地状态机以保证与leader节点的日志数据一致.即:最后,关于Raft算法的日志复制,可以类比数据库的主从复制架构来思考,上述的提交日志可以理解为binlog或者是oplog,那么每次发起的RPC日志复制抑或是心跳检测都会携带日志最大且即将提交的索引值index,通过binlog或者是oplog将数据更新到节点的状态机上.
一致性检测原理
假设当前Raft服务集群节点的log以及对应的logEntry如下:
在上述图中,我们看到leader节点与follower节点的日志数据存在不一致,我们知道Raft算法是属于强leader模型,一切以“leader”为主,因此日志复制也不例外,一旦出现不一致,那么follower节点会进行一致性检查并以leader发送的RPC日志为主将不一致性的数据强制更新为与leader节点日志一致,而对于leader节点的日志是不会覆盖和删除自己的日志记录.也就是说对于raft算法的一致性检查原理主要包含以下步骤:
一致性检查流程
以上面的日志记录为例,leader节点当前的索引值为8,而follower节点A与follower节点B索引值分别为5和8,这个时候假设leader节点向集群follower节点通过RPC发送新的日志记录抑或是心跳消息.此时follower节点A与B将会进行一致性检查.
上述不论是发送RPC复制日志项还是心跳消息,在follower节点B以及C中由于日志属性不匹配抑或是日志项不存在而拒绝当前index=9
或者index=8
的日志项更新,于是对于leader节点将向后递减重新发送新的RPC复制日志到follower节点,即:
至此,在有限的时间内leader节点会将其日志复制到follower节点来保证整个Raft集群的日志数据一致性.
小结
index=rpcIndex
从上面我们可以看到在一个Raft集群服务中,如果leader节点发生不可用,那么剩下的follower节点将会重新进行选举,假设此时选举B作为leader节点,那么当原有的leader节点恢复正常的时候,此时集群存在两个“leader”节点,如何解决?
从上述可以看到,在实现集群服务节点的扩容时,如果新加入的服务节点刚好碰上原有的集群服务发生网络分区,导致C与B,A节点失去联系,而在C节点恢复的时候与刚加入的服务节点D&E组成一个新的Raft集群(D&E与原有的服务节点属于同一个区域内);其次如果是新加入的两个节点与原有的服务节点不属在同一个区域,那么当前raft集群扩容就存在跨区域的集群,跨区域必然会存在网络不可靠的因素,因此一旦两个区域发生网络分区错误,那此时新区域下的D&E以及原有的区域集群节点分别组成了一个Raft集群,此时就会面临双leader节点问题.
从上述的问题分析中,我们都看到集群服务可能出现多个leader节点,这就违背了Raft算法的强leader且唯一性的特征,而对于Raft算法解决这类集群成员节点变更则是通过单节点变更来解决集群的“脑裂”问题.
在Raft算法的论文中关于集群成员节点的变更存在着一个集群的配置属性,即在了解单节点变更方式之前,我们需要对集群cluster的配置有一个基本的认知(与ES集群相似)
集群配置
在一个稳定的Raft集群服务中,存在着以下的一个leader以及两个follower节点,follower节点的配置需要从leader节点同步进行更新,于是在这里我们关注leader节点的配置即可,也就是整个集群的一份配置.对于ES集群而言,其配置信息如下:
上述的log/clusterName/nodes等信息组成一个集群的配置信息,也就是说Raft 算法要解决上述多leader节点的问题,其实是保障在集群配置变更时,集群能稳定运行,不会同时出现多个leader节点的集群配置.
引入集群配置的目的
因此Raft算法利用单节点变更的方式来实现自动化的配置更新以保证我们集群服务的强一致性.
单节点变更原理
解决成员变更分析
此时集群的配置由[A,B,C]变更为[B,C],同时配置中的部分属性数据也会发生变更,比如任期term以及log数据.
在现有的Raft集群中加入节点D,此时集群raft_cluster监听到节点D加入集群,此时leader节点更新集群的配置并向节点D同步日志数据log,最后更新集群配置之后再向Raft集群服务节点发起日志复制的RPC请求消息同步最新的集群配置信息从而保证Raft集群的强一致性.
集群脑裂
对于3&4问题,属于跨区域的集群的“脑裂”问题(ES集群也存在同样的问题)
如何解决集群脑裂问题
(n/2)+1
并且是在处于同一个区域下,即:Raft算法分析小结
通过上述可知,客户端client service多个节点发起事务操作提交到集群的leader节点,集群的leader服务节点通过共识模块来输出对应的数据值并记录变更日志log,同时发起日志复制到集群其他服务节点以便于同步变更操作并等待大多数节点的响应之后再持久化到本地的状态机,最后更新之后再返回给客户端响应,而集群服务的其他节点则通过新的日志复制RPC消息抑或是RPC心跳检测进行一致性校验然后更新到对应的状态机上.
简而言之,就是不同进程p对分别输入一组u的数据,通过相同的程序处理逻辑来保证其输出值最终都是v.即:
当Follower节点发现Raft集群leader节点不可用时就会推荐自己选举成为leader节点并发起投票选举,这个时候Follower节点成为Candidate节点,于是会自增加自己的任期Term并向Raft集群其他服务节点发起RPC通讯的投票请求,如果赢得超过半数投票请求,那么当前Follower节点就晋升成为leader节点.
我们知道Raft算法是属于强leader模型,所有的事务请求最终都会落到leader服务节点上,那么在Raft集群服务中只有leader节点的进程输入数据并通过leader节点的共识算法模块输出状态变更的记录值,并复制共识输出的变更记录log同步到Raft集群Follower节点.
Raft集群服务对外提供数据的读取始终保证一致性,即对Raft集群之外的服务,简称为客户端服务client service,client service多个节点node向Raft集群服务发起读取请求,那么要保证client service的每个节点node读取到请求数据都是一致的.
当Raft算法已经选举Leader节点之后,为了保证Raft集群中的数据一致性,Raft算法采取强制的Leader策略,将客户端的写入操作更新到leader节点的日志文件中,并以RPC通讯的方式复制到Raft集群的从服务节点中,从服务节点从操作日志来增量更新数据从而保证leader与follower节点数据的一致性.
当leader节点发起复制日志的RPC请求消息到Raft集群中各个follower节点,如果此时leader节点发生不可用,那么此时会有以下几种情况(前提是leader节点的日志已经写入成功,leader节点恢复之前):
其一follower节点大多数接收到复制日志的请求并执行成功;
其二follower节点只有少数接收到复制日志的请求并执行成功;
其三follower节点没有接收到复制日志的请求;
不论是上述哪种情况,leader节点发生不可用的时候,必然会重新选举一个具备日志完整性的follower节点作为新的leader节点,如果当前leader节点存在原有的log的记录(1&2的情况),会重新发起复制日志的RPC请求消息到集群服务的各个节点,如果大多数集群服务节点都响应成功那么就会在当前的leader节点将日志log应用到状态机并在下一个RPC日志复制抑或是心跳检测消息通知其他follower节点更新到状态机上;如果响应失败(机器不可用除外,需要更新集群配置,重新RPC日志复制),一般是一致性检查失败,于是会根据一致性流程强制更新数据并最终保证日志数据与leader节点一致;最后是follower节点上并没有先前leader的日志记录,那么对应的数据将会丢失,因为重新选举之后,当旧的leader节点恢复时,日志数据会根据一致性检查被强制更新为与新的leader节点日志一致,因此需要在客户端服务进行重试与幂等性操作保证数据不丢失.
leader节点会周期性向follower节点发起心跳检测(携带投票选举的Term),以避免follower节点成为候选节点进行投票选举.
Raft集群服务的follower节点在指定的时间内没有接收到leader节点的心跳检测消息,那么此时会认为leader节点不可用,会推荐自己成为候选节点并自增任期编号,同时发起leader选举.
follower节点成为candidate节点发起的leader选举,如果获得集群服务大多数服务节点的投票响应,那么当前follower节点就会成为leader节点
Raft集群通过每次选举产生新的leader,同时会对应新的Term,每一轮新Term都具备持续性,也就是说在一个任期Term内,只要是leader节点是可用的,那么就不会发生新的一轮选举,可用性是通过周期性检测来保证.
在一次选举中,每一个服务节点最多会对一个任期编号进行投票,并且按照先来先服务原则进行投票.即在发生选举过程中,可能存在两个或者多个候选节点向集群服务发起投票,Raft集群为了避免同时发生投票的碰撞,采取随机超时时间的心跳检测机制来进行投票,这个时候对于其中一个服务节点A,先接收到服务节点B且携带任期编号为v的投票请求并给予投票,此时服务节点C也携带任期编号为v投票请求到服务节点A,由于A节点先投票给B,于是返回给节点C当前已经没有选票,投票失败的响应.
日志完整性高的follower节点拒绝投票给日志完整性低的候选节点.假设现在Raft集群服务提交的日志log如下(其中包含日志索引logIndex,实体log包含任期编号term以及变更的指令):
现在Raft集群中各个节点以及日志复制情况如上,那么此时如果leader节点发生不可用,followers都具备成为leader节点,但是如果是一个日志索引下标logIndex=5
的候选节点向一个日志索引下标为logIndex=8
的follower节点发起投票请求,这个时候follower节点将会被拒绝,主要原因是后者的logIndex
更大,相对地,其日志完整性更高(可类比于kafka的ISR副本机制)
关于raft算法的论文,感兴趣的同学可以关注下面公众号并回复“raft”获取,最后感谢花时间阅读,如对你有用,欢迎转发或好看,谢谢!
你好,我是疾风先生,先后从事外企和互联网大厂的java和python工作,现以go语言开发为主, 记录并分享个人技术栈,欢迎关注我的公众号,致力于做一个有深度,有广度,有故事的工程师,欢迎成长的路上有你陪伴,关注后回复greek可添加私人微信,欢迎技术互动和交流,添加烦请注明姓名,谢谢!