12
Jun
2014

Paper Rush-2: Apache ZooKeeper & ZAB

引言(Introduction)

ZooKeeper(通常简称ZK)为Apache比较出名的一个开源项目,其定义为"a service for co-ordinating processes of distributed applications",提供多种集群机器协调同步服务,如分布式锁,配置通知,目录查找等等。其核心是ZAB(Zookeeper Atomic Broadcast),它提供以下功能:

  • 全顺序(Total Order):顺序写(Linearizable Write),结果按顺序(FIFO)在每个客户端生效,通俗点说就是你写的是什么顺序,在客户端生效的就是什么顺序;
  • 完整性(Integrity):即收到的数据肯定是发送的数据,而且发送成功了就肯定能收到;
  • 高容灾(Fault Tolerance):对任意台机器,只要有机器正常,则集群便能正常工作

这里我们先介绍ZooKeeper系统身来再介绍ZAB。

原理及实现(How it works&Implements)

Zookeeper

概览

就我看来ZK设计的应用场景不针对具体,它提供的是最基础的功能模块,在此之上,开发者可以构建适应多种应用场景,如配置同步、分布式锁、分布式队列等等。一个典型的ZK部署结构如下图所示:


首先ZK里的实例(Replicate)分为可以有四种状态:Leading、Following、Observing与Looking,对应的角色分别为:Leader(也被称为Primary Replicate)、Follower与Observer。 所有的写请求都是走Leader,然后通过ZAB同步到其它实例,如果数据有处于Watch状态的客户端,再通知客户端。当然Leader其实自身也会包含Follower的功能,客户端也是可以从Leader那里获取到数据变更通知的。简单来说,Leader的就是负责接入新数据并协调同步到其它Follower那里,其它功能与Follower一样。ZK在启动的时候,需要选举出一位Leader,选举的时候只要大多同意就能够产生(具体的选举算法详后文),之后Leader需要与Follower保持长连接并定期发送心跳包以探测对方健康情况。说到心跳包,这里我想多说一下,我们知道其实TCP本来就是有Keep Alive机制的,为什么还需要应用层再去处理一遍呢?首先:于TCP的在空闲(Idle)状态的探测间隔不是应用层能够设置的,这个是在OS参数里的,而且对于Linux系统,这个参数会影响到所有的连接探测;其次:一般来说这个间隔都非常大,而且最小的单位是秒,所以用TCP的这个机制来说连接的健康检测是非常不方便灵活的。现在回到我们刚才的话题,一旦Leader与大多数Follower失去联系或者Follower与Leader失去联系,相应的ZK实际都会重新进入到选举阶段。

ZK的消息通知示意图

数据结构/功能

ZK数据结构的核心就是一颗树,每个结点被称为ZNode,ZNode有两种:一种是普通持久的(Regular),另一种则是非持久的(Ephemeral),非持久在当创建其主机与ZK断开连接时,ZK会自动删除。可别小看了非持久结点,诸多功能(如分布式锁,下面会详细讨论)都是依赖它才得以实现的。一颗典型的ZNode树如下所示:



一个ZK结点树示意图

在这里不同的应用可以选择自己的命名空间,也就是将ZNode挂载至哪个父结点下,ZNode存储的是数据内容,这个数据大小默认为1MB[5],但是是可以调整的,但建议不要调太大,因为数据都是需要加载到内存中的。ZK的一些API提供了一个Watch Flag,设置后可以对结点的状态进行监控,即 getData(path, watch),当监控的数据发生变化是就能得到及时的通知。基于此,我们就能实非常简单地实现一个配置同步的功能,具体如下:

  • 假设存在三个进程,首先预建一个znode:
  • 调用 getData(path, watch) 对Z1进行watch便可获得最新的数据;
  • 之后任何进程如需要更新,调用 setData(path, data, version) API即可(注意这里的version必须比已有的新,否则会更新失败,当然啦,也可以设置成-1,表示不进行版本检测) ;
  • 其它进程便可由watch来获得最新的配置信息。 

注:如果想同时保存多条历史记录,可以在创建时创建一个Parent ZNode:,以后所有的数据都挂载至它下面,之后调用getChildren(path, watch),便可下面的子结点状态进行监控。

是不是很简单?为了保证写顺序,ZK采用的是“一写多读”部署结构,也就是说,每次写都是写Leader,之后ZK会严格按到达的顺序基于ZAB将数据同步到各Follower。由于这种机制的存的,数据写便成了ZK的一个性能瓶颈,而且会随着机器数器的增加而线性下降。ZK的每个接口都提供同步与异步两种接口。除了上面说的那几个之外,还有一个比较有趣的接口,那就是 sync(path),这个接口的具体作用是:自调用起,等待之前的异步操作完成。这么一来,我们就可以进行多路并发操作,最后使用 sync 接口等待所有任务完成。现在我们来理解一个Quorum的概念,也就是大多数,其理论定义如下:

..............[公式1]

就是说对任意的两个Quorum,其交集不等于空。然后对于写入数据,ZK都能提供以下保证:

  1. 如果一个写被一个Q接收成功,则该写对于整个ZK集群就是成功的,故障的机器将在恢复后同步;
  2. 只要一个Q的机器正常工作,则整个ZK集群也能正常工作,只要那些故障的机器能能够最终恢复过来。

下面我们来看一看如何用ZK来实现一个简单的分布式锁。

Lock

  1. n = create(L + “/lock-”, EPHEMERAL|SEQUENTIAL) // 在父结点下建立一个非持久结点,SEQUENTIAL 标志位会保证结点名称的唯一性并按顺排在所有之前的孩子之后
  2. C = getChildren(L, false) // 获取父结点 L 下所有的子结点
  3. if n is lowest znode in C, exit // 如果 n 是最小的,就说明前面没有进程在占用这个锁了,自然可以运行了,所以便可以退出了
  4. p = znode in C ordered just before n // 如果不是,则获取前一个等待进程创建的结点
  5. if exists(p, true) wait for watch event // 对 p 进行 watch,若 p 失效了,则说明前面等待的进程已经完结
  6. goto 2

Unlock

  1. delete(n) // 显示删除自己创建的 znode,以表示锁释放

总的来说确实是非常高效简洁的一种实现分布式锁的方法,ZK真的就像积木一样,开发者们可以依靠其提供的基础API打造属于满足于自己需要的系统。除了上面说明的两个之外,ZK还可以实现更复杂的功能,比如集群管理(Group Management),读写锁(Read Write Locks),大家可以自行查阅,这里就不多说了。值得一提的是ZK的setData(node, data, version)接口还支持条件更新,如果Server中的版本与传入的不一致,那么就会更新失败,如果版本设置的是-1,那么禁用了这个功能。

性能

前面说了,ZK是单写入模式,然后通过ZAB同步到其它实现,在集群实例比较少的情况下,写入的瓶颈完成由Leader的性能决定。在集群数较多时,ZAB的同步瓶颈便显现出来。而对于读,就可以充分利用集群的优势,其性能基本上是随着机器数的增加而线性增涨。实验结果如下表所示:

上图:ZK数据读性能测试;下图:ZK数据写入性能测试

ZK写性能低的另一上原因是,每次写入Leader写入后,需要通过ZAB同步给Quorum数量的机器,并且都落盘成log之后才会返回成功。这就造成一个问题,随着集群机器数量的增加,ZK的写入性能会线性下降。


ZAB(ZooKeeper Atomic Broadcast)

单从功能上讲,ZK大抵如此,现在我们来讨论一下最核心的ZAB。ZAB其实就是分布式一致性算法Fast Paxos的一个实现。主要分为:选主、同步、恢复,这三部分。


选主

首先来说选主,如下列图所示:

选举的过程分为两个阶段,四个步骤。

  1. [1a Prepare]每个实例根据自己的历史记录,选择最大的一个序号N至其它实际,这条消息被称作Proposal N,简称
  2. [2b Promise]当一个Acceptor收到时,就向发送方发送回执,里面的内容是自己数据的历史记录,同时保证不再接收小于N的Proposal;
  3. [2a Accept!]当一个实例收到Quorum机器数量的回执时,会认为自己获得推举,这里根据回执的历史记录找出最大的(至于大于的意义,下面会再说)那个作为本次epoch的初始历史;
  4. [2b Accepted]每个收到Quorum回执的实际向其它实际发起NEWLEADER消息,内容是,当收到Quorum数量的回执后便正式被选举成Leader。为什么需要这步呢?因为在某些情况下可能推举出两个Leader,例如:, , , ,他们的序号从小至大,由于网络延迟原因,可能,,先推举出,但后来加入了,那么就也会被推举成Leader,但由于每个推举的Leader必须收到Quorum数量的回执才视为成功由于,且每次向被推举的实例发起回执时便保证不再响应比其小的请求,所以不存在两个Leader同时通过选举的情况,否则

这里有几个地方可以稍微进行一下优化:

  1. 在刚启动时,由于所有实例的历史记录都是为空,所以不需要收集Acceptor的历史,直接可以到第3步,只要每次Acceptor到序列号为N的消息后,就不再接收那之前的就可以了;
  2. prepare与accept!都可以只发送给一个Quorum的机器就足够了,只要这个Quorum只的机器都是存活着,且能与之通信;

这里有一点需要明确,ZK实例状态的先后是依据什么来比较的?其理论定义如下:

 


其中  ..........[公式2]


如果你没有看懂,没关系,我这里们举个例子来说明:

  • 推荐的节点的纪元比当前的节点的Epoch要大,可以举个列子,有一个人从秦代穿越过来,一个是现代人,如果我们想选择哪个人更加了解历史,我们一般会选择现代人;
  • 如果不满足第一点,则比较节点的更新操作Counter数量,更新比较频繁的节点则推荐该节点id,举个例子,两个都是现代人,我们会选择那个拼命学习历史知识的人;
  • 如果还是不能满足上面两点,则推荐zxid大的,比如说,我们选择那个身份证比较大的人。

广播

对于ZK的广播,有特性:

  • [B1]如果一个Replicate:  向  连续发送了两个事务z',z且,那么接收的顺序也必定是先z'后z
  • [B2]所有的ZK实例都会按照先后顺序(Total Order)来提交事务:即如果提交了提交了,那么必须提交或者,另外,如果,则在提交前必须提交
  • [B3]所有Replicate提交的数据都是按到达Master的顺序一致的。

选举完成后就可以开始广播了。Leader需要与所有的Follower维持一个健康检测长连接,当与Leader正常维持的健康机器少于一个Quorum时,便需要重新进行选举。每次选择一出一个新Leader,就开启一个新的Epoch。按照上面的算法,新的Leader会包含上一个Epoch最新的历史记录。Leader每次在广播的时候,也是采取二段提交(Two-Phase Commit)的方式——只是没有取消(Abort)操作——向所有Follower提起一个事务(v,z),然后进行Prepare(e, (v,z)),每次在返回Prepare的ACK之前都会将数据先写到磁盘上以用于保证在Commit的时候能够成功,当Quorum数量的Replicate返回Prepare的ACK后,Leader就会发起Commit(e, (v,z))操作,每次事务由一个串性唯一的Zxid进行标识,事务的先后顺序也是由此保证的。当Follower收到;Commit除了会向上层应用递交本次事务以外,还会把所有之前的一起递交了,即的事务。

现在我们来回答一个问题:为什么Qumron数量的Replicate返回Promise的ACK之后Leader就可以发起Commit了?这里存在两种情况:

  1. 某台机器由于网络原因,接收延迟,没有在规定时间返回Promise的ACK。对于这种情况,根据B1特性,对慢的那台机器而言最多也就是同步慢点,最终也是能达到一致的。由于ZK使用是TCP长连接,TCP本身提供顺序保证,所以B1特性是显而易见的。
  2. 某台机器由于网络原因,与Leader失去联系。于对这种情况,该机与Leader的长连会失效,本机便会重新进入到搜索Leader的状态,之后便可以从其它主机那里获取到同步数据。

恢复

对于故障恢复,Zab有以下几点应对措施:

  • 每个Replicate存储的都是全量副本,即使一台出现故障,客户可以很快重连接到其它正常Replicate上。
  • Leader与每台Follower都建立有长连接,不管是Leader还是Follower出现故障都可以非常迅速地侦测。如果是Leader出现故障便新进入到选主过程,在此期间ZK是暂时不可写的。
  • 每次返回Prepare的ACK消息前,都会将数据写在磁盘上,每次Commit前都需要有Quorum数量的机器返回成功才行。

下图反应了各种故障情况对ZK的读写影响,该测试集群有5台机器:


  • [1,2] 单个Follower故障
  • [3,5] Leader故障
  • [4] 两个Follower同时故障

理论证明(Proofs)

这里由于篇幅原因,只对一个比较重要的特性加以证明解释,其它可以自行参看Zab论文[2]。


1. ZK满足全序(Total Order)特性:即如果一个ZK实例提交了前提交了,则任意一个实例在提交必须提交

证:

表示实例当前的历史,由已知得:

 ......................[1]

(意思是数据D等于数据D',并且在各自己的历史记录中)

要证明的是

如果

   显然有

如果

   设表示实例R在选主时最终被确认作为本次epoch的初始历史记录,所以有:

........................[2]

(由于每次在投票中,自己的投递的历史记录不一定会被选为本次epoch的基线,而Master始终会选择最大那一个,因此最终的值肯定是自己的后续超集)

   则:

..........................................[3]

   由于每次选主成功后,Leader均是选取版本最新结点的历史作为本次epoch的基值,则

................................[4]

   结合公式2与公式4得:

...........................[5]

  又由已知得:

.....................................[6]

   那么就有:

  ................................................[7]

   到公式7,我们就成功证明了数据D'也存在于R'的历史记录中,之后由于假设R'历史为R历史的先序,而D'先于D于R历史中且D'存在于R'的历史中,即有:


如果

   有

........................[8]

  由假设知:

.................................[9]

  同理同样:

  


证毕。


参考资料(References)

  1. ZooKeeper: Wait-free coordination for Internet-scale systems https://www.usenix.org/legacy/event/usenix10/tech/full_papers/Hunt.pdf
  2. Zab: High-performance broadcast for primary-backup systems http://www.stanford.edu/class/cs347/reading/zab.pdf 
  3. 自己动手实现zookeeper的FastLeaderELection选举算法和心跳同步 http://blog.csdn.net/techq/article/details/7233870
  4. Paxos http://en.wikipedia.org/wiki/Paxos_algorithm
  5. http://www.benhallbenhall.com/2011/01/what-is-the-znode-data-limit-size-for-apache-zookeeper/



----------------------------------------------------草稿----------------------------------------------------------

ZooKeeper also has the following two liveness and
durability guarantees: if a majority of ZooKeeper servers
are active and communicating the service will be avail-
able; and if the ZooKeeper service responds successfully
to a change request, that change persists across any num-
ber of failures as long as a quorum of servers is eventu-
ally able to recover.


the client will see
the notification event before it sees the new state of the
system after the change is made.


即使全异步发起模式下也可以实现顺序写


 We have also to provide order guarantees for
operations.


ZooKeeper has two basic ordering guarantees:
Linearizable writes: all requests that update the state
of ZooKeeper are serializable and respect prece-
dence;
FIFO client order: all requests from a given client are
executed in the order that they were sent by the
client.

上一篇:Paper Rush-3:Apache Kafka 下一篇:收获

评论列表:

发表评论: