ZooKeeper学习(六)—ZAB协议

Scroll Down

ZooKeeper学习(六)—ZAB协议

ZAB协议基本介绍

ZooKeeper并没有完全采用Paxos算法,而是使用了一种称为ZooKeeper Atomic Broadcast(ZAB,ZooKeeper原子消息广播协议)的协议作为其数据一致性的核心算法。ZAB是一种专门为zookeeper设计的支持崩溃恢复的原子广播协议

在ZooKeeper中,主要依赖ZAB协议来实现分布式数据一致性,基于该协议,ZooKeeper实现了一种主备模式的系统架构来保持集群中各副本之间数据的一致性。

ZooKeeper使用一个单一的主进程来接收并处理所有客户端的事务请求,并采用ZAB的原子广播协议,将服务器数据的状态变更以事务Proposal的形式广播到所有的副本进程上去,ZAB协议保证了同一时刻集群中只能有一个主进程来广播服务器的状态变更,由主进程来协调处理所有的事务请求,这样能够很好的处理客户端大量的并发请求。

另一方面,考虑到在分布式环境中,顺序执行的一些状态变更其前后会存在一定的依赖关系,有些状态变更必须依赖于比它早生成的那些状态变更,例如变更C需要依赖变更A和变更B。这样的依赖关系也对ZAB协议提出了一个要求:ZAB协议必须能够保证一个全局的变更序列被顺序应用,也就是说,ZAB协议需要保证如果一个状态变更已经被处理了,那么所有其依赖的状态变更都应该已经被提前处理掉了。最后,考虑到主进程在任何时候都有可能出现崩溃退出或重启现象,因此,ZAB协议还需要做到在当前主进程出现上述异常情况的时候,依旧能够正常工作

ZAB核心定义

ZAB 协议的核心是定义了对于那些会改变 ZooKeeper 服务器数据状态的事务请求的处理方式,即:

所有事务请求必须由一个全局唯一的服务器来协调处理,这样的服务器被称为 Leader服务器,而余下的其他服务器则成为 Follower 服务器。Leader 服务器负责将一个客户端事务请求转换成一个事务 Proposal(提议),并将该 Proposal 分发给集群中所有的Follower 服务器。之后 Leader 服务器需要等待所有 Follower 服务器的反馈,一旦超过半数的 Follower 服务器进行了正确的反馈后,那么 Leader 就会再次向所有的 Follower服务器分发Commit消息,要求其将前一个Proposal进行提交。

image-20200706152134404

ZAB协议的崩溃恢复与消息广播

ZAB协议中包含两种最基本的模式:崩溃恢复与消息广播

崩溃恢复

​ 当整个服务框架在启动过程中,或是当Leader服务器出现网络中断、崩溃退出与重启等异常情况时,ZAB 协议就会进入恢复模式并选举产生新的 Leader 服务器。当选举产生了新的Leader服务器,同时集群中已经有过半的机器与该Leader服务器完成了状态同步之后,ZAB协议就会退出恢复模式,所以ZAB需要一个高效且可靠的Leader选举算法,从而确保能够快速的选举出新的Leader。同时,Leader选举算法不仅仅需要让Leader自己知道已被选举为Leader,也要让集群中其他的机器能够快速的感知到选举产生了新的Leader服务器

消息广播

​ 当集群中已经有过半的机器与该Leader服务器完成了状态同步之后,ZAB协议就会退出恢复模式并进入消息广播模式,当一台同样遵守 ZAB 协议的服务器启动后加入到集群中时,如果此时集群中已经存在一个Leader服务器在负责进行消息广播,那么新加入的服务器就会自觉地进入数据恢复模式:找到Leader所在的服务器,并与其进行数据同步,然后一起参与到消息广播流程中去。

​ ZooKeeper 设计成只允许唯一的一个 Leader 服务器来进行事务请求的处理。Leader 服务器在接收到客户端的事务请求后,会生成对应的事务提案并发起一轮广播协议;而如果集群中的其他机器接收到客户端的事务请求,那么这些非Leader服务器会首先将这个事务请求转发给Leader服务器。当Leader服务器出现崩溃退出或机器重启,亦或是集群中已经不存在过半的服务器与该Leader服务器保持正常通信时,那么在重新开始新一轮的原子广播事务操作之前,所有进程首先会使用崩溃恢复协议来使彼此达到一个一致的状态,于是整个 ZAB 流程就会从消息广播模式进入到崩溃恢复模式。
​ 一个机器要成为新的Leader,必须获得过半进程的支持,同时由于每个进程都有可能会崩溃,因此,在 ZAB 协议运行过程中,前后会出现多个 Leader,并且每个进程也有可能会多次成为Leader。进入崩溃恢复模式后,只要集群中存在过半的服务器能够彼此进行正常通信,那么就可以产生一个新的Leader并再次进入消息广播模式。举个例子来说,一个由3台机器组成的ZAB服务,通常由1个Leader、2个Follower服务器组成。某一个时刻,假如其中一个 Follower服务器挂了,整个 ZAB 集群是不会中断服务的,这是因为Leader服务器依然能够获得过半机器(包括Leader自己)的支持。

消息广播的过程

​ ZAB协议的消息广播过程使用的是一个原子广播协议,类似于一个二阶段提交过程。针对客户端的事务请求,Leader服务器会为其生成对应的事务Proposal,并将其发送给集群中其余所有的机器,然后再分别收集各自的选票,最后进行事务提交。

image-20200706170859439

​ 而ZAB协议又与二阶段提交协议有所不同,ZAB的二阶段提交过程中,移除了中断逻辑,并且在有过半的Follower服务器反馈ACK后就开始提交事务Proposal了,不需要等待集群中所有的Follower服务器都反馈响应,一旦Leader发生崩溃并退出,ZAB需要采用崩溃恢复模式来处理Leader崩溃带来的数据不一致的问题。

​ 整个消息广播是基于FIFO特性的TCP协议进行网络通信,因此可以很容易保证消息广播过程中消息发送与接收的顺序性。

​ 在整个消息广播过程中,leader服务器会为每个事务请求都生成对应的Proposal来进行广播,并为其分配一个全局单调递增的唯一事务ID(即ZXID),ZAB协议需要严格的保证每一个消息的因果关系,因此必须将每一个事务Proposal按照ZXID的顺序来进行排序与处理。

消息广播的具体过程

  • Leader服务器会为每一个Follower服务器分配一个单独的队列,并将需要广播的事务依次放入队列中,并且根据FIFO的策略进行消息发送。
  • 每一个Follower服务器在接收到事务的Proposal之后,都会先将其已事务日志的形式写入本地磁盘中区,并且在成功写入之后反馈给Leader服务器一个Ack响应
  • Leader服务器接收到超过半数Follower服务器的Ack响应后,就会广播一个Commit消息给所有的Follower服务器以通知其进行事务提交,并且Leader也会完成对该事务的提交,此后Follower服务器在接收到Commit消息后,也会完成对事务的提交。

ZAB协议的基本特性

ZAB协议规定了如果一个事务Proposal在一台机器上被处理成功,那么应该在所有的机器上都被处理成功,哪怕机器出现故障崩溃。

ZAB协议需要确保那些已经在Leader服务器上提交的事务最终被所有服务器都提交

假设一个事务在 Leader 服务器上被提交了,并且已经得到过半 Follower 服务器的Ack反馈,但是在它将Commit消息发送给所有Follower机器之前,Leader服务器挂了

image-20200706172236494

在Leader服务器Server1广播了消息P1、P2、C1、P3和C2,其中Leader服务器刚刚将消息C2(C2即是Proposal2的Commit消息)发出后就挂了,这时候,ZAB协议还是会在崩溃恢复过程中,确保Proposal2最终能在所有的服务器上都被提交成功,否则就会出现不一致的场景。

ZAB协议需要确保丢弃那些只在Leader服务器上被提出的事务

如果在崩溃恢复过程中出现一个需要被丢弃的提案,那么在崩溃恢复结束后需要跳过该事务Proposal

image-20200706172544691

假设初始的 Leader 服务器 Server1 在提出了一个事务P3之后就崩溃退出了,从而导致集群中的其他服务器都没有收到这个事务Proposal。于是,当 Server1 恢复过来再次加入到集群中的时候,ZAB 协议需要确保丢弃P3这个事务。

**ZAB算法特性:**能够确保提交已经被 Leader 提交的事务 Proposal,同时丢弃已经被跳过的事务Proposal。针对这个要求,如果让Leader选举算法能够保证新选举出来的Leader服务器拥有集群中所有机器最高编号(即ZXID最大)的事务Proposal,那么就可以保证这个新选举出来的Leader一定具有所有已经提交的提案。更为重要的是,如果让具有最高编号事务 Proposal 的机器来成为 Leader,就可以省去 Leader 服务器检查Proposal的提交和丢弃工作的这一步操作了。

ZAB协议中的数据同步

完成Leader选举之后,在正式开始工作(即接收客户端的事务请求,然后提出新的提案)之前,Leader服务器会首先确认事务日志中的所有Proposal是否都已经被集群中过半的机器提交了,即是否完成数据同步

数据同步的过程

Leader服务器需要确保所有的Follower服务器能够接收到每一条事务Proposal,并且能够正确地将所有已经提交了的事务Proposal应用到内存数据库中去。具体的,Leader服务器会为每一个Follower服务器都准备一个队列,并将那些没有被各Follower服务器同步的事务以Proposal消息的形式逐个发送给Follower服务器,并在每一个Proposal消息后面紧接着再发送一个Commit消息,以表示该事务已经被提交。等到Follower服务器将所有其尚未同步的事务 Proposal 都从 Leader 服务器上同步过来并成功应用到本地数据库中后,Leader服务器就会将该Follower服务器加入到真正的可用Follower列表中,并开始之后的其他流程

在ZAB协议的事务编号ZXID设计中,ZXID是一个64位的数字,其中低 32 位可以看作是一个简单的单调递增的计数器,针对客户端的每一个事务请求,Leader服务器在产生一个新的事务Proposal的时候,都会对该计数器进行加1操作;而高32位则代表了Leader周期epoch的编号,每当选举产生一个新的Leader服务器,就会从这个Leader服务器上取出其本地日志中最大事务Proposal的ZXID,并从该ZXID中解析出对应的epoch值,然后再对其进行加1操作,之后就会以此编号作为新的epoch,并将低32位置0来开始生成新的ZXID。ZAB协议中的这一通过epoch编号来区分 Leader 周期变化的策略,能够有效地避免不同的 Leader 服务器错误地使用相同的ZXID编号提出不一样的事务Proposal的异常情况,这对于识别在Leader崩溃恢复前后生成的Proposal非常有帮助,大大简化和提升了数据恢复流程。

基于这样的策略,当一个包含了上一个 Leader 周期中尚未提交过的事务 Proposal 的服务器启动时,其肯定无法成为 Leader,原因很简单,因为当前集群中一定包含一个Quorum集合,该集合中的机器一定包含了更高epoch的事务Proposal,因此这台机器的事务 Proposal 肯定不是最高,也就无法成为 Leader 了。当这台机器加入到集群中,以Follower角色连接上Leader服务器之后,Leader服务器会根据自己服务器上最后被提交的Proposal来和 Follower服务器的Proposal进行比对,比对的结果当然是Leader会要求 Follower 进行一个回退操作——回退到一个确实已经被集群中过半机器提交的最新的事务Proposal。

ZAB协议的算法描述

整个ZAB协议主要包括消息广播和崩溃恢复两个过程,进一步可以细分为三个阶段,分别是发现(Discovery)、同步(Synchronization)和广播(Broadcast)阶段。组成ZAB协议的每一个分布式进程,会循环地执行这三个阶段。

下面先对ZAB协议算法定义几个术语

术语名说明
F.pFollower f处理的最后一个事务Proposal
F.zxidFollower f处理过的历史事务Proposal的事务标识ZXID
h.f每一个Followe f通常都处理了不少事务,这里针对已经处理过的事务的集合,将其表示为hf,表示Follower f已经处理过的事务队列
Ie初始化历史记录,在某个主进程周期 epoch e中,当准Leader完成阶段一之后,此时它的h.f标记为Ie

阶段一,发现

阶段一主要就是Leader选举过程,用于在多个分布式进程中选举出主进程,准Leader L和Follower F的工作流程分别如下:

  1. 步骤F.1.1 Follower F将自己最后接受的事务Proposal的epoch值CEPOCH(F.p)发送给准Leader L。
  2. 步骤L.1.1 当接收到来自过半 Follower 的 CEPOCH(F.p)消息后,准 Leader L 会生成NEWEPOCH(e′)消息给这些过半的Follower。关于这个epoch值e′,准Leader L会从所有接收到的CEPOCH(F.p)消息中选取出最大的epoch值,然后对其进行加1操作,即为e′。
  3. 步骤F.1.2 当Follower接收到来自准Leader L的NEWEPOCH(e′)消息后,如果其检测到当前的CEPOCH(F.p)值小于e′,那么就会将CEPOCH(F.p)赋值为e′,同时向这个准Leader L反馈Ack消息。在这个反馈消息(ACK-E(F.p,hf))中,包含了当前该Follower的epoch CEPOCH(F.p),以及该Follower的历史事务Proposal集合:hf。
    当Leader L接收到来自过半Follower的确认消息Ack之后,Leader L就会从这过半服务器中选取出一个Follower F,并使用其作为初始化事务集合Ie'。
  4. Follower F的选举,选择返回过半Follower的服务器中CEPOCH值最大并且F.zxid最大的那个服务器

阶段二,同步

完成发现流程后,进入同步阶段,在这一阶段中,Leader L和Follower F的工作流程分别如下

  1. 步骤L.2.1 Leader L会将e'和Ie'以NEWLEADER(e',Ie')消息的形式发送给所有Quorum中的Follower,就是将最新的任期以及初始化数据以消息的形式广播给所有的Follower

  2. 步骤F.2.1 当 Follower 接收到来自 Leader L 的 NEWLEADER(e',Ie')消息后,如果Follower 发现 CEPOCH (F.p) ≠ e',那么直接进入下一轮循环,因为此时Follower发现自己还在上一轮,或者更上轮,无法参与本轮的同步。

    如果CEPOCH (F.p)=e',那么Follower就会执行事务应用操作。具体的,对于每一个事务 Proposal:<v,z>∈Ie′,Follower 都会接受<e',<v,z>>。最后,Follower会反馈给Leader,表明自己已经接受并处理了所有Ie'中的事务Proposal。

  3. 步骤L.2.2 当Leader 接收到来自过半Follower 针对NEWLEADER(e',Ie')的反馈消息后,就会向所有的Follower发送Commit消息。至此Leader完成阶段二。

  4. 步骤F.2.2 当Follower收到来自Leader的Commit消息后,就会依次处理并提交所有在Ie′'中未处理的事务。至此Follower完成阶段二。

阶段三,广播

完成同步阶段后,ZAB协议就可以正式开始接收客户端新的事物请求,并进行消息广播流程

  1. 步骤L.3.1 Leader L接收到客户端新的事务请求后,会生成对应的事务Proposal,并根据ZXID的顺序向所有Follower发送提案<e',<v,z>>,其中epoch(z)=e′。
  2. 步骤F.3.1 Follower根据消息接收的先后次序来处理这些来自Leader的事务Proposal,并将他们追加到hf中去,之后再反馈给Leader。
  3. 步骤L.3.1 当 Leader接收到来自过半 Follower针对事务 Proposal<e',<v,z>>的 Ack消息后,就会发送Commit<e',<v,z>>消息给所有的Follower,要求它们进行事务的提交。
  4. 步骤F.3.2 当Follower F接收到来自Leader的Commit<e',<v,z>>消息后,就会开始提交事务Proposal<e',<v,z>>。需要注意的是,此时该Follower F必定已经提交了事务Proposal<v',z'>,其中<v',z'> ∈。image-20200706235344711

在正常运行过程中,ZAB协议会一直运行于阶段三来反复地进行消息广播流程。如果出现Leader崩溃或其他原因导致Leader缺失,那么此时ZAB协议会再次进入阶段一,重新选举新的Leader。

流程总结

消息说明:

  • CEPOCH:Follower进程向准Leader发送自己处理过的最后一个事务Proposal的epoch值。
  • NEWEPOCH:准Leader进程根据接收的各进程的epoch,来生成新一轮周期的epoch值。
  • ACK-E:Follower进程反馈准Leader进程发来的NEWEPOCH消息。
  • NEWLEADER:准Leader进程确立自己的领导地位,并发送NEWLEADER消息给各进程。
  • ACK-LD:Follower进程反馈Leader进程发来的NEWLEADER消息。
  • COMMIT-LD:要求Follower进程提交相应的历史事务Proposal。
  • PROPOSE:Leader进程生成一个针对客户端事务请求的Proposal。
  • ACK:Follower进程反馈Leader进程发来的PROPOSAL消息。
  • COMMIT:Leader发送COMMIT消息,要求所有进程提交事务PROPOSE。

image-20200706235538864

ZAB协议运行时状态分析

ZAB协议设计中,每一个服务器都可能处于以下三种状态之一:

  • LOOKING:Leader选举阶段
  • **FOLLOWING:**Follower服务器和Leader保持同步状态
  • LEADING:Leader服务器作为主进程领导状态

集群中机器的初始化状态都是LOOKING状态,此时所有的机器会试图选举出一个Leader,如果进程发现已经选举出了Leader了会立刻将自身状态切换至FOLLOWING,并开始于Leader保持同步。

由于Leader服务器随时会挂掉,当Leader服务器已经崩溃或者放弃领导地位后,其余的Follower进程会转换到LOOKING状态,并进行新一轮的Leader选举,因此在ZAB协议运行过程中,每个服务器都会在LEADING,FOLLOWING,LOOKING状态之间不断地转换。

在完成选举出了Leader服务器后,这个Leader服务器只能称为准Leader,只有在完成阶段二,Leader服务器与过半的Follower服务器完成数据同步后,他才能称为一个真正的Leader服务器,可以开始接收事务请求了。

Leader服务器会为每一个Follower都会建立一个操作队列,Leader进程与所有的Follower进程之间都会通过心跳检测机器来感知彼此的情况,如果Leader不能在超时时间内收到过半的Follower心跳检测或者TCP本身连接断开,那么Leader服务器会终止该周期的领导,并将状态转换为LOOKING状态,其余的Follower也会将状态切换到LOOKING状态,并进行新一轮的Leader选举,并在选举产生新的Leader之后重新开始阶段一、二、三。

ZAB协议与Paxos的差异与联系

ZAB协议与Paxos算法的联系:

  • 两者都有一个类似Leader进程的角色,Paxos算法中是一个主Proposer提供提案,ZAB协议是Leader服务器协调多个Follower进程
  • Leader进程都使用过半原则,只需要过半的Follower做出正确反馈后,才会将提案进行提交
  • 在ZAB协议中,每个Proposal都包含了一个epoch值,用于标识当前Leader周期,同样,Paxos中也存在一个这样的标识,只是名字为Ballot

ZAB协议与Paxos的不同:

  • 在Paxos算法中,新选举的主进程会进行两个阶段工作,一个阶段是读阶段,用于收集上一个主进程提出的提案,并将该提案提交。在进入第二个写阶段后才开始提出自身的提案,而ZAB协议在此添加了一个同步阶段,在发现阶段之后(类似于Paxos的读阶段),新的Leader会确保过半的Follower已经提交了之前Leader周期内所有可提交的事务,在此阶段之后就进入类似于Paxos算法写阶段的广播阶段。

ZAB协议与Paxos算法本质区别在于,ZAB协议主要用于构建一个高可用的分布式数据主备系统,而Paxos算法则是用于一个分布式的一致性状态机系统