乐趣区

关于java:一文彻底搞懂ZAB算法看这篇就够了

jiezi

最近须要设计一个分布式系统，须要一个中间件来存储共享的信息，来保障多个零碎之间的数据一致性，调研了两个支流框架 Zookeeper 和 ETCD，发现都能满足咱们的零碎需要。其中 ETCD 是 K8s 中采纳的分布式存储，而其底层采纳了 RAFT 算法来保障一致性，之前曾经详细分析了 Raft 算法的原理，明天次要仔细分析下 Zookeeper 的底层算法 -ZAB 算法。

什么是 ZAB 算法？

ZAB 的全称是 Zookeeper Atomic Broadcast（Zookeeper 原子播送)。Zookeeper 是通过 Zab 算法来保障分布式事务的最终一致性。

  1. Zab 协定是为分布式协调服务 Zookeeper 专门设计的一种 反对解体复原  的  原子播送协定 ，是 Zookeeper 保证数据一致性的外围算法。Zab 借鉴了 Paxos 算法，但又不像 Paxos 那样，是一种通用的分布式一致性算法。 它是特地为 Zookeeper 设计的反对解体复原的原子播送协定。
  2. 在 Zookeeper 中次要依赖 Zab 协定来实现数据一致性，基于该协定，zk 实现了一种主备模型（即 Leader 和 Follower 模型）的零碎架构来保障集群中各个正本之间数据的一致性。这里的主备零碎架构模型，就是指只有一台客户端（Leader）负责解决内部的写事务申请，而后 Leader 客户端将数据同步到其余 Follower 节点。

客户端的读取流程：客户端会随机的链接到 zookeeper 集群中的一个节点，如果是读申请，就间接从以后节点中读取数据；如果是写申请，那么节点就会向 Leader 提交事务，Leader 接管到事务提交，会播送该事务，只有超过半数节点写入胜利，该事务就会被提交。

深刻 ZAB 算法

ZAB 算法分为两大块内容，音讯播送 和解体复原。

  • 音讯播送（boardcast）：Zab 协定中，所有的写申请都由 leader 来解决。失常工作状态下，leader 接管申请并通过播送协定来解决。
  • 解体复原（recovery）：当服务首次启动，或者 leader 节点挂了，零碎就会进入恢复模式，直到选出了有非法数量 follower 的新 leader，而后新 leader 负责将整个零碎同步到最新状态。

1. 音讯播送

音讯播送 的过程实际上是一个简化的两阶段提交过程，这里对两阶段提交做一个简略的介绍。

两阶段提交

两阶段提交算法自身是统一强一致性算法，适宜用作数据库的分布式事务，其实数据库的常常用到的 TCC 自身就是一种 2PC。

上面以 MySQL 中对数据库的批改过程，来介绍下两阶段提交的具体流程，在 MySQL 中对一条数据的批改操作首先写 undo 日志，记录的数据原来的样子，接下来执行事务批改操作，把数据写到 redo 日志外面，万一捅娄子，事务失败了，可从 undo 外面复原数据。数据库通过 undo 与 redo 能保证数据的强一致性。

  • 首先第一阶段叫筹备节点，事务的申请都发送给一个个的资源，这里的资源能够是数据库，也能够是其余反对事务的框架，他们会别离执行本人的事务，写日志到 undo 与 redo，然而不提交事务。
  • 当事务管理器收到了所以资源的反馈，事务都执行没报错后，事务管理器再发送 commit 指令让资源把事务提交，一旦发现任何一个资源在筹备阶段没有执行胜利，事务管理器会发送 rollback，让所有的资源都回滚。这就是 2pc，非常简单。

说他是强一致性的是他须要保障任何一个资源都胜利，整个分布式事务才胜利。

长处：原理简略，实现不便
毛病：同步阻塞，单点问题，数据不统一，容错性不好

  • 同步阻塞：在二阶段提交的过程中，所有的节点都在期待其余节点的响应，无奈进行其余操作。这种同步阻塞极大的限度了分布式系统的性能。
  • 单点问题：协调者在整个二阶段提交过程中很重要，如果协调者在提交阶段呈现问题，那么整个流程将无奈运行。更重要的是，其余参与者将会处于始终锁定事务资源的状态中，而无奈持续实现事务操作。
  • 数据不统一：假如当协调者向所有的参与者发送 commit 申请之后，产生了部分网络异样，或者是协调者在尚未发送完所有 commit 申请之前本身产生了解体，导致最终只有局部参与者收到了 commit 申请。这将导致重大的数据不统一问题。
  • 容错性不好：二阶段提交协定没有设计较为欠缺的容错机制，任意一个节点是失败都会导致整个事务的失败。

ZAB 音讯播送过程

Zookeeper 集群中，存在以下三种角色的节点：

  • Leader：Zookeeper 集群的外围角色，在集群启动或解体复原中通过 Follower 参加选举产生，为客户端提供读写服务，并对事务申请进行解决 *。
    Follower：Zookeeper 集群的外围角色，在集群启动或解体复原中加入选举，没有被选上就是这个角色， 为客户端提供读取服务 ，也就是解决非事务申请，Follower 不能处理事务申请，对于收到的事务申请会转发给 Leader。
    Observer：观察者角色， 不加入选举，为客户端提供读取服务，解决非事务申请，对于收到的事务申请会转发给 Leader。应用 Observer 的目标是为了扩大零碎，进步读取性能。
  1. Leader 接管到音讯申请后，将音讯赋予一个全局惟一的 64 位自增 id，叫做：zxid，通过 zxid 的大小比拟即可实现因果有序这一个性。
  2. Leader 通过先进先出队列（通过 TCP 协定来实现，以此实现了全局有序这一个性）将带有 zxid 的音讯作为一个提案（proposal）分发给所有 follower。
  3. 当 follower 接管到 proposal，先将 proposal 写到硬盘，写硬盘胜利后再向 leader 回一个 ACK。
  4. 当 leader 接管到非法数量的 ACKs 后，leader 就向所有 follower 发送 COMMIT 命令，同时会在本地执行该音讯。
  5. 当 follower 收到音讯的 COMMIT 命令时，就会执行该音讯。

相比于残缺的二阶段提交，Zab 协定最大的区别就是不能终止事务，follower 要么回 ACK 给 leader，要么摈弃 leader，在某一时刻，leader 的状态与 follower 的状态很可能不统一，因而它不能解决 leader 挂掉的状况，所以 Zab 协定引入了恢复模式来解决这一问题。

从另一角度看，正因为 Zab 的播送过程不须要终止事务，也就是说不须要所有 follower 都返回 ACK 能力进行 COMMIT，而是只须要非法数量（2n+1 台服务器中的 n+1 台）的 follower，也晋升了整体的性能。

Leader 服务器与每一个 Follower 服务器之间都保护了一个独自的 FIFO 音讯队列进行收发音讯，应用队列音讯能够做到异步解耦。Leader 和 Follower 之间只须要往队列中发消息即可。如果应用同步的形式会引起阻塞，性能要降落很多。

2. 解体复原

解体复原的次要工作就是选举 Leader（Leader Election），Leader 选举分两个场景：

  • Zookeeper 服务器启动时 Leader 选举。
  • Zookeeper 集群运行过程中 Leader 解体后的 Leader 选举。

选举参数

在介绍选举流程之前，须要介绍几个参数，

  • myid: 服务器 ID，这个是在装置 Zookeeper 时配置的，myid 越大，该服务器在选举中被选为 Leader 的优先级会越大。ZAB 算法中通过 myid 来躲避了多个节点可能有雷同 zxid 问题，留神能够比照之前的 Raft 算法，Raft 算法中通过随机的 timeout 来躲避多个节点可能同时成为 Leader 的问题。
  • zxid: 事务 ID，这个是由 Zookeeper 集群中的 Leader 节点进行 Proposal 时生成的全局惟一的事务 ID，因为只有 Leader 能力进行 Proposal，所以这个 zxid 很容易做到全局惟一且自增。因为 Follower 没有生成 zxid 的权限。zxid 越大，示意以后节点上提交胜利了最新的事务，这也是为什么在解体复原的时候，须要优先思考 zxid 的起因。
  • epoch: 投票轮次，每实现一次 Leader 选举的投票，以后 Leader 节点的 epoch 会减少一次。在没有 Leader 时，本轮此的 epoch 会放弃不变。

另外在选举的过程中，每个节点的以后状态会在以下几种状态之中进行转变。

LOOKING: 竞选状态。FOLLOWING: 随从状态，同步 Leader 状态，参加 Leader 选举的投票过程。OBSERVING: 察看状态，同步 Leader 状态，不参加 Leader 选举的投票过程。LEADING: 领导者状态。

选举流程

选举的流程如下：

  • 每个 Server 会收回一个投票, 第一次都是投本人。投票信息：（myid，ZXID）
  • 收集来自各个服务器的投票
  • 解决投票并从新投票，解决逻辑：优先比拟 ZXID, 而后比拟 myid
  • 统计投票，只有超过半数的机器接管到同样的投票信息，就能够确定 leader
  • 扭转服务器状态，进入失常的音讯播送流程。

ZAB 算法须要解决的两大问题

1. 曾经被解决的音讯不能丢

这一状况会呈现在以下场景：当 leader 收到非法数量 follower 的 ACKs 后，就向各个 follower 播送 COMMIT 命令，同时也会在本地执行 COMMIT 并向连贯的客户端返回「胜利」。然而如果在各个 follower 在收到 COMMIT 命令前 leader 就挂了，导致剩下的服务器并没有执行都这条音讯。

为了实现曾经被解决的音讯不能丢这个目标，Zab 的恢复模式应用了以下的策略：

  1. 选举领有 proposal 最大值（即 zxid 最大）的节点作为新的 leader：因为所有提案被 COMMIT 之前必须有非法数量的 follower ACK，即必须有非法数量的服务器的事务日志上有该提案的 proposal，因而，只有有非法数量的节点失常工作，就必然有一个节点保留了所有被 COMMIT 的 proposal。而在选举 Leader 的过程中，会比拟 zxid，因而选举进去的 Leader 必然会蕴含所有被 COMMIT 的 proposal。
  2. 新的 leader 将本人事务日志中 proposal 但未 COMMIT 的音讯解决。
  3. 新的 leader 与 follower 建设先进先出的队列，先将本身有而 follower 没有的 proposal 发送给 follower，再将这些 proposal 的 COMMIT 命令发送给 follower，以保障所有的 follower 都保留了所有的 proposal、所有的 follower 都解决了所有的音讯。

2. 被抛弃的音讯不能再次出现

这一状况会呈现在以下场景：当 leader 接管到音讯申请生成 proposal 后就挂了，其余 follower 并没有收到此 proposal，因而通过恢复模式从新选了 leader 后，这条音讯是被跳过的。此时，之前挂了的 leader 重新启动并注册成了 follower，他保留了被跳过音讯的 proposal 状态，与整个零碎的状态是不统一的，须要将其删除。

Zab 通过奇妙的设计 zxid 来实现这一目标。一个 zxid 是 64 位，高 32 是纪元（epoch）编号，每通过一次 leader 选举产生一个新的 leader，新 leader 会将 epoch 号 +1。低 32 位是音讯计数器，每接管到一条音讯这个值 +1，新 leader 选举后这个值重置为 0。这样设计的益处是旧的 leader 挂了后重启，它不会被选举为 leader，因为此时它的 zxid 必定小于以后的新 leader。当旧的 leader 作为 follower 接入新的 leader 后，新的 leader 会让它将所有的领有旧的 epoch 号的未被 COMMIT 的 proposal 革除。

Zab 协定设计的优良之处有两点，一是简化二阶段提交，晋升了在失常工作状况下的性能；二是奇妙地利用率自增序列，简化了异样复原的逻辑，也很好地保障了程序解决这一个性

参考：

  • https://www.cnblogs.com/CNRF/p/14862669.html

欢送关注公众号【码老思】，这里有最通俗易懂的原创技术干货。

退出移动版