ZAB算法

发表于 | 评论数： | 阅读次数：

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

词典

角色

  1. 主节点（leader） 在全局负责处理事务请求，一个集群只有一个
  2. 从节点（follower） 从leader获取数据并同步到自身

动作

  1. 选举（election）
  2. 发现（discovery）
  3. 同步（sync）
  4. 广播(Broadcast)

名称

  1. ZXID事务id，zookeeper采用了递增ZXID来保证事务的顺序
  2. epoch主节点信息，ZXID的高32位其实保存的就是主节点标识，低32位用来计数
  3. 提议（proposal）

正文

意义

ZAB协议主要是为了保证两件事情：

  1. 崩溃恢复，在集群启动或者主节点崩溃的时候，选举出新的主节点，在新的主节点与半数以上节点同步之后推出这个模式。
  2. 消息广播，主节点进行事务请求处理并且进行广播。

选举

选举发生的时间有两种可能，一是集群启动时，还没有主节点；二是主节点无法和半数以上节点产生链接，认为他已经发生故障；

服务器状态枚举

每个节点存在以下状态：

  1. LOOKING:寻找leader，没有主节点
  2. FOLLOWING：当前服务器从节点
  3. LEADING：当前服务器主节点
  4. OBSERVING：当前服务器主节点，用来观察主节点不参与事务处理
启动时选举

这个时候，节点的状态都是LOOKING，在发现其他服务器的时候才可以进行选举，只有一个节点时无法发起选举，因为此时无法向其他节点发起投票。
每个节点都会推荐自己作为主节点，携带myid、epoch和ZXID发送给其他节点进行投票。

收到投票之后，会根据epoch来判断是否属于本次投票，如果版本不对表示已经发生了新的选举，无需处理；然后选择ZXID最大的为主节点，保证顺序性；如果ZXID发生重复，
则选择myid最大的为主节点，这里没有特殊的含义。

统计选票，查看有没有过半的节点选择了相同的主节点，如果发现主节点则选举完成。主节点更改状态为LEADING，从节点更改状态为FOLLOWING。

故障时选举

主节点挂了之后，从节点将自己的状态更改为LOOKING

重复启动时选举的过程

选举注意事项

在故障选举的情况下，可能有下面两种问题造成数据不同步：

  1. 挂掉的主节点里还没有执行完成二阶段commit；需要保证已经提交的事务最终会被从节点提交；
  2. 挂掉的主节点在事务提出之后挂掉了，没能发起广播；需要丢弃这些事务；

按照以下规则进行筛选即可满足

  1. 新的主节点不能包含未提交的事务
  2. 新的主节点有最大的ZXID（按顺序最大的事务进行选择，减少了事务提交和丢弃检查）

发现

从节点和半数以上主节点进行通信，同步从节点近期收到的事务，发现最大的ZXID

同时在主节点维护一个从节点列表

同步

主节点根据自己在发现阶段收集到的事务，向所有从节点发起同步，当半数以上从节点同步完成，从节点根据ZXID的大小，选择比自身lastZXID大的事务进行同步

广播

Zookeeper集群可以对外提供服务，主节点开始提供两种服务：

  1. 接收所有的事务请求，并广播给所有的从节点
  2. 当新的从节点加入，同步事务

事务

事务的处理是一个二段提交

  1. 主节点将事务请求封装为一个事务，并通过ZXID保证全局唯一，并向所有的从节点发送数据广播请求。
  2. 从节点反馈是否接受事务，并给主节点发送ACK响应。
  3. 只要超过半数的从节点ACK响应为接受，则主节点直接向所有的从节点发送commit请求。