ZooKeeper选Leader算法

2017-12-01  本文已影响207人  忘净空

概念

ZXID设计

一个ZXID是64位,高32是纪元(epoch)编号,每经过一次leader选举产生一个新的leader,新leader会将epoch号+1。低32位是消息计数器,每接收到一条消息这个值+1,新leader选举后这个值重置为0,可以简单理解epoch为皇帝的年后,低位32位为朝中的大臣,真所谓一朝天子、一朝臣。

选举流程

ZooKeeper选主的接口是Election,默认的具体实现类是FastLeaderElection,接下来主要走读下lookForLeader()方法。代码参考zookeeper-3.4.5

  1. 当前服务器选举轮次加1操作

  2. 更新提案,默认将票投给你自己

  3. 将提案通知给其他服务器,通知的时候会将logicalclock赋值给electionEpoch,即完成加1操作

没有外部投票的处理流程 有外部投票的处理流程
  1. 外部投票的轮次大于内部投票
    更新服务器的投票轮次,然后内部投票和外部投票PK,具体PK或得提案,具体PK算法见下图。

  2. 中外部投票轮次小于内部投票
    直接忽略

  3. 中外部投票轮次等于内部投票
    内部投票和外部投票PK,具体PK算法见下图

PK算法
  1. 外部投票中被推荐Leader服务器的选举轮次大于内部投票,提案变更。

  2. 轮次相同,外部投票被推荐Leader服务器的ZXID大于内部投票,提案变更。

  3. ZXID相同,外部投票被推荐Leader服务器的SID大于内部投票,提案变更。(SID是serverId)

过半投票认可当前内部投票
  1. 过半投票认可当前内部投票

  2. 有没有被推荐的Leader

  3. 更新服务器状态(leading,observing,following)

总流程

参考:从Paxos到Zookeeper分布式一致性原理与实践

区分外部投票轮次,外部投票中被推荐Leader投票轮次,内部同理


        /*
         * Epoch 投票轮次
         */
        long electionEpoch;

        /*
         * epoch of the proposed leader 被推荐Leader投票轮次
         */
        long peerEpoch;

简单总结选主流程(模拟选举一个NB的人)

  1. 在没有遇到比我牛的人之前,第一票推荐我自己。

  2. 我有一个票箱,保存了当前这一轮选举中自己的推荐人以及接收到的推荐人信息,一人一票,重复或过期的票概不接受,当我发现了比我推荐的牛人还牛的时候,改为推荐这个牛人,否则,我还是推荐我自己。如果我发现我的选举轮数落后了,清空票箱,改为推荐接收到的最新选举中大家推荐的最牛的那个人(如果没有人比我牛,那还是推荐我自己)。

  3. 不断的重复上面的过程,不断的告诉别人“我的投票是第几轮”、“我推举的人是谁”。直到我的票箱中“我推举的最牛的人”收到了不少于N/2+1的推举投票,此时这个人就是我认定的最终leader。

  4. 当我确定了谁是最终 leader 并且这个 leader 一切正常,我就更新我的状态为 FOLLOWING/LEADING(我自己是最终 leader 则是 LEADING 否则就是 FOLLOWING),之后的选举中都直接反馈我确定的这个最终 leader。

问题

提交已被Leader Commit的事务

发生场景

Leader发送Propose请求,Follower F1和Follower F2都向Leader回复了ACK,Leader向所有的Follower发送Commit请求并Commit自身,此时Leader宕机,Leader已经Commit,但Follower尚未Commit,数据不一致。

处理方式

选举F.zxid最大的Follower成为新的准Leader,由于旧Leader宕机前,半数或以上的Follower曾经发送ACK消息,新的准Leader必然是这半数或以上Follower的一员;新的准Leader会发现自身存在已经Propose但尚未Commit的事务Proposal,新的准Leader会向所有的Follower先发送Propose请求,再发送Commit请求。

丢弃只被Leader Propose的事务

发生场景

Leader收到了事务请求,将其包装成了事务Proposal,此时Leader宕机,Follower并没有收到Propose请求,Follower进入选举阶段,选举产生新Leader,旧的Leader重启,以Follower的角色加入集群,此时旧Leader上有一个多余的事务Proposal,数据不一致。

处理方式

新的准Leader会根据自己服务器上最后被提交的事务Proposal和Follower的事务Proposal进行对比,然后新的准Leader要求Follower执行一个回退操作,回退到一个已经被集群半数以上机器提交的最新的事务Proposal。

上一篇下一篇

猜你喜欢

热点阅读