再谈2PC和3PC

简介:

之前的一篇文章感觉分析得不太完整,所以再记录点东西。

故障组合情况

对于多个节点且每个节点有多个可能状态参与的分布式系统来说,假设在有限的某个时间点上发生故障的概率为0,对于coordinator(proposer/master/leader等),在发送接收的一轮交互中,可能在发送消息前(t < t1),发送部分消息(t1 < t < t2),发送所有消息后并且接收消息前(t2 < t < t3),接收到部分消息(t3 < t < t4),接收到所有消息后发生故障(t > t4);对于每个participant(acceptor/follower/slave)来说,在接收发送的一轮交互中,可能在接收消息前(t’ < t1’),接收到消息且未发送应答(t1’ < t’ < t2’),发送应答后(t’ > t2’)发生故障。

coordinator和participants在不同的时间段发生故障的组合会有不同的能够保持全局事务状态一致的故障发生时行为以及恢复策略,而且可能不存在能保持全局事务状态一致的相应行为以及恢复策略。对于发生故障时的行为,在程序实现上我们必须用上面提到的时间段来分析,而且假定coordinator广播消息这个动作的过程中不会出现故障(这其实是比较合理的,因为即使只发送了部分消息也可以看做是有一部分participants没有收到消息,这两种情况对于最终的系统全局状态是一样的),这样程序实现上相应能简化不少。而对于故障恢复的策略以及正确性,我们可以从有节点发生故障后最终整个系统可能处于的全局状态来详细分析论证,虽然对于n个参与节点来说,其状态组合指数级增长,但是其中大多数状态可以用全称量词和存在量词描述,因为很多状态对于恢复策略是一样的。下面以2PC和3PC为例来分析,从中可以比较容易地看出2PC存在的问题,以及3PC为什么能够解决这个问题。2PC和3PC的正常流程可以参考相应的资料,这里不赘述。
这里写图片描述

这里写图片描述

故障模型

首先我们这里只考虑fail-recover的故障模型

我们只考虑在有coordinator以及participant挂掉的情况,而且coordinator本身不具有participant的身份。对于没有participant挂掉但是coordinator挂掉的情况,只需要选择新的coordinator并向所有存活的participant发送最后一条日志记录的请求就可以确定发生故障时全局事务的状态,从而恢复,所以比较简单。对于有paticipant挂掉以及coordinator没有挂掉的情况,由于coordinator知道所有participants的响应消息,所以可以决定此次事务的最终状态,可能会阻塞等待participant的恢复,但不会造成不一致。

举一个coordinator没有故障但是paticipant故障的例子:对于2PC的阶段一(即有部分participant还未收到coordinator的proposal消息),如果coordinator未发生故障,但是有participant发生故障,这种情况下,只需要取消此次proposal即可,等到故障的participant恢复后询问coordinator要相应的日志记录,不会造成最终全局事务状态的不一致。(这里关于整个系统能不能progress可能有不同说法,如果我们将故障的participant移除coordinator活跃列表那么接下来的事务(如果这里的事务只是单纯的replication)可以正常进行,但是如果分布式事务本身必须要故障的participant参与,那么整个系统必须阻塞直到participant恢复,但总之不会造成恢复后系统全局状态的不一致)。


2PC故障恢复分析

下面考虑coordinator和participant故障的情况:

  • 1.对于2PC的阶段一(即有部分participant还未收到coordinator的proposal消息)

    • 此时新选出的coordinator询问剩余存活节点的消息后可以直接cancel,因为不可能有节点commit
  • 2.对于2PC的阶段二,情况稍微复杂,故障发生时,所有剩余存活节点可能的状态只能是accept/refuse/commit/abort中的一个,并且只有以下组合

    • (1).存活节点中返回accept的数量满足0 <= n < N(存活节点总数)

      • a. n中除去accept的剩余全是commit => commit

      • b. n中除去accept的剩余全是abort => abort

      • c. n中除去accept的全是refuse => abort

      • d. n中除去accept的剩余部分是abort,部分是abort => abort

    • 以上几种情况下新的coordinator的abort/commit选择在故障节点恢复后都不会造成不一致。

    • (2).存活节点全部返回accept,即n == N

      • 此时故障的participant可能处于的状态有:

        • a. accept

        • b. refuse

        • c. commit

        • d. abort

    • 可以看出,无论新的coordiantor选择commit还是abort,最终participant恢复时有可能是abort或者commit,这样会导致不一致,所以整个系统只有等故障participant恢复之后,新的coordinator才可能继续,整个系统才可能progress。这也是导致2PC缺陷的根本原因。

    • 综合(1)(2)两种情况,在(2)中由于故障的节点可能成为唯一接收到commit/abort消息的节点,所以从剩余节点中我们没办法知道整个系统的状态。因此3PC引入了prepare-commit阶段,在真正提交(commit阶段)之前,让所有节点都能知道整个系统的状态是可以提交(即coordinator收到所有accept)还是cancel(abort,即coordinator没有收到所有accept),然后在commit阶段,如果有节点挂掉了,也可以通过其他其他节点得知整个系统此次事务投票的状态,从而progress。


3PC故障恢复分析

  • 1.对于3PC的阶段一(即有部分participant还未收到coordinator的proposal消息)

    • 此时新选出的coordinator询问剩余存活节点的消息后可以直接cancel,因为不可能有节点commit
  • 2.对于3PC的阶段二和阶段三,情况比较复杂,故障发生时,所有剩余存活节点可能的状态只能是accept/refuse/prepare-commit/cancel/commit中的一个,并且只有以下组合

    • (1).存活节点中返回accept的数量满足0 <= n < N(存活节点总数)

      • a. n中除去accept的全是refuse => abort

      • b. n中除去accept的全是cancel => abort

      • c. n中除去accept的部分是refuse,部分是cancel => abort

      • d. n(==0)中除去accept的全是prepare-commit => commit

      • e. n(==0)中除去accept的全是commit => commit

      • f. n(==0)中除去accept的部分是commit,部分是prepare-commit => commit

    • 可以看出,上述所有情况,新的coordinator都可以有确定的abort/commit选择,不会造成故障节点恢复后整个系统的不一致。

    • (2).存活节点全部返回accept,即n == N

      • 此时故障节点可能处于的状态有:
        • a. accept
        • b. refuse
        • c. prepare-commit
        • d. cancel
        • e. 不可能有commit(如果是commit那么必然所有存活的都是prepare-commit,这样就避免了2PC存在的问题!)
    • 可以看出,3PC引入prepare-commit阶段后,(2)中解决了2PC的问题。(2)中a,b,c,d四种可能情况下由于不可能出现故障节点commit的情况,所以新的coordinator都可以采取abort,从而在故障节点恢复后不会造成不一致状态。但是3PC的一个局限在于无法容忍网络分区:比如如果发生了网络分区,其中一部分的coordinator收到那一部分所有存活节点都是prepare-commit,那么会决定commit;但是另外一部分的coordinator收到的存活节点中全是accept,那么会决定abort。这样导致了整个系统状态的不一致。


总结

本文对于每种恢复情况都做了一定考虑,对于只有一个coordinator和participant的情况,我们可以画出系统的全局状态图,从而判断不同故障组合是否会导致状态转换的不确定结果,即最终的全局状态既有commit又有abort,上述的分析本质上也是将一些状态分了类。但是对于多节点的组合,感觉始终没有太严格地形式证明,在思考代码实现的时候也是总感觉不具有百分之百的说服力…状态组合爆炸也是并发与分布式的一个比较难的问题吧。

相关文章
|
5月前
|
监控 安全 Linux
基于PC的控制技术编程入门
基于PC的控制技术编程入门
|
6月前
感知偶然性(perceived contingency,PC)量表。
感知偶然性(perceived contingency,PC)量表。感知偶然性(Perceived Contingency,PC)量表是一种用于评估个体对事件之间关系的认知程度的量表。
77 0
|
9月前
|
安全
STM32 配置PC13~PC15
STM32 配置PC13~PC15
205 0
|
算法 关系型数据库 调度
你可能不知道的平时在用的一致性协议2PC、3PC?
在分布式系统中,当一个事务操作需要跨越多个分布式节点时,为了保持事务的ACID特性,就出现了“协调者(Coordinator)”来统一调度所有分布式节点的执行逻辑,而被调度的分布式节点则被称为“参与者(Cohort)”。协调者(Coordinator)负责调度参与者(Cohort)的行为,并最终决定这些参与者(Cohort)是否把事务真正进行提交。基于这个思想,衍生出2PC和3PC两种协议。
137 0
你可能不知道的平时在用的一致性协议2PC、3PC?
|
缓存 算法 关系型数据库
深入分布式缓存-2PC 3PC
深入分布式缓存-2PC 3PC
95 0
深入分布式缓存-2PC 3PC
|
缓存 前端开发 JavaScript
前端性能优化(PC版)(3)
前端性能优化(PC版)(3)
166 0
|
缓存 前端开发 JavaScript
前端性能优化(PC版)(2)
前端性能优化(PC版)(2)
99 0
|
存储 缓存 前端开发
前端性能优化(PC版)(1)
前端性能优化(PC版)(1)
146 0
|
编解码 JavaScript 前端开发
如何判断是pc端还是移动端
如何判断是pc端还是移动端
1338 0
|
编解码
只有PC可以玩原生4K《英灵殿》?你可能想多了
今年微软和索尼将推出次世代主机,育碧作为全球知名游戏厂商今年也有两款3A大作将要上市,《刺客信条:英灵殿》和《看门狗:军团》。
201 0
只有PC可以玩原生4K《英灵殿》?你可能想多了