ZAB 协议

ZAB 协议 简介

• ZAB ，Zookeeper Atomic Broadcast，ZooKeeper原子消息广播协议，是专为ZooKeeper 设计的一种支持崩溃恢复的原子广播协议，在 Zookeeper 中，主要依赖 ZAB 协议来实现分布式数据一致性。
• Zookeeper 使用一个单一主进程来接收并处理客户端的所有事务请求，即写请求。当服务器数据的状态发生变更后，集群采用 ZAB 原子广播协议，以事务提案 Proposal 的形式广播到所有的副本进程上。ZAB 协议能够保证一个全局的变更序列，即可以为每一个事务分配一个全局的递增编号 xid。 当 Zookeeper 客户端连接到 Zookeeper 集群的一个节点后，若客户端提交的是读请求，那么当前节点就直接根据自己保存的数据对其进行响应；如果是写请求且当前节点不是Leader，那么节点就会将该写请求转发给 Leader，Leader 会以提案的方式广播该写 *** 作，只要有超过半数节点同意该写 *** 作，则该写 *** 作请求就会被提交。然后 Leader 会再次广播给所有订阅者，即通知它们同步数据。
  

ZAB 与 Paxos 的关系

• ZAB 协议是 Fast Paxos 算法的一种工业实现算法。但两者的设计目标不太一样。ZAB 协议主要用于构建一个高可用的分布式数据主备系统，例如，Leader 挂了，马上就可以选举出一个新的 Leader。而 Paxos 算法则是用于构建一个分布式一致性状态机系统，确保系统中各个节点的状态都是一致的。
• ZAB 还使用 Google 的 Chubby 算法作为分布式锁的实现，而 Google 的 Chubby 也是 Paxos 算法的应用。

三类角色

为了避免 Zookeeper 的单点问题，Zookeeper 也是以集群的形式出现的。Zookeeper 集群中的角色主要有以下三类：

• Leader : 事务请求的唯一处理者，并且可处理读
• Follower ：可处理读，不会处理事务请求。如果leader挂掉，“具备选举权和被选举权”。
• Observer ： 可处理读，不会处理事务请求。如果leader挂掉，“不具备选举权和被选举权”。其目的在于提高集群请求处理的吞吐量。

这三类角色在不同的情况下又有一些不同的叫法:

• Learner ：即Follower 或者 Observer
• QuorumServer ：即leader 或者 Follower

三个数据

在 ZAB 中有三个很重要的数据：

• zxid ：64位long类型，高32位表示epoch，低32位表示xid
• epoch ：时期。每个leader选举结束后会生成一个epoch，并通知给所有learner
• xid ：事务id，流水记录号。

三种模式

ZAB 协议中对 Zookeeper Server 的状态描述有三种模式。这三种模式并没有十分明显的界线，它
们相互交织在一起。

• 恢复模式 ： 集群启动中或leader崩溃后的系统模式。 该模式包含两个阶段：Leader选举和初始化同步。
• 广播模式 ： 分为初始化广播和更新广播。
• 同步模式 ： 分为初始化同步和更新同步。

同步模式和广播模式 初始化同步

当完成 Leader 选举后，此时的 Leader 还是一个准 Leader，其要经过初始化同步后才能变为真正的 Leader。

具体过程：

1. 为了保证 Leader 向 Learner 发送提案的有序，Leader 会为每一个 Learner 服务器准备一
   个队列
2. Leader 将那些没有被各个 Learner 同步的事务封装为 Proposal
3. Leader 将这些 Proposal 逐条发给各个 Learner，并在每一个 Proposal 后都紧跟一个
   COMMIT 消息，表示该事务已经被提交，Learner 可以直接接收并执行
4. Learner 接收来自于 Leader 的 Proposal，并将其更新到本地
5. Follower 更新成功后，会向准 Leader 发送 ACK 信息
6. Leader 服务器在收到该来自 Follower 的 ACK 后就会将该 Follower 加入到真正可用的
   Follower 列表。没有反馈 ACK，或反馈了但 Leader 没有收到的 Follower，Leader 不会将
   其加入到 Follower 列表

消息广播算法

当集群中已经有过半的 Follower 完成了初始化状态同步，那么整个 Zookeeper 集群就进入到了
正常工作模式

如果集群中的其他节点收到客户端的事务请求，那么这些 Learner 会将请求转发给Leader 服务器。然后再依次执行：

1. Leader 接收到事务请求后，为事务赋予一个全局唯一的 64 位自增 id，即 zxid，通过
   zxid 的大小比较即可实现事务的有序性管理，然后将事务封装为一个 Proposal
2. Leader 根据 Follower 列表获取到所有 Follower，然后再将 Proposal 通过这些 Follower 的
   队列将提案发送给各个 Follower
3. 当 Follower 接收到提案后，会先将提案的 zxid 与本地记录的事务日志中的最大的 zxid
   进行比较。若当前提案的 zxid 大于最大 zxid，则将当前提案记录到本地事务日志中，并
   向 Leader 返回一个 ACK
4. 当 Leader 接收到过半的 ACK 后，Leader 就会向所有 Follower 的队列发送 COMMIT
   消息，向所有 Observer 的队列发送 Proposal
5. 当 Follower 收到 COMMIT 消息后，就会将日志中的事务正式更新到本地。当 Observer
   收到 Proposal 后，会直接将事务更新到本地

恢复模式的两个原则

当集群正在启动过程中，或 Leader 与超过半数的主机断连后，集群就进入了恢复模式。对于要恢复的数据状态需要遵循两个原则。

1.已被处理过的请求的不能丢

当 Leader 收到超过半数 Follower 的 ACK 后，就向各个 Follower 广播 COMMIT 消息，批准各个 Server 执行该写 *** 作事务。当各个 Server 在接收到 Leader 的 COMMIT 消息后就会在本地执行该写 *** 作，然后会向客户端响应写 *** 作成功。但是如果在非全部 Follower 收到 COMMIT 消息之前 Leader 就挂了，这将导致一种后果：部分 Server 已经执行了该事务，而部分 Server 尚未收到 COMMIT 消息，所以其并没有执行该事务。当新的 Leader 被选举出，集群经过恢复模式后需要保证所有 Server 上都执行了那些已经被部分 Server 执行过的事务。

2.已被丢弃的消息不能再现

当 Leader 接收到事务请求并生成了 Proposal，但还未向任何 Follower 发送时就挂了，因此，其他 Follower 根本就不知道该 Proposal 的存在。当新的 Leader 选举出来，整个集群进入正常服务状态后，之前挂了的 Leader 主机重新启动并注册成为了 Follower。若那个别人根本不知道的 Proposal 还保留在那个主机，那么其数据就会比其它主机多出了内容，导致整个系统状态的不一致。所以，该 Proposal 应该被丢弃。类似这样应该被丢弃的事务，是不能再次出现在集群中的，应该被清除。

Leader 选举

当集群正在启动过程中，或 Leader 与超过半数的主机断连后，集群就进入了恢复模式。而恢复模式中最重要的阶段就是 Leader 选举。

三个基本概念

1. myid : 这是 zk 集群中服务器的唯一标识，称为 myid。例如，有三个 ZooKeeper 服务器，那么编号分别是1,2,3。
2. 逻辑时钟 : Logicalclock，是一个整型数，该概念在选举时称为 logicalclock，而在选举结
   束后称为 epoch。即 epoch 与 logicalclock 是同一个值，在不同情况下的不同名称。
3. ZooKeeper 状态 : ZooKeeper 集群中的每一台主机，在不同的阶段会处于不同的状态。每一台主机具有四种状态。
   • LOOKING
   • FOLLOWING
   • OBSERVING
   • LEADING

Leader 选举算法

在集群启动过程中的 Leader 选举过程（算法）与 Leader 断连后的 Leader 选举过程稍微有一些区别，基本相同。

A. 集群启动中的 Leader 选举

• 若进行 Leader 选举，则至少需要两台主机，这里以三台主机组成的集群为例。
• 在集群初始化阶段，当第一台服务器 Server1 启动时，其会给自己投票，然后发布自己的投票结果。投票包含所推举的服务器的 myid 和 ZXID，使用(myid, ZXID)来表示，此时 Server1的投票为(1, 0)。由于其它机器还没有启动所以它收不到反馈信息，Server1 的状态一直属于Looking，即属于非服务状态。
• 当第二台服务器 Server2 启动时，此时两台机器可以相互通信，每台机器都试图找到
  Leader，选举过程如下：

1. 每个 Server 发出一个投票。此时 Server1 的投票为(1, 0)，Server2 的投票为(2, 0)，然后
   各自将这个投票发给集群中其他机器。
2. 接受来自各个服务器的投票。集群的每个服务器收到投票后，首先判断该投票的有效
   性，如检查是否是本轮投票、是否来自 LOOKING 状态的服务器。
3. 处理投票。针对每一个投票，服务器都需要将别人的投票和自己的投票进行 PK，PK
   规则如下：
   • 优先检查 ZXID。ZXID 比较大的服务器优先作为 Leader。
   • 如果 ZXID 相同，那么就比较 myid。myid 较大的服务器作为 Leader 服务器。
4. 统计投票。每次投票后，服务器都会统计投票信息，判断是否已经有过半机器接受到相同的投票信息。对于 Server1、Server2 而言，都统计出集群中已经有两台主机接受了(2, 0)的投票信息，此时便认为已经选出了新的 Leader，即 Server2。
5. 改变服务器状态。一旦确定了 Leader，每个服务器就会更新自己的状态，如果是Follower，那么就变更为 FOLLOWING，如果是 Leader，就变更为 LEADING。
6. 添加主机。在新的 Leader 选举出来后 Server3 启动，其想发出新一轮的选举。但由于
   当前集群中各个主机的状态并不是 LOOKING，而是各司其职的正常服务，所以其只能是以
   Follower 的身份加入到集群中。
   

B. 断连后的 Leader 选举

• 在 Zookeeper 运行期间，Leader 与非 Leader 服务器各司其职，即便当有非 Leader 服务器宕机或新加入时也不会影响 Leader。但是若 Leader 服务器挂了，那么整个集群将暂停对外服务，进入新一轮的 Leader 选举，其过程和启动时期的 Leader 选举过程基本一致。
• 假设正在运行的有 Server1、Server2、Server3 三台服务器，当前 Leader 是 Server2，若
  某一时刻 Server2 挂了，此时便开始新一轮的 Leader 选举了。选举过程如下：

1. 变更状态。Leader 挂后，余下的非 Observer 服务器都会将自己的服务器状态由FOLLOWING 变更为 LOOKING，然后开始进入 Leader 选举过程。
2. 投票。每个 Server 会发出一个投票，仍然会首先投自己。不过，在运行期间每个服务器上
   的 ZXID 可能是不同，此时假定 Server1 的 ZXID 为 111，Server3 的 ZXID 为 333；在第一轮投票中，Server1 和 Server3 都会投自己，产生投票(1, 111)，(3, 333)，然后各自将投票发送给集群中所有机器。
3. 接收来自各个服务器的投票。与启动时过程相同。集群的每个服务器收到投票后，首先判断该投票的有效性，如检查是否是本轮投票、是否来自 LOOKING 状态的服务器。
4. 处理投票。与启动时过程相同。针对每一个投票，服务器都需要将别人的投票和自己的投票进行 PK。对于 Server1 而言，它的投票是(1, 111)，接收 Server3 的投票为(3, 333)。其首先会比较两者的 ZXID，Server3 投票的 zxid 为 333 大于 Server1 投票的 zxid 的 111，于是Server1 更新自己的投票为(3, 333)，然后重新投票。对于 Server3 而言，其无须更新自己的投票，只是再次向集群中所有主机发出上一次投票信息即可。
5. 统计投票。与启动时过程相同。对于 Server1、Server2 而言，都统计出集群中已经有两台主机接受了(3, 333)的投票信息，此时便认为已经选出了新的 Leader，即 Server3。
6. 改变服务器的状态。与启动时过程相同。一旦确定了 Leader，每个服务器就会更新
   自己的状态。Server1 变更为 FOLLOWING，Server3 变更为 LEADING。
   

GAP定理

CAP 原则又称 CAP 定理，指的是在一个分布式系统中，Consistency（一致性）、Availability（可用性）、Partition tolerance（分区容错性），三者不可兼得。

• 一致性（C）：分布式系统中多个主机之间是否能够保持数据一致的特性。当系统数据发生更新 *** 作后，各个主机中的数据仍然处于一致的状态。
• 可用性（A）：系统提供的服务必须一直处于可用的状态，即对于用户的每一个请求，系统总是可以在有限的时间内对用户做出响应。
• 分区容错性（P）：分布式系统在遇到任何网络分区故障时，仍能够保证对外提供满足一致性或可用性的服务。

对于分布式系统，网络环境相对是不可控的，出现网络分区是不可避免的，因此系统必须具备分区容错性。但其并不能同时保证一致性与可用性。CAP 原则对于一个分布式系统来说，只可能满足两项，即要么 CP，要么 AP。

base 理论

base 是 Basically Available（基本可用）、Soft state（软状态）和 Eventually consistent（最
终一致性）三个短语的简写。
base 理论的核心思想是：即使无法做到强一致性，但每个系统都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性。

ZooKeeper 与 CP

ZooKeeper 遵循的是 CP 原则，即保证了一致性，但牺牲了可用性。体现在哪里呢？

• 当 Leader 宕机后，ZooKeeper 集群会马上进行新的 Leader 的选举。但选举时长在 30-200 毫秒间，整个选举期间 ZooKeeper 集群是不接受客户端的读写 *** 作的，即 ZooKeeper 集群是处于瘫痪状态的。所以不满足可用性。

高可用集群的容灾 服务器数量的奇数与偶数

• 若出现超过半数的主机宕机，则投票永远无法通过。基于该理论，由 5 台主机构成的集群，最多只允许 2 台宕机。而由 6 台构成的集群，其最多也只允许 2 台宕机。即，6 台与5 台的容灾能力是相同的。基于此容灾能力和资源节省的原因，建议使用奇数台主机构成集群。（但从系统吞吐量上说，6 台主机的性能一定是高于 5 台的）

容灾设计方案

1. 三机房部署 ： 最常见的、容灾性最好的部署方案
2. 双机房部署 ：（若主机房出现问题，则整个集群会瘫痪）

重启

1. 整体重启：将整个集群停止，然后更新所有主机的配置后再次重启集群。该方式会使集群停止对外服务，所以该方式慎用。
2. 部分重启： 每次重启一小部分主机。注意：不能多于半数，因为重启的主机过半，则无法进行选举，无法应对宕机或者写 *** 作。