Zookeeper之领导者选举算法源码分析

作者: loveFXX | 来源:发表于2020-06-22 17:41 被阅读0次

QuorumPeer#run

QuorumPeer继承了ZooKeeperThread线程类
org.apache.zookeeper.server.quorum.QuorumPeer#run
本地或远程注册

image.png

在循环内根据不同的状态运行

image.png
ServerState状态有LOOKING(不清楚自己是什么节点需要领导者选举)、FOLLOWING(跟随者从节点)、LEADING(领导者--主节点)、OBSERVING(观察者)

LOOKING

1、readonlymode
首先判断只读模式是否打开readonlymode.enabled默认是false

image.png

2、进行领导者选举

image.png
org.apache.zookeeper.server.quorum.QuorumPeer#makeLEStrategy

image.png
electionAlg = FastLeaderElection 快速领导者选举类

lookForLeader

image.png

表示：zk1、zk2、zk3三台zk服务端（myid1=1、epoch1当前届数、zxid1是当前zk1服务的状态信息）。图中连线0表示把投给自己的选票并放入sendqueue队列中，图中连线1表示发送给其他参与者(即是调用sendNotifications方法)，2表示从recvqueue接收队列获取的选票与当前服务器持有选票进行比较。
org.apache.zookeeper.server.quorum.FastLeaderElection#lookForLeader

image.png

1、第一次启动，默认投自己，并更新当前服务协议的领导者信息的值proposedLeader、proposedZxid、proposedEpoch

image.png
2、sendNotifications把投给自己的发送给其他服务器

image.png
3、封装成ToSend对象放入到sendqueue发送队列

image.png

4、从recvqueue不断获取收到的投票信息
其他服务器的投票或投给自己的都放到这里

image.png
这里首先会收到自己发送给自己的
会直接放入到recvset和voteSet(确认)集合中
voteSet确认后会判断是否超过一半，如果超过则会进行角色设置

image.png
5、与其他服务端建立连接
①、haveDelivered是否已经投递
org.apache.zookeeper.server.quorum.QuorumCnxManager#haveDelivered

image.png
queueSendMap集合中值，是从sendqueue获取的(对照领导者选举初始化的集合和线程比较好理解)，如果queueSize=0说明里面没有可以发送的数据，说明已经发送过了则返回true。如果里面有值，说明有数据没发送出去，连接没建立好。
如果再次从recvqueue集合得到的为null，则会进行是否发送过。如果没有则会与其他服务器建立连接

image.png

②、connectAll建立连接
org.apache.zookeeper.server.quorum.QuorumCnxManager#connectAll

image.png
org.apache.zookeeper.server.quorum.QuorumCnxManager#connectOne(long)

image.png
org.apache.zookeeper.server.quorum.QuorumCnxManager#connectOne

image.png
最后通过QuorumConnectionReqThread线程进行连接处理
6、获取的选票的状态是LOOKING，会先对届数Epoch比较
如果得到的其他选票信息比当前服务器的大n.electionEpoch > logicalclock.get()，说明得到的这个选票的机器经历的届数比当前服务器大，会先更改届数logicalclock.set(n.electionEpoch)，然后两个投票会进行比较。如果比当前小，则会直接break。如果相等，也会进行两个投票会进行比较

image.png

image.png
7、totalOrderPredicate
两个投票进行比较vote1 VS vote2。比较规则是先epoch 再zxid 最后myid
org.apache.zookeeper.server.quorum.FastLeaderElection#totalOrderPredicate

image.png

image.png
首先比较领导选举届数newEpoch(其他服务器获取到的选票)与curEpoch(当前服务器)
如果届数Epoc相等则比较newZxid(其他服务器获取到的选票)与curZxid(当前服务器)
如果Zxid相等则比较newId(myid)
更新心仪的领导者，然后发送给其他服务器
8、getVoteTracker投票筛选
最终修改ack的ackset值。第一个参数投票箱recvset，这个值中的票是从其他服务器获取的n，也是从recvqueue队列拉取的Notification，recvset是HashMap每个sid只能是一个不能重复。第二个参数是当前服务经过totalOrderPredicate比较后的领导者信息。recvset集合有可能得到其他所有服务器vote2、vote3等的投票，然后与当前服务器所比较后认定的比较。如果相等一个就addAck一次
org.apache.zookeeper.server.quorum.FastLeaderElection#getVoteTracker

image.png
org.apache.zookeeper.server.quorum.SyncedLearnerTracker#addAck

image.png
9、过半处理hasAllQuorums

image.png

org.apache.zookeeper.server.quorum.SyncedLearnerTracker#hasAllQuorums
是否过半判断

image.png
10、确立角色前如果能获取到更加符合领导者的投票信息
如果通过过半机制，则会继续从recvqueue队列获取。在finalizeWait = 200ms内如果获取到的新值比当前更符合当领导者则会机会继续循环再次比较

image.png
11、身份确立
如果在指定时间finalizeWait = 200ms内从recvqueue获取不到值，则会进行角色设置。确立后会把当前投票的服务返回endVote，并赋值给QuorumPeer#currentVote
如果当前协商的领导者与当前myid相同则把当前确立为领导者。

image.png
与当前myid不相同则是FOLLOWING

image.png

领导者角色已经确立

领导者角色已经确立，其他服务器启动角色处理
recvqueue数据是从Messenger.WorkerReceiver线程不断获取的
1、WorkerReceiver#run
org.apache.zookeeper.server.quorum.FastLeaderElection.Messenger.WorkerReceiver#run

image.png

2、不是有效的投票者
!validVoter(response.sid)表示是观察者
这里也进行了处理，把当前current的投票放入到sendqueue并返回给当前启动的那台服务器（通过response.sid）

image.png

image.png
3、是有效的投票者
①、如果当前服务状态是LOOKING，就是最前面分析情况。
这里会先进行判断n.electionEpoch < logicalclock.get()。说明这个投票信息已经落后，放入到sendqueue的届数是logicalclock.get()的值。

image.png
②、如果当前服务器状态已经投好票，确定了角色

image.png

把当前服务得到的currentVote放入到sendqueue队列，并返回发送给这台服务器

image.png
4、FastLeaderElection#lookForLeader
领导者选举处理
org.apache.zookeeper.server.quorum.FastLeaderElection#lookForLeader
此时从n.state得到的状态信息就不是LOOKING，而是FOLLOWING或LEADING
这里也是进行recvset投票箱和voteSet投票集合过滤，过半机制验证处理
①、届数相等

image.png
org.apache.zookeeper.server.quorum.FastLeaderElection#checkLeader
不符合下面几种情况都是返回true：
当前服务器是FOLLOWING，votes（voteSet）集合中没有LEADING那台sid的选票，如果有votes的状态不是LEADING
当前服务器是LEADING，届数不相等