小占的技术日志

奋起直追

0%

分布式事务之两阶段提交

Posted on Edited on In ,

文章主要引用自 http://duanple.blog.163.com/blog/static/70971767201311810939564/ 他的博客给我提供了很多帮助。感谢！

在看这篇文章之前我一直有一个疑惑，2pc和raft有什么局别(2pc也可以实现一致性，副本的一致性为什么不用2pc)？ 现在大约有一个答案了：2pc更加注重的是当前的一个事件（不用事务的原因是不一定只能用于事务）在系统中都达到一致之后才认为这个事件是完成了的。而raft等只要大多数达到一致就可以了，其他不一致的节点可以后面慢慢追上。这使得2pc和raft有了不同的分工

下面2pc没有解决协调者挂掉时，而所有参与者都处于不确定区间时的情况，所有参与者都在等待协调者的恢复，因为参与者不能确定事务的状态。 我的想法是在客户端中维持一个与协调者的心跳如果协调者故障，则重新安排协调者，并且重新发送vote-req信息，这些2pc，不过相应的参与者中的代码机制就要改一下了，在超时执行termination protocol之前看看没有有vote-req消息。

背景介绍

事务处理的困难源于两个方面：concurrency和failures。为了达到高的性能，并发是必要的。而在现实中，计算机系统会面临各种各样的故障，操作系统可能会出错，硬件也有可能会出错。当这些错误发生时，应用程序可能会在正执行的过程中被打断，而这可能会产生错误的结果。比如用户正在转账，在中间失败可能会导致一个账户上的钱少了，但是另一个账户却没有收到钱的情况。Recovery就是要避免因故障而产生错误结果。所以就引出了Concurrency Control和Recovery这两个概念。

在事务处理中就有这样的一个难解问题，即事务终止的一致性。如前所述，分布式事务的Commit或Abort操作必须要保证在事务的数据访问涉及到的所有节点上执行。在允许局部失败的情况下，这个问题变得非常复杂。

我们将可以保证这种一致性的算法称为**原子性提交协议(ACP-atomic commitment protocol)**。本章我们的主要目标就是介绍这种可以容忍各种错误的ACP协议。在具体介绍之前，我们先详细介绍下分布式系统中存在的各种错误类型。

分布式系统中的故障

分布式系统由两种组件组成：负责处理信息的节点和负责在节点间传递消息的通信链路。
系统无法区分是节点故障还是通信故障使得一个节点无法与另一个节点进行通信。采用超时检测故障的存在。

节点故障

我们假设：站点要么是可以正常工作(称它是operational的)要么是完全无法工作(称之为down)，它永远都不会执行错误的动作。这种故障模型也被称为fail-stop，because sites fail only by stopping。很明显这有些理想化。由于软硬件bug的存在，计算机偶尔还是有可能会执行不正确的动作。通过不断的测试以及软硬件内建的冗余，可以构建出一个基本上满足fail-stop的系统。我们并不想在本文中深入讨论这些技术，我们假设节点都是fail-stop的。本章中我们将要讨论的各个协议的正确性将会基于这个假设。

尽管单个节点只有两个状态，要么正常工作要么停止工作，但是不同节点可能处于不同状态。这样仍然会存在一种局部故障(partial failure)的情况：某些节点正常某些节点down掉。如果所有节点都down掉的话就是total failure的情况。

Partial Failure很难处理。从根本上说，这是因为正常工作的节点根本无法确定失败的那些节点的状态。在这些不确定性解决之前，正常节点可能会被阻塞，无法Commit或者Abort一个事务。原子性提交协议的一个重要设计目标就是要尽量将单个节点的故障的影响最小化，使得其他节点可以继续处理。

通信故障

通信链路也有可能发生故障。故障可能使得节点之间无法通信。可能有各种各样的通信故障：消息内容可能会由于链路上的噪声被破坏；链路可能临时失灵，导致单个消息完全丢失；链路可能会中断一段时间，导致通过它的所有消息都丢失。使得产生分区。

那我们怎么对待无法传送的消息呢？

无法传送的消息

节点和通信故障的存在需要我们能够处理那些不能发送的消息。消息可能会因为接收者down掉或者网络分区的存在，而无法发送。有两种选择：

  1. 持久化消息。由网络系统对消息进行存储，在可以发送时再发送
  2. 丢失消息。网络系统不再尝试重发
    我们选择第2种方式，这也是很多设备采用的方式。第1种方式需要非常复杂的协议，它们本身非常类似于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的协调者。剩余进程称为T的参与者。协调者知道所有参与者的名字，因此它可以向它们发送消息。参与者知道协调者的名字，但是它们相互之间并不知晓。

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

我们还假设每个节点都包含一个分布式的事务日志(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是说事务终止的一致性。但是，我们确实是要求一旦所有故障被修复所有进程能达成一个决定(AC5)，这个需求就将那些一旦发生故障就允许进程永远处于未决议状态的无意义协议排除了。AC2是说节点上事务的执行结果是不可更改的。AC3是说只有当事务执行中涉及的所有节点都同意时事务才能提交。AC4是AC3的逆的一个弱化版本。它确保了在某些情况下必须达成Commit决定，因此就将那些总是采用选择Abort的平凡解法的协议排除在外了。

只有才，后推前；只有A才B ,B→A；逆否命题：否后否前即-A→-B.

AC3蕴含如果节点投的是Abort时，最后一定是Abort的。所以可以在进程还未投Yes的情况下，它可以在任意时刻单方面的选择Abort。另一方面，一旦投了Yes它就不能再单方面地采取行动。在进程投了Yes之后到它获取足够的信息来确定最终决定是啥之前，这中间的这个时间段称为进程的不确定区间(uncertainty period)。

场景

由上面的ACP协议可以推出，只有节点处于不确定区间是最麻烦的，其他情况都可以独立恢复。

考虑下面的场景：

  1. 在P处于不确定状态时，故障导致进程P与其他进程不可通信。根据不确定区间的定义，在故障恢复之前进程无法达到决定状态。
    在继续处理之前进程必须等待故障被修复，也就是说它被阻塞了。阻塞并不是我们期望的，因为它可能导致进程等待任意长的时间。场景1表明通信故障可能导致进程被阻塞。
  2. 在处于不确定状态时，进程P发生故障。在P恢复时，它无法仅通过它自身决定状态。它必须与其他进程进行通信以确定决定是啥。
    我们将进程不需要与其他进程进行通信就能够进行恢复的能力称为独立可恢复性(independent recovery)。这种能力非常吸引人，因为它简单低廉。此外，如果缺乏这种能力那么在所有进程都发生故障的情况下，会导致阻塞。比如，我们假设p是在一个total failure中第一个恢复的进程，因为p处于不确定状态，因此它需要与其他进程进行通信以确定状态，但是其他的都还down着呢，因此它就无法与它们进行通信，因此p就被阻塞了。

结论：
这两个场景表明，在进程处于不确定状态时发生的故障可能导致严重的问题。那么我们是否能够设计出一种没有不确定阶段的ACPs？不幸的是，不能。我们有如下一些结论：

  1. 如果可能发生通信故障或者完全故障，那么所有的ACPs都可能会导致进程被阻塞
  2. 没有一种ACP可以保证故障进程的独立可恢复性

两阶段提交协议

阶段1：请求阶段（commit-request phase，或称表决阶段，voting phase）

  1. 步骤1，协调者发送一个VOTE-REQ消息给所有的参与者
  2. 步骤2，当参与者接收到VOTE-REQ消息后，它会发送一个包含参与者投票结果的消息(YES或NO)给协调者作为响应。如果参与者投的是No，它会决定Abort事务并停止运行

AC5的要求：参与者节点执行询问发起为止的所有事务操作，并将Undo信息和Redo信息写入日志。

例如某一事务的事务序号为T1，其对数据X进行修改，设X的原值是5，修改后的值为15，那么Undo日志为<T1, X, 5>，Redo日志为<T1, X, 15>。

阶段2：提交阶段（commit phase）

  1. 步骤3，协调者收集来自所有参与者的投票信息。如果所有的消息都是YES，同时协调者投的也是Yes，那么协调者就会决定进行Commit，并向所有参与者发送COMMIT消息。否则协调者就会决定进行Abort，并向所有投Yes的参与者发送ABORT消息(那些投No的参与者已经在第2步中决定Abort了)。之后，对于这两种情况协调者都会停止运行
  2. 步骤4，每个投Yes的参与者等待来自协调者的COMMIT或ABORT消息。收到消息后执行相应动作然后停止运行。

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

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

超时处理

在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来完成。

termination 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。

恢复

考虑一个从故障中恢复的进程p，为满足AC5，p必须能够达成一个与其他进程相一致的决定—不一定是恢复完成后就要达成，可能是在等其他故障恢复后的某个时间段内。

假设p恢复时它还记得发生故障时的状态—后面我们会再讨论如何做到这一点。如果p是在它向协调者发送YES之前发生了故障(2PC的步骤2)，那么p可以单方面地决定进行Abort。另外，如果p是在接收到来自协调者的COMMIT或ABORT消息或者已经单方面地决定Abort之后发生的故障，那么此时它已经完成了决定。在这些情况下，p都可以独立地完成恢复。

但是如果p是在处于不确定区间时发生了故障，那么恢复时就无法仅通过自身来完成决定。因为它已经投了Yes，有可能所有其他进程也都投了Yes，这样在p挂掉的时候就已经决定要Commit了。但是也有可能其他一些进程投了No或者是根本还没有投，最终决定变成是要Abort。仅仅依赖本地信息，p无法区分出这两种可能，因此必须与其他进程通信再做决定。这也从一个方面说明了为何没法进行独立地恢复(independent recovery)。

这种情况就跟p等待来自协调者的COMMIT或ABORT消息而超时了的情况是一样的。因此p可以通过使用terminaion protocol达成决定。需要注意的是p可能会被阻塞，因为它可以进行通信的那些进程也是处于不确定状态。

为了记住故障发生时的状态，每个进程必须保存一些信息到节点的DT log中。当然，每个进程只能访问它本地的那个DT log。假设使用的是cooperative terminaion protocol，DT log的管理方式如下：

  1. 当协调者发送VOTE-REQ消息时，它会在DT log中写入一条start-2PC记录。该记录包含了所有参与者的标识符，同时写入可以发生在发送消息之前或之后。
  2. 如果参与者投了Yes，它会在向协调者发送YES消息前向DT log中写入一条记录。该记录包含了协调者名称及参与者列表(由协调者通过VOTE-REQ消息提供)。如果参与者投了No，它可以在向协调者发送NO消息之前或之后写入一个abort记录。
  3. 在协调者向参与者发送COMMIT消息之前，它会向DT log中写入一条commit记录。
  4. 当协调者向参与者发送ABORT消息时，它会向DT log中写入一条abort记录。写入可以发生在发送消息之前或之后。
  5. 在收到COMMIT(或ABORT)消息后，参与者向DT log中写入一条commit(或abort)记录。
    在上述讨论中，在DT log中写入一条commit(或abort)记录实际上就代表进程决定了是Commit还是Abort。

现在可以来简单介绍下事务提交过程是如何与事务处理的其他活动进行交互的。一旦commit(或abort)记录写入了DT log，DM就可以执行Commit(或Abort)操作了。当然这其中还有大量的细节需要考虑。比如，如果DT log是作为DM log的一部分实现的，那么commit(或abort)记录的写入就可能需要通过调用本地DM的接口来实现。通常来说，细节上如何来操作取决于本地DM采用了什么样的算法。

当节点S从故障中恢复时，分布式事务在S上的执行取决于DT log的内容：

  • 如果DT log包含一个start-2PC记录，那么说明S就是协调者所在节点。如果它还有commit(或abort)记录，那么说明在发生故障前协调者已经做出了决定。如果这两种记录(commit或abort)都没有找到，那么协调者可以通过向DT log中插入一条abort记录来单方面地决定进行Abort。这样可以工作的关键在于，协调者是先将commit记录写入DT log，然后再发送COMMIT消息的(上面的第3点)。
  • 如果DT log中没有start-2PC记录，那么S就是参与者节点。那么有如下三种可能：
    1. DT log中包含一个commit(或abort)记录。那么说明在发生故障之前，参与者已经达成了决定。
    2. DT log中没有yes记录。那么要么是参与者是在投票前发生的故障，要么投的是No(但是在发生故障前还没有完成abort记录的写入)。(这也是为何yes记录必须要在发送YES消息前写入日志的原因；参考上面的第2点。)因此，它可以单方面地通过向DT log中写入一条abort记录决定进行Abort。
    3. DT log中包含了yes记录，但是没有commit(或abort)记录。那么说明参与者是在不确定区间内发生的故障。它可以通过使用terminaion protocol来达成决定。回想一下，yes记录中包含了协调者名称以及所有的参与者，这正是terminaion protocol所需要的。

超时处理的主要是通信问题，恢复处理的是节点故障。二者相差不多，但是通信故障中状态都还在内存中可以不考虑持久化问题，但是恢复中就需要考虑持久化问题了，所以引入了DT log的设计。

我们关于ACP的研究都是从单个事务的角度来看的，这也隐藏了节点恢复时的一些问题。在一个节点恢复时，它必须要为那些故障发生前还未commit或abort的所有事务完成ACP的执行。什么时候节点可以恢复正常的事务处理呢？在一个集中化的DBS恢复后，在重启过程完成之前事务是无法被处理的，因为需要恢复那些已存储的数据库状态。分布式DBS中的节点恢复也与之类似，因为某些事务可能会被阻塞。在这种情况下，在该恢复节点的DBS在所有被阻塞的事务被提交或abort之前也是不可访问的。

避免这种问题的方法取决于所使用的调度器类型。考虑使用严格两阶段锁协议（strict 2PL）的情况。当节点的恢复过程已经为所有的未阻塞事务完成决定时，它应该通知调度器来重新获取那些在故障发生之前由被阻塞的事务占有的锁。实际上，一个被阻塞的事务T只需要获取它的写锁。问题在于锁表通常是保存在内存中的，因此在系统发生故障时会丢失。为避免丢失这些信息，负责管理T的原子性提交的进程需要将T的写锁也记录到它写入到DT log中的yes记录中。当然如果这些信息可以从该节点的RM维护的日志中获取，就没必要这样做。比如，在第6章描述的undo/redo算法，因为在T投Yes之前，所有的更新都会进入日志。这些记录就可以用来确定T的写锁集合。

增加锁信息可以加快节点的恢复服务的时间，因为不用等待所以之前未决定的事务的裁决。 但我觉得没有什么必要，毕竟故障是小概率事件，而且故障时未裁决的事务数量应该不多。

2PC协议和cooperative terminaion protocol的伪码，包括了上面讨论的关于超时处理和DT log相关的处理动作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 2pc algorithm
// // Coordinator's algorithm
send VOTE-REQ to all participants;
write start-2PC record in DT log;
wait for vote messages (yes or no) from all participants
    on timeout begin
        let Py be the processes from which yes was received;
        write abort record in DT log;
        send ABORT to all processes in Py;
        return
    end;
    if all votes were yes and Coordinator votes yes then begin
        write commit record in DT log;
        send COMMIT to all participants;
    end;
    else begin
        let Py be the processes from which yes was received;
        write abort record in DT log;
        send ABORT to all processes in Py;
    end;
    return
// // Participant's algorithm
wait for VOTE-REQ from coordinator
    on timeout begin
        write abort record in DT log;
        return
    end;
    if participant votes yes then begin
        write a yes record in DT log;
        send YES to coordinator;
        wait for decision message (COMMIT or ABORT) from coordinator
            on timeout initiate termination protocol
            if decision message is COMMIT then write commit record in DT log
            else write abort record in DT log
    end
    else /* participant's vote is No */ begin
        write abort record in DT log;
        set NO to coordinator;
    end;
    return

// termination protocol.
// // Initiator's algorithm
start: send DECISION-REQ to all processes:
    wait for decision message from any processes
        on timeout goto start; /*blocked*/
    if decision message is COMMIT then
        write commit record in DT log
    else /*decision message is ABORT */
        write abort record in DT log;
    return
// // Responder's algorithm
wait for DECISION-REQ from any processe p;
if responder has not voted yes or has decided to abort then
    send ABORT to p
else if responder has decided to commit then send COMMIT to p
else skip;
return

没有解决协调者挂掉时，而所有参与者都处于不确定区间时的情况，所有参与者都在等待协调者的恢复，因为参与者不能确定事务的状态。 我的想法是在客户端中维持一个与协调者的心跳如果协调者故障，则重新安排协调者，并且重新发送vote-req信息，这些2pc，不过相应的参与者中的代码机制就要改一下了，在超时执行termination protocol之前看看没有有vote-req消息。

DT log 回收

也需要对DT log中的那些过期信息进行垃圾回收。在垃圾回收时，有如下两个基本原则需要遵守：
GC1：至少要等到RM执行了RM-Commit(T)和RM-Abort(T)之后，节点才能将事务T的相关日志记录从它的DT log中删除。
GC2：至少有一个节点在它收到事务T涉及的所有节点都执行了RM-Commit(T)和RM-Abort(T)的消息之前，不会将事务T的相关日志记录从它的DT log中删除。

GC2 保证AC5，即一个节点从故障中恢复时可以查询到事务的状态。

通过使用每个节点上的本地信息就可以确保GC1。但是GC2需要节点间通信的支持。为了实现GC2通常有两种极端策略：GC2只对一个节点成立，通常都是协调者；GC2对于T的执行相关的所有节点都成立。

2PC的评价

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

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

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

我们通过对非阻塞情况下节点达成一个决定最坏情况下所需要的消息交换轮数进行计数，来衡量ACP的时间复杂度。
通过协议所使用的消息总数来衡量消息复杂性。这也是合理的，因为消息本身并不长。但是如果它们很长的话，我们也是需要将长度考虑在内的，而不能仅仅考虑个数。

现在我们来考察下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发送的消息数将是：
在n=m时该多项式取得最大值，也就是当所有参与者都在处于不确定区间时超时。因此，terminaion protocol贡献了多达n(3n+1)/2个消息，对于整个2PC协议来说就是n(3n+7)/2。

参考文献： [分布式事务之两阶段提交 ](http://duanple.blog.163.com/blog/static/70971767201311810939564/) [Concurrency Control and Recovery in Database Systems 原文](https://pdfs.semanticscholar.org/9aaf/a4657a4c2745062e423b63c05171eebf7e92.pdf)