Zookeeper的ZAB协议和Leader选举过程剖析
1. 概念
很多人可能会认为zookeeper就是paxos算法的?个实现，但事实上，zookeeper并没有完全采?paxos算法，?是使?了?种称为Zookeeper Atomic Broadcast（ZAB，Zookeeper 原子消息广播协议 ）的协议作为其数据?致性的核?算法。
- Paxos算法 是?种通?的分布式?致性算法
- ZAB协议是?种特别为zookeeper专?设计的?种
- 分布式数据的?致性
- ?持崩溃恢复的原??播协议
在zookeeper中，主要就是依赖ZAB协议来实现分布式数据的?致性
基于该协议，Zookeeper实现了?种主备模式的系统架构来保持集群中各副本之间的数据的?致性，表现形式就是使??个单?的主进程来接收并处理客户端的所有事务请求，并采?ZAB的原??播协议，将服务器数据的状态变更以事务Proposal的形式?播到所有的副本进程中，ZAB协议的主备模型架构保证了同?时刻集群中只能够有?个主进程来?播服务器的状态变更，因此能够很好地处理客户端?量的并发请求。但是，也要考虑到主进程在任何时候都有可能出现崩溃退出或重启现象，因此,ZAB协议还需要做到当前主进程当出现上述异常情况的时候，依旧能正常?作。
2. ZAB核心
ZAB协议的核?是：定义了对于那些会改变Zookeeper服务器数据状态的事务请求的处理?式
即：所有事务请求必须由 ?个全局唯?的服务器来协调处理 ，这样的服务器被称为Leader服务器，余下的服务器则称为Follower服务器
Leader服务器负责
- 将?个客户端事务请求转化成?个事务Proposal（提议）
- 并将该Proposal分发给集群中所有的Follower服务器
- 之后Leader服务器需要等待所有Follower服务器的反馈，?旦超过半数的Follower服务器进?了正确的反馈后
- 那么Leader就会再次向所有的Follower服务器分发Commit消息，要求其将前?个Proposal进?提交
3. ZAB协议介绍
ZAB协议包括两种基本的模式：崩溃恢复和消息?播
3.1 进?崩溃恢复模式：
当整个服务框架启动过程中，或者是Leader服务器出现?络中断、崩溃退出或重启等异常情况时，ZAB协议就会进?崩溃恢复模式，同时选举产?新的Leader服务器。当选举产?了新的Leader服务器，同时集群中已经有过半的机器与该Leader服务器完成了状态同步之后，ZAB协议就会退出恢复模式，其中，所谓的状态同步 就是指数据同步，?来保证集群中过半的机器能够和Leader服务器的数据状态保持?致
3.2 进?消息?播模式：
当集群中已经有过半的Follower服务器完成了和Leader服务器的状态同步，那么整个服务框架就可以进?消息?播模式，当?台同样遵守ZAB协议的服务器启动后加?到集群中，如果此时集群中已经存在?个Leader服务器在负责进?消息?播，那么加?的服务器就会?觉地进?数据恢复模式：找到Leader所在的服务器，并与其进?数据同步，然后?起参与到消息?播流程中去。Zookeeper 只允许唯?的?个Leader服务器来进?事务请求的处理，Leader服务器在接收到客户端的事务请求后，会?成对应的事务提议并发起?轮?播协议，?如果集群中的其他机器收到客户端的事务请求后，那么这些?Leader服务器会?先将这个事务请求转发给Leader服务器。
4. ZAB协议介绍
接下来我们就重点讲解?下ZAB协议的消息?播过程和崩溃恢复过程
4.1 消息广播
ZAB协议的消息?播过程使?原?广播协议，类似于?个?阶段提交过程
针对客户端的事务请求
- Leader服务器会为其?成对应的事务Proposal
- 并将其发送给集群中其余所有的机器
- 然后再分别收集各?的选票
- 最后进?事务提交。
在ZAB的?阶段提交过程中，移除了中断逻辑
所有的Follower服务器
- 要么正常反馈Leader提出的事务Proposal
- 要么就抛弃Leader服务器
同时，ZAB协议将?阶段提交中的中断逻辑移除意味着我们可以在过半的Follower服务器已经反馈Ack之后就开始提交事务Proposal了，?不需要等待集群中所有的Follower服务器都反馈响应，但是，在这种简化的?阶段提交模型下，?法处理因Leader服务器崩溃退出?带来的数据不?致问题，因此ZAB采?了崩溃恢复模式来解决此问题，另外，整个消息?播协议是基于具有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消息后，也会完成对事务的提交
4.2 崩溃恢复（Leader选举算法/zxid）
ZAB协议的这个基于原??播协议的消息?播过程，在正常情况下运??常良好，但是?旦在Leader服务器出现崩溃，或者由于?络原因导致Leader服务器失去了与过半Follower的联系，那么就会进?崩溃恢复模式。
在ZAB协议中，为了保证程序的正确运?，整个恢复过程结束后需要选举出?个新的Leader服务器，因此，ZAB协议需要?个?效且可靠的Leader选举算法，从?保证能够快速地选举出新的Leader，同时，Leader选举算法不仅仅需要让Leader?身知道已经被选举为Leader，同时还需要让集群中的所有其他机器也能够快速地感知到选举产?出来的新Leader服务器。
5. 基本特性
根据上?的内容，我们了解到，ZAB协议规定了如果?个事务Proposal在?台机器上被处理成功，那么应该在所有的机器上都被处理成功，哪怕机器出现故障崩溃。接下来我们看看在崩溃恢复过程中，可能会出现的两个数据不?致性的隐患及针对这些情况ZAB协议所需要保证的特性。
5.1 ZAB协议需要确保那些已经在Leader服务器上提交的事务最终被所有服务器都提交（Follower已经提交）
假设?个事务在 Leader 服务器上被提交了，并且已经得到过半 Folower 服务器的Ack反馈，但是在它将Commit消息发送给所有Follower机器之前，Leader服务器挂了，如图所示
图中的消息C2就是?个典型的例?：在集群正常运?过程中的某?个时刻，Server1 是 Leader 服务器，其先后?播了消息 P1、P2、C1、P3 和 C2，其中，当Leader服务器将消息C2（C2是Commit Of Proposal2的缩写，即提交事务Proposal2）发出后就?即崩溃退出了。针对这种情况，ZAB协议就需要确保事务Proposal2最终能够在所有的服务器上都被提交成功，否则将出现不?致。
5.2 ZAB协议需要确保丢弃那些只在Leader服务器上被提出的事务
如果在崩溃恢复过程中出现?个需要被丢弃的提案，那么在崩溃恢复结束后需要跳过该事务Proposal，如图所示。
在图所示的集群中，假设初始的 Leader 服务器 Server1 在提出了?个事务Proposal3 之后就崩溃退出了，从?导致集群中的其他服务器都没有收到这个事务Proposal3。于是，当 Server1 恢复过来再次加?到集群中的时候，ZAB 协议需要确保丢弃Proposal3这个事务。
结合上?提到的这两个崩溃恢复过程中需要处理的特殊情况，就决定了 ZAB 协议必须设计这样?个Leader 选举算法：
- 能够确保提交已经被 Leader 提交的事务 Proposal
- 同时丢弃已经被跳过的事务Proposal。
针对这个要求，如果让Leader选举算法能够保证新选举出来的Leader服务器拥有集群中所有机器最?编号（即ZXID最大）的事务Proposal，那么就可以保证这个新选举出来的Leader?定具有所有已经提交的提案。更为重要的是，如果让具有最?编号事务Proposal 的机器来成为 Leader，就可以省去 Leader 服务器检查Proposal的提交和丢弃?作的这?步操作了。
5.3 总结：让具有最高编号事务Proposal 的机器来成为 Leader（ZXID最大）
5.4 验证：leader选举过程
Leader选举是zookeeper最重要的技术之?，也是保证分布式数据?致性的关键所在。
当Zookeeper集群中的?台服务器出现以下两种情况之?时，需要进?Leader选举。
- 服务器初始化启动
- 服务器运?期间?法和Leader保持连接
下?就两种情况进?分析讲解。
5.4.1 服务器启动时期的Leader选举
若进?Leader选举，则?少需要两台机器，这?选取3台机器组成的服务器集群为例。在集群初始化阶段，当有?台服务器Server1启动时，其单独?法进?和完成Leader选举，当第?台服务器Server2启动时，此时两台机器可以相互通信，每台机器都试图找到Leader，于是进?Leader选举过程。选举过程如下
-
每个Server发出?个投票
由于是初始情况，Server1（假设myid为1）和Server2假设myid为2）都会将??作为Leader服务器来进?投票，每次投票会包含所推举的服务器的myid和ZXID，使?(myid, ZXID)来表示，此时Server1的投票为(1, 0)，Server2的投票为(2, 0)，然后各?将这个投票发给集群中其他机器 -
接受来?各个服务器的投票
集群的每个服务器收到投票后，?先判断该投票的有效性，如检查是否是本轮投票、是否来?LOOKING状态的服务器。 -
处理投票
针对每?个投票，服务器都需要将别?的投票和??的投票进?PK，PK规则如下- 优先检查ZXID。ZXID?较?的服务器优先作为Leader。
- 如果ZXID相同，那么就?较myid。myid较?的服务器作为Leader服务器。
现在我们来看Server1和Server2实际是如何进?投票处理的。对于Server1来说，它??的投票是（1，0），?接收到的投票为（2，0）。?先会对?两者的ZXID，因为都是0，所以?法决定谁是Leader。接下来会对?两者的myid，很显然，Server1发现接收到的投票中的myid是2，?于??，于是就会更新??的投票为（2，0），然后重新将投票发出去。?对于Server2来说，不需要更新??的投票
-
统计投票
每次投票后，服务器都会统计所有投票，判断是否已经有过半的机器接收到相同的投票信息。对于Server1和Server2服务器来说，都统计出集群中已经有两台机器接受了（2，0）这个投票信息。这?我们需要对“过半”的概念做?个简单的介绍。所谓“过半”就是指?于集群机器数量的?半，即?于或等于（n/2+1）。对于这?由3台机器构成的集群，?于等于2台即为达到“过半”要求。那么，当Server1和Server2都收到相同的投票信息（2，0）的时候，即认为已经选出了Leader。 -
改变服务器状态
?旦确定了 Leader，每个服务器就会更新??的状态：如果是 Follower，那么就变更为FOLLOWING，如果是Leader，那么就变更为LEADING。
5.4.2 服务器运?时期的Leader选举
在ZooKeeper集群正常运?过程中，?旦选出?个Leader，那么所有服务器的集群???般不会再发?变化——也就是说，Leader服务器将?直作为集群的Leader，即使集群中有?Leader机器挂了或是有新机器加?集群也不会影响Leader。但是?旦Leader所在的机器挂了，那么整个集群将暂时?法对外服务，?是进?新?轮的Leader选举。服务器运?期间的Leader选举和启动时期的Leader选举基本过程是?致的。
我们还是假设当前正在运?的 ZooKeeper 机器由 3 台机器组成，分别是 Server1、Server2和Server3，当前的Leader是Server2。假设在某?个瞬间，Leader挂了，这个时候便开始了Leader选举。
- 变更状态
Leader挂后，余下的?Observer服务器都会将??的服务器状态变更为LOOKING，然后开始进?Leader选举过程。 - 每个Server会发出?个投票
在运?期间，每个服务器上的ZXID可能不同，此时假定Server1的ZXID为123，Server3的ZXID为122；在第?轮投票中，Server1和Server3都会投??，产?投票(1, 123)，(3, 122)，然后各?将投票发送给集群中所有机器。 - 接收来?各个服务器的投票，与启动时过程相同
- 处理投票。与启动时过程相同，此时，Server1将会成为Leader
- 统计投票。与启动时过程相同
- 改变服务器的状态。与启动时过程相同
6. 数据同步
完成Leader选举之后，在正式开始?作（即接收客户端的事务请求，然后提出新的提案）之前，Leader服务器会?先确认事务?志中的所有Proposal是否都已经被集群中过半的机器提交了，即是否完成数据同步。下?我们就来看看ZAB协议的数据同步过程。
所有正常运?的服务器，要么成为 Leader，要么成为 Follower 并和 Leader 保持同步。Leader服务器需要确保所有的Follower服务器能够接收到每?条事务Proposal，并且能够正确地将所有已经提交了的事务Proposal应?到内存数据库中去。具体的，Leader服务器会为每?个Follower服务器都准备?个队列，并将那些没有被各Follower服务器同步的事务以Proposal消息的形式逐个发送给Follower服务器，并在每?个Proposal消息后?紧接着再发送?个Commit消息，以表示该事务已经被提交。等到Follower服务器将所有其尚未同步的事务 Proposal 都从 Leader 服务器上同步过来并成功应?到本地数据库中后，Leader服务器就会将该Follower服务器加?到真正的可?Follower列表中，并开始之后的其他流程。
7. 运行时状态分析
在ZAB协议的设计中，每个进程都有可能处于如下三种状态之?
- LOOKING：Leader选举阶段。
- FOLLOWING：Follower服务器和Leader服务器保持同步状态。
- LEADING：Leader服务器作为主进程领导状态。
所有进程初始状态都是LOOKING状态，此时不存在Leader，接下来，进程会试图选举出?个新的Leader，之后，如果进程发现已经选举出新的Leader了，那么它就会切换到FOLLOWING状态，并开始和Leader保持同步，处于FOLLOWING状态的进程称为Follower，LEADING状态的进程称为Leader，当Leader崩溃或放弃领导地位时，其余的Follower进程就会转换到LOOKING状态开始新?轮的Leader选举。
?个Follower只能和?个Leader保持同步，Leader进程和所有的Follower进程之间都通过?跳检测机制来感知彼此的情况。若Leader能够在超时时间内正常收到?跳检测，那么Follower就会?直与该Leader保持连接，?如果在指定时间内Leader?法从过半的Follower进程那?接收到?跳检测，或者TCP连接断开，那么Leader会放弃当前周期的领导，并转换到LOOKING状态，其他的Follower也会选择放弃这个Leader，同时转换到LOOKING状态，之后会进?新?轮的Leader选举
8. ZAB与Paxos的联系和区别
8.1 联系：
① 都存在?个类似于Leader进程的??，由其负责协调多个Follower进程的运?。
② Leader进程都会等待超过半数的Follower做出正确的反馈后，才会将?个提议进?提交。
③ 在ZAB协议中，每个Proposal中都包含了?个epoch值，?来代表当前的Leader周期，在Paxos算法中，同样存在这样的?个标识，名字为Ballot。
8.2 区别：
Paxos算法中，新选举产?的主进程会进?两个阶段的?作，第?阶段称为读阶段，新的主进程和其他进程通信来收集主进程提出的提议，并将它们提交。第?阶段称为写阶段，当前主进程开始提出自己的提议。
ZAB协议在Paxos基础上添加了同步阶段，此时，新的Leader会确保 存在过半的Follower已经提交了之前的Leader周期中的所有事务Proposal。这?同步阶段的引?，能够有效地保证Leader在新的周期中提出事务Proposal之前，所有的进程都已经完成了对之前所有事务Proposal的提交。
总的来说，ZAB协议和Paxos算法的本质区别在于，两者的设计?标不太?样，ZAB协议主要?于构建?个?可?的分布式数据主备系统，?Paxos算法则?于构建?个分布式的?致性状态机系统
