Zookeeper Atomic Broadcast(ZAB，zookeeper原子消息广播协议)。ZAB 协议是为分布式协调服务 ZooKeeper 专门设计的一种支持崩溃恢复的原子广播协议。在 ZooKeeper 中，主要依赖 ZAB 协议来实现分布式数据一致性，基于该协议，ZooKeeper 实现了一种主备模式的系统架构来保持集群中各个副本之间的数据一致性，同时其崩溃恢复过程也确保看zk集群的高可用性（HA）。zab协议重要的三个过程：

  (1). 消息广播协议（leader想其他节点广播事务） 

  (2). leader选举（快速选举过程fastleaderelection，集群刚启动时，leader崩溃或leader与集群中超过一半的节点断连后） 

  (3). leader重新选举后，如何进行数据同步到一致状态

1）消息广播

ZAB协议保证所有的事物请求最终都会转发给Leader服务器，由Leader服务器进行生成一个全局唯一的ZXID（Zxid 是一个 64 位的数字，其中低 32 位是一个简单的单调递增的计数器，针对客户端每一个事务请求，计数器加 1；而高 32 位则代表 Leader 周期 epoch 的编号，每个当选产生一个新的 Leader 服务器，就会从这个 Leader 服务器上取出其本地日志中最大事务的ZXID，并从中读取 epoch 值，然后加1，以此作为新的 epoch，并将低 32 位从 0 开始计数）赋给事务，并按照FIFO原则的进行广播；超过半数的Follower节点返回ACK时，Leader将广播commit的消息给所有Follower提交事物。

image.png

2）崩溃恢复或选举

ZAB协议会让ZK集群进入崩溃恢复模式的情况如下：

  （1）当服务框架在启动过程中

  （2）当Leader服务器出现网络中断，崩溃退出与重启等异常情况。

  （3）当集群中已经不存在过半的服务器与Leader服务器保持正常通信。

Leader选举需要达到的再次使用的条件，需要解决以下两个问题

 （1）已经被leader提交的事务需要最终被所有的机器提交（已经发出commit了）；

  （2）保证丢弃那些只在leader上提出的事务。（只在leader上提出了proposal，还没有收到回应，还没有进行提交）

A. 服务器启动时期的Leader选举

若进行Leader选举，则至少需要两台机器，这里选取3台机器组成的服务器集群为例。在集群初始化阶段，当有一台服务器Server1启动时，其单独无法进行和完成Leader选举，当第二台服务器Server2启动时，此时两台机器可以相互通信，每台机器都试图找到Leader，于是进入Leader选举过程。选举过程如下

(1) 每个Server发出一个投票。由于是初始情况，Server1和Server2都会将自己作为Leader服务器来进行投票，每次投票会包含所推举的服务器的myid和ZXID，使用(myid, ZXID)来表示，此时Server1的投票为(1, 0)，Server2的投票为(2, 0)，然后各自将这个投票发给集群中其他机器。

image.png

节点2

image.png

(2) 接受来自各个服务器的投票。集群的每个服务器收到投票后，首先判断该投票的有效性，如检查是否是本轮投票、是否来自LOOKING状态的服务器。

(3) 处理投票。针对每一个投票，服务器都需要将别人的投票和自己的投票进行PK，PK规则如下

· 优先检查ZXID。ZXID比较大的服务器优先作为Leader。

· 如果ZXID相同，那么就比较myid。myid较大的服务器作为Leader服务器。

对于Server1而言，它的投票是(1, 0)，接收Server2的投票为(2, 0)，首先会比较两者的ZXID，均为0，再比较myid，此时Server2的myid最大，于是更新自己的投票为(2, 0)，然后重新投票，对于Server2而言，其无须更新自己的投票，只是再次向集群中所有机器发出上一次投票信息即可。

(4) 统计投票。每次投票后，服务器都会统计投票信息，判断是否已经有过半机器接受到相同的投票信息，对于Server1、Server2而言，都统计出集群中已经有两台机器接受了(2, 0)的投票信息，此时便认为已经选出了Leader。

(5) 改变服务器状态。一旦确定了Leader，每个服务器就会更新自己的状态，如果是Follower，那么就变更为FOLLOWING，如果是Leader，就变更为LEADING。

image.png

B. 服务器运行时期的Leader选举

在Zookeeper运行期间，Leader与非Leader服务器各司其职，即便当有非Leader服务器宕机或新加入，此时也不会影响Leader，但是一旦Leader服务器挂了，那么整个集群将暂停对外服务，进入新一轮Leader选举，其过程和启动时期的Leader选举过程基本一致。假设正在运行的有Server1、Server2、Server3三台服务器，当前Leader是Server2，若某一时刻Leader挂了，此时便开始Leader选举。选举过程如下

(1) 变更状态。Leader挂后，余下的非Observer服务器都会讲自己的服务器状态变更为LOOKING，然后开始进入Leader选举过程。

(2) 每个Server会发出一个投票。在运行期间，每个服务器上的ZXID可能不同，此时假定Server1的ZXID为123，Server3的ZXID为122；在第一轮投票中，Server1和Server3都会投自己，产生投票(1, 123)，(3, 122)，然后各自将投票发送给集群中所有机器。

(3) 接收来自各个服务器的投票。与启动时过程相同。

(4) 处理投票。与启动时过程相同，此时，Server1将会成为Leader。

(5) 统计投票。与启动时过程相同。

(6) 改变服务器的状态。与启动时过程相同。

image.png

上边选出的只是准leader，要想变成leader还需完成数据同步。

（3）数据同步

同步阶段主要是利用 leader 前一阶段获得的最新提议历史，同步集群中所有的副本。只有当 集群过半机器都同步完成，准 leader 才会成为真正的 leader。follower 只会接收 zxid 比自己的 lastZxid 大的提议。

当完成Leader选举后，进行故障恢复的第二步就是数据同步： Leader服务器会为每一个Follower服务器准备一个队列，并将那些没有被各个Follower服务器同步的事务以Proposal的形式逐条发给各个Follower服务器，并在每一个Proposal后都紧跟一个commit消息，表示该事务已经被提交，档follower服务器将所有尚未同步的事务proposal都从leader服务器同步过来并成功应用到本地后，leader服务器就会将该follower加入到真正可用的follower列表中。（新选举周期，epoch已经更新了）

每个zookeeper 事务都有一个全局唯一的事务ID，ZXID。ZXID 高32 位是leader 周期epoch，低32 位是递增计数器。从算法角度上看：

第一阶段（准leader生成初始事务集合）

所有follower 向准leader 发送自己最后接收的事务的epoch；

准leader 选取最大的epoch，加1得到e1，将e1 发送给follower；（准leader已经是zxid最大的机器了，且已经完成epoch更新了，防止说个leader出现）

follower 收到准leader 发送的epoch 值之后，与自己的epoch 值作比较，若小于，则将自己的epoch 更新为e1，并向准leader 发送反馈ACK信息（epoch 信息、历史事务集合）；

准leader 接收到ACK 消息之后，会在所有历史事务集合中选择其中一个历史事务集合作为初始化事务集合，该事务集合满足ZXID最大；

第二阶段（正式同步）

准leader 将epoch 与 初始化事务集合发送给集群中过半的follower；每个follower 会分配到一个队列，leader 会将那些没有被各个follower 同步的事务以proposal 形式发送给各个follower，并在后面追加commit 消息，表示事务已被提交；follower 接收后，会执行初始化事务集合中的事务（执行过跳过，未执行执行），反馈给leader 表明自己已经处理（追上来了）leader 收到后过半反馈后，发送commit 消息；follower 接收到commit 消息后，提交事务；注意：在zk选举中，通过投票已经确认leader服务器是最大的zxid的节点了，所以同步过程没有那么复杂。

ZAB协议与Paxos算法的异同

ZAB协议并不是 Paxos 算法的一个典型实现，在讲解 ZAB和 Paxos之间的区别之前, 我们首先看下两者的联系，

两者都有一个类似于Leader进程的角色，由其负责协调多个Follower运行

Leader进程都会等待超过半数的Follower做出正确的反馈后，才会将一个提案进行提交。

在ZAB协议中，每个Proposal都包含了一个epoch值，用来代表当前的Leader 周期，在Paxos算法中，同样存在这样的一个标识，只是名字变成了Ballot。

在Paxos算法中，一个新选举产生的主进程会进行两个阶段的工作，第一阶段被称为读阶段，在这个阶段中，这个新的主进程会通过和所有其他进程进行通信的方式来收集上一个—个主进程提出的提案，并将它们提交.第二阶段被称为写阶段，在这个阶段，与前主进程开始提出自己的提案。

在Paxos算法设计的基础上， ZAB协议额外添加了一 个同步阶段。在同步阶段之前，ZAB协议也存在一个和Paxos算法中的读阶段I类似的过程，被称为发现（ Discovery)阶段，在同步阶段中，新的 Leader会确存在过半数的Follower已经提交了之前Leader周期中的所有事物的Proposal，在这一同步阶段的引人，能够有效地保证Leader在新的周期中提出事务Proposal之前，所有的进程都已经完成了对之前所有事物的Proposal的提交。

一旦完成同步阶段后，那么 ZAB就会执行和 Paxos算法类似 的写阶段。

总的来汫， ZAB协议和 Paxos本质区别在于，两者的设计目标不太一样。 ZAB 协议主要用于构建一个高可用的分布式数椐主备系统，例如ZooKeeper, 而Paxos算法 则是用于构建一个分布式的一致性状态机系统，

参考 https://blog.csdn.net/u013679744/article/details/79240249