ZooKeeper的ZAB协议

很多人认为ZooKeeper是Paxos算法的一个实现,但是ZK并没有完全采用Paxos算法,而是使用了一种叫做ZooKeeper Atomic Broadcast(ZAB,ZooKeeper原子消息广播协议)的协议作为数据一致性的核心算法。

ZAB协议的核心是定义了修改数据的事务处理请求:

所有事务请求必须由一个全局唯一的服务器(Leader)来协调处理,其他的服务器则成为Follower。Leader会将一个客户端的事务请求转换为一个Proposal(提议),然后分发为集群中所有的Follower。当有过半数的Follower进行了正确的反馈之后,Leader会向所有的Follower发出Commit消息,然后返回客户端成功。

相关术语

Quorum:集群中超过半数的节点集合。

ZAB中的节点有3种状态:

Following:当前节点是跟随者,服从Leader节点的命令。

Leading:当前节点是leader,负责协调事务。

Election/Looking:节点处于选举状态。

节点状态

ZK启动时所有节点状态为Looking,这是集群会选举出一个Leader节点,然后选举出的节点切换为Leading状态。当节点发现集群中已经选举出了Leader,则该节点会切换为Following状态,然后和Leader保持同步。当Follower节点和Leader节点连接断开时,则会切换到Looking状态,然后开始新一轮的选举。如下图所示:

协议阶段

ZAB协议定义了:选举(Election)发现(Discovery)同步(Sync)广播(Broadcast)4个阶段。ZAB选举时,当Follower存在ZXID(事务ID)时,判断所有Follower节点的事务日志,只有lastZXID的节点才有资格成为Leader。这种情况下选举出来的Leader总有最新的事务日志,基于这个原因ZK实现时,把发现(Discovery)和同步(Sync)合并为恢复(Recovery)阶段

选举(Election)

选举阶段必须确保选出的Leader具有最大的ZXID,否则在恢复阶段无法保证数据的一致性。恢复阶段Leader要求Follower向自己同步数据,所以选举出来的Leader要具有最大(最新)的ZXID。在选举的过程中,会对每个Follower节点的ZXID进行对比,只有最大ZXID的Follower才可能当选Leader。流程如下:

1、每个Follower都向其他节点发送自投票(Vote)的请求,等待回复。

2、Follower接收到的Vote如果比自身的大(ZXID更大),则投票并更新自身的Vote,否则拒绝投票。

3、每个Follower中都维护着一个投票记录表,当某个节点(发送方)接收到过半投票时,投票结束并把该Follower选为Leader。

ZAB协议中使用64位的ZXID作为事务编号。其中低32位是一个递增的计数器,每个客户端的一个事务请求时,Leader产生的新Proposal后,计数器的值都会自增。高32位为Leader的Epoch编号(如皇帝的年号),当新选出一个Leader之后,Leader会根据本地日志找出最大的ZXID值,并解析出Epoch值,然后+1作为新的Epoch。此时低32位将从0开始,继续产生新的ZXID,这里面ZAB使用Epoch来区分不同的Leader周期。

恢复(Recovery)

在Election阶段选举出来的Leader已经具有最新的ZXID,因此恢复阶段主要是根据Leader的事务日志对Follower节点数据进行更新。同步策略如下:

SNAP:如果Follower的数据太老,Leader将发送SNAP快照指令给Follower同步数据。

DIFF:Leader发送从Follower.lastZXID到Leader.lastZXID区间的DIFF指令给Follower同步数据。

TRUNC:当Follower.lastZXID比Leader.lastZXID大时,Leader发送从Leader.lastZXID到Follower.lastZXID的TRUNC指令,让Follower丢弃该段数据。

此时如果Follower往Leader中发送FOLLOWERINFO指令,Leader会拒绝转到Election阶段。当Follower接收Leader的NEWLEADER指令,如果指令中Epoch比当前Follower的小,那么Follower转为Election阶段。还有,Follower主要是接收SNAP/DIFF/TRUNC指令同步数据,同步成功后回复ACK,然后进入下一阶段。Follower将所有的事务同步完成之后,Leader会将其加入到可用Follower中去。

SNAP与DIFF用于保证集群中Follower阶段已经提交的数据一致性,TRUNC用于抛弃已经被处理但没有提交的数据。

广播(Broadcast)

Client提交事务请求时,Leader为每一个请求生成一个Proposal,将其发送给集群中所有的节点。当过半的Follower反馈后,进行事务的提交,然后返回给客户端成功。因此集群中有可能会出现数据不一致的现象,这里使用的ZAB的崩溃恢复来保证最终一致性的。

消息广播使用了TCP进行通讯,保证了发送和接收的顺序性。广播消息时,Leader为每个事务分配一个全局递增的ZXID(事务ID),每个事务都需要按照ZXID的顺序来处理。Leader为每一个Follower维护一个事务队列,使用FIFO(先进先出)的原则,从而保证事务的顺序性。


参考:ZooKeeper之ZAB协议Zookeeper ZAB 协议分析