ZAB协议分析和ZooKeeper的leader选举机制

Posted on | In , | | 浏览 次
Words count in article: 4.2k | Reading time ≈ 14

前言

ZAB协议是专门为zookeeper实现分布式协调功能而设计。zookeeper主要是根据ZAB协议是实现分布式系统数据一致性。

zookeeper根据ZAB协议建立了主备模型完成zookeeper集群中数据的同步。这里所说的主备系统架构模型是指，在zookeeper集群中，只有一台leader负责处理外部客户端的事物请求(或写操作)，然后leader服务器将客户端的写操作数据同步到所有的follower节点中。

1 ZAB协议内容

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

ZAB有两种基本的模式：崩溃恢复和消息广播。

  • 当整个服务框架启动过程中或Leader服务器出现网络中断、崩溃退出与重启等异常情况时，ZAB协议就会进入恢复模式并选举产生新的Leader服务器。

  • 当选举产生了新的Leader服务器，同时集群中已经有过半的机器与该Leader服务器完成了状态同步之后，ZAB协议就会退出恢复模式，那么整个服务框架就可以进入消息广播模式。其中，所谓的状态同步是指数据同步，用来保证集群中存在过半的机器能够与leader服务器的数据状态保持一致。

  • Leader选举算法不仅仅需要让Leader自身知道已经被选举为Leader，同时还需要让集群中的所有其他机器也能够快速地感知到选举产生的新的Leader服务器。

  • 当一台同样遵守ZAB协议的服务器启动并加入集群后，如果已经存在leader，那么它会自觉的找到leader，与其进行数据同步，然后一起参与消息广播。

  • 如果follower服务器接收到客户端的事务请求，那么他们会将这个事务请求转发给leader服务器。

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

  • 一个机器要成为leader，要获得过半机器的支持，而由于每台机器都可能崩溃，因此整个过程可能出现多个leader，一个机器也可能多次成为leader。

2 消息广播

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

  • 此处ZAB的二阶段提交和一般的二阶段提交略有不同，ZAB移除了二阶段提交中的事务中断的逻辑，follower服务器要么正常反馈，要么抛弃leader。好处是我们不需要等待所有follower都反馈响应才能提交事务，坏处是集群无法处理leader崩溃而带来的数据不一致的问题。后者需要崩溃恢复模式来解决这个问题。

  • 整个消息广播协议是基于具有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之后，也会完成对事务的提交。

  • 在广播过程中，如果follower接收到proposal之后记录事务日志失败，或者proposal丢失。紧接着不久后，它直接接到了这个proposal的commit，那么follower就会向leader发送请求重新申请这个任务，leader会再次发送proposal和commit。

关于 ZXID
  zxid，也就是事务id，它是全局唯一且递增的，为了保证事务的顺序一致性，zookeeper采用了递增的事务id号（zxid）来标识事务。所有的提议（proposal）都在被提出的时候加上了 zxid。实现中zxid是一个 64 位的数字，它高32 位是epoch（ZAB协议通过epoch编号来区分Leader周期变化的策略）用来标识leader关系是否改变，每次一个leader被选出来，它都会有一个新的epoch=（原来的 epoch+1），标识当前属于那个 leader 的统治时期。低 32 位用于递增计数。

3 崩溃恢复

  • 当整个服务框架启动过程中或Leader服务器出现网络中断、崩溃退出与重启等异常情况无法与半数以上的follower联系时，ZAB协议就会进入恢复模式。

3.1 崩溃恢复下的两种情况和所要保证的特性

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

    • 如果leader在崩溃前发出了proposal1，proposal2，commit1（proposal1的commit），proposal3，commit2（说明leader自己已经commit了proposal2），那么ZAB需要确保恢复后proposal2在所有服务器上都被提交成功，否则会出现不一致。

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

    • 如果leader服务器A在崩溃前发出了proposal1，proposal2，commit1（proposal1的commit），proposal3，commit2，并且执行了commit3（说明leader自己已经commit了proposal3），但是commit3还未发出，leader便宕机了，那么ZAB需要确保恢复后，A重新加入集群（大概率不是leader了）后，要舍弃proposal3这个事务。

      3.2 进入崩溃恢复模式的流程

  3. 当leader出现问题，zab协议进入崩溃恢复模式，并且选举出新的leader。当新的leader选举出来以后，如果集群中已经有过半机器完成了leader服务器的状态同（数据同步），退出崩溃恢复，进入消息广播模式。

  1. 当新的机器加入到集群中的时候，如果已经存在leader服务器，那么新加入的服务器就会自觉进入崩溃恢复模式，找到leader进行数据同步。

3.2.1 leader选举算法

zookeeper提供了三种选举方式：

  • LeaderElection
  • AuthFastLeaderElection
  • FastLeaderElection （最新默认）
    默认的算法是FastLeaderElection，所以这里主要分析它的选举机制。

选举过程中，有四个概念我们需要明确一下：

  1. Serverid：服务器ID
    • 比如有三台服务器，编号分别是1,2,3。
  2. Zxid：数据ID
    • 事务id，你也可以理解为当前服务器中存放的最大数据ID。
  3. Epoch：逻辑时钟
    • 在投票过程中，每投完一次票这个数据就会增加，然后与接收到的其它服务器返回的投票信息中的数值相比，根据不同的值做出不同的判断。
  4. Server状态：选举状态
  • LOOKING，竞选状态。
  • FOLLOWING，随从状态，同步leader状态，参与投票。
  • OBSERVING，观察状态，同步leader状态，不参与投票。
  • LEADING，领导者状态。

zk在选举投票的时候，他们的票上，就带有上述这四个信息。

根据前文的描述，我们知道选举成功的leader应该要满足如下特性：

  • 能够确保提交已经被Leader提交的事务的Proposal，同时丢弃已经被跳过的事务Proposal。
  • 如果让Leader选举算法能够保证新选举出来的Leader服务器拥有集群所有机器中最高编号（ZXID最大）的事务Proposal，那么就可以保证这个新选举出来的Leader一定具有所有已经提交的更改。
  • 更为重要的是，如果让具有最高编号事务的Proposal机器成为Leader，就可以省去Leader服务器查询Proposal的提交和丢弃工作这一步骤了。

所以zk的leader选举的判断优先级是（后文我们称为rules judging）：

  1. 优先检查ZXID。ZXID比较大的服务器优先作为Leader
  2. 如果ZXID相同，那么就比较Serverid。Serverid较大的服务器作为Leader服务器。

选举步骤如下：

  1. Server刚启动（宕机恢复或者刚启动）准备加入集群，此时读取自身的zxid等信息。

  2. 所有Server加入集群时都会推荐自己为leader，然后将（leader id 、 zixd 、 epoch）作为广播信息，广播到集群中所有的服务器(Server)。然后等待集群中的服务器返回信息。

  3. 收到集群中其他服务器返回的信息，此时要分为两类：该服务器处于looking状态，或者其他状态。

    1. 服务器处于looking状态
      1. 首先判断逻辑时钟Epoch:
        • 如果接收到Epoch大于自己目前的逻辑时钟（说明自己所保存的逻辑时钟落伍了）。更新本机逻辑时钟Epoch，同时 Clear其他服务发送来的选举数据（这些数据已经OUT了）。然后根据rules judging判断是否需要更新当前自己的选举情况（一开始选择的leader id是自己）。然后再将自身最新的选举结果(也就是上面提到的三种数据（leader Serverid，Zxid，Epoch）广播给其他server)
        • 如果接收到的Epoch小于目前的逻辑时钟。说明对方处于一个比较OUT的选举轮数，这时只需要将自己的 （leader Serverid，Zxid，Epoch）发送给他即可。
        • 如果接收到的Epoch等于目前的逻辑时钟。再根据判断规则，将自身的最新选举结果广播给其他 server。
      2. 如果Server接收到了其他所有服务器的选举信息，那么则根据这些选举信息确定自己的状态（Following,Leading），结束Looking，退出选举。
      3. 即使没有收到所有服务器的选举信息，也可以判断一下根据以上过程之后最新的选举leader是不是得到了超过半数以上服务器的支持，如果是则尝试接受最新数据，倘若没有最新的数据到来，说明大家都已经默认了这个结果,同样也设置角色退出选举过程。
    2. 服务器处于其他状态（Following, Leading）
      1. 如果逻辑时钟Epoch相同,将该数据保存到recvset,如果所接收服务器宣称自己是leader,那么将判断是不是有半数以上的服务器选举它,如果是则设置选举状态退出选举过程
      2. 否则这是一条与当前逻辑时钟不符合的消息，那么说明在另一个选举过程中已经有了选举结果，于是将该选举结果加入到outofelection集合中，再根据outofelection来判断是否可以结束选举,如果可以也是保存逻辑时钟，设置选举状态，退出选举过程。

3.2.2 数据同步

完成Leader选举后，在正式开始工作前，Leader服务器首先会确认日志中的所有Proposal是否都已经被集群中的过半机器提交了，即是否完成了数据同步。

基于上文讲到的两种情况，数据同步会有不同的处理：

  • 同步事务的提交：
    • leader为每一个follower都准备一个队列，并将那些没有被各follower同步的事务以proposal消息的形式逐个发送给follower，并在每个proposal消息后面紧跟一个commit消息表示该事务已经被leader提交。等到某个follower同步了所有之前尚未同步的事务并将其成功应用到本地数据库，leader会将该follower加入到可用follower列表中。
  • 处理丢弃的事务
    • 下面分析ZAB协议如何处理需要丢弃的事务Proposal的，ZXID是一个64位的数字，其中低32位可以看做是一个简单的单调递增的计数器，针对客户端的每一个事务请求，Leader服务器在产生一个新的事务Proposal时，都会对该计数器进行加1操作；而高32位则代表了Leader周期的epoch编号，每当选举产生一个新的Leader时，就会从这个Leader上取出其本地日志中最大事务Proposal的ZXID，并解析出epoch值，然后加1，之后以该编号作为新的epoch，低32位从0来开始生成新的ZXID。
    • ZAB协议通过epoch号来区分Leader周期变化的策略，能够有效地避免不同的Leader服务器错误地使用不同的ZXID编号提出不一样的事务Proposal的异常情况。当一个包含了上一个Leader周期中尚未提交过的事务Proposal的服务器启动时，其肯定无法成为Leader，因为当前集群中一定包含了一个Quorum（过半）集合，该集合中的机器一定包含了更高epoch的事务的Proposal，因此这台机器的事务Proposal并非最高，也就无法成为Leader。
    • 当这台机器以follower身份连上leader之后，leader会根据自己最后被提交的proposal来和这台机器的proposal作比较，发现有不一致的，则以leader为准，明确需要舍弃的事务后，leader会要求该台机器进行回滚操作，回滚到某个被半数机器执行的最新的事务版本。

epoch：可以理解为当前集群所处的年代或者周期，每个leader就像皇帝，都有自己的年号，所以每次改朝换代，leader 变更之后，都会在前一个年代的基础上加 1。这样就算旧的 leader 崩溃恢复之后，也没有人听他的了，因为 follower 只听从当前年代的leader的命令。

4 ZAB和paxos的联系和区别

4.1 联系

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

4.2 区别

  1. Paxos算法中，新选举产生的主进程会进行两个阶段的工作，第一阶段称为读阶段，新的主进程和其他进程通信来收集主进程提出的提议，并将它们提交。第二阶段称为写阶段，当前主进程开始提出自己的提议。
  2. ZAB协议在Paxos基础上添加了同步阶段，此时，新的Leader会确保存在过半的Follower已经提交了之前的Leader周期中的所有事务Proposal。
  3. ZAB协议主要用于构建一个高可用的分布式数据主备系统，而Paxos算法则用于构建一个分布式的一致性状态机系统。
0%