单点系统的数据是天然一致的,但为了避免单点故障问题,我们引入了分布式系统。
将数据以副本的形式保存在多个节点上,可以有效避免单点故障造成的服务不可用以及数据丢失的情况。
但如何去保证多个节点的一致性呢,如何达成分布式共识,Raft算法就应运而生了。
现在市面上有很多对Raft的实现,比如Etcd、Consul等等。
本文主要带大家了解一下Raft中的Leader选举与日志复制流程
在Raft中,有以下三种角色:
所有节点的初始状态,内部都会有一个超时时间。对于每一个Follower,其超时时间是随机的。
这个超时时间,规定了在倒计时结束后仍然收不到Leader的心跳,Follower就会转变为Candidate。
为什么每个Follower的超时时间是随机的,改成一样的可以吗?
不可以,相同的超时时间会造成多个Follower同时转变为Candidate,选票被瓜分,导致获取不到半数以上的选票,就需要进行新一轮的选举,效率低下。
Follower在转变为Candidate后,超时时间重置,倒计时结束时就会向其他节点拉取选票。
如果能获得半数以上(包含自己投给自己的)的选票,则当选为Leader,这个过程就叫做Leader选举。
为什么在转变后,会重置超时时间,直接进行Leader选举不行吗?
Follower的超时时间是随机的,但不保证不会随机到相同的时间。那么此时再进行一次倒计时,可在大概率上避免选票被瓜分的情况。
为什么要获得半数以上的选票,获得一半选票行不行?
显然是不行的,因为这样在极端情况下会在一个集群中选举两个Leader出来,产生脑裂问题。
Raft集群通过Leader与客户端进行交互,Leader不断处理写请求与发送心跳给Follower。
Follower在收到Leader的心跳后,其超时时间会重置,即重新开始倒计时。
无论当前节点处于什么角色,内部都会有一个任期编号,初始值为0。
当Follower转变为Candidate时,任期编号将会自增。
每个节点在当前的任期内,只能投出一份选票。
任期有什么用呢?
假设当前Raft集群共有5个节点,初始状态都为Follower,任期也都是0。
图中F代表Follower,C代表Candidate,L代表Leader,T表示任期编号。
F1的超时时间最短,因此F1转变为C1,重置超时时间,任期加1。
当C1重置完超时时间,倒计时结束后,将会向其他节点拉取选票。
其他节点投出自己的选票,并将自己的任期加1。
由于C1得到半数以上的选票,则转变为Leader,并不断向其他节点发送心跳。
在某一时刻,Leader由于故障宕机,此时Follower收不到心跳消息。
F3的超时时间最短,最先转变为Candidate,此时任期加1,并向其他节点请求投票。
其余节点投出选票,任期加1。此时,C3得到半数以上的票,转变为Leader,并向其他节点发送心跳。
L1宕机恢复后,会向各个节点发送一个当前任期的请求。
L1发现其他的节点的任期比自己大,于是主动降级为Follower并同步任期,接收来自L3的心跳信息。
假如在一个集群或系统中,同时出现1个以上的Leader,这样的现象就是脑裂。
多个Leader会向Follower同时发号施令,Follower不清楚该接受哪个Leader的指令,最终会造成内部混乱。
在没有出现网络分区的情况下,Raft通过以下两条约束来避免脑裂:
在固定的选票下,获得半数以上选票的才能成为Leader,有效避免了脑裂问题。
如果在现网络分区的情况呢?
先说结论,其实和Leader宕机恢复很像,低任期的Leader在发现有高任期的Leader后,会主动降级为Follower。
一开始,集群内部只有一个Leader。后来发生了网络分区,L1无法向F3、F4与F5发送心跳。
F3、F4与F5将会开启新一轮选举,接着F4获得当前所有的选票,即3份,为半数以上,当选为新的Leader。
当网络分区结束后,集群内部会短暂的出现两个Leader的情况。
L1发现L4的任期比自己的大,于是主动降级为Follower,并接收来自L4的心跳。
我们知道,只有Leader能处理外部客户端的数据的增删改操作,Leader会将顺序接收到的操作指令序列化成日志,之后节点上的某个程序(有些文章称之为状态机)执行日志中的命令,只要各个节点上的日志相同,则程序执行后产生的结果就相同。
那么日志具有怎样的一个结构呢?
一份日志主要包含以下信息:
因此Raft集群的重点在于Leader需要将自己的日志同步到Follower节点,以保证整个Raft集群的数据一致性。
这样我们在访问任意一个节点时,都能获得相同的返回数据。
一个简要的日志复制过程如下:
首先,经过一轮选举后,产生了一个Leader。
当L1接收到客户端的数据修改的指令后,首先会append到自己的本地日志中,状态为未提交,之后会向Follower节点发起append请求。
当Follower节点接收到append请求后,同样也会append到自己的本地日志中,状态为未提交。
当半数以上的Follower写入成功后,Leader会将日志提交,并应用到状态机中执行,同时回应客户端修改成功。
最后Leader通知Follower节点将日志提交
在这个时候,整个Raft集群实现了分布式的数据一致性。
我们整理一下日志复制的过程:
上图描述的是一个在理想状态下的复制过程,在实际场景中,可能会出现Leader宕机、网络分区的情况,这些情况会导致日志的不一致,那么Raft是怎么保证日志的一致性的呢?
Raft集群是一个strong leader的系统,因此会强制Follower复制Leader的日志。
Leader会在心跳信息中,将已提交的日志数据不断发送给Follower,复制请求中包含上一条日志的索引值与任期(记为L.pre.index与L.pre.term),当前日志的索引值与任期(记为L.cur.index与L.cur.term)。
Follower在收到复制请求后,先查找自身L.pre.index索引值的日志term,是否等于L.pre.term,如果等于,则将L.cur.index与L.cur.term追加到本地日志中,并返回复制成功。
如果Follower中L.pre.index索引值的日志term,不等于L.pre.term,则返回复制失败。此时Leader会将更前面一条的日志发送过来,如果依然复制失败,则继续往前,一直从后往前找到第一个共同的日志。并从这里开始往后复制,使得Follower与Leader的日志一致。
举个例子:
假设该集群在运行一段时间后,Leader与其中一个Follower的日志情况如下:
1、此时Leader需要Follower复制索引为5的日志,于是将索引4和5的日志一起发送给了Follower。
2、Follower发现索引4的日志,任期和Leader日志不一致,因此返回复制失败。
3、Leader发现复制失败后,将索引3和4的日志一起发送给了Follower。
4、Follower发现索引3的日志,任期是一致的,这就找到了和Leader共同的日志项,于是覆盖索引4的本地日志,返回复制成功。
5、Leader发现复制成功,便不再往前递归寻找。
6、下一轮的心跳信息中,Leader将索引4和5的日志一起发送给了Follower。
7、Follower比对发现索引4的日志一致,于是将索引5的Leader日志追加到本地日志中,此时Leader与Follower的日志一致了。
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/qq_33591903/article/details/121002970
内容来源于网络,如有侵权,请联系作者删除!