概述

zk通过Multi-Paxos思想实现分布式一致性，Multi-Paxos为了解决Paxos需要2轮RPC通讯(准备阶段和接受阶段)往返消息多、耗性能、延迟大的问题引入了Leader-Follower-Learner模式；考虑到高可用性，有Leader就会涉及选举Leader的问题，本节就来分析下zk是如何实现选主的；

1. 选主过程

1.1. 启动选主

选举-初始启动.png

以三个节点同时启动为例：

• 1.首先进行第一轮投票，每个节点默认先投自己一票，然后把选自己作为Leader的选票发送给其他节点；
• 2.每个节点收到其他节点发送的选票，进行选票PK；例如Server1收到Server2的【1，2，0】，Server3的【1，3，0】跟本身的【1，1，0】进行PK；先比对electionEpoch，再比对zxid，再比对SID，最终Server3获胜；
• 3.经过第一轮选票PK后，每个节点把PK后的结果放到自己的票箱同时发送给其他节点，进行第二轮PK；例如：Server1本身放入票箱（1，3）同时发送给Server2、Server3【1，3，0】；
• 4.进行第二轮PK，如果票箱中某个节点票数过半，则该节点认为选出Leader；例如：Server1收到Server2的【1，3，0】放入票箱之后，Server3已经有2票即已经过半，则选出Server3为Leader；

1.2. Follower重启

选举-Follower重启.png

以3个节点中Server1作为Follower重启为例：

• 1.Server1启动时为Looking状态，Server2为Following状态，Server3为Leading状态；
• 2.Server1向Server2/Server3发送投票信息【2，1，xxx】；
• 3.Server2知道当前leader为Server3，于是回复【2，3，xxx】，同样Server3也回复【2，3，xxx】；
• 4.Server1进行选票PK，过半数投票3，于是选Server3作为Leader，并更改状态为Following；

1.3. Leader宕机

选举-Leader宕机.png

以4个节点中Server4作为Leader宕机为例：

• 1.初始状态为Server4-Leading、Server1/2/3-Following，Server4宕机后，Server1/2/3变为Looking状态，开始进行投票选主；
• 2.选主过程跟启动选主一致；
• 3.当Server4恢复之后重新加入集群，加入过程跟Follower重启过程一致；

2. 涉及到的概念

2.1. 服务器角色

Leader：一个zk集群同一时刻只有一个Leader，所有写操作必须通过Leader完成，然后再广播给其他服务器；
Follower：一个zk集群同一时刻有多个Follower。Follower可以直接处理读请求，但是写请求需要转发给Leader处理，同时负责在Leader处理写请求时对请求进行投票；
Observer：功能跟Follower类似，但是没有投票权；

2.2. 服务器状态

Looking：寻找Leader状态，处于该状态的服务器会发起选主；
Following：跟随者状态，表明当前服务器是Follower；
Leading：领导者状态，表明当前服务器是Leader;
Observing：观察者状态，表明当前服务器是Observer;

2.3. 选主涉及类

选举-信息流.png
FastLeaderElection快速选举算法，zk默认的选举算法，负责选主的主要业务逻辑；
QuorumCnxManager负责选举时的网络通信，使用Java的Socket编程，没有使用NIO和Netty；

2.4. 选主涉及线程

Listener.run监听2888端口，阻塞在ServerSocket.accept，等待其他服务器请求创建连接；
RecvWorker.run阻塞在DataInputStream.read，获取对应服务器发送的投票信息；
SendWorker.run阻塞在ArrayBlockingQueue.poll，获取待发送消息，发送给对应服务器；
WorkerReceiver.run阻塞在recvqueue.poll，获取RecvWorker.run中接收的投票消息Notification；
WorkerSender.run阻塞在sendqueue.poll，获取待发送ToSend到SendWorker.run进行处理；
QuorumPeer.run集群模式启动过程中选举结束后，根据当前服务器状态进行之后的异步流程处理；

2.5. 选主涉及集合

LinkedBlockingQueue<ToSend> sendqueueFastLeaderElection中的请求发送队列，存放的是ToSend；

static public class ToSend {
    // 当前服务器认为的leader的sid
    long leader;
    // 当前服务器认为的leader的最新的zxid
    long zxid;
    // logicalclock.get()保持一致，每进行一轮选举就+1
    long electionEpoch;
    // 当前服务器状态
    QuorumPeer.ServerState state;
    // 当前服务器sid
    long sid;
    // 当前leader的任期
    long peerEpoch;
}

LinkedBlockingQueue<Notification> recvqueueFastLeaderElection中的请求接受队列，存放的是Notification；

static public class Notification {
    // 选择的leader的sid
    long leader;
    // 选择的leader的zxid
    long zxid;
    // logicalclock.get()保持一致，每进行一轮选举就+1
    long electionEpoch;
    // 当前服务器状态
    QuorumPeer.ServerState state;
    // 当前服务器sid
    long sid;
    // 当前leader的任期
    long peerEpoch;
}

ConcurrentHashMap<Long, SendWorker> senderWorkerMapsid -> 当前服务器到该sid的SendWorker；每个服务器会跟比自己sid小的服务器创建一个SendWorker用于投票选主时发送投票信息；
ConcurrentHashMap<Long, ArrayBlockingQueue<ByteBuffer>> queueSendMapsid -> 当前服务器需要发送到该sid的投票消息的队列；WorkerSender.run中会根据不同sid把对用的选票信息放入对应的ArrayBlockingQueue中；
ConcurrentHashMap<Long, ByteBuffer> lastMessageSentsid->最后一次发送到该sid的投票信息；
ArrayBlockingQueue<Message> recvQueueWorkerReceiver.run中接收到的投票信息，解析字节流转成Message放到recvQueue中；

static public class Message {
    // 其他服务器发送的ByteBuffer
    ByteBuffer buffer;
    // 对方服务器的sid
    long sid;
}

小结

zk选主涉及6个线程、多个集合，过程比较饶，必须要先把选主的流程和各个线程、集合的作用等搞清楚，不然理解起来比较难。下一节通过源码来具体分析选主的实现；
------over------