ZooKeeper的一致性协议ZAB

ZAB协议

ZAB协议有两种模式，分别是广播模式(同步)和恢复模式(选主)。ZooKeeper用于解决自身分布式一致性的问题，保证各个Server之间的信息同步。
为了保证事务的顺序一致性，ZooKeeper采用了递增的事务ID号(zxid)来标识事务，所有的提议(proposal)都在被提出的时候加上了zxid。zxid是一个64位的数字，它高32位是纪元(epoch)用来标识领导者(leader)关系是否改变，每次一个领导者被选出来，它都会有一个新的纪元，标识当前属于这个领导者的统治时期。低32位用于递增计数。
每个Server工作状态有三种：LOOKING(当前Server不知道领导者是谁，正在搜寻)，LEADING(当前Server即为选举出来的领导者)，FOLLOWING(领导者已经选举出来，当前Server与之同步)。换种说法，LOOKING状态的Server处于选主状态，选主成功之后，LEADING状态的Server是领导者，FOLLOWING状态的Server是追随者。

ZAB协议的两种模式

广播模式(同步)

1. ZooKeeper中所有的写请求都是交由领导者接受与处理。领导者接受到消息请求后，封装为一个提议并且分配一个zxid。
2. 领导者为每一位追随者都分配了一个单独的FIFO队列，提议依次放入到有序的队列之中，分发给所有的追随者。
3. 追随者接收到提议，会先将其以事务日志的方式写入到磁盘中，之后发送一个响应回复给领导者。
4. 领导者不需要等待全部的追随者回复成功，只需要接受超过半数的追随者回复成功，就认为可以发送提交(commit)消息。
5. 领导者收到半数以上的成功回复，向所有追随者发送提交消息，同时自己也提交完成事务。
6. 追随者收到提交消息后，提交本地的事务。

广播模式与2PC协议相似(可以参考分布式一致性——2PC和3PC)，步骤1-4是第一阶段提交，步骤5-6是第二阶段的提交。ZAB协议使用zxid保证消息的有序性，并且FIFO队列可以使得领导者和追随者消息传递解耦防止阻塞的发生。关于领导者的单点问题，ZAB协议恢复模式处理。

恢复模式(选主)

ZAB协议在恢复后需要保证如下两个要求：

要求1. 确保那些已经在领导者服务器上提交的事务最终被所有服务器都提交。
要求2. 确保丢弃那些只在领导者服务器上被提出的事务。

简而言之，就是以领导者的第二阶段发出提交(commit)消息为分界，之前的就需要被丢弃，之后的要保证都提交。

为了保证上述两条要求的实现，ZAB协议需要做到：

1. 针对要求1，选举算法要保证新的领导者具有最大的zxid。因为在旧领导者提交的事务之前，一定已经经过了第一阶段的广播，这时一定有半数以上的追随者保留有这个最大的zxid。只要有合法数量的节点正常工作，就肯定有至少有一个节点上保存所有被提交的提议状态。
2. 针对要求2，当旧领导者重新加入到集群中，会发现保存的尚未提交的提议zxid已经过期，如今已经是新的纪元了，所以旧领导者作为新领导者的追随者会丢弃过时的提议。

上面所说概况一下新的领导者选举需要具备哪些条件：(后面称为选举条件)

1. 选择纪元最大的
2. 纪元相同时，选择递增计数最大的
3. 纪元和递增计数都相等，选择ServerId最大的(在配置文件中配置的)。

快速选举(Fast Leader Election)

1. 开始选举时，所有节点默认投票给自己。
2. 然后接收其他节点发来的拉票消息(每个节点会广播自己的zxid和纪元信息，要求其他节点选举自己成为领导者)，如果发来信息的节点满足选举条件，则改为选择其他节点。
3. 发送投票信息给其他节点。
4. 当一个节点得票超过半数时，该节点就会设置自己成为领导者，状态为LEADING。通知其他节点，其他节点改状态为FOLLOWING。

在选举过程中，某Server首先向所有Server提议自己要成为领导者，当其他Server收到提议后，解决纪元和zxid冲突，并接受对方的提议，然后向对方发送接受提议完成的消息，重复这个流程，最后一定能选举出领导者。

选举之后的同步过程

1. 新领导者等待追随者连接。
2. 追随者连接领导者，将最大的zxid发送给领导者。
3. 领导者根据追随者的zxid确定同步点。
4. 完成同步之后通知追随者已成为更新状态。
5. 追随者收到更新消息后，又可以重新接受客户端的请求进行服务。