1. 协议概述

ZAB协议是为分布式协调服务zk专门设计的一种支持崩溃恢复的原子广播协议，在协议设计之初并没有要求其具有很好的扩展性，最初只是为雅虎公司内部哪些高吞吐量、低延迟、健壮、简单的分布式系统场景设计的。zk文档中也指出，ZAB协议并不像Paxos算法那样，是一种通用的分布式一致性算法，它是一种特别为zk设计的崩溃可恢复的原子消息广播算法

zk中，主要依赖ZAB协议来实现分布式数据一致性，基于该协议，zk实现了一种主备模式的系统架构来保持集群中各副本之间数据的一致性。具体实现是：

zk使用一个单一的主进程来接收并处理客户端的所有事务请求，并采用ZAB的原子广播协议，将服务器数据的状态变更以事务的形式广播到所有的副本进程上去。ZAB协议的这个主备模型架构保证了同一时刻集群中只能有一个主进程来广播服务器的状态变更，因此能够很好地处理客户端的大量的并发请求。另外，考虑到在分布式环境中，顺序执行的一些状态变更其前后存在一定的依赖关系，有些状态变更必须依赖于比它早生成的那些状态变更，例如变更C需要依赖变更A和变更B。这样的依赖关系也对ZAB协议提出了一个要求：ZAB协议必须能够保证一个全局的变更序列被顺序应用，也就是说，ZAB协议需要保证如果一个状态变更已经被处理了，那么所有其依赖的状态变更都应该已经被提前处理掉了，考虑到主进程任何时候都有可能出现崩溃或重启现象，ZAB协议还需要做到在当前主进程出现了上述异常情况的时候，依旧能够正常工作。

ZAB协议的核心是定义了对于那些会改变zk服务器数据状态的事务请求的处理方式：

所有的事务请求必须由一个全局唯一的服务器来协调处理，这样的服务器被称为Leader服务器，而余下的服务器则成为Follower服务器。Leader服务器负责将一个客户端事务请求转换为一个事务Proposal（提议），并将该Proposal分发给集群中的所有Follower机器，之后Leader需要等待所有的Follower服务器的反馈，一旦超过半数的Follower服务器进行了正确的反馈后，那么Leader就会再次向所有的Follower分发Commit消息，要求其将前一个Proposal进行提交

2. 协议介绍

接下来讲解ZAB协议的具体内容。

ZAB协议包括两种基本的模式，分别是崩溃恢复和消息广播。当在异常情况（重启、网络中断、崩溃退出）下，ZAB协议就会进入崩溃恢复模式并选举产生新的Leader服务器。当选举产生了新的Leader服务器，同时集群中过半的机器与该leader服务器完成了状态同步后，ZAB协议就会退出恢复模式。

接上述，完成状态同步后，就进入了消息广播模式。当一台遵守ZAB协议的服务器加入到集群中时，会自觉的进入数据恢复模式，找到Leader服务器，然后与其进行数据同步，然后参与到消息广播流程中去。

当Leader服务器出现故障或集群中已经不存在过半的服务器与该Leader服务器保持正常通信，那么在进行新一轮的原子广播事务操作之前，所有进程首先会使用崩溃恢复协议来使彼此达到一个一致的状态。于是整个ZAB流程就会从消息广播模式进入到了崩溃恢复模式。

下面详细看一下消息广播和崩溃恢复的过程

2.1. 消息广播

ZAB协议的消息广播过程使用的是一个原子广播协议，类似于二阶段提交过程，但是移除了中断逻辑。针对客户端的事务请求，Leader服务器会为其生存对应的事务Proposal，并将其发送给集群中的其余所有机器，然后再分别接收各自的选票。最后进行事务提交。示意图如下：

移除中断逻辑意味着我们可以在过半的Follower服务器已经反馈Ack之后就开始提交事务Proposal了，不需要等到集群中所有Follower都响应。这种简化的二阶段提交模型，是无法处理Leader服务器崩溃而带来的数据不一致性的，因此ZAB中采用崩溃恢复来解决这个问题。另外，整个消息广播过程是基于具有FIFO特性的TCP协议来进行网络通信的，因此能够很容易保证消息广播过程中消息接收与发送的顺序性。

广播事务之前，Leader服务器会为这个事务Proposal分配一个全局单调递增的唯一ID，我们称为事务ID（即ZXID）。ZAB协议要保证每一个消息严格的因果关系，因此对事务Proposal必须按照ZXID的先后顺序来进行排序与处理。

具体实现：消息广播过程中，Leader服务器会为每一个Follower服务器各自分配一个单独的队列，然后将需要广播的事务Proposal依次放入这些队列中去，并且根据FIFO策略进行消息发送。每一个Follower接收到事务后，首先将事务以日志的方式写入本地磁盘，写入成功后给Leader一个Ack响应。当Leader收到过半的响应，就会广播一个Commit消息给所有Follower进行事务提交，Leader自身也会完成事务的提交。

2.2. 崩溃恢复

当Leader服务器崩溃或者网络原因导致Leader与过半的Follower失去联系，就会进入崩溃恢复模式。ZAB协议需要一个高效可靠的Leader选举算法，确保能快速的选出Leader。同时选举算法不仅需要让Leader知道自己已经被选为Leader，还需要快速的让集群中其他机器感知到新的Leader

2.2.1. 基本特性

ZAB协议需要确保那些已经在Leader服务器上提交的事务最终被所有服务器都提交

ZAB协议需要确保丢弃那些只在Leader服务器上被提出的事务

针对这些要求，如果让Leader选举算法能够保证新选举出来的Leader服务器拥有集群中所有机器最高编号（即ZXID最大）的事务Proposal，那么就可以保证新选举出来的Leader一定具有所有已经提交过的提案。同时可以省去检查Proposal的提交和丢弃工作的这一步了。

2.2.2. 数据同步

完成选举之后，在正式开始工作之前，Leader服务器会确认事务日志中的所有Proposal是否都已经被集群中国版的机器提交过了，即是否完成了数据同步

正常的数据同步是使用队列的方式，上面消息广播的时候已经讲过，下面看一下ZAB协议如何处理那些需要被丢弃的事务。ZAB协议事务编号ZXID的设计中，ZXID是一个64位的数字，其中低32位可以看做是一个简单的单调递增计数器，针对客户端每个事务请求，Leader在生产事务Proposal的时候，都会对计数器进行加1操作，高32代表了Leader周期epoch的编号，每当选举产生一个新的Leader服务器，就会从Leader服务器本地日志中取出最大事务Proposal的ZXID，并从ZXID中解析出对应的epoch值，然后对其进行加1操作，之后会以此编号作为新的epoch，并将低32位置为0开始生成新的ZXID。
通过epoch机制，可以避免不同的Leadre服务器错误的使用相同的ZXID提出不一样的事务Proposal的异常情况，这对于识别在Leader崩溃恢复前后生产的Proposal非常有帮助，简化和提升了数据恢复流程。

基于这样的策略，当一个上个Leader周期未提交过事务的Proposal服务器启动时，肯定无法成为Leader。因为集群中存在其他机器存在包含了更高epoch的事务Proposal。

3. 深入ZAB协议

3.1.系统模型

抽象一下ZAB协议需要构建的分布式系统模型。通常存在一个由一组进程 P = {p1,p2,...Pn}组成的分布式系统中，每个进程都具有各自的存储设备，各进程之间通过相互通信来实现消息传递。在这样一个分布式系统中，每一个进程都随时有可能出现崩溃。这些进程恢复之后再次加入到进程组中去。如果一个进程正常工作，我们称为UP状态，崩溃了称为DOWN状态。当集群中存在过半的处于UP状态的进程组成一个进程子集后，就可以进行正常的消息广播了，这样一个进程子集称为Quorum。

其有两个特性：完整性和前置性，忽略不讲了。

3.2.问题描述

ZAB协议规定了任何时候都需要保证只有一个主进程负责进行消息广播。如果主进程崩溃，需要选举产生一个新的主进程。随着时间的推移，会出现无限多个主进程并构成一个主进程序列：P1，P2...,Pe，e表示主进程序列号，也称为主进程周期

3.2.1.主进程周期

为了保证主进程每次广播出来的事务消息都是一致的，必须确保ZAB协议只有在充分完成了崩溃恢复阶段之后，新的主进程才可以开始生成新的事务消息广播。为了实现这个目的，假设存在一个ready(e)这个的函数，明确的告知上次系统是否可以进行消息广播。调用ready(e)函数后，ZAB还需要为当前主进程设置一个实例值，标识当前的主进程周期，在进行消息广播的时候，主进程使用该值设置事务标识中的epoch字段。

3.2.2.事务

主进程每次对状态变更的广播就是一个事务

3.3.算法描述

从算法角度描述ZAB协议的内部原理。整个ZAB协议主要包括消息广播和崩溃恢复两个过程。进一步可以细分为三个阶段，分别是发现、同步、广播阶段，组成了ZAB协议的每一个分布式进程，会循环的执行这三个阶段，我们将这样一个循环称为一个主进程周期

ZAB协议算法描述术语介绍

3.3.1.阶段一：发现

选举的过程。准Leader L和Follower F的工作流程分别如下：
步骤F1.1 Follower F将自己最后接受的事务Proposal的epoch值发送给准Leader L
步骤L1.1 当接收到来自过半FOllower的CEPOCH(F.p)消息后，准Leader L会生成NEWEPOCH(e`)消息给过半的Follower。

关于epoch值e`，

准Leader L会从所有接收到的CEPOCH(F.p)消息中选出最大的epoch值，然后对其进行加1操作，即为e`

步骤F1.2 当Follower接收到来自准Leader L的NEWEPOCH(e`)消息后，如果其检测到当前的CEPOCH(F.p)值小于e·，那么就将CEPOCH(F.p)赋值为e·，同时要这个准Leader L反馈Ack消息。

当Leader L接收到来自过半Follower的确认消息Ack之后，Leader L就会从这过半服务器中选取出一个Follower F，并使用其作为初始化事务集合Ie`

关于这个Follower F的选取，对于Quorum中其他任意一个Follower F·，F需要满足以下两个条件的一个：
CEPOCH(F·.p) < CEPOCH(F.p)
(CEPOCH(F·.p) = CEPOCH(F.p)) & (F·.zxid = F·.zxid)

至此，完成阶段一的工作流程

3.3.2.阶段二：同步

这一阶段，Leader L和Follower F的工作流程分别如下：

步骤L.2.1： Leader L会将e·和Ie·以NEWLEADER(e·,Ie·)消息的形式发送给所有Quorum中的Follower

步骤F.2.1： 当Follower接收到来自Leader L的NEWLEADER(e·,Ie·)消息后，如果Follower发现CEPOCH(F.P) 不等于 e·，那么进入下一轮循环，因为此时Follower发现自己还在上一轮，无法参与本轮的同步。

如果Follower发现CEPOCH(F.P) = e·，那么Follower就会执行事务应用操作，具体的，对于每一个事务Proposal：<v,z>属于Ie·，Follower都会接受<e·,<v,z>>。最后Follower反馈给Leader，表明自己已经接受并处理了所有的Ie·中的事务Proposal

步骤F.2.2：当Follower收到来自Leader的Commit消息后，就会一次处理并提交所有在Ie·中未处理的事务，至此Follower完成阶段二。

3.3.3.阶段三：广播

完成同步阶段，ZAB协议就可以正式接受客户端新的事务请求，并进行消息广播流程。

步骤L.3.1：Leader L接收到客户端新的事务请求后，会生成对应事务的Proposal，并根据ZXID的顺序向所有Follower发送提案<e·,<v,z>>，其中epoch(z) = e·。

步骤F.3.1： Follower根据消息接收的先后次序来处理这些来自Leader的事务Proposal，并将它们追加到hf中去，之后再反馈给Leader。

步骤L.3.1：当Leader接收到来自过半的Follower针对事务Proposal<e·，<v,z>>的Ack消息后，就会发送Commit<e·，<v,z>>消息给所有的Follower，要求它们进行事务的提交。

步骤F.3.2：当Follower F接收到来自Leader的Commit<e·，<v,z>>消息后，就会开始提交事务Proposal<e·，<v,z>>。

以上就是整个ZAB协议的三个核心工作流程。

ZAB协议算法描述示意图：

3.4.运行分析

在ZAB协议的设计中，每一个进程都有可能处于一下三种状态之一。

• LOOKING：leader选举阶段
• FOLLOWING:Follower服务器和Leader保持同步状态
• LEADING:Leader服务器作为主进程领导状态。

所有进程启动的时候，初始化状态都是LOOKING状态，此时进程中不存在Leader。选举出Leader后马上进入FOLLOWING状态，进行状态同步。我们将处于FOLLOWING状态的进程称为Follower，将处于LEADING状态的进程称为Leader。Leader崩溃后其余的进程马上进入LOOKING状态，并开始进行新一轮的选举。

4.ZAB与Paxos的联系与区别

联系：

• 都存在一个类似于Leader的角色，由其协调多个Follower进行运行
• Leader进程会等待超半数的Follower作出正确的反馈后，才会将一个提案进行提交
• 在ZAB协议中，每个Proposal中都包含了一个epoch值，用来代表当前的Leader周期，在Paxos算法中，同样存在一个这样的标识，只是名字编程了Ballot

区别：

• 在Paxos算法中，一个新选举产生的主进程会进行两个阶段的工作。第一阶段被称为读操作，在这个阶段，这个新的主进程会通过和所有其他进程进行通讯的方式来收集上一个主进程提出的提案，并将它们提交。第二个阶段为写阶段，在这个阶段，当前主进程开始提出它自己的提案。
• 在Paxos基础上，ZAB协议额外添加了一个同步阶段。在同步阶段之前，ZAB协议也存在一个和Paxos算法读阶段很类似的过程称为发现（Discovery）阶段。在同步阶段，新的Leader会确保存在过半的Follower已经提交了之前Leader周期中的所有事务Proposal。这一阶段的引入，能够有效保证Leader在新的周期中提出事务Proposal之前，所有的进程都已经完成了对之前所有事务Proposal的提交。

综上，两者的本质区别在于，设计目标不太一致。ZAB协议主要用于构建一个高可用的布式数据主备系统。例如ZooKeeper。而Paxos算法则是用于构建一个分布式的一致性状态机系统。

来自《从paxos到zookeeper 分布式一致性原理与实战》，稍微进行了归纳总结。