ZooKeeper源码学习笔记(4)--集群选主算法
FastLeaderElection
ZooKeeper 中一共有三个实现了Election接口的选举类，分别是 LeaderElection , AuthFastLeaderElection 和 FastLeaderElection。
前两个类已经在3.4.0版本之后被废弃掉，因此在本节中，我只会介绍LeaderElection 的选主算法。
接下来我会以一个5台节点的集群为例，介绍 ZooKeeper 中的选主算法。
拥有五个节点的集群
如图所示，A、B、C、D、E代表着一个集群中的5台节点机器，冒号后面的数字代表各个机器上的sid，紫色的节点代表着 PARTICIPANT , 绿色的节点代表着 OBSERVER。
currentVote = new Vote(myid, getLastLoggedZxid(), getCurrentEpoch());
this.electionAlg = createElectionAlgorithm(electionType);
每个节点都存在一个 currentVote 对象，我们可以把他称作是这个节点的候选人。
每个节点在启动之后，首先在 QuorumPeer::start 通过 startLeaderElection 设定初始化选举配置，将候选人设置为自身，并创建对应的选举算法对象。
构造 FastLeaderElection 的时候，会启动一个 QuorumCnxManager.Listener 线程，负责监听选举端口(electionAddr)，在选举过程中维护各个节点的点对点通信。
选主流程的具体入口可以在 QuorumPeer::run 看到，当 QuorumPeer 的状态处于 LOOKING 的时候， 会调用 Election::lookForLeader 进行选主流程。
private void sendNotifications() {
for (QuorumServer server : self.getVotingView().values()) {
long sid = server.id;
ToSend notmsg = new ToSend(ToSend.mType.notification,
proposedLeader,
proposedZxid,
logicalclock,
QuorumPeer.ServerState.LOOKING,
sid,
proposedEpoch);
sendqueue.offer(notmsg);
}
FastLeaderElection::lookForLeader 中通过 sendNotifications 同其他PARTICIPANT节点建立链接关系。
我们看到 sendNotifications 中构造了一个 ToSend 对象，proposedLeader 代表当前节点的候选人的sid，proposedZxid 代表着当前节点的候选人的zxid，logicalclock 在默认情况下是通过 ZxidUtils.getEpochFromZxid(newLeaderZxid); 根据 zxid 进行计算出的，可以认为是zxid的另一种表现形式。
当 ToSend 对象被加入到 sendqueue 栈后，会有一个独立线程 WorkSender 专门负责将 ToSend 发送给对应 sid 的节点，告知他们本节点的候选人情况。
//If wins the challenge, then close the new connection.
if (sid < self.getId()) {
SendWorker sw = senderWorkerMap.get(sid);
if (sw != null) {
sw.finish();
}
closeSocket(sock);
connectOne(sid);
} else {
SendWorker sw = new SendWorker(sock, sid);
RecvWorker rw = new RecvWorker(sock, sid, sw);
sw.setRecv(rw);
SendWorker vsw = senderWorkerMap.get(sid);
if(vsw != null)
vsw.finish();
senderWorkerMap.put(sid, sw);
if (!queueSendMap.containsKey(sid)) {
queueSendMap.put(sid, new ArrayBlockingQueue<ByteBuffer>(
SEND_CAPACITY));
}
sw.start();
rw.start();
}
当 QuorumCnxManager.Listener 接受到消息之后，如果发现发送socket的节点的sid小于当前节点的sid，则关闭链接。否则保持当前的socket链接。
根据这个解释，虽然我们在每个节点的 Election::lookForLeader 的阶段都向其他节点进行了点对点链接，这样会导致两个节点互相给对方建立socket，但接受到消息的节点会根据 sid 关闭掉由 低 sid 发送给 高 sid 的socket，从而保证两个节点间的通信是唯一的。
集群节点间的通信
如上图所示，箭头指向代表着Socket到ServerSocket的指向，我们可以看到箭头指向总是从比较高的sid节点指向比较低的sid节点。
同时需要留意的是，两个绿色的 OBSERVER 节点之间是没有通信关系的，因为在 sendNotifications 的时候只会同 PARTICIPANT 节点进行通信。
选主逻辑
在节点间中点对点通信中，节点会不断接收到来自其他节点的 Message 对象 response, 如果发现 response 中候选人不是 PARTICIPANT 而是 OBSERVER, 则会将自身节点的候选人 currentVote 告知来源节点。
如果其他节点的候选人是 PARTICIPANT, 则会将这条 Message 封装成一个 Notification 对象同时放到 recvqueue 中。
FastLeaderElection::lookForLeader 会不断的从 recvqueue 中获取 Notification , 当发现满足 totalOrderPredicate 条件，即:
protected boolean totalOrderPredicate(long newId, long newZxid, long newEpoch, long curId, long curZxid, long curEpoch) {
return ((newEpoch > curEpoch) ||
((newEpoch == curEpoch) &&
((newZxid > curZxid) || ((newZxid == curZxid) && (newId > curId)))));
}
如果满足了 totalOrderPredicate 条件，则认为其他节点的候选人比当前的候选人要优秀，则通过 updateProposal 将这个更优秀的候选人设定为当前的候选人。
if (termPredicate(recvset, new Vote(proposedLeader, proposedZxid, logicalclock, proposedEpoch))) {
Vote endVote = new Vote(proposedLeader, proposedZxid, logicalclock, proposedEpoch);
leaveInstance(endVote);
return endVote;
}
当发现大部分的节点的候选人都趋于统一的时候，则认为选举结束，退出选举流程。
总结
通过 FastLeaderElection ，我们看到只有 PARTICIPANT 的节点才会被列入候选人，即便 OBSERVER 向 PARTICIPANT 中推荐自身，但是也会被在第一时间打回。从而确保了 Leader节点只会产生在 PARTICIPANT 中。
根据 totalOrderPredicate 条件我们还可以看出，FastLeaderElection 的选主算法所能够选举出的主节点是固定的，在选主的过程中，一定会选出拥有最大的zxid的节点(epoch的值也是根据zxid进行计算的，zxidA>zxidB 时，必然有 epochA>=epochB)。如果拥有最大的 zxid 的节点有多个，则一定会选择 sid 更大的那一个。
在 FastLeaderElecton 的选举中，整个选举算法的时间复杂度是 O(n), 能够确保只要节点同其他节点沟通一次之后，一定能够找到最优秀的候选人，从而将其设置为Leader节点。
PS: 整个ZooKeeper 的源码分析就到此结束了，谢谢大家的阅读。
