通俗易懂ZooKeeper基本原理

x33g5p2x  于2020-11-02 转载在 Zookeeper  
字(8.7k)|赞(0)|评价(0)|浏览(437)

Zookeeper 最早起源于雅虎研究院的一个研究小组。在当时,研究人员发现,在雅虎内部很多大型系统基本都需要依赖一个类似的系统来进行分布式协调,但是这些系统往往都存在分布式单点问题。所以,雅虎的开发人员就试图开发一个通用的无单点问题的分布式协调框架,以便让开发人员将精力集中在处理业务逻辑上。

关于“ZooKeeper”这个项目的名字,其实也有一段趣闻。在立项初期,考虑到之前内部很多项目都是使用动物的名字来命名的(例如著名的Pig项目),雅虎的工程师希望给这个项目也取一个动物的名字。时任研究院的首席科学家 Raghu Ramakrishnan开玩笑地说:“在这样下去,我们这儿就变成动物园了!”此话一出,大家纷纷表示就叫动物园管理员吧,因为各个以动物命名的分布式组件放在一起,雅虎的整个分布式系统看上去就像一个大型的动物园了。

而 Zookeeper 正好要用来进行分布式环境的协调,于是,Zookeeper的名字也就由此诞生了。在讲述ZooKeeper之前,需要先介绍下Paxos一致性协议。

1、Paxos一致性协议

Paxos 一致性协议可以说是一致性协议研究的起点,也以难以理解闻名。其实协议本身并没有多难理解,它的难理解性主要体现在:为何如此设计协议以及如何证明其正确性

Paxos 可以分为两种:

(1)Single-Decree Paxos:决策单个Value

(2)Multi-Paxos:连续决策多个Value,并且保证每个节点上的顺序完全一致,多Paxos往往是同事运行多个单Paxos协议共同执行的结果。

这里只关注单 Paxos 的原理,理解了单Paxos,多Paxos也就不难理解了。

A、Paxos 协议中的三种角色

(1)倡议者(Proposer):倡议者可以提出提议(数值或者操作命令)以供投票表决

(2)接受者(Acceptor):接受者可以对倡议者提出的提议进行投票表决,提议有超半数的接受者投票即被选中

(3)学习者(Learner):学习者无投票权,只是从接受者那里获知哪个提议被选中。

在协议中,每个节点可以同时扮演以上多个角色。

B、Paxos 的特点

(1)一个或多个节点可以提出提议;

(2)系统必须针对所有提案中的某个提案达成一致(超过半数的接受者选中);

(3)最多只能对一个确定的提议达成一致;

(4)只要超半数的节点存活且可互相通信,整个系统一定能达成一致状态,即选择一个确定的提议。

C、协议图示

通过上面的流程,如果有多个节点同时提出各自的提议,Paxos 就可以保证从中选出一个唯一确定的值,保证分布式系统的一致性。

D、Paxos实例

下面通过例子来理解 Paxos 的实际应用过程。假设现在有五个节点的分布式系统,此时A节点打算提议X值,E节点打算提议Y值,其他节点没有提议。

假设现在 A 节点广播它的提议(也会发送给自己),由于网络延迟的原因,只有A,B,C节点收到了。注意即使A,E节点的提议同时到达某个节点,它也必然有个先后处理的顺序,这里的“同时”不是真正意义上的“同时”。

A,B,C接收提议之后,由于这是第一个它们接收到的提议,acceptedProposal和acceptedValue都为空。

由于 A 节点已经收到超半数的节点响应,且返回的acceptedValue都为空,也就是说它可以用X作为提议的值来发送Accept 请求,A,B,C接收到请求之后,将acceptedValue更新为X。

A,B,C会发送 minProposal 给A,A检查发现没有大于1的minProposal出现,此时X已经被选中。等等,是不是忘了D,E节点?它们的acceptedValue并不是X,系统还处于不一致状态。至此,Paxos过程还没有结束,继续看。

此时 E 节点选择Proposal ID为2发送Prepare请求,结果就和上面不一样了,因为C节点已经接受了A节点的提议,它不会三心二意,所以就告诉E节点它的选择,E节点也很绅士,既然C选择了A的提议,那我也选它吧。于是,E发起Accept请求,使用X作为提议值,至此,整个分布式系统达成了一致,大家都选择了X。

上面是 Paxos 的一个简单应用过程,其他复杂的场景也可以根据流程图慢慢推导,这里只是抛砖引玉。

2、ZooKeeper Leader选举

Leader在集群中是非常重要的一个角色,负责了整个事务的处理和调度,保证分布式数据一致性的关键所在。既然Leader在ZooKeeper集群中这么重要,所以一定要保证集群在任何时候都有且仅有一个Leader存在。

如果集群中Leader不可用了,需要有一个机制来保证能从集群中找出一个最优的服务晋升为Leader继续处理事务和调度等一系列职责,这个过程称为Leader选举。

A、选举机制

ZooKeeper选举Leader依赖下列原则并遵循优先顺序:

**(1)**选举投票必须在同一轮次中进行

如果Follower服务选举轮次不同,不会采纳投票。

**(2)**数据最新的节点优先成为Leader

数据的新旧使用事务ID判定,事务ID越大认为节点数据越接近Leader的数据,自然应该成为Leader。

**(3)**比较server.id,id值大的优先成为Leader

如果每个参与竞选节点的事务ID一样,再使用server.id做比较。server.id是节点在集群中唯一的id,myid文件中进行配置。

不管是在集群启动时选举Leader还是集群运行中重新选举Leader,集群中每个Follower角色服务都是以上面的条件作为基础推选出合适的Leader,一旦出现某个节点被过半推选,那么该节点晋升为Leader。

**B、过半原则 **

ZooKeeper集群会有很多类型投票。Leader选举投票;事务提议投票;这些投票依赖过半原则。就是说ZooKeeper认为投票结果超过了集群总数的一半,便可以安全的处理后续事务。

**(1)**事务提议投票

假设有3个节点组成ZooKeeper集群,客户端请求添加一个节点。Leader接到该事务请求后给所有Follower发起「创建节点」的提议投票。如果Leader收到了超过集群一半数量的反馈,继续给所有Follower发起commit。此时Leader认为集群过半了,就算自己挂了集群也是安全可靠的。

**(2)**Leader选举投票

假设有3个节点组成ZooKeeper集群,这时Leader挂了,需要投票选举新Leader。当相同投票结果过半后Leader选出。

**(3)**集群可用节点

ZooKeeper集群中每个节点有自己的角色,对于集群可用性来说必须满足过半原则。这个过半是指Leader角色+ Follower角色可用数大于集群中Leader角色+ Follower角色总数/2。假设有5个节点组成ZooKeeper集群,一个Leader、两个Follower、两个Observer。当挂掉两个Follower或挂掉一个Leader和一个Follower时集群将不可用。因为Observer角色不参与任何形式的投票。

所谓过半原则算法是说票数 > 集群总节点数/2。其中集群总节点数/2的计算结果会向下取整。在ZooKeeper源代码QuorumMaj.java中实现了这个算法。下面代码片段有所缩减。

public boolean containsQuorum(HashSet<Long> set) {

  /// n是指集群总数/*/

  int half = n / 2;

  return (set.size() > half);

}

所以3节点和4节点组成的集群在ZooKeeper过半原则下都最多只能挂1节点,但是4比3要多浪费一个节点资源。

C、Leader选举场景实战

以两个场景来了解集群不可用时Leader重新选举的过程.

I、3节点集群重选Leader

假设有3节点组成的集群,分别是server.1(Follower)、server.2(Leader)、server.3(Follower)。此时server.2不可用了。集群会产生以下变化:

**(1)**集群不可用

因为Leader挂了,集群不可用于事务请求了。

**(2)**状态变更

所有Follower节点变更自身状态为LOOKING,并且变更自身投票。投票内容就是自己节点的事务ID和server.id。以(事务ID, server.id)表示。假设server.1的事务id是10,变更的自身投票就是(10, 1);server.3的事务id是8,变更的自身投票就是(8, 3)。

**(3)**首轮投票

将变更的投票发给集群中所有的Follower节点。server.1将(10, 1)发给集群中所有Follower,包括它自己。server.3也一样,将(8, 3)发给所有Follower。所以server.1将收到(10, 1)和(8, 3)两个投票,server.3将收到(8, 3)和(10, 1)两个投票。

**(4)**投票PK

每个Follower节点除了发起投票外,还接收其他Follower发来的投票,并与自己的投票PK(比较两个提议的事务ID以及server.id),PK结果决定是否要变更自身状态并再次投票。

对于server.1来说收到(10, 1)和(8, 3)两个投票,与自己变更的投票比较后没有一个比自身投票(10, 1)要大的,所以server.1维持自身投票不变。对于server.3来说收到(10, 1)和(8, 3)两个投票,与自身变更的投票比较后认为server.1发来的投票要比自身的投票大,所以server.3会变更自身投票并将变更后的投票发给集群中所有Follower。

**(5)**第二轮投票

server.3将自身投票变更为(10, 1)后再次将投票发给集群中所有Follower。对于server.1来说在第二轮收到了(10, 1)投票,server.1经过PK后继续维持不变。对于server.3来说在第二轮收到了(10, 1)投票,因为server.3自身已变更为(10, 3)投票,所以本次也维持不变。此时server.1和server.3在投票上达成一致。

**(6)**投票接收桶

节点接收的投票存储在一个接收桶里,每个Follower的投票结果在桶内只记录一次。ZooKeeper源码中接收桶用Map实现。

下面代码片段是ZooKeeper定义的接收桶,以及向桶内写入数据。Map.Key是Long类型,用来存储投票来源节点的server.id,Vote则是对应节点的投票信息。节点收到投票后会更新这个接收桶,也就是说桶里存储了所有Follower节点的投票并且仅存最后一次的投票结果。

HashMap<Long, Vote> recvset = new HashMap<Long, Vote>();

recvset.put(n.sid, new Vote(n.leader, n.zxid, n.electionEpoch, n.peerEpoch));

**(7)**统计投票

接收到投票后每次都会尝试统计投票,投票统计过半后选举成功。投票统计的数据来源于投票接收桶里的投票数据,从头描述这个场景,来看一下接收桶里的数据变化情况。server.2挂了后,server.1和server.3发起第一轮投票。server.1接收到来自server.1的(10, 1)投票和来自server.3的(8, 3)投票。server.3同样接收到来自server.1的(10, 1)投票和来自server.3的(8, 3)投票。此时server.1和server.3接收桶里的数据是这样的:

server.3经过PK后认为server.1的选票比自己要大,所以变更了自己的投票并重新发起投票。server.1收到了来自server.3的(10, 1)投票;server.3收到了来自sever.3的(10, 1)投票。此时server.1和server.3接收桶里的数据变成了这样:

基于ZooKeeper过半原则:桶内投票选举server.1作为Leader出现2次,满足了过半2 > 3/2即2>1。最后sever.1节点晋升为Leader,server.3变更为Follower。

****II、集群扩容Leader启动时机

ZooKeeper集群扩容需要在zoo.cfg配置文件中加入新节点。扩容流程在ZooKeeper扩容中介绍。这里以3节点扩容到5节点时,Leader启动时机做一个讨论。假设目前有3个节点组成集群,分别是server.1(Follower)、server.2(Leader)、server.3(Follower),假设集群中节点事务ID相同。配置文件如下。

server.1=localhost:2881:3881

server.2=localhost:2882:3882

server.3=localhost:2883:3883

**(1)**新节点加入集群

集群中新增server.4和server.5两个节点,首先修改server.4和server.5的zoo.cfg配置并启动。节点4和5在启动后会变更自身投票状态,发起一轮Leader选举投票。server.1、server.2、server.3收到投票后由于集群中已有选定Leader,所以会直接反馈server.4和server.5投票结果:server.2是Leader。server.4和server.5收到投票后基于过半原则认定server.2是Leader,自身便切换为Follower。

/#节点server.1、server.2、server.3配置

server.1=localhost:2881:3881

server.2=localhost:2882:3882

server.3=localhost:2883:3883

 

/#节点server.4、server.5配置

server.1=localhost:2881:3881

server.2=localhost:2882:3882

server.3=localhost:2883:3883

server.4=localhost:2884:3884

server.5=localhost:2885:3885

**(2)**停止Leader

server.4和server.5的加入需要修改集群server.1、server.2、server.3的zoo.cfg配置并重启。但是Leader节点何时重启是有讲究的,因为Leader重启会导致集群中Follower发起Leader重新选举。在server.4和server.5两个新节点正常加入后,集群不会因为新节点加入变更Leader,所以目前server.2依然是Leader。

以一个错误的顺序启动,看一下集群会发生什么样的变化。修改server.2 zoo.cfg配置文件,增加server.4和server.5的配置并停止server.2服务。停止server.2后,Leader不存在了,集群中所有Follower会发起投票。当server.1和server.3发起投票时并不会将投票发给server.4和server.5,因为在server.1和server.3的集群配置中不包含server.4和server.5节点。相反,server.4和server.5会把选票发给集群中所有节点。也就是说对于server.1和server.3他们认为集群中只有3个节点。对于server.4和server.5他们认为集群中有5个节点。

根据过半原则,server.1和server.3很快会选出一个新Leader,这里假设server.3晋级成为了新Leader。但是没有启动server.2的情况下,因为投票不满足过半原则,server.4和server.5会一直做投票选举Leader的动作。截止到现在集群中节点状态是这样的:

**(3)**启动Leader

现在,启动server.2。因为server.2 zoo.cfg已经是server.1到serverv.5的全量配置,在server.2启动后会发起选举投票,同时serverv.4和serverv.5也在不断的发起选举投票。当server.2的选举轮次和serverv.4与serverv.5选举轮次对齐后,最终server.2会变更自己的状态,认定server.5是Leader。意想不到的事情发生了,出现两个Leader:

ZooKeeper集群扩容时,如果Leader节点最后启动就可以避免这类问题发生,因为在Leader节点重启前,所有的Follower节点zoo.cfg配置已经是相同的,他们基于同一个集群配置两两互联,做投票选举。

3、ZooKeeper分布式锁机制

 一起来看看多客户端获取及释放zk分布式锁的整个流程及背后的原理。见下图,如果现在有两个客户端一起要争抢zk上的一把分布式锁,会是个什么场景?

zk里有一把锁,这个锁就是zk上的一个节点。然后呢,两个客户端都要来获取这个锁,具体是怎么来获取呢?假设客户端A抢先一步,对zk发起了加分布式锁的请求,这个加锁请求是用到了zk中的一个特殊的概念,叫做**“临时顺序节点”。**简单来说,就是直接在"my_lock"这个锁节点下,创建一个顺序节点,这个顺序节点有zk内部自行维护的一个节点序号。比如说,第一个客户端来创建一个顺序节点,zk内部会给起个名字叫做:xxx-000001。然后第二个客户端来创建一个顺序节点,zk可能会起个名字叫做:xxx-000002。注意一下,最后一个数字都是依次递增的,从1开始逐次递增。zk会维护这个顺序。所以这个时候,假如说客户端A先发起请求,就会先创建出来一个顺序节点,看下面的图,Curator框架大概会弄成如下的样子:

客户端A发起一个加锁请求,先会在要加锁的node下创建一个临时顺序节点,这一大坨长长的名字都是Curator框架自己生成出来的。然后,那个最后一个数字是"1"。注意一下,因为客户端A是第一个发起请求的,所以给他创建出来的顺序节点的序号是"1"。接着客户端A创建完一个顺序节点,还没完,他会查一下"my_lock"这个锁节点下的所有子节点,并且这些子节点是按照序号排序的,这个时候他大概会拿到这么一个集合:

接着客户端A会走一个关键性的判断,就是说:唉!兄弟,这个集合里,我创建的那个顺序节点,是不是排在第一个啊?如果是的话,那我就可以加锁了啊!因为明明我就是第一个来创建顺序节点的人,所以我就是第一个尝试加分布式锁的人啊!bingo!加锁成功!看下面的图,直观感受一下整个过程。

接着假如说,客户端A都加完锁了,客户端B过来想要加锁了,这个时候他会干一样的事儿:先是在"my_lock"这个锁节点下创建一个临时顺序节点,此时名字会变成类似于:

看看下面的图:

客户端B因为是第二个来创建顺序节点的,所以zk内部会维护序号为"2"。接着客户端B会走加锁判断逻辑,查询"my_lock"锁节点下的所有子节点,按序号顺序排列,此时他看到的类似于:

同时检查自己创建的顺序节点,是不是集合中的第一个?明显不是啊,此时第一个是客户端A创建的那个顺序节点,序号为"01"的那个。所以加锁失败!加锁失败以后,客户端B就会通过ZK的API,对他的上一个顺序节点加一个监听器。zk天然就可以实现对某个节点的监听。

举例说明,客户端B的顺序节点是

他的上一个顺序节点,不就是下面这个吗?

也就是客户端A创建的那个顺序节点!所以,客户端B会对:

这个节点加一个监听器,监听这个节点是否被删除等变化!说了那么多,来一张图,直观的感受一下:

接着,客户端A加锁之后,可能处理了一些代码逻辑,然后就会释放锁。那么,释放锁是个什么过程呢?其实很简单,就是把自己在zk里创建的那个顺序节点,也就是:

这个节点给删除。删除了那个节点之后,zk会负责通知监听这个节点的监听器,也就是客户端B之前加的那个监听器,说:兄弟,你监听的那个节点被删除了,有人释放了锁。看看下面的图,体会一下这个过程:

此时客户端B的监听器感知到了上一个顺序节点被删除,也就是排在他之前的某个客户端释放了锁。此时,就会通知客户端B重新尝试去获取锁,也就是获取"my_lock"节点下的子节点集合,此时为:

集合里此时只有客户端B创建的唯一的一个顺序节点了!然后呢,客户端B一判断,发现自己居然是集合中的第一个顺序节点,bingo!可以加锁了!直接完成加锁,运行后续的业务代码即可,运行完了之后再次释放锁。最后,来一张图,顺着图仔细的捋一捋这整个过程:

其实如果有客户端C、客户端D等N个客户端争抢一个zk分布式锁,原理都是类似的。大家都是上来直接创建一个锁节点下的一个接一个的临时顺序节点,如果自己不是第一个节点,就对自己上一个节点加监听器,只要上一个节点释放锁,自己就排到前面去了,相当于是一个排队机制。而且用临时顺序节点的另外一个用意就是,如果某个客户端创建临时顺序节点之后,不小心自己宕机了也没关系,zk感知到那个客户端宕机,会自动删除对应的临时顺序节点,相当于自动释放锁,或者是自动取消自己的排队。最后,来看下用Curator框架进行加锁和释放锁的一个过程:

相关文章

热门文章

更多