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

• ：判断符号右边的数据比左边的数据更新。如果是zxid，z1z2代表z1.e < z2.e或者z1.e = z2.e,z1.c < z2.c，如果是vote，v1v2代表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合并，减少网络上的开销和多流程的复杂性

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

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

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

• 广播阶段：Leader接受写请求，并广播给Quorum Follower

Talk is cheap.Show me the Code

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

快速选举Leader阶段（FLE)

首先初始化一些数据

• ReceivedVotes：投票箱，存储投票节点以及当前投票信息

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

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

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

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

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

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

恢复阶段

经过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，并进入广播阶段。

广播阶段

进入到这个阶段，说明所有数据完成同步，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