Zookeeper一致性协议Zab详解

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和一致性。

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

Zab的理论和实现并不完全一致。

实现是在理论的基础之上做了一些优化手段，这些优化是在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.

通过本文可以看出，过早优化是万恶之源。但是同时，一个好的程序员也不会忘记需要优化的那部分，他会定位相应的代码，然后针对性的修改。这也是zookeeper的开发者所做的。

更多相关文章

随机推荐