Zookeeper里Leader选举算法

Zookeeper里Leader选举算法,第1张

Zookeeper里Leader选举算法

ZooKeepe集群中的三种服务器角色:Leader、Follower、Observer,本文主要概述Leader选举算法相关的知识。

一、Zookeeper里三种角色

1.Leader:Leader是整个集群中的核心,主要工作内容是

事务请求的唯一调度和处理者,保证集群事务处理的顺序性。集群内部各服务器的调度者

2.Follower:Follower服务器是Zookeeper集群状态的跟随者,其主要工作内容是:

处理客户端非事务请求,转发事务请求给Leader服务器参与事务请求Proposal的投票参与Leader选举投票

3.Observer:在工作原理上基本与Follower一致,不参与任何形式的投票,观察同步集群的最新状态并同步

二、选举算法

Zookeeper中主要提供了三种Leader选举算法,分别是LeaderElection、UDP版本的FastLeaderElection和TCP版本的FastLeaderElection,可以在配置文件zoo.cfg中使用electionAlg属性来指定,分别使用数字0-3来表示。下文介绍的是TCP版本的FastLeaderElection选举算法。

1. 相关术语

SID:服务器ID,SID是一个数字,用来标识一台Zookeeper中的机器,取值和myid配置文件中的值一致。

ZXID:事务ID,用来标识一次服务器状态的变更。

Vote:投票。一个Vote包含以下几个属性:

        id:被推举的Leader的SID值。

        zxid:被推举的Leader的事务ID。

        electionEpoch:逻辑时钟,用来判断多个投票是否在同一轮选举周期中。

        peerEpoch:被推举Leader的epoch。

        state:当前服务器的状态,LOOKING、FOLLOWING、LEADEING、OBSERVING

2. 算法分析

当ZooKeeper集群中的一台服务器出现以下两种情况之一时,就会开始进入Leader选举。

服务器初始化启动服务器运行期间无法和Leader保持连接

注:当一台服务器加入集群中时,如果当前集群中已经存在一台正常工作的Leader,那么这个服务器会连接Leader进行数据同步,若无Leader,则会进行Leader选举阶段。

开始第一次投票    

当集群中的机器进行Leader选举阶段,机器的状态会变更为LOOKING,当一台机器处于LOOKING转态时,它会向集群中的其他所有机器发送消息,这个消息为“投票”,同时该机器也会接受其他机器的“投票”。

我们用(SID,ZXID)这样的形式来表示一次投票信息。例如,当前服务器要推举SID为1、ZXID为8 的服务器成为Leader,那么它这次的投票信息可以表示为:(1,8)。

我们假设Zookeeper由5台机器组成,SID分别为1、2,3、4、5,ZXID分别为9、9、9、8、8。

并且此时SID为2的机器是Leader服务器。在某一时刻,1和2所在机器发生故障,此时集群开始进行Leader选举。

在第一次投票时,因为无法检测到集群中其他机器的状态信息,每台机器在第一次投票时,会将自己作为推举对象进行投票。即集群中正常运行的3、4、5号机器第一次投票的信息为(3,9)、(4,8)、(5,8)。

变更投票

集群中的每台机器发出自己的投票,也会接收到来自集群中其他机器的投票。机器会根据相应的规则来处理接收到的其他机器的投票,在这个过程中,可能会保持自己的投票,也可能会丢弃自己的投票更改为接收到的投票。下面定义一些术语:

vote_sid:接收到的投票中所推举的Leader服务器的SIDvote_zxid:接收到的投票中所推举的Leader服务器的ZXIDself_sid:当前服务器自己的SIDself_zxid:当前服务器自己的ZXID

处理投票的规则:

处理收到的投票,都是对(vote_sid,vote_zxid)和(self_sid,self_zxid)的比较。

规则一:如果vote_zxid 大于 self_zxid,就认可当前收到的投票,并将该投票(vote_sid,vote_zxid)发送出去规则二:如果vote_zxid 小于 self_zxid,那么就坚持自己的投票(self_sid,self_zxid)规则三:如果vote_zxid 等于 self_zxid,继续比较vote_sid和self_sid,如果vote_sid大于self_id,那么就认可接收到的投票,并将该投票(vote_sid,vote_zxid)发送出去,如果vote_sid小于self_sid,同样坚持自己的投票(self_sid,self_zxid)

根据以上规则,我们来分析上面提到的例子。

正常工作的3台机器发出第一轮投票(投给自己的投票),其他两台机器也会收到相应的投票。下面我们对每台机器的投票情况进行分析:

对于Sever3:Sever3接收到了Server4的投票(4,8)和Sever5的投票(5,8),然后按照上面阐述的规则,对比(3,9)(4,8)(5,8),Sever3的ZXID要大于Sever4和Sever5的ZXID,所以Sever3保留自己的投票,不做任何变更。对于Sever4:Sever4接收到了Sever3的投票(3,9)和Sever5的投票(5,8),然后进过对比,发现(3,9)这个投票的ZXID大于自己,因此需要变更投票为(3,9),然后变更后的投票发送给Sever3和Sever5两台机器。对于Sever5:处理的逻辑与Sever4相同。

确认Leader

如果一台机器收到了超过半数的相同的投票,那么这个投票对应的SID机器即为Leader。

当Zookeeper集群中的机器为5台,那么quorum= (5/2 +1) = 3,即只要收到3个或3个以上的相同投票即可确定Leader。在上面的例子中,Sever3、Sever4和Sever5最终都投了Sever3作为Leader,因此 Sever3成为Leader。

总结

通常具有最大的ZXID的机器越容易成为Leader,具有最大的ZXID的机器成为Leader可以保证集群数据的恢复。如果相同ZXID,那么较大的SID的那台服务器成为Leader。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5717709.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存