zookeeper的选举和数据一致性-ZAB协议

x33g5p2x  于2021-03-14 发布在 Zookeeper  
字(6.3k)|赞(0)|评价(0)|浏览(453)

1. ZAB协议简介

ZAB ( ZooKeeper Atomic Broadcast , ZooKeeper 原子消息广播协议)是zookeeper数据一致性的核心算法。

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

2.ZAB协议的四个阶段

ZAB 中的节点有三种状态

  • following:当前节点是跟随者,服从 leader 节点的命令
  • leading:当前节点是 leader,负责协调事务
  • election/looking:节点处于选举状态

代码实现中多了一种:observing 状态,这是 Zookeeper 引入 Observer 之后加入的,Observer 不参与选举,是只读节点,跟 ZAB 协议没有关系

节点的持久状态

  • history:当前节点接收到事务提议的 log
  • acceptedEpoch:follower 已经接受的 leader 更改年号的 NEWEPOCH 提议
  • currentEpoch:当前所处的年代
  • lastZxid:history 中最近接收到的提议的 zxid (最大的)
Zxid:在 ZAB 协议的事务编号 Zxid 设计中,Zxid 是一个 64 位的数字,其中低 32 位是一个简单的单调递增的计数
器,针对客户端每一个事务请求,计数器加 1;而高 32 位则代表 Leader 周期 epoch 的编号,每个当选产生一个新的 
Leader 服务器,就会从这个 Leader 服务器上取出其本地日志中最大事务的ZXID,并从中读取 epoch 值,然后加 1,
以此作为新的 epoch,并将低 32 位从 0 开始计数。

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

Phase 0: Leader election(选举阶段)

节点在一开始都处于选举阶段,只要有一个节点得到超半数节点的票数,它就可以当选准 leader。只有到达 Phase 3 准 leader 才会成为真正的 leader。这一阶段的目的是就是为了选出一个准 leader,然后进入下一个阶段。

协议并没有规定详细的选举算法,后面我们会提到实现中使用的 Fast Leader Election。

Phase 1: Discovery(发现阶段)

在这个阶段,followers 跟准 leader 进行通信,同步 followers 最近接收的事务提议。这个一阶段的主要目的是发现当前大多数节点接收的最新提议,并且准 leader 生成新的 epoch,让 followers 接受,更新它们的 acceptedEpoch。

一个 follower 只会连接一个 leader,如果有一个节点 f 认为另一个 follower p 是 leader,f 在尝试连接 p 时会被拒绝,f 被拒绝之后,就会进入 Phase 0。

Phase 2: Synchronization(同步阶段)

同步阶段主要是利用 leader 前一阶段获得的最新提议历史,同步集群中所有的副本。只有当 quorum 都同步完成,准 leader 才会成为真正的 leader。follower 只会接收 zxid 比自己的 lastZxid 大的提议。

Phase 3: Broadcast(广播阶段)

到了这个阶段,Zookeeper 集群才能正式对外提供事务服务,并且 leader 可以进行消息广播。同时如果有新的节点加入,还需要对新节点进行同步。

值得注意的是,ZAB 提交事务并不像 2PC 一样需要全部 follower 都 ACK,只需要得到 quorum (超过半数的节点)的 ACK 就可以了。

3.ZAB协议的实现

协议的 Java 版本实现跟上面的定义有些不同,选举阶段使用的是 Fast Leader Election(FLE),它包含了 Phase 1 的发现职责。因为 FLE 会选举拥有最新提议历史的节点作为 leader,这样就省去了发现最新提议的步骤。实际的实现将 Phase 1 和 Phase 2 合并为 Recovery Phase(恢复阶段)。所以,ZAB 的实现只有三个阶段:

  • Fast Leader Election
  • Recovery Phase
  • Broadcast Phase

Fast Leader Election

前面提到 FLE 会选举拥有最新提议历史(lastZixd最大)的节点作为 leader,这样就省去了发现最新提议的步骤。这是基于拥有最新提议的节点也有最新提交记录的前提。

成为 leader 的条件

  • 选epoch最大的
  • epoch相等,选 zxid 最大的(表示数据最新)
  • epoch和zxid都相等,选择server id最大的(就是我们配置zoo.cfg中的myid)

节点在选举开始都默认投票给自己,当接收其他节点的选票时,会根据上面的条件更改自己的选票并重新发送选票给其他节点,当有一个节点的得票超过半数,该节点会设置自己的状态为 leading,其他节点会设置自己的状态为 following。

Leader选举概述

  Leader选举是保证分布式数据一致性的关键所在。当Zookeeper集群中的一台服务器出现以下两种情况之一时,需要进入Leader选举。

  (1) 服务器初始化启动。

  (2) 服务器运行期间无法和Leader保持连接(运行期间,leader出现故障)。

  下面就两种情况进行分析讲解。

a. 服务器启动时期的Leader选举

  若进行Leader选举,则至少需要两台机器,这里选取3台机器组成的服务器集群为例。在集群初始化阶段,当有一台服务器Server1启动时,其单独无法进行和完成Leader选举,当第二台服务器Server2启动时,此时两台机器可以相互通信,每台机器都试图找到Leader,于是进入Leader选举过程。选举过程如下

(1) 每个Server发出一个投票。由于是初始情况,Server1和Server2都会将自己作为Leader服务器来进行投票,每次投票会包含所推举的服务器的myid和ZXID,使用(myid, ZXID)来表示,此时Server1的投票为(1, 0),Server2的投票为(2, 0),然后各自将这个投票发给集群中其他机器。

(2) 接受来自各个服务器的投票。集群的每个服务器收到投票后,首先判断该投票的有效性,如检查是否是本轮投票、是否来自LOOKING状态的服务器。

(3) 处理投票。针对每一个投票,服务器都需要将别人的投票和自己的投票进行PK,PK规则如下

  • 优先检查ZXID。ZXID比较大的服务器优先作为Leader。
  • 如果ZXID相同,那么就比较myid。myid较大的服务器作为Leader服务器。

对于Server1而言,它的投票是(1, 0),接收Server2的投票为(2, 0),首先会比较两者的ZXID,均为0,再比较myid,此时Server2的myid最大,于是更新自己的投票为(2, 0),然后重新投票,对于Server2而言,其无须更新自己的投票,只是再次向集群中所有机器发出上一次投票信息即可。

(4) 统计投票。每次投票后,服务器都会统计投票信息,判断是否已经有过半机器接受到相同的投票信息,对于Server1、Server2而言,都统计出集群中已经有两台机器接受了(2, 0)的投票信息,此时便认为已经选出了Leader。

(5) 改变服务器状态。一旦确定了Leader,每个服务器就会更新自己的状态,如果是Follower,那么就变更为FOLLOWING,如果是Leader,就变更为LEADING。

b. 服务器运行时期的Leader选举

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

(1) 变更状态。Leader挂后,余下的非Observer服务器都会讲自己的服务器状态变更为LOOKING,然后开始进入Leader选举过程。

(2) 每个Server会发出一个投票。在运行期间,每个服务器上的ZXID可能不同,此时假定Server1的ZXID为123,Server3的ZXID为122;在第一轮投票中,Server1和Server3都会投自己,产生投票(1, 123),(3, 122),然后各自将投票发送给集群中所有机器。

(3) 接收来自各个服务器的投票。与启动时过程相同。

(4) 处理投票。与启动时过程相同,此时,Server1将会成为Leader。

(5) 统计投票。与启动时过程相同。

(6) 改变服务器的状态。与启动时过程相同。

Leader选举算法分析

在3.4.0后的Zookeeper的版本只保留了TCP版本的FastLeaderElection选举算法。当一台机器进入Leader选举时,当前集群可能会处于以下两种状态

  • 集群中已经存在Leader。
  • 集群中不存在Leader。

对于集群中已经存在Leader而言,此种情况一般都是某台机器启动得较晚,在其启动之前,集群已经在正常工作,对这种情况,该机器试图去选举Leader时,会被告知当前服务器的Leader信息,对于该机器而言,仅仅需要和Leader机器建立起连接,并进行状态同步即可。而在集群中不存在Leader情况下则会相对复杂,其步骤如下

(1) 第一次投票。无论哪种导致进行Leader选举,集群的所有机器都处于试图选举出一个Leader的状态,即LOOKING状态,LOOKING机器会向所有其他机器发送消息,该消息称为投票。投票中包含了SID(服务器的唯一标识)和ZXID(事务ID),(SID, ZXID)形式来标识一次投票信息。假定Zookeeper由5台机器组成,SID分别为1、2、3、4、5,ZXID分别为9、9、9、8、8,并且此时SID为2的机器是Leader机器,某一时刻,1、2所在机器出现故障,因此集群开始进行Leader选举。在第一次投票时,每台机器都会将自己作为投票对象,于是SID为3、4、5的机器投票情况分别为(3, 9),(4, 8), (5, 8)。

(2) 变更投票。每台机器发出投票后,也会收到其他机器的投票,每台机器会根据一定规则来处理收到的其他机器的投票,并以此来决定是否需要变更自己的投票,这个规则也是整个Leader选举算法的核心所在,其中术语描述如下

  • vote_sid:接收到的投票中所推举Leader服务器的SID。

  • vote_zxid:接收到的投票中所推举Leader服务器的ZXID。

  • self_sid:当前服务器自己的SID。

  • self_zxid:当前服务器自己的ZXID。

  每次对收到的投票的处理,都是对(vote_sid, vote_zxid)和(self_sid, self_zxid)对比的过程。

规则一:如果vote_zxid大于self_zxid,就认可当前收到的投票,并再次将该投票发送出去。
规则二:如果vote_zxid小于self_zxid,那么坚持自己的投票,不做任何变更。
规则三:如果vote_zxid等于self_zxid,那么就对比两者的SID,如果vote_sid大于self_sid,那么就认可当
前收到的投票,并再次将该投票发送出去。
规则四:如果vote_zxid等于self_zxid,并且vote_sid小于self_sid,那么坚持自己的投票,不做任何变更。

  结合上面规则,给出下面的集群变更过程。

(3) 确定Leader。经过第二轮投票后,集群中的每台机器都会再次接收到其他机器的投票,然后开始统计投票,如果一台机器收到了超过半数的相同投票,那么这个投票对应的SID机器即为Leader。此时Server3将成为Leader。

  由上面规则可知,通常那台服务器上的数据越新(ZXID会越大),其成为Leader的可能性越大,也就越能够保证数据的恢复。如果ZXID相同,则SID越大机会越大。

Recovery Phase

同步时机:当leader完成选举后,follower需要与新的leader同步数据
同步准备-leader

  • leader会告诉其他的follower当前最新的数据是什么,即zxid
  • leader会给每一个follower创建一个线程LearnerHandler来处理每一个follower的同步请求,同时leader阻塞,直到超过半数的follower完成同步,同步过程才算完成,leader才成为真正的leader。

同步准备-follower

  • 选举完成后,follower尝试与leader建立同步连接,如果一段时间没有连接上则报错超时,并重新选举。
  • 向leader发送followerinfo包,带上follower自己最大的zxid。

同步算法

  • 直接差异化同步(DIFF同步)
  • 仅回滚同步(Trunc同步),即删除多余的事务日志。宕机的leader又重新加入集群,可能存在自己写入提交,而其他的follower还没来的及提交的事务日志
  • 先回滚再差异化同步(Trunc + DIFF同步)
  • 全量同步(SNAP同步)

同步举例:

场景一:minCommittingZxid<peerLastZxid<maxCommittingZxid

peerLastZxid:follower最后的事务id
minCommittingZxid:最小的事务日志id
maxCommittingZxid:最大的事务日志id

同步方案:直接差异化同步

  • leader会给follower发送DIFF指令,进入差异化同步过程
  • leader先发送一个数据修改的proposal,然后再发送commit

Broadcast Phase

广播流程

  • 集群选举完成,并且完成数据同步后,即可开始对外提供服务,接收读写请求
  • 当leader接收到客户端新的事务请求后,会生成对应的事务proposal,并根据zxid的排序向所有的follower发送提案,即proposal
  • 当follower收到leader的proposal时,根据接收的先后顺序处理这些proposal,即如果先后收到1,2,3条,则如果处理完了第3条,则代表1,2两条一定已经处理成功
  • 当Leader收到follower针对某个事务proposal过半的ack后,则发起事务提交,重新发起一个commit的proposal
  • Follower收到commit的proposal后,记录事务提交,并把数据更新到内存数据

参考资料

  1. https://www.cnblogs.com/longxok/p/8951867.html
  2. http://blog.xiaohansong.com/2016/08/25/zab/
  3. 炼数成金 http://edu.dataguru.cn

相关文章