Distributed Systems-2PC和3PC

  1. 云栖社区>
  2. 博客>
  3. 正文

Distributed Systems-2PC和3PC

feilengcui008 2016-01-21 20:35:31 浏览930
展开阅读全文
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/feilengcui008/article/details/50557511

这篇文章主要讨论下解决分布式一致性问题的两种算法:两阶段提交(2PC)和三阶段提交(3PC)。之前感觉2PC和3PC的流程挺简单的,但是真正仔细去分析过后,才发现很多的细节。而这些细节对理解Paxos,Raft,Viewstamp Replication,Atomic Broadcast等其他更复杂的一致性算法有很大的作用。所以才在此记录一下这些细节,尤其是从工程实现的角度来思考。

具体的术语,像coordinator,participant具体指代什么,不熟悉的可以参考其他讲2PC和3PC的文章。

1.正常交互流程

这里的正常是指coordinator和participant没有挂掉的。交互流程如下所示,比较容易理解。

2PC

  • (1). coordinator ——(proposal)—–> all participants
  • (2). all participants —-(accept/refuse)———-> coordinator
  • (3.1). if any of participants is refuse, then coordinator ——-(abort)——–> all participants
    (3.2). else coordinator ——-(commit)——-> all participants

3PC

  • (1). coordinator ——(proposal)—–> all participants
  • (2). all participants —-(accept/refuse)———-> coordinator
  • (3.1). if any of participants is refuse, then coordinator ——-(cancel)——–> all participants
    (3.2). else coordinator ——-(prepare-commit)——-> all participants
  • (4). all participants ——(prepare-commit-received)——> coordinator
  • (5). if coordinator received prepare-commit-received from all participants then coordiantor —(commit)—> all participants

2.有挂掉的情况

2PC和3PC很多细节其实是在这一部分,因为在不同时间点(阶段),不同类型节点挂掉的情况下,能不能recover以及recover的结果都是不一样的(也就是容错,比如fail-recover,fail-stop,network partition等的程度不同)。我觉得严格来讲,对于coordinator和participants的挂掉的不同组合以及相应的恢复策略,应该用各自接收和发送消息的时间点严格定义,而不是笼统地说阶段1,阶段2等。由于组合情况比较多,而且有些情况的recover方式相同,这里就简单总结分类一下。

2PC和3PC最主要的区别在于coordinator挂掉的情况下,如果存在participant挂掉,那么能不能recover保证liveness(或者整个系统progress)的问题。对于2PC来说是不能的,对于3PC来说是可以的,而prepare-commit阶段起了决定性作用,这一点后面会详细分析。

2PC 有节点挂掉的可能情况(主要以coordinator的视角)

  • (1).coordinator在未发送proposal消息给任何participant以及之前挂掉了
  • (2).coordinator在给一部分participant发送proposal消息后挂掉
  • (3).coordinator在给所有participant发送proposal消息,但是没有发送所有commit/abort消息的情况下挂掉了
  • (4).coordinator在发送所有commit/abort后挂掉
    上述(1)和(4)是相同的情况,对于(2)recover处理比较简单,对于(3)比较麻烦,因为participants可能存在一种状态,是在有至少一个participant挂掉的情况下,整个事务状态是无法确定的。下面具体分析。

2PC coordinator recovery

这里不讨论所有participant都返回(即没有participant挂掉的情况),因为只要所有的participant都返回了,判断事务的状态就能确定了

  • 新的coordinator向剩余的所有participant发送query请求,获得其最后一条日志记录
    • 如果返回至少一个refuse,则新的coordinator abort
    • 如果返回至少一个commit,则新的coordinator commit
    • 导致可能出现不一致的情况:如果其中有一个participant挂掉没返回,而且其他节点都返回accept,这种情况下,新的coordinator无法决定是abort还是commit,因为挂掉的节点可能处于accept/refuse/commit/abort的任何一个状态,如果coordiantor commit或者abort了,都可能导致次participant恢复后与其余participant不一致。2PC最主要的限制就在这一点

3PC 有节点挂掉的可能情况(主要以coordinator的视角)

  • (1).coordinator在未发送proposal消息给任何participant以及之前挂掉了
  • (2).coordinator在给一部分participant发送proposal消息后挂掉
  • (3).发送全部proposal消息,但是没有发送全部prepare-commit/cancel消息
  • (4).发送全部prepare-commit消息,但是没有发送全部commit消息
  • (5).发送全部commit消息。

3PC coordinator recovery

这里不讨论所有participant都返回(即没有participant挂掉的情况),因为只要所有的participant都返回了,判断事务的状态就能确定了

  • 新的coordinator向剩余的所有participant发送query请求,获得其最后一条日志记录
    • 如果返回至少一个refuse,则新的coordinator abort
    • 如果返回至少一个commit,则新的coordinator commit
    • 如果返回的所有节点中有一个不是prepare-commit,则可以安全地abort,因为不可能有节点进入commit(其实包含了第一种情况)
    • 如果返回的节点全部是prepare-commit,此时可能会有participant挂掉,但是其可能的状态为accept/prepare-commit/commit,这三种情况下此participant恢复的时候都能commit,所以此时新的coordinator可以决定提交,不会造成恢复后的不一致状态。这一点是与2PC最大的区别

3.总结

综上,最核心的还是recovery中2PC和3PC的最后一点,也是加入prepare-commit阶段后造成的本质区别。当然虽然3PC保证了participant挂掉的时候系统能够继续progress(也就是能容错),但是其也存在问题,比如在网络分区的时候,刚好coordinator所在的一部分能commit,但是另一部分重新选择coordinator后不能commit,这样分区恢复后会导致不一致,这种情况就是Paxos,Raft等算法能解决的,后面会结合这些更复杂一些的算法分析。其实,对于分布式一致性算法来说,了解其历史对了解算法本质是很有帮助的。

网友评论

登录后评论
0/500
评论
feilengcui008
+ 关注