Zookeeper ZAB协议原理浅析

前言

DTCC 要在下周一到周三要在北京举办，身边有不少人都去参加了，领略中国最为领先的一些公司的自研存储技术。
阿里自研polardb，polardb-x(x-engine)相关，华为自研Gaussdb，开源TiDB 等，从SQL，到NoSQL,到NewSQL 都会将一些核心技术设计在大会上分享讨论，而且今年也是中国数据存储技术进入时间领先领域的一年（之前都是google，微软等巨头），那这场大会将是深入了解近年来中国存储最为前沿的技术盛会。

然后周五的一场技术分享却发现自己知识体系的严重漏洞， 分布式领域从上到下（分布式协调系统，分布式数据库(kv,table,graph,document)，分布式存储(块，文件系统，对象)，单机存储），除了最底层的单机存储引擎（现在做的）之外没有一个能够深入理解掌握并灵活应用的。仅仅为了准备一个分布式协调系统的分享，就发现了无数的知识漏洞（从基础的编码到上层的系统认知），那这样的基础去参加更高层次的技术集会岂不是被吊打。就像平时听大佬们分享一样，总是在感叹自己的无知，没有足够的知识基础，没有办法在大脑中快速打造属于自己的知识架构，最后反而适得其反。

回到我们要讨论的ZAB协议上，这是周内分享的一部分，当然仅仅是一些原理上的描述，并没有涉及zookeeper内部的代码实现。分享过程中将ZAB协议的演进也做了一个整体的分享，从paxos,multi paxos, raft/zab 都做了整体的描述，本篇文章主要讨论zab的协议原理，毕竟zookeeper的实现核心，当然要上干货。
之前有两篇相关的zookeeper 基础入门和运维相关的文章，能够有效节省大家的入门时间，先对 zookeeper有一个整体的了解。

1. 一文入门zookeeper
2. 一文运维zookeeper

关于zab协议内容的介绍能够回答如下几个问题：

1. zookeeper 客户端接口为什么是wait-free的？即接口之间不会相互影响，所以不需要相互等待返回，可以并行调用接口。（并行更新数据）
2. zookeeper 如何保证不出现双主？
3. zookeeper如何保证请求顺序执行？

1. 基本角色和概念

ZAB 协议(zookeeper atomic broadcast) zookeeper原子广播协议，作为zookeeper实现分布式协调服务的核心，提供从leader 选举，到日志复制，到数据同步 以及 最后的数据广播 ，提供了一整套的实现算法。是一个值得学习研究的分布式系统，能够极大得帮助一些感兴趣的同学提升对分布式系统的理解和认知。

zookeeper 内部有三种角色，每一种角色可以用一个zookeeper server进程来表示：

• leader： 整个集群只能有一个，主要处理写请求，zookeeper中所有的写请求都需要由leader负责处理。当然也能提供读服务。
• follower: 整个集群可以有多个，只能提供读服务。在leader发生异常之后通过ZAB的leader election 以及后续的Discovery完成leader的重新选举，将一个follower 标记为leader，对外提供读写服务。
• observer: 不参与leader选举和投票，仅仅提供读服务和接受leader变更的通知。可以作为zookeeper同城双机房，中的从机房的角色。既能够提供读服务，又能够有效得减少两个机房之间的rpc通信，从而提升整体的集群性能（当然，存在的问题也很明显，主从机房发生网络分区，从机房就不可用了）。

ZAB协议的主要是四个阶段：

• Leader Election: 主要是节点之间进行信息同步，选择出一个leader
• Discovery: leader 获取最新的history信息。（这里的history信息是整个集群最新的<v,zxid> 事务版本zxid以及其对应的数据）
• Synchronization: leader将获取到的最新的数据同步到其他的从节点，并补全老数据，删除新数据
• BroadCast: 之前的三个阶段都是集群不可用的状态。到了这个阶段，整个集群就可以对外提供读写服务，且zookeeper集群正常状态下处于该阶段。

ZAB 协议中有一些基本概念需要提前同步一下，如果感觉理解的还不很深刻，建议先看看前言推荐的两篇文章。

• zxid: 唯一标识一个trasaction, 全局唯一递增的64位整数。zxid由 <epoch, count>
• Epoch: 每个leader生命周期的一个标识。newEpoch = lastEpoch + 1
• Count :表示每个Epoch期间发生的transaction id, 每个count 都是从0开始加一递增
• zxid的比较； 我们称zxid <e, c> 大于 zxid’<e’, c’>，当满足 (e > e’ ) || (e = e’ & c > c’).

同时在ZAB中，我们前面说到的zookeeper内部的角色都会统称为peer, 一个peer代表一个角色进程；peer中有如下几个核心变量：

• history: 被Peer提交的历史proposal<v,zxid>，也就是数据和事务id
• acceptedEpoch,接受最新的NEWEPOCH的Epoch，主要是用来leader选举过程中follower判断是否接受leader的NEWEPOCH信息。
• currentEpoch 接受最新的NEWLEADER的epoch， 当选举出来新的 leader之后，会将新leader的epoch更新到这个文件中。
• lastZxid: 表示history 最近提交的proposal的zxid.

这么多概念第一次看肯定记不下， 实际讲解的过程中如果忘记了可以返回来查看。

2. Leader Election

顾名思义，这个阶段就是选举leader的阶段，集群不可用。
核心目的：通过投票完成leader选举，且集群每一个成员都会知道leader的epoch和leader id(myid文件)

时序图如下：

投票的信息主要是类似vote (zxid,id)，当然实际更加详细（vote,id,state,round）;id表示 唯一标识一个peer的id,也就是myid文件中的编号；state表示peer的所处的状态（ leader,follower,election），round表示当前peer是第几轮投票。

上图中我们使用node(id,zxid)来简化选举过程，其中id就是myid, zxid就是当前peer最新的版本号。
图中有三条白色箭头，分别代表三个节点的时间，每一个节点在某一个时间会有三条线。
比如T1时刻的node1的三条黄色线，表示分别向自己投票，将自己的投票信息发送给其他两个节点，投票信息的大小比较如下规则：node1(id,zxid) > node2(id’ , zxid’) ，当满足 zxid > zxid’ || (zxid==zxid’ && id > id’)

T1 时刻 开始了leader选举，三个节点都将各自的node信息先发送给自己，再发送给其他两个节点。
T2 时刻， 其他两个节点都已经完成了投票信息的比较：

• 比如 node1 会收到其他两个节点的投票信息，依次和自己的zxid进行比较，版本号高的成为leader；node1最高，不需要再发送消息投票（它开始已经投自己一票了）。
• node2 会收到来自node3和node1的投票，进行投票信息的比较，发现node1 > node2，node1 > node3，投票给node1，并准备好 新的投票结果进行广播。
• node3 类似，投票给node1。

T3 时刻，整个集群其实已经完成了选举，node1成为新leader, 不过还是准leader，后续需要进行一些更进一步的版本数据同步。

这个过程存在一些问题，比如node1 T1时刻发送给 node2节点的投票信息出现rpc延迟，在node2完成投票决策之后才到达node2。

在T1 时候 , node2只收到了node2自己和node3的投票，进行投票信息的比对，虽然zxid 相等，但是node3 id更大，且也满足大多数，则node2 会选择node3作为leader，而node3会选择node1进行投票（node1发送到node3的投票信息并没有延迟）也就是到T3时刻，node2认为node3是leader ， 而node3和node1都认为自己是leader。当然实际情况node3并不会被标记为leader，因为node3只收到一个投票，不满足大多数，只是集群中会存在这样的冲突。

当然这种问题在后续的Dicovery阶段进行leader版本信息比较时就能够避免，发现leader的版本号比follower 版本号更低时会触发重新选举，这里说一下Leader Election这个阶段如何避免 某个peer出现 delay message的问题。

维护一个超时时间 Finalize Wait Time，当某一个peer收到投票信息后发送了一次投票结果，但是在这段时间内如果还收到其他的投票信息且需要变更投票结果，那么这个peer会重新发送一个新的决策结果给其他的peer。

也就是到这个Finalize Wait Time 结束后的集群leader才会是新的Leader。
T2时刻也处在FWT的时间段内，这个时候延迟的node1 的投票信息发送到了node2，发现之前的投票结果需要变更，则会重新发起一次投票，投票为node1作为leader。

当然这个 Finalize Wait Time 肯定也不能完全保证解决这个问题，它的数值设置多大也只是概率性的降低delay message 导致的投票信息延迟达到的问题。所以，还需要更加严谨的机制来保证不出现leader冲突的问题，我们继续来看后续阶段。

3. Discovery

Leader Election之后整个集群已经完成了选主，当然这个leader并不是真正的leader。之前它可能拥有最新的版本号，但现在已经改朝换代了，需要有自己的年号来向天下宣告自己的登基。所以它需要重新发布年号（版本号），同时需要掌控整个王朝最新的资源（最新的数据），只有完成这一些事情自己才能稳坐宝座，成为正王。

现在的集群拥有这个几个角色，其中有一个准leader(按照之前leader选举过程，也有可能出现双leader，然后进入这个阶段)

ZAB协议的角度先总体说一下这个阶段的核心目的：

1. 确认/生成 一个新leader的Epoch
2. 新的Epoch同步到所有的Follower
3. Leader获取最新的history, 准备进行后续的Synchronization 阶段。history: <value, zxid>

具体过程如下：

1. Follower节点知道准Leader节点之后，会发送一个FOLLOWERINFO的信息携带自己的f.acceptedEpoch内容

2. 准leader节点收到超过半数的FOLLOWERINFO之后，会从中选择一个最大的，并在最大的基础上+1，即max{f.acceptedEpoch} + 1

3. 准Leader将准备好的NEWEPOCH发送到follower, 表示自己的年号已经更新。等待quorum中的成员回复ACK

4. follower 收到NEWEPOCH之后和自己本地epoch进行比对：

   a. leader 发送过来的epoch > acceptedEpoch,更新自己的acceptedEpoch 为新的epoch,并回复一个ACKEPOCH消息，这个消息中携带上个currentEpoch, history 和 lastZxid(history 最近提交的proposal的zxid)

   b. leader发送过来的epoch < acceptedEpoch ，则 回退到阶段0，重新进行leader选举（集群中存在节点异常）。
   c. leader发送过来的epoch 和 本地acceptedEpoch相等的场景论文并没有提到，感觉应该会需要重新选举，毕竟leader已经在收到大多数的FOLLOWERINFO 中最大的+1了。

5. Leader收到所有quorum中follower的ACKEPOCH, 从所有的消息中找出currentEpoch最大的或者lastZxid最大的follower,然后把该follower的history 作为自己的history（pull history的过程）。当然，如果本地自己的currentEpoch 或者 lastZxid最大，那就用本地的history即可。

到现在，Leader 已经获取到最新的history, 并开始准备进行后续的Synchronization 阶段。

4. Synchronization

这个阶段的核心目的是：

1. 同步history proposal。即将Leader获取到的最新的history 数据同步到follower节点，让整个集群数据对齐。
2. 处理上个阶段遗留下来的proposal，follower节点中的数据 需要清理的可以清理，需要删除的可以删除。

大体过程如下：

Leader这个阶段刚开始的时候已经有了整个集群最新的history数据。

1. Leader 想所有的follower发送NEWLEADER信息，其中包括leader自己最新的epoch 和 最新的history数据。

2. follower 收到leader的消息之后判断当前轮次自己的acceptedEpoch和leader发送过来的epoch是否一样（discovery阶段已经对follower自己的acceptedEpoch进行了更新）

   1). follower的acceptedEpoch和新epoch相同，表示自己已经跟上了新的epoch, 那么做如下几个事情
   a. 更新自己的currentEpoch为新的epoch，表示进入新的朝代了
   b. 按照zxid的大小逐一进行本地proposed，此时这些transaction还未commit。
   c. 更新自己的history为最新的history
   d. 返回一个ACKNEWLEADER 给leader, 表示这个follower已经完成数据同步

   2). follower收到的epoch和本地的acceptedEpoch不同，那么回退到阶段0，重新选主（存在节点异常，当前主节点并不能包含所有的数据，不能随意更新，否则会丢数据）。

3. Leader 收到follower节点的ACKNEWLEADER消息之后，对proposal的数据进行提交commit，所有的follower节点也会收到commit请求（落盘）

4. follower节点收到leader的COMMIT请求，会对自己本地已经proposed但还未commit的事务，按照zxid进行从小到大的排序，优先commit zxid较小的节点。

5. Leader 和 Follower都完成同步之后进入第四阶段。

从朝代更替来看，前面的几个阶段整个国家处于乱世：无君，君臣各有所思，各有所谋，可能的多君。。。。
到这个阶段，历经千难万险完成了国家统一，君强臣明，整个国家开始一致对外，共向繁荣的场景。
正如我们的春秋战国到秦，五代十国到宋，南宋到元，每一个帝国的崛起都历经无数次的尝试和磨难，但大一统的目标从秦遍成了唯一，只有集群大一统，才能够更好得施展每一个角色的才华。

5. BroadCast

这是一个稳定的时代， 之前三个阶段，zookeeper无法对外提供服务。到了这个阶段，整个集群即能够对外提供读写服务。

这个阶段如果发生集群成员变更，即加入了follower和observer。
整体过程如下：

1. Leader收到一个写请求，会生成一个Proposal: <value, zxid>, zxid = lastZxid + 1，对quorum中的follower节点发起propose请求，并携带生成的Proposal。
2. follower节点收到propose的proposal，将其加入到history队列，并向leader回复ACK，表示已经收到propsal。
3. leader收到过半节点的ACK之后，认为可以进行commit，则向quorum发送COMMIT请求
4. follower收到propose的commit 之后开始进行提交
   1). 为了满足zxid的全局一致性，这里会检查follower本地是否有未提交的proposal<v,z>，保证比当前zxid小的propose先提交
   2). 当所有小于zxid的propose都完成commit之后再提交当前的zxid。
5. BroadCast阶段 也能够接受新的Follower或者Observer的加入，步骤如下:
   1). 新加入的节点会给Leader发送一个FOLLOWERINFO信息
   2). Leader收到后会回复给他一个NEWEPOCH 和 NEWLEADER, 告诉这个节点集群最新的epoch和history数据
   3). 新节点收到NEWLEADER后，如果正常逻辑处理完成后（将history中的数据并发propose），回一个ACKNEWLEADER给Leader
   4). Leader收到ACK回复之后告诉他可以进行本地proposal的提交了,会发送一个COMMIT 请求
   5). 新节点收到这个请求，对本地完成proposed的数据按照zxid从小到达进行commit（落盘）。
   6). 新节点完成commit之后，leader会将新的节点加入到自己的quorum列表中。

ps :
a. 以上过程不论是leader还是follower 节点在进行propose的过程都是可以并发进行的。对于leader来说，一个proposal的发起不会等待上一个commit完成之后才会发起，当前proposal和上一个proposal是可以并行处理，保证了zookeeper的更新接口可以提供wait-free 的能力。

b. commit 时需要保证本地比当前zxid更小的事务优先提交，从而保证zookeeper的Linearizable 特性。

以上基本就是ZAB协议的每个阶段的细节，在我们实际zookeeper的实现中，会对以上四个阶段做优化。

我们能够看到从开始选主到能够提供服务，这个过程还是会有大量的rpc 和数据交互，zookeeper实际将leader election和discovery变更为 FLE(Fast Leader Election)阶段，在完成Leader 选举之后 leader 就已经拥有了最新的history数据。

将Synchronization 阶段变更为了Recovery 过程，整体上就是让单次rpc携带的数据量更大，能够在完成相互的交流通信之后进行更多更快的本地计算，而不是将较多的时间消耗在rpc和等待rpc数据的过程中。

后记

这是一个乱世的结束，但从历史的角度看，也会是一个乱世的开始。

居安思危很难，领导层 只能够在大多数场景做出正确的决策，但p9999和max之间差异还是太大。我们的系统 同样是一个复杂体系，大量的静默错误（硬件损耗，磁盘的bit位反转，还有大量的底层系统软件到上层应用软件的bug）无法保证一个分布式集群 每时每刻都正常运行。只能在有限的人力，有限的资源下最大化我们系统的可用性，创造足够的价值。正如那一些历史上的伟大帝国 在他们所在的时代创造了让后人敬仰的文明。