今天是分布式一致性算法的第三个——ZAB 算法。

关于 ZAB 算法

ZAB协议，全称 Zookeeper Atomic Broadcast（Zookeeper 原子广播协议）。它是专门为分布式协调服务——Zookeeper，设计的一种支持 崩溃恢复 和 原子广播 的协议。

从设计上看，ZAB协议和 Raft 很类似。ZooKeeper集群中，只有一个Leader节点，其余均为Follower节点。整个ZAB协议一共定义了四个阶段：选举（Leader Election）、 发现（Discovery） 、 同步（Synchronization） 、 广播（Broadcast） 。

ZAB借鉴了Paxos算法，但又不像Paxos那样，是一种通用的分布式一致性算法。

在Zookeeper中主要依赖ZAB 协议来实现数据一致性，基于该协议，zk实现了一种主备模型（即Leader和Follower模型）的系统架构来保证集群中各个副本之间数据的一致性。 这里的主备系统架构模型，就是指只有一台客户端（Leader）负责处理外部的写事务请求，然后 Leader 客户端将数据同步到其他 Follower 节点。

Zookeeper 客户端会随机的链接到 zookeeper 集群中的一个节点，如果是读请求，就直接从当前节点中读取数据；

如果是写请求，那么节点就会向 Leader 提交事务，Leader 接收到事务提交，会广播该事务，只要超过半数节点写入成功，该事务就会被提交。

特点

相比Paxos，Zab最大的特点是保证强一致性(strong consistency，或叫线性一致性linearizable consistency)。

  1. ZAB 协议需要确保那些已经在 Leader 服务器上提交（Commit）的事务最终被所有的服务器提交。

  2. ZAB 协议需要确保丢弃那些只在 Leader 上被提出而没有被提交的事务。

zab 协议特性

作用

  1. 使用一个单一的主进程（Leader）来接收并处理客户端的事务请求（也就是写请求），并采用了Zab的原子广播协议，将服务器数据的状态变更以事务 proposal （事务提议）的形式广播到所有的副本（Follower）进程上去。

  2. 保证一个全局的变更序列被顺序引用。

    Zookeeper是一个树形结构，很多操作都要先检查才能确定是否可以执行，比如P1的事务t1可能是创建节点”/a”，t2可能是创建节点”/a/bb”，只有先创建了父节点”/a”，才能创建子节点”/a/b”。

    为了保证这一点，Zab要保证同一个Leader发起的事务要按顺序被apply，同时还要保证只有先前Leader的事务被apply之后，新选举出来的Leader才能再次发起事务。

  3. 当主进程出现异常的时候，整个zk集群依旧能正常工作。

直观理解：Zookeeper分布式一致性协议ZAB

基于ZAB协议，Zookeeper实现一种主备模式的系统架构来保持集群中主备副本之间数据的一致性。

ZAB算法分为两大块内容，消息广播 和 崩溃恢复。

  • 消息广播（boardcast）：Zab 协议中，所有的写请求都由 leader 来处理。正常工作状态下，leader 接收请求并通过广播协议来处理。
  • 崩溃恢复（recovery）：当服务初次启动，或者 leader 节点挂了，系统就会进入恢复模式，直到选出了有合法数量 follower 的新 leader，然后新 leader 负责将整个系统同步到最新状态。

下面来详细介绍这两种基本模式的实现过程：

消息广播

角色

消息广播是 Zookeeper 用来保证写入一致性的方法，在 Zookeeper 集群中，存在三种角色的节点：

  • Leader：Zookeeper集群的核心角色，在集群启动或崩溃恢复中通过 Follower 参与选举产生，为客户端提供读写服务，并对事务请求进行处理。
  • Follower：Zookeeper 集群的核心角色，在集群启动或崩溃恢复中参加选举，没有被选上就是这个角色，为客户端提供读取服务，也就是处理非事务请求，Follower 不能处理事务请求，对于收到的事务请求会转发给Leader。
  • Observer：观察者角色，不参加选举，为客户端提供读取服务，处理非事务请求，对于收到的事务请求会转发给 Leader。使用 Observer 的目的是为了扩展系统，提高读取性能。

img

过程

下面通过几张图对ZAB的消息广播过程进行简单的介绍：

  1. Zookeeper各节点会接收来自客户端的请求，如果是非事务请求，各节点自行进行相应的处理。若接收到的是客户端的事务请求，如果当前节点是Follower则将该请求转发给当前集群中的Leader节点进行处理。

    处理

  2. Leader接收到事务处理的请求后，将向所有的Follower节点发出Proposal提议，并等待各Follower的Ack反馈。

    在广播事务之前Leader服务器会先给这个事务分配一个全局单调递增的唯一ID，也就是事务ID（zxid），每一个事务必须按照zxid的先后顺序进行处理。

    而且Leader服务器会为每一个Follower分配一个单独的队列，然后将需要广播的事务放到队列中。

    广播

  3. 各Follower节点对Leader节点的Proposal进行Ack反馈，Leader对接收到的Ack进行统计，如果超多半数Follower进行了Ack，此时进行下一步操作，否则之间向客户端进行事务请求失败的Response。

    超过一半

  4. 如果Leader节点接收到了超过半数的Ack响应，此时Leader会向所有的Follower发出事务Commit的指令，同时自己也执行一次Commit，并向客户端进行事务请求成功的Response。

    成功

zookeeper 采用 Zab 协议的核心，就是只要有一台服务器提交了 Proposal，就要确保所有的服务器最终都能正确提交 Proposal。

这也是 CAP/BASE 实现最终一致性的一个体现。

Leader 服务器与每一个 Follower 服务器之间都维护了一个单独的 FIFO 消息队列进行收发消息，使用队列消息可以做到异步解耦。

Leader 和 Follower 之间只需要往队列中发消息即可。

如果使用同步的方式会引起阻塞，性能要下降很多。

丢弃的事务proposal处理过程：

ZAB协议中使用ZXID作为事务编号，ZXID为64位数字，低32位为一个递增的计数器，每一个客户端的一个事务请求时Leader产生新的事务后该计数器都会加1， 高32位为Leader周期epoch编号，当新选举出一个Leader节点时Leader会取出本地日志中最大事务Proposal的ZXID解析出对应的epoch把该值加1作为新的epoch，将低32位从0开始生成新的ZXID；

ZAB使用epoch来区分不同的Leader周期，能有效避免了不同的leader服务器错误的使用相同的ZXID编号提出不同的事务proposal的异常情况，大大简化了提升了数据恢复流程；

所以这个崩溃的机器启动时，也无法成为新一轮的Leader，因为当前集群中的机器一定包含了更高的epoch的事务proposal。

Zookeeper的消息广播过程类似 2PC（Two Phase Commit），ZAB 仅需要超过一半以上的Follower返回 Ack 信息就可以执行提交，大大减小了同步阻塞，提高了可用性。

ZAB协议简化了2PC事务提交：

  1. 去除中断逻辑移除，follower要么ack，要么抛弃Leader；
  2. leader不需要所有的Follower都响应成功，只要一个多数派ACK即可。

崩溃恢复

在 Zookeeper 集群启动、运行过程中，如果 Leader 出现崩溃、网络断开、服务停止或重启等异常情况，或集群中有新服务器加入时，ZAB 会让当前集群快速进入崩溃恢复模式并选举出新的 Leader 节点，在此期间，整个集群不对外提供任何读取服务。

当产生新的 Leader 后，并且集群中有过半的 Follower 完成了与 Leader 的状态同步，那么 ZAB 协议就会让 Zookeeper 集群从崩溃恢复模式转换成消息广播模式。

崩溃恢复的目的就是保证当前Zookeeper集群快速选举出一个新的Leader并完成与其他Follower的状态同步，以便尽快进入消息广播模式对外提供服务。

Zookeeper崩溃恢复的主要任务就是选举Leader（Leader Election），Leader选举分两个场景：一个是Zookeeper服务器启动时Leader选举，另一个是Zookeeper集群运行过程中Leader崩溃后的Leader选举。

参数

在详细介绍Leader选举过程之前，需要先介绍几个参数：

  • myid: 服务器ID，这个是在安装 Zookeeper 时配置的，myid 越大，该服务器在选举中被选为 Leader 的优先级会越大。

  • zxid: 事务ID，这个是由 Zookeeper 集群中的 Leader 节点进行 Proposal 时生成的全局唯一的事务ID，由于只有 Leader 才能进行Proposal，所以这个zxid很容易做到全局唯一且自增。因为 Follower 没有生成zxid的权限。zxid越大，表示当前节点上提交成功了最新的事务，这也是为什么在崩溃恢复的时候，需要优先考虑zxid的原因。

  • epoch: 投票轮次，每完成一次Leader选举的投票，当前Leader节点的epoch会增加一次。在没有Leader时，本轮此的epoch会保持不变。

优先选择 myid + zxid 最大的数据。

另外在选举的过程中，每个节点的当前状态会在以下几种状态之中进行转变。

1
2
3
4
5
6
7
LOOKING: 竞选状态。 

FOLLOWING: 随从状态，同步Leader 状态，参与Leader选举的投票过程。 

OBSERVING: 观察状态，同步Leader 状态，不参与Leader选举的投票过程。 

LEADING: 领导者状态。

集群启动时的 Leader 选举

假设现在存在一个由5个Zookeeper服务器组成的集群Sever1，Sever2，Sever3，Sever4和Sever5，集群的myid分别为：1， 2，3，4，5。

依次按照myid递增的顺序进行启动。

由于刚启动时zxid和epoch都为0，因此Leader选举的关键因素成了myid。

  1. 启动Sever1，此时整个集群中只有Sever1启动，Sever1无法与其他任何服务建立通信，立即进入LOOKING状态，此时Server1给自己投1票（上来都觉得自己可以做Leader），由于1不大于集群总数的一半，即2，此时Sever1保持LOOKING状态。
  2. 启动Sever2，此时Sever2与Server1建立通信，Sever1和Sever2互相交换投票信息，Server1投票的myid为1，Server2投票的myid为2，此时选取myid最大的，因此Sever1的投票会变成2，但是由于目前投票Server2的服务器数量为2台，小于集群总数的一半2，因此Sever1和Sever2继续保持LOOKING状态。
  3. 启动Sever3，此时三台服务器之间建立了通信，Server3进入LOOKING状态，并与前两台服务器交换投票信息，Server1和Server2的投票信息为2，Server3投票自己，即myid为3，这个时候选择myid最大的作为Leader。此时集群中投票3的服务器数量变成了3台，此时3>2，Sever3立刻变成LEADING状态，Sever1和Sever2变成FOLLOWING状态。
  4. 启动Sever4，Sever4进入LOOKING状态并与前三台服务器建立通信，由于集群中已经存在LEADING状态的节点，因此，Sever4立刻变为FOLLOWING状态，此时Sever3依旧处于LEADING状态。
  5. 启动动Sever5，Sever5与Sever4一样，在与其他服务器建立通信后会立刻变为FOLLOWING状态，此时Sever3依旧处于LEADING状态。

最终整个Zookeeper集群中，Server3成为Leader，Server1，Server2，Server4和Server5成为Follower，最终Server3的epoch加一。

ps: 启动时，都给自己投一票，选举时，优先按照 myid 对比。超过一半的数量，则成为 leader。

Leader 崩溃时的 Leader 选举

在Zookeeper集群刚启动的时候，zxid和epoch并不参与群首选举。

但是如果Zookeeper集群在运行了一段时间之后崩溃了，那么epoch和zxid在Leader选举中的重要性将大于myid。

重要性的排序为：epoch > zxid > myid。

当某一个Follower与Leader失去通信的时候，就会进入Leader选举，此时Follower会跟集群中的其他节点进行通信，但此时会存在两种情况：

1) Follower与Leader失去通信，但此时集群中的Follower并未崩溃，且与其他Follower保持正常通信。此时当该Follower与其他Follower进行通信时，其他Follower会告诉他，老大还活着，这个时候，Follower仅需要与Leader建立通信即可。
2) Leader真的崩溃了，此时集群中所有节点之间会进行通信，当得知老大挂了之后，每个节点都会开启争老大模式，各自会将当前节点最新的epoch，zxid和myid发送出来，参与投票，此时各节点之间会参照 epoch > zxid > myid 进行Leader选举，最后投票数超过集群数量一般的节点会成为新的Leader。

这种崩溃后的Leader选举机制也很好理解，如果Leader挂了，优先选择集群中最后做过（epoch）Leader的节点为新的Leader节点，其次选取有最新事务提交的节点（zxid）为Leader，最后才按默认的最大机器编号（myid）进行投票。

保持数据一致性

ZooKeeper从以下几点保证了数据的一致性

顺序一致性

来自任意特定客户端的更新都会按其发送顺序被提交。

也就是说，如果一个客户端将Znode z的值更新为a，在之后的操作中，它又将z的值更新为b，则没有客户端能够在看到z的值是b之后再看到值a（如果没有其他对z的更新）。

原子性

每个更新要么成功，要么失败。这意味着如果一个更新失败，则不会有客户端会看到这个更新的结果。

单一系统映像

一个客户端无论连接到哪一台服务器，它看到的都是同样的系统视图。

这意味着，如果一个客户端在同一个会话中连接到一台新的服务器，它所看到的系统状态不会比在之前服务器上所看到的更老。

当一台服务器出现故障，导致它的一个客户端需要尝试连接集合体中其他的服务器时，所有滞后于故障服务器的服务器都不会接受该连接请求，除非这些服务器赶上故障服务器。

持久性

一个更新一旦成功，其结果就会持久存在并且不会被撤销。

这表明更新不会受到服务器故障的影响。

Zab特殊情况下需要解决的两个问题

崩溃恢复过程中，为了保证数据一致性需要处理特殊情况：

  1. 已经被Leader提交的proposal确保最终被所有的服务器follower提交

  2. 确保那些只在Leader被提出的proposal被丢弃

针对这个要求,如果让Leader选举算法能够保证新选举出来的Leader服务器拥有集群中所有机器最高的ZXID事务proposal，就可以保证这个新选举出来的Leader一定具有所有已经提交的提案，也可以省去Leader服务器检查proposal的提交与丢弃的工作。

已经被处理的事务请求（proposal）不能丢（commit的）

问题描述

当 leader 收到合法数量 follower 的 ACKs 后，就向各个 follower 广播 COMMIT 命令，同时也会在本地执行 COMMIT 并向连接的客户端返回「成功」。但是如果在各个 follower 在收到COMMIT 命令前 leader 就挂了，导致剩下的服务器并没有执行都这条消息。

解决方式

  1. 选举拥有 proposal 最大值（即 zxid 最大） 的节点作为新的 leader。

    由于所有提案被 COMMIT 之前必须有合法数量的 follower ACK，即必须有合法数量的服务器的事务日志上有该提案的 proposal，因此，zxid最大也就是数据最新的节点保存了所有被 COMMIT 消息的 proposal 状态。

  2. 新的 leader 将自己事务日志中 proposal 但未 COMMIT 的消息处理。

  3. 新的 leader 与 follower 建立先进先出的队列， 先将自身有而 follower 没有的 proposal 发送给 follower，再将这些 proposal 的 COMMIT 命令发送给 follower，以保证所有的 follower 都保存了所有的 proposal、所有的 follower 都处理了所有的消息

没被处理的事务请求（proposal）不能再次出现什么时候会出现事务请求被丢失呢？

问题描述

当 leader 接收到消息请求生成 proposal 后就挂了，其他 follower 并没有收到此 proposal，因此经过恢复模式重新选了 leader 后，这条消息是被跳过的。 此时，之前挂了的 leader 重新启动并注册成了 follower，他保留了被跳过消息的 proposal 状态，与整个系统的状态是不一致的，需要将其删除。

解决方式

Zab 通过巧妙的设计 zxid 来实现这一目的。

一个 zxid 是64位，高 32 是纪元（epoch）编号，每经过一次 leader 选举产生一个新的 leader，新 leader 会将 epoch 号 +1。低 32 位是消息计数器，每接收到一条消息这个值 +1，新 leader 选举后这个值重置为 0。

这样设计的好处是旧的 leader 挂了后重启，它不会被选举为 leader，因为此时它的 zxid 肯定小于当前的新 leader。当旧的 leader 作为 follower 接入新的 leader 后，新的 leader 会让它将所有的拥有旧的 epoch 号的未被 COMMIT 的 proposal 清除。

总结

最近的几篇文章都是围绕着分布式系统来开展的，学习了一些一致性算法和 ID 生成算法，每次开始学习这种新的知识的时候我都会感慨他们简直就是天才，十分神奇。有机会的话还会去更加全面的学习，现在还是只停留在纸面上，还没找到合适的机会去实战。

今天上午面试结束了，准备了很长时间也确实收获了很多东西，应该算是找到了比较正确的学习方法。除了学习方面的问题，通过昨天准备 HR 面的时候好好反思了自己的一些问题，还是觉得做事急于求成和功利心这方面的问题要及时纠正，最近两周也有在做一些调整，还是需要改掉这些毛病的，最起码要保证做一些事情的时候不要老是想成功了之后怎样怎样、失败了怎样怎样。

昨天晚上紧张的整晚都没睡好觉，今天早上六点多就起来了，准备了一下面试的东西，虽然面试的时候没有问，但是我确实有了不小的底气。至于结果怎么样，我非常希望会是一个好的结果，估计要到一周之后见分晓了。在北京、字节的王牌部门，如果能进去实习当然会往转正的方向努力。祝我面试成功！！！