【ZooKeeper】一文简单了解 ZAB 协议

本文将会围绕《ZooKeeper’s atomic broadcast protocol: Theory and practice》这篇论文讲解 ZooKeeper 和 ZAB 的精髓之处。

📢📢📢大家好，我是周周，前几周开组会时被点名回答一些 ZooKeeper 相关问题，竟然一问三不知，组长直呼当初被我帅气外表所骗，稀里糊涂的招了进来。

于是下来后对这个在我手发挥极其重要作用的这项基建产生了浓厚兴趣，所以决定痛改前非，先从 ZAB 出发，开启一系列的 ZooKeeper 进阶之旅。

tips：

本文主要是对 Paper 的消化和理解，稍显枯燥，建议工作累了划水时对着 Paper 慢慢看。

文章目录

1 概述

ZooKeeper 作为一项重要的基础设施应用于各大厂商中，其可用性和可靠性不言而喻，而 ZAB（ZooKpeeper 原子广播协议）更是保证 ZK 可用性和可靠性的基础，也是本文主要的分享点。

1.1 什么是 ZooKeeper

在了解 ZAB 之前，我们要先了解 ZooKeeper 是究竟什么？

关于这个问题，ZK 官方给出了自己的定义：A Distributed Coordination Service for Distributed Applications。即 ZK 是一个为分布式系统提供协调能力的系统。

ZK 作用

• 配置服务
• 分布式锁
• 服务管理
• 服务注册与发现

数据模型

ZK 本质还是一个基于内存的 KV 系统，但与一般 KV 系统不同的是 ZK 以 Path 来作为 Key，以 DataTree 树视图来组织这些 Path。

如上图所示，数据信息被保存在⼀个个的数据节点上，这些节点被称为 ZNode，ZNode 是 ZooKeeper 中最⼩数据单位，在 ZNode 下⾯⼜可以再挂 ZNode，这样⼀层层下去就形成了⼀个层次化命名空间 ZNode 树。

ZK 内部用

ConcurrentHashMap<String /*Path*/, DataNode>

来维持所有的 Path，每个 ZNode 会挂一个子节点的 Path 列表。

所以 ZK 对某个 Path 的插入和查询性能很高，并不需要遍历什么树，是直接对 HashMap 的操作。

节点角色

• Leader 所有的写操作均需要通过该节点完成
• Follower 处理读请求和转发写请求给 Leader，并对 Leader 广播的写请求投票
• Observer 类似 Follower，但无投票权

1.2 什么是 ZAB

ZAB 协议是为 Zookeeper 专门设计的一种支持崩溃恢复的原子广播协议。而 Paxos 是一种通用的分布式一致性算法，故不能把 ZAB 和 Paxos 进行等同。

在 ZK 中主要依赖 ZAB 来实现分布式数据的一致性。从本质上讲，ZK 也是一种主备模式（Leader-Follower-Observer）的系统架构，用来保持集群中各副本之间的一致性，即在 Leader 进行单点写，同时也能在 Leader crash 后进行恢复重新选主。

ZAB 协议的核心是定义了那些会改变 ZooKeeper 服务器数据状态的事务请求（Transaction）的处理方式。即：

1）所有事务请求必须由一个全局唯一的服务器（Leader）来协调处理，剩余的服务器称为 Follower（有权利参与选主）或者 Observer（只负责从 Leader 同步数据，用于读扩展和分担集群整体连接数）。

2）Leader 负责将一个客户端事务请求转换成一个事务 Proposal（提议），并将该 Proposal 分发给集群中所有的 Follower 节点（Leader 会维持一个 Follower 列表）。

3）之后 Leader 需要等待 Follower 的反馈，一旦超过半数的 Follower 进行了正确的反馈，Leader 则会对所有 Follower 发起 Commit 消息，要求所有 Follower 将该 Proposal 进行提交（即写入 Transaction Log）。

• Refer 实例详解ZooKeeper ZAB协议、分布式锁与领导选举

1.3 奔溃恢复模型

Crash-recovery system model

ZooKeeper 是一个奔溃恢复系统模型，即有能力从崩溃状态中自我恢复。如某个节点挂掉或者 Leader 挂掉，只要过半的节点存活并且能通信就能保证 ZooKeeper 的高可用和高可靠能力。

假设系统是由 N 个进程组成

Π = {p1, p2, . . . , pN }

，每个进程称为 Peer（节点），且节点之间能够相互通信，并有各自的存储来记录事务日志和 DataTree 的快照。

Q (quorum of Π)

表示进程集合中的过半节点集合，满足

Q ⊆ Π

和

|Q| > N/2

。任何的两个 Q 必然会有 Peer 之间的交集。

进程有两种状态：up 和 down。ZK 节点什么时候提供写能力呢？

一个 Follower 节点挂了重启后不是立马就能对外响应请求的，因为 Follower 落后 Leader 的 Proposal，只有待数据同步后才能对外提供服务。

所以 Peer 奔溃后到开始恢复前阶段称为 down 状态，从开始恢复阶段到下次奔溃称为 up 状态。

1.4 ZAB 的基本属性

在崩溃恢复模型中，需要保证同一时刻只有一个 Leader 存在，每个时期（epoch）的 Leader 可以不同，如

p1.p2.p3....pe..., ρe ∈ Π

。

每个 Proposal 用

<v, z>

表示，其中

v

是提交的新状态值，

z

则是 zxid。

zxid 用于唯一标示一个事务请求（Transaction），一个事务请求有两种状态：

• proposed 表示一个事务已经被 Leader 提出，但尚未被 Quorum 进行 ACK，
• commited 表示这个 Transaction 已经被 Quorum 进行 ACK，后续 Leader 对所有的 Follower 发出 commit 的请求，所有节点进行了本地 commit 操作。

因为，为了实现 ZooKeeper 副本的一致性，ZAB 需要满足一下基本条件：

• Integrity（正确性）：如果有节点收到 commit Proposal（提交议案） 的请求，那么肯定是有节点对该 Proposal 进行了广播。即 Proposal 不能是拜占庭问题。
• Total order（全局顺序性）：，即某个 Peer 按序提交了 <v, z>和 <v', z'> 两个 Proposal， 那么任意其它 Peer 上也必然是 <v, z> 比 <v', z'> 先被提交。
• Agreement（契约性）：如果 Pi 提交了 <v, z>， Pj 提交了 <v', z'>，那么要不 Pi 已经提交了了 <v', z'> , 要不 Pj 已经提交了 <v, z>。

此外，对于 Leader 节点而言，还需满足其顺序属性：

• Local primary order（本地顺序性）：如果 Leader 在原子广播阶段先后 commit了 <v, z> 和 <v', z'>， 一个 Follower 提交了 <v', z'>， 那么 Follower 肯定先提交了 <v, z>。
• Global primary order（全局一致性）：如果 ρi 是 epoch 为 i 的 Leader，ρj 是 epoch 为 j 的 Leader，且 i < j, 表示 ρi 是之前的 Leader， ρj 是之后的 Leader。ρi 提交了 <v, z>， pj 提交了 <v', z'>, 如果 Leader 提交了 <v, z> 和 <v', z'>， 那么肯定是 <v, z> 先于 <v', z'> 被提交.
• Primary integrity (正确性）：ρi 如果广播了<v, z> ，并且其他Follower commit了<v’, z’>，而<v’, z’> 是pj先于pi提交的，即pj的epoch比pi的epoch小，那么pi肯定也commit了<v, z>。

2 原子广播协议

Atomic broadcast protocol

在了解原子广播协议前，先来了解一些概念：

三种状态
在 ZAB 协议中，每个服务器节点 Peer 有三种可能状态：following、leading 以及 election。（其中处于 following 的节点称为 Follower，处于 leading 的节点称为 Leader）

四个阶段
同时 ZAB 协议整体分为四个阶段：0）Leader election、 1）discovery、 2）synchronization、 3）broadcast。

处于阶段 0）到阶段 2）的 ZK 集群还处于不可用的状态，即不能响应客户端的读写请求操作。只有选出主并完成上一个 epoch 期间的 Proposal 的广播后，整个集群才会对外服务。也就是说只有处于阶段3即原子广播阶段才能对外服务。

ZAB 的每个阶段是顺序推进的，如果在阶段 1）-3） 任何一个阶段出现故障，比如失败或者超时，则会重新进入阶段 0）再来一轮。

zxid
zxid 作为 ZooKeeper 最核心的一个概念，唯一标识一个 Transaction，即 Proposal 表示为

<value, zxid>

。为了保证顺序性，zkid 必须单调递增，因此全局唯一递增的 64 位正整数，所以 zxid 又由

<epoch, count>

构造。

epoch 是 zxid 的高 32 位，指的是每个 Leader 生命周期的一个标识，简单来说就是年号。每次选出新的 Leader，epoch 就加一。

count 是低 32 位，标识一个 epoch 期间每个 Transaction ID，每个 epoch 的 count 都会从 0 开始递增。

核心变量
1）history：被 Peer 提交的历史 Proposal
2）acceptedEpoch：接收最新 NEWEPOCH 的 epoch
3）currentEpoch：接收最新 NEWLEADER 的 epoch
4）lastZxid：history 中最近一个提交的 Proposal 的 zxid

简单的来说，acceptedEpoch 用于 Discovery 阶段来判断要不要接收新的 NEWEPOCH。currentEpoch 用于存放上个 epoch 的值。

这几个值都会进行存储，其中 acceptedEpoch 和 currentEpoch 会存储在磁盘上，history 和 lastZxid 可以从 DataTree 的 snapshot 中恢复。

2.1 选举阶段

Leader Election

这个阶段的目的是选出一个 Leader，然后进入后续阶段。具体的算法将会在后续 ZK 的实现小节中阐述，也就是 FLE（Fast Leader Election）算法。

2.2 发现阶段

Discovery

该阶段的目的就是确定一个新 Leader 的 epoch 值，然后找到上个 epoch 周期内拥有最大 zxid 的 Follower 节点。之所以可以取最大 zxid 作为新的 Leader 的 history，是基于一个假设，因为 zxid 是全局递增的，也就是拥有最大 zxid 的节点也拥有了最新的 Proposal 提交记录。

具体流程如下：

1）Follower 向准 Leader 发送一个 FOLLOWERINFO 类型消息，将自己的信息上报给准 Leader，该信息包括自己的 epoch 内容 F.acceptedEpoch。

2）Leader 等待收到过半的 FOLLOWERINFO 消息后，从这些 Follower 节点的 acceptedEpoch 中取出最大的 epoch，并且加1，即

newEpoch = max {F.acceptedEpoch} + 1

，再将新的 epoch 信息 NEWEPOCH 发给集群中的节点。

3）Follower 收到 NEWEPOCH 后，将新的 epoch 与自己的 epoch 比较：

• 新 epoch > acceptedEpoch, 即更新自己的 acceptedEpoch为 为新 epoch，然后给 Leader 发送一个 ACKEPOCH 信息，该信息包括上个 epoch、history 和 lastZxid。
• 新 epoch < acceptedEpoch，则回退到阶段0

4）Leader 收到所有 Follower 的 ACKEPOCH 后，从中找出 currentEpoch 最大的或者 lastZxid 最大的 Follower，把该 Follower 的 history 作为自己的 history。

值得注意的是，Quorum 是包括 Leader 自身的。这里的 Leader 还只是准 Leader。

2.3 同步阶段

Synchronization

同步阶段的目的就是准 Leader 需要将最新的 history 同步给集群内所有的 Follower。

1）在上阶段准 Leader 拿到过半的 ACKEPOCH 后，也就是有了最新的 Proprosal history。

2）Leader 给所有 Follower 发一个 NEWLEADER 类型消息，把最新的 epoch 和 histroy 带过去。

3）Follower 收到 NEWLEADER 消息后，判断自己的 acceptedEpoch 和新 epoch 是否相等。

• 如果相等则表示自己已经跟上了新 epoch，那么更新自己的 currentEpoch 为新 epoch，表示进入新的朝代。同时按照 zxid 的大小逐一进行本地 proposed（此时这些 Transaction 还未 commit），然后更新history，返回一个 ACKNEWLEADER 消息表示已经同步完数据。
• 如果不相等，那么退回到选举阶段，重新进行选主。

3）Leader 收到集群中节点的 ACKNEWLEADER 后，对 history 中的这些 Proposal 进行 commit，即向所有 Follower 发送 commit 请求。

4）Follower 收到 Leader 对 history 的 COMMIT 消息后，对于 outstanding（即已经 proposed，但还未 commit）的事务按 zxid 顺序进行 commit。

5）Leader 和 Follower 都完成数据同步后进入广播阶段.

2.4 广播阶段

如果所有节点都安然无恙，那么集群就会永远停留在这个阶段，也就是原子广播阶段。该阶段才真正对外通过服务，也就是开始接收外界写请求（Transaction）。

这个阶段不可能会存在双主，但可以加入新的 Follower 或 Observer 节点。

发起 Proposal 流程
1）Leader 在接收到 write 请求后，生成一个

Proposal <value, zxid>, zxid = lastzxid + 1

，然后对集群 Quorum 中的 Follower 节点发起 propose 请求

2）Follower 接收到 propose 请求后，将 Proposal 放入自己 history 队列中，并返回 ACK

3）Leader 收到过半的针对 Proposal 的 ACK 后，认为获得了大部分的同意，则对 Proposal 进行提交，向所有 Follower 发起 COMMIT 请求

4）Follower 收到

Propose <value, zxid>

的 COMMIT 请求后开始提交，但是为了满足 zxid 的全局一致性，如果存在比该 zxid 更小的

zxid‘

还未提交，那么需要等待

zxid’

的

Propose <value', zxid'>

被提交

新增 Follower 流程

1）新加入的节点会给 Leader 发一个 FOLLOWERINFO 请求
2）Leader 收到 FOLLOWERINFO 请求后会回复 NEWEPOCH 和 NEWLEADER，即告诉 Follower 当前的 epoch 和 history
3）新节点收到 NEWLEADER 后，如果正常逻辑处理后，回一个 ACKNEWLEADER 给 Leader
4）Leader 收到 ACKNEWLEADER 后给该新节点一个 COMMIT 请求，让新节点提交 history
5）Leader 最后把新加入的 Follower 节点放入自己的 Quorum 列表中。

值得注意的是：

• 整个 propose 过程是并行的，对于 Leader 来说，一个 Proposal 不会等上一个 commit 才会发起新 Proposal 的 propose 请求
• 每个 Peer 进行本地 commit Proposal 的时候是有序的，即 zxid 小的需要先 commit。这也是为了保障全局顺序性

3 ZAB 协议实现

在 ZooKeeper 实现原子广播协议中，对上面描述的几个阶段进行了优化，如图所示：

ZK 将阶段 0）选主和阶段 1）发现合二为一，实现为 Fast Leader Election 阶段，其算法核心内容是尝试选出一个拥有最新 history 数据（即最大 lastZxid）的节点作为 Leader。这样就可以把 Discovery 阶段省掉。

同时 ZK 还针对阶段 2）同步进行了一些调整，实现为发现阶段，接下来我们将详细描述这两个阶段的具体实现。

3.1 Discover

当 ZK 集群进入到恢复阶段，Leader 节点已由 FLE 阶段选举出来，并且拥有最大的 zxid。

为了将集群中节点数据恢复到一致，Follower 将处理来自准 Leader 的三种请求：

• SNAP：从 Leader 拉一份 snapshot（快照），再进行本地提交
• DIFF：提交请求体中的 Proposal
• TRUNC：Follower 节点丢弃 Leader.lastCommitedZxid～lastZxid 之间所有的 Proposal

接下来的主要流程：

1）Leader 从 lastZxid 中拿出 epoch 进行加 1 作为新的 epoch，并且低 32 位重置为 0，即

LastZxid ← {lastZxid.epoch + 1, 0}

。

2）Follower 连接上准 Leader 节点后，向其发送携带自己 lastZxid 的 FOLLOWERINFO 信息。如果 Leader 拒绝了连接，可能是因为 Leader 的 epoch 比自己小等原因，那么 Follower 重新将状态设置回 election，回退到FLE阶段。

3）Leader 接收到 Follower 请求后，发送 NEWLEADER 信息给 Follower。

4）如果 Follower 的 lastZxid 小于 Leader 中的 lastCommittedZxid，证明 Follower 的提交落后于 Leader，需要同步：

• 如果 Follower 的 lastZxid 比 Leader 设置的同步 DIFF 阈值还小，需要同步整个 snapshot，即向 Follower 发一个 SNAP 类型消息
• 否则 发送一个 DIFF 类型消息，消息内容是 Leader 已经提交的 history 中的那些 diff 的议案

5）Follower 收到准 Leader 的 NEWLEADER 请求后，需要对比 epoch：

• 如果 NEWLEADER.newLeaderZxid.epoch 比当前小，那么不能认可该 Leader，自己更新为选主状态，重新选主
• 如果 epoch 是同一个轮次中，那么则需要处理 SNAP、DIFF 和 TRUNC 请求
• 完成同步后，返回一个 ACKNEWLEADER 消息，进入广播阶段

6）Leader 收到集群大部分 Follower 节点的 ACKNEWLEADER 后，表示过半节点完成了同步，也进入阶段3——广播阶段。

至于为什么出现 TRUNC 请求，原因很简单，因为出现了一个有意思的例子：https://issues.apache.org/jira/browse/ZOOKEEPER-1154

3.2 Fast Leader Election

FLE 算法的核心是在集群 Quorum 中找出 lastZxid 最大的那个节点。那么每个节点之间需要同步选票，就需要几个核心信息：

• id：投票节点的 myid（在配置文件中配置）
• vote：被投票节点的 myid
• state：投票节点的状态，可以是 leading、following 或 election（只有重新发起新一轮 FLE 后才会变更为 election）
• round：投票轮次，每一轮 FLE 都会有一个 round，并在之前基础上加 1

选票 PK

我们将定义

Vote(zi , i)

表示一次投票，即 myid 为 i 的节点当前 zxid 是 zi。同时定义 Vote 间的优劣：

(zi, i) > (zj, j), 满足zi > zj || (zi = zj && i > j)

，通俗来说，zxid 大的优先，谁大选谁，zxid 相同时再比较 myid，大的优先。

所以我们在配置 ZK 集群时，需要给每个节点配置一个全局唯一的 myid。

接收选票

在 FLE 阶段，集群中每个节点都会维护一个列表当做 “投票箱” 以存放其他节点的选票信息，当然，也包括节点自身的选票。ZK 还会启动一个线程以便发送自身选票和接收其他节点的选票，同时还会根据对方选票记录和变更自己的状态和选择。

1）如果当前节点是选主（election）状态，则先将对方投票信息放入列表中
2）如果对方节点状态也是选主，那么将先比较一下选举轮次（round），如果当前节点轮次小于对方节点，则通知对方自己的投票信息
3）如果当前节点非选主状态，说明当前节点已经是 Leader 或 Follower，且对方节点还是选主状态的话，则需要告知对方当前节点的状态
4）如果双方都非选主状态，则代表这一轮选举结束

整个流程的精髓在于：记录对方的选票，然后互通有无。

FLE 算法

先看主流程：

1）节点 P 在启动初始化后，会投票给自己，即投票是

vote <P.zxid, P.myid>

，此时

round = round + 1

，就是 1。

2）然后开始给所有节点发送自己的投票

（<P.zxid, P.myid>, P.myid, election, 1）

。

3）完成对自己的投票后，开始等待接收其它节点的投票信息。（这里需要注意一下，收到的投票不是投给 P 的，是由其它节点广播给所有集群内的节点自己的选择）

4）当节点收到了对法节点状态是 Leading 的通知或者在循环内达成了投票共识（即决策了Leader）后，退出循环，结束选主状态。

决策流程

首先从当前节点的选票队列中弹出收到的选票 n，如果当前没有收到的投票，那么发出自己的投票信息，等待 2 倍的 timeout 时间。

当拿到选票后，对选票处理也很简单，根据选票中投票节点的状态可以做出两种行为：
1 如果选票 n 是选主状态，即

P.state = election

：

1）比较选票的投票轮次

• 如果选票中的轮次大于当前节点，代表自身轮次落后，需要更新当前节点的轮次和选票队列 （i）更新节点自身的 round 为选票 n 的 round，同时清空选票队列 ReceivedVotes （ii）PK 选票 v = Vote(zxid , myid) ，如果对方节点的选票较新，则修改自身选票为 v （iii）向集群广播自己新一轮选票
• 如果选票轮次与当前节点相同，表示在同一个选票轮次中，那么更新自身的 vote 为选票 n 中的 vote，然后再次进行广播
• 如果选票轮次比当前节点小，则忽略改选票，继续处理下一条新

2）如果投票 n 是有效的，那么就放入到队列 ReceivedVotes 中

3）如果当前 ReceivedVotes 等于 SizeEnsemble，也就是所有节点都进行了投票，则进行开票流程

4）如果当前节点获得的投票已经占了过半数，则等一个选举时间（tickTime）后进行开票

2 如果选票 n 已经是 leading 或 following 状态，那么说明某个节点已经进行开票并决策出结果，当前的节点进行更新状态即可：

1）如果选票 n 和当前节点处于同一个投票轮次，则选票有效，放入队列中：

• 如果 n 的状态是 leading，表示对方节点已经是 leading 状态，那么直接开票，不用继续看其余选票。
• 如果 n 是 following，那么对比下选票看看是不是自己中选（超过过半节点）了，如果是则开票更新，否则看下票的 id 是不是处于 leading 状态，是则开票

2）OutOfElection 是已经出结果的集合，因为这个选票 n 不是 following 就是 leading，所以放入 OutOfElection，然后根据 OutOfElection 进行判断自己结果

• 当前选票 n 投票的是自己，并且自己获取了 OutOfElection 中的过半，那么开票，变更状态
• 如果 OutOfElection 中有过半的投票投给了 n, 并且被投票的节点处于 leading 状态，也属于 OutOfElection，进行开票

3 如果以上逻辑均未命中，拿出下个选票，继续循环。

算法精髓

1）节点会随着收到投票的状态而变更自己的投票结果，即如果有人投票比自身新，那就变票然后再次发声。

2）在裁定状态及退出循环的判断中，只接收轮次不比自身小的。不仅会判断

(vote, id, state, round)

中投票者的状态，也会判断这个被投票节点的状态，另外还要满足过半节点的策略。

3）每个节点会维持俩个状态集合 ReceivedVotes 和 OutOfElection， ReceivedVotes存放接收到的合法选票，OutOfElection 存放节点已经是 leading 或 following 状态的选票。这也不难理解，ReceivedVotes 是还没开票，需要判断，OutOfElection 则是已经大选已经接收了，明确的状态了。

4）总有一个节点会在 election 选主状态先拿到过半节点，判定自己就是 leading 状态，然后广播给其其它节点，其它节点收到广播后进行自身状态修改。

4 总结

其实 ZAB 的哲学和 Paxos 一致，即限制未来就是更好的选择。

就如德州扑克一样，随着不断开牌，胜算小的选手就会不断放弃自己的 call，最终只剩一个赢家拿走所有筹码。

🌲🌲🌲 最后，如果大家觉得对你有帮助的话还希望大家动动手指给个免费的一键三连~，你的支持是我前进最大的动力。