8-zookeeper算法基础(尚硅谷学习笔记)

2021/10/5 11:10:52

本文主要是介绍8-zookeeper算法基础(尚硅谷学习笔记),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

  • 拜占庭将军问题
  • paxos算法
    • paxos算法流程
    • 情况一
    • 情况二
      • 情况1
      • 情况2
  • ZAB协议
    • ZAB协议内容
      • 消息广播
        • 过程
        • 可能出现的问题
      • 崩溃恢复
        • 异常假设
        • leader选举
        • 数据恢复
  • CAP理论

拜占庭将军问题

拜占庭罗马帝国国土辽阔,为了达到防御目的,每个军队都分隔很远,将军与将军之间只能靠信差传消息。在战争的时候,拜占庭军队内所有将军和副官必须达成一致的共识,决定是否有赢的机会才去攻打敌人的阵营。但是,在军队内有可能存有叛徒和敌军的间谍,左右将军们的决定又扰乱整体军队的秩序。在进行共识时,结果并不代表大多数人的意见。这时候,在已知有成员谋反的情况下,其余忠诚的将军在不受叛徒的影响下如何达成一致的协议,拜占庭问题就此形成(百度百科)

paxos算法

在paxos算法中,首先将所有节点划分为proposerI(提议者)、acceptor(接收者)、learner(学习者)每个节点可以充当多个角色

paxos算法流程

1.Prepare(准备阶段)
proposer向多个acceptor发出propose请求promise
acceptor针对收到的propose请求进行promise
2.accept(接受阶段)
proposer收到多数acceptor承诺地epromise后,向acceptor发出propose请求
acceptor针对收到的propose请求进行accept处理
3.learn(学习阶段)
1.prepare:proposer生成全局唯一递增的Proposal ID,向所有Accepter发送Propose请求,这里毋须携带提案内容,只携带proposal ID即可

2.promise:acceptor收到propose请求后,做出“两个承诺,一个应答”

​ (1)不再接受proposal ID小于等于当前请求的Propose请求

​ (2)不再接受proposal ID小于当前请求的accept请求

​ (3)不违背以前作出的承诺下,回复已经accept过的提案中的proposal ID最大的哪个提案的value和proposal ID,没有则返回空值

3.propose:proposer收到多数accepter的promise应答后,从应答中选择proposal ID最大的提案的value,作为本次要发起的提案。如果所有应答的提案value均为空值,则可以自己随意决定提案value,然后携带当前proposal ID,向所有acceptor发送propose请求

4.accept:acceptot收到propose请求后,在不违背自己之前做出的承诺下,接受并持久化当前proposal ID和提案value
请添加图片描述

情况一

A1,A2,A3,A4,A5五位议员就税率问题进行决议
请添加图片描述

1.A1发起Proposal的Propose(未告知决议的内容),等待承诺

2.A2-A5回应promise

3.A1在收到两份回复时就会发起税率10%的proposal

4.A2-A5回应accept

5.通过proposal,税率10%

情况二

A1提出提案的同时,A5决定将税率定为20%

1.A1,A5同时发起Proposal的Propose(序号分别为1,2)

2.A2承诺A1,A4承诺A5,A3成为关键

情况1

请添加图片描述

3.A3先收到A1消息,承诺A1

4.A1发起proposal(1,10%),A2,A3接受

5.之后A3又收到A5消息,回复A1:(1,10%),并承诺A5

6.A5发起proposal(2,20%),A3,A4接受,之后A1,A5同时广播决议,由于A5的proposal ID大,A2,A3更新承诺

情况2

A3先收到A1的消息,承诺A1,之后立刻收到A5的消息,承诺A5

A1发起Proposal(1,10%),无足够响应,A1重新propose(序号为3),A3再次承诺A1

A5发起Proposal(2,20%),无足够响应,A5重新propose(序号为4),A3再次承诺A5

以此往复

造成这种情况的原因是系统中有一个以上的proposer相互竞争acceptor,造成长时间无法达成一致的情况。
改进方法:从系统中选出一个节点作为leader,只有leader能够发起提案。这样一次paxos只有一个proposer不会出现活锁的情况

ZAB协议

ZAB借鉴了paxos算法,为zookeeper设计的支持崩溃恢复的原子广播协议。基于该协议,zookeeper设计为只有一台客户端(leader)于该协议,Zookeeper设计为只有一台客户端(Leader)负责处理外部的写事务请求,然后Leader客户端将数据同步到其他Follower节点。即 Zookeeper只有一个Leader可以发起提案。

ZAB协议内容

ZAB协议包括:消息广播,崩溃恢复

消息广播

在这里插入图片描述

过程

(1)客户端发起一个写操作请求。
(2)Leader服务器将客户端的请求转化为事务Proposal提案,同时为每个Proposal分配一个全局的ID,即zxid。
(3) Leader服务器为每个Follower服务器分配一个单独的队列,然后将需要广播的 Proposal依次放到队列中去,并且根据FIFO策略(先进先出)进行消息发送。
(4)Follower接收到Proposal后,会首先将其以事务日志的方式写入本地磁盘中,写入成功后向Leader反馈一个Ack响应消息。
(5)Leader接收到超过半数以上Follower的Ack响应消息后,即认为消息发送成功,可以发送commit消息。
(6)Leader向所有Follower广播commit消息,同时自身也会完成事务提交。Follower接收到commit消息后,会将上一条事务提交。
(7) Zookeeper采用Zab协议的核心,就是只要有一台服务器提交了Proposal,就要确保所有的服务器最终都能正确提交Proposal。

可能出现的问题

ZAB协议针对事务请求的处理过程类似于一个两阶段提交过程:(1)广播事务阶段(2)广播提交操作
这两阶段提交模型如下,有可能因为Leader宕机带来数据不一致,比如
( 1 ) Leader发起一个事务Proposal1后就宕机,Follower都没有Proposall
( 2 ) Leader收到半数ACK宕机,没来得及向Follower发送Commit

崩溃恢复

崩溃恢复主要包括两部分:Leader选举和数据恢复。

异常假设

假设两种服务器异常情况
在这里插入图片描述

(1)假设一个事务在Leader提出之后,Leader挂了。
(2)一个事务在Leader上提交了,并且过半的Follower都响应Ack了,但是Leader在Commit消息发出之前挂
Zab协议崩溃恢复要求满足以下两个要求:
(1)确保已经被Leader提交的提案Proposal,必须最终所有的Follower服务器提交。(已经产生的提案,Follower必须执行)
(2)确保丢弃已经被Leader提出的,但是没有被提交的Proposal。

leader选举

选举条件:
(1)新选举出来的Leader不能包含未提交的Proposal。即新Leader必须都是已经提交了Proposal的Follower服务器节点
(2)新选举的Leader节点中含有最大的zxid。这样做的好处是可以避免Leader服务器检查Proposal的提交和丢弃工作。

数据恢复

在这里插入图片描述

数据同步
(1)完成Leader选举后,在正式开始工作之前(接收事务请求,然后提出新的Proposal), Leader服务器会首先确认事务日志中的所有的Proposal是否已经被集群中过半的服务器Commit
(2)Leader服务器需要确保所有的Follower服务器能够接收到每一条事务的Proposal,并且能将所有已经提交的事务Proposal应用到内存数据中。等到Follower将所有尚未同步的事务Proposal都从Leader服务器上同步过,并且应用到内存数据中以后,Leader才会把该Follower加入到真正可用的Follower列表中

CAP理论

一个分布式系统不可能同时满足:一致性、可用性、分区容错性,并且最多只能满足其中两个!
1 )一致性( C:Consistency )
在分布式环境中,一致性是指数据在多个副本之间是否能够保持数据一致的特性。在一致性的需求下,当一个系统在数据一致的状态下执行更新操作后,应该保证系统的数据仍然处于一致的状态。
2)可用性(A:Available)
可用性是指系统提供的服务必须一直处于可用的状态,对于用户的每一个操作请求总是能够在有限的时间内返回结果。
3)分区容错性(P:Partition Tolerance)
分布式系统在遇到任何网络分区故障的时候,仍然需要能够保证对外提供满足一致性和可用性的服务,除非是整个网络环境都发生了故障。

CA without P:如果不要求P(不允许分区),则C(强一致性)和A(可用性)是可以保证的。但其实分区不是你想不想的问题,而是始终会存在,因此CA的系统更多的是允许分区后各子系统依然保持CA。
CP without A:如果不要求A(可用),相当于每个请求都需要在Server之间强一致,而P(分区)会导致同步时间无限延长,如此CP也是可以保证的。很多传统的数据库分布式事务都属于这种模式。
AP wihtout C:要高可用并允许分区,则需放弃一致性。一旦分区发生,节点之间可能会失去联系,为了高可用,每个节点只能用本地数据提供服务,而这样会导致全局数据的不一致性。现在众多的NoSQL都属于此类。

ZooKeeper保证的是CP
(1) ZooKeeper不能保证每次服务请求的可用性。(注:在极端环境下,ZooKeeper可能会丢弃一些请求,消费者程序需要重新请求才能获得结果)。所以说,ZooKeeper不能保证服务可用性。
(2)进行leader选举时集群都是不可用的



这篇关于8-zookeeper算法基础(尚硅谷学习笔记)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程