zookeeper-leader选举

介绍

  ZAB协议包括了两种基本模式：崩溃恢复，数据广播。
  一旦Leader服务器出现崩溃或者由于网络原因导致Leader服务器失去了与过半Follower的联系，那么就会进入崩溃恢复模式。
  崩溃恢复主要包括两部分：Leader选举和数据恢复。

保证数据一致性

  假设两种情况：

1. 一个事务在Leader上提交了，并且过半的Folower都响应Ack了，但是Leader在Commit消息发出之前挂了。
2. 假设一个事务在Leader提出之后，Leader挂了。

  要满足上面这两个问题，必须做到：

1. 确保已经被Leader提交的Proposal必须最终被所有的Follower服务器提交。
2. 确保丢弃已经被Leader提出的但是没有被提交的Proposal。

  新的Leader的必须满足：

1. 新选举出来的Leader不能包含未提交的Proposal。
2. 新选举的Leader节点中含有最大的Zxid。

ZAB如何数据同步

  完成Leader选举后（新的Leader具有最高的Zxid），在正式开始工作之前（接收事务请求，然后提出新的Proposal），Leader服务器会首先确认事务日志中的所有的Proposal是否已经被集群中过半的服务器Commit。
  Leader服务器需要确保所有的Follower服务器能够接收到每一条事务的Proposal，并且能将所有已经提交的事务Proposal应用到内存数据中。等到Follower将所有尚未同步的事务Proposal都从Leader服务器上同步过啦并且应用到内存数据中以后，Leader才会把该Follower加入到真正可用的Follower列表中。

ZAB数据同步过程中，如何处理需要丢弃的Proposal

  在ZAB的事务编号Zxid设计中，Zxid是一个64位的数字。
  其中低32位可以看成一个简单的单增计数器，针对客户端每一个事务请求，Leader在产生新的Proposal事务时，都会对该计数器加1。而高32位则代表了Leader周期的epoch编号。

  epoch编号可以理解为当前集群所处的年代，或者周期。每次Leader变更之后都会在epoch的基础上加1，这样旧的Leader崩溃恢复之后，其他Follower也不会听它的了，因为Follower只服从epoch最高的Leader命令。

  每当选举产生一个新的Leader，就会从这个Leader服务器上取出本地事务日志充最大编号Proposal的Zxid，并从Zxid中解析得到对应的epoch编号，然后再对其加1，之后该编号就作为新的epoch值，并将低32位数字归零，由0开始重新生成Zxid。
  ZAB协议通过epoch编号来区分Leader变化周期，能够有效避免不同的Leader错误的使用了相同的Zxid编号提出了不一样的Proposal的异常情况。
  当一个包含了上一个Leader周期尚未提交过的事务Proposal的服务器启动时，当这台机器加入集群中，以Follower角色连上Leader服务器上，Leader服务器会根据自己服务器上最后提交的Proposal来和Follower服务器的Proposal进行比对，比对的结果肯定是Leader要求Follower进行一个回退操作，回退到一个确实已经被集群中过半机器Commit的最新Proposal。

---

Leader选举

  选举分为四个阶段：选举阶段，发现阶段，同步阶段，广播阶段。

选举阶段

  节点在一开始都处于选举阶段，只要一个节点得到超过半数节点的票数，他就可以当选准Leader，只有达到同步阶段，这个节点才能真正称为Leader。
  Zookeeper规定所有有效的投票都必须在同一个轮次中，每个服务器在开始新一轮投票时，都会对自己维护的logicalClock进行自增操作。
  每个服务器在广播自己的选票前，会将自己的投票箱（recvset）清空。该投票箱记录了所受到的选票。(3,2)这种格式，表示3投给了2。
  广播选票后，会进行选票PK，选出准Leader。

发现阶段

  在这个阶段，Followers和上一轮选举出的准Leader进行通信，同步Followers最近接收的事务Proposal。
  一个Follower只会连接一个Leader，如果一个 Follower节点拒绝另一个Follower节点，则会在尝试连接时被拒绝。被拒绝之后，该节点就会进入Leader Election阶段。
  这个阶段的主要目标是发现当前大多数节点接收的最新Proposal，并且准Leader生成新的epoch，让Follower接收，更新它们的acceptedEpoch。

同步阶段

  同步阶段主要是利用Leader前一阶段获得最新的Proposal历史，同步集群中所有的副本。
  只有当超过半数节点都同步完成，准Leader才会称为真正的Leader。Follower只会接受Zxid比自己LastZxid大的Proposal。

广播阶段

  到了这个阶段，Zookeeper集群才能正式向外部提供服务，并且Leader进行消息广播。如果有新节点，对新节点进行数据同步。
  Zookeeper不需要得到全部的Follower的ACK，超过一般数量的ACK，就饿可以Commit。

---

协议实现

  实际的实现跟上面有所不同，分为三个阶段，将发现和同步阶段合在一起。
  实际分为，选举、恢复、广播三个阶段。

选举阶段

  选举阶段采用Fast Leader Election（FLE），会采用LastZxid最大的节点作为Leader，这样就省去了发现最新提议的阶段。
  这是基于拥有最新提议的节点也拥有最新的提交记录。
  称为Leader的条件：

1. 选epoch最大的。
2. epoch相等，选Zxid最大的。
3. 若 epoch 和 zxid 相等，选择 server_id 最大的（zoo.cfg中的myid）。

  节点在选举开始时，都默认投票给自己，当接收其他节点的选票时，会根据上面的Leader条件 判断并且更改自己的选票，然后重新发送选票给其他节点。当有一个节点的得票超过半数，该节点会设置自己的状态为Leading ，其他节点会设置自己的状态为Following。

恢复阶段

  这一阶段Follower发送他们的lastZxid给Leader，Leader根据lastZxid决定如何同步数据。这里的实现跟前面的Phase 2有所不同：Follower收到TRUNC指令会终止L.lastCommitedZxid之后的Proposal，收到DIFF指令会接收新的Proposal。

---

两个问题

已经被处理的请求不能丢

  就是发送Commit提交消息时，挂掉了。

1. 选举拥有proposal最大值（即zxid最大）的节点作为新的 leader。

   zxid最大也就是数据最新的节点保存了所有被COMMIT消息的proposal状态。

2. 新的leader将自己事务日志中proposal但未COMMIT的消息处理。
3. 新的leader与follower建立先进先出的队列，先将自身有而 follower没有的proposal发送给follower，再将这些proposal的COMMIT命令发送给follower，以保证所有的follower都保存了所有的proposal、所有的follower都处理了所有的消息。通过以上策略，能保证已经被处理的消息不会丢。

没被处理的请求需要丢失

  当leader接收到消息请求生成proposal后就挂了，其他follower并没有收到此proposal，因此经过恢复模式重新选了leader后，这条消息是被跳过的。此时，之前挂了的leader重新启动并注册成了follower，他保留了被跳过消息的proposal状态，与整个系统的状态是不一致的，需要将其删除。
  Zxid的设计的好处是旧的leader挂了后重启，它不会被选举为leader，因为此时它的zxid肯定小于当前的新leader。当旧的leader作为follower接入新的leader后，新的leader会让它将所有的拥有旧的epoch号的未被COMMIT的proposal清除。