通过《zookeeper知识结构1》了解了zookeeper是什么?为什么使用zookeeper? 以及zookeeper内部数据结构,选举机制
ZAB全称ZooKeeper Atomic Broadcast protocol
ZooKeeper原子广播协议,实现了主备模式下的系统架构,保持集群中各个副本之间的数据同步(数据最新,一致性)
在具体深入zab之前,先搞明白原子广播
原子性好理解,不管是事务的ACID,还是多线程中,都有这个概念;广播也好理解,像系统中常引入消息队列进行消息广播
但两者合在一起,有点犯晕了,广播怎么需要原子性?哪部分操作不可分割呢?
所有事务请求的处理结果在整个集群中所有机器上的应用情况是一致的,也就是说,要么整个集群所有机器都成功应用了某一个事务, 要么就都没应用.
按照上面的解释,原子性体现在所有机器事务一致性,要么都接受广播,要么都不接受;为了更深入理解,从头开始深入一下这个机制的大致流程
在分布式中,这个机制有很多具体实现,比如2PC,3PC,paxos等等
在这个机制介绍前,需要先介绍下分布式中的副本(Replication)
副本简直是处理故障恢复的的万能钥匙
数据副本的收益:
分布式系统采用副本可以获得可扩展性,高性能,可用性,容错性
正常多副本,可以从任何副本请求数据
为了多个副本上的数据同步,一般会加一个dispatche,client请求到dispatche上,dispatche会对请求进行排序,并按同样的顺序分发到各个副本,保持各副本数据一致
此时,dispatche成了系统中的单点,不具备高可用,所以会部署多个dispatch
每个dispatche相互通信,并且每个dispatche都可以分发到各个副本;此时就会出现上图中的并发更新一致性问题,类似于《深入浅出事务》中的第二类更新丢失
在并发操作时,应用本身对于数据的先后都是可以接受的,但在各个副本中的数据必须保持一致,也就是下图中的结果都是可以的
也就是讲,各个dispatche得以相同的顺序进行更新副本
解决并发更新不一致问题,思路就是对请求操作进行排序,按顺序执行
数据更新的过程如下:
在这个模型中,原子广播的逻辑和业务逻辑是分开的。这么做的好处是非常明显的,业务逻辑的实现不再受分布式需求的限制,原子广播的逻辑则不需要考虑业务逻辑的具体需求。独立的原子广播的逻辑可以被重用到很多的分布式的应用上
根据上面的推导,得出一个最简单的原型
dispatche增加一个队列,也可以把它设计成日志文件(顺序追加的文件)或者管道等等,当有请求时,会按顺序存储到队列,但这个队列中的每个位置只能存储一次数据,存储后不能进行更改
当两个client分别发到不同到dispatche上请求,两个dispatche相互同步时,出现了不一致,违背了各个队列的每个位置只能存储一次元素,不能更改的原则
对于并发问题,首先想到就是加锁,对于分布式系统怎么加锁呢?
2PC提供了好的思路
借鉴一下2pc,加锁过程如下:
第一步:加锁
第二步:更新
并发考虑的两个问题:安全性与活跃性
dispatche1与dispatche2分别接收到请求,在第一步加锁时,先给自己队列加锁,再发送加锁指令给其它dispatche
此时,就出现死锁:如dispathe1对自身队列位置1加锁,再发送指令给disptache2的队列位置1加锁,但disptache2的队列位置1被自己锁住了,反之disptache1队列位置1也一样,此时双方进入死锁,永远阻塞
有一种策略,就是给锁增加一个优化级
如图所示,两个dispatche分别接收到请求,p1 p2是各自锁的优先级,p1高于p2
优先级:
比如以dispatche的id作为优先级值,dispatcheId是不同的,也能区分优先级,但这样会出现不平衡,以id大的优先级高,那永远id为大的优先获取锁,加锁成功处理请求
为了更好的均衡各个客户的请求处理,可以采用下面的优先级定义:[数值,dispatcheID]
数值可以由各个dispatche指定,比如所有disptache都原子累加,这样可以保证每个dispathe的均衡,当数值相等时,再比较dispatcheId
故障可能发生在每个阶段,一是加锁阶段,二是数据更新阶段;再细节大概有三种情况:
这个很好解决,通过优先级锁,另的节点发起一个更高优先级操作就可以覆盖先前的记录
解决这个问题,需要加强一下更新操作,之前的更新操作,发送存储指令给各个节点,就结束了
现在不单单发送指令,还需要再广播
也就是节点接受到存储指令,如果节点已经有数据写入,则与数据一起返回;这样当所有节点返回加锁成功后,检查是否有数据返回,如果有数据返回,则将数据放入存储指令,发送给所有节点
需要增加一个“预存储队列”,预写入机制
当dispatche1发生故障时,其它的dispatche的预存储队列中已经存入了数据。其它节点接管dispatche1时,会先重发预存储队列中的数据到所有dispatche
预写入过程可以保证:如果数据被写入了任意的存储队列,那么所有节点的预存储队列都有这个数据
上面的广播机制中,加锁以及预写入都需要所有节点返回成功。如果任意一个节点有故障都会失败。在复杂网络环境下,整个系统很脆弱,不能高可用
因此可以改进为半数以上节点成功回复就可以
大多数派机制下,会带来一些更复杂的中间状态,整个过程:
有了上面的原型,理解其它的具体协议就会轻松很多,在具体实现时,都会看到原型中的概念
ZAB协议是为分布式协调服务 Zookeeper 专门设计的一种支持 崩溃恢复 和 原子广播 协议
ZAB协议定义了选举(election)、发现(discovery)、同步(sync)、广播(Broadcast)四个阶段
根据上面的原型,结合zk的源码,梳理一下源码中对应原型的抽象
这个对象对应着原型中的存储指令,优先级加锁指令
public Vote(long id, long zxid) {
this.id = id;
this.zxid = zxid;
this.electionEpoch = -1;
this.peerEpoch = -1;
this.state = ServerState.LOOKING;
}
id:被推举的Leader的SID
zxid:被推举的Leader事务ID
为了保证事务的顺序一致性,zookeeper 采用了递增的事 务 id 号(zxid)来标识事务。
所有的提议(proposal)都在被提出的时候加上了 zxid。
实现中 zxid 是一个 64 位的数字
它高32 位是 epoch(ZAB 协议通过 epoch 编号来区分 Leader 周期变化的策略)用来标识 leader关系是否改变,每次一个 leader 被选出来,它都会有一个新的epoch=(原来的 epoch+1),标识当前属于那个 leader 的统治时期。
低 32 位用于递增计数
可以想象为中国古代的年号,例如万历十五年,万历是epoch,十五年是id
electionEpoch:逻辑时钟,用来判断多个投票是否在同一轮选举周期中,该值在服务端是一个自增序列,每次进入新一轮的投票后,都会对该值进行加1操作
peerEpoch:被推举的Leader的epoch
electionEpoch和peerEpoch的区别在于,electionEpoch记录的选举的轮次,而peerEpoch则指的是当前leader的任期
state:当前服务器的状态
zk默认的选举算法,为什么需要选举可以参照《zookeeper知识结构1》
electionEpoch和logicalclock的区别在于,electionEpoch指的是发出server的logicalclock,而logicalclock则指的是当前Server所处的选举的轮次
ClientCnxn是ZooKeeper客户端中用于处理网络I/O的一个管理器
在Leader选举的过程中也有类似的角色,那就是QuorumCnxManager——每台服务器启动的时候都会启动一个QuorumCnxManager,负责各台服务器之间的底层Leader选举过程中的网络通信
QuorumCnxManager这个类内部维护了一系列的队列,用于保存接收到的、待发送的消息,以及消息的发送器。
除接收队列以外,这里提到的所有队列都有一个共同点——按SID分组形成队列集合,我们以发送队列为例来说明这个分组的概念。
假设集群中除自身外还有4台机器,那么当前服务器就会为这4台服务器分别创建一个发送队列,互不干扰。
在SendWorker的具体实现中,有一个细节需要我们注意一下:一旦ZooKeeper发现针对当前远程服务器的消息发送队列为空,那么这个时候就需要从lastMessageSent中取出一个最近发送过的消息来进行再次发送。这个细节的处理主要为了解决这样一类分布式问题:接收方在消息接收前,或者是在接收到消息后服务器挂掉了,导致消息尚未被正确处理。那么如此重复发送是否会导致其他问题呢?当然,这里可以放心的一点是,ZooKeeper能够保证接收方在处理消息的时候,会对重复消息进行正确的处理
lastMessageSent接近原型中的预存储队列
以上10个步骤就是FastLeaderElection的核心,其中步骤4-9会经过几轮循环,直到有Leader选举产生。
通过对原子广播原型的理解,更容易理解zab,对于paxos也一样
当然zab还有很多的细节,还能再深入,挖出很多知识点。但只看理论终归有些空洞,下一篇实践一下,详述zk版本分布式锁
Leader选举
分布式系统
由浅入深理解Paxos协议