菜鸟笔记
提升您的技术认知

分布式一致性算法Raft

阅读 : 85

前言

单点系统的数据是天然一致的,但为了避免单点故障问题,我们引入了分布式系统。

将数据以副本的形式保存在多个节点上,可以有效避免单点故障造成的服务不可用以及数据丢失的情况。

但如何去保证多个节点的一致性呢,如何达成分布式共识,Raft算法就应运而生了。

现在市面上有很多对Raft的实现,比如Etcd、Consul等等。

本文主要带大家了解一下Raft中的Leader选举与日志复制流程

Raft节点的角色划分与任期

在Raft中,有以下三种角色:

Follower 跟随者

所有节点的初始状态,内部都会有一个超时时间。对于每一个Follower,其超时时间是随机的。

这个超时时间,规定了在倒计时结束后仍然收不到Leader的心跳,Follower就会转变为Candidate。

为什么每个Follower的超时时间是随机的,改成一样的可以吗?

不可以,相同的超时时间会造成多个Follower同时转变为Candidate,选票被瓜分,导致获取不到半数以上的选票,就需要进行新一轮的选举,效率低下。

Candidate 候选者

Follower在转变为Candidate后,超时时间重置,倒计时结束时就会向其他节点拉取选票。

如果能获得半数以上(包含自己投给自己的)的选票,则当选为Leader,这个过程就叫做Leader选举

为什么在转变后,会重置超时时间,直接进行Leader选举不行吗?

Follower的超时时间是随机的,但不保证不会随机到相同的时间。那么此时再进行一次倒计时,可在大概率上避免选票被瓜分的情况。

为什么要获得半数以上的选票,获得一半选票行不行?

显然是不行的,因为这样在极端情况下会在一个集群中选举两个Leader出来,产生脑裂问题。

Leader 领导者

Raft集群通过Leader与客户端进行交互,Leader不断处理写请求与发送心跳给Follower。

Follower在收到Leader的心跳后,其超时时间会重置,即重新开始倒计时。

Term 任期

无论当前节点处于什么角色,内部都会有一个任期编号,初始值为0。

当Follower转变为Candidate时,任期编号将会自增。

每个节点在当前的任期内,只能投出一份选票。

任期有什么用呢?

  • 高任期的节点向低任期的节点拉取选票时,低任期的节点将会把自己的任期修改为高任期,因此来实现任期的统一。
  • Leader宕机恢复后发现自己的任期比其他节点小,则自动转变为Follower。是因为任期的增加,表明原Leader宕机期间已经发生了新的选举,需要以新的选举结果为准。
  • 低任期的节点向高任期的节点拉取选票时,高任期的节点将直接拒绝。

角色之间的转变过程图

Leader选举过程

假设当前Raft集群共有5个节点,初始状态都为Follower,任期也都是0。

图中F代表Follower,C代表Candidate,L代表Leader,T表示任期编号。

F1的超时时间最短,因此F1转变为C1,重置超时时间,任期加1。

当C1重置完超时时间,倒计时结束后,将会向其他节点拉取选票。

 

其他节点投出自己的选票,并将自己的任期加1。

由于C1得到半数以上的选票,则转变为Leader,并不断向其他节点发送心跳。

Leader宕机后恢复

在某一时刻,Leader由于故障宕机,此时Follower收不到心跳消息。

F3的超时时间最短,最先转变为Candidate,此时任期加1,并向其他节点请求投票。

 

其余节点投出选票,任期加1。此时,C3得到半数以上的票,转变为Leader,并向其他节点发送心跳。

L1宕机恢复后,会向各个节点发送一个当前任期的请求。

L1发现其他的节点的任期比自己大,于是主动降级为Follower并同步任期,接收来自L3的心跳信息。

如何解决脑裂问题?

假如在一个集群或系统中,同时出现1个以上的Leader,这样的现象就是脑裂。

多个Leader会向Follower同时发号施令,Follower不清楚该接受哪个Leader的指令,最终会造成内部混乱。

在没有出现网络分区的情况下,Raft通过以下两条约束来避免脑裂:

  • 每个节点在一个任期内,只能投票一次。
  • 获得半数以上的选票,才能成为Leader。

在固定的选票下,获得半数以上选票的才能成为Leader,有效避免了脑裂问题。

如果在现网络分区的情况呢?

先说结论,其实和Leader宕机恢复很像,低任期的Leader在发现有高任期的Leader后,会主动降级为Follower。

一开始,集群内部只有一个Leader。后来发生了网络分区,L1无法向F3、F4与F5发送心跳。

F3、F4与F5将会开启新一轮选举,接着F4获得当前所有的选票,即3份,为半数以上,当选为新的Leader。

当网络分区结束后,集群内部会短暂的出现两个Leader的情况。

L1发现L4的任期比自己的大,于是主动降级为Follower,并接收来自L4的心跳。

日志复制

我们知道,只有Leader能处理外部客户端的数据的增删改操作,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的日志一致了。