一文通吃:从 ZooKeeper 一致性,Leader选举讲到 ZAB 协议与 PAXOS 算法(上)

目录

一、ZooKeeper集群保证数据一致性
    (一)一致性
    (二)zookeeper保证数据一致性的协议
二、Zookeeper集群Leader选举
    (一)ZooKeeper集群中三种类型的节点
    (二)ZAB 中的节点有四种状态
    (三)Leader选举过程
三、ZAB协议
    (一)ZAB 协议 ZXID 是如何生成的
    (二)ZAB协议——崩溃恢复模式
    (三)ZAB协议——消息广播模式
四、Paxos算法
    (一)关于ZAB协议中Leader的单点问题
    (二)Paxos是什么
    (三)问题背景
    (四)相关概念
    (五)Paxos算法处理过程
    (六)总结:Paxos算法

本文将从ZooKeeper集群如何保证一致性,讲到zookeeper保证数据一致性的协议,然后展开讲Zookeeper集群Leader选举,包括集群三种节点的类型,ZAB协议中节点的四种状态,以及两种情况下Leader选举的过程。然后会详细展开讲解ZAB协议,包括ZAB协议中ZXID的结构,ZAB协议的两个重点,崩溃恢复模式和消息广播模式。然后会通过一个例子来说明ZAB协议中Leader的单点问题,进而引出Paxos算法。文章会分为上下两个篇章,本文为第一部分。

ZooKeeper集群保证数据一致性

首先我们先来了解一下,关于一致性问题。

一致性

我们用集群是为了提高整个系统的可用性,就是即使少数节点挂掉的话,整个集群还是可以去提供服务的。好,zookeeper集群每一个节点上面,它存储的数据都是全量的数据,也就是它们之间,每一台上面存储的数据都是同一份数据,而我们前面也提到,集群中它每个节点都可以去提供读取服务,所以这样的话,就得保证多个节点之间,它们的数据是一致的,才不会出现连接不同节点读取到不同的值是吧,也就是我们需要去保证集群节点间数据的一致性。那么接下来我们就来看一下,zookeeper集群是如何去做到这一点的,就是如何去做节点间数据的同步

zookeeper保证数据一致性的协议

而在我们的zookeeper中保证数据一致性用的是ZAB协议。通过这个协议来进行ZooKeeper集群间的数据同步,保证数据的一致性。

我们先来简单看一下zab协议是工作流程(图):

https://img3.sycdn.imooc.com/62921073000189ff14520648.jpg

ZooKeeper写数据的机制是客户端把写请求发送到leader节点上,如果发送的是follower节点,follower节点会把写请求转发到leader节点,leader节点会把数据通过proposal请求发送到所有节点,包括自己,所有到节点接受到数据以后都会写到自己到本地磁盘上面,写好了以后会发送一个ack请求给leader,leader只要接受到过半的节点发送ack响应回来,就会发送commit消息给各个节点,各个节点就会把消息放入到内存中,放内存是为了保证高性能,该消息就会用户可见了。

那这个时候,若ZooKeeper要想保证数据一致性,就需考虑如下两个情况

  • 情况一:leader执行commit了,还没来得及给follower发送commit的时候,leader宕机了,这个时候如何保证消息一致性?

  • 情况二:leader的事务性请求已经在部分节点应用了,这个时候leader挂掉了,如何保证消息一致性?

如果是Leader故障,事务型请求未提交的情况,也就是只在Leader服务器上提出但没有提交的操作的操作需要丢弃掉。因为实际上它只是完成了第一阶段。

https://img1.sycdn.imooc.com/6292108900013b2615180604.jpg

Leader故障,事务型请求已提交的情况,也就是已在Leader服务器上提交的操作最终被所有的服务器节点都提交。等后面讲到ZAB协议,概念就更清晰了,在某个节点提交应用成功,那这个节点的zxid肯定更大,决定它会被选举为新的leader。然后再进行同步。

https://img1.sycdn.imooc.com/629210a0000183f814980586.jpg

Zookeeper集群Leader选举

ZooKeeper集群中三种类型的节点

集群在运行过程中,节点发生故障时,这个集群是如何来应对的?

ZooKeeper中三种类型的节点是吧,我们逐个类型来看一下:

https://img3.sycdn.imooc.com/629210b40001e50719180956.jpg

  • Observer节点,这种节点它只是为了提升读性能,并不会参与到任何决策过程,所以,就算它挂了,也是不会影响集群的正常运行的。

  • Follower节点,如果是少数节点挂了的话,就是没超过半数的话,那也不会影响,那如果故障节点超过半数的话,这个时候就没办法了,需要把节点恢复起来之后才可以运行

  • Leader节点,通过前面的学习我们也知道,这个Leader在整个集群中起着至关重要的作用,整个集群的协调工作都是由它来发起的,所以这个时候假如Leader挂掉了,整个集群也没办法正常运行,就不是有没有超过半数的问题了。

所以当Leader节点挂掉之后,就需要尽快从可用的节点中再来选出一个节点来当新的Leader,才能让集群恢复可用。那这里怎么选新的Leader,就是一个需要解决的问题了。我们想一下,可以简单的从剩下的Follower节点随便选一个来当新的领导吗?我们可以想一下这个场景:Leader故障,事务型请求已提交,在这个场景中,我们这Follower节点的状态明显是不一样的,所以当时我们也说了,这个场景下,ZooKeeper集群是有机制去保证让这个Server1当上新领导的。这里就涉及到了ZooKeeper集群的Leader选举算法了,这个算法对ZooKeeper集群去保证可用性和数据一致性是非常重要的,那么我们就来详细看一下,这个算法它具体是什么样的一个处理过程。

那么在开始分析算法之前,我们先来看一下集群中节点的几种状态,因为整个选举的过程,会涉及到这几个状态的流转。

ZAB 中的节点有四种状态

  • looking:节点处于选举状态

  • following:当前节点是跟随者,服从 leader 节点的命令,后面它是会参与投票的

  • Obsering:观察状态,同步leader状态,但是不参与投票

  • leading:当前节点是 leader,负责协调事务

Leader选举过程

好,接下来我们来看一下Leader的选举过程,那么对于Zookeeper集群来说,当出现以下两种情况的时候,就需要进行Leader选举:

  1. 集群启动期间Leader选举

  2. 集群运行期间Leader故障

然后整个Leader选举的过程,就是一个投票的过程,然后当某一个节点,它接收到超过半数节点的选票的话,就可以认为它当选Leader了。但是这里要投给谁,其实还是有讲究的。

那么我们可以想一下比如我们在选村长的时候,一般我们就看谁能力大是吧,谁能力大就投给谁,然后如果能力差不多,可能就会选年纪大一点的,德高望重嘛。好那在ZooKeeper集群选举里面,当一个节点要决定这个选票要投给谁的时候,会根据两个重要的ID来进行判断:

  1. 首先是看事务ID(zxid),哪个服务器上的事务ID最大,就投给哪个。【对应这个场景:Leader故障,事务型请求已提交

  2. 那么当两个节点事务ID一样的话,就会看节点编号,也就是myid里面存的编号,哪个大投给哪个

好有了投票标准之后,就可以来开始选举了,但是选举的时候,可能会有不止一轮的投票,同样跟我们选村长一样一般也会有多轮投票,那这种情况下,前一轮的选票,到下一轮的话,就应该变成无效选票了是吧。

而在ZooKeeper里面,它同样有这个轮次的概念,就是每一次投票它其实是有时间限制的【syncLimit:集群中的follower服务器与leader服务器之间请求和应答之间能容忍的最多心跳数(tickTime的数量)。】,如果当前投出去的票,没有收到反馈,那么在等待一段时间后,就当作超时处理,这个时候就可以发起一下轮的投票,诶但是有可能,上一轮的反馈它是因为网络延迟的问题,这个时候才收到,那么因为现在已经是开始了下一轮了,所以这个也只能当做无效选票处理了。

图:投票响应超时则进入下一轮

https://img1.sycdn.imooc.com/629210bf00011a2116261078.jpg

选举算法

好 有了这些选举的标准和规则之后,就可以来开始选举了,选举算法:

  1. 首先每个节点均发起选举自己为领导者的投票(自己的投给自己);因为刚开始也不知道哪个节点的事务ID最大,所以就先给自己一票再说,接着就给其它节点发消息来拉票,拉票的时候,像在选举的时候一样,拉票的时候就会说自己能力多牛,那么这里也一样,它会把当前节点上最大的事务ID给带过去

  2. 其它节点收到拉票请求时,就会比较发起者的事务ID,是否比自己最新的事务ID大,如果比自己的ID大,那好就给它投一票吧,否则就不投给它了。那如果事务ID相等的话,则比较发起者的服务器编号。这一点呢我们前面也说到过,就像选举的时候,先看一下能力谁强,再看一下谁的年纪大。

  3. 然后经过每一轮的投票之后,就看有没有哪个节点,它获得的票数(含自己的)大于集群的半数,有的话就说明这个节点竞选成功,成为了Leader节点,未超过半数且领导者未选出,则再次发起投票。

集群启动期间Leader选举

我们现在看第一种服务器启动时候对leader选举 我们来看一下这张图

https://img3.sycdn.imooc.com/629210ca0001162a19620986.jpg

假设一个 Zookeeper 集群中有5台服务器,id从1到5编号,并且它们都是最新启动的,没有历史数据

假设服务器依次启动,我们来分析一下选举过程:

服务器1启动

服务器1启动,发起一次选举,服务器1投自己一票,此时服务器1票数一票,不够半数以上,要大于等于3票,选举无法完成。 所以,这个时候对投票结果:服务器1为1票。

服务器1状态保持为LOOKING。

https://img1.sycdn.imooc.com/629210d5000174d919780984.jpg

服务器2启动

服务器2启动,也发起一次选举,服务器1和2分别投自己一票,此时服务器1发现服务器2的服务id比自己大,更改选票投给服务器2。 所以投票结果:服务器1为0票,服务器2为2票。

服务器1,2状态保持LOOKING

https://img4.sycdn.imooc.com/629210df0001f3b919640982.jpg

服务器3启动

服务器3也启动了,同时也发起一次选举,服务器1、2、3先投自己一票,然后因为服务器3的服务器id最大,两者更改选票投给为服务器3;

这时候,投票结果为:服务器1为0票,服务器2为0票,服务器3为3票。此时服务器3的票数已经超过半数,服务器3当选Leader。

服务器1,2更改状态为FOLLOWING,服务器3更改状态为LEADING

https://img1.sycdn.imooc.com/629210e90001c98419600984.jpg

服务器4启动

服务器4启动,也加入进来,发起一次选举,此时服务器1,2,3已经不是LOOKING 状态,不会更改选票信息。交换选票信息结果:服务器3为3票,服务器4为1票。此时服务器4服从多数,更改选票信息为服务器3。

服务器4并更改状态为FOLLOWING。

https://img3.sycdn.imooc.com/629210f30001d79419640980.jpg

服务器5启动

与服务器4一样投票给3,此时服务器3一共5票,服务器5为0票。

服务器5并更改状态为FOLLOWING。

https://img1.sycdn.imooc.com/6292112d00014a1119700982.jpg

最终的结果:

服务器3是 Leader,状态为 LEADING;其余服务器是 Follower,状态为 FOLLOWING。

好,这就是服务器初始化启动时候的选举过程。

服务器运行期间 Leader 故障

那么,我们继续来看一下第二种选举过程,服务器运行期间 Leader 故障。

我们来看一下这个场景:

在 Zookeeper运行期间 Leader 和 follower 各司其职,当有follower 服务器宕机或加入不会影响 Leader,但是一旦 Leader 服务器挂了,那么整个 Zookeeper 集群将暂停对外服务,会触发新一轮的选举。

初始状态下服务器3当选为Leader,假设现在服务器3故障宕机了,此时每个服务器上zxid可能都不一样,server1为10,server2为12,server4为10,server5为10

https://img4.sycdn.imooc.com/629211390001e83b19620992.jpg

运行期选举

运行期选举与初始状态投票过程基本类似,大致可以分为以下几个步骤:

  • 状态变更。Leader 故障后,剩下的follower节点因为跟Leader联系不上了,这个时候它会将自己的服务器状态变更为LOOKING,然后开始进入Leader选举过程。

  • 每个Server会发出投票。

  • 接收来自各个服务器的投票,如果其它服务器的数据比自己的新会改投票。

  • 处理和统计投票,每一轮投票结束后都会统计投票,超过半数即可当选。

  • 改变服务器的状态,宣布当选

好,这里我们以这张图来说明比较好容易理解点:

https://img2.sycdn.imooc.com/629211460001ddea24980806.jpg

1)第一次投票,每台机器都会将票投给自己。

2)接着每台机器都会将自己的投票发给其它机器,如果发现其它机器的zxid比自己大,那么就需要改投票重新投一次。比如server1 收到了三张票,发现server2的xzid为102,pk一下发现自己输了,后面果断改投票选server2为老大,同理,因为从图中很明显看到服务器2点xzxid是最大的,所以最后是服务器2当选leader服务器。

小结

简单来将,通常哪台机器服务器上的数据越新,那么越有可能成为leader,原因也很简单,数据越新,那么它的zxid也就越大,也就越能够保证数据的恢复。如果集群中有几个相同的最大的zxid,那么服务器id较大的服务器成为leader。

作者:|大能老师|,原文链接: http://www.imooc.com/article/325752

文章推荐

ROS基本程序实现

记录:yum Could not resolve host: mirr

3000帧动画图解MySQL为什么需要binlog、redo log和undo log

Spring Boot整合Swagger报错:"this.condition" is null

数仓血缘关系数据的存储与读写

CoaXPress 线缆和接插件的设计要求

Git技法:.gitignore、移除暂存与撤销修改

数仓选型必列入考虑的OLAP列式数据库ClickHouse(上)

RabbitMQ 工作队列

【Java数据结构及算法实战】系列010:Java队列04——链表实现

探讨生产环境下缓存雪崩的几种场景及解决方案

ES安装max number of threads问题