ZooKeeper 选举机制FasterLeaderElection详解

本文主要是介绍ZooKeeper 选举机制FasterLeaderElection详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

- 选举方式
- 选举内容
- 选举机制

ZooKeeper的核心是原子广播，这个机制保证了各个Server之间的同步。实现这个机制的协议叫做Zab协议。Zab协议有两种模式，它们分别是选举模式和同步模式。当服务启动或者在领导者崩溃后，Zab就进入了选举模式，当领导者被选举出来，且大多数Server完成了和leader的状态同步以后，选举模式就结束了。状态同步保证了leader和Server具有相同的系统状态。

1. 选举方式

ZooKeeper提供三种选举方式，分别是

FasterLeaderElection
AuthFastLeaderElection
LeaderElection.

默认采用的是类似Fast Paxos算法的FasterLeaderElection

至于Fast Paxos算法见分布式了解Paxos和Fast Paxos算法

为了保证事务的顺序一致性，zookeeper采用了递增的事务id号（zxid）来标识事务。所有的提议（proposal）都在被提出的时候加上了zxid。实现中zxid是一个64位的数字，它高32位是epoch用来标识leader关系是否改变，每次一个leader被选出来，它都会有一个新的epoch，标识当前属于那个leader的统治时期。低32位用于递增计数。

2. 选举内容

ServerId (zoo.cfg文件中server.x中的x和myid文件中的数字) Server编号，越大权重越大
Zxid（运行时产生的数据id）存储最大的数据id，数值越大权重越大
Epoch（数字时钟）投票次数，用来标记当前选举
选举状态有四种：
- LOOKING:启动时状态竞选状态
- OBSERVING:观察状态同步Leader状态不参与投票
- FOLLOWING:随从状态同步Leader状态参与投票
- LEADING:领导状态

3. 选举机制

在了解选举机制之前我们先要知道几个概念

1.一个Server是如何知道其它的Server的？

在ZooKeeper集群中，Server的信息都在zoo.conf配置文件中，根据配置文件的信息就可以知道其它Server的信息。

2.成为Leader的必要条件？

Leader要具有最高的zxid，并且集群中的大多数机器（至少n/2+1）得到相应并且选举该Leader

3.如果所有zxid都相同(刚初始化时所有的Server的epoch和zxid都是相同的)，此时有可能不能形成n/2+1个Server，怎么办？

ZooKeeper中每一个Server都有一个ID，这个ID是不重复的，如果遇到这样的情况时，ZooKeeper就推荐ID最大的哪个Server作为Leader。

4.ZooKeeper中Leader怎么知道Follwer还存活，Follwer怎么知道Leader还存活？

Leader定时向Follwer发ping消息，Follwer定时向Leader发ping消息，当发现Leader无法ping通时，就改变自己的状态(LOOKING)，发起新的一轮选举。

接下来我们来看选举机制：

在FasterLeaderElection中一个内部类Messenger，其中有两个线程WorkerReceiver和WorkSender，功能就和名字一样，分别用来接收和发送选举信息。

synchronized(this){//逻辑时钟           logicalclock++;//getInitLastLoggedZxid(), getPeerEpoch()这里先不关心是什么，后面会讨论updateProposal(getInitId(), getInitLastLoggedZxid(), getPeerEpoch());
}//getInitId() 即是获取选谁，id就是myid里指定的那个数字，所以说一定要唯一
private long getInitId(){if(self.getQuorumVerifier().getVotingMembers().containsKey(self.getId()))       return self.getId();else return Long.MIN_VALUE;
}//发送选举信息，异步发送
sendNotifications();

当集群初始化时或者是Leader无法连通时，就需要进行新一轮的选举。首先集群中的每个节点，默认都是把票投给自己的，于是把选举信息(serverid,zxid和epoch)向其他节点广播，选举信息首先被放入WorkerSender内的一个队列中，之后从队列中取出选票交付给QuorumCnxManager发送

public void toSend(Long sid, ByteBuffer b) {if (self.getId() == sid) {b.position(0);addToRecvQueue(new Message(b.duplicate(), sid));} else {//发送给别的节点，判断之前是不是发送过if (!queueSendMap.containsKey(sid)) {//这个SEND_CAPACITY的大小是1，所以如果之前已经有一个还在等待发送，则会把之前的一个删除掉，发送新的ArrayBlockingQueue<ByteBuffer> bq = new ArrayBlockingQueue<ByteBuffer>(SEND_CAPACITY);queueSendMap.put(sid, bq);addToSendQueue(bq, b);} else {ArrayBlockingQueue<ByteBuffer> bq = queueSendMap.get(sid);if(bq != null){addToSendQueue(bq, b);} else {LOG.error("No queue for server " + sid);}}//这里是真正的发送逻辑了connectOne(sid);}}

connectOne就是真正发送了。在发送之前会先把自己的id和选举地址发送过去。然后判断要发送节点的id是不是比自己的id大，如果大则不发送了。如果要发送又是启动两个线程：SendWorker,RecvWorker(这种一个进程内许多不同种类的线程，各自干活的状态真的很难理解)。发送逻辑还算简单，就是从刚才放到那个queueSendMap里取出，然后发送。并且发送的时候将发送出去的东西放到一个lastMessageSent的map里，如果queueSendMap里是空的，就发送lastMessageSent里的东西，确保对方一定收到了。

接下来来看数据接收的逻辑，根据当前Server的状态分为LOOKING状态和其他状态两种情况

1.LOOKING状态

首先判断接收到的选举信息的逻辑时钟epoch
- 如果该epoch大于当前Server的epoch –> 当前数据过期 –> 更新当前epoch,同时清空选举数据,再判断是否需要更新选举情况
- 如果该epoch小于当前Server的epoch –> 对方数据过期 –> 把本机数据(Leader.ServerId,Zxid,Epoch)发送给该Server
- 如果该epoch等于当前Server的epoch –> 直接进入判断逻辑
epoch相等的情况下先判断zxid –> 大者获胜
zxid也相等的就判断ServerId –> 大者获胜

结果:
1. 接收到了所有Server的选举信息,根据选举信息决定当前Server的状态(Leading/Following),结束Looking状态,退出选举
2. 没有接收到所有的选举信息,判断投票数是否超过半数,设置当前Server状态

2.其他状态（FOLLOWING/LEADING）

如果逻辑时钟Epoch相同,将该数据保存到recvset,如果所接收服务器宣称自己是leader,那么将判断是不是有半数以上的服务器选举它,如果是则设置选举状态退出选举过程
否则这是一条与当前逻辑时钟不符合的消息，那么说明在另一个选举过程中已经有了选举结果，于是将该选举结果加入到outofelection集合中，再根据outofelection来判断是否可以结束选举,如果可以也是保存逻辑时钟，设置选举状态，退出选举过程。

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)))));}

private boolean termPredicate(HashMap<Long, Vote> votes,Vote vote) {HashSet<Long> set = new HashSet<Long>();//遍历已经收到的投票集合，将等于当前投票的集合取出放到set中for (Map.Entry<Long,Vote> entry : votes.entrySet()) {if (self.getQuorumVerifier().getVotingMembers().containsKey(entry.getKey())&& vote.equals(entry.getValue())){set.add(entry.getKey());}}//统计set，也就是投某个id的票数是否超过一半return self.getQuorumVerifier().containsQuorum(set);}public boolean containsQuorum(Set<Long> ackSet) {return (ackSet.size() > half);}

一个小问题一个集群有3台机器，挂了一台后的影响是什么？挂了两台呢？

挂了一台：挂了一台后就是收不到其中一台的投票，但是有两台可以参与投票，按照上面的逻辑，它们开始都投给自己，后来按照选举的原则，两个人都投票给其中一个，那么就有一个节点获得的票等于2，2 > (3/2)=1 的，超过了半数，这个时候是能选出leader的。

挂了两台：挂了两台后，怎么弄也只能获得一张票， 1 不大于 (3/2)=1的，这样就无法选出一个leader了

再看一个选举流程的实例：

目前有5台Server，每台Server均没有数据，它们的编号分别是1,2,3,4,5,按编号依次启动，它们的选择举过程如下：

Server1启动，给自己投票，然后发投票信息，由于其它机器还没有启动所以它收不到反馈信息，Server1的状态一直属于Looking。
Server2启动，给自己投票，同时与之前启动的Server1交换结果，由于Server2的编号大所以Server2胜出，但此时投票数没有大于半数，所以两个Server的状态依然是LOOKING。
Server3启动，给自己投票，同时与之前启动的Server1,2交换信息，由于Server3的编号最大所以Server3胜出，此时投票数正好大于半数，所以Server3成为领导者，Server1,2成为小弟。
Server4启动，给自己投票，同时与之前启动的Server1,2,3交换信息，尽管Server4的编号大，但之前Server3已经胜出，所以Server4只能成为小弟。
Server5启动，后面的逻辑同Server4成为小弟。

这篇关于ZooKeeper 选举机制FasterLeaderElection详解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！