zookeeper的ZAB协议

ZAB协议

• 崩溃恢复
• • zxid
  • 选举
  • 数据同步
  • 数据同步的四种策略
• 消息广播
• • zab协议的有序性保证

zab(Zookepper Actomic Broadcast) 是专为zk 设计的支持崩溃恢复的原子广播协议。是保证数据一致性的核心算法。
ZAB协议有两种模式：崩溃恢复和消息广播
当集群启动时，或者leader服务器出现网络中断，崩溃推出或者重启等异常时，zab协议会进入崩溃恢复模式，选举产生新leader，选举成功后，进入消息广播模式。

崩溃恢复 zxid

leader服务器在接收到事务请求后，会为每个事务请求生产对应的propsal来进行广播，在广播之前，leader 服务器会为每个事务生成一个唯一的全局id , 即事务id(zxid)。

zxid 是一个全局的有序的64位数字，可以分为两部分：

1. 高 32 位是： epoch（纪元），epoch代表当前集群所属的哪个leader，leader的选举就类似一个朝代的更替。每次选举产生的新leader 都会取出其zxid，解析 epoch 值 再加1 ，作为新的epoch , 并将低32 位置零
2. 低 32 位是 counter（计数器），是一个单调递增的计数器，针对客户端的每次事务都会加一

选举

1. 所有节点第一票先选举自己当leader，将投票信息（自己的myid，zxid）广播出去。
2. 各节点收到信息后将收到的（myid，zxid）和自己的比较。先比较zxid，如果zxid 相同，再比较myid，选最大的myid 作为leader.
3. 然后判断是否有半数的机器投票选出 Leader，如果否，在进入新一轮投票，直到选出.
4. 选出 Leader 后，其他节点就变成 Follower 角色，并向 Leader 发送自己服务器的最大 zxid ，Leader 服务器收到后会和自己本地的提议缓存队列进行比较，判断使用那种策略进行同步
5. 当同步完成，集群就可以正常的处理请求了，就进入消息广播模式了

数据同步

1. 完成 Leader 选举后（新的 Leader 具有最高的zxid），在正式开始工作之前（接收事务请求，然后提出新的 Proposal），Leader 服务器会首先确认事务日志中的所有的 Proposal 是否已经被集群中过半的服务器 Commit。
2. Leader 服务器需要确保所有的 Follower 服务器能够接收到每一条事务的 Proposal ，并且能将所有已经提交的事务 Proposal 应用到内存数据中。等到 Follower 将所有尚未同步的事务 Proposal 都从 Leader 服务器上同步过并且应用到内存数据中以后，Leader 才会把该 Follower 加入到真正可用的 Follower 列表中

数据同步的四种策略

在数据同步之前，Leader 服务器会进行数据同步的初始化，首先会从 Zookeeper 的内存数据库中提取出事务前期对应的提议缓存队列，同时会初始化三个 ZXID 的值：
peerLastZxid：这是 Follower 的最后处理 ZXID
minCommittedLog：Leader 服务器的提议缓存队列中 最小的 ZXID
maxCommittedLog：Leader 服务器的提议缓存队列中 最大的 ZXID
根据这三个参数，就可以确定四种同步方式，分别为：

1. 直接差异化同步
   场景：当 minCommittedLog < peerLastZxid < maxCommittedLog 时
2. 先回滚在差异化同步
   场景：假如集群有 A、B、C 三台机器，此时 A 是 Leader 但是 A 挂了，在挂之前 A 生成了一个提议假设是：03，然后集群有重新选举 B 为新的 Leader，此时生成的的提议缓存队列为：01~02，B 和 C 进行同步之后，生成新的纪元，ZXID 从 10 开始计数，集群进入广播模式处理了部分请求，假设现在 ZXID 执行到 15 这个值，此时 A 恢复了加入集群，这时候就比较 A 最后提交的 ZXID：peerLastZxid 与 minCommittedLog、maxCommittedLog 的关系。此时虽然符合直接差异化同步：minCommittedLog < peerLastZxid < maxCommittedLog 这样的关系，但是提议缓存队列中却没有这个 ZXID ，这时候就需要先回滚，在进行同步。
3. 仅回滚同步
   场景：这里和先回滚在差异化同步类似，直接回滚就可以。
4. 全量同步
   场景：peerLastZxid < minCommittedLog，当远远落后 Leader 的数据时，直接全量同步。
   这就是四种同步策略，这几种同步方式也解决了上文提出的问题：

只在 Leader 服务器上提出的事务，要丢弃（这个问题会在同步时，会进行回滚，使得只在 Leader 服务器上提出的事务丢弃）

消息广播

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

收到写请求的具体步骤：

1. Leader收到客户端的写请求，生成一个事务（Proposal），其中包含了zxid；
2. Leader开始广播该事务，需要注意的是所有节点的通讯都是由一个FIFO的队列维护的；
3. Follower接受到事务之后，将事务写入本地磁盘，写入成功之后返回Leader一个ACK；
4. Leader收到过半的ACK之后，开始提交本事务，并广播事务提交信息
5. 从节点开始提交本事务

zookeeper通过二阶段提交来保证集群中数据的一致性，因为只需要收到过半的ACK就可以提交事务，所以zookeeper的数据并不是强一致性。

zab协议的有序性保证

1. Leader 服务器为每个 Follower 服务器分配一个单独的队列，然后将需要广播的 Proposal 依次放到队列中取，并且根据 FIFO 策略进行消息发送.保证全局有序性.
2. 通过全局递增的zxid保证因果有序性