braft

ZAB是Zookeeper Atomic Broadcast协议的简称,是为分布式协调服务Zookeeper专门设计的一种支持崩溃恢复的原子广播协议。其实现类似Raft构建了一个树形主备模式的架构来保持集群中各副本间数据的一致性。采用单一的主进程接受并处理客户端的全部请求,采用ZAB的原子广播协议,将服务状态变更通过proposal的形式广播给其他副本进程。ZAB协议保证了任意时刻一个集群中同时只有一个主进程来广播proposal,所有proposal在副本间保证有序提交。

在ZooKeeper中所有的事务请求都由一个主服务器也就是Leader来处理,其他服务器为Follower,Leader将客户端的事务请求转换为事务Proposal,并且将Proposal分发给集群中其他所有的Follower,然后Leader等待Follwer反馈,当有过半数(>=N/2+1)的Follower反馈信息后,Leader将再次向集群内Follower广播Commit信息,Commit为将之前的Proposal提交。

ZAB协议简介

状态

ZAB协议中每个进程有三种状态:

ZooKeeper启动时所有节点初始状态为Looking,这时集群会尝试选举出一个Leader节点,选举出的Leader节点切换为Leading状态;当节点发现集群中已经选举出Leader则该节点会切换到Following状态,然后和Leader节点保持同步;当Follower节点与Leader失去联系时Follower节点则会切换到Looking状态,开始新一轮选举;在ZooKeeper的整个生命周期中每个节点都会在Looking、Following、Leading状态间不断转换。

持久化数据

在 ZAB 协议的事务编号 Zxid 设计中,Zxid 是一个 64 位的数字,其中低 32 位是一个简单的单调递增的计数器,针对客户端每一个事务请求,计数器加 1;而高 32 位则代表 Leader 周期 epoch 的编号,每个当选产生一个新的 Leader 服务器,就会从这个 Leader 服务器上取出其本地日志中最大事务的ZXID,并从中读取 epoch 值,然后加 1,以此作为新的 epoch,并将低 32 位从 0 开始计数。

epoch:类似Raft中的term,标明leader的版本,每次leader变更都会进行提升,这样可以用于fence之前老的leader崩溃恢复之后重新加入。

协议流程

ZAB协议主要包括消息广播和崩溃恢复两个过程,进一步可以细分为发现(discovery)、同步(sync)和广播(Broadcast)阶段,组成ZAB协议的每一个分布式进程会循环执行这三个阶段。每个节点启动之后进入discovery阶段,其实就是一次选主过程,如果选主成功则进入Leader状态,否则可能会发现当前Leader加入集群。一旦节点出现异常,将会进入discovery阶段。

img

消息

上面是ZAB协议的三个核心工作流程,整个过程中各进程间交互的消息说明如下:

Phase 0: Leader election

节点在一开始都处于选举阶段,只要有一个节点得到超半数节点的票数,它就可以当选准 leader。只有到达 Phase 3 准 leader 才会成为真正的 leader。这一阶段的目的是就是为了选出一个准 leader,然后进入下一个阶段。

协议并没有规定详细的选举算法,后面我们会提到实现中使用的 Fast Leader Election。

Phase 1: Discovery

这个阶段主要就是Leader是选举过程,用于在多个分布式进程中选举出一个准Leader进程。这个时候准leader不一定能够选主成功,任何一个节点故障之后都会触发选主流程加入集群。

zab的实现不是基于RPC的,而是面向socket的方式。选举开始后节点会建立与其他节点的连接,并发送自己的epoch和lastZxid,其他节点回复currentEpoch(cepoch)。准Leader收集Follower的cepoch,并根据max(cepoch)+1生成newEpoch,再通知给其他节点更新其acceptEpoch。newEpoch通知过程中,Follower会反馈其历史事务proposal集合。这样准Leader就可以判断出当前集群中多数节点中哪个节点拥有最新的数据。

img

Phase 2: Synchronization

同步阶段主要是利用 leader 前一阶段获得的最新提议历史,同步集群中所有的副本。准Leader先与Discovery阶段发现的各个Follower节点的历史proposal集合,判断出最新数据节点,然后与其进行同步。

当准Leader同步完成最新数据之后,再通过NewLeader向其他节点通知其当选为新的Leader,并向其同步数据。只有当 quorum 都同步完成,准 leader 才会成为真正的 leader。follower 只会接收 zxid 比自己的 lastZxid 大的提议。

img

这里只有当准Leader将多数节点数据同步到一致状态之后,才会发送NewLeader给多数节点,多数节点才更新其本地的currentEpoch。这与raft中term节点自行增加的方式不同。

Phase 3: Broadcast

到了这个阶段, leader才能对外提供服务,可以进行消息广播。数据同步的过程类似一个2PC,Leader将client发过来的请求生成一个事务proposal,然后发送给Follower,多数Follower应答之后,Leader再发送Commit给全部的Follower让其进行提交。

img

具体算法描述如下:e’为新的epoch,Q为quorum集合,f为follower。

img

协议实现

协议的 Java 版本实现跟上面的定义有些不同,选举阶段使用的是 Fast Leader Election(FLE),它包含了 Phase 1 的发现职责。因为 FLE 会选举拥有最新提议历史的节点作为 leader,这样就省去了发现最新提议的步骤。实际的实现将 Phase 1 和 Phase 2 合并为 Recovery Phase(恢复阶段)。所以,ZAB 的实现只有三个阶段:

Fast Leader Election

FastLeaderElection是标准的Fast Paxos的实现,它首先向所有Server提议自己要成为leader,当其它Server收到提议以后,解决 epoch 和 zxid 的冲突,并接受对方的提议,然后向对方发送接受提议完成的消息。FastLeaderElection算法通过异步的通信方式来收集其它节点的选票,同时在分析选票时又根据投票者的当前状态来作不同的处理,以加快Leader的选举进程。FLE 会选举拥有最新提议历史(lastZxid最大)的节点作为 leader,这样就省去了发现最新提议的步骤。这是基于拥有最新提议的节点也有最新提交记录的前提。

成为 leader 的条件

节点在选举开始都默认投票给自己,当接收其他节点的选票时,会根据上面的条件更改自己的选票并重新发送选票给其他节点,当有一个节点的得票超过半数,该节点会设置自己的状态为 leading,其他节点会设置自己的状态为 following。

img

数据恢复阶段

每个ZooKeeper Server读取当前磁盘的数据(transaction log),获取最大的zxid。

发送选票

每个参与投票的ZooKeeper Server向其他Server发送自己所推荐的Leader,这个协议中包括几部分数据:

处理选票

每台Server将自己的数据发送给其他Server之后,同样也要接受其他Server的选票,并做一下处理。

如果Sender的状态是LOOKING

当Server处理完选票后,可能需要对Server的状态进行更新:

如果Sender的状态是FOLLOWING或者LEADER

Recovery Phase

这一阶段 follower 发送它们的 lastZixd 给 leader,leader 根据 lastZixd 决定如何同步数据。这里的实现跟前面 Phase 2 有所不同:Follower 收到 TRUNC 指令会中止 L.lastCommittedZxid 之后的提议,收到 DIFF 指令会接收新的提议。

ZAB中Leader会根据Follower数据情况使用多种同步策略:

SNAP和DIFF用于保证集群中Follower节点上已经Committed的数据的一致性,TRUNC用于抛弃已经被处理但是还没有Committed的数据。Follower接收SNAP/DIFF/TRUNC指令同步数据与ZXID,同步成功之后向Leader发送ACK-LD,Leader才会将其加入到可用Follower列表。

img

具体消息流程如下:

img