分布式协议与算法实战01

标签:无 1545人阅读 评论(0)

分布式协议与算法实战01

1. 拜占庭将军问题

拜占庭将军问题是一个协议问题,拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的,并且将军中存在叛徒。叛徒可以任意行动以达到以下目标:欺骗某些将军采取进攻行动;促成一个不是所有将军都同意的决定,如当将军们不希望进攻时促成进攻行动;或者迷惑某些将军,使他们无法做出决定。如果叛徒达到了这些目的之一,则任何攻击行动的结果都是注定要失败的,只有完全达成一致的努力才能获得胜利。

拜占庭假设是对现实世界的模型化,由于硬件错误、网络拥塞或断开以及遭到恶意攻击,计算机和网络可能出现不可预料的行为。拜占庭容错协议必须处理这些失效,并且这些协议还要满足所要解决的问题要求的规范。这些算法通常以其弹性t作为特征,t表示算法可以应付的错误进程数。

口信消息型拜占庭问题之解:如果叛将人数为 m,将军人数不能少于 3m + 1 ,那么拜占庭将军问题就能解决了。前提是叛将人数 m,或者说能容忍的叛将数 m,是已知的。在这个算法中,叛将数 m 决定递归循环的次数(也就是说,叛将数 m 决定将军们要进行多少轮作战信息协商),即 m+1 轮(所以,你看,只有楚是叛变的,那么就进行了两轮)。从另外一个角度理解:n 位将军,最多能容忍 (n - 1) / 3 位叛将。

签名消息型拜占庭问题之解:通过签名机制约束叛将的叛变行为,任何叛变行为都会被发现,也就会实现无论有多少忠诚的将军和多少叛将,忠诚的将军们总能达成一致的作战计划。

2.CAP理论

CAP 理论对分布式系统的特性做了高度抽象,形成了三个指标:一致性(Consistency)、可用性(Availability)分区容错性(Partition Tolerance)。

一致性说的是客户端的每次读操作,不管访问哪个节点,要么读到的都是同一份最新写入的数据,要么读取失败。一致性这个指标,描述的是分布式系统非常重要的一个特性,强调的是数据正确。也就是说,对客户端而言,每次读都能读取到最新写入的数据。

可用性说的是任何来自客户端的请求,不管访问哪个非故障节点,都能得到响应数据,但不保证是同一份最新数据。你也可以把可用性看作是分布式系统对访问本系统的客户端的另外一种承诺:我尽力给你返回数据,不会不响应你,但是我不保证每个节点给你的数据都是最新的。这个指标强调的是服务可用,但不保证数据正确。可用性说的是任何来自客户端的请求,不管访问哪个非故障节点,都能得到响应数据,但不保证是同一份最新数据。你也可以把可用性看作是分布式系统对访问本系统的客户端的另外一种承诺:我尽力给你返回数据,不会不响应你,但是我不保证每个节点给你的数据都是最新的。这个指标强调的是服务可用,但不保证数据正确。

分区容错性说的是,当节点间出现任意数量的消息丢失或高延迟的时候,系统仍然在继续工作。也就是说,分布式系统在告诉访问本系统的客户端:不管我的内部出现什么样的数据同步问题,我会一直运行。这个指标,强调的是集群对分区故障的容错能力。因为分布式系统与单机系统不同,它涉及到多节点间的通讯和交互,节点间的分区故障是必然发生的,所以在分布式系统中分区容错性是必须要考虑的。

CAP 不可能三角说的是对于一个分布式系统而言,一致性(Consistency)、可用性(Availability)、分区容错性(Partition Tolerance)3 个指标不可兼得,只能在 3 个指标中选择 2 个。

图片 1.png

   现在就只剩下一致性(C)和可用性(A)可以选择了:要么选择一致性,保证数据正确;要么选择可用性,保证服务可用。那么 CP 和 AP 的含义是什么呢?当选择了一致性(C)的时候,一定会读到最新的数据,不会读到旧数据,但如果因为消息丢失、延迟过高发生了网络分区,那么这个时候,当集群节点接收到来自客户端的读请求时,为了不破坏一致性,可能会因为无法响应最新数据,而返回出错信息。当选择了可用性(A)的时候,系统将始终处理客户端的查询,返回特定信息,如果发生了网络分区,一些节点将无法返回最新的特定信息,它们将返回自己当前的相对新的信息。

其实,在不存在网络分区的情况下,也就是分布式系统正常运行时(这也是系统在绝大部分时候所处的状态),就是说在不需要 P 时,C 和 A 能够同时保证。只有当发生分区故障的时候,也就是说需要 P 时,才会在 C 和 A 之间做出选择。而且如果读操作会读到旧数据,影响到了系统运行或业务运行(也就是说会有负面的影响),推荐选择 C,否则选 A。

3. ACID理论——一致性

为了保证执行过程中的一致性,

二阶段提交协议最早是用来实现数据库的分布式事务的,不过现在最常用的协议是 XA 协议。这个协议是 X/Open 国际联盟基于二阶段提交协议提出的,也叫作 X/Open Distributed Transaction Processing(DTP)模型,比如 MySQL 就是通过 MySQL XA 实现了分布式事务。但是不管是原始的二阶段提交协议,还是 XA 协议,都存在一些问题:在提交请求阶段,需要预留资源,在资源预留期间,其他人不能操作(比如,XA 在第一阶段会将相关资源锁定);数据库是独立的系统。

TCC(Try-Confirm-Cancel):

实际上是服务化的两阶段提交协议。

两阶段提交协议:事务管理器分两个阶段来协调资源管理器,第一阶段准备资源,也就是预留事务所需的资源,如果每个资源管理器都资源预留成功,则进行第二阶段资源提交,否则协调资源管理器回滚资源。

2PC协议的核心是,划分出了事务参与者和协调者的角色,并将整个过程划分成两个阶段:

第一阶段:所有事务参与者,执行后进行预提交;直到协调者收到所有参与者的预提交才会进入第二步;如果在协调者的超时时间内,有任意参与者的预提交preCommit没发送或未到达,都会结束事务。

第二阶段:所有事务预提交了各自的结果后,由协调者决定最终事务是成功(commit)还是失败(rollback)。

二阶段提交看起来确实能够提供原子性的操作,但是不幸的事,二阶段提交还是有几个缺点的:

1.执行过程中,所有参与节点都是事务阻塞型的。当参与者占有公共资源时,其他第三方节点访问公共资源不得不处于阻塞状态。

2.参与者发生故障。协调者需要给每个参与者额外指定超时机制,超时后整个事务失败。(没有多少容错机制)

3.协调者发生故障。参与者会一直阻塞下去。需要额外的备机进行容错。(这个可以依赖后面要讲的Paxos协议实现HA)

4.二阶段无法解决的问题:协调者再发出commit消息之后宕机,而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者,这条事务的状态也是不确定的,没人知道事务是否被已经提交。

4. BASE理论——可用性

BASE 理论是 CAP 理论中的 AP 的延伸,是对互联网大规模分布式系统的实践总结,强调可用性。它的核心就是基本可用(Basically Available)和最终一致性(Eventually consistent)。

在现实情况中,实现流量基本可用一般有四种方法:流量削峰、延迟响应、体验降级和过载保护。

最终一致性是指,系统中所有的数据副本在经过一段时间的同步后,最终能够达到一个一致的状态。也就是说,在数据一致性上,存在一个短暂的延迟。

实现最终一致性的方法:一般来说,有两种。一种是以最新写入的数据为准,另外一种是以第一次写入的数据为准。实现最终一致性的具体方式常用的有3种:

读时修复:在读取数据时,检测数据的不一致,进行修复。比如 Cassandra 的 Read Repair 实现,具体来说,在向 Cassandra 系统查询数据的时候,如果检测到不同节点的副本数据不一致,系统就自动修复数据。

写时修复:在写入数据,检测数据的不一致时,进行修复。比如 Cassandra 的 Hinted Handoff 实现。具体来说,Cassandra 集群的节点之间远程写数据的时候,如果写失败就将数据缓存下来,然后定时重传,修复数据的不一致性。

异步修复:这个是最常用的方式,通过定时对账检测副本数据的一致性,并修复。


查看评论

暂无评论

发表评论
  • 评论内容:
      
首页
团队介绍
发展历史
组织结构
MESA大事记
新闻中心
通知
组内动态
科研成果
专利
论文
项目
获奖
软著
人才培养
MESA毕业生
MESA在读生
MESA员工
招贤纳士
走进MESA
学长分享
招聘通知
招生宣传
知识库
文章
地址:北京市朝阳区华严北里甲22号楼五层 | 邮编:100029
邮箱:nelist@iie.ac.cn
京ICP备15019404号-1