2PC and 3PC

这篇文章主要讨论下解决分布式一致性问题的两种算法：两阶段提交(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等算法能解决的，后面会结合这些更复杂一些的算法分析。其实，对于分布式一致性算法来说，了解其历史对了解算法本质是很有帮助的。

时间： 2024-11-01 01:31:05

2PC and 3PC的相关文章

再谈2PC和3PC

之前的一篇文章感觉分析得不太完整,所以再记录点东西. 故障组合情况 对于多个节点且每个节点有多个可能状态参与的分布式系统来说,假设在有限的某个时间点上发生故障的概率为0,对于coordinator(proposer/master/leader等),在发送接收的一轮交互中,可能在发送消息前(t < t1),发送部分消息(t1 < t < t2),发送所有消息后并且接收消息前(t2 < t < t3),接收到部分消息(t3 < t < t4),接收到所有消息后发生故障

三：分布式事务一致性协议2pc和3pc

一:分布式一致性协议--->对于一个分布式系统进行架构设计的过程中,往往会在系统的可用性和数据一致性之间进行反复的权衡,于是就产生了一系列的一致性协议.--->长期探索涌现出一大批经典的一致性协议和算法.其中最著名的就是二阶段提交协议,三阶段提交协议和paxos算法. 二:2PC与3PC--->在分布式系统中,每一个机器节点虽然都能够明确知道自己在进行事务操作过程中的结果是成功或失败,但却无法直接获取到其他分布式节点的操作结果.因此,当一个事务操作需要跨越多个分布式节点的时候,为了保持事

关于分布式事务

一.普通事务与分布式事务 1.1 普通事务 普通事务就是一般所说的数据库事务,大家对数据库事务应该都很了解,这里再简单介绍下. 事务是数据库管理系统执行过程中的一个逻辑单位,由一个有限的数据库操作序列构成.当事务被提交给了DBMS(数据库管理系统),则DBMS(数据库管理系统)需要确保该事务中的所有操作都成功完成且其结果被永久保存在数据库中,如果事务中有的操作没有成功完成,则事务中的所有操作都需要被回滚,回到事务执行前的状态;同时,该事务对数据库或者其他事务的执行无影响,所有的事务都好像在独立的

浅谈分布式事务

现今互联网界,分布式系统和微服务架构盛行.一个简单操作,在服务端非常可能是由多个服务和数据库实例协同完成的.在一致性要求较高的场景下,多个独立操作之间的一致性问题显得格外棘手. 基于水平扩容能力和成本考虑,传统的强一致的解决方案(e.g.单机事务)纷纷被抛弃.其理论依据就是响当当的CAP原理.往往为了可用性和分区容错性,忍痛放弃强一致支持,转而追求最终一致性. 分布式系统的特性 在分布式系统中,同时满足CAP定律中的一致性 Consistency.可用性 Availability和分区容错性 P

Java中JDBC事务与JTA分布式事务总结与区别_java

Java事务的类型有三种:JDBC事务.JTA(Java Transaction API)事务.容器事务.常见的容器事务如Spring事务,容器事务主要是J2EE应用服务器提供的,容器事务大多是基于JTA完成,这是一个基于JNDI的,相当复杂的API实现.所以本文暂不讨论容器事务.本文主要介绍J2EE开发中两个比较基本的事务:JDBC事务和JTA事务. JDBC事务 JDBC的一切行为包括事务是基于一个Connection的,在JDBC中是通过Connection对象进行事务管理.在JDBC中,

分布式系统学习资料（ing）

一.理论知识 从ACID到CAP到BASE 2PC到3PC到Paxos到Raft到ISR 复制.分片和路由 副本更新策略 负载均衡算法及手段 二.数据库 笔者带你剖析淘宝TDDL--Matrix层的分库分表配置与实现 纠正文章关于分库分表规则的一点错误:<property name="dbRuleArray" value="(#id#.longValue() % 4096).intdiv(16)"/>这个规则,表示分4096张表,每个库16张表.因此,t

3PC

3PC,是Three-Phase Commit的缩写,即三阶段提交,是2PC的改进版,其二阶段提交协议的"提交事务请求"过程一分为二,形成了由CanCommit,PreCommit,do Commit三个阶段组成的事务处理协议. 阶段一:CanCommit 1.事务询问:协调者向所有的参与者发送一个包含事务内容的canCommit请求,询问是否可以执行事务提交操作,并开始等待各个参与者的响应. 2.各个参与者向协调者反馈事务询问的响应:参与者在接收到来自协调者的canCommit请求后

Oracle分布式事务和两阶段提交(2PC)

分布式事务是指发生在多台数据库之间的事务,Oracle中通过dblink方式进行事务处理, 分布式事务比单机事务要复杂的多.大部分的关系型数据库通过两阶段提交(2 Phase Commit 2PC)算法来完成分布式事务,下面重点介绍下2PC算法. 1.分布式事务的 组成 在分布式事务中,主要有以下几个组成部分: Client:调用其它数据库信息的节点 Database:接受来自其它节点请求的节点 Global Coordinator (GC):发起分布式事务的节点 Local Coordinat

PostgreSQL 忘记提交2PC事务对数据库造成的危害.

我在数据库中开启了一个2PC事务,但是不去管他,会发生什么呢?有什么危害? postgres=# begin; BEGIN postgres=# insert into t6 values (1); INSERT 25622 1 postgres=# prepare transaction 'a'; PREPARE TRANSACTION postgres=# select * from txid_current_snapshot(); txid_current_snapshot -------