虽然两阶段提交协议只是 Paxos 协议的一个特例（参见 Jim Gray & Leslie Lamport 对两种协议的比较，Consensus on Transaction Commit，2004），但 2PC 在传统的数据库分布式事务处理中有着广泛的应用，因此研究 2PC 及其具体的实现仍具有一定的意义。

介绍

分布式事务处理的困难源自于两个方面：并发和异常（concurrency and failures）。

多并发编程对于获得高性能至关重要。它的作用是允许多程序交错执行。也就是说，它们会“同时”执行。当此类程序交错访问数据库时，就会产生干扰。避免这种干扰称为并发控制问题（concurrency control problem）。

计算机系统会遭受许多类型的故障。操作系统可能出错，运行它们的硬件也可能会出错。当发生故障时，一个或多个应用程序可能会在中途中断，而中断执行可能会导致错误的结果。例如，汇款过程可能会在减掉一个帐户余额但未在增加另一个帐户余额之前因失败而中断。避免由于故障而导致的此类错误结果称为恢复问题（recovery problem）。

对于一个解决了并发控制和恢复问题的系统来说，在用户看来，所有程序的执行都是原子的——就像没有其他程序在并行执行，可靠的——就像没有故障发生。这种原子的可靠的程序执行过程就称之为事务。

集中式和分布式事务处理之间的一个重要区别在于故障的性质。在集中式系统中，故障是要么全发生要么没发生（all-or-nothing）。而在分布式系统中，我们可能会出现部分故障（partial failures）。部分结果正常，而部分结果异常。

分布式系统中的故障不一定会产生集中式故障的特性，为分布式系统提高自身可靠性创造了机会，但也为很多问题创造了困难。比如分布式事务处理中的事务终止一致性（consistent termination）。在事务处理中（并且在没有数据复制的情况下），必须在其中事务访问数据项的所有节点上处理分布式事务的“提交”或“中止”操作。由于可能会出现局部故障，因此要确保在多个节点上始终执行单个逻辑操作（“提交”或“中止”）相当复杂。

能保证这种一致性的算法我们称之为原子提交协议/ACP（atomic commitment protocol ），两阶段提交协议就属于 ACPs 之一。

原子提交（ATOMIC COMMITMENT）

考虑一个执行过程涉及到节点 S1, S2…Sn 的分布式事务 T。假设 S1 上的 TM 负责管控 T 的执行。在 S1 上的 TM 向 S1, S2…Sn 发送 Commit 操作之前，它必须确保每个节点上的调度器和 DM 已经准备好并且可以进行 Commit。否则，T 就可能在某些节点上进行了 Commit，而在某些节点上进行了 Abort，这样就产生了不一致。我们来看一下调度器和 DM 满足什么样的条件才算是准备好并且可以进行 Commit 了。

只要 T 在节点上满足了可恢复条件，那么该节点上的调度器就允许进行 Commit(T) 操作。也就是说，只要其他事务针对事务T读取的所有值的相关写入都提交了就可以了。需要注意的是如果调度器产生的执行过程是不会级联 abort 的，那么上面的条件就总是成立的。在这种情况下，因为调度器随时都可以处理 Commit(T) 操作，S1 的 TM 发送 Commit 操作就不需要征求调度器的意见。

只要 T 在节点上满足了 Redo 规则，那么该节点上的 DM 就可以执行 Commit(T) 了。也就是说，该节点上所有由 T 写入的 value 值都已经进入了可靠性存储中——数据库或者日志中（具体取决于DM的恢复算法）。如果 T 仅仅是向某些节点提交了读请求，那么它就不需要征求这些节点的 DM 意见。

只有当得到了来自所有节点的调度器和 DM 的允许后，S1 上的 TM 才能向所有节点的调度器和 DM 发送 Commit(T)。实际上，这就是我们要在下一节中讨论的两阶段提交协议（2PC）。为什么我们要将这样一个看起来很简单的思路放到单独的一节中讨论呢？原因是前面的这些讨论并未解决节点或者通信故障。如果说在处理中有一个或者多个节点出错了会怎么样呢？如果有一个或多个消息丢失了会怎样呢？原子性提交问题的真正难点就在于设计一个具有高度容错性的协议。

为简化讨论以及专注于原子性提交问题的本质，我们不再局限于“TM-调度器-DM”模型。为将原子性提交问题从事务处理的其他概念中剥离出来，我们假设对于每个分布式事务 T，在执行 T 的每个节点上都有一个进程。这些进程负责为事务 T 实现原子性提交。我们把在 T 主节点上的进程称为 T 的协调者（coordinator）。剩余进程称为 T 的参与者（participants）。协调者知道所有参与者的名字，因此它可以向它们发送消息。参与者知道协调者的名字，但是它们相互之间并不知晓。

需要强调的是协调者和参与者都是我们为了阐述的方便进行的抽象。实际实现中并不需要参与事务执行的每个节点为每个事务创建一个独立进程。通常，这样的实现都会是很低效的，因为需要管理大量的进程。协调者和参与者进程都是一种抽象，实际中在每个节点上可以由单个或多个进程提供它们的功能，而且通常都是由多个事务共享的。

我们还假设每个节点都包含一个分布式的事务日志（DT log），协调者和参与者可以将事务相关的信息记录在日志中。DT log 必须保存在可靠性存储中，因为它的内容必须不受节点故障的影响。

严格地讲，原子性提交协议（ACP）是一种由协调者和参与者执行的算法，通过它来保证协调者和所有的参与者要么是将事务提交要么是将事务回滚。我们可以更精确地描述如下。每个进程只能投两种票：Yes 或 No，同时最终只能达成一个决定：Commit 或 Abort。ACP 是一种可以让进程达成如下决定的算法：
AC1：所有进程达成的决定都是同一个。
AC2：进程一旦达成决定，就不能改变。
AC3：只有当所有进程都投 Yes 的时候，才能达成 Commit 决定。
AC4：如果没有故障且所有进程投的都是 Yes，那么决定最终将会是 Commit。
AC5：假设执行中只包含算法设计中可以容忍的那些故障，在执行中的任意时刻，如果所有现有故障都已修复同时在足够长的时间内都不再有新故障发生，那么所有进程最终将会达成一个决定。

该问题的抽象形式与“TM-调度器-DM”模型的事务处理联系如下。只有当 A 的调度器和 DM 已经准备好并且可以进行 Commit，节点 A 上的进程才能投 Yes。如果进程决定 Commit（或 Abort），那么 A 的 DM 要执行 Commit（或 Abort）操作。在执行该操作时，节点 A 就像一个集中式 DBS，采用第 6 章中的算法。实际上，处理事务的不同节点可以使用不同的 DM 算法。

现在我们再讨论下这些条件。AC1 是说事务终止的一致性。需要注意的是，我们并未要求所有进程都要达成一个决定。这是一个不现实的目标，因为一个进程可能在发生故障后永不恢复。我们甚至也不要求所有正常的进程达成一个决定。这也是不现实的，尽管原因没有那么显而易见（见下面 Proposition 1）。但是，我们确实是要求一旦所有故障被修复所有进程能达成一个决定（AC5），这个要求就将那些一旦发生故障就允许进程永远处于未决议状态的无意义协议排除了。

AC2 是说节点上事务的执行结果是不可更改的。如果事务一旦 Commit（或Abort），那么之后它就不能再被 Abort（或 Commit）。

AC3 是说只有当事务执行中涉及的所有节点都同意时事务才能提交。AC4 是 AC3 的一个弱化版本。它确保了在某些情况下必须达成 Commit 决定，因此就将那些总是采用选择 Abort 的解法的协议排除在外了。但是我们也并不要求 AC3 的逆完全成立。因为就算所有进程都投的是 Yes，但是最终还是有可能 Abort 的（比如发生了故障，进程投的 Yes 并未被接收到）。关于 AC3 的一个非常重要的推论是，在进程还未投 Yes 的情况下，它可以在任意时刻单方面的选择 Abort。另一方面，一旦投了 Yes 它就不能再单方面地采取行动。在进程投了 Yes 之后到它获取足够的信息来确定最终决定是啥之前，这中间的这个时间段称为进程的不确定区间（uncertainty period）。当进程处在这个时间段时，我们就说进程是不确定的（uncertain）。在这个时间段内，进程既不知道最终决定是要 Commit 还是 Abort，也不能单方面地决定 Abort。

场景1：在 P 处于不确定状态时，故障导致进程 P 与其他进程不可通信。根据不确定区间的定义，在故障恢复之前 P 进程无法达到决定状态。

在继续处理之前进程必须等待故障被修复，也就是说它被阻塞了（blocked）。阻塞并不是我们期望的，因为它可能导致进程等待任意长的时间。事务可能会一直处于未终止状态，无用地消耗资源（例如持有锁）。场景 1 表明通信故障可能导致进程被阻塞。

场景2：当 P 处于不确定状态时发生故障。在 P 恢复时，它无法仅通过它自身决定状态。它必须与其他进程进行通信以确定决定是啥。

我们将进程不需要与其他进程进行通信就能够进行恢复的能力称为独立可恢复性（independent recovery）。这种能力非常吸引人，因为它简单低廉。此外，如果缺乏这种能力那么在所有进程都发生故障的情况下，会导致阻塞。比如，我们假设 p 是在一个 total failure 中第一个恢复的进程，因为 p 处于不确定状态，因此它需要与其他进程进行通信以确定状态，但是其他进程都还 处于 down 状态，因此它就无法与它们进行通信，因此 p 就被阻塞了。

这两个场景表明，在进程处于不确定状态时发生的故障可能导致严重的问题。那么我们是否能够设计出一种没有不确定阶段的 ACPs？不幸的是，不能。因此，我们有以下重要观察：
Proposition 1. 如果可能发生通信故障或者完全故障，那么所有的 ACPs 都可能会导致进程被阻塞。
Proposition 2. 没有一种 ACP 可以保证故障进程的独立可恢复性。

两阶段提交协议（THE TWO PHASE COMMIT PROTOCOL）

两阶段提交协议是最简单最流行的 ACP。在没有故障发生的情况下，它的执行过程如下：

  1. 协调者发送一个 VOTE-REQ（也即 vote request） 消息给所有的参与者。
  2. 当参与者接收到 VOTE-REQ 消息后，它会发送一个包含参与者投票结果的消息（YES/NO）给协调者作为响应。如果参与者投的是 No，它会决定 Abort 事务并停止运行。
  3. 协调者收集来自所有参与者的投票信息。如果所有的消息都是 YES，同时协调者投的也是 Yes，那么协调者就会决定进行 Commit，并向所有参与者发送 COMMIT 消息。否则协调者就会决定进行 Abort，并向所有投 Yes 的参与者发送 ABORT 消息（那些投 No 的参与者已经在第 2 步中决定 Abort 了）。之后，对于这两种情况协调者都会停止运行。
  4. 每个投 Yes 的参与者等待来自协调者的 COMMIT 或 ABORT 消息。收到消息后执行相应动作然后停止运行。

2PC 的两个阶段是指投票阶段（步骤 1 和 2）和决定阶段（步骤 3 和4）。参与者的不确定区间始于向协调者发送 YES（步骤 2），终于接收到 COMMIT 或 ABORT 消息（步骤4）。协调者没有不确定区间，因为只要它投了票结果就确定了，当然它投票时需要知道参与者的投票结果（步骤3）。

很容易可以看出 2PC 满足条件 AC1-AC4。不幸的是，目前为止的描述并不满足 AC5。有两个原因，首先在协议的很多点上，进程在继续处理之前必须要等待消息。但是消息可能会由于故障而无法到达。因此，进程可能会无限等待下去。为避免这个问题，需要使用超时机制。当进程的等待因为超时而打断时，进程必须采取特定的动作，称之为超时动作（timeout action）。因此，为满足 AC5，必须为协议中进程需要等待消息的地方引入合理的超时动作。

其次，当进程从故障中恢复时，AC5 要求进程能够达成与其他进程可能已经达成的决定相一致的决定（可能还必须要等待某些其他故障修复之后才能达成这样的决定）。因此，进程还必须要将某些信息存入可靠性存储中，比如 DT log 中。为满足 AC5，我们还必须要说明需要将哪些信息存入 DT log 以及如何在恢复时使用它们。

超时动作（Timeout Actions）

在 2PC 中有如下三个需要进程等待消息的地方：在步骤 2, 3 和 4 的开始阶段。在步骤 2 中，参与者需要等待来自协调者的 VOTE-REQ 消息。这发生在参与者进行投票之前。由于任何一个进程在它投 Yes 之前都可以单方面地决定进行 Abort，因此如果参与者在等待 VOTE-REQ 消息时超时，它可以简单地决定进行 Abort，然后停止运行。

在步骤 3 中，协调者需要等待来自所有参与者的 YES 或 NO 消息。在这个阶段，协调者也还没有达成任何决定。此外，也没有任何参与者已经决定要 Commit。因此协调者可以决定进行 Abort，但是必须要向给它发送 YES 的每个参与者发送 ABORT 消息。

在步骤 4 中，投了 Yes 的参与者 p 要等待来自协调者的 COMMIT 或 ABORT 消息。此时，p 处于不确定状态。因此，与前面两种情况下进程可以单方面进行决定不同，在这种情况下参与者必须与其他进程商议决定如何动作。这个商议过程需要通过执行一个 terminaion protocol 来完成。

最简单的 terminaion protocol 如下：在与协调者的通信恢复之前 p 始终保持阻塞。之后，协调者通知 p 对应的决定结果。协调者肯定支持这样做，因为它没有不确定区间。该 terminaion protocol 满足 AC5，因为如果所有的故障都修复了的话，p 就能与协调者通信，然后就能达到决定状态。

这种简单的 terminaion protocol 缺点在于，p 可能要经历不必要的阻塞。比如，假设现在有两个参与者 p 和 q。协调者先给 q 发送了一个 COMMIT 或 ABORT 消息，但是在发送给 p 之前发生了故障。因此，尽管 p 是不确定的，但是 q 不是。如果 p 可以与 q 进行通信，那么它就可以从 q 那得知最终的决定结果。并不需要一直等待着协调者的恢复。

但是这意味着需要参与者之间需要相互知晓，这样它们才能相互直接通信。但是我们前面描述原子性提交问题时，只是说协调者认识所有参与者，参与者认识协调者，但是参与者初始时相互并不知晓。但是这也不是什么大问题，我们可以让协调者在发送 VOTE-REQ 消息时将参与者信息附加在上面，发给所有参与者。这样在参与者接收到该消息后，相互就都知道了。事实上，在发送该消息之前它们之间也是不需要相互知晓的，因为如果参与者在接收到 VOTE-REQ 消息前超时了，它可以单方面地决定进行 Abort。

下面我们再来介绍下 cooperative terminaion protocol：参与者 p 如果在不确定区间超时，它会发送一个 DECISION-REQ 消息给所有其他进程，设为 q，问下 q 是否知道决定结果或者能否单方面地做出决定。在这个场景中，p 是initiator，q 是 responder。有如下三种情况：

  1. q 已经决定进行 Commit（或Abort）：q 简单地发送一个 COMMIT（或ABORT）消息给 p，然后 p 进行相应动作。
  2. q 还未进行投票：q 可以单方面地决定进行 Abort。然后它发送 ABORT 消息给 p，p 会因此决定进行 ABORT。
  3. q 已经投了 Yes 但是还未做决定：q 也是处于不确定状态，因此无法帮助 p 达成决定。

对于该协议来说，如果 p 可以同某个进程 q 通信并且上述 1 或 2 成立，那么 p 就可以不经阻塞地达成决定。另一方面，如果 p 通信的所有进程都是 3 成立，那么 p 就会被阻塞。且 p 的阻塞会一直持续到有 q 被故障修复且满足条件 1 或 2 为止。至少会有一个这样的进程存在，即协调者。因此这个 terminaion protocol 满足 AC5。

总而言之，虽然 cooperative termination protocol 减少了阻塞的可能性，但也不能完全消除这种可能性。鉴于 Proposition 1，这不足为奇。

针对两阶段提交的评估（Evaluation of 2PC）

我们可以从如下几个维度来对2PC进行评价：

  • Resiliency：可以容忍哪些故障？
  • Blocking：进程是否有可能被阻塞？如果是，什么情况下会被阻塞？
  • 时间复杂度：达成决定需要花多长时间？
  • 消息复杂度：达成决定需要多少次消息交换？

前两个维度用来衡量协议的可靠性，后两个用来衡量协议的效率。可靠性和效率是两个冲突的目标：任意一个都可以以另一个为代价来获得。协议如何选择取决于对于特定的应用来说哪个目标更重要。但是，无论协议如何选择，我们都需要尽力对无故障时的情况进行优化——主要是提高系统的正常工作速率。

我们通过对非阻塞情况下节点达成一个决定最坏情况下所需要的消息交换轮数进行计数，来衡量 ACP 的时间复杂度。轮（round）代表了消息到达目标节点所需的最大时间。用于故障检测的超时机制就是基于这个最大的消息延迟是已知的这样一个假设。需要注意的是，一轮内可能会有很多消息被发送——就看有多少个发送者/接收者对。如果一个消息必须等另一个消息接收到之后才能发送，那么这两个消息就肯定属于不同的轮。比如，2PC 中的 COMMIT 和 YES 消息就属于不同的轮，因为前者必须要等接收到后者后才能发送。另一方面，所有的 VOTE-REQ 消息就属于同一轮，因为它们是并发地发送到目标节点的。对于所有的 COMMIT 消息来说也是这样。用于计算轮数的一种简单方式就是认为同一轮中发送的消息都是同时发出的，同时具有相同的延迟。因此，每一轮都是从消息发送时开始，在消息被接收后结束。

使用轮来衡量时间复杂度实际上就忽略了消息处理所需的时间。这也是合理的，因为通常情况下消息传输延迟都要远远大于消息处理延迟。但是，如果要想得到一个更精确的时间复杂度度量，还需要将另外两个因素考虑进来。

首先，如目前所知，进程必须在发送或接收特定消息时将它们记录到 DT log中。在某些情况下，这样的一个文件服务器是在一个本地网络中，这种针对可靠性存储的访问也会引入与消息发送相当的开销。因此针对可靠性存储的访问次数也会成为影响协议的时间复杂度的重要因素。

其次，在某些轮中，进程是要将某个消息发送到所有其他进程。比如，在第一轮协调者会向所有参与者发送 VOTE-REQ 消息。这种行为称为广播。为了广播一个消息，进程必须将同一消息的n个拷贝放到网络上，n 代表接收者数目。通常来说，将消息放到网络上的时间与在网络上传输的时间相比要小很多。但是如果 n 足够大，那么为广播所进行的准备时间也会变得很大，需要考虑在内。

因此，关于时间复杂度的更精确的衡量可能需要将总的轮数，访问可靠性存储的时间以及消息广播时间加起来。但是，后面的分析中我们还是会忽略后面两个因素，只关注轮数。

我们通过协议所使用的消息总数来衡量消息复杂性。这也是合理的，因为消息本身并不长。但是如果它们很长的话，我们也是需要将长度考虑在内的，而不能仅仅考虑个数。在我们本章中所讨论的协议的消息都是很短的，因此我们还是只关注消息个数。

现在我们来考察下 2PC 的 resiliency，blocking，时间和消息复杂度。

Resiliency：

2PC 可以容忍节点故障和通信故障(无论是网络分区还是超时故障)。我们前面介绍的超时动作那部分的内容本身并未对超时产生的原因做任何假设， 通过这一点就可以得出该结论。超时可能是由节点故障，分区或者仅仅是因为伪超时导致的。

Blocking：

2PC 是会经历阻塞的。如果进程在不确定区间超时，同时可以进行通信的那些进程本身也是不确定的，那么进程就会被阻塞。实际上，即使是在只有节点故障的情况下，2PC 仍然可能会被阻塞。如果要精确计算阻塞发生的概率，必需首先要知道故障发生的概率，同时这种类型的分析也超出了本书的范围。

时间复杂度：

在没有故障发生的情况下，2PC 需要三轮：(1)、协调者广播 VOTE-REQ 消息；(2)、参与者回复投票信息；(3)、协调者广播最终决定结果。如果有故障发生，可能还要额外加上 terminaion protocol 需要的那两轮：第一轮用于超时的参与者发送 DECISION-REQ 请求，第二轮用于接收到消息的进程度过不确定区间后进行响应。可能会有多个参与者同时调用 terminaion protocol。但是不同的调用可以重叠进行，因此合起来也还是只有两轮。

因此，在有故障发生的情况下那些未被阻塞或没有发生故障的进程需要五轮才能达成决定。这与故障发生的个数无关。根据定义，一个被阻塞的进程可能会被阻塞无限长的时间。因此，为了得到有意义的结论，我们在考虑时间复杂度时需要将那些被阻塞的进程排除在外。

消息复杂度：

令 n 代表参与者数目（因此总进程数就是 n+1）。在 2PC 的每轮中，有 n 个消息被发送。因此在没有故障的情况下，协议将会使用 3n 个消息。 cooperative terminaion protocol 将会被那些投了 Yes 但是未收到来自协调者的 COMMIT 或 ABORT 消息的所有参与者调用。假设有 m 个这样的参与者。因此将会有 m 个进程初始化 terminaion protocol 的执行，每个发送 n 个 DECISION-REQ 消息。最多有 n-m+1（未处于不确定状态的最大进程数）个进程会响应第一个 DECISION-REQ 消息。收到这些响应后，将会有一个新的进程从不确定状态退出，因此它会向另一个 terminaion protocol 执行实例发送响应消息。因此最坏情况下，由 terminaion protocol 发送的消息数将是： nm + sum (n-m+i) = 2nm-m^2/2+m/2. 在 n=m 时该多项式取得最大值，也就是当所有参与者都在处于不确定区间时超时。因此，terminaion protocol 贡献了多达 n(3n+1)/2 个消息，对于整个 2PC 协议来说就是 n(3n+7)/2。

附记

1、关于三阶段提交协议（Three-phase commit protocol）：

三阶段提交协议虽然对二阶段提交协议做了改进，但仍然不是一个完美的协议，且增加了二阶段提交协议的复杂度（参照 Jim Gray & Leslie Lamport，Consensus on Transaction Commit 中的评述）。

2、Google Chubby 服务的创建者 Mike Burrows 说过“世界上只有一种一致性协议，那就是 Paxos” ——所有其他的方法都只是 Paxos 的一个特化版本。

参考资料
[1]. Concurrency Control and Recovery in Database Systems. Chapter 7, DISTRIBUTED RECOVERY. https://courses.cs.washington.edu/courses/cse551/09au/papers/CSE550BHG-Ch7.pdf
[2]. 分布式事务之两阶段提交。http://duanple.com/?p=56
[3]. Consensus on Transaction Commit. https://www.microsoft.com/en-us/research/uploads/prod/2004/01/twophase-revised.pdf
[4]. Consensus on Transaction Commit(译)。http://duanple.com/?p=45