ZooKeeper篇：Leader选举

         Leader选举是ZooKeeper保证分布式数据一致性的关系，选举的Leader必然是ZXID最大的一个节点，这才才能保证数据恢复

服务器启动时期的Leader选举

          隐式条件便是ZooKeeper的集群规模至少是两台机器，这里以3台机器组成的服务器集群为例。在服务器集群初始化阶段，当有一台服务器（我们假设这台机器的myid为1，因此称其为Server1）启动的时候，它是无法完成leader选举的，是无法进行leader选举的。当第二台机器（同样，我们假设这台服务器的myid为2，称其为Server2）也启动后，此时这两台机器已经能够进行互相通信，每台机器都试图找到一个Leader，于是便进入了Leader选举流程。

1.每个Server会发出一个投票

         由于是初始情况，因此对于Server1和Server2来说，都会将自己座位Leader服务器来进行投票，每次投票包含的最基本的元素包括：所选举的服务器的myid和ZXID，我们以（myid，ZXID）的形式来表示。因为是初始化阶段，因此无论是Server1还是Server2，都会投给自己，即Server1的投票为（1，0），server2的投票为（2，0），然后各自将这个投票发给集群中其他所有机器。

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

         每个服务器都会接收来自其他服务器的投票。集群中的每个服务器都在接收到投票后，首先会判断该投票的有效性，包括检查是否是本轮投票，是否会来自LOOKING状态的服务器。

3.处理投票

          在接收到来自其他服务器的偷拍后，针对每一个投票。服务器都需要将别人的投票和自己的投票进行PK，PK的规则如下：

         优先检查ZXID。ZXID比较大的服务器优先作为Leader。

          如果ZXID相同的话，那么就比较myid。myid比较较大的服务器作为Leader服务器。

         现在我们来看Server1和Server2实际是如何进行投票处理的。对于Server1来说，它自己的投票是（1，0），而接收到的投票是（2，0）。首先会对比两者的ZXID，因为都是0，所以无法决定谁是Leader。接下来会对比两者的myid，很显然，Server1发现接收到的投票的myid是2，大于自己，于是就会更新自己的投票为（2，0），然后重新奖投票发出去。而对于Server2来说，不需要更新自己的投票信息，只是再一次向集群中所有机器发出上一次投票信息即可。

4.统计投票

         每次投票后，服务器都会统计所有投票，判断是否已经有过半的机器接收到相同的投票信息。对于Server1和Server2服务器来说，都会统计出集群中已经有两台机器接受了（2，0）这个投票信息。

         那么，当Server1和Server2都收到相同的投票信息（2，0）的时候，即认为已经选出了Leader。

5.改变服务器状态

          一旦确定了Leader，每个服务器都会更新自己的状态：如果是Follower，那么就变更为FOLLOWING，如果是Leader，那么就变更为LEADING。

服务器运行期间的Leader选举

          在ZooKeeper集群正常运行过程中，一旦选出一个Leader，那么所有服务器的集群角色一般不会再发生变化——也就是说，Leader服务器将一直作为集群的Leader，即使集群中有非Leader集群挂了或者是有新机器假如集群也不会影响Leader。但是一旦Leader所在的机器挂了，那么整个集群将暂时无法对外服务，而是进入新一轮的Leader选举。服务器运行期间的Leader选举和启动时期的Leader选举基本过程是一致的。

          我们假设当前正在运行的ZooKeeper服务器由3台机器组成，分别是Server1、Server2和Server3，当前的Leader是Server2.假设在某一个瞬间，Leader挂了，这个时候便开始了Leader选举。

1.变更状态

         当Leader挂了之后，余下的非Observer服务器都会将自己的服务器状态变更为LOOKING，然后开始进入Leader选举流程。

2.每个Server会发出一个投票

          在这个过程中，需要生成投票信息（myid，ZXID）。因为是运行期间，因此每个服务器上的ZXID可能不同，我们假定Server1的ZXID为123，而Server3的ZXID为122。第一轮投票中，Server1和Server3都会投自己，即分别产生投票（1，123）和（3，122），然后各自将这个投票发送给集群中的所有机器。

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

4.处理投票

         对于投票的处理，和上面提到的服务器启动期间的处理规则是一致的。在这个例子里面，由于Server1的ZXID为123，Server3的ZXID为122，那么，Server1会成为Leader。

5.统计投票

6.改变服务器状态。

Leader选举的算法分析

         在ZooKeeper中，提供了三种Leader选举的算法，分别会LeaderElection、UDP版本的FastLeaderElection和TCP版本的FastLeaderElection，可以通过在配置文件zoo.cfg中使用electionAlg属性来指定，分别使用数字0~3表示。0代表LeaderElection，这时一种纯UDP实现的Leader选举算法：1代表UDP版本的FastLeaderELection，并且是非授权模式；2也代表UDP版本的FastLeaderElection，但使用授权模式；3代表TCP版本的FastLeaderElection，从3.4.0版本开始，废弃012三种Leader选举算法，只保留TCP版本的FastLeaderElection

术语解释

         SID：服务器ID

         SID是一个数字，用来唯一标识一台ZooKeeper集群中的机器，每台机器不能重复，和myid的值一致。

         ZXID：事务ID

         ZXID是一个事务ID，用来唯一标识一次服务器状态变更。集群中每台机器的ZXID值不一定全都一致，这和ZooKeeper服务器对客户端“更新请求”的处理逻辑有关

         Vote：投票

         Leader选举，当集群中的机器发现自己无法检测到Leader机器的时候，就会开始尝试进行投票。

         Quorum：过半机器数****

          n/2 + 1

算法分析

进入Leader选举

         当ZooKeeper集群中的一台服务器出现以下两种情况之一时，就会开始进入Leader选举。

         服务器初始化启动

         服务器运行期间无法和Leader保持连接

         而当一台机器进入Leader选举流程时，当前集群也可能处于以下两种状态。

                 集群中本来就已经存在一个Leader

                 集群中确实不存在Leader

         第一种已经存在Leader的情况。这种情况通常是集群中的某一台机器启动比较晚，当它启动之前，集群已经可以正常工作，即已经存在了一台Leader服务器。针对这种情况，当该机器试图去选举Leader是，会被告知的当前服务器的Leader信息，对于该机器来说，仅仅需要和Leader机器建立起谅解，并进行状态同步即可。

开始第一次投票

         通常两种其概况会导致集群中不存在Leader，一种情况是整个服务器刚刚初始化启动时，此时尚未产生一台Leader服务器；另一种情况就是运行期间当前Leader所在的服务器挂了。无论哪种情况，此时集群中的所有机器都处于一种试图选举出一个Leader状态，我们把这种状态称为“LOOKING”，意思是说正在寻找Leader。当一台服务器处于LOOKING状态的时候，那么它就会向集群中所有的其他机器发送消息，我们称这关消息为：“投票”。

         这关投票消息中包含了两个最基本的信息：所推举的服务器的SID和ZXID，分别表示了被推举服务器的唯一标识和事务ID，（SID，ZXID）这样的形式标识一次投票信息。例如，如果当前服务器要推举SID为1、ZXID为8的服务器成为Leader，那么它的天次跳票信息可以表示为（1，8）。

          我们假设ZooKeeper由5台机器组成，SID分别为1、2、3、4和5，ZXID分别为9、9、9、8和8，并且此时SID为2的机器是Leader服务器。某一时刻，1和2所在的机器出现故障，因此集群开始进行Leader选举。

         在第一次投票的时候，由于还无法检测到集群中其他机器的状态信息，因此每台机器都是将自己作为被推荐的对象来进行投票。于是SID为3、4和5的机器，投票情况分别为：（3，9）、（4，8）和（5，8）。

变更投票

         集群中的每台机器发出自己的投票后，也会接收到来自集群中其他机器的投票。每台机器都会根据一定的规则，来处理收到的其他机器的投票，并以此来决定是否需要变更自己的投票。这个规则也成为了整个Leader选举算法的核心所在。

         vote_sid : 接收到的投票中所推举Leader服务器的SID

         vote_zxid: 接收到的投票中所推举Leader服务器的ZXID

         self_sid： 当前服务器自己的SID

         self_zxid: 当前服务器自己的ZXID

         对于每次收到的投票的处理，都是一个对（vote_sid，vote_zxid）和（self_sid，self_zxid）对比的过程

         规则1 ： 如果vote_zxid大于self_zxid，就认可当前收到的投票，并再次将该投票发送出去。

         规则2 ： 如果vote_zxid小于self_zxid，那么就坚持自己的投票，不做任何变更

         则3 ： 如果vote_zxid等于self_zxid，那么就对比两者的SID。如果vote_sid大于self_sid，那么就认可当前接收到的投票，并再次将该投票发送出去

         规则4： 如果vote_zxid等于self_zxid，并且vote_sid小于self_sid，那么同样坚持自己的投票，不作变更

         每台机器都会把投票发出去后，同时也会接收到来自另外两台机器的投票。

         对于Server3来说，它接收到了（4，8）和（5，8）两个投票，对比后，由于自己的ZXID要大于接收到的两个投票，因此不需要做任何变更

         对于Server4来说，它接收到了（3，9）和（5，8）两个投票，对比后，由于（3，9）这个投票的ZXID大于自己，因此需要变更投票为（3，9），然后继续将这个投票发送给另外两台机器。

确定Leader

         经过这二次投票后，集群中的每台机器都会再次收到其他机器的投票，然后开始统计投票，然后开始统计投票。如果一台机器收到了超过半数的相同的投票，那么这个投票对应的SID机器即为Leader

         比如这里，Server3、Server4和Server5都投票（3，9），因此确定了Server3位Leader

         简单来说，通常哪台服务器上的数据越新，那么就越有可能成为Leader，因为数据越新ZXID也就越大，能够保证数据的恢复。

参考：

《从Paxos到ZooKeeper分布式一致性原理与实践》