本文将简要介绍Zookeeper的ZAB协议

基本概念

ZAB VS Base-Paxos

Base-Paxos是通用的分布式一致性算法
ZAB协议不是Base-Paxos的典型实现，而是特别为Zookeeper设计的一种支持崩溃恢复的原子广播协议
相对于ZAB协议，Base-Paxos主要存在2个问题：活锁问题+全序问题
- 活锁问题是指在Base-Paxos算法中，由于并不存在Leader角色，新轮次可以不断抢占旧轮次，如此循环往复，产生活锁
- 全序问题是指如果消息a在消息b之前发送，则所有Server应该看到相同的结果，但Base-Paxos并不保证这一点
ZAB的解决方案
- 为了解决活锁问题，ZAB协议引入了Leader角色，所有的事务请求只能由Leader处理，但是单Leader会存在单点问题，ZAB协议进而引入崩溃恢复模式
- 为了解决全序问题，ZAB协议引入了ZXID（全局单调递增的唯一ID）和利用TCP的FIFO特性

服务器角色

Zookeeper中服务器有三种角色：Leader、Follower和Observer，其中Observer与ZAB协议本身无关

Leader的工作职责
- 事务请求的唯一调度者和处理者，保证集群事务处理的顺序性
- 调度集群内部其他服务器（Follower和Observer）
Follower的工作职责
- 处理非事务请求
- 转发事务请求给Leader服务器
- 参与事务Proposal的投票
- 参与Leader选举投票
Observer的工作职责
- 用于观察并同步集群的最新状态变化
- Observer在工作原理上与Follower基本一致，与Follower的主要区别
  - Observer只提供非事务服务
  - Observer不参与任何形式的投票
- 通常用于在不影响集群事务处理能力的前提下提升集群的非事务处理能力

主备模式架构

Zookeeper实现了一种主备模式的系统架构来保持集群中各副本之间的数据一致性，Zookeeper使用单一的主进程（Leader）来接收并处理客户端的所有事务请求，并采用ZAB协议，将服务器数据的状态变更以事务Proposal的形式广播到所有副本进程（Follower和Observer）

事务请求

所有事务请求必须由一个全局唯一的服务器来协调处理，这样的服务器被称为Leader，而其他服务器则被称为Follower（ZAB协议不考虑Observer）
Leader负责将一个客户端的事务请求转换成为一个事务Proposal，并将该事务Proposal分发给集群中所有的Follower
Leader等待所有的Follower关于事务Proposal的反馈，一旦_半数或以上_的Follower进行了正确地反馈，那么Leader会再次向所有的Follower分发Commit消息，要求其将事务Proposal进行Commit（类似于2PC，但移除了事务回滚，容易导致数据不一致，需要崩溃恢复模式的支持）

半数以上（Follower + Leader）

_半数以上_的服务器能够正常相互通信，保证了不会因网络分区等原因而导致同时出现两组集群服务，因为两个 _半数以上_必然有交集！！

半数或以上（Follower）

半数或以上（Follower）是为了保证半数以上（Follower + Leader）
假若有n-1个Follower，S = sum(半数或以上的Follower + Leader) >= ceil[(n-1)/2]+1

如果n为偶数，即n=2k，S >= ceil[(n-1)/2]+1 = ceil[(2k-1)/2]+1 = k+1 ，剩下k-1 < k+1
如果n为奇数，即n=2k+1，S >= ceil[(n-1)/2]+1 = ceil[(2k)/2]+1 = k+1 ，剩下k < k+1
假若有2个Follower，半数或以上的Follower为1、2；假若有3个Follower，半数或以上的Follower为2、3

两种模式

ZAB协议运行过程中，存在两种模式：崩溃恢复模式+消息广播模式，模式切换图如下

消息广播模式

示意图

具体过程（类2PC）

针对客户端的事务请求，Leader会为其生成对应的事务Proposal，Leader会为每个事务Proposal分配一个全局单调递增的唯一ID，即ZXID
消息广播过程中，Leader会为每一个Follower都各自分配一个单独的队列，然后将需要广播的事务Proposal依次放入到这些队列中去，并根据FIFO策略进行消息发送
每一个Follower在接收到事务Proposal之后，都会首先将其以_事务日志_的形式写入到本地磁盘中，并且在成功写入后向Leader反馈ACK
当Leader接收到_半数或以上_的Follower反馈的ACK后，就会广播一个Commit消息给所有的Follower以通知其进行事务提交，同时Leader自身也会完成事务提交
每一个Follower接收到Commit消息后，也会完成事务提交

崩溃恢复模式

恢复过程结束后需要选举新Leader，ZAB协议需要一个高效且可靠的Leader选举算法，在选举出准Leader后，需要进行数据同步，同步完成后，准Leader_成为正式Leader_
崩溃恢复阶段需要处理2种特殊情况
- 提交已被Leader Commit的事务
- 丢弃只被Leader Propose的事务

进阶理解

分布式系统模型

进程组 ∏

分布式系统由一组进程构成：∏ = {P1,P2,...,Pn}，各个进程之间通过相互通信来实现消息的传递

进程子集 Quorum

每个进程随时都可能崩溃退出，正常工作的进程处于UP状态，否则处于DOWN状态，_半数以上_处于UP状态的进程构成进程子集Q，Q满足两个条件：∀Q，Q⊆∏，∀Q1和Q2，Q1∩Q2≠∅

网络通信 Cij

Cij表示进程Pi和Pj之间的网络通信，其中Pi∈∏，Pj∈∏，Cij满足完整性和前置性

完整性

如果进程Pj收到来自进程Pi的消息m，那么进程Pi一定确实发送了消息m

前置性

如果进程Pj收到了消息m，那么存在消息m'：如果消息m'是消息m的前置消息，那么Pj务必先接收消息m'，然后再接收消息m，记为m≺m'

问题描述

使用Zookeeper的分布式系统，通常存在大量的客户端进程，依赖Zookeeper来完成类似配置存储等分布式协调工作，因此Zookeeper必须具备以下特性

高吞吐和低延时
在高并发的情况下完成分布式数据的一致性处理
同时能够优雅地处理运行时故障，具备快速从故障中恢复的能力

主进程周期

ZAB协议是Zookeeper框架的核心，任何时候都需要保证只有一个主进程负责消息广播，如果主进程崩溃了，需要选举出新的主进程，随着时间的推移，形成主进程序列：P1,P2...Pe，∀Pe∈∏，e称为主进程周期，如果e小于e'，那么Pe是Pe'之前的主进程，表示为Pe≺Pe'，进程可能会崩溃重启，因此Pe和Pe'本质上可能是同一个进程，只是处于不同的主进程周期而已。为了保证主进程每次广播出来的事务Proposal都是一致的，只有在 _充分完成崩溃恢复阶段_之后，新的主进程才可以开始生成新的事务Proposal并进行消息广播

广播事务Proposal

transactions(v,z)：实现事务Proposal的广播

v为事务Proposal的内容
z为事务Proposal的标识，z=<e,c>
- e为主进程周期，e=epoch(z)
- c为当前主进程周期内的事务计数，c=counter(z)
- 如果z'优先于z，记为z≺z'，有2种情况
  - epoch(z)<epoch(z')：主进程周期不同
  - epoch(z)==epoch(z') && counter(z)<counter(z')：主进程周期相同

算法描述

整个ZAB协议主要包括消息广播和崩溃恢复两个过程，进一步可以细分为发现（Discovery）、同步（Synchronization）和广播（Broadcast）三个阶段，每一个分布式进程会循环执行这三个阶段
崩溃恢复 = 发现+ 同步 = （选举准Leader + 生成新主进程周期） + 同步

术语

术语	说明
F.p	Follower f处理过的`最后一个`事务Proposal
F.zxid	Follower f处理过的历史事务Proposal中`最后一个`事务Proposal的事务标识ZXID
hf	Follower f`已经处理过的事务Proposal序列`
Ie	`准Leader`完成发现阶段后的初始化历史记录

发现：选举准Leader + 生成新主进程周期

发现过程就是Leader选举过程，首先选举准Leader，然后完成epoch的更新（新的主进程周期）和Ie的初始化

选举准Leader

进入Leader选举流程，即机器进入LOOKING状态，有3种情况

机器初始化启动，机器进入LOOKING状态
Follower运行期间无法与Leader保持连接，Follower进入LOOKING状态
Leader无法收到半数或以上 Follower的心跳检测，Leader进入LOOKING状态

当一个机器进入Leader选举流程时，当前集群可能处在两个状态：存在（准）Leader+不存在（准）Leader

术语

术语	说明
SID	Server ID，用来唯一标识一台Zookeeper集群中的机器，全局唯一，与myid一致
ZXID	事务ID，用来唯一标识一次服务器状态的变更，在同一时刻，集群中每一台机器的ZXID不一定完全一致
Vote	当集群中的机器发现自己无法检测到Leader机器的时候，就会尝试开始投票
Quorum	`半数以上`机器，`quorum >= (n/2+1)`

集群存在（准）Leader

当该机器试图去选举准Leader的时候，会被告知当前集群的（准）Leader信息，对于该机器来说，仅仅需要与（准）Leader机器建立连接，并完成数据状态同步既可

集群不存在（准）Leader

集群中的所有机器都处于一种试图选举出一个准Leader的状态，我们把这种状态称为LOOKING，处于LOOKING状态的机器会向集群中的所有其他机器发送消息，这个消息就是投票，投票消息组成：所推举的服务器SID和ZXID，(SID，ZXID)

第1次投票

第1次投票，由于无法检测到集群中其他机器的状态信息，因此每台机器都将自己作为被推举的对象进行投票

变更投票

集群中的每台机器发出自己的投票后，也会接收到来自集群中其他机器的投票，并依据一定的规则，来处理收到的其他机器的投票，并决定是否需要变更自己的投票

术语	说明
vote_sid	接收到的投票中所推举Leader服务器的SID
vote_zxid	接收到的投票中所推举Leader服务器的ZXID
self_sid	当前服务器自己的SID
self_zxid	当前服务器自己的ZXID

变更规则：

vote_zxid > self_zxid ：认可当前收到的选票，并再次将该投票发送出去
vote_zxid < self_zxid ：坚持自己的投票，不做任何变更
vote_zxid == self_zxid && vote_sid > self_sid ：认可当前收到的选票，并再次将该投票发送出去
vote_zxid == self_zxid && vote_sid < self_sid ：坚持自己的投票，不做任何变更

统计投票

如果一台机器收到_半数以上_的相同的投票（包括自身投票），那么这个投票对应的SID即为准Leader

示例

生成新主进程周期

e'：表示新的主进程周期，Ie'：e'对应的初始化历史记录，准Leader L与Follower F的工作流程

Follower F将自己最后接受的事务Proposal的epoch值CEPOCH(F.p)发送给准Leader L
当准Leader L接收来自半数或以上 Follower的CEPOCH(F.p)消息后，从这些CEPOCH(F.p)消息中选取出最大的epoch值，然后加1，即为e'，最后生成NEWEPOCH(e')消息并发送给这些半数或以上 Follower
当Follower接收到来自准Leader L的NEWEPOCH(e')消息后，检查当前的CEPOCH(F.p)是否小于e'，如果是，则将CEPOCH(F.p)更新为e'，同时向准Leader L发送ACK-E消息（包含当前Follower的epoch值CEPOCH(F.p)以及该Follower已经处理过的事务Proposal序列 _hf_）
当准Leader L接收到来自半数或以上_的Follower的ACK-E消息后，准Leader L会从这半数或以上_的Follower中选取一个Follower F，并将其 _hf_作为初始化历史记录Ie'，假若选取F，那么∀F'∈Q，满足下面的其中1个条件
- CEPOCH(F'.p)<CEPOCH(F.p)
- CEPOCH(F'.p)==CEPOCH(F.p) && (F'.zxid≺F.zxid || F'.zxid==F.zxid )

同步：准Leader ➔ 正式Leader

准Leader L与与Follower F的工作流程

准Leader L向Quorum中的Follower发送NEWLEADER(e',Ie')消息
当Follower F接收到准Leader L的NEWLEADER(e',Ie')消息后
- 如果Follower F的CEPOCH(F.p)≠e'，不参与本轮的同步，直接进入发现阶段
- 如果CEPOCH(F.p)=e'，那么Follower会执行事务应用操作，即∀<v,z>∈Ie'，Follower都会接受<e',<v,z>>，最后Followe会向准Leader L发送ACK-LD消息，表示已经接受并处理Ie'中所有的事务Proposal
当准Leader L接收到半数或以上_的Follower的ACK-LD消息后，向所有的Follower发送Commit-LD消息，此时准Leader L完成同步阶段，成为 _正式Leader
当Follower接收到Commit-LD消息后，就会依次提交所有Ie'中尚未处理的事务Proposal

广播

广播阶段类似于2PC，ZAB协议移除了2PC的事务回滚，因此Follower只能回复ACK或者不回复，Leader主要收到_半数或以上_的ACK，就可以发送Commit，这样的设计很容易带来数据不一致性，因此才需要崩溃恢复模式（Leader选举+数据同步）

工作流程

Leader L接收到客户端新的事务请求后，会生成对应的事务Proposal<e',<v,z>>，并根据ZXID的顺序向所有Follower发送Propose<e',<v,z>>，其中epoch(z)=e'
Follower根据消息接收的先后顺序来处理这些来自Leader的事务Proposal，并将它们追加到hf，之后给Leader反馈ACK消息
当Leader接收到来自半数或以上 Follower针对Propose<e',<v,z>>的ACK消息后，就会向所有Follower发送Commit<e',<v,z>>消息
当Follower接收到来自Leader的Commit<e',<v,z>>消息后，就会开始提交事务Proposal<e',<v,z>>，此时必定已经提交了事务Proposal<e',<v',z'>>，其中<v',z'> ∈ hf，z'≺z

两种特殊情况

提交已被Leader Commit的事务

发生场景

Leader发送Propose请求，Follower F1和Follower F2都向Leader回复了ACK，Leader向所有的Follower发送Commit请求并Commit自身，此时Leader宕机，Leader已经Commit，但Follower尚未Commit，数据不一致

处理方式

选举F.zxid最大的Follower成为新的准Leader，由于旧Leader宕机前，_半数或以上_的Follower曾经发送ACK消息，新的准Leader必然是这半数或以上Follower的一员；新的准Leader会发现自身存在已经Propose但尚未Commit的事务Proposal，新的准Leader会向所有的Follower先发送Propose请求，再发送Commit请求

丢弃只被Leader Propose的事务

发生场景

Leader收到了事务请求，将其包装成了事务Proposal，此时Leader宕机，Follower并没有收到Propose请求，Follower进入选举阶段，选举产生新Leader，旧的Leader重启，以Follower的角色加入集群，此时旧Leader上有一个多余的事务Proposal，数据不一致

处理方式

新的准Leader会根据自己服务器上最后被提交的事务Proposal和Follower的事务Proposal进行对比，然后新的准Leader要求Follower执行一个回退操作，回退到一个已经被集群半数以上机器提交的最新的事务Proposal

三阶段示意图

在正常运行时，ZAB协议一直运行在**`广播阶段`**，如果出现Leader宕机或其他原因导致的Leader缺失，此时ZAB协议会进入**`发现阶段`**

运行分析

运行状态切换

组成ZAB协议的所有进程启动的时候，初始状态为LOOKING
如果进程发现已经存在新的（准）Leader，马上切换到FOLLOWING状态，并开始和（准）Leader保持同步
处于LOOKING状态的进程称为Follower，处于LEADING状态的进程称为Leader
当检测到Leader崩溃或放弃领导地位，其余Follower会切换到LOOKING状态，并开始新一轮的选举
在ZAB协议运行过程中，每个进程的状态都会在LOOKING、FOLLOWING和LEADING之间不断地转换
完成Leader选举阶段，进程成为准Leader，完成数据同步阶段，准Leader成为正式Leader
- 准Leader接收来自半数或以上的Follower进程针对Le'的NEWLEADER(e',Ie')的ACK-LD消息，那么Le'正式成为了周期e'的Leader
- 在原子广播阶段，Leader会为每一个与自己保持同步的Follower创建一个操作队列，Leader与所有的Follower之间需要通过心跳检测机制来感知彼此。如果在指定的超时时间内Leader无法从半数或以上的Follower那里接收到心跳检测或者TCP连接断开，Leader和所有的Follower都会切换到LOOKING状态

参考资料

从Paxos到Zookeeper