ZAB 协议是为分布式协调服务 ZooKeeper 专门设计的一种支持崩溃恢复的原子广播协议。具体的，ZooKeeper 使用一个单一的主进程来接收并处理客户端的所有事务请求，并采用 ZAB 的原子广播协议，将服务器数据的状态变更以事务 Proposal 的形式广播到所有的副本进程上。ZAB 协议的主备模型架构保证了同一时刻集群中只能够有一个主进程来广播服务器的状态变更。此外，考虑到在分布式环境中，顺序执行的一些状态变更其前后会存在一定的依赖关系，有些状态变更必须依赖于比它早生成的那些状态变更，因此，ZAB 协议必须能够保证一个全局的变更序列被顺序应用。最后，考虑到主进程在任何时候都有可能出现崩溃或重启，ZAB 协议还需要保证当前主进程在出现异常时，整个集群还能正常工作。

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

为什么 ZooKeeper 没用兰伯特的 Multi-Paxos 实现各节点数据的共识和一致呢？因为兰伯特的 Multi-Paxos 虽然能保证达成共识后的值不再改变，但它不关心达成共识的值是什么，也无法保证各值（也就是操作）的顺序性。而这正是 ZAB 协议着力解决的问题，也是理解 ZAB 协议的关键。

如何实现操作的顺序性

假如节点 A、B、C 组成的一个分布式集群，我们要设计一个算法，来保证指令（比如 X、Y）执行的顺序性，比如，指令 X 在指令 Y 之前执行，那我们该如何设计这个算法呢？
image.png

1. 为什么 Multi-Paxos 无法保证操作顺序性？

假设当前所有节点上的被选定指令，最大序号都为 100，那么新提议的指令对应的序号就会是 101。首先节点 A 是领导者，提案编号为 1，提议了指令 X、Y，对应的序号分别为 101 和 102，但是因为网络故障，指令只成功复制到了节点 A。
image.png
假设这时节点 A 故障了，新当选的领导者为节点 B。节点 B 当选领导者后，需要先作为学习者了解目前已被选定的指令。节点 B 学习后，发现当前被选定指令的最大序号为 100（因为节点 A 故障了，它被选定指令的最大序号 102，无法被节点 B 发现），那么它可以从序号 101 开始提议新的指令。这时它接收到客户端请求，并提议了指令 Z，指令 Z 被成功复制到节点 B、C。
image.png
假设这时节点 B 故障了，节点 A 恢复了，选举出领导者 C 后，节点 B 故障也恢复了。节点 C 当选领导者后，需要先作为学习者了解目前已被选定的指令，这时它执行 Basic Paxos 的准备阶段，就会发现之前选定的值（比如 Z、Y），然后发送接受请求，最终在序号 101、102 处达成共识的指令是 Z、Y。
image.png
在这里，你可以看到，原本预期的指令是 X、Y，最后变成了 Z、Y。这个过程，很明显的验证了 Multi-Paxos 虽然能保证达成共识后的值不再改变，但它不关心达成共识的值是什么。那 Raft 也可以实现操作的顺序性，为什么 ZooKeeper 不用 Raft 呢？因为 Raft 出来的比较晚，直到 2013 年才正式提出，在 2007 年开发 ZooKeeper 时，还没有 Raft 呢。所以 ZooKeeper 采用了 ZAB 协议实现了操作的顺序性。

2. ZAB 如何实现操作的顺序性？

还是以 X、Y 指令为例，假设节点 A 为主节点，节点 B、C 为备份节点。首先，需要注意的是，在 ZAB 中，写操作必须在主节点（比如节点 A）上执行。如果客户端访问的节点是备份节点（比如节点 B），它会将写请求转发给主节点。接着，当主节点接收到写请求后，会基于写请求中的指令来创建一个提案（Proposal）并使用一个唯一的 ID 来标识这个提案。这里的唯一 ID 就是指事务标识（zxid），就像下图的样子。
image.png
可以看到，X、Y 对应的事务标识符分别为 <1, 1> 和 <1, 2>。实际上，事务标识符是 64 位的 long 型变量，有任期编号 epoch 和计数器 counter 两部分组成，高 32 位为任期编号，低 32 位为计数器：

  • 任期编号，就是创建提案时领导者的任期编号。当新领导者当选时，任期编号递增，计数器重置为零。
  • 计数器，就是具体标识提案的整数。每次领导者创建新的提案时，计数器将递增。

为什么要这么设计呢？因为事务标识必须按照顺序、唯一标识一个提案，即事务标识必须是唯一递增的。

在创建完提案之后，主节点会基于 TCP 协议，并按照顺序将提案广播到其他节点。这样就能保证先发送的消息，会先被收到，保证了消息接收的顺序性。
image.png
然后，当主节点接收到指定提案的“大多数”的确认响应后，该提案将处于提交状态（Committed），主节点会通知备份节点提交该提案。
image.png
主节点提交提案是有顺序性的。主节点根据事务标识大小，按照顺序提交提案，如果前一个提案未提交，此时主节点是不会提交后一个提案的。也就是说，指令 X 一定会在指令 Y 之前提交。

最后，当写操作执行完后，接下来你可能需要执行读操作了。为了提升读并发能力，Zookeeper 提供的是最终一致性，也就是读操作可以在任何节点上执行，客户端会读到旧数据。如果客户端必须要读到最新数据，Zookeeper 提供了 sync 命令，可以在执行读操作前先执行 sync 命令，这样客户端就能读到最新数据了。

处理写请求

在 ZooKeeper 中，写请求是必须在领导者上处理，如果跟随者接收到了写请求，它需要将写请求转发给领导者，当写请求对应的提案被复制到大多数节点上时，领导者会提交提案，并通知跟随者提交提案。而读请求可以在任何节点上处理，也就是说，ZooKeeper 实现的是最终一致性。

写请求执行过程：
image.png
ZAB 协议的广播过程类似事务的二阶段提交过程，但 ZAB 协议不需要等待集群中所有的 Follower 服务器都反馈响应。另外，整个消息广播协议是基于具有 FIFO 特性的 TCP 协议来进行网络通信的，因此能够很容易地保证消息广播过程中消息接收与发送的顺序性。

同时，由于 ZAB 协议需要保证每一个消息严格的因果关系，因此必须将每一个事务 Proposal 按照其 ZXID 的先后顺序来进行排序与处理。具体的，在消息广播过程中，Leader 服务器会为每一个 Follower 服务器都各自分配一个单独的队列，然后将需要广播的事务 Proposal 依次放入队列中，并根据 FIFO 策略进行消息发送。每一个 Follower 在接收到这个事务 Proposal 后，都会首先将其以事务日志的形式写入到本地磁盘中去，并且在成功写入后反馈给 Leader 一个 ack 响应。当 Leader 接收到超过半数 Follower 的 ack 响应后，就会广播一个 commit 消息给所有 Follower 以通知其进行事务提交，同时 Leader 自身也会完成对事务对提交。

领导者选举

领导者选举，关乎着节点故障容错能力和集群可用性，是 ZAB 协议非常核心的设计之一。同时，Leader 选举算法不仅需要让 Leader 自己知道其自身已经被选举为 Leader， 同时还需要让集群中的所有其他机器也能够快速感知到选举产生的新的 Leader 服务器。

1. 集群成员身份

既然要选举领导者，那就涉及成员身份变更，那在 ZAB 中支持哪些成员身份呢？ZAB 支持 3 种成员身份（领导者、跟随者、观察者）。

  • 领导者（Leader）： 作为主（Primary）节点，在同一时间集群只会有一个领导者。所有的写请求都必须在领导者节点上执行。

  • 跟随者（Follower）：作为备份（Backup）节点， 集群可以有多个跟随者，它们会响应领导者的心跳，并参与领导者选举和提案提交的投票。跟随者可以直接处理并响应来自客户端的读请求，但对于写请求，跟随者需要将它转发给领导者处理。

  • 观察者（Observer）：作为备份（Backup）节点，类似跟随者，但是没有投票权，也就是说，观察者不参与领导者选举和提案提交的投票。

2. 如何选举领导者？

一个节点要成为新的 Leader，必须获得集群中过半节点的支持。举个例子，假设投票信息的格式是 <proposedLeader, proposedEpoch, proposedLastZxid, node>：

  • proposedLeader：节点提议的领导者集群节点 ID，即在集群配置（比如 myid 配置文件）时指定的 ID。
  • proposedEpoch：节点提议的领导者的任期编号。
  • proposedLastZxid：节点提议的领导者的事务标识最大值，也就是最新提案的事务标识。
  • node：投票的节点。

假设一个 ZooKeeper 集群，由节点 A、B、C 组成，其中节点 A 是领导者，节点 B、C 是跟随者。假设节点 B、C 的 epoch 都是 1，lastZxid 分别是 101 和 102，集群 ID 分别为 2 和 3。此时，如果主节点 A 宕机了，会如何选举呢？
image.png
首先，当跟随者检测到连接领导者节点的读操作等待超时了，跟随者会变更节点状态，将自己的节点状态变更成 LOOKING，然后发起领导者选举：
image.png
接着，每个节点会创建一张选票，这张选票是投给自己的，也就是说，节点 B、C 都推荐自己为领导者，并创建选票 <2, 1, 101, B> 和 <3, 1, 102, C>，然后各自将选票发送给集群中所有节点，也就是说，B 发送给 B、C，C 也发送给 B、C。

一般而言，节点会先接收到自己发送给自己的选票（因为不需要跨节点通讯，传输更快），即 B 会先接收到来自 B 的选票，C 会先接收到来自 C 的选票：
image.png
集群的各节点收到选票后，为了选举出数据最完整的节点，对于每一张接收到选票，节点都需要进行领导者 PK，也就将选票提议的领导者和自己提议的领导者进行比较，找出更适合作为领导者的节点，PK 规则如下：

  • 优先检查任期编号（Epoch），任期编号大的节点作为领导者；
  • 如果任期编号相同，比较事务标识的最大值，值大的节点作为领导者；
  • 如果事务标识的最大值相同，比较集群节点 ID，集群节点 ID 大的节点作为领导者。

如果选票提议的领导者，比自己提议的领导者，更适合作为领导者，那么节点将调整选票内容，推荐选票提议的领导者作为领导者。当节点 B、C 接收到的选票后，因为选票提议的领导者与自己提议的领导者相同，所以，领导者 PK 的结果，是不需要调整选票信息，那么节点 B、C，正常接收和保存选票就可以了。
image.png
接着节点 B、C 分别接收到来自对方的选票，比如 B 接收到来自 C 的选票，C 接收到来自 B 的选票：
image.png
对于 C 而言，它提议的领导者是 C，而选票（<2, 1, 101, B>）提议的领导者是 B，但因为节点 C 的事务标识的最大值比节点 B 的大，按照 PK 规则，相比节点 B，节点 C 更适合作为领导者，因此，节点 C 不需要调整选票信息，正常接收和保存选票就可以了。

但对于对于节点 B 而言，它提议的领导者是 B，选票（<3, 1, 102, C>）提议的领导者是 C，因为节点 C 的任期编号与节点 B 相同，但节点 C 的事务标识的最大值比节点 B 的大，按照 PK 规则，相比节点 B，节点 C 应该作为领导者，所以，节点 B 除了接收和保存选票信息，还会更新自己的选票为 <3, 1, 102, B>，也就是推荐 C 作为领导者，并将选票重新发送给节点 B、C：
image.png
接着，当节点 B、C 接收到来自节点 B 新的选票时，因为这张选票（<3, 1, 102, B>）提议的领导者，与他们提议的领导者是一样的，都是节点 C，所以，他们正常接收和存储这张选票就可以。
image.png
最后，因为节点 C 赢得大多数选票（2 张选票），那么节点 B、C 将根据投票结果，变更节点状态，并退出领导者选举。比如，因为当选的领导者是节点 C，那么节点 B 将变更状态为 FOLLOWING，并退出选举，而节点 C 将变更状态为 LEADING，并退出选举。
image.png
领导者选举的目标，是从大多数节点中选举出数据最完整的节点，也就是大多数节点中，事务标识符值最大的节点。另外，ZAB 本质上是通过“见贤思齐，相互推荐”的方式来选举领导者的。也就说，根据领导者 PK，节点会重新推荐更合适的领导者，最终选举出了大多数节点中数据最完整的节点。

故障恢复

领导者选举只是选举了一个适合当领导者的节点，然后把这个节点的状态设置成 LEADING 状态。此时，这个节点还不能作为主节点处理写请求，也不能使用领导职能。因为集群还没有从故障中恢复过来，而成员发现和数据同步会解决这个问题。成员发现和数据同步不仅让新领导者正式成为领导者，确立了它的领导关系，还解决了各副本的数据冲突，实现了数据副本的一致性。这样集群就能正常处理写请求了。

  • 确立领导关系，也就是在成员发现（DISCOVERY）阶段，领导者和大多数跟随者建立连接，并再次确认各节点对自己当选领导者没有异议，确立自己的领导关系；

  • 处理冲突数据，也就是在数据同步（SYNCHRONIZATION）阶段，领导者以自己的数据为准，解决各节点数据副本的不一致。注意，基于“大多数”的提交原则和选举原则，能够确保被复制到大多数节点并提交的提案，就不再改变。

1. 如何确立领导关系？

我们知道，选举出的领导者，是在成员发现阶段确立领导关系的。在当选后，领导者会递增自己的任期编号，并基于任期编号值的大小，来和跟随者协商，最终建立领导关系。具体就是跟随者会选择任期编号值最大的节点作为自己的领导者，而被大多数节点认同的领导者，将成为真正的领导者。

假设一个 ZooKeeper 集群，由节点 A、B、C 组成。其中，领导者 A 已经宕机，C 是新选出来的领导者，B 是新的跟随者，假设 B、C 已提交提案的事务标识最大值分别是 <1, 10> 和 <1, 11>，其中 1 是任期编号，10、11 是事务标识符中的计数器值，A 宕机前的任期编号也是 1。那么 B、C 如何协商建立领导关系呢？

首先，B、C 会把自己的 ZAB 状态设置为成员发现（DISCOVERY），这就表明，选举（ELECTION）阶段结束了，进入了下一个阶段。接下来，B 会主动联系 C，发送给它包含自己接收过的领导者任期编号最大值（也就是前领导者 A 的任期编号，1）的 FOLLOWINFO 消息。
image.png
当 C 接收来自 B 的信息时，它会将包含自己事务标识符最大值的 LEADINFO 消息发给跟随者。注意，领导者进入到成员发现阶段后，会对任期编号加 1，创建新的任期编号，然后基于新任期编号，创建新的事务标识符。在这个例子中，就是 <2, 0>。
image.png
当接收到领导者的响应后，跟随者会判断领导者的任期编号是否最新，如果不是，就发起新的选举；如果是，跟随者返回 ACKEPOCH 消息给领导者。在这里，C 的任期编号（也就是 2）大于 B 接受过的其他领导任期编号（也就是旧领导者 A 的任期编号 1），所以 B 返回确认响应给 C 并设置 ZAB 状态为数据同步。
image.png
最后，当领导者接收到来自大多数节点的 ACKEPOCH 消息时，就设置 ZAB 状态为数据同步。在这里，C 接收到 B 的消息再加上 C 自己就是大多数了，所以，在接收到来自 B 的消息后 C 设置 ZAB 状态为数据同步。
image.png
现在，ZAB 在成员发现阶段确立了领导者的领导关系，之后领导者就可以行使领导职能了。而这时它首先要解决的就是数据冲突，实现各节点数据的一致性，那么它是怎么做的呢？

2. 如何处理冲突数据？

因为 C 已提交提案的事务标识符最大值（也就是 <1, 11>）大于 B 已提交提案的事务标识符最大值（也就是 <1, 10>），所以 C 会用 DIFF 的方式修复数据副本的不一致，并返回差异数据（也就是事务标识符为 <1, 11> 的提案）和 NEWLEADER 消息给 B。然后 B 修复不一致数据，返回 NEWLEADER 消息的确认响应给领导者。
image.png
接着，当领导者接收到来自大多数节点的 NEWLEADER 消息的确认响应，将设置 ZAB 状态为广播。在这里，C 接收到 B 的确认响应，加上 C 自己，就是大多数确认了。所以，在接收到来自 B 的确认响应后，C 设置自己的 ZAB 状态为广播，并发送 UPTODATE 消息给所有跟随者，通知它们数据同步已经完成了。最后当 B 接收到 UPTODATE 消息时就知道数据同步完成了，就设置 ZAB 状态为广播。此时，集群就可以正常处理写请求了。