Zookeeper一致性协议Zab详解

原作者中国开源网【loda0128】

zookeeper是分布式协调系统,用来协调、同步多服务器之间的状态,容错能力强

一个应用要保证HA,往往需要N个服务器(N>1)提供服务,其中有M台master,N-M台slave。这样一台挂了,另外N-1台也能提供服务。所以,数据也会备份成N份散布在这些服务器上。现在的问题变成了,如何管理这N台服务器?如何在master节点失败的时候重新选择master?如何保证所有服务器存储的备份数据一致?

如果你碰到上面那些棘手的问题,zookeeper刚好可以帮到你:

  • 存储公共配置信息

  • 跟踪所有进程运行状态

  • 集群中各节点的管理

  • master选主

  • 提供分布式同步支持(分布式锁等功能)

上面列出的是官方提供的功能支持,还有很多其他功能等待挖掘。

当你的系统依赖zookeeper保证HA和一致性的时候,你肯定也好奇,zookeeper本身是如何保证这两个特性的。幕后功臣往往容易被忽视,其实它就是Zookeeper原子广播协议(Zab协议)。如果你了解过二阶段提交、paxos算法、raft算法等大名鼎鼎的分布式一致性算法,Zab肯定也不会陌生,因为他们要达到的目的相同,就是保证应用程序的HA和一致性。

背景

为了读懂后面的内容,有些术语需要了解:

  • Peer:节点。代表了系统中的进程,往往系统有多个进程,也就有多个节点提供服务

  • Quorum:多数。当有N个Peer,多数就代表Q(Q>N/2)个Peer

  • Leader:主节点,最多存在一个。代表zookeeper系统中主要的工作进程,Leader才是真正处理所有zookeeper写请求的节点,写请求会从Leader广播到Quorum Follower

  • Follower:从节点,可以有多个。如果client对zookeeper发起一个读请求,Follower可以直接处理。如果client对zookeeper发起一个写请求,Follower需要转发到唯一的Leader,再有Leader处理并发起广播

  • transaction:事务,一次写请求就代表一次事务

  • zxid:事务id。zk为了保证消息有序性,提出了事务编号这个概念。zxid是一个二元组<e,c>,e代表选举纪元(如果将选举理解更皇帝的选举,这纪元代表年号),c代表事务的计数,同一纪元内每次出现写请求,c自增(代表某个年号内经过了多少年)。容易理解,纪元不变时,计数不断增加,纪元变化时,计数清零

  • lastZxid:peer中存储的最新的zxid

  • vote:选票,代表二元组<zi,i>。zk会给每个peer打上唯一标识,即i,二元组的i就代表了选举的peer,而zi代表了这个peer上最新的zxid

  • ![](http://7xvaaj.com1.z0.glb.clouddn.com/later.png):判断符号右边的数据比左边的数据更新。如果是zxid,z1![](http://7xvaaj.com1.z0.glb.clouddn.com/later.png)z2代表z1.e < z2.e或者z1.e = z2.e,z1.c < z2.c,如果是vote,v1![](http://7xvaaj.com1.z0.glb.clouddn.com/later.png)v2代表v1.zi < v2.zi或者v1.zi = v2.zi,v1.i < v2.i

  • state:节点状态,目前只有这三种election、leading、following

  • history:记录所有事务的日志

  • lastCommittedZxid:最近提交成功的事务

  • oldThreshold:日志中记录最早提交成功的事务。之所以设置一个最早的门槛,就是觉得没有必要保留非常久远以前的事务,以便减少对内存的占用以及数据同步带来的网络开销

详解

Zab Theory and practice这篇论文中解释说,Zab的理论和实现并不完全一致。理论就是yahoo发布的关于zab的论文,实现也就是Zookeeper开源代码。

实现是在理论的基础之上做了一些优化手段,这些优化是在zookeeper不断发展的过程中给加上的。我接下来的讲解,也是参照这篇论文,以zookeeper 3.3.3的版本的实现为准,并用自己的语言总结。

理论中的协议

随着系统启动或者恢复,会经历Zab协议中描述的如下四个阶段

  • 阶段0:Leader选举。每个peer从Quorum peer中选出自己心中的预备leader

  • 阶段1:发现。预备leader从Quorum Follower中发现最新的数据,并覆盖自己的过期数据

  • 阶段2:同步。预备leader采用二阶段提交的方式将自己的最新数据同步给Quorum Follower。完成这个步骤,预备leader就转为正式leader

  • 阶段3:广播。Leader接受写请求,并通过二阶段提交的方式广播给Quorum Follower

之前我只是简述了一下理论中的协议,然而理想很骨感,有很多需要改进或者妥协的地方。下面我会一一阐明:

  • 阶段0的选举leader实际上很简陋,只是“看对眼”了就选为预备leader,所以预备leader的数据可能并非最新

  • 预备leader数据过期,就需要用阶段1来弥补,通过互相传输数据,来发现最新的数据,并完成预备leader的数据升级

  • 更多的网络间数据传输代表了更大的网络开销

协议实现

了解了理想的骨感之后,我们回归现实。

真正apache zookeeper在实现上提出设想:优化leader选举,直接选出最新的Peer作为预备Leader,这样就能将阶段0和阶段1合并,减少网络上的开销和多流程的复杂性

Zookeeper一致性协议Zab详解

由图可知,代码实现上,协议被简化为三个阶段

  • 快速选举Leader阶段:从Quorum Peer中选出数据最新的peer作为leader

  • 恢复阶段:Leader将数据同步给Quorum Follower

  • 广播阶段:Leader接受写请求,并广播给Quorum Follower

Talk is cheap.Show me the Code

这时Linus说过的一句话,无论语言多么有力,只有代码才能真正展现作者的思想。之前我只是对是协议实现的三个阶段做了一番简述,只有代码才能真正拨开Zab协议外面那层迷雾。(为了不浪费篇幅,这里采用伪代码)

快速选举Leader阶段(FLE)

Zookeeper一致性协议Zab详解

首先初始化一些数据

  • ReceivedVotes:投票箱,存储投票节点以及当前投票信息

  • OutOfElection:存储已经成为Leader、Follower,不参与投票的节点信息,以及它的历史投票信息

  • 在选票中写上自己的大名

  • send notification:发起选票通知,该节点会携带选票,进入目标节点的队列中,相当于给自己投了一票,并毛遂自荐给其他人

如果当前节点处于选举状态,则它也会接到选票通知。它会从队列中不断轮询节点,以便获取选票信息(如果超时,则不断放松超时时间,直至上限)。根据轮询出来的发送节点的状态,来做相应的处理。

  • election:如果发送节点的轮次(round)大于自己,说明自己的选举信息过时,则更新自己的选举轮次,清空投票箱,更新自己的选票内容,并将新的选票通知给其他节点;如果发送节点的轮次等于自己,并且投票内容比自己的更新,则只需要更新自己的选票,并通知给其他节点就行;如果发送节点的轮次小于自己,说明投票内容过期,没有参考意义,直接忽略。所有未被忽略的选票,都会进入投票箱。最终根据选票箱中的结果,判断当前节点的选票是不是占大多数,如果是就根据当前节点的选票选出Leader

  • leading或following:发送节点轮次等于自己,说明发送节点还参与投票,如果发送节点是Leading或者它的选票在选票箱中占大多数,则直接完成选举;如果发送节点已经完成选举(轮次不同)或者它收集的选票较少,那么它的信息都会存放在OutOfElection中。当节点不断完成选举,OutOfElection中数量逐渐变成Quorum时,就把OutOfElection当做投票箱,从中检查发送节点的选票是否占多数,如果是就直接选出Leader

恢复阶段

Zookeeper一致性协议Zab详解

经过FLE,已经选出了日志中具有最新已提交的事务的节点作为预备Leader。下面就分Leader和Follower两个视角来介绍具体实现。

Leader视角

首先,更新lastZxid,将纪元+1,计数清零,宣布改朝换代啦。然后在每次接收到Follower的数据同步请求时,都会将自己lastZxid反馈回去,表示所有Follower以自己的lastZxid为准。接下来,根据具体情况来判断该如何将数据同步给Follower

  • 如果Leader的历史提交事务比Follower的最新事务要新,说明Follower的数据有待更新。更新方式取决于,Leader最早事务有没有比Follower最新事务要新:如果前者更新,说明在Leader看来Follower所有记录的事务都太过陈旧,没有保留价值,这时只需要将Leader所有history发给Follower就行(响应SNAP);如果后者更新,说明在Leader看来,Follower从自己的lastZxid开始到Leader日志的最新事务,都需要同步,于是将这一部分截取并发送给Follower(响应DIFF)

  • 如果Leader的历史提交事务没有Follower的最新事务新,说明Follower存在没有提交的事务,这些事务都应该被丢弃(响应TRUNC)

当Follower完成同步时,会发送同步ack,当Leader收到Quorum ack时,表示数据同步阶段大功告成,进入最后的广播阶段。

Follower视角

通知Leader,表示自己希望能同步Leader中的数据。

  • 当收到Leader的拒绝响应时,说明Leader不承认自己作为Follower,有可能该Leader并不可靠,于是开始重新开始FLE

  • 当收到SNAP或DIFF响应时,Follower会同步Leader发送过来的事务

  • 当收到TRUNC响应,Follower会丢弃所有未完成的数据

当每个Follower完成上述的同步过程时,会发送ack给Leader,并进入广播阶段。

广播阶段

Zookeeper一致性协议Zab详解

进入到这个阶段,说明所有数据完成同步,Leader已经转正。开始zookeper最常见的工作流程:广播。

广播阶段是真正接受事务请求(写请求)的阶段,也代表了zookeeper正常工作阶段。所有节点都能接受客户端的写请求,但是Follower会转发给Leader,只有Leader才能将这些请求转化成事务,广播出去。这个节点一样有两个角色,下面还是按照这两个角色来讲解。

Leader视角:

  • Leader必须经过ready,才能接受写请求。完成ready的Leader不断接受写请求,转化成事务请求,广播给Quorum Follower。

  • 当Leader接收到ack时,说明Follower完成相应处理,Leader广播提交请求,Follower完成提交。

  • 当发现新Peer请求作为Follower加入时,将自己的纪元、事务日志发送给该Peer,以便它完成上述恢复阶段的过程。收到该Peer的同步完成的ack时,Leader会发送提交请求,以便Peer提交所有同步完成的事务。这时,该Peer转正为Follower,被Leader纳入Quorum Follower中。

Follower视角:

  • Follower被发现是Leading状态,则执行ready过程,用来接受写请求。

  • 当接受到Leader广播过来的事务请求时,Follower会将事务记录在history,并响应ack。

  • 当接收到Leader广播过来的提交请求时,Follower会检查history中有没有尚未提交的事务,如果有,需要等待之前的事务按照FIFO顺序提交之后,才能提交本事务。

总结

这篇文章没有介绍Zookeeper的使用,而是着重讲解它的核心协议Zab的实现。正如文中提及,Zab最早的设想和现在的实现并不相同,今日的实现是在Zookeeper不断发展壮大的过程中不断优化、改进而来的,也许早期的实现就是yahoo论文中构想的那样。罗马不是一日建成,任何人都不能指望一口吃个大胖子。如果Zookeeper刚开始就想着如何优化到极致,那反而会严重影响到这个项目本身的价值,因为它很可能还没面试就被淘汰。

We should forget about small e ciencies, say about 97% of the time: premature optimization is the root of all evil.

Knuth提醒我们,过早优化是万恶之源。但是同时,一个好的程序员也不会忘记需要优化的那部分,他会定位相应的代码,然后针对性的修改。这也是zookeeper的开发者所做的。

问题汇总

  • 一般Leader election算法都收到Quorum节点的选票,为什么?

    基于以下两点:

  • 防止选出多个Leader,每人一票,同一纪元最多选出一个Leader

  • 当log被提交时,说明Quorum节点存储了这个log。当进行Leader election的时候,当收到Quorum选票称为Leader时,必定存储了最新被提交的log

相关推荐