分布式相关理论和分布式事务

2018-12-20  本文已影响0人  鱼_乐

原文地址: https://blog.wangriyu.wang/2018/06-Distribution.html

简书上传不了 svg 格式的图片吗?! 图文可以去原文看 😅

分布式系统理论

CAP 定理

CAP 定理指出对于一个分布式系统来说,不可能同时满足以下三点:

一个分布式系统里面,节点组成的网络本来应该是连通的。然而可能因为一些故障或者延时,使得有些节点之间不连通了,整个网络就分成了几块区域。数据就散布在了这些不连通的区域中,这就叫分区。当你一个数据项只在一个节点中保存,那么分区出现后,和这个节点不连通的部分就访问不到这个数据了。这时分区就是无法容忍的。提高分区容忍性的办法就是将一个数据项复制到多个节点上,那么出现分区之后,这一数据项就可能分布到各个区里,容忍性就提高了。然而,要把数据复制到多个节点,就会带来一致性的问题,就是多个节点上面的数据可能是不一致的。要保证一致,每次写操作就都要等待全部节点写成功,而这等待又会带来可用性的问题。总的来说就是,数据存在的节点越多,分区容忍性越高,但要复制更新的数据就越多,一致性就越难保证。为了保证一致性,更新所有节点数据所需要的时间就越长,可用性就会降低 -- 来自知乎邬江的回答

CAP 理论实际想表达的是任何分布式系统不能同时满足强一致性、高可用性和较好的分区容错性

[图片上传失败...(image-bb9105-1545273484228)]

RDBMS: Relational Database Management System,关系型数据库管理系统

由 CAP 定理可知数据库的设计需要权衡取舍,所以可以把数据库大致分为三类:

分布式和集群的区别:

分布式: 不同的多台服务器上面部署不同的服务模块,他们之间通过 Rpc/HTTP 等方式进行通信和调用,对外提供服务和组内协作

集群: 不同的多台服务器上面部署相同的服务模块,通过分布式调度软件进行统一的调度,对外提供服务和访问

ACID 和 BASE

ACID

ACID 指的是传统数据库中事务操作所具备的四个特性:

BASE

BASE 理论是对 CAP 理论的延伸,核心思想是虽然无法做到强一致性 (Strong Consistency),但可以采用适合的方式达到最终一致性 (Eventual Consitency)

BASE 包含三部分:

两者区别

ACID 隶属于 CA,是传统数据库常用的设计理念,追求强一致性模型

BASE 隶属于 AP,支持的是大型分布式系统,提出通过牺牲强一致性获得高可用性

但在实际的分布式场景中,不同业务单元和组件对数据一致性的要求是不同的,因此在具体的分布式系统架构设计过程中,ACID 特性与 BASE 理论往往会结合在一起使用。比如整体满足 BASE,局部满足 ACID。

一致性模型

上述最终一致性的不同方式可以进行组合,例如单调读一致性和读己之所写一致性就可以组合实现。并且从实践的角度来看,这两者的组合,读取自己更新的数据,和一旦读取到最新的版本不会再读取旧版本,对于此架构上的程序开发来说,会少很多额外的烦恼。

从服务端角度,如何尽快将更新后的数据分布到整个系统,降低达到最终一致性的时间窗口,是提高系统的可用度和用户体验非常重要的方面。

为了解决分布式的一致性问题,出现了很多一致性协议和算法,比如二阶段提交协议,三阶段提交协议和 Paxos 算法

FLP 不可能定理

异步通信场景,即使只有一个进程失败了,也没有任何算法能保证非失败进程能够达到一致性。

异步通信与同步通信的最大区别是没有时钟、不能时间同步、不能使用超时、不能探测失败、消息可任意延迟、消息可乱序

FLP Impossibility 的证明

分布式事务

分布式事务用于在分布式系统中保证不同节点之间的数据一致性,通常会涉及到多个数据库。分布式事务处理的关键是必须有一种方法可以知道事务在任何地方所做的所有动作,提交或回滚事务的决定必须产生统一的结果(全部提交或全部回滚)。

DRDA: Distributed Relational Database Architecture,分布式关系数据库架构

XA 规范

XA 规范是 X/Open 组织(即现在的 Open Group) 关于分布式事务处理 (DTP) 模型的处理规范。

DTP 模型包括应用程序 AP事务管理器 TM资源管理器 RM通信资源管理器 CRM 四部分。常见的事务管理器 TM 是交易中间件,常见的资源管理器 RM 是数据库,常见的通信资源管理器 CRM 是消息中间件。交易中间件是必需的,由它通知和协调相关数据库的提交或回滚。

规范描述了全局的事务管理器与局部的资源管理器之间的接口。XA 规范的目的是允许的多个资源(如数据库,应用服务器,消息队列,等等)在同一事务中访问,这样可以使 ACID 属性跨越应用程序而保持有效。

XA 使用两阶段提交或三阶段提交来保证所有资源同时提交或回滚任何特定的事务

两阶段提交-2PC

当一个事务跨越多个节点时,为了保持事务的 ACID 特性,需要引入一个作为协调者的组件来统一掌控所有节点(称作参与者)的操作结果并最终指示这些节点是否要把操作结果进行真正的提交。所以两阶段提交 (Two-phase Commit) 的算法思路可以概括为: 参与者将操作成败通知协调者,再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。

两阶段提交需要的条件:

  1. 分布式系统中,存在一个节点作为协调者 (Coordinator),其他节点作为参与者 (Cohorts),且节点之间可以进行网络通信
  2. 所有节点都采用预写式日志,且日志被写入后即被保持在可靠的存储设备上,即使节点损坏不会导致日志数据的消失
  3. 所有节点不会永久性损坏,即使损坏后仍然可以恢复

两个阶段分别为:

  1. 准备阶段(投票阶段)
  2. 提交阶段(执行阶段)

准备阶段

  1. 事务协调者(事务管理器)给每个参与者(资源管理器)发送 Prepare 消息,询问是否可以执行提交操作,并开始等待各参与者节点的响应
  2. 参与者执行事务操作,并将 Undo 信息和 Redo 信息写入日志
  3. 各参与者节点响应协调者节点发起的询问。如果参与者节点的事务操作实际执行成功,则它返回一个"同意" (agreement) 消息;如果参与者节点的事务操作实际执行失败,则它返回一个"中止" (Abort) 消息

[图片上传失败...(image-41b4a6-1545273484228)]

第一阶段也被称作投票阶段,即各参与者投票是否要继续接下来的提交操作

提交阶段

[图片上传失败...(image-9f15ac-1545273484228)]

[图片上传失败...(image-181417-1545273484228)]

不管最后结果如何,第二阶段都会结束当前事务

缺陷

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

2、单点故障。由于协调者的重要性,一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段,协调者发生故障,那么所有的参与者还都处于锁定事务资源的状态中,而无法继续完成事务操作。(如果是协调者挂掉,可以重新选举一个协调者,但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题)

3、数据不一致。在第二阶段中,当协调者向参与者发送 commit 请求之后,发生了局部网络异常或者在发送 commit 请求过程中协调者发生了故障,这会导致只有一部分参与者接受到了 commit 请求。而在这部分参与者接到 commit 请求之后就会执行 commit 操作。但是其他部分未接到 commit 请求的机器则无法执行事务提交,于是整个分布式系统便出现了数据不一致的现象

4、二阶段提交存在一个无法解决的问题:

对于现有模型,可能会出现的错误和相应的措施如下

关于第三个问题的详细描述如下:

[图片上传失败...(image-c43b4a-1545273484228)]

协调者挂了,RM3 也挂了,此时分两种情况,RM3 是否执行了最后的事务操作:

最后这个问题就是 2PC 无法解决的问题,但 3PC 可以一定程度上解决

三阶段提交-3PC

三阶段提交 (Three-phase Commit) 是针对两阶段缺点而设计的改进型,相比较两阶段提交,做出以下两点改动:

  1. 引入超时机制。同时在协调者和参与者中都引入超时机制(2PC 只有协调者设置了超时机制),超时后可以默认执行 Commit 或者 Abort,这一点可以避免事务资源长时间被阻塞
  2. 在第一阶段和第二阶段中插入一个准备阶段。保证了在最后提交阶段之前各参与节点的状态是一致的

三个阶段分为:

  1. CanCommit
  2. PreCommit
  3. DoCommit

CanCommit

  1. 协调者向参与者发送 CanCommit 请求。询问是否可以执行事务提交操作。然后开始等待参与者的响应
  2. 参与者接到 CanCommit 请求之后,正常情况下,如果其自身认为可以顺利执行事务,则返回 Yes 响应,并进入预备状态。否则反馈 No

[图片上传失败...(image-1618d1-1545273484228)]

PreCommit

[图片上传失败...(image-7bd5b9-1545273484228)]

此图中如果某条 PreCommit 消息未到达或者超时,RM 应该中断自己本地的事务,就跟下图中 Abort 超时一样

[图片上传失败...(image-ea0c4f-1545273484228)]

DoCommit

根据情况分为两种情形:

[图片上传失败...(image-508d8f-1545273484228)]

[图片上传失败...(image-8ad1fa-1545273484228)]

图中 RM3 在第二阶段未正常响应 ACK,可能有如下情况:

在第三阶段,如果参与者无法及时接收到来自协调者的 DoCommit 或者 Abort 请求时,会在等待超时之后,会继续进行事务的提交

这么做是有一定考究的,因为能进入第三阶段,说明协调者肯定在第二阶段发起了 PreCommit 请求,而发起 PreCommit 请求的前提是第一阶段所有参与者都响应了 Yes,这表明所有参与者当时的状态都是乐观的,那么第三阶段参与者就算没有按时收到来自协调者的 DoCommit 请求,也继续完成本地事务的提交,这样完成全局事务的可能性还是很大的,这一点是针对 2PC 数据不一致问题的

但是这一点也会造成 3PC 的一致性缺陷: 如果此时是协调者对某个 RM 发出的 Abort 请求超时,而那个 RM 继续完成本地事务的提交,这就会造成与其他进行回滚操作的节点数据不一致(这种情况概率较小)

缺陷

对应 2PC 的缺陷,我们可以看到 3PC 解决了不少问题,一方面默认的超时机制可以避免单点故障造成的资源长久阻塞的问题;另一方面状态确认和默认超时提交也可以解决 2PC 的数据不一致问题(虽然这会造成 3PC 自己的不一致问题,但是因为 3PC 的机制,这种概率更小)

至于前面提到的 2PC 无法解决的问题,3PC 又是怎么解决的呢?

我们可以回想 2PC 的问题,冲突的条件就是 RM3 第一阶段投了反对票,而这件事只有原协调者知道,挂掉的两者执行了回滚操作,而新协调者和正常节点会执行提交操作;但是 3PC 将准备阶段分为两步可以确保最终事务操作之前,大家都知道投票结果,描述如下:

[图片上传失败...(image-85e40a-1545273484228)]

其实只要没有执行事务最终的提交或者回滚都不影响最终结果,只要后面 RM3 恢复后查询协调者并执行相同的操作即可

[图片上传失败...(image-68f35a-1545273484228)]

这时候新协调者出现后,只要查看正常节点的状态就可以知道发送提交还是回滚指令: 如果都是 Commited 或者 PreCommit 状态,说明第一轮投票结果都是 Yes,否则不可能进入 PreCommit 状态,所以新协调者发送提交指令即可;如果存在节点的状态是 Cancel,说明第一轮投票结果有反对票,那么新协调者发送回滚指令即可。可能这里会有个疑问,讲 DoCommit 的时候我们说过第二阶段参与者的 ACK 可能无法正常响应协调者,如果是 RM3 第一轮投了支持票后面进入 PreCommit 状态时没有把 ACK 正常响应给协调者,因此协调者发送了 Abort 指令给 RM3 后挂了,RM3 收到指令后也挂了,此时还是会造成 RM3 回滚,而新协调者和正常节点执行提交的状况,这里其实 3PC 好像也没法解决,但是这种情况的概率你可以估算一下,本来协调者发送指令挂了然后某些参与者执行后也挂了的概率本身就低了,还要满足挂的协调者在投完支持票后响应超时引起协调者发送 Abort 指令的概率,那就更小了

理解 2PC 和 3PC

我们用一个实际生活的例子来说明并理解这个过程:

假设协调者是牧师,而参与者是一男一女,他们来到教堂单独跟牧师见面并传达是否想跟另一方建立更深的关系的信息

2PC

第一步男女双方给牧师递了小纸条,上面写着是否想跟另一方建立更深的关系,并且各自准备好了信物 (Undo&Redo)

第二步牧师看过之后,如果双方都写“是”,那么告知双方交换信物表示可以继续深交;如果有一方写“否”,那么告知双方分手吧,信物也撤了吧

但是这里 2PC 无法解决一个问题: 假如男方写的纸条信息是“否”,而牧师看过之后先告诉男方你把信物撤了吧,你们不合适,但是牧师紧接着心脏病犯了住院了,而男方收到消息后也撤了信物准备分手,可是男方突然被人打了住院昏迷;新牧师出现,继续询问女方的意见,因为不知道男方的意见,他们可能会促成一桩不美满的关系

3PC

第一步男女双方还是递了小纸条,表示自己的意愿

第二步牧师看过之后,如果双方都写“是”,那么先告知双方准备信物;如果有一方写“否”,那么告知双方不用准备信物了;双方收到消息后再回应说自己知道了

第三步牧师确认双方的回应后,告知双方最后是否在一起,是否交换信物

在这里假如第三步牧师也是先告知男方后突发心脏病住院,而男方也是收到消息后被打昏迷,此时新牧师出现后可以查看女方是否准备了信物而完成最后的决定,因为假如男方原本是不同意,那么第二步双方肯定是没有准备信物的,而假如男方是同意的,那么双方肯定是准备了信物的,那么新牧师可以放心宣布双方可以在一起

3PC 还对双方都引入了超时,2PC 中只有牧师没收到消息时会取消事务,而 3PC 中如果男女双方长时间没有收到牧师消息后也会执行自己的决定,避免了 2PC 中同样情形时男女双方在这里一直耗着(阻塞)而错过了下一任。只不过我们提到了如果第三步牧师是因为长时间没有收到男方的消息时也取消了事务,虽然这时候男女双方都是同意的,但是还是会被取消事务,这也可能造成新的不一致问题,但是相对来说概率就小得多了

解决不一致问题

通过上述过程可知最后无论是二阶段提交还是三阶段提交都无法彻底解决分布式的一致性问题,如果系统正常运行都能满足强一致性,但是如果出现意外还是会导致不一致,不过可以通过其他手段达到一致性,比如分区数据恢复或者事务补偿机制或者采用其他一致性算法

分区数据恢复

Partition-Recover

复杂的数据恢复可以参见 SVN 的版本控制,可能可以自动合并,也可能会发生冲突然后需要人工干预

简单的数据恢复可以参见 Mysql 的主从同步,数据可以自动从主库导到从库

合并分区数据达成一致并不是最困难的,更困难的是处理分区过程中产生的错误。当分区操作引起错误,可以通过事务补偿补救错误,这可能是人工的也可能是自动的

分区事务补偿

比如 MQ 消息事务和 TCC 事务协议就是一种补偿机制:

其他一致性算法

Reference

上一篇 下一篇

猜你喜欢

热点阅读