ZooKeeper(一)

Paxos算法

Basic Paxos

角色介绍

client,系统外部角色,请求发起者,向民众

Propser,接受Client请求,向集群提出提议(propose),并在发送冲突的时候,起到冲突调节的作用,向议员,替民众提出议案

Acceptor,提议投票和接受者,只有在形成发法定人数(Quorum),提议才会被接受,像国会

leaner,提议接受者,备份,对集群一致性没有说明影响,向记录员

分为两大步骤,每一步骤又分为两小步骤

  1. prepare

proposer提出一个提案N,然后向Acceptor的某个超过半数的子集成员发送提案N的prepare请求

  1. promise 如果N大于此Acceptor之前接受的任何提案编号则接受,否则拒绝
  2. Accept 如果大多数人都接受,Proposer发出accept请求,此请求包含提案编号N,以及提案内容
  3. Accepted 如果此时Acceptor在此期间没有收到任何编号大于N的提案,则接受此提案,否则忽略

基本流程

  1. 客户端发起请求到proposer
  2. proposer提出编号为1的提案,交给大多数Acceptor
  3. Acceptor收到prepare进行讨论,得到最大的编号1,反馈给proposer
  4. proposer收到了大部分Acceptor的响应,就会发出请求提案(1,Vn),Vn为最大编号的值,交给Acceptor
  5. 当Acceptor接受到(1,Vn)的请求,只要该Acceptor尚未对更大编号prepare请求做出响应,这个提案就会通过

部分节点失败,但是绝大部分正常

上图在当Acceptor其中有一个节点失败了,但是存活的还是大多数进行了响应,因此后面的流程正常进行

proposer失败

  1. 上图前面两部不变,但是在进行请求Accept的时候,proposer宕机
  2. 此时分布式可用性体现出来,另外一个proposer就会重新发起一个提案2
  3. 然后依次正常执行,最后(2,Vn)提案被选了出来

潜在的问题,就是活锁

正如我们最开始的步骤,第二步

2.promise
如果N大于此Acceptor之前接受的任何提案编号则接受,否则拒绝

当在进行第二步操作的时候,此时又来了一个提案编号是2,则Acceptor就会接受提案2,此时前一次的proposer看到自己的提案被替换了,就会在此提一个提案,编号为3,就这样一次类推,最后造成活锁

当然这个问题也很好解决,就是当第二个提案提出的时候,如果已经有提案了,我们可以等一会,这样当过一会第一个提案可能已经选了出来.

可以发现Basic Paxos有很多问题,难实现,效率低,发生活锁因此提出了优化

Multi Paxos

Leader唯一的propser,所有请求都需要经过此leader

  1. 不管客户端是否有请求,proposer就会发出prepare(N),说我要当leader
  2. 当Acceptor接受到请求之后,就你就当leader吧
  3. 当客户端请求来的时候,就不用再次执行上限操作,此时只有一个leader的proposer,他就是N为领导,他提出提案编号为I,提案内容为Vm
  4. 然后Acceptor收到请求,然后接受这个请求,对应的提案就会被选出来

这样当下次客户端请求的时候,此时领导还没有改变,就会直接提出I+1提案,提案的内容为w,不会产生冲突,然后进行流程选出提案,这样的好处节省了一次RPC请求,且这种算法也简化了角色。如下图

ZAB协议

所有事务请求必须有一个全局唯一的服务器来协调处理,这样的服务器就是leader,其余的其他服务器则成为Follower的服务器,Leader服务器就是负责一个客户端事务请求转换一个事务proposal,并提交proposal分发给其他follower,但其中大部分follower反馈可以的时候,leader服务器就会在再次向所有的Follower服务器分发commit消息,要求其将前一个proposal进行提交

ZAB要解决两个问题,设计两种模式

  • 消息广播,把数据更新到多有follower
  • 崩溃恢复模式,Leader发生崩溃时候,如何恢复

消息广播

消息广播类似一个二阶段提交,但是又不一样,是因为移除了中断逻辑,所有follower服务器要么正常反馈leader提出的事务proposal,要么抛弃leader服务器,同时ZAB协议将二阶段提交中的中断逻辑意味着我们不需要等到多有Folloer的反馈.

  1. leader将客户端的request转化为一个propose
  2. leader为每个Follower准备了一个FIFO队列,并把Proposal发送到队列上
  3. leader接受到大多数Follower反馈
  4. leader向所有follower发送commit

崩溃恢复

上面我们提到了二阶段的优化,移除了中断阶段,只要大多数follower的反馈,因此出现数据不一致的情况,且当leader服务器崩溃或者网络原因导致失去了过半follower的联系,因此崩溃恢复就起到了作用

基本特性

  • ZAB协议需要确保那些已经在leader服务器上提交的事务最终被所有服务提交
  • ZAB协议需要确保丢弃那些只在leader服务器上被提出的事务

leader在ZAB协议中是一个重要角色,正如生活中,部门的领导,如果领导离职了,公司肯定会重新选择一个leader组织,其中这个选择一个领导是一个非常重要的过程。如下过程

既然要当领导,每个人都希望自己是领导,因此就会投票选举,且会每个人都会有一个记录表,来记录这个信息,比如有三个人A,B,C

  1. 成员A告诉BC要成为领导,BC记录下来(A成员广播)
  2. B恢复可以,C恢复不可以
  3. A收到B和C的回复更新自己的记录表
  4. 此时A是2票,B0票,C0票
  5. C也想当领导,而且给自己投了一票
  6. B和A都同意了
  7. C收到了AB的回复,更新记录表
  8. 此时A0票,B0票,C3票,于是C成为领导了

整个选举过程,并且每个人选举,都代表了一个事件,为了保证分布式系统的时间有序性,因此每个事件都分配了一个ZXID,相当一个编号,64位的数字,高32代表了leader周期epoch编号,每当选举产生一个新的leader服务器,就会从这个leader服务器中解析最大事务proposal的ZXID,然后取出高32位的epoch加1,低32为代表一个事务计数器,产生一个事务就会累计1操作。

崩溃恢复基本过程

  1. 选取当前最大的ZXID代表当前事件的最新的
  2. 选举的新的leader把这个事件proposal提交给其他follower节点
  3. follower节点会根据leader的消息进行回退或者数据同步操作,最终目的就是要达到所有节点的数据副本保持一致
1.Leader election(选举阶段):节点在一开始都处于选举阶段,只要有一个节点得到超半数节点的票数,它就可以当选准 leader。
2. Discovery(发现阶段):在这个阶段,followers 跟准 leader 进行通信,同步 followers 最近接收的事务提议。
3. Synchronization(同步阶段):同步阶段主要是利用 leader 前一阶段获得的最新提议历史,同步集群中所有的副本。同步完成之后 准 leader 才会成为真正的 leader。
4. Broadcast(广播阶段):到了这个阶段,Zookeeper 集群才能正式对外提供事务服务,并且 leader 可以进行消息广播。同时如果有新的节点加入,还需要对新节点进行同步。

ZAB和Paxos算法区别

相同点

  • 两者都有类似leader角色,负责协调follower进行
  • Leader都是超过多半数的follower做出正确反馈后,才会将一个提案提交

不同点

  • ZAB协议,每个proposal都包含一个epoch值代表当前的leader周期,paxos中的名字Ballot
  • ZAB用来构建高可用的分布式数据主备系统(zookeeper),Paxos用来构建分布式一致性状态机系统
  • 在paxos算法中,一个新的选举的主进程会进行两个阶段的工作,第一阶段读阶段,这个新的主进程会通知和所有其他进程通信的方式收集上一个主进程提出的提案,第二阶段是写阶段,这阶段开始提交他自己的提案,而ZAB添加了同步阶段,在同步阶段之前,ZAB协议也存在一个和Paxos算法中阶段类似过程的发现阶段,在同步阶段中,新的leader可以确保在过半的follower已经提交了之前leader周期中的所有事务proposal,这个同步阶段,能够有效的保证leader在新的周期提出事务之前,所有的进程都已经完成了对之前所有的事务proposal的提交。

Leader如何选举

server id(sid),服务id,比如有三台服务器,编号分别是1,2,3

zxid:事务id,服务器存放的数据事务id,值越大说明数据越新

Epoch,投票的次数即第几代领导

server状态,LOOKING,竞选状态,FOLLOWING,随从状态,参与投票,OBSERVING,观察状态,不参与投票,leading,领导者状态

首先要明白几个东西,zookeeper节点是根据什么进行比较选举成leader,首先比较的是事物id即zxid(节点越新zxid就越大),如果zxid一样,就比较sid,即集群节点的唯一标识

什么时候进行选举的

  • 服务初始化
  • 服务器运行期间leader宕机

服务器初始化

服务1启动

服务1感觉自己可以当领导,就会投自己一票,不够半数以上,选举无法完成

此时投票结果,服务器1位1票,状态为LOOKING

服务2启动

服务2启动也感觉自己可以,投自己一票,但是和服务1交流得出,服务2的id比较大,因此更改服务1的投票,选择投给了服务2,此时达到了半数,因此此时服务2就变成了leader,同时更改服务1的状态为follower

服务3启动

此时服务1,2,已经不是looking状态了,不会更改投票信息了,且已经有了leader,因此服务4虽然此时投了自己一票,但是和其他服务器交流,然后还是更改了投票给了服务2,然后此时服务3的状态改成了Following

最终服务2成为了leader,其他服务是follower

运行期间leader宕机进行新的leader选举

此时集群leader宕机,

  1. 状态变更,leader故障后,余下的Follower状态变成了Looking,然后进行新的选举
  2. 每个server发出投票
  3. 接受到各个服务器的投票,如果其他服务器的数据比自己的新会改投票
  4. 处理和统计投票,每一轮投票结果都会统计投票,超过半数可当选
  5. 改变服务器的状态,宣布当选

如上图,每个服务器都会先选择自己,然后每个台机器会将自己的投票发给其他机器,如果比自己的zxid大,就会重新投一次,比如server1收到三张偷拍哦,发现server2的zxid为102,因此修改自己的投票,给了server2,最终server2成为了leader.

本文分享自微信公众号 - 洁癖是一只狗(rookie-dog),作者:洁癖汪

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-07-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 深入浅出Zookeeper(一) Zookeeper架构及FastLeaderElection机制

    Jason Guo
  • zookeeper第一弹!

    Hello,大家好,我是兔君哦!今天主要介绍一下zookeeper,以及相关功能和数据结构。后续还会继续分享。

    萌兔IT
  • ZooKeeper学习第七期--ZooKeeper一致性原理

    我们知道可以通过ZooKeeper对分布式系统进行Master选举,来解决分布式系统的单点故障,如图所示。

    用户5640963
  • 深入解读zookeeper一致性原理

    我们知道可以通过ZooKeeper对分布式系统进行Master选举,来解决分布式系统的单点故障,如图所示。

    用户1655470
  • 模拟Dubbo的zookeeper一致性Hash发现

    接之前一篇<手写zookeeper来模拟dubbo的注册/发现>,使用一致性Hash来进行查找需要寻找的服务.

    算法之名
  • 分布式之Zookeeper一(分布式锁与Zookeeper集群)

    说到分布式开发,不得不说的就是zookeeper了;zookeeper官网说到Apache ZooKeeper致力于开发和维护可实现高度可靠的分布式协调的开源服...

    Java_老男孩
  • 少年:ZooKeeper学一下

    很多中间件,比如Kafka、Hadoop、HBase,都用到了 Zookeeper,于是很多人就会去了解这个 Zookeeper 到底是什么,为什么它在分布式系...

    sowhat1412
  • Zookeeper系列一:Zookeeper基础命令操作

    由于公司年底要更换办公地点,所以最近投了一下简历,发现面试官现在很喜欢问dubbo、zookeeper和高并发等。由于公司没有使用dubbo,只知道dubbo是...

    java干货
  • Zookeeper笔记一:session

    Chroot特性 从3.2.0版本开始可通过connection String后面跟上一个绝对路径设置root,比如“192.168.1.1:2181/app/...

    囚兔
  • ZooKeeper学习第一期---Zookeeper简单介绍

    在给大家介绍ZooKeeper之前先来给大家介绍一种技术——分布式协调技术。那么什么是分布式协调技术?那么我来告诉大家,其实分布式协调技术 主要用来解决分布式环...

    用户5640963
  • 聊一聊ZooKeeper的顺序一致性

    ZooKeeper作为分布式应用系统协调服务,在分布式系统中的应用非常广泛,在某些业务场景下甚至可以作为注册中心、分布式锁来使用。ZooKeeper之所以能有如...

    孙玄@奈学教育
  • ZooKeeper 一二事 - 搭建ZooKeeper伪分布式及正式版集群 提供集群服务

    集群真是好好玩,最近一段时间天天搞集群,redis缓存服务集群啦,solr搜索服务集群啦,,,巴拉巴拉 今天说说zookeeper,之前搭建了一个redis集...

    风间影月
  • 关于Zookeeper一键启动/关闭脚本所产生的乌龙事件

    大家都知道在Hadoop集群开启/关闭Zookeeper集群的时候,需要到不同的节点ZK的bin目录下执行对应的启动/关闭脚本,十分的麻烦。所以...

    大数据梦想家
  • 分布式利器Zookeeper(一)Hello,Zookeeper初步认识Zookeeper的数据模型初步认识Zookeeper的角色组成install Zookeeper基本的ZK命令ZooInspe

    Zookeeper不论是在实际项目中,还是在各种分布式开源项目中都得到了广泛应用,从本篇博客开始,将为大家带来我对Zookeeper的认识。这个系列将会涵盖Zo...

    用户2890438
  • zookeeper系列(一)——简介和原理

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    逝兮诚
  • ZooKeeper入门教程(一)

    想必大家都对分布式系统有所耳闻,大部分人对分布式都能侃侃而谈,但到了真正实施的时候,才发现其中的不易。今天带大家一起了解一款开源软件,ZooKeeper。它通过...

    好好学java
  • ZooKeeper简单介绍(一)

    这篇博文我们简单的介绍一下什么是ZooKeeper,ZooKeeper的下载安装,以及Zookeeper的整体概况,它们将作为黑暗中的探照灯指明我们前进的方向。

    程序猿小亮
  • Zookeeper学习笔记(一)

      1、集群的角色: Leader 和 Follower (半数存活机制)(一个Leader多个Follower);

    挽风
  • 通过 Netty、ZooKeeper 手撸一个 RPC 服务

    使用 Netty、ZooKeeper 和 Spring Boot 手撸一个微服务框架。

    Yano_nankai

扫码关注云+社区

领取腾讯云代金券