zookeeper集群选举机制(二)

        在上面我们总结了简单的zookeeper集群的配置，也提到了集群中的leader和follower，那么我们是如何选举出leader的呢？这里需要先了解下paxos算法，它是一种基于消息传递且具有高度容错性的一致性算法，是分布式一致算法中的经典算法，它也是两阶段提交算法，但是与平时所说的两阶段算法不一样，在paxos算法中有提议者(proposer)、接收者(acceptor)和学习者(leaner)三种节点角色。

       提议者负责提出需要达成一致的value值，而接收者则负责接收提议者发送过来的value，对该提议进行投票，以决定是否接收提议者发送过来的value，学习者不参与投票，只接收投票结果。下面大概解释下paxos算法的两阶段提交算法：

     A1.提议者选择一个提案编号n，并且给大多数的接收者发送带有该编号n的一个提案预请求。

     A2.如果接收者接收到一个编号为n的提案预请求，并且请求的编号n大于前面已经响应过的预请求编号，那么则做出响应，同时承诺不再接收比该编号n更小的预请求编号，如果接收者中已经有预请求编号，则在做出的响应中返回接收过的最高的编号提案。

   B1.如果提议者接收到大多数接收者对于编号n的预请求响应，这时会给每个接收者发送一个带有提议编号为n和值为v的接收请求，这个v值的来源是如果接收者响应中已经包含有其他提议者的内容，则取接收者响应中最高编号的对应的v值，如果响应中没有其他提议内容，则v可以取任意值，这个响应的v值会覆盖提议者当前编号n对应的v值。

   B2.如果接收者收到一个提议编号为n的接收请求，它接收该提案，如果它已经准备对大于编号n的预请求做出响应，则不接收编号n的提案。

    经过以上步骤，最终只会有一个提议者被选择，只有被选择的提议者才会被learn节点学习，同时也保证了选择的可终止性。

   了解完paxos算法也就大概明白了zookeeper的leader选举过程，只不过在zookeeper中还有一些专门的名词:

    服务器id---集群中在配置文件中dataLog路径下存放的myid。

    事务id---服务器中存放的最大数据zxid。

    逻辑时钟---发起的投票轮数计数。

    选举状态：

         LOOKING---竞选状态。

         FOLLOWING---随从状态，同步LEADER状态，参与投票。

         OBSERVING---观察者状态，同步LEADER状态，不参与投票。

         LEADING---领导者状态。

     在zookeeper集群中要作为LEADING，必须要满足以下2个条件：

           1.选举出的leader必须要有最高的zxid。

           2.要超过半数节点同意。半数节点的计算方式是n/2+1，n代表zookeeper服务器的数量，作为分布式集群n的数量一般设置为奇数个。

     在其内部有3种默认的选举算法：

          1.基于UDP的非认证的fast leader election

          2.基于UDP的认证的fast leader election

          3.基于TCP的fast leader election

     需要注意的是前2种算法将在下一个版本中删除，只有第3种版本。我们具体了解下zookeeper的选举算法：

       1.每个zookeeper服务实例都向自己发起选择自己为leader的投票。

       2.其他服务实例收到投票邀请时，比较发起者的zxid是否比自己的zxid大，大则投票给它，小则不投票，相等则比较发起者的服务器id，大则投票给它。

       3.发起者收到大家的投票反馈后，看投票数(包含自己)是否大于集群的半数，大则胜出，当选leader；未超过半数且领导者未选举出来，则重新发起投票。

     假设我们有5台zookeeper服务器，假设都是第一次启动，所有的zxid都相同，我们依次启动1,2,3,4,5服务器，看它是如何选举出leader的：

     1.服务器1启动时，它自己给自己投票，然后对其他服务器发起投票，由于其他服务器还没有启动，那么服务器1就会一直处于LOOKING状态

      2.服务器2启动，它也会给自己投票，同时它会向其他服务器发起投票，这时因为zxid都相同，所以比较它们的服务器id，所以服务器2胜出，但是由于不满足大多数服务器已启动的要求，所以服务器1，2也都会处于LOOKING状态。

      3.服务器3启动，这时会给自己投票，同时也会向其他服务器发起投票，因为服务器1,2都已经启动，并且它们的zxid都相同，所以比较服务器id，因为服务器3的服务器id比1,2的都大，所以这时服务器3就会满足成为leader的条件，因为已经超过大多数。

       4.服务器4启动，这时会给自己投票，同时也会向其他服务器发起投票，因为服务器1,2,3已经启动并且已经选举出了leader，尽管服务器4的服务id都比它们大，但是服务器3已经成为leader已经是事实，所以它也只能成为FOLLOWING了。

      5.服务器5启动，它也会做出和服务器4一样的动作，但是也只能成为FOLLOWING了。

      我们选举完成了leader后，我们如何保证leader和followering数据的同步呢？这时就不得不了解我们zookeeper的协议zab协议了，它是专门为zookeeper设计的数据一致性协议，其最重要的就是数据的有序性，它也是参考paxos算法实现的。我们了解下zab协议的过程：

     1.所有的事务请求(增删改)都会转发到leader服务器处理。

     2.leader会分配全局的事务id(zxid)，然后向following进行广播事务提议。

     3.following进行提议处理，做出反馈给leader。

     4.leader收到过半数的反馈，就广播commit。

     5.leader对传送来事务请求的服务器做出反应，不管是来自following还是自己。

     我们接下来看下如果某台服务器宕机或者失联后，我们该如何处理？这里我们得说明下zab协议最重要的2个确保机制：

     1.zab协议确保leader提交的事务最终被所有的服务器都提交。zab协议规定如果在某一台服务器上面事务提议处理成功，那么在所有的服务器上面都会处理成功，哪怕是某个服务器崩溃了。

    2.zab协议确保丢弃那些只在leader上面被提出的事务，也就是说还没有广播给following的数据。

    我们还是以上面的5台服务器为例，服务3是现在的leader：

    1.当服务器1宕机后，因为服务器1是following，所以不会触发leader重新选举，当服务器1重新启动后，那么会自动的将leader中的数据同步到服务器1中。

    2.当服务器1和2和leader失联后，由于形成不了大多数，所以也不会出现新的选举，当恢复重连后也会自动将新的数据同步到服务器1和2中。

   3.当服务器3宕机或失联后，这时会出现重新选举leader，首先它会根据选举策略获取zxid最大的服务器，如果只有1台服务器的zxid是最大的，那么这台服务器就会成为新的leader，如果有多台服务器的zxid都是最大的，那么则会根据服务器id来选举出新的leader；新的leader服务器中的数据会根据zab协议的2个确保机制来保证是最新的，当服务器3恢复后，它会向其他的服务器发送提议毕竟以前它是leader，这时它才发现它的数据已经不是最新的了，这时它就会把自己的数据丢弃掉同时成为following，去新的leader同步数据到自己。

     在这里需要说明下的是zxid是一个64位的数字，后32位是单调递增的计数器，leader每产生一次提议就会对该计数器+1，前32位表示一个周期纪元编号，也是一个计数器，每产生一个新的leader就会+1。