登录 |  注册
首页 >  云计算&大数据 >  经典算法大全 · 实例详解 >  PacificA算法分析-分布式一致性框架

PacificA算法分析-分布式一致性框架

PacificA严格来说不是一个算法,而是一个分布式一致性框架。它采用配置集群和存储集群的方式,实现数控分离,这点和SDN有点像。其中配置集群负责管理,具体说来是采用了ETCD方案,而ETCD又是采用raft算法来实现一致性的。具体说来,选主的过程可以概括为:从者失联,自立为王;主者失联,下野流放。还有一点有意思的是,这里也应用了一种叫做租约机制的玩意,形象的说就是一厢情愿。所谓一厢,指的是授权者颁布lease时,不会管接收方的状态。就像男孩子追女孩子一样,虽然有点傻,但一般男生在一段时间内会信守承诺,克服重重困难。但和所有靠谱承诺一样,都是会是有期限的。所以lease期限到后,双方都不认了,这时授权者又可以重新颁发lease,接收方也不相信这个lease的有效性。比如说,一台服务器发出lease,我在30秒内部改变数据,那么其他client就可以放心的在这30s内访问数据,不用担心数据不一致问题。30s后,其他client再收到lease就视而不见了。

PacificA算法分析

PacificA算法是微软亚洲研究院提出的一种用于日志复制系统的分布式一致算法,与其他的一致性算法相比,PacificA算法主要用于数据的一致性管理,并另辟蹊径采用其他一致性组件来进行配置一致性管理。

1. 特点

  • 配置管理与数据管理分离:引入额外一致性组件来维护Configuration

  • 强一致性:任意时刻读取到的数据都是最新数据

  • 少数派Replica可用时仍可读写:每个副本都有全量数据因此只要有一个副本存在即可保证读写

  • 去中心化的故障检测:通过节点间的契约机制来进行故障检测

2. 名词

  • Replica Group:互为副本的一组数据的集合,其中有一个primary,其余都是secondary

  • Configuration: Repica Group的元数据,如副本有哪些,谁是primary等

  • Configuration Manager: 配置一致性管理工具

  • Serial Number(SN): 代表Update的执行顺序,每次update增加1

  • Prepared List: Update操作的序列

  • Committed List: 已经提交的update序列,是Prepared List的前缀

3. 读写流程

3.1 查询(query)

该算法中,查询只能在primary上进行,primary获取自身的数据,直接返回即可

3.2 更新(update)

更新也是在primary上发起,流程如下

  1. primary为updateRequest分配一个SN

  2. primary发送prepare请求到各secondary,请求中包含updateRequest和SN

  3. 各secondary接收到请求,并将updateRequest和SN加入到PreparedList中,返回ACK给primary

  4. 当primary收到所有secondary的ack后,则执行该update,并将commit point移动到该commit。

  5. 返回执行成功

可以看到当一个update执行成功后,primary上对应的数据已经commit,secondary上数据也被加入到了更新队列中。在这种情况下

  • 读操作读取的是primary上的commitList,可以拿到更新的数据。

  • secondary中虽然数据没有被commit,但是也被加入到了prepared List中,当主节点挂掉时仍能保证数据不丢失。

  • secondary上的数据不能自己commit,而必须由于primary来触发。这是为了应对由于异常情况导致update没有执行成功,secondary自主commit导致未更新成功数据被commit,且数据领先与primary。

3.3 Committed Invariant

从读写流程可以推导出committed不变式"Committed Invariant"

  • Secondary Committed List为Primary committed List的前缀, 即primary commit领先于secondary。

  • Primary Committed List为Secondary PreparedList的前缀,即Sencodary拥有primary commit的所有数据(虽然没有committed)。其实当没有在进行update操作时,Secondary的PreparedList和Primary的CommittedList是应该是一样长的。

这里想到一个异常情况,当update执行过程中,primary挂掉了,导致更新失败,secondary已经被prepare了update,这时一个secondary被选为新的primary,将其所有的update commit,那之前失败的update操作数据不就出现在了数据中,导致与预期不符?

这里与同事讨论了一下,认为pacificA算法中一个primary或secondary是一个数据实体,不应该是一个执行实体,所以当primary挂掉后,update任务不会执行失败,而是等待选出新的primary,并在其上commit这个update,保证不会出现数据不一致的情况。

4. 故障检测和恢复

pacificA通过契约(lease)的方式来进行primary和secondary间的互相检测。primary会定期(lease period)向各节点请求契约,如果某个节点没有回复,则说明该节点已经故障,primary会向Configuration Manager请求移除该secondary。 如果过了(grace period), 一个secondary没有收到primary的请求,则认为primary故障,该secondary会向Configuration请求移除Primary,并将自己设置为primary。这里要注意

  • 当多个secondary均发现primary故障,则按照first win原则,先请求的成为primary

  • 当出现网络分区时,primary会要求剔除secondary, secondary要求剔除primary,但由于lease period< grace period,可以保证primary先于secondary发现故障,并将secondary剔除

4.1 secondary故障

当一个scondary故障时,primary在向该secondary发送lease请求时会超时,primary向Configuration Manage发送Reconfiguration请求将该secondary从Configuration中移除

4.2 primary故障

当primary故障时, secondary在超过grace period没有收到primary的请求,就会向Configuration Manager发送Reconfiguraiont请求

要求将primary从configuration中移除并将自己选为primary。多个secondary竞争成为primary时,遵循first win原则。

当一个secondary被选为primary后 ,它会向所有的secondary发送prepare请求,要求所有的sencodary均以其pareparedList为准进行对齐,当收到所有secondary的ack后,primary将自己的commit point移动到最后,这个时候primary才能对外提供服务。

4.3 网络分区的场景

网络分区场景下,primary认为secondary故障,secondary认为primary故障,但由于lease period小于grace period,所以primary会先与secondary发现故障,并向Congfiguration Manager发送请求移除secondary

4.4 新节点加入

新节点加入时,首先会先成为secondary candidate, 然后追平primary的preparedList,然后申请成为secondary。还有一种情况是之前故障的节点恢复加入,这个时候会复用之前的preparedlist并追平secondary的preparedlist, 然后申请成为secondary。

4.5 Primary Invariant

在pacificA算法中,要保证primary不变式Primary Invariant,即

  • 同一个时刻只有一个副本认为自己是primary

  • configuration Manager也认为其是primary。

    从前面的故障恢复可以看到pacificA算法通过lease(契约)机制保证了这个不变式

4.6 Reconfiguration Invariant

重新配置不变式:当一个新的primary在T时刻完成reconfiguration,那么T时刻之前任意节点(包括原primary)的committedList都是新的primary当前committedList的前缀。

该不变式保证了reconfiguration过程中没有数据丢失,由于update机制保证了任意的sencondary都有所有的数据,而reconfiguration重新选primary要求新的primary commit其所有的prepareList,因此这个不变式可以得到保证。

5. 算法总结

PacificA是一个读写都满足强一致的算法,它通过三个不变式保证了读写的primary的唯一性,读写的强一致性,故障恢复的可靠性。

它把数据的一致性和配置的一致性分开,使用额外的一致性组件(Configuration Manager)维护配置的一致性,结合lease机制保证了Primary Invariant,使得在同一时刻有且仅有一个primary。

 update操作时,要求所有的secondary均prepare当前update,primary commit当前update,保证了Committed Invariant, 使得读操作可以获取到最新数据,primary故障时,secondary也有全量的数据。

故障恢复机制保证了当secondary被选为primary时,其commit包含之前primary或secondary的commit,保证了Reconfiguration Invariant,使得在故障恢复后数据不会有丢失。

原文链接: https://www.yukx.com/arithmetic/article/details/2051.html 优科学习网PacificA算法分析-分布式一致性框架

<<上一课程
推荐文章
  • Raft协议分区容忍的一致性协议的核心思想:一致性的保证不一定非要所有节点都保持一致,只要大多数节点更新了,对于整个分布式系统来说数据也是一致性的。Raft协议将概念分解成:Leaderelection、Logreplication、Safety。Raft把一致性协议划分为Leader选举、Memb
  • Paxos、Raft分布式一致性算法应用场景一文讲述了分布式一致性问题与分布式一致性算法的典型应用场景。作为分布式一致性代名词的Paxos算法号称是最难理解的算法。本文试图用通俗易懂的语言讲述Paxos算法。 Paxos算法简介Paxos算法是1990年LeslieLamport在论文《ThePar
  • 一、准备工作搭建hadoop伪分布式环境;见hadoop伪分布式搭建下载hive安装包;下载路径http://archive.apache.org/dist/hive/二、设置环境变量将安装包解压到/opt目录下$ tar xvzf apache-hive-0.13.0-bin.tar.gz设置环境
  • 什么是Hive?Hive是基于Hadoop的一个数据仓库工具,可以将HDFS中结构化的数据文件映射为一张表,并提供类SQL查询功能,本质是将HQL转化为mapreduce程序。mapreduce理解mapreduce数据以一条记录为单位经过map方法映射成KV,相同的key为一组,这一组数据用一次r
  • Docker使用客户端-服务器(C/S)架构模式,使用远程API来管理和创建Docker容器。Docker容器通过Docker镜像来创建。容器与镜像的关系相似于面向对象编程中的对象与类。Docker总
  • Docker是什么?Docker是一个开源的应用容器引擎,基于Go语言并遵从Apache2.0协议开源。Docker可以让开发者打包他们的应用以及依赖包到一个轻量级、可移植的容器中,然后发布到任何流行
学习大纲