分布式提交协议——2pc&3pc

以前在学习数据库理论时已经接触过事务的概念以及事务ACID特性，对于分布式事务，即涉及多个服务器的事务，其中一个很大的不确定性就是服务器和网络的故障情况。那么在分布式场景下我们有什么手段可以保证事务的原子性？

分布式事务

提起事务的一个很常见的例子便是银行的转账操作，比如A给B转账X元，需要将A的账户先减去X元，然后给B的账户加上X元。这个转账的多个操作便是事务。事务定义了一个服务器的操作序列，服务器需要保证在多个客户端和服务器出现故障时的原子性。

而分布式事务就是涉及到多个服务器的事务。还是以转账例子为例，在单机时数据库系统已经为我们保证了事务操作的原子性，但在分布式场景下，A和B的账户可能分布在不同的服务器上，这时候又该如何保证多个服务器之间的原子性？这便是分布式事务首先必须要解决的问题。

分布式提交

分布式提交关注的是原子性，它涉及到要使一个操作被进程组中的每个成员都执行或一个成员都不执行。这个操作，在可靠多播中是消息的发送，在分布式事务中对应的则是单个节点上的事务提交，它是整个事务的一部分。

分布式事务中涉及到的服务器使用原子提交协议来进行协作，以使服务器能够就是否可以提交或中止事务达成联合决策。其中最常用的原子提交协议是两阶段提交协议（2PC）。

通常在分布式提交中主要有两类角色：协作者和参与者。

单阶段提交协议（1PC）

这是一个最简单分布式提交方案，协作者只是简单的通知所有涉及到的参与者按要求执行操作即可。但该方案有个致命的缺陷，就是如果参与者不能执行某个操作，它没有办法通知协作者。如之前的提到的异步复制方案就相当于是单阶段提交：


单阶段提交协议的缺陷会破坏分布式事务所要求的原子性约束从而导致数据的不一致，在实际应用中我们需要更复杂的协议来进行分布式提交从而保证一致性。

两阶段提交协议（2PC）

两阶段提交协议（two–phase commit protocol）是一种原子提交协议，用来协调参与分布式事务的所有进程是否提交/终止事务。2PC之所以称之为两阶段，是因为进行事务的提交他需要经历两个阶段：准备阶段和提交阶段，而每个阶段又由两步组成。准备阶段分为询问和投票两步，提交阶段分为决策和完成两步。

  1. 准备阶段
    1. 询问：协调者询问每个参与者能够进行本地事务提交；
    2. 投票：参与者根据自身情况向协调者发送Yes/No消息；
  2. 提交阶段
    1. 决策：如果所有参与者回复Yes则协调者进行全局事务提交，否则全局中止事务；
    2. 完成：参与者根据协调者的结果进行事务的提交或回滚。

2PC状态及消息流转


阶段一：准备阶段（Prepare phase）

这个阶段也可以称为投票阶段或表决阶段。

  1. 协调者在接收到客户请求消息后进入INIT 状态，然后协调者对所有的参与者发送 QUERY_TO_COMMIT消息来询问参与者是否能够进行事务提交操作，然后从INIT状态进入 WAIT
    状态并等待所有参与者的回复消息；
  2. 参与者收到协调者的 QUERY_TO_COMMIT 消息后进入INIT状态并开始尝试进行本地事务提交：
    1. 如果成功则写redo和undo日志，然后从INIT状态进入READY状态，并向协调者回复一个 YES 消息表示接受事务；
    2. 如果失败则从 INIT 状态进入 ABORT 状态，并向协调者回复一个 NO 消息表示拒绝事务；

这个阶段的关键在步骤二，这里实际相当于是一阶段提交协议里面本地提交，只不过增加了一步即向协调者发送本次提交结果以方便协调者能够做出最终的决策，同时参与者并还没有进行最终的事务提交，它需要写redo和undo日志以方便事务的回滚，同时继续持有已申请的资源并等待协调者的最终指令。

阶段二：提交阶段（Commit phase）

这个阶段又称为决定阶段。协调者需要根据接收到的所有参与者的回复消息做出最终的决策：如果所有参与者的消息为YES则进行全局事务提交，否则只要有一个参与者回复NO消息则进行全局事务中止操作。

提交全局事务

  1. 协调者从 WAIT 状态进入 COMMIT 状态，并向所有的参与者发送 GLOBAL_COMMIT 消息并等待所有的参与者回应；
  2. 参与者接收到 GLOBAL_COMMIT 消息后进入 COMMIT 状态，根据日志对本地事务进行最终提交，释放锁等相关的资源，然后向协调者发送ACK消息表示事务已提交，并从 COMMIT 状态转为 DONE 状态；

中止全局事务

  1. 协调者从 WAIT 状态进入 ABORT 状态，并向所有的参与者发送 GLOBAL_ABORT 消息并等待所有的参与者回应；
  2. 参与者收到 GLOBAL_ABORT 消息后进入 ABORT 状态，根据日志回滚撤销之前的本地事务提交，释放锁等相关资源，然后向协调者发送 ACK 消息表示事务已中止，并从 ABORT 状态转为 DONE 状态；

协调者在接收到参与者的ACK消息后即可对客户返回操作结果了，同时标记全局事务完成，重新等待客户请求。实际上，协调者在做出全局表决之后就已经可以向客户返回操作结果了，而不必等到参与者回复ACK消息。

2PC的故障模型

2PC协议本身并复杂，可以说是相当的简单，在正常没有故障的情况下，它可以运行非常好。在学习2PC协议的时候一个容易被忽视的地方就是故障处理。接下来讨论的是协调者和参与者在不同状态下故障时可能导致的问题及解决方案。

首先，注意到协调者和参与者都具有等待消息的状态（协调者 WAIT 状态，参与者 READY 状态），因为只要一个进程的崩溃或消息的丢失都有可能导致无线等待的问题，因此需要使用超时机制。

  1. 协调者 INIT 状态奔溃恢复

    在INIT状态时，协调者可能已经向部分参与者发送了 QUERY_TO_COMMIT 消息，也可能一个也没有发送，则当期从奔溃中恢复之后，需要向所有的参与者重新发送 QUERY_TO_COMMIT 消息，参与者如果收到了重复的询问消息后需要进行幂等处理，即需要向协调者回复其之前做出的投票。

  2. 协调者在 WAIT 状态奔溃恢复

    协调者在 WAIT 状态时可能已经接收到部分参与者的投票了，也可能一个都没有收到就奔溃了，这时它从奔溃中恢复时可以简单的向所有参与者发送 GLOBAL_ABORT 消息中止事务即可。

  3. 协调者在 WAIT 状态等待某个参与者的投票超时

    协调者可以简单认为该参与者的投票为NO来直接中止事务。

  4. 协调者在 COMMIT/ABORT 状态奔溃恢复

    由于协调者可能还没来得及发送全部的 GLOBAL_COMMIT/GLOBAL_ABORT 消息就奔溃了，因此恢复后需要向所有的参与者从新发送全局表决消息。

协调者的奔溃处理要相对简单一些。接下来介绍的是参与者的故障处理：

  1. 参与者在 INIT 状态奔溃恢复

    这个时候协调者可能已经因为该参与者的投票消息超时而进行了全局事务的中止操作，因此参与者恢复后只需要简单粗暴的中止事务即可。

  2. 参与者在 COMMIT/ABORT 状态奔溃恢复

    此时参与者只需要简单重新进行本地事务的 COMMIT/ABORT 操作即可。

  3. 参与者在 READY 状态奔溃恢复

    由于这个时候协调者可能已经做出了全局表决，参与者不能简单直接进行事务的提交或中止，因此参与者恢复后的首要任务就是探知全局事务是否已提交还是中止：

    1. 参与者首先向协调者查询全局事务的状态，如果协调者正常工作则返回事务的全局状态；如果协调者奔溃或等待消息超时，则参与者只能向其它参与者进行询问；
    2. 假设该奔溃恢复的参与者为P，它向另外的参与者Q1查询事务的状态，如果Q1回复为中止，则P可以安全的进行事务中止操作；否则它需要继续向其它所有的参与者进行询问，只有当其它所有的参与者都回复已提交时P才可以进行事务提交操作；
    3. 如果其中某个参与者Q也奔溃了，那么P将无法做出决策，只能继续等待，此时2PC将无法继续正常工作，需要人工介入修复。
  4. 参与者在 READY 状态等待协调者的全局表决信息超时

    这是一个在实现2PC协议时很容易被错误实现的地方，从而导致脑裂问题，即参与者之间对事物的最终状态产生了分歧。

    部分实现中参与者在READY状态等待协调者的全局表决消息时超时会粗暴的认为事物提交失败而中止事务，这个时候可能协调者已经向其中的部分参与者发送了 GLOBAL_COMMIT 消息了，造成了部分参与者已经进行了事务提交，从而出现脑裂的问题。正确的处理方式是参考上面一条规则，应该把超时认为参与者奔溃恢复来处理。

    在很多文章中都会说脑裂问题是2PC的一个缺陷，其实这和2PC并没有必然关联，更多是实现者的实现不够严谨导致。

2PC的缺陷

从上面我们可以直观的感受到2PC是一个阻塞协议，这是其最大的缺点，在事务处理过程中，所有的参与者都处于阻塞状态，任意一个角色的故障都有可能导致协议一直处于阻塞状态。另一个问题是单点问题，最明显的是协调者的单点问题，并且任一节点（协调者或参与者）的失败都有可能导致协议失败。

三阶段提交协议

三阶段提交协议（three-phase commit protocol）是2PC的一个变种，主要是针对2PC的阻塞范围进行了优化。通过之前2PC的学习我们已经知道了2PC的一个主要问题便是阻塞，在投票阶段参与者就需要先在本地尝试进行事务的预提交操作来进入ready状态，而这种预提交操作在最终决策为中止事务时显得是非常浪费的；而ready状态又是一种不确定状态，事务涉及的任何一方异常都有可能导致参与者进入悬而未决的状态。而三阶段提交协议则是通过增加一个阶段来抉择这些问题的。

3PC的三个阶段

阶段一：投票阶段

  1. 事务询问

    协调者收到客户请求后进入INIT状态，然后所有的参与者发送一个包含事务内容信息的QUERY_TO_COMMIT消息进行事务询问请求，并从INIT状态转变为WAIT状态；

  2. 事务反馈

    参与者在收到协调者的 QUERY_TO_COMMIT 消息后进入INIT状态，并根据自身的当前状态信息对事务操作进行判断，如果能够进行后续的事务提交操作则锁定资源并向协调者发送YES消息进行反馈，同时进入READY状态，否则发送NO消息并直接进入ABORT状态；

阶段二：决策阶段或预提交阶段

协调者需要根据所有参与者的反馈消息来进行决策，如果所有参与者的反馈消息都是YES则执行预提交动作，否则只要有一个参与者反馈NO或超时失败则中止事务。

执行事务预提交

  1. 发送预提交请求

    协调者收到所有参与者的YES反馈消息后，然后向所有的参与者发送PREPARE_COMMIT消息指示参与者进行本地事务提交操作，并从WAIT状态转变为PRECOMMIT状态；

  2. 执行预提交操作

    参与者收到协调者发送的PREPARE_COMMIT消息后执行本地事务提交操作，然后给协调者发送YES消息进行反馈，并从READY转变为PRECOMMIT状态；

中止事务

  1. 发送全局事务中止请求

    协调者只要收到其中一个参与者的NO消息或这超时消息时，即可从WAIT状态直接变为ABORT状态，并给所有的参与者发送GLOBAL_ABORT消息指示中止事务操作；

  2. 执行事务中止操作

    参与者收到协调者发送的GLOBAL_ABORT消息后释放之前的资源中止事务，并进入ABORT状态。

阶段三：执行提交阶段

协调者在PRECOMMIT状态等待参与者的预提交反馈消息。

  1. 发送提交全局事务请求

    协调者接收到所有参与者的YES反馈消息后从PRECOMMIT状态转变为COMMIT状态，并向所有的参与者发送GLOBAL_COMMIT消息；

  2. 执行全局事务提交

    参与者接收到协调者发送的GLOBAL_COMMIT消息对本地事务确认进行最终提交，并从PRECOMMIT状态变为COMMIT状态，同时给协调者发送ACK消息进行反馈；

与2PC的关键区别

3PC相对去2PC的主要区别在于把2PC的阶段一再细分为投票和预提交两个阶段，之前2PC在阶段一进行投票YES的时候就会进行预提交操作，而3PC则不需要，仅仅只是需要先锁定事务依赖的资源即可，减少事务中止时的回滚阻塞时间。

3PC的故障模型

3PC的故障模型与2PC类似，但没有了2PC参与者在READY状态奔溃恢复或等待超时可能进入悬而未决的状态。

首先还是从协调者开始说起：

  1. 协调者在INIT或WAIT状态时奔溃，这时候部分参与者可能已经接收到了QUERY_TO_COMMIT消息并给协调者发送了YES消息进行反馈并进入READY状态，因此恢复后只需要简单的中止事务，并给所有的参与者发送GLOBAL_ABORT消息即可；
  2. 协调者在WAIT状态等待某个参与者的投票信息时超时，可以简单的认为参与者的投票为NO并进行全局事务中止操作；
  3. 协调者在PRECOMMIT状态奔溃，首先协调者处于PRECOMMIT状态表明所有参与者都向协调者发送的YES消息并已经进入READY状态，这意味着所有的参与者已经准备就绪可以进行事务提交操作，然而由于奔溃可能导致部分参与者没有收到协调者发送的PREPARE_COMMIT消息，因此恢复后需要重新向所有的参与者发送PREPARE_COMMIT消息；
  4. 协调者在PRECOMMIT状态等待某个参与者对PREPARE_COMMIT消息的应答时超时，由于这个时候所有的参与者只可能处于READY或PRECOMMIT状态，因此可以忽略这个超时直接向所有的参与者发送GLOBAL_COMMIT消息即可；
  5. 协调者在COMMIT或ABORT状态奔溃恢复，简单根据当前状态进行事务的全局提交或中止即可；

接下来是参与者的故障处理：

  1. 参与者在INIT状态奔溃，恢复后直接中止事务；
  2. 参与者在READY状态奔溃，这个时候参与者并不止到全局事务的状态，恢复后首先需要确定当前的协调者的状态，如果协调者处于PRECOMMIT状态则进行预提交操作进入PRECOMMIT状态；如果协调者处于ABORT状态，则中止事务；如果协调者处于WAIT状态则阻塞等待协调者发送决策结果消息；如果此时协调者也处于奔溃状态如何处理？这个参考下面的情形；
  3. 参与者在READY状态等待协调者信息超时，这个时候可以认为协调者已经奔溃，这个时候只能通过其余的参与者来确定当前事务的状态。如果存在另一个参与者的状态为INIT，则说明协调者肯定还没有进入PRECOMMIT状态，此时参与者直接中止事务即可；若存在一个参与者处于ABORT状态，也直接中止事务；若存在一个参与者处于PRECOMMIT状态，说明协调者已经进入PRECOMMIT状态并发出了PREPARE_COMMIT消息，此时参与者执行本地事务的预提交操作并进入PRECOMMIT状态；若其它所有存活的参与者都处于READY状态，则可以直接中止事务。