分布式协议及Zookeeper实现(ZAB协议)(二)

女爷i 2022-02-05 02:49 251阅读 0赞

**  在解决分布式数据一致性方面，ZooKeeper并没有直接采用Paxos算法，而是采用了一种被称为ZAB（ZooKeeper Atomic Broadcast）的一致性协议。**

ZAB协议的核心：

***    所有事务请求必须由一个全局唯一的服务器来协调处理，这样的服务器被称为Leader服务器，而余下的其他服务器则成为Follower服务器。Leader服务器负责将一个客户端事务请求转换成一个事务Proposal（提议），并将该Proposal分发给集群中所有的Follower服务器。之后Leader服务器需要等待所有Follower服务器的反馈，一旦超过半数的Follower服务器进行了正确的反馈后，那么Leader就会再次向所有的Follower服务器分发Commit消息，要求其将前一个Proposal进行提交。***

## 协议介绍 ##

**ZAB协议包括两种基本的模式，分别是崩溃恢复和消息广播。**当整个服务框架在启动过程中，或是当Leader服务器出现网络中断、崩溃退出与重启等异常情况时，ZAB协议就会进入恢复模式并选举产生新的Leader服务器。当选举产生了新的Leader服务器，同时集群中已经有过半的机器与该Leader服务器完成了状态同步之后，ZAB协议就会退出恢复模式。其中，状态同步是指数据同步，用来保证集群中存在过半的机器能够和Leader服务器的数据状态保持一致。

当集群中已经有过半的Follower服务器完成了和Leader服务器的状态同步，那么整个服务框架就可以进入消息广播模式了。当一台同样遵守ZAB协议的服务器启动后加入到集群中时，如果此时集群中已经存在一个Leader服务器在负责进行消息广播，那么新加入的服务器就会自觉的进入数据恢复模式；找到Leader所在的服务器，并与其进行数据同步，然后一起参与到消息广播流程中去。ZooKeeper设计成只允许唯一的一个Leader服务器来进行事务请求的处理。Leader服务器在接收到客户端的事务请求后，会生成对应的事务提案并发起一轮广播协议；而如果集群中的其他机器接收到客户端的事务请求，那么这些非Leader服务器会首先将这个事务请求转发给Leader服务器。

当Leader服务器出现崩溃退出或机器重启，亦或是集群中已经不存在过半的服务器与该Leader服务器保持正常通信时，那么在重新开始新一轮的原子广播事务操作之前，所有进程首先会使用崩溃恢复协议来使彼此达到一个一致的状态， 于是整个ZAB流程就会从消息广播模式进入到崩溃恢复模式。

一个机器要成为新的Leader，必须获得过半进程的支持，同时由于每个进程都有可能会崩溃，因此，在ZAB协议运行过程中，前后会出现多个Leader，并且每个进程也有可能会崩溃，因此，在ZAB协议运行过程中，前后会出现多个Leader，并且每个进程也有可能会多次成为Leader。进入崩溃恢复模式后，只要集群中存在过半的服务器能够彼此进行正常通信，那么就可以产生一个新的Leader并再次进入消息广播模式。举个例子来说，一个由3台机器组成的ZAB服务，通常由1个Leader、2个Follower服务器组成。某一个时刻，假如其中一个Follower服务器挂了，整个ZAB集群中不会中断服务的，这是因为Leader服务器依然能够获得过半机器（包括Leader自己）的支持。

### 消息广播 ###

**ZAB协议的消息广播过程使用的是一个原子广播协议，类似于一个二阶段提交过程。**针对客户端的事务请求，Leader服务器会为其生成对应的事务Proposal，并将其发送给集群中其余所有的机器，然后再分别收集各自的选票，最后进行事务提交，下图所示就是ZAB协议消息广播流程的示意图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70][]

在ZAB协议的二阶段提交过程中，移除了中断逻辑，所有的Follower服务器要么正常反馈Leader提出的事务Proposal，要么就抛弃Leader服务器。同时，ZAB协议将二阶段提交中的中断逻辑移除意味着我们可以在过半的Follower服务器已经反馈Ack之后就开始提交事务Proposal了，而不需要等待集群中所有的Follower服务器都反馈响应。

在这种简化了的二阶段提交模型下，是无法处理Leader服务器崩溃退出而带来的数据不一致问题的，因此在ZAB协议中添加了另一个模式，即采用崩溃恢复模式来解决这个问题。另外，整个消息传播协议是基于具有FIFO特性的TCP协议来进行网络通信的，因此能够很容易的保证消息广播过程中消息接收与发送的顺序性。

在整个消息广播中，Leader服务器会为每个事务请求生成对应的Proposal来进行广播，并且在广播事务Proposal之前，Leader服务器会首先为这个事务Proposal分配一个全局单调递增的唯一ID，我们称之为事务ID（即ZXID）。由于ZAB协议需要保证每一个消息严格的因果关系，因此必须将每一个事务Proposal按照其ZXID的先后顺序来进行排序与处理。

具体的，在消息广播过程中，Leader服务器会为每一个Follower服务器都各自分配一个单独的队列，然后将需要广播的事务Proposal依次放入这些队列中去，并且根据FIFO策略进行消息发送。每一个Follower服务器在接收到这个事务Proposal之后，都会首先将其以事务日志的形式写入到本地磁盘中去，并且在成功写入后反馈给Leader服务器一个Ack响应。当Leader服务器接收到超过半数Follower的Ack响应后，就会广播一个Commit消息给所有的Follower服务器以通知其进行事务提交，同时Leader自身也会完成对事务的提交，而每一个Follower服务器在接收到Commit消息后，也会完成对事务的提交。

### 崩溃恢复 ###

ZAB协议的这个基于原子广播协议的消息传播过程，在正常情况下运行非常良好，但是一旦Leader服务器出现崩溃，或者说由于网络原因导致Leader服务器失去了与过半Follower联系，那么就会进入崩溃恢复模式。在ZAB协议中，为了保证程序的正确运行，整个恢复过程结束后需要选举出一个新的Leader服务器。因此，ZAB协议需要一个高效且可靠的Leader选举算法，从而确保能够快速地选举出新的Leader。同时，Leader选举算法不仅仅需要让Leader自己知道其自身已经被选举为Leader，同时还需要让集群中的所有其他机器也能够快速的感知到选举产生的新的Leader服务器。

### 基本特性 ###

**    ZAB 协议需要确保那些已经在Leader服务器上提交的事务最终被所有服务器都提交**

假设一个事务在Leader服务器上被提交了，并且已经得到过半Follower服务器的Ack反馈，但是在他将Commit消息发送给所有Follower机器之前，Leader服务器挂了，如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 1][]

上图的消息C2就是一个典型的例子：在集群正常运行过程中的某一个时刻，Server 1 是Leader服务器，其先后广播了消息P1、P2、C1、P3和C2，其中，当Leader服务器将消息C2（C2是Commit Of Proposal2的缩写，即提交事务Proposal2）发出后就立即崩溃退出了。针对这种情况，ZAB协议就需要确保事务Proposal2最终能够在所有的服务器上都被提交成功，否则将出现不一致。

**    ZAB协议需要确保丢弃那些只在Leader服务器上被提出的事务**

相反，如果在崩溃恢复过程中出现一个需要被丢弃的提案，那么在崩溃恢复结束后需要跳过该事务Proposal，如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 2][]

在上图所示的集群中，假设初始的Leader服务器Server1 在提出了一个事务Proposal3之后就崩溃退出了，从而导致集群中的其他服务器都没有收到这个事务Proposal。于是，当Server1恢复过来再次加入到集群中的时候，ZAB协议需要确保丢弃Proposal3这个事务。

结合上面提到的这两个崩溃恢复过程中需要处理的特殊情况，就决定了ZAB协议必须设计这样一个Leader选举算法：能够确保提交已经被Leader提交的事务Proposal，同时丢弃已经被跳过的事务Proposal。针对这个要求，如果让Leader选举算法能够保证新选举出来的Leader服务器拥有集群中所有机器最高编号（即ZXID最大）的事务Proposal，那么就可以保证这个新选举出来的Leader一定具有所有已经提交的提案。更为重要的是，如果让具有最高编号事务Proposal的机器来成为Leader，就可以省去Leader服务器检查Proposal的提交和丢弃工作的这一步操作了。

### 数据同步 ###

完成Leader选举之后，在正式开始工作（即接收客户端的事务请求，然后提出新的提案）之前，Leader服务器会首先确认事务日志中的所有Proposal是否都已经被集群中过半的机器提交了，即是否完成数据同步。

所有正常运行的服务器，要么成为Leader，要么成为Follower并和Leader保持同步。Leader服务器需要确保所有的Follower服务器能够接收到每一条事务Proposal，并且能够正确的将所有已经提交了的事务Proposal应用到内存数据库中去。具体的，Leader服务器会为每一个Follower服务器都准备一个队列，并将那些没有被Follower服务器同步的事务以Proposal消息的形式逐个发送给Follower服务器，并在每一个Proposal消息后面紧接着再发送一个Commit消息，以表示该事务已经被提交。等到Follower服务器将所有其尚未同步的事务Proposal都从Leader服务器上同步过来并成功应用到本地数据库中后，Leader服务器就会将该Follower服务器加入到真正的可用Follower列表中，并开始之后的其他流程。

上面的是正常情况下的数据同步逻辑，下面来看ZAB协议是如何处理那些需要被丢弃的事务Proposal的。在ZAB协议的事务编号ZXID设计中，ZXID是一个64位的数字，其中低32位可以看作是一个简单的单调递增的计数器，针对客户端的每一个事务请求，Leader服务器在产生一个新的事务Proposal的时候，都会对该计数器进行加1操作；而高32位则代表了Leader周期epoch的编号，每当选举产生一个新的Leader服务器，就会从这个Leader服务器上取出其本地日志汇总最大事务Proposal的ZXID，并从该ZXID中解析出对应的epoch值，然后再对其进行加1操作，之后就会以此编号作为新的epoch，并将低32位置0来开始生成新的ZXID。ZAB协议中的这一通过epoch编号来区分Leader周期变化的策略，能够有效地避免不同的Leader服务器错误的使用相同的ZXID编号提出不一样的事务Proposal的异常情况，这对于识别在Leader崩溃恢复前后生成的Proposal非常有帮助，大大简化和提升了数据恢复流程。

基于这样的策略，**当一个包含了上一个Leader周期中尚未提交过的事务Proposal的服务器启动时，其肯定无法成为Leader，原因很简单，因为当前集群中一定包含一个Quorum集合，该集合中的机器一定包含了更高epoch的事务Proposal，因此这台机器的事务Proposal肯定不是最高，也就是无法成为Leader了。**当这台机器加入到集群中，以Follower角色连接上Leader服务器之后，Leader服务器会根据自己服务器上最后被提交的Proposal来和Follower服务器的Proposal进行比对，比对的结果当然是Leader会要求Follower进行一个回退操作——回退到一个确实已经被集群中过半机器提交的最新的事务Proposal。

## 深入ZAB协议 ##

### ZAB算法描述 ###

**整个ZAB 协议主要包括消息广播和崩愤恢复两个过程，进一步可以细分为三个阶段，分别是发现(Discovery)、同步(Synchronization)和广播(Broadcast)阶段。组成ZAB协议的每一个分布式进程，会循环地执行这三个阶段，我们将这样一个循环称为一个主进程周期。**

<table> 
 <thead> 
  <tr> 
   <th style="width:69px;">术语名</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="width:69px;">F.p</td> 
   <td>Follower f处理过的最后一个事务 Proposal</td> 
  </tr> 
  <tr> 
   <td style="width:69px;">F.zxid</td> 
   <td>Follower f 处理过的历史事务Proposal 中最后一个事务Proposal 的事务标识ZXID</td> 
  </tr> 
  <tr> 
   <td style="width:69px;">hf</td> 
   <td>每一个Follower f通常都已经处理（接受）了不少事务Proposal ,并且会有一个针对已经处理过的事务的集合， 将其表示为hf， 表示Follower f 已经处理过的事务序列</td> 
  </tr> 
  <tr> 
   <td style="width:69px;">Ie</td> 
   <td>初始化历史记录，在某一个主进程周期epoch e 中， 当准Leader 完成阶段一之后，此时它的hf就被标记为Ie</td> 
  </tr> 
 </tbody> 
</table>

### 阶段1：发现 ###

**    阶段一主要就是Leader选举过程，用于在多个分布式进程中选举出主进程，准Leader L和Follower F的工作流程分别如下**：

*  步骤F.1.1：Follower F将自己最后接受的事务Proposal的epoch值CEPOCH(F.p)发送给准Leader L。
 *  步骤L.1.1：当接收到来自过半Follower的CEPOCH(F.p)消息后，准Leader L会生成NEWEPOCH(e’)消息给这些过半的Follower。 （关于这个epoch值e'，准Leader L 会从所有接收到的CEPOCH(F.p）消息中选取出最大的epoch值，然后对其进行加1操作，即为e'。）
 *  步骤F.1.2：当Follower接收到来自准Leader L 的NEWEPOCH(e')消息后，如果其检测到当前的CEPOCH(F.p)值小于e'，那么就会将CEPOCH(F.p)赋值为e',同时向这个准Leader L反馈Ack消息。在这个反馈消息(ACK-E(F.p,hf)中,包含了当前该Follower 的epoch CEPOCH(F.p),以及该Follower的历史事务Proposal集合:hf。

当Leader L接收到来自过半Follower的确认消息Ack之后，Leader L就会从这过半服务器中选取出一个Follower F,并使用其作为初始化事务集合Ie'。

关于这个 Follower F 的选取，对于Quorum中其他任意一个Follower F'，F需要满足以下两个条件中的一个：

![20190506001752271.png][]

### 阶段2：同步 ###

在这一阶段中，Leader L和Follower F的工作流程分别如下。

*  步骤L.2.1：Leader L会将e'和Ie'以NEWLEADER(e',Ie'）消息的形式发送给所有Quorum中的Follower。
 *  步骤F.2.1：当Follower接收到来自Leader L的NEWLEADER(e',Ie')消息后，如果Follower发现CEPOCH(F.p)！=e'，那么直接进入下一轮循环，因为此时Follower发现自己还在上一轮，或者更上轮，无法参与本轮的同步。如果CEPOCH(F.p) = e'，那么Follower就会执行事务应用操作。

最后，Follower会反馈给Leader,表明自己已经接受并处理了所有Ie'中的事务 Proposal。

*  步骤L.2.2： 当Leader接收到来自过半Follower针对NEWLEADER(e',Ie')的反馈消息后，就会向所有的Follower发送Commit消息。至此Leader完成阶段二。
 *  步骤F.2.2： 当Follower收到来自Leader的Commit消息后，就会依次处理并提交所有在Ie'中未处理的事务。至此Follower完成阶段二。

### 阶段3：广播 ###

**完成同步阶段后，ZAB协议就可以正式接受客户端的事物请求，并进行消息广播流程。**

*  步骤L.3.1： Leader L接收到客户端新的事务请求后，会生成对应的事务Proposal,并根据ZXID的顺序向所有Follower发送提案<e',<v,z>> ,其中epoch(z)=e'。
 *  步骤F.3.1： Follower根据消息接收的先后次序来处理这些来自Leader的事务Proposal,并将他们追加到hf中去，之后再反馈给Leader。
 *  步骤L.3.1： 当Leader接收到来自过半Follower针对事务Proposal<e',<v,z>>的Ack消息后，就会发送Commit<e',<v,z>>消息给所有的Follower，要求它们进行事务的提交。
 *  步骤F.3.2： 当Follower F接收到来自Leader的Commit <e',<v,z>>消息后，就会开始提交事务Proposal <e,<v,z>>。需要注意的是此时该Follower F必定已经提交事物Proposal<e',<v',z'>>。

**    在正常运行过程中， ZAB协议会一直运行于阶段三来反复地进行消息广播流程。如果出现Leader崩溃或其他原因导致Leader缺失，那么此时ZAB协议会再次进入阶段一，重新选举新的Leader。 **

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 3][]

### 运行分析*　　* ###

*    *在ZAB协议的设计中，每一个进程都有可能处于以下三种状态之一。**　　　　**

*  LOOKING: Leader选举阶段
 *  FOLLOWING: Follower服务器和Leader保持同步状态
 *  LEADING: Leader服务器作为主进程领导状态

组成ZAB协议的进程刚开始启动时，所有进程都处于LOOKING的初始化状态，此时集群中并不存在Leader。所有处于这种状态的进程都会试图去选举出一个Leader。如果某个进程发现已经选举出了Leader，那么它会马上切换到FOLLOWING状态，开始和Leader保持同步。这里，我们将处于FOLLOWING状态的进程称为Follower，将处于LEADING状态的进程称为Leader。考虑到Leader进程随时可能挂掉，当检测出Leader已经崩溃或放弃领导地位时，其余的FOLLOWING状态的进程就会重新进入LOOKING状态，并开始进行新一轮的Leader选举。**因此在ZAB协议中，每个进程的状态都在LOOKING、FOLLOWING和LEADING之间不断转换。**

**在完成Leader选举和数据同步之后，ZAB协议就进入了广播阶段。**在这个阶段中，Leader会以队列的形式为每一个与自己保持同步的Follower创建一个操作队列。同一时刻，一个Follower只能与一个Leader保持同步。Leader进程与所有的Follower进程之间通过心跳检测机制来感知彼此的状态。如果Leader能在超时时间内收到Follower的心跳，那么Follower就会一直与该Leader保持同步。而如果在指定的超时时间内Leader无法从过半的Follower进程那收到心跳检测，或者TCP连接本身断开了，那么Leader就会停止对当前周期的领导，同时转换到LOOKING状态，所有Follower也会放弃这个Leader，进入LOOKING状态。之后，所有进程就会开启新一轮的Leader选举，并在选举产生新的Leader之后开始新一轮的主进程周期。

## ZAB与Paxos算法的联系与区别 ##

ZAB 协议并不是Paxos算法的一个典型实现，在讲解ZAB和Paxos之间的区别之前，首先来看下两者的联系：

*  两者都存在一个类似于Leader进程的角色，由其负责协调多个Follower进程的运行。
 *  Leader进程都会等待超过半数的Follower做出正确的反馈后，才会将一个提案进行提交。
 *  在ZAB协议中，每个Proposal中都包含了一个epoch值，用来代表当前的Leader周期，在Paxos算法中，同样存在这样的一个标识，只是名字变成了Ballot。

**在Paxos算法中，一个新选举产生的主进程会进行两个阶段的工作。第一阶段被称为读阶段，在这个阶段中，这个新的主进程会通过和所有其他进程进行通信的方式来收集上一个主进程提出的提案，井将它们提交。第二阶段被称为写阶段，在这个阶段，当前主进程开始提出它自己的提案。**在Paxos算法设计的基础上，ZAB协议额外添加了一个同步阶段。在同步阶段之前，ZAB协议也存在一个和Paxos算法中的读阶段非常类似的过程，称为发现(Discovery)阶段。在同步阶段中，新的Leader会确保存在过半的Follower已经提交了之前Leader周期中的所有事务Proposal。这一同步阶段的引入，能够有效地保证Leader在新的周期中提出事务Proposal之前，所有的进程都已经完成了对之前所有事务Proposal的提交。一旦完成同步阶段后，那么ZAB就会执行和Paxos算法类似的写阶段。

总的来讲，**ZAB协议和Paxos算法的本质区别在于，两者的设计目标不太一样。ZAB协议主要用于构建一个高可用的分布式数据主备系统，例如ZooKeeper，而Paxos算法则是用于构建一个分布式的一致性状态机系统。**

**参考《从Paxos到Zookeeper 分布式一致性原理与实践》**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70]: /images/20220205/5b56a8c135224188991e96c7ed581e16.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 1]: /images/20220205/10527045a74d4b3f81abe92a3275da36.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 2]: /images/20220205/7d88095aab5240d182636f86da494518.png
[20190506001752271.png]: /images/20220205/66d21ec521d64ad596a3cffb9bb2527b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70 3]: /images/20220205/42397f7a08ff47e6b93a29255f5bee2a.png