令人赞叹的分布式一致协议raft

Java框架

浏览数:179

2019-2-24

AD:资源代下载服务

# 引子

分布式一致协议是做什么的?很简单,就是让不同机器上的进程对某种状态达成一致的看法,从而能够协作完成各种任务。这个问题貌似很简单,其实是非常难以实现的,因为有太多不可控因素。机器会宕机,进程会死掉,网络会中断,网络包还可能发生错误,更让人受不了的,这些问题还可能频繁发生,循环往复。你说难不难?

尽管很难,但是解决方案已经有了,咱们今天来看的raft协议就是其中之一。

个人认为,学习raft协议最好的办法,就是自己提前想想达成分布式一致的各种挑战,自己思考一下有没有什么解决办法,哪些地方感觉很难,带着这些思考认识去学习raft协议,就有种向武林宗师请教的赶脚,协议中一些精巧的处理就好比大师的高言宏论,令人醍醐灌顶,茅塞顿开!

(思考中……)

那么,让我们开始学习吧!

#从一个例子开始

假设,我有三个server进程,分别称为s1,s2,s3,可以接收一个值,并存储起来。现在有一个client进程,称为c1,要将10这个值存到三个server进程中,假设c1已经将10这个值发送给三个server进程了,此时,我们要确保三个server进程都成功接收并存储了10这个值,这才算存储成功,如何确保这一点?这就是分布式一致协议要解决的问题,通俗点讲,就是让分布在不同机器上的s1,s2,s3有着一致的存储值。

#思考的起点

稍加思考,我们就可以找到一个很简单的办法,就是让所有收到10这个值并成功存储的server进程发送一个存储成功的信号给c1,当c1收到s1,s2,s3发回的信号后,就认为存储成功了,如果有一个server进程没回发信号,就让c1再发送一次10,直到收到信号。

这个方案简单但基本不能使用,因为有如下缺陷:

1,如果c1不是要server存储一个值,而是要它们把自己存储的值加10,假设s1收到这个请求,并执行了加10操作,也回发了成功信号,但是信号由于网络原因丢失了,那么,c1只能再发送一次加10操作给s1,这将引发s1两次执行加10操作,结果错误。也就是说,c1发给各个s进程的操作只能是幂等的,也就是重复执行结果相同的操作。

2,如果s1挂掉了,那么整个系统就不能用了,因为c1永远收不到s1发回的信号,也就永远无法确认成功,也就是可用性很差。

3,不优雅,存储作为一项服务,却需要client端自己确认存储成功,这个有点egg pain

# 把思路转向server端

以上,我们看到,要做到分布式一致不是那么简单的。

但我们不能放弃,进一步思考,可不可以在三个server进程上作文章呢。

分析一下我们的核心需求,是让三个server进程有一致的状态,那么我们可以把三个server进程看作一个整体,让它们其中一个作为主server进程,负责对外提供服务,其他的进程只要能够紧紧跟上主server进程的状态就可以了。

至此,我们已经走上正确的方向,raft协议正是这种思想的一个实现。

下面,我们就开始学习raft协议吧。

# raft协议的基本概念

Raft协议将server进程分成三类,分别是Leader, Candidate, Follower,一个server进程在某一时刻,只能是其中一种类型,但这不是固定的,不同的时刻,它可能拥有不同的类型,具体一个server进程的类型是如何改变的,后面会有解释,暂时按下不表。

此时,我们只需知道,把server进程分成三类,是为了让server进程便于达成一致。

#从系统启动开始

假设现在启动了s1,s2,s3三个进程,它们会首先做如下动作:

1,读取配置文件,三个进程读取的配置文件是一样的,配置文件中记录了该集群所有server进程的ip地址和端口,也就是集群成员的联系方式。

2,将自己的类型设为Follower,代码示意如下:

type=Follower

3,将term变量设为0

term=0

term怎么理解?

咱们不是刚开完十九大吗,十九大选举出了新一届的中央委员,政治局常委,党的总书记。这一届任期为五年。

term就类似于这里的“届”,每一届中都会有固定的一个Leader,一群Followers,每届结束时都会重新选举新的Leader,但这里每届的时间不是固定的,原则上,对一个Follower进程来说,只要它持续收到Leader的消息,它的term信息就不会改变。

作为Leader的server进程,也有义务定时向所有的Followers发送消息,称为heartbeat,依此向集群其他成员原告,老大我活得好好的,你们谁都不要想篡位!

4,设置一个倒计时器叫election timeout,一般会随机设定一个150到300毫秒的值。

这个时间就是该server进程等待Leader消息的最长时间,只要在该倒计时为零之前,该server收到了Leader发来的心跳信息,就会重新随机初始化election timeout,开始新的倒计时。假如一个Follower进程等待Leader消息的时间超过了这个时间,Follower进程就认为Leader已经挂了,要进行下一次选举。

#Leader选举

三个进程做完上面的工作后,就开始了各自的election timeout倒计时,由于这个值是随机设定的,所以可以认为三个进程各不相同,所以,总会有一个进程先倒计时完毕,假设是进程s1,此时它就认为Leader不存在了,然后就将自己变身为Candidate,即

type=candidate

啥?你说万一多个进程的election timeout一样咋办?这个raft协议也早做了防备,我们后面再说,现在,让我们集中精力看看Leader是如何选举出来的吧。

s1变身candidate后,会首先给自己投上一票,然后向s2,s3发送请求,希望它们为自己投票。

s2,s3收到请求后,会查看一下,在第0届任期内,即term=0,自己有没有投过票,如果没有投过,就会将票投给s1,显然,它们此时都会给s1投票。

投完票后,它们会重新初始化自己的election timeout,并重新倒计时。

此时,我们观察一下s2,s3的状态,它们的term还是0,并且投过票,重新开始了倒计时。

在倒计时结束之前,如果再有其他进程来请求投票,它们都不会再投的,因为在本届任期内,它们已经投出一票了。

这里的默认假设就是投出一票后,就会有新的Leader出现,新的Leader会在election timeout结束之前给它们发送heartbeat,所以,在此期间,它们不会再投票给其他进程。你说,万一投票后没有新的Leader产生怎么办?放心,这个问题是已经解决的,但这属于特殊情况的处理,我们单独另说。

好了,s1收到s2,s3的投票后,数一数,加上自己给自己的投票,一共收到三张票,超过半数,自己当选为Leader!

当上leader的s1首先将term升为1,表示新一届的开始,并通过heartbeat将这个信息通知给其他进程。

s2,s3如同预期那样,收到了s1发来的heartbeat,它们也将term升级为1。

至此,系统有了稳定的Leader,Follower。

下面,我们讨论下刚才提到的几个冲突情况。

第一个,多个进程同时变成candidate,会同时向其他进程发出投票申请,对于一个Follower来说,哪个的请求先到,就投票给谁,后来的请求,在timeout结束之前,都不会给它投票。

由于在一个term内,每人只能投一票,则最后结果无非两种:

1,其中某个candidate获得了多数投票,变身领导者,升级term,并通知其他进程,包括与他竞争的那些candidate,其他进程都会承认它的领导地位,选举结束。

2,每个candidate都没获得过半的票数,那么,这些candidates会重新随机初始化自己的election timeout。所有的进程又像系统刚启动时那样了,由于每个candidate重新随机初始化了自己的倒计时,所以,可以期待不会再发生冲突,如果还是有冲突,重复上面的过程即可。

这里,唯一不可能的就是出现多个leader,因为只有一个candidate能够获得过半投票。

#log复制

有了Leader,以后集群的所有对外服务都要经过Leader。下面我们用个例子来说明。

假设现在客户端向s1(此时的leader)发送了5,希望将5存到集群中。

s1收到请求后将采取如下动作:

首先将5存到log中,作为一条记录,这样的记录称为entity。

然后,将这个entity发送给其他进程

其他进程收到entity后,会发送确认信息给s1,

s1收到过半的确认信息后,就会将自己的值改为5,并及时通知到其他进程,其他进程收到这个通知后,也会把自己的值改为5。至此,完成一次存储过程。

这里为什么只需过半就可以呢?万一有个进程死掉了,然后又重启,假设是s2,刚好错过s1发送5的消息会怎样呢?

当s2重启后,马上会收到s1发来的heartbeat,此时,它会发现自己已经落后于Leader了,所以他只需跟上Leader的状态即可。

让我们再把问题复杂一些,假设s2刚重启,作为Leader的s1挂掉了,然后会不会出现这样的情况,重新进行选举,s2当选,要求其他进程向他看齐,放弃原先存好的5,比如s3这个进程。

答案是不会的,我们不要忘记,还有term在呢,s2重启后,term归0,在和其他进程交流时,发现自己term小,所以会首先将状态同步到其他进程的。

# 容忍网络分化

让我们假设一种情景,有五个节点,姑且叫s1到s5,s1是leader,突然,s1,s2和s3,s4,s5隔开了。这时会发生什么呢?

s1作为leader,收到客户端的存储请求后,依然按上面的步骤进行,但由于它此时只能收到s2发来的确认信息,确认信息无法超过半数,所以一直不会更新自己的存储值 。仅仅将各种更新操作存到log里。

另外三个进程,一段时间后会选出自己的Leader,比方说是s3,客户端发给s3的存储操作都会成功,因为s3可以收到过半数的确认信息。

一段时间后,网络又恢复了。s1这个老leader和s3这个新leader碰面了,由于s3的term值比s1高(每次成功的选举都会增加term值),s1就会自动退位成Follower。

#无总结,不进步

以上,我们用通俗的方式了解了一下raft协议,可以看到,raft协议十分易于理解。这是它与paxos协议相比的一大优点。同时,它的设计也是十分巧妙,让人有一种美的享受。