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

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

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

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

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，届数不相等

image.png

②、届数不相等
如果投票的届数与当前服务器届数不相等，则会放入到outofelection集合中
n.electionEpoch != logicalclock.get()

image.png

其他情况的领导者选举

1、FOLLOWING节点挂了一半
org.apache.zookeeper.server.quorum.Leader#lead

image.png

不断向learners节点ping，如果挂了一半则会跳出循环leader.lead();阻塞被解除

image.png

org.apache.zookeeper.server.quorum.QuorumPeer#run
会走向finally，并updateServerState更新服务状态

image.png

org.apache.zookeeper.server.quorum.QuorumPeer#updateServerState

image.png

QuorumPeer#run会进行下次循环
2、LEADING节点挂掉
follower.followLeader();这个阻塞方法会调用finally。与FOLLOWING挂掉一半类似

image.png

总结：

领导者选举算法核心就是把选票封装并放入到sendqueue集合发送，通过recvqueue得到其他服务节点的选票。并不断比较PK，更改选票并不断发送，并验证是否过半。如果过半则选举出来领导者。
领导者选举触发情况：刚启动、FOLLOWING节点挂了一半、LEADING节点挂掉