ZooKeeper选举流程
阅读本文前，请确保您已经阅读了我的文章：ZooKeeper基础
为了保证ZooKeeper的可用性，在生产环境中我们使用ZooKeeper集群模式对外提供服务，并且集群规模至少由3个ZooKeeper节点组成。
但是，并非节点越多越好。节点越多，使用的资源越多，ZooKeeper节点间花费的通讯成本也越高。
3节点集群和4节点集群，我们选择使用3节点集群；5节点集群和6节点集群，我们选择使用5节点集群，以此类推。因为生产环境为了保证高可用，3节点集群最多只允许挂1台，4节点集群最多也只允许挂1台(过半原则)。同理5节点集群最多允许挂2台，6节点集群最多也只允许挂2台。因此出于对资源节省的考虑，我们应该使用奇数节点来满足相同的高可用性。
如果3个节点组成集群，其中1个节点挂掉后，根据ZooKeeper的Leader选举机制是可以从另外2个节点选出一个作为Leader的，集群可以继续对外提供服务。
为了保证写操作的一致性与可用性，Zookeeper专门设计了一种名为原子广播（ZAB）的支持崩溃恢复的一致性协议。基于该协议，Zookeeper实现了一种主从模式的系统架构来保持集群中各个副本之间的数据一致性。
根据ZAB协议，所有的写操作都必须通过Leader完成，Leader写入本地日志后再复制到所有的Follower节点。
一旦Leader节点无法工作，ZAB协议能够自动从Follower节点中重新选出一个合适的替代者，即新的Leader，该过程即为领导选举。领导选举过程，是ZAB协议中最为重要和复杂的过程，ZAB协议选举Leader算法被称为基于TCP的FastLeaderElection算法。
1. 选举基本原则
1. 选举投票必须在同一轮次中进行
如果Follower服务选举轮次不同，不会采纳投票。使用选举轮次的目的稍后再说。
2. 数据最新的节点优先成为Leader
数据的新旧使用每个节点的最大zxid来判定，zxid越大认为节点数据约接近Leader的数据，自然应该成为Leader。
3. 比较server.id，id值大的优先成为Leader
如果每个参与竞选节点zxid相同，再使用server.id做比较。server.id是在配置文件中指定的节点在集群中唯一的id。
最后，当超过半数的节点投票都指向的节点成为Leader，其他参与投票的节点则成为Follower。
zxid用于标识一次更新操作的Proposal ID。为了保证顺序性，该zkid必须单调递增。因此Zookeeper使用一个64位的数来表示，高32位是Leader的epoch，从1开始，每次选出新的Leader，epoch加一。低32位为该epoch内的序号，每次epoch变化，都将低32位的序号重置。这样保证了zkid的全局递增性。
2. 节点状态
集群内的几点状态分为以下4种：
- LOOKING：不确定Leader状态。该状态下的服务器认为当前集群中没有Leader，会发起Leader选举
- FOLLOWING：跟随者状态。表明当前服务器角色是Follower，并且它知道Leader是谁
- LEADING：领导者状态。表明当前服务器角色是Leader，它会维护与Follower间的心跳
- OBSERVING：观察者状态。表明当前服务器角色是Observer，与Folower唯一的不同在于不参与选举，也不参与集群写操作时的投票（Observer角色用于读操作，增加集群吞吐量）。
3. 选举流程
3.1 自增选举轮次
Zookeeper规定所有有效的投票都必须在同一轮次中。每个服务器在开始新一轮投票时，会先对自己维护的logicClock进行自增操作。
每个服务器都会维护一个名为logicClock的变量，用于标识当前选举的轮次。每开始一次Leader选举，服务器都会将自己存储的logicClock执行加一操作，并且投票时会附带上这个logicClock。如果其他服务器收到了一个带有旧的logicClock的投票，则会直接忽略这个投票。
使用
logicClock记录轮次的目的在于：考虑一台机器宕机了，宕机时它的logicClock为2，此时它的投票桶内的所有数据都是在第2轮次中收到的数据。当它恢复后，轮次已经来到了4，此时如果让它直接参与投票是不正确的，因为它的投票桶的数据并不是最新数据，因此它无法投出正确的选票。
logicClock变量只在一次Leader选举开始时执行一次递增操作，一次选举中的多轮投票并不会改变logicClock变量的值。
3.2 初始化选票
每个服务器在广播自己的选票前，会将自己的投票箱清空。
投票箱记录了所收到的选票。例：服务器2投票给服务器3，服务器3投票给服务器1，服务器1投给了服务器1，则服务器1的投票箱为(2, 3), (3, 1), (1, 1)。票箱中只会记录每一个投票者的最后一票，如投票者更新了自己的选票，则其它服务器收到该新选票后会在自己票箱中更新该服务器的选票。
每个服务器在进行领导选举时，会发送如下关键信息：
- logicClock：每个服务器会维护一个自增的整数，名为logicClock，它表示这是该服务器发起的第多少轮投票
- state：当前服务器的状态
- self_id：当前服务器的myid
- self_zxid：当前服务器上所保存的数据的最大zxid
- vote_id：被推举的服务器的myid
- vote_zxid：被推举的服务器上所保存的数据的最大zxid
事实上，每一台机器投票箱的数据结构是一个Map，如下所示：
HashMap<Long, Vote> recvset = new HashMap<Long, Vote>();
recvset.put(n.sid, new Vote(n.leader, n.zxid, n.electionEpoch, n.peerEpoch));
我们可以看到，一个投票包含了选举轮次，目标Leader的server.id和zxid等信息。
3.2 发送选票
每台服务器将给自己的投票放入投票箱，通过广播把投给自己的票发送给集群中其他LOOKING状态的服务器。
投票.PNG
如图所示，首先每一台服务器内的投票箱都被初始化为自己，（1，1）表示服务器1投给服务器1。另外，服务器1分别向服务器2和服务器3发送了两张投票，投票内容为（1，1，0）表示（logicClock，leaderServer.id, maxZxid），表示服务器1认为的leader的server.id是1，它的最大zxid为0。
每一台服务器收到其他服务器的投票后，都会更新自己的投票箱，然后根据投票箱内的投票情况选择出下一票投给谁。
3.4 接收外部投票
服务器会尝试从其它服务器获取投票，并记入自己的投票箱内。如果无法获取任何外部投票，则会确认自己是否与集群中其它服务器保持着有效连接。如果是，则根据投票箱内的内容发送自己的投票；如果否，则马上与之建立连接。
服务器在收到其他机器的投票后，会根据投票箱中的所有投票来判断下次投票投给谁。例如某一时刻服务器1内的投票箱内的投票是：（1，1），（2，2），（3，3）（服务器1投给1，2投给2，3投给3）。那么服务器1会根据各个投票内包含的zxid和server.id来判断下一次投票投给谁，并发送给集群内的其他机器。
3.5 判断选举轮次
收到外部投票后，首先会根据投票信息中所包含的logicClock来进行不同处理。
- 如果外部投票的logicClock大于自己的logicClock。说明该服务器的选举轮次落后于其它服务器的选举轮次，立即清空自己的投票箱并将自己的logicClock更新为收到的logicClock，然后再对比自己之前的投票与收到的投票以确定是否需要变更自己的投票，最终再次将自己的投票广播出去。
- 外部投票的logicClock小于自己的logicClock。当前服务器直接忽略该投票，继续处理下一个投票。
- 外部投票的logickClock与自己的相等。当时进行选票PK。
3.6 选票PK
选票PK是基于(vote_id, vote_zxid)的对比
- 外部投票的logicClock大于自己的logicClock，则将自己的logicClock及自己的选票的logicClock变更为收到的logicClock
- 若logicClock一致，则对比二者的vote_zxid，若外部投票的vote_zxid比较大，则将自己的票中的vote_zxid与vote_myid更新为收到的票中的vote_zxid与vote_myid并广播出去，另外将收到的票及自己更新后的票放入自己的票箱。
- 若二者vote_zxid一致，则比较二者的vote_myid，若外部投票的vote_myid比较大，则将自己的票中的vote_myid更新为收到的票中的vote_myid并广播出去，另外将收到的票及自己更新后的票放入自己的票箱
3.7 统计选票
如果已经确定有过半服务器认可了自己的投票（可能是更新后的投票），则终止投票。否则继续接收其它服务器的投票，直到过半服务器的投票都与自己的投票相同。
3.8 更新服务器状态
投票终止后，服务器开始更新自身状态。若过半的票投给了自己，则将自己的服务器状态更新为LEADING，否则将自己的状态更新为FOLLOWING
