从PAXOS到ZOOKEEPER分布式一致性原理与实践：Lead

本文内容为《从PAXOS到ZOOKEEPER分布式一致性原理与实践》一书学习笔记。本文主要概述第七章选举部分的内容。

Leader选举隐式条件：ZooKeeper的集群规模至少是2台机器。以3台机器组成的集群为例。在服务器集群初始化阶段：有1台服务器（假设此机器myid为1，称其为Server1）启动时，是无法进行Leader选举的。当第2台服务器（myid为2，Server2）启动后，两台机器可以互相通信，都试图找到一个Leader，进入Leader选举流程。

服务器启动时的Leader选举：

1. 每个Server发出一个投票。由于是初始化阶段，Server1和Server2都会选自己作Leader并投票。投票元素包括所推选的服务器的myid和ZXID，以（myid , ZXID）形式表示。所以Server1的投票是（1，0）；Server2的投票是（2，0），然后将这个投票发给集群中所有其他机器。

2. 接收来自各个服务器的投票。每个服务器都会接受来自其他服务器的投票，并判断该投票的有效性，例如是否是本轮投票，是否来自LOOKING状态的服务器。

3. 处理投票（即再次投票）。接受到来自其他服务器的投票后，每台服务器都会变更投票。变更规则：先比较ZXID，ZXID大的优先作为Leader；ZXID相同则比较myid，myid较大的作为Leader。对于Server1来说，自己的投票是（1，0），接受的投票是（2，0）；两者ZXID相同，而接受到的投票的myid是2，更大，所以Server1会更新自己的投票为（2，0）并重新发出去，Server2则不需要更新投票信息，将上次投票信息再发送一次即可。

4. 统计投票。每次投票后，服务器都会统计所有投票，看是否已经有过半的机器接收到相同的投票信息（过半指大于集群数量的一半，即大于或等于（n/2+1））。将该机器作为Leader。

5. 改变服务器状态。确定Leader后，每个服务器都会更新自己的状态：如果是Follower，变更为FOLLOWING，如果是Leader，变更为LEADING。

服务器运行期间的Leader选举：

ZooKeeper集群正常运行过程中，Leader选出一般不再变化，即使集群中有非Leader机器挂了或有新集群加入Leader也不会影响Leader。但Leader如果挂了就需要新一轮选举。

1. 变更状态。Leader挂了后，余下的非Observer服务器都会将自己的服务器状态变更为LOOKING，然后开始Leader选举。

2. 每个Server发出一个投票。运行期间每个机器上的ZXID可能不同。但第一轮投票都是投给自己。

3. 接收来自各个服务器的投票。

4. 处理投票。

5. 统计投票。

6. 改变服务器状态。

选举过程底层实现：

涉及术语解释：

1. SID：服务器ID，唯一标识一台ZooKeeper集群中的机器，值和myid一致。

2. ZXID：事务ID，唯一标识一次服务器状态的变更。

3. Quorum：过半机器数。

4. ZooKeeper底层采用的是基于TCP的FastLeaderElection算法实现。底层网络IO部分是QuorumCnxManager管理选举之间的通信（每台服务器启动的时候，都会启动一个QuorumCnxManager）。在QuorumCnxManager这个类内部维护了一系列队列：

a. recvQueue：消息接收队列。存放从其他服务器接收到的消息

b. queueSendMap：消息发送队列，保存待发送的消息。它是一个Map，按照SID分组形成队列集合；为集群中的每台机器分配了一个单独队列，保证各台机器之间的消息发送互不影响。（按照SID分组定义：假设集群中除自身外还有4台服务器，那么当前服务器会为这4台服务器分别创建一个发送队列，互不干扰。）

c. senderWorkerMap：发送器集合。同样按照SID分组。每个消息发送器与远程ZooKeeper服务器是一对一关系。

d. lastMessageSent：最近发送过的消息。同样按照SID分组。为每个SID保留最近发送过的一个消息。

建立连接：所有机器都需要两两建立起连接。为了避免两台服务器之间重复创建TCP连接。只允许SID大的服务器主动和其他服务器建立连接。当前服务器接收到连接请求后如果发现自己的SID值比远程服务器更大，会断开当前连接，自己去和远程服务器建立连接。

消息接收与发送：消息的接收：ZooKeeper会为每个远程服务器（集群中处了自己其他的服务器）分配一个单独的消息接收器RecvWorker。每个RecvWorker不断从TCP连接中读取消息，并保存到recvQueue里去。消息发送：同上，每个服务器单独有消息发送器SendWorker，SendWorker不断从消息发送队列（自：queueSendMap）获取一个消息发送即可，同时将这个消息放入lastMessageSent。有个细节：一旦ZooKeeper发现针对当前远程服务器的的消息发送队列为空，那么此时从lastMessageSent取出一个最近未发送过的消息来再次发送。这个细节主要是为了解决这么一类分布式问题：接收方在消息接收前或接收到消息后服务器挂掉了，导致消息尚未被正确处理。同时ZooKeeper能保证接收方在处理消息的时候，会对重复消息进行正确的处理。

选票管理：
外部投票：其他服务器发来的投票。
内部投票：服务器自身当前的投票。

底层接收（QuorumCnxManager）数据，上层则进行选票管理。接收器WorkerReceiver（我的理解是上面的RecvWorker）会不断地从QuorumCnxManager获取从其他服务器发来的选举消息，并将其转换成一个选票，然后保存到recvQueue队列中去，再由具体选举算法得出选票放入sendqueue选票发送队列，由WorkSender发送至底层网络IO发送给其他服务器（我的理解是上面的SendWorker）。

统计投票说明：最后进行选票统计时，是对自己内部选票的统计（自己投的票）是否过半认可，若认可，则根据投票内容决定自己是Leader还是Follower。