Nivelle 开拓视野冲破艰险看见世界 身临其境贴近彼此感受生活

Zookeeper学习(一)之分布式基础

2016-04-12

分布式架构

集中式的特点

所谓的集中式系统就是指由一台或多台主计算机组成中心节点,数据集中存储于这个中心节点中,并且整个系统的所有业务单元都集中部署在这个中心节点上,系统的所有功能尤其集中处理。也就是说,在集中式系统中,每个终端或客户端机器仅仅负责数据的录入和输出,而数据的存储于控制处理完全交由主机来完成。

分布式的特点

分布式系统是一个硬件或软件组件分布在不同的网络计算机上,彼此之间仅仅通过消息传递进行通信和协调的系统。

  • 分布性:系统中多台计算机都会在空间上随意分布,同时,机器的分布情况也会随时变动。
  • 对等性:分布式系统中的计算机没有主从之分,既没有控制整个系统的主机,也没有被控制的从机,组成分布式系统的所有计算机节点都是对等的。副本是分布式系统最常见的概念之一,指的是分布式系统和服务提供的一种冗余方式。 数据副本:在不同节点上持久化同一份数据,当某一个节点上存储的数据丢失时,可以从副本上读取到该数据,这是解决分布式系统数据丢失问题最为有效的手段 服务副本:指多个阶段提供同样的服务,每个节点都有能力接收来自外部的请求并进行相应的处理
  • 并发性:在一个计算机网络中,程序运行过程中的并发操作时非常常见的行为。例如同一个分布式系统中的多个节点,可能会并发地操作一些共享的资源,注入数据库或分布式存储等。

  • 缺乏全局时钟:一个典型的分布式系统是由一些列在空间上随意分布的多个进程组成的,具有明显的分布性,这些进程之间通过交换消息来进行互相通信。因此在分布式系统中,很难定义两个事件究竟谁先谁后,原因就是分布式系统缺乏一个全局的时钟序列控制。

分布式环境的各种问题

  • 通信异常:分布式系统需要在各个节点之间进行网络通信,因此每次网络通信都会伴随着网络不可用的风险,网络光纤、路由器或是DNS等硬件设备或是系统不可用都会导致最终分布式系统无法完成一次网络通信。同时,消息丢失和消息延迟的现象也无法避免。
  • 网络分区:当网络由于发生异常情况,导致分布式系统中部分节点之间的网络延时不断增大,最终导致组成分布式系统的所有节点中,只有部分节点之间能够进行正常通信,而另一些节点则不能,我们将这个现象称为网络分区。

三态

成功、失败、超时

超时:

  1. 由于网络原因,该请求并没有被成功地发送到接收方,而是在发送过程就发生了消息丢失现象。
  2. 该请求成功的被接收方接收后,并进行了处理,但是在将响应反馈给发送方的过程中,发生了消息丢失现象。

节点故障:

指的是组成分布式系统的服务器节点出现宕机或“僵死”现象。

分布式事务:

分布式事务是指事务的参与者、支持事物的服务器、资源服务器以及事务管理器分别位于分布式系统的不同节点之上。通常一个分布式事务中会涉及对多个数据源或业务系统的操作。

一个分布式事务可以看作是由多个分布式的操作序列组成的,通常可以把这一系列分布式的操作序列称为子事务。因此,分布式事务也可以被定义为一种嵌套型的事务,同时也就具有了ACID事务特性。但由于在分布式事务中,各个子事务的执行时分布式的。

CAP理论

CAP理论告诉我们,一个分布式系统不可能同时满足一致性、可用性和分区容错性。

  • 一致性:指的是数据在多个副本之间是否能够保持一致的特性。在一致性的需求下,当一个系统在数据一致的状态下执行更新操作后,应该保证形态的数据仍然处于一致的状态。
  • 可用性:系统服务必须一直处于可用的状态,对于用户的每个操作请求总是能够在有限的时间内返回结果。
  • 分区容错性:分布式系统在遇到任何网络分区故障的时候,任然需要能够保证对外提供满足一致性和可用性的服务,除非是整个网络环境都发生了故障。

网络分区是指在分布式系统中,不同的节点分布在不同的子网络(机房或异地网络等)中,由于一些特殊的原因导致这些子网络之间出现网络不连通的状况,但各个子网络的内部网络是正常的,从而导致整个系统的环境被切分成了若干个孤立的区域。需要注意的是,组成一个分布式系统的每个节点的加入与退出都可以看作是一个特殊的网络分区。

image

BASE理论

BASE是对CAP中一致性和可用性权衡的结果,其来源于对大规模互联网系统分布式实践的总结,是基于CAP定理逐步演化而来的,其核心思想是即使无法做到强一致性,但每个应用都可以根据自身的业务特点,采用适当的方式来使胸到达最终一致性。

BASE三要素:

  • 基本可用

在出现不可预知故障时,允许牺牲部分可用性。

1.响应时间上的损失。

2.功能上的损失。例如为了保护核心功能,部分请求可能被引导到一个降级页面。

  • 弱状态

弱状态也称为软状态,和硬状态相对,是指允许系统中的数据存在中间状态,并认为该中间状态的存在不会影响系统的整体可用性,即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

  • 最终一致性

最终一致性强调的是系统中所有的数据副本,在经过一段时间的同步后,最终能够达到一个一致状态。因此,最终一致性的本质是需要系统保证最终数据能够达到一致,而不需要实时保证系统数据的强一致性。

最终一致性的五类主要变种:

  1. 因果一致性

如果进程A在更新完某个数据项后通知了进程B,那么进程B之后对该数据项的访问都应该能够获取到进程A更新后的最新值,并且如果进程B要对该数据项进行更新操作的话,务必基于进程A更新后的最新值,即不能发生丢失更新的情况。

  1. 读己之所写

读己之所写是指,进程A更新一个数据项之后,它自己总是能够访问到更新过的最新值,而不会看到旧值。

  1. 会话一致性

会话一致性将对系统数据的访问过程框定在了一个会话当中:系统能保证在同一个有效的会话中实现“读己之所写”的一致性,也就是说,执行更新能操作之后,客户端能够在同一会话中始终读取到该数据项的最新值。

  1. 单调读一致性

单调读一致性是指如果一个进程从系统中读取一个数据项的某个值后,那么系统对于该进程后续的任何数据访问都不应该返回更旧的值。

  1. 单调写一致性

单调写一致性是指,一个系统需要能够保证来自同一个进程的写操作被顺序地执行。

2PC与3PC

背景:

在分布式系统中,每一个机器节点虽然能够明确地知道自己在进行事务操作过程中的结果是成功或失败,但却无法直接获取到其他分布式节点的结果。因此,当一个事物的操作需要跨越多个分布式节点的时候,为了保持事务处理的ACID特性,就需要引入一个称为“协调者”的组件来统一调度所有分布式节点的执行逻辑,这些被调度的分布式节点则被称为“参与者”。协调者负责调度参与者的行为,并最终决定这些参与者是否要把事务真正进行提交。

2pc

Two-Phase Commit的缩写,即二阶段提交,是计算机网络尤其是在数据库领域内,为了使基于分布式系统架构下的所有节点在进行事务处理过程中能够保持原子性和一致性而设计的一种算法。通常,二阶段提交协议也被认为是一种一致性协议,用来保证分布式系统数据的一致性。

协议说明:

阶段一:提交事务请求

1 . 事务询问。

协调者向所有的参与者发送事务内容,询问是否可以执行事务提交操作,并开始等待各参与者的响应。

2 . 执行事务。

各参与者节点执行事务操作,并将Undo和Redo信息记入事务日志中。

3 . 各参与者向协调者反馈事务询问的响应。

如果参与者成功执行了事务操作,那么就反馈给协调者YES响应,表示事务可以执行;如果参与者没有成功执行事务,那么就反馈给协调者NO。

阶段二:执行事务提交

在阶段二中,协调者会根据各参与者的反馈情况来决定最终是否可以进行事务提交操作,正常情况下,包含以下两种情况。

执行事务提交

假如协调者从所有的参与者获得的反馈都是YES响应,那么就会执行事务提交。

1 . 发送提交请求。

协调者向所有参与者发出Commit请求。

2 . 事务提交

参与者接收到Commit请求后,会正式执行事务提交操作,并在完成提交之后释放在整个事物执行期间占用的事务资源。

3 . 反馈事务提交结果

参与者在完成事务提交之后,向协调者发送Ack消息。

4 . 完成事务

协调者接收到所有参与者反馈的Ack消息后,完成事务。


中断事务

假如任何一个参与者向协调者反馈了No响应,或者在等待超时之后,协调者尚无法接收到所有参与者的反馈响应,那么就会中断事务。

  1. 发送回滚请求。

协调者向所有参与者节点发出Rollback请求。

  1. 事务回滚

参与者接收到RollBack请求后,会利用其在阶段一种记录的Undo信息来执行事务回滚操作,并在完成回滚之后释放在整个事物执行期间占用的资源。

  1. 反馈事务回滚结果。

参与者在完成事务回滚之后,向协调者发送Ack消息。

  1. 中断事务。

协调者接收到所有参与者反馈的Ack消息后,完成事务中断。

image


3pc

协议说明

3PC,是Three-Phase Commit的缩写,即三阶段提交,是2PC的改进版,其将二阶段提交协议的“提交事务请求”过程一分为二,形成了由CanCommit、PreCommit和do Commit三个阶段组成的事务处理协议。

image

阶段一:CanCommit
  1. 事务询问。

协调者向所有的参与者发送一个包含事务内容的canCommit请求,询问是否可以执行事务提交操作,并开始等待各参与者的响应。

  1. 各参与者向协调者反馈事务询问的响应。

参与者在接收到来自协调者的canCommit请求后,正常情况下,如果其自身认为可以顺利执行,那么会反馈Yes响应,并进入预备状态,否则反馈No响应。

阶段二:PreCommit

在阶段二中,协调者会根据各参与者的反馈情况来决定是否可以进行事务的PreCommit操作,正常情况下,包含两种可能。

执行事务提交

假如协调者从所有的参与者获得的反馈都是Yes响应,那么就会执行事务预提交

  1. 发送预提交请求

协调者向所有参与者节点发出preCommit的请求,并进入Prepared阶段。

  1. 事务预提交

参与者接收到preCommit请求后,会执行事务操作,并将Undo和Redo信息记录到事务日志中。

3.各参与者向协调者反馈事务执行的响应。

如果参与者成功执行了事务操作,那么就会反馈给协调者Ack响应,同时等待最终的指令:提交(commit)或者终止(abort)

中断事务

假如任何一个参与者向协调者反馈了No响应,或者在等待超时之后,协调者尚无法接收到所有参与者的反馈响应,那么就会中断事务。

  1. 发送中断请求。

协调者向所有参与者发出abort请求。

  1. 中断事务

无论是收到来自协调者的abort请求,或者是在等协调者请求超时,参与者都会中断事务。

阶段三:doCommit

该阶段将进行真正的事务提交,会存在以下两种情况。

执行提交

  1. 发送提交请求。

进入这一阶段,假设协调者处于正常工作状态,并且它接收到了来自所有参与者的Ack响应,那么它将从“预提交”状态转换到“提交”状态,并向所有的参与者发送doCommit请求。

  1. 事务提交。

参与者接收到doCommit请求后,会真是执行事务提交操作,并在完成提交之后释放在整个事物执行期间占用的事务资源。

  1. 反馈事务提交结果。

参与者在完成事务提交之后,向协调者发送Ack消息。

  1. 完成事务。

协调者接收到所有参与者反馈的Ack消息后,完成事务。

中断事务:

进入这一阶段,假设协调者处于正常工作状态,并且有任意一个参与者向协调者反馈了No响应,或者在等待超时之后,协调者尚无法接收到所有参与者的反馈响应,那么就会中断事务。

  1. 发送中断请求。

协调者向所有的参与者节点发送abort请求。

  1. 事务回滚。

参与者接收到abort请求后,会利用其在阶段二中记录的Undo信息来执行事务回滚操作,并在完成回滚之后释放在整个事务执行期间占用的资源。

  1. 反馈事务回滚结果。

参与者在完成事务回滚之后,向协调者发送Ack消息。

  1. 中断事务。

协调者接收到所有参与者反馈的Ack消息后,中断事务。

需要注意的是,一旦进入阶段三,可能会存在以下两种故障。

  • 协调者出现问题。
  • 协调者和参与者之间的网络出现故障。

无论出现那种情况,最终都会导致参与者无法及时收到来自协调者的doCommit或是abort请求,针对这样的异常情况,参与者都会在等待超时之后,继续进行事务提交。


Paxos算法

基于消息传递且具有高度容错性的一致性算法,是目前公认的解决分布式一致问题最有效的算法之一。

问题描述

假设有一组可以提出提案的进程集合,那么对于一个一致性算法来说需要保证以下几点:

  • 在这些被提出的提案中,只有一个会被选定。
  • 如果没有提案被提出,那么就不会有被选定的提案。
  • 当一个提案被选定后,进程应该可以获取被选定的提案信息。

对于一致性来说,安全性需求如下:

  • 只有被提出的提案才能被选定。
  • 只能有个一个值被选定
  • 如果某个进程认为某个提案被选定了,那么这个提案必须是真的被选定的那个。

在一致性算法中,有三种参与角色,我么用Proposer(建议人)、Acceptor(接受者)和Learner(学习者)来表示。

提案选取过程:

Proposer向一个Acceptor集合发送提案,同样,集合中的每个Acceptor都可能会批准(Accept)该提案,当有足够多的Acceptor批准这个提案的时候,我们就可以认为该提案被选定了。我们假定足够多的Acceptor是整个Acceptor集合的一个子集,并且让这个集合大得可以包含Acceptor集合中的大多数成员,因为任意两个包含大多数Acceptor的子集至少有一个公共成员。

推导过程

在没有失败和消息丢失的情况下,如果我们希望即使在只有一个提案被提出的情况下,任然可以选出一个提案,这就暗示了如下的需求。

P1:一个Acceptor必须批准它收到的第一个提案。

但是:如果有多个提案被不同的Proposer同时提出,这可能会导致虽然每个Acceptor都批准了它收到的第一个提案,但是没有一个提案是由多数人都批准的。另外,即使只有两个提案被提出,如果每个提案都被差不多一半的Acceptor批准了,此时即使只有一个Acceptor出错,都有可能导致无法确定该选定那个提案。

image

解决方案: 我们使用一个全局的编号(这种全局唯一编号的生成并不是Paxos算法需要关注的地方,就算法本身而言,其假设当前已经具备这样的外部组件能够生成一个全局唯一的编号)来唯一标识每一个被Acceptor批准的提案,当一个具有某Value值得提案被半数以上的Acceptor批准后,我们就认为该Value被选定了,此时我们也认为该提案被选定了。需要注意的是,此处讲到的提案已经和Value不是同一个概念了,提案变成了一个由编号和Value组成的组合体,因此我们以“[编号,Value]”来表示一个提案。

根据上面讲到的内容,我们虽然允许多个提案被选定,但同时必须要保证所有被选定的提案都具有相同的Value值————这是一个关于提案Value的约定,结合提案的编号,该约定可以定义如下:

P2 :如果编号为M0、Value值为V0的提案(即[M0,V0])被选定了,那么所有比编号M0更高的,且被选定的提案,其Value值必须也是V0 .

因为提案的编号是全序的,条件P2就保证了只有一个Value值被选定这一个关键安全性属性。同时,一个提案要被选定,其首先必须被至少一个Acceptor批准,因此我们可以通过满足如下条件来满足P2.

p2a:如果编号为M0、value值为V0的提案(即[M0,V0])被选定了,
那么所有比编号M0更高的,且被Acceptor批准的提案,其Value值必须也是V0.

因为通信是异步的,一个提案可能会在某个Acceptor还未收到任何提案时就被选定了:

image

P2b:如果一个提案[M0,V0]被选定后,那么之后任何Proposer产生的编号更高的提案,其Value值都为V0.

因为一个提案必须在被Proposer提出后才能被Acceptor批准,因此P2b包含了P2a,进而包含了P2。于是,接下去的重点就是论证P2b成立即可:

假设某个提案[M0,V0]已经被选定了,证明任何编号Mn>M0的天,其值都是V0.

Proposer生成提案

  • Proposer选择一个新的提案编号Mn,然后向某个Acceptor集合的成员发送请求,要求改集合中的Acceptor做出如下回应。
  1. 向Proposer承诺,保证不再批准任何编号小于Mn的提案

  2. 如果Acceptor已经批准过任何提案,那么其向Proposer反馈当前Acceptor已经批准的标号小于Mn但为最大编号的的那个提案的值。

  • 如果Proposer收到了来自半数以上的Acceptor的相应结果,那么它就可以产生编号为Mn,Value值为Vn的提案,这里的Vn是所有响应编号中最大的提案的Value值。当然还存在另一种情况,就是半数以上的Acceptor都没有批准过任何提案,即响应中不包含任何的提案,那么此时Vn值就可以有Proposer任意选择。

Acceptor批准提案

在上文,我们已经讲解了Paxos算法中Proposer的处理逻辑,根据上面的内容,一个Acceptor可能会收到来自Proposer的两种请求,分别是Prepare请求和Acceptor请求,对着两类请求做出响应的条件分别如下。

  • Prepare请求:Acceptor可以在任何时候响应一个Prepare请求。
  • Accept请求:在不违背Accept现有承诺前提表,可以任意响应Accept请求。

因此,对于Acceptor逻辑处理的约束条件,大体可以定义如下。

P1a:一个Acceptor只要尚未响应过任何编号大于Mn的Prepare请求,那么就可以接受这个编号为Mn的提案。

内容来自《从Paxos到Zookeeper分布式一致性原理与实践》 作者:倪超


上一篇 dubbo基础学习

评论