ZooKeeper选Leader算法、Zookeeper选举算法（ FastLeader选主）

谁借莪１个温暖的怀抱￠ 2022-02-02 01:47 198阅读 0赞

转载自：[https://www.jianshu.com/p/07114f1ee595][https_www.jianshu.com_p_07114f1ee595]

### 概念 ###

*  logicalclock: ZooKeeper服务器Leader选举的轮次
 *  electionEpoch: 当前服务器的选举轮次，每次进入新一轮投票后进行加1操作
 *  peerEpoch: 被推荐的Leader的选举轮次
 *  外部投票: 特指其他服务器发来的投票
 *  内部投票: 服务器自身当前的投票
 *  Zookeeper规定了所有有效的投票都必须在同一轮次

ZXID设计

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

### 选举流程 ###

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

![format_png][]

1.  当前服务器选举轮次加1操作
2.  更新提案，默认将票投给你自己
3.  将提案通知给其他服务器，通知的时候会将logicalclock赋值给electionEpoch，即完成加1操作

![format_png 1][]

没有外部投票的处理流程

![format_png 2][]

有外部投票的处理流程

1.  外部投票的轮次大于内部投票  
    更新服务器的投票轮次，然后内部投票和外部投票PK，具体PK或得提案，具体PK算法见下图。
2.  中外部投票轮次小于内部投票  
    直接忽略
3.  中外部投票轮次等于内部投票  
    内部投票和外部投票PK，具体PK算法见下图

![format_png 3][]

PK算法

1.  外部投票中被推荐Leader服务器的选举轮次大于内部投票，提案变更。
2.  轮次相同，外部投票被推荐Leader服务器的ZXID大于内部投票，提案变更。
3.  ZXID相同，外部投票被推荐Leader服务器的SID大于内部投票，提案变更。（SID是serverId）

![format_png 4][]

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

1.  过半投票认可当前内部投票
2.  有没有被推荐的Leader
3.  更新服务器状态(leading,observing,following)

总流程

![format_png 5][]

参考:从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。

==============================

[https_www.jianshu.com_p_07114f1ee595]: https://www.jianshu.com/p/07114f1ee595
[format_png]: /images/20220202/92918ce4ef7a4136a51c8544cdbc628d.png
[format_png 1]: /images/20220202/8827d3928c264c619d6cbf190f24e98e.png
[format_png 2]: /images/20220202/de9fb98bfe6f4127b28d7acb66a55f7c.png
[format_png 3]: /images/20220202/8984cb519acc4d44a2481c4c67aed96a.png
[format_png 4]: /images/20220202/cd7d6447b74045d5a6269aa9849d45dc.png
[format_png 5]: /images/20220202/228a5a4f76c841eda09151ecd7fbcbdc.png