五、ZooKeeper的ZAB协议
ZooKeeper使用了一种称为ZooKeeper Atomic Broadcast（ZAB，ZooKeeper原子消息广播协议）的协议作为其数据一致性的核心算法，ZAB协议是为分布式协调服务ZooKeeper专门设计的一种支持崩溃恢复的原子广播协议
ZAB协议的核心是定义了对于那些会改变ZooKeeper服务器数据状态的事务请求的处理方式，即：
所有事务请求必须由一个全局唯一的服务器来协调处理，这样的服务器被称为Leader服务器，而余下的其他服务器则成为Follower服务器。Leader服务器负责将一个客户端事务请求转换成一个事务Proposal（提议），并将该Proposal分发给集群中所有的Follower服务器。之后Leader服务器需要等待所有Follower服务器的反馈，一旦超过半数的Follower服务器进行了正确的反馈后，那么Leader就会再次向所有的Follow分发Commit消息，要求其将前一个Proposal进行提交
1、协议介绍
ZAB协议包括两种基本的模式，分别是崩溃恢复和消息广播。当整个服务框架在启动过程中，或是当Leader服务器出现网络中断、崩溃退出与重启等异常情况时，ZAB协议就会进入恢复模式并选举产生新的Leader服务器。当选举产生了新的Leader服务器，同时集群中已经有过半的机器与该Leader服务器完成了状态同步之后，ZAB协议就会退出恢复模式。其中，所谓的状态同步是指数据同步，用来保证集群中存在过半的机器能够和Leader服务器的数据状态保持一致
当集群中已经有过半的Follower服务器完成了和Leader服务器的状态同步，那么整个服务框架就可以进入消息广播模式了。当一台同样遵守ZAB协议的服务器启动后加入到集群中时，如果此时集群中已经存在一个Leader服务器在负责进行消息广播，那么新加入的服务器就会自觉地进入数据恢复模式：找到Leader所在的服务器，并与其进行数据同步，然后一起参与到消息广播流程中去。ZooKeeper设计成只允许唯一的一个Leader服务器来进行事务请求的处理。Leader服务器在接收到客户端的事务请求后，会生成生成对应的事务提案并发起一轮广播协议，而如果集群中的其他机器接收到客户端的事务请求，那么这些非Leader服务器会首先将这个事务请求转发给Leader服务器
当Leader服务器出现崩溃退出或机器重启，亦或是集群中已经不存在过半的服务器与该Leader服务器保持正常通信时，那么在重新开始新一轮的原子广播事务操作之前，所有进程首先会使用崩溃恢复协议来使彼此达到一个一致的状态，于是整个ZAB流程就会从消息广播模式进入崩溃恢复模式
一个机器要成为新的Leader，必须获得过半进程的支持，同时由于每个进程都有可能会崩溃，因此，在ZAB协议运行过程中，前后会出现多个Leader，并且每个进程也有可能会多次成为Leader。进入崩溃恢复模式后，只要集群中存在过半的服务器能够彼此进行正常通信，那么就可以产生一个新的Leader并再次进入消息广播模式。举个例子来说，一个由3台机器组成的ZAB服务，通常由1个Leader、2个Follower服务器组成。一个时刻，假如其中一个Follower服务器挂了，整个ZAB集群是不会中断服务的，是因为Leader服务器依然能够获得过半机器（包括Leader自己）的支持
2、消息广播
ZAB协议的消息广播过程使用的是一个原子广播协议，针对客户端的事务请求，Leader服务器会为其生成对应的事务Proposal，并将其发送给集群中其余所有的机器，然后再分别收集各自的选票，最后进行事务提交
如下图所示就是ZAB协议消息广播流程的示意图：
在ZAB协议的二阶段提交过程中，所有的Follower服务器要么正常反馈Leader提出的事务Proposal，要么就抛弃Leader服务器，且在过半的Follower服务器已经反馈Ack之后就开始提交事务Proposal了。整个消息广播协议是基于具有FIFO特性的TCP协议来进行网络通信的，因此能够很容易地保证消息广播过程中消息接收与发送的顺序性
在整个消息广播过程中，Leader服务器会为每个事务请求生成对应的Proposal来进行广播，并且在广播事务Proposal之前，Leader服务器会首先为这个Proposal分配一个全局单调递增的唯一ID，称之为事务ID（即ZXID）。由于ZAB协议需要保证每一个消息严格的因果关系，因此必须将每一个事务Proposal按照其ZXID的先后顺序来进行排序与处理
在消息广播过程中，Leader服务器会为每一个Follower服务器都各自分配一个单独的队列，然后将需要广播的事务Proposal依次放入这些队列中去，并且根据FIFO策略进行消息发送。每一个Follower服务器在接收到这个事务Proposal之后，都会首先将其以事务日志的形式写入到本地磁盘中去，并且在成功写入后反馈给Leader服务器一个Ack响应。当Leader服务器接收到超过半数Follower的Ack响应后，就会广播一个Commit消息给所有的Follower服务器以通知其进行事务提交，同时Leader自身也会完成对事务的提交，而每一个Follower服务器在接收到Commit消息后，也会完成对事务的提交
3、崩溃恢复
一旦Leader服务器出现崩溃，或者说由于网络原因导致Leader服务器失去了与过半Follower的联系，那么就会进入崩溃恢复模式
基本特性
ZAB写规定了如果一个事务Proposal在一台机器上被处理成功，那么应该在所有的机器上都被处理成功，哪怕机器出现故障崩溃。接下来我们看看在崩溃恢复过程中，可能会出现的两个数据不一致的隐患及针对这些情况ZAB协议所需要保证的特性
1）ZAB协议需要确保那些已经在Leader服务器上提交的事务最终被所有服务器都提交
假设一个事务在Leader服务器上被提交了，并且已经得到过半Follower服务器的Ack反馈，但是在它将Commit消息发送给所有Follower机器之前，Leader服务器挂了，如下图所示：
上图中的消息C2就是一个典型的例子：在集群正常运行过程中的某一个时刻，Server1是Leader服务器，其先后广播了消息P1、P2、C1、P3和C2，其中，当Leader服务器将消息C2（提交事务Proposal2）发出后就立即崩溃退出了。针对这种情况，ZAB协议就需要确保事务Proposal2卒子红能够在所有的服务器上都被提交成功，否则将出现不一致
2）ZAB协议需要确保丢弃那些只在Leader服务器上被提出的事务
如果在崩溃恢复过程中出现一个需要被丢失的提案，那么在崩溃恢复结束后需要跳过该事务Proposal，如下图所示：
在上图所示的集群中，假设初始的Leader服务器Server1在提出了一个事务Proposal3之后就崩溃退出了，从而导致集群中的其他服务器都没有收到这个事务Proposal。于是，当Server1恢复过来再次加入到集群中的时候，ZAB协议需要确保丢失Proposal3这个事务
结合上面提到的这两个崩溃恢复过程中需要处理的特殊情况，就决定了ZAB协议必须设计这样一个Leader选举算法：能够确保提交已经被Leader提交的事务Proposal，同时丢弃已经被跳过的事务Proposal。针对这个要求，如果让Leader选举算法能够保证新选举出来的Leader服务器拥有集群中所有机器最高编号（即ZXID最大）的事务Proposal，那么就可以保证这个新选举出来的Leader一定具有所有已经提交的提案。更为重要的是，如果让具有最高编号事务Proposal的机器来成为Leader，就可以省去Leader服务器检查Proposal的提交和丢弃工作的这一步操作了
数据同步
Leader服务器需要确保所有的Follower服务器能够接收到每一条事务Proposal，并且能够正确地将所有已经提交了的事务Proposal应用到内存数据库中去。具体的，Leader服务器会为每一个Follower服务器都准备一个队列，并将那些没有被各Follower服务器同步的事务以Proposal消息的形式逐个发送给Follower服务器，并在每一个Proposal消息后面紧接着再发送一个Commit消息，以表示该事务已经被提交。等到Follower服务器将所有尚未同步的事务Proposal都从Leader服务器上同步过来并成功应用到本地数据库中后，Leader服务器就会将该Follower服务器加入到真正的可用Follower列表中，并开始之后的其他流程
在ZAB协议的事务编号ZXID设计中，ZXID是一个64位的数字，其中低32位可以看作是一个简单的单调递增的计数器，针对客户端的每一个事务请求；而高32位则代表了Leader周期epoch的编号，每当选举产生一个新的Leader服务器，就会从这个Leader服务器上取出其本地日志中最大事务Proposal的ZXID，并从该ZXID中解析出对应的epoch值，然后再对其进行加1操作，之后就会以此编号作为新的epoch，并将低32位置0开始生成新的ZXID。ZAB协议中这一通过epoch编号来区分Leader周期变化的策略，能够有效地避免不同的Leader服务器错误地使用相同的ZXID编号提出不一样的事务的异常情况
基于这样的策略，当一个包含了上一个Leader周期中尚未提交过的事务Proposal的服务器启动时，其肯定无法成为Leader，原因很简单，因为当前集群中一定包含一个Quorum集合，该集合中的机器一定包含了最高epoch的事务Proposal，因此这台机器的事务Proposal肯定不是最高，也就无法成为Leader了。当这台机器加入到集群中，以Follower角色连接上Leader服务器之后，Leader服务器会根据自己服务器上最后被提交的Proposal来和Follower进行一个回退操作——回退到一个确实已经被集群中过半机器提交的最新的事务Proposal
4、运行分析
在ZAB协议的设计中，每一个进程都有可能处于以下三种状态之一
- LOOKING：Leader选举阶段
- FOLLOWING：Follower服务器和Leader保持同步状态
- LEADING：Leader服务器作为主进程领导状态
组成ZAB协议的所有进程启动的时候，其初始化状态都是LOOKING状态，此时进程组汇总不存在Leader。所有处于这种状态的进程，都会试图去选举出一个新的Leader。随后，如果进程发现已经选举出新的Leader了，那么它就会马上切换到FOLLOWING状态，并开始和Leader保持同步。处于FOLLOWING状态的进程称为Follower，处于LEADING状态的进程称为Leader。考虑到Leader进程随时会挂掉，当检测出Leader已经崩溃或者是放弃了领导地位时，其余的Follower进程就会切换到LOOKING状态，并开始进程新一轮的Leader选举。因此在ZAB协议运行过程中，每个进程都会在LEADING、FOLLOWING和LOOKING状态之间不断地切换