深入理解ZAB协议

从以下四个方面来深入ZAB协议

系统模型

II = {P1,P2,P3…Pn}：代表一组进程组成的分布式系统，UP、DOWN代表正常和崩溃

Q(Quorum)：“过半”进程处于UP状态的一组子集

Q∈II，Q1∩Q2≠∅，Pi和Pj代表两个进程，Cij代表Pi和Pj之间的网络通信通道

完整性：Pi收到Pj的消息M1，那么Pj一定发送了消息M1

前置性：在Pi接收到的消息中，如果m'是m的前置消息，那么Pi必定先接收到m'，然后才接收到m

问题描述

Zookeeper是一个高可用的分布式协调服务，在很多大型系统上得到应用，这类系统有一个共同的特定，即存在大量的客户端进程，并且都依赖Zookeeper完成一系列诸如可靠的存储配置和运行时状态记录等分布式协调工作，因此Zookeeper必须具备高吞吐和低延迟的特性，并且能够在高并发情况下完成数据一致性的处理，同时能优雅的处理故障并从中恢复过来。

ZAB协议是整个Zookeeper的核心所在，其规定了任何时候都只有一个主进程负责进行消息的广播，如果主进程崩溃，那么就选举出新的主进程，同时产生一个唯一的序列号e标识“主进程的周期”，存在主进程Pe'在Pe之前，那么e'<e。主进程的选举机制和消息广播机制是密切相关的，为了保证主进程每次广播出来的消息是一致的，只有在完成崩溃恢复阶段之后，新的主进程才能进行新的事务消息广播。为了实现这一过程，ZAB协议会通过类似函数调用（ready(e)）的方式告知上层系统（主/副进程）是否可以开始事务消息的广播。在消息广播的时候，主进程使用系列号来设置事务标识中的epoch字段。

每个进程都存在类似transactions(v, z)的函数调用，v代表事务内容，z代表事务标识，同时z=<e,c>，e代表主进程周期epoch(z)，e代表当前主进程周期中的事务计数counter(z)。

如果一个事务标识z'优先于另一个事务z，那么有两种情况：epoch(z')<epoch(z)或者epoch(z')=epoch(z) and counter(z')<counter(z)。

算法描述

整个ZAB协议包括消息广播和崩溃恢复两个过程，可以细分为三个阶段：发现、同步、广播。我们来这三个阶段的详细算法流程。

阶段一：发现

主要是Leader选举过程。

首先，Follower将自己最后接受到的事务Proposal的epoch值发送给准Leader；

然后，Leader接受到过半Follower的epoch后，选出最大的epoch值加1生成新的epoch发送给这些过半的Follower；

最后，Follower接受到新的epoch值监测是否大于自己最后接受到的epoch值，如果是则更新epoch，并反馈消息ACK-E(F.p,hf)，包含最后接受的epoch，hf为该Follower的历史事务Proposal集合。Leader 接受到过半Follower的反馈之后，会选出这些过半服务器中的一个Follower，并将其作为初始化事务的集合Ie'

阶段二：同步

发现阶段之后，进入同步阶段。

第一步，Leader发送NEWLEADER(e',Ie')消息给Quorum中所有的Follower，e'代表epoch值，Ie'代表初始化事务Proposal的集合

第二步，Follower接受到NEWLEADER(e',Ie')消息之后，判断自己的epoch值是否等于e'，如果不是直接进入下一轮循环，因为此时自己还处于上一轮或者更上一轮，无法进行同步。如果epoch=e'，那么Follower会执行初始化事务Proposal集合中的事务操作，最后Follower会反馈给Leader，表明自己已经处理完所有的事务Proposal。

第三步，Leader接收到过半Follower的NEWLEADER(e',Ie')反馈消息之后，会向所有Follower的发送Commit消息，至此Leader完成了阶段二

第四步，Follower接收到Leader的Commit消息，会依次处理并提交所有未处理的事务，至此Follower完成了阶段二

阶段三：广播

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

第一步，Leader接受到客户端新的事务请求之后，会生成对应的事务Proposal，并根据ZXID顺序想所有Follower发出提案<e',<v,z>>，epoch(z)=e'

第二步，Follower接受到提案后，会依次处理事务Proposal，并将处理过的事务加入到历史事务集合hf，之后反馈给Leader

第三步，Leader接收到过半的Follower针对Proposal<e',<v,z>>的ACK之后，会向所有的Follower发送Commit<e',<v,z>>，要求他们提交事务

第四步，Follower接收到Leader发送的Commit<e',<v,z>>之后，开始提交Proposal<e',<v,z>>，并且在此之前Follower已经提交过Proposal<v',z'>，<v',z'>∈hf,z'<z

算法描述示意图

运行分析

每个进程都可能出现三种状态：LOOKING（Leader选举阶段）、FOLLOWERING（Follower服务器和Leader服务器同步状态）、LEADING（Leader服务器作为主进程的状态）

组成ZAB协议的所有进程启动的时候，初始化状态都是LOOKING，然后每个进程都会尝试选举出一个新Leader，当Leader被选出后，Leader服务器会切换成LEADING状态，其他Follower则切换成FOLLOWERING状态，之后Leader和所有Follower之间通过心跳检测机制来感知彼此的状况，在所有进程运行的过程中Leader可能随时崩溃或者断开TCP连接，如果在指定超时时间内Leader无法从过半的Follower进程那里接收到心跳检测，或者断开TCP连接，那么Leader会放弃当前周期的领导，状态转换为LOOKING，Follower也会放弃Leader状态转换为LOOKING，进行新一轮的选举。所以整个过程每一个进程都有可能处于三种状态中的某一种状态。

ZAP协议和Paxos算法的联系和区别

未完待续………………..