zab协议的zookeeper领导者选举与数据同步
1 简介
zab协议是zookeeper atomic broadcast，即原子广播协议。在一个zookeeper分布式集群中，各个进程之间通过zab协议进行通信。集群中有三种角色，分别是leader,follower以及observer，observer不参与选举，每一个事务请求（更新，写入，删除）都必须由leader处理，并且最后将leader服务器的数据状态同步到其他机器。
2 请求处理
集群中所有机器均可以接收请求，对于读请求，每个机器均可以独自处理，而对于写请求则必须转发给leader进行处理。leader收到写请求过后会向所有follower发出一个proposal，当过半（quorum)的follower响应这个proposal时，leader会进行事务提交，并且通知其他机器进行事务提交，协议保证最终在leader服务器上提交的事务请求过后的状态会同步到所有机器。需要注意的是协议不保证强一致性，只保证最终所有机器的状态是一致的（状态同步是很快的）。
和两阶段三阶段一样，zab处理写请求也存在异常的情况，zab是这么处理的：
- 如果在leader发出一个proposal之前leader就挂了，那么该事务将被丢弃
- 反之，都将保证该事务在每个机器上被提交。
上面提到了过半（quorum)，这是zab的特点，对于事务请求或者内部的选举投票，只要过半就认为结束。个人认为这种方式可以节约时间。
3 数据初始化
首先需要明确如下变量的含义：
long lastProcessedZxid;//已经提交的最大的zxid，在领导者选举中初始化投票中的zxid
LinkedList<Proposal> committedLog;//服务器上记录最近的proposal commit记录，默认最多500
/**
committedLog中的最小最大proposal，用于数据同步
**/
long minCommittedLog, maxCommittedLog;
/leader所有，leader收到的proposal，一旦得到过半ack就将proposal干掉
ConcurrentMap<Long, Proposal> outstandingProposals；
//leader所有，得到过半ack后proposal将被放入toBeApplied
ConcurrentLinkedQueue<Proposal>
集群启动时，每一台服务器会从dataDir和dataLogDir分别加载数据快照和事务日志，二者和内存数据库共同组成了zookeeper的数据存储体系
3.1 数据快照
数据快照是zookeeper内存数据库每隔一段时间向本地文件存储的实时数据，包括客户端建立的session和节点。每一个数据快照的名称都使用lastProcessedZxid的十六进制作为后缀，当服务器重新启动进行数据恢复时将以该zxid作为起点。默认zookeeper会加载前一百个快照进行数据恢复，事实上只要解析到一个无误的文件后就将把数据同步到内存数据库，后面的文件不再解析。
3.2 事务日志
每当服务器收到一个proposal，就将往事务日志记录一笔，和数据快照不同的是，事务日志的大小是固定的，都为64M，并且为了提高磁盘的访问效率，每当新创建一个日志文件时将使用”\0"填满文件，日志文件的命名也使用zxid作为后缀，不过这个zxid是创建当前的日志文件后的第一个zxid，这样当进行数据恢复时，当加载完数据快照的数据后将根据数据快照的最大zxid找到其所在的事务日志，继续从事务日志中恢复数据。这里可以发现无论proposal最终是否提交，在恢复阶段，都将作为一个已经提交的proposal进行数据恢复，并最终等待leader的同步进行增删。
当服务器完成从本地日志的数据恢复后将更新lastProcessedZxid，maxCommittedLog，minCommittedLog, maxCommittedLog，接下来进行领导者选举。
4 领导者选举
zookeeper在两种情况下需要领导者选举，一种是系统启动时，一种是运行时leader挂掉或者由于网络问题形成的脑裂。领导者选举时每台参与选举的机器会向其他机器发送一个投票信息请求对方给自己投票，考虑到一轮投票可能无法选出Leader，因此投票可以使多轮的，直到选出Leader，当一个机器获得半数以上的机器投票时将成为leader。
领导者选举时发送的投票信息包括:
long id;//服务器sid，从配置文件读取
long zxid;//服务器上已经提交的最大的zxid
electionEpoch;//选举epoch，初始化为选举时钟logicalclock
long peerEpoch;//事务epoch，取zxid的高32位
ServerState state;//服务器状态，包括leader, follower, observer, looking, 选举初始为looking
描述选举算法之前先明确几个概念
recvqueue : 从其他服务器收到的投票信息
recvMap : 服务器收到的来自其他状态为looking的服务器的最新的投票信息，以及具有相同选举时钟并且状态为following或者leading的服务器的最新的投票信息
sendqueue ：需要发送到其他服务器的当前服务器的投票信息
outofelection ：很特别，接收来自其他状态为following或者leading的服务器的最新的投票信息
下面说下选举过程：
step1:投自己一票，并且向其他机器告知自己的投票结果
step2:判断自己是否是looking状态，如果不是则结束投票，如果收到的投票中的机器状态为looking转step3，如果是following和leading则转step8
step3:从recvqueue中获取一条投票信息n，成功获取根据n的选举时钟转step4、step5或者step6，如果没获取到则检查sendqueue中信息是否已经发送完毕，如果是再次告知所有机器自己的投票结果转2
step4:比较选举时钟，如果自己落后则需要将时钟更新为n的选举时钟，然后进行拼票，自己拼输了则更新自己的投票结果并广播，转step7
拼票逻辑是这样，依次比较事务epoch,zxid和服务器sid（注意此时的sid不一定是自己的sid了，如果在拼票过程中失败将被其他机器的sid替换）
/*
* We return true if one of the following three cases hold:
* 1- New epoch is higher
* 2- New epoch is the same as current epoch, but new zxid is higher
* 3- New epoch is the same as current epoch, new zxid is the same
* as current zxid, but server id is higher.
*/
return ((newEpoch > curEpoch) ||
((newEpoch == curEpoch) &&
((newZxid > curZxid) || ((newZxid == curZxid) && (newId > curId)))));
step5:如果选举时钟大于n的选举时钟，转2
step6:如果选举时钟和n相同，拼票，如果输了更新自己的投票结果，并广播自己的投票结果，转step7
step7:recvmap根据n更新投票信息，判断当前是否已经有leader产生，方法是看n投票的sid在recvmap中是否得到了过半的票数，如果成功产生leader则执行如下过程:
// Verify if there is any change in the proposed leader
while((n = recvqueue.poll(finalizeWait,
TimeUnit.MILLISECONDS)) != null){
if(totalOrderPredicate(n.leader, n.zxid, n.peerEpoch,
proposedLeader, proposedZxid, proposedEpoch)){//拼票
recvqueue.put(n);
break;
}
}
这个过程会获取recvqueue中所有投票，确认当前选出的leader确实是真leader，考虑本该当选的服务器由于网络原因发送的投票信息更晚到达各个服务器，这一步是很有意义的。
当recvqueue中已经没有投票消息即确认新leader产生，判断leader是否是自己，如果是则更新状态为leading，如果不是更新为following，结束领导者选举，否则转step2
step8: 如果n的选举时钟和自己的相同，转step9，否则转step10
step9: recvmap更新投票信息，接下来当且仅当n中推举的leader已经在recvmap中获得半数以上投票并且满足一下任意一个条件时
c1: n中推举的leader就是当前服务器自己
c2: n中推举的leader不是自己并且当前服务器自己的outofelection中已经收到记录了leader所在的服务器发过来的投票，同时该投票信息中服务器状态为leading
判断leader是否是自己，如果是则更新状态为leading，如果不是更新为following，结束领导者选举，如果不满足c1或者c2转step10
step10: outofelection根据n更新投票信息，接下来当且仅当n中推举的leader已经在outofelection中获得半数以上投票并且满足一下任意一个条件时
c3: n中推举的leader就是当前服务器自己
c4: n中推举的leader不是自己并且当前服务器自己的outofelection中已经收到记录了leader所在的服务器发过来的投票，同时该投票信息中服务器状态为leading
判断leader是否是自己，如果是则更新状态为leading，如果不是更新为following，结束领导者选举，如果不满足c3或者c4则转step2
特别注意：当集群中任意一个服务器确认自身状态并且结束选举算法时，仍然会有一个线程接收来自其他服务器的投票，此时该线程会回复自己的投票信息。
4.1 outofelection的意义
选举算法中outofelection的存在意义在于
- 选举时钟相同，当前服务器收到的消息晚于已经确认自身状态的服务器，这时候当前服务器需要确保是真的有leader选出，因此首先需要自己的recvmap确认已经有准leader，接着需要判断当前服务器已经收到过准leader的消息，假设这里不去校验准leader是否给当前服务器发消息就有可能将一个和leader失联的机器加入到集群。
- 选举时钟不同，这种情况很有可能是当前服务器由于网络等问题或者当前服务器是新加入的一个集群服务器，这时候需要调整时钟，并且使用outofelection去接收所有已经确认自身状态的服务器（理论上大部分服务器已经确认自身状态，并且无论如何最终总会从outofelection或者recvmap中确认得到半数投票的leader)，显然同样需要保证outofelection中有得到半数投票的机器并且包含了leader发过来的投票信息。注意：2中调整时钟过后如果继续受到投票将进入1。假设这里根据投票信息直接确认leader就有可能将上一个选举周期的leader作为最终leader；
5 集群的数据同步
完成领导者选举后将进行数据同步，同步根据leader的minCommittedLog, maxCommittedLog和follower的lastProcessedZxid确定。
s1:当lastProcessedZxid在minCommittedLog介于maxCommittedLog之间时，follower需要同步lastProcessedZxid
到maxCommittedLog之间的数据。
s2:当lastProcessedZxid小于minCommittedLog时，follower需要同步全量同步leader的数据
s3:当lastProcessedZxid大于maxCommittedLog之间时，follower需要回滚自己的数据到maxCommittedLog的位置。
特殊场景：针对s1，当follower的lastProcessedZxid无法在leader中找到时，需要先将follower的数据回滚到在leader中可以找到的日志记录为止。
6 开始对外服务
当leader收到一个proposal后将添加到outstandingProposals，接着向各个follower发送该proposal，收到proposal的follower记录事务日志后恢复ack，得到过半ack(包括leader自己)后leader将proposal从outstandingProposals移除并加入到toBeApplied，接下来告知各个follower可以进行事务提交，leader自己也将进行事务提交，并将proposal从toBeApplied移除，并且根据proposal更新lastProcessedZxid，maxCommittedLog。
参考：从Paxos到Zookeeper分布式一致性原理与实践
