一文彻底搞懂ZAB算法,看这篇就够了

什么是ZAB 算法？

ZAB的全称是 Zookeeper Atomic Broadcast （Zookeeper原子广播。Zookeeper 是通过 Zab 算法来保证分布式事务的最终一致性。

支持崩溃恢复的 原子广播协议 ，是Zookeeper保证数据一致性的核心算法。Zab借鉴了Paxos算法，但又不像Paxos那样，是一种通用的分布式一致性算法。它是特别为Zookeeper设计的支持崩溃恢复的原子广播协议。

客户端的读取流程：客户端会随机的链接到 zookeeper 集群中的一个节点，如果是读请求，就直接从当前节点中读取数据；如果是写请求，那么节点就会向 Leader 提交事务，Leader 接收到事务提交，会广播该事务，只要超过半数节点写入成功，该事务就会被提交。

深入ZAB算法

消息广播和崩溃恢复。

崩溃恢复（recovery）：当服务初次启动，或者 leader 节点挂了，系统就会进入恢复模式，直到选出了有合法数量 follower 的新 leader，然后新 leader 负责将整个系统同步到最新状态。

1. 消息广播

消息广播的过程实际上是一个简化的两阶段提交过程，这里对两阶段提交做一个简单的介绍。

两阶段提交

下面以MySQL中对数据库的修改过程，来介绍下两阶段提交的具体流程，在MySQL中对一条数据的修改操作首先写undo日志，记录的数据原来的样子，接下来执行事务修改操作，把数据写到redo日志里面，万一捅娄子，事务失败了，可从undo里面恢复数据。数据库通过undo与redo能保证数据的强一致性。

当事务管理器收到了所以资源的反馈，事务都执行没报错后，事务管理器再发送commit指令让资源把事务提交，一旦发现任何一个资源在准备阶段没有执行成功，事务管理器会发送rollback，让所有的资源都回滚。这就是2pc，非常简单。

说他是强一致性的是他需要保证任何一个资源都成功，整个分布式事务才成功。

缺点：同步阻塞，单点问题，数据不一致，容错性不好

单点问题：协调者在整个二阶段提交过程中很重要，如果协调者在提交阶段出现问题，那么整个流程将无法运转。更重要的是，其他参与者将会处于一直锁定事务资源的状态中，而无法继续完成事务操作。
数据不一致：假设当协调者向所有的参与者发送commit请求之后，发生了局部网络异常，或者是协调者在尚未发送完所有 commit请求之前自身发生了崩溃，导致最终只有部分参与者收到了commit请求。这将导致严重的数据不一致问题。
容错性不好：二阶段提交协议没有设计较为完善的容错机制，任意一个节点是失败都会导致整个事务的失败。

ZAB消息广播过程

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

Leader 通过先进先出队列（通过 TCP 协议来实现，以此实现了全局有序这一特性）将带有 zxid 的消息作为一个提案（proposal）分发给所有 follower。
当 follower 接收到 proposal，先将 proposal 写到硬盘，写硬盘成功后再向 leader 回一个 ACK。
当 leader 接收到合法数量的 ACKs 后，leader 就向所有 follower 发送 COMMIT 命令，同时会在本地执行该消息。
当 follower 收到消息的 COMMIT 命令时，就会执行该消息。

从另一角度看，正因为 Zab 的广播过程不需要终止事务，也就是说不需要所有 follower 都返回 ACK 才能进行 COMMIT，而是只需要合法数量（2n+1 台服务器中的 n+1 台）的follower，也提升了整体的性能。

2. 崩溃恢复

崩溃恢复的主要任务就是选举Leader（Leader Election），Leader选举分两个场景：

Zookeeper集群运行过程中Leader崩溃后的Leader选举。

选举参数

myid

ZAB算法中通过myid来规避了多个节点可能有相同zxid问题，注意可以对比之前的Raft算法，Raft算法中通过随机的timeout来规避多个节点可能同时成为Leader的问题。

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

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

LOOKING: 竞选状态。
FOLLOWING: 随从状态，同步Leader 状态，参与Leader选举的投票过程。
OBSERVING: 观察状态，同步Leader 状态，不参与Leader选举的投票过程。
LEADING: 领导者状态。

选举流程

选举的流程如下：

收集来自各个服务器的投票
处理投票并重新投票，处理逻辑：优先比较ZXID,然后比较myid
统计投票，只要超过半数的机器接收到同样的投票信息，就可以确定leader
改变服务器状态，进入正常的消息广播流程。

ZAB算法需要解决的两大问题

1. 已经被处理的消息不能丢

为了实现已经被处理的消息不能丢这个目的，Zab 的恢复模式使用了以下的策略：

因此，只要有合法数量的节点正常工作，就必然有一个节点保存了所有被 COMMIT 的 proposal。而在选举Leader的过程中，会比较zxid，因此选举出来的Leader必然会包含所有被COMMIT的proposal。

新的 leader 将自己事务日志中 proposal 但未 COMMIT 的消息处理。
新的 leader 与 follower 建立先进先出的队列，先将自身有而 follower 没有的 proposal 发送给 follower，再将这些 proposal 的 COMMIT 命令发送给 follower，以保证所有的 follower 都保存了所有的 proposal、所有的 follower 都处理了所有的消息。

2. 被丢弃的消息不能再次出现

Zab 协议设计的优秀之处有两点，一是简化二阶段提交，提升了在正常工作情况下的性能；二是巧妙地利用率自增序列，简化了异常恢复的逻辑，也很好地保证了顺序处理这一特性

https://www.cnblogs.com/CNRF/p/14862669.html

欢迎关注公众号【码老思】，这里有最通俗易懂的原创技术干货。

编程笔记 » 一文彻底搞懂ZAB算法,看这篇就够了