用流程图来理解 - ZooKeeper 中的 ZAB 协议

2020-06-21 00:00:00 消息 事务 节点 请求 过半

想了解一些分布式一致性协议比较久了，之前一直写了些草稿，之后想慢慢更新更多的内容。非资料搬运，知识水平有限，如果有任何谬误，欢迎批评指正。

简介

ZAB 协议全称 ZooKeeper Atomic Broadcast，是 zookeeper 维持数据一致性的核心算法。基于该协议，zk 实现了主备模式的系统架构来保持集群中各副本的一致性。对于改变服务状态的写请求，通过一致性协议处理同步。对于读请求可以在本地副本上进行返回。

基础概念

在熟悉流程之前先了解一些概念是必要的。

概念与术语

  • Leader 主: 接收客户端请求，负责将一个客户端事务请求转换成一个 Proposal，并将该 Proposal 分发给集群中的所有 Follower。之后 Leader 等待所有 Follower 的反馈，当过半的 Follower 服务器正确反馈后，也称 Quorum，就会再次向所有 Follower 分发 Commit 消息，将 Proposal 提交。
  • Follower 从: 追随主，将写请求转发给主，可以负责读请求。所以，集群扩容的时候会增加读请求的性能，相反，写性能会有所下降，因为需要同步的机器更多了。
  • Proposal 提案：<v, z>，v 表示值，z 表示 zxid。
  • Commit 提交: 事务提交。
  • Quorum 仲裁: 一般是指过半机制。
  • Oberver 观察者: 从的一种形式，但是不参与选举。引入只是为了系统的可扩展性。
  • Epoch 纪元：即每一个 Leader 的任期。

ZXID

zxid（Zookeeper Transaction Id）是 ZAB 协议的事务编号，其是一个 64 位的整数，在整个过程中。

  • 低 32 位是一个单调递增的计数器，每当 Leader 服务器产生一个新的事务 Proposal 时，递增 1。
  • 高 32 位代表 Leader 的 epoch 编号，有点类似于 Raft 的任期，每当选举一个新 Leader 时，就会从新 Leader 取出本地日志中的大事务 Proposal 的 zxid，解析出 epoch 然后加 1，并将低 32 位置 0 来开始新的 zxid。

节点状态

在 ZAB 协议中，每一个进程都有可能处于以下三种状态之一。其实还有一种 Oberserving 状态，是观察者的状态，可以先忽略。

每个节点保存以下数据，

术语

  • CEpoch：Follower 发送自己处理过的后一个事务 Proposal 的 epoch 值。
  • NewEpoch：Leader 根据接收 Follower 的 epoch，来生成新一轮 epoch 值。
  • Ack-E：Follower 确认接收 Leader 的新 epoch。
  • NewLeader：确立领导地位，向其他 Follower 发送 NewLeader 消息。
  • Ack-LD：Follower 确认接收 Leader 的 NewLeader 消息。
  • Commit-LD：提交新 Leader 的 proposal。
  • Propose：Leader 开启一个新的事务。
  • Ack：Follower 确认接收 Leader 的 Proposal。
  • Commit：Leader 发送给 Follower，要求所有 Follower 提交事务 Proposal。

流程

ZAB 协议主要包括消息广播和崩溃恢复两个过程。具体又可以分为 Discovery 发现，Synchronization 同步，Broadcast 广播三个阶段。下图是 ZAB 协议的简介 ，我们将每个阶段又分为 3 小节，后续说明每个小节分别做了什么。颜色箭头表示节点间的通信方向，黑色箭头表示进入各阶段的过程。

崩溃恢复

当出现以下情况时，ZAB 协议会进入恢复模式并选举新的 Leader。

  • 服务框架重启
  • 网络中断
  • 崩溃退出

ZAB 协议会进入恢复模式并选举新的 Leader。当选举出新 Leader ，同时集群中已经有过半机器与新 Leader 完成了数据同步之后，ZAB 协议会退出恢复模式。

选举过程

示例图中有三台机器 server 1，server 2，server 3。括号中 (3, 6) 表示选票，其中包含 sid （即配置文件中的 myid）和 zxid。zooKeeper 默认使用快速选举算法，具体可以参考源码和上述流程图。

  1. 崩溃或重启后，各节点都变更为 Looking 状态，然后开始选举过程。
  2. 各个节点先投票给自己，然后广播投票结果给所有节点。也就是说 server 1 把自己的选票 (3, 6) 广播给所有节点。
  3. 如果得到大多数节点的同意，那么就认为自己是 Leader。图中所有节点都选出了 (3, 6) 然后向所有节点广播，确定了 Leader 是 server 1。

发现

  1. 阶段 CEpoch：Follower 将自己后处理的事务 Proposal 的 epoch 值发送给 Leader，消息 CEpoch(F.p)，F.p 可以提取出 zxid。
  2. 第二阶段 NewEpoch：当 Leader 接收到过半的 Follower 的 CEpoch 消息后，Leader 生成 NewEpoch(e') 发送给这些过半的 Follower，e' 是比任何从 CEpoch 消息中收到的 epoch 值都要大，毕竟要改朝换代嘛。
  3. 第三阶段 Ack-E：
    1. Follower 一旦从 Leader 处收到 NewEpoch(e') 消息，如果 F.p < e'，
    2. Leader 一旦收到了过半的 Follower 的确认消息。它会从这些过半的 Follower 中选取一个 F，并使用它作为初始化事务的集合 S'（用于同步集群数据），然后结束发现阶段。

如何选取这个 Follower 呢？因为既然要选择需要同步的事务集合，必然要选择事务全的吧。所以，须满足epoch 是大的且 zxid 也是大的。

同步

在完成发现流程之后（即确定了数据源 Follower F 的事务集合 S'），接下来就进入了同步阶段了。

  1. 阶段 NewLeader：Leader 将新 epoch 和 S' 以 NewLeader(e', S')的消息形式发送给所有过半 (Quorum) 的 Follower。在上一阶段 L.history = F.history，所以 S' 就是流程图中的 L.history。

  2. 第二阶段 Ack-LD：当 Follower 接收到 NewLeader(e', S') 消息后，

    1. 如果 Follower 的 epoch 等于 e'，也就是确认是不是该主的子民，因为前一阶段段已经存储了新的e'。Follower 将会执行事务应用操作，将接收 S' 中的所有事务 Proposal，注意只是接收。
    2. 如果 Follower 的 epoch 不等于 e'，即不是这一轮的 Follower，直接进入下一代循环。
    3. Leader 在接收到过半的 Follower 的 Ack-LD 消息后，发送 Commit 消息所有的 Follower，之后进入下一阶段即 Broadcast（消息广播）。

  3. 第三阶段 Commit-LD：在收到 Leader 的 Commit 消息后，按顺序依次调用 abdeliver(<v, z>) 处理 S' 的每一个事务，随后完成这一阶段。

消息广播

当主从数据同步完成之后，集群就可以对外服务了，Leader 负责写请求（如果有写请求落到 Follower 上，会转发给 Leader）。

  1. 阶段 Propose：Leader 收到来自客户端新的事务请求后，会生成对应的事务 Proposal，并根据 zxid 的顺序（递增）向追随自己的所有 Follower 发送 P<e', <v, z>>，其中 epoch(z) == e'。
  2. 第二阶段 Ack：Follower 根据收到消息的次序来处理这些 Proposal，并追加到 H 中去，然后反馈给 Leader。
  3. 第三阶段 Commit：一旦 Follower 收到来自 Leader 的 Commit(e', <v, z>)消息，将调用 abdeliver(<v, z>) 提交事务 <v, z>。需要注意的是，此时 Follower 必定提交了 z' < z 之前的事务。

接下来集群出去消息广播，正常对外服务的状态，直到下一次选举开始。

广播的流程

在进入消息广播阶段后，Leader 会为每一个 Follower 分配一个 FIFO 形式的队列进行通信，确保了同一时刻一个 Follower 只能和一个 Leader 保持同步，Leader 和 Follower 彼此之间通过心跳检测来感知。

分两种情况 Leader 会终止当前周期的领导，

  1. Leader 掉线了，Follower 的心跳包会超时，然后 Follower 进入 Looking 状态。
  2. Leader 已经没有过半的 Follower 追随了，Leader 自己进入 Looking 状态，追随它的 Follower 也会转为 Looking 状态。

当异常情况发生后，就开始新一轮的崩溃恢复过程。

广播流程，

  1. Leader（主）服务器接收 Client（客户端） 的请求，为其生成 Proposal（提案）。
  2. 然后将 Proposal 发送给所有 Follower （从）。主会为每一个从分配一个单独的队列，以保证消息的有序性。
  3. 主等待所有从服务器反馈 Ack，当有过半的从服务器 Ack 之后，主会提交本地事务。然后广播 Commit 给所有从，从接收到 Commit 之后完成提交。

参考

  1. ZAB paper
  2. zookeeper 分布式协同技术详解
  3. 从 Paxos 到 zookeeper 分布式技术原理与实践
  4. zookeeper wiki
  5. ZooKeeper’s atomic broadcast protocol: Theory and practice
  6. 不要再将数据库称作CP或AP

相关文章