分布式系统入门笔记(五):ZooKeeper之ZAB一致性协议

  得益于Zookeeper在生产环境的广为使用,ZAB(ZooKeeper Atomic Broadcast,ZooKeeper原子消息广播协议)可算是最广泛应用的分布式一致性协议了,其是对Paxos算法进行了大量的改进后形成的分布式系统数据一致性协议。当之前了解Paxos和Raft算法后,落下ZAB总觉得欠缺了那么点什么。查看资料发现ZooKeeper是2007年开始开发的,而Raft算法2013年才正式发布,所以Raft中的一些设计难免会借鉴ZAB,两者存在了很多相似之处,不过多了解多掌握,想必对于分布式系统原理的融汇贯通还是会大有裨益的!

一、前言

  首先强调一点,无论是ZAB还是Raft,作为生产环境都极度强调了事务严格按照客户端请求的顺序提交,这一点在Zab+vs.+Paxos中解释的很清楚:
  Paxos注重的是一个状态机模型,一致性协议保证所有的状态机副本以相同的顺序执行相同的指令,那么所有状态机可以保证以相同的状态变化进行转移。而为了性能方面的考虑,一致性算法都允许客户端提出多个提议,当客户端并行或者重叠地提出多个决议的情况。在MultiPaxos就有了提交窗口的概念,但是在某个时刻点Leader发生崩溃后,对应的提交窗口中的提案可能有的提案被提交,有提案未被提交,那么新选出来的Leader可以按照任何顺序重新组织这些提案的表决和提交顺序,甚至也有可能会被丢弃掉。所以,Paxos算法没能够保证严格的因果一致性。
  ZAB和Raft注重的是主备(primary-backup)工作模式,各个副本节点会严格按照Leader接收到客户端请求的顺序进行提交,所以可以描述为一种可靠的增量状态更新。客户端可以提出多个决议,这些决议保证会按照FIFO的顺序被提交,即便在Leader崩溃后发生Leader选取的情况下也会有此保证。虽然,Paxos可以不开启提交窗口的功能,任何时候都只允许有一个未提交的决议,那么就可以得到严格序列化的状态转移,但是相比ZAB和Raft这种专门设计优化过的一致性协议,性能会大打折扣;还有就是Paxos算法可以通过将多个提案封包成batch模式,然后整体显露作为一个提案来表决处理(PhxPaxos有这么一个特性)以提高性能,但是按照Paper所述这些改进措施不见得性能会有多大的提高。

  可能是我看的文献比较旧吧,没有介绍到ZooKeeper成员的自动变更,只能通过重启集群的方式才能变更成员。后面看手册知道3.5.0开始支持动态成员变更,不过该版本目前仍然处于alpha状态,所以生产环境目前暂且还是持观望态度吧。所以这点来说,Raft算法通过产生一个过渡一致性状态,可以在不停服务进行动态成员变更,算是做的比较好的。
  从ZooKeeper官方的项目列表观来,其已经扮演者一个通用分布式系统的库或者框架的角色了,通过将分布式系统中一致性这个最复杂、最本质的问题进行实现和封装,同时向上提供简洁统一的数据模型和操作接口,就可以在该基础之上快速构建分布式应用了。

二、ZAB协议的基本知识

  ZooKeeper对外展现的是一颗类似Unix文件系统的树形数据模型(形如/foo/path1),其基本元素称之为数据节点(ZNode),ZNode并不是用来存储实际的数据,而是代表着一种状态信息。ZNode可以分为持久节点和临时节点两种类型:持久节点是一旦创建后,除非主动进行ZNode的移除操作,否则这个ZNode将一直保存;临时节点的生命周期和客户端会话相绑定的,一旦客户端会话失效,那么这个临时节点将会被自动移除。同时,ZAB还可选对每个ZNode附加一个SEQUENTIAL属性,具有这样属性的节点在创建的时候,ZooKeeper会在其尾部追加一个递增的整形数字,这样不仅可以用于创建多个ZNode,而且某种形式上保留了一种次序信息。然后通过提供ZNode的创建、删除、侦听(Watcher)等接口,加上ZNode持久性和临时性的特点,就可以实现集群选主、消息队列等各种分布式服务和模型。
  ZAB也是在协议中,规定集群中只有唯一的Leader,负责处理所有客户端的变更事务请求,通过广播的形式将事务传输到其他Fellower节点上形成副本,每当Fellower接收到事务后首先将其以事务日志的形式固化保存到本地,并向Leader返回Ack确认信息;当Leader一旦收到超过半数的Fellower节点的Ack反馈后,Leader就会再次向所有的Fellower节点发送Commit消息进行事务提交。这种主备的工作形式和2PC十分相像,但是两者还是有着本质的差异。还有,ZAB保证会按照客户端的事务请求顺序执行事务提交的,因此保证了严格的因果一致性。
  从Client的角度上,Client可以向集群的任何一台机器发送请求,如果该请求会引发状态机的改变(非只读请求),就会被转发到Leader节点;而任何节点都可以直接处理Client的只读类请求,这样一定程度上保证了系统的高可用性,而Client如果想要保证只读请求事务得到的副本是最新的,可以向其直接连接的服务器发送sync请求。在ZAB中,所有更新事务都会由一个64位的事务编号ZXID来标示,这也是实现前面严格提交顺序的基础,ZXID的高32位代表了Leader的周期epoch编号而低32位是一个简单连续单调递增的计数器,Leader接收到客户端的每一个请求,在产生新事务的时候都会对该计数值+1;每当选举产生一个新的Leader的时候,就会从这个Leader服务器上取出本地日志最大事务Proposal的ZXID,并提取出周期epoch进行+1,然后低32位置零从新开始计数。
p-a-c
  在工作过程中,任意时刻集群中的任意节点都可能随时崩溃退出,ZAB保证了在大多数集群成员正常工作的情况下,整个集群也能够正常工作。

三、ZAB协议中四个Phase介绍

  ZAB协议规定了整个集群所有节点具有4个Phase阶段:在Phase0会进行Leader Election选主操作,后面会依次经历Discovery、Synchronization、Broadcast状态的迭代。集群稳定工作的时候节点会一直处于Phase Broadcast响应客户端的请求,该阶段下集群的工作模式类似于2PC两阶段提交,但是没有2PC中的中断事务的情况,即没有事务回滚情况的发生,同时ZAB也不必等待所有成员的Ack响应,只要过半服务器回复Ack应答之后就可以进行事务提交了,从而允许少部分Fellower非正常的情况下整个集群仍然工作。集群的Leader和Fellower会通过心跳信息保持相互感知,Fellower会向Leader发送心跳消息,如果Leader在指定的超时时间内不能够得到过半数目Fellower的消息,其就会终止当前任期的Leader角色,所有的Fellower也会放弃该Leader,进入到Phase 0阶段重新进行选主;而Fellower如果在超时之后没有收到Leader的消息,也会切换到Phase 0选主的状态。
  对于每个节点,需要关注以下几个持久化变量的状体,他们跟节点的工作和Phase阶段的切换密切相关:
  history:已经被接收的提案的日志信息
  acceptedEpoch:接受到的最后一个NEWEPOCH消息的epoch
  currentEpoch:接受到的最后一个NEWLEADER消息的epoch
  lastZxid:history中最后一个提案的ZXID编号

3.1 阶段0: Leader Election

 在ZAB中并没有强制某种Leader选取算法,只需要能够得到集群中过半数的vote选票,该节点就可以成为Leader。后面我们会看到,ZooKeeper实现了一个FLE快速选主算法。要注意,只有进入Phase3阶段,Leader的身份才真正的确定,在此之前都是每个节点记录自己所投的prospective Leader,后面要进行一个恢复状态(数据同步)的过程。

3.2 阶段1: Discovery

  在这个阶段,虽然prospective leader只是一种一对一的关系,但是候选Leader肯定是集群中过半数机器的prospective leader。此时所有节点会把自己的F:acceptedEpoch通过FOLLOWERINFO发送给自己的prospective leader,当那个候选Leader得到过半的FOLLOWERINFO消息时候,会在收到消息中取出所见最大的epoch并将其递增,这样之前的Leader就不能再提交新的提案了,然后该候选Leader再将这个新epoch通过NEWEPOCH消息发回给这些节点并等待确认。
  在Fellower节点收到候选Leader发送NEWEPOCH后,将其与自己本地的acceptedEpoch对比,如果比他们大就更新自己acceptedEpoch,并返回ACKEPOCH消息后进入Phase 2,否则切换会Phase 0状态。候选Leader也只能在收到过半数目的ACKEPOCH才会进入Phase 2。需要注意的是这里Fellower发送的ACKEPOCH包含了额外的重要信息——自己最新提交日志,这样候选Leader在收集ACKEPOCH的同时就知道哪个Fellower具有最新提交了,选定到这个具有最新提交的Fellower后向其同步日志。
discovery
  可见,这个Discovery就是要在过半机器中发现最大提案,使得候选Leader在创建一个新epoch周期的同时,也向具有最新提交的Fellower节点同步得到最新提交日志,方便了下一步向其他Fellower同步日志信息。

3.3 阶段2: Synchronization

  进入这个阶段后,候选Leader已经确立了最新任期号和最新提交日志,然后他会把自己的history通过新epoch作为NEWLEADER消息发送给所有的集群成员,集群成员更新自己currentEpoch 并按需同步history信息。完成这个步骤后候选Fellower向Leader发送ACKNEWLEADER消息,而候选Leader得到过半数目的ACKNEWLEADER消息后,会向所有的Fellower发送COMMIT并进入Phase 3,而Fellower接收到COMMIT命令而完成提交后,也会切换到Phase 3。
sync

3.4 阶段3: Broadcast

  到达这个阶段后,所有节点检查自己的prospective leader,如果发现它是自己,就切换到正式Leader的状态,不是这种情况的节点切换到正式Fellower的状态,而一致性协议保证此时只可能会有一个Leader。这是整个集群稳定工作状态,其基本流程也类似于上面提到的Propose-ACK-COMMIT的伪2PC操作,只要。
broadcast
  因为只需要得到集群中过半机器的支持,Leader就可以通过上面Phase的迭代而成为新epoch的正式Leader。那些落后的Fellower也允许加入到这个新epoch中来,我们看见Leader仍然保持接受FOLLOWERINFO消息的请求,然后直接返回NEWEPOCH和NEWLEADER消息,接收到该消息的Fellower更新epoch并同步日志后ACKNEWLEADER,接着Leader发送COMMIT命令让其提交。
  在这个阶段,还有一点需要额外注意的是当某个Fellower因为某种原因错过了某些提交,而当前接收到的Leader的提案和自己提交历史之间存在空洞的情况。在图上我们看到存在outstanding transaction的时候Fellower的处理的方式就是Do nothing(wait),我还没看到具体的实现是什么意思,难道是要阻塞自己到超时,然后通过上面的机制进入Phase 2 Synchronization进行提交事务同步么?

四、ZooKeeper中的FLE选主约束

4.1 一致性算法的选主要求

  分布式系统一致性协议中的重点和难点,就是在Leader崩溃后集群选举出新的Leader,在这种临界情况下对于未完成的提案的正确处理。安全的一致性协议应当保证:
  (1). 确保那些已经在Leader服务器提交的事务,最终都会被所有的服务器提交。
  其临界情况就是当Leader获得绝大多数Ack反馈,但是在其将Commit消息发送给所有Fellower之前崩溃了(已经发出但是Fellower没有收到);
  (2). 确保丢弃那些只在Leader服务器上仅被提出的事务。
  其临界情况比如Leader在提出一个事务之后就崩溃退出了,而后来该Leader复活后再次加入集群中时候,ZAB协议需要确保丢弃这个事务;
  如果集群中任意一个Fellower都可以被选取成为候选Leader,那么候选Leader就需要通过上面Phase 1 Discovery的方式搜集所有Fellower的提交信息以寻找得到具有最新提案的Fellower并与其进行同步,然后在Phase 2阶段候选Leader以自己作为标杆再将最新提交信息发送给那些落后的Fellower。而如果让选主算法能够保证新选举出来的候选Leader拥有集群中所有机器最高事务编号(ZXID)的事务,那么就可以保证新选举出来的Leader一定具有所有已经提交的提案了,则Phase 1的工作就可以被省略掉了!

4.2 FLE选主算法下的Phase转化

  ZAB协议没有对Phase 0选主协议具体化,通过任何方式获得绝大多数Fellower的vote都可以成为候选Leader进而进入Phase 1阶段,而由上面可知Phase 1的主要职责就是产生新的epoch,同时发现具有最新提交日志的Fellower并向其同步提交日志。在ZooKeeper的实现中,设计了一种叫做FLE的选主算法,在要求候选Leader获得绝大多数vote的同时增加了一条额外的约束:候选Leader必须在绝大多数成员中具有最新的提交历史,这种约束条件下产生Leader后就可以直接忽略Phase 1阶段的操作了(看看,这个跟Raft的选主约束是何其的相似啊!)。然后,论文中将Phase 1和Phase 2结合起来称之为Phase Recovery。
  Phase Recovery的工作过程和Phase 2的情况很不相同,此时选举出来的Leader成为了正式的标杆。同样在这个阶段开始的时候,Fellower会向自己的prospective leader发送自己最新提案号lastZxid,候选Leader接收到该消息后同自己的lastCommittedZxid进行比对,并根据比对结果反馈响应的消息类型:
  (1). 如果f.lastZxid比候选Leader的lastCommittedZxid要大,则Leader向其发送TRUNC消息,使该Fellower中不应当被提交的议案被丢弃掉;
  (2). 如果f.lastZxid比候选Leader的lastCommittedZxid要小,但是比oldThreshold要大,则发送两者的差异DIFF消息完成同步;
  (3). 如果f.lastZxid比候选Leader的lastCommittedZxid要小,而且比oldThreshold还要小,说明该Fellower已经太过于落后了,候选Leader直接发送完整SNAP快照给Fellower使其进行更新;
  当Fellower接收到上面的消息后,根据消息类型对自己的提交进行同步更新,然后向候选Leader发送ACKNEWLEADER确认信息,自己进入Phase 3;而当候选Leader接收到过半的ACKNEWLEADER信息后,自己也进入Phase 3成为正式Leader。
broadcast

4.3 ZooKeeper中FLE算法简介

  FLE的算法流程还是比较复杂的,这里先不细究了,后面可以找个时间单独理一下,这里先描述一下大概的思路。
  使用FLE算法的目的,就是要选出具有最大提交历史的节点作为候选Leader,这样后续的日志就只需要考虑候选Leader到其他Fellower节点的单向同步就可以保证一致性了。在FLE算法中通过筛选具有最大lastZxid的节点作为候选Leader,因为具有最大lastZxid的节点肯定具有最全的提交历史。
  在FLE算法中,每个节点都只能投一张选票,只有这样才能确定过半选票的统计值,其思路就是在投票的过程中,节点之间互相交换信息,然后节点根据自己获得的信息(发现更好的候选者)不断地更新自己手中的选票,更新的标准就是具有更新的提案号:要么具有更新的epoch,或者在相同epoch下具有更大的编号。那么这个迭代更新的过程什么时候结束呢?
  首先,每一轮的选取会有一个递增的round number作为标识,这个值越高优先级越高;其次,每一个节点都有一个状态标识自己:election和leading/fellowing,同时每个节点都知道集群中其他节点的个数,以及和他们通信的方式。选举刚刚开始的时候,每个节点在没有先验信息的情况下都把选票投向自己,并把这个消息发送给所有的节点,然后等待其他节点们的响应,节点再收到这个消息的时候:
  (1). 如果选票的round number比较旧,则忽略之;
  (2). 如果选票的round number比自己新,则更新自己的round number,并清空上一轮相关的陈旧信息,开始广播自己新的选票;
  (3). 如果是在同一轮投票中:如果接收到的选票的角色是election,并且该消息附带更新的提案号,则更新自己的选票并继续广播自己的选票;如果收到的选票角色是election,但是消息的提案号比自己旧或者跟自己一样,则记录这张选票,而检查发现自己得到针对某个节点超过集群半数的选票,自己切换为leading/fellowing状态,并转入Phase Recovery;
  (4). 任何时候一旦收到leading/fellowing的选票,都指明当前集群中已有有效的候选Leader了,直接更新自己切换入Phase Recovery阶段;
  千言万语,还是伪代码图比较的清晰明了:
FLE

本文完!

参考