作者：Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman. 1987
原文：Concurrency Control and Recovery in Database Systems
译者：phylips@bmy 2013-02-14
译文：http://duanple.blog.163.com/blog/static/70971767201311810939564/
[序：历史上，数据库领域共产生过三位图灵奖得主Charles Bachman，E.F.Codd和Jim Gray
1961年，通用电气公司(General Electric Co.)的Charles Bachman成功地开发出世界上第一个网状DBMS也是第一个数据库管理系统——集成数据存储(Integrated DataStore IDS)，奠定了网状数据库的基础，并在当时得到了广泛的发行和应用。后Charles Bachman因在数据库方面的贡献获得1973年图灵奖。
1970年6月，IBM圣约瑟研究实验室的高级研究员Edgar Frank Codd在Communications of ACM上发表了A Relational Model of Data for Large Shared Data Banks。首次明确提出关系数据库模型。此后，之前基于层次模型和网状模型的数据库产品很快消亡。1972年，Codd提出了关系代数和关系演算的概念， 定义了关系的并、交、投影、选择、连接等各种基本运算， 为日后成为标准的结构化查询语言(SQL)奠定了基础。 后来Codd又陆续发表多篇论文，论述了范式理论和衡量关系系统的12条标准，为关系数据库建立了一个严格的数学模型。而此时网状数据库的标准化工作正在进行，同时有人认为关系数据库是一个过于理想化的模型，对它的性能表示担忧。又是出现了关系数据库与反关系数据库两派(历史总是如此相似)。后E.F.Codd获得1981年图灵奖。
1976年，IBM 的研究员 Jim Gray 发表了名为Granularity of Locks and Degrees of Consistency in a Shared DataBase的论文，正式定义了数据库事务的概念和数据一致性的机制。后Jim Gray因在数据库和事务处理研究和实现方面的开创性贡献获得1998年图灵奖。
迄今，数据库已经是一个理论研究非常成熟同时商业化也足够高的领域了。同时，它本身所涉及的知识面也是非常广的，这篇文章我们将主要关注事务处理方面的提交问题。
上世纪70年代，在关系数据库理论基本成熟后，各大公司在关系数据库管理系统的实现和产品开发中遇到了一系列技术问题。主要是在数据库的规模愈来愈大，数据库的结构愈来愈复杂，又有愈来愈多的用户共享数据库的情况下，如何保障数据的完整性、安全性、并发性以及故障恢复的能力，这些问题成为数据库产品是否能实用化并最终为用户接受的关键因素。Jim Gray在解决这些重大技术问题，使RDBMS成熟并顺利进入市场的过程中，起到了关键性作用。概括地说，解决上述问题的主要技术手段和方法是：把对数据库的操作划分为称为“事务”的基本原子单位，一个事务要么全做，要么全不做（即all-or-nothing原则）；用户在对数据库发出操作请求时，需要对有关的数据“加锁”，防止不同用户的操作之间互相干扰；在事务运行过程中，采用“日志”记录事务的运行状态，以便发生故障时进行恢复；对数据库的任何更新都采用“两阶段提交”策略。以上方法及其他各种方法总称为“事务处理技术”。
首先来回顾一下有关事务处理的一些经典书籍文章。Jim Gray在1977年写过一篇文章“Notes on Data Base Operating Systems”，总共80多页，应该算是早期非常完善地介绍数据库这门学科内容的教科书了，文章内容来源广泛，汇集了那个时代众多数据库先驱们的想法和思考。IBM的System R对该文章产生了重要影响。很多内容都是直接来源于Jim Gray与他人的讨论，因此很多想法已经无法找到明确的参考文献。在这篇文章中，将一个数据库系统划分成了如下四个主要组件：数据字典(dictionary)，数据通信(data communications)，数据库管理(database manager)，事务管理(transaction management)。尤其对事务管理中的并发控制(locking)和系统可靠性机制(recovery)进行了深入讲解。比如5.7.5节，引用的就是Jim Gray 1976年的经典论文“Granularity of Locks and Degrees of Consistency in a Shared DataBase”的内容。同时描述了大量事务处理方面的细节，以及所用到一些重要协议算法，像两阶段提交协议。当然这里关于事务处理的大部分想法也都源自于IBM IMS开发者的实际经验以及作者本身参与的System R的开发过程。之后在1981年的文章“The Transaction Concept:Virtues and Limitations”中，Jim Gray提出事务应具有三个属性：Consistence，Atomicity，Durability。而ACID的叫法，则是在1983年由Theo Harder和Andreas Reuter在他们发表的文章“Principles of Transaction-Oriented Database Recovery”中首次提出，之后才被广泛使用的。顺便来看一些其他重要概念的起源，Write-Ahead-Log概念是Ron Obermark在1974年提出的，大概也是在那个时候他实现了nested-two-phase commit protocol；Earl Jenner和Steve Weick在1975年首次实现了两阶段提交协议，当然实际上它可能源于由Niko Garzado在1970年实现的某些系统，此后IMS，System R都提供了不同形式的实现；Paul McJones和Jim Gray参考Warren Titlemann在INTERLISP中的实现，在System R中实现了DO-UNDO-REDO 策略。此外Lampson和Sturgis在1976年的论文” Crash Recovery in a Distributed System”中独立提出了两阶段提交协议，Lewis, Sterns和Rosenkrantz在论文” System Level Concurrency Control for Data Base Systems”中独立提出了nested commit protocol。1987年，Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman的书籍“Concurrency Control and Recovery in Database Systems”，全书共300多页，系统描述了数据库系统中的并发控制和恢复机制。
1992年，C.Mohan的ARIES出世，这篇论文详细描述了一系列关于恢复，并发和存储管理的算法。事实上该论文中的很多想法源于C.Mohan与Don Haderle的交流，那个时候Don Haderle正担任IBM DB2的主架构师。通过这个交流，C.Mohan意识到DB2对于某些问题的处理方式与System R有所不同，同时System R基于shadow page的恢复算法留下了一个开放性问题“如何在使用write-ahead logging的情况下对记录加锁”。ARIES就是在这样的背景下写出来的。由于这篇文章试着综合了所有相关工作，并对那些可能成为ARIES算法一部分的特征进行了解释，导致这篇文章写出来后非常长，接近70页，这也使得它成为TODS历史上唯一超过50页限制而被接受的文章。1993年，Jim Gray和Andreas Reuter 合写的关于事务处理的经典书籍“Transaction Processing:Concepts and Techniques”出版。
最后再简要介绍下Jim Gray吧：关系数据库领域大师，因在数据库和事务处理研究和实现方面的开创性贡献而获得1998年图灵奖。美国科学院、工程院两院院士，ACM和IEEE两会会士。1966年在UC Berkeley拿到数学工程系学位，之后去纽约大学科朗研究所呆了一年，1967年又回到了Berkeley，仅用了一年半就拿到了博士学位，不过论文题目不是关于数据库的，而是关于语法分析理论的。博士毕业后，先在Berkeley做了两年博士后，继续从事理论研究与系统开发工作，之后去了IBM。在IBM工作期间参与和主持了IMS、System R、SQL/DS、DB2等项目的开发。后任职于微软研究院，主要关注应用数据库技术来处理各学科的海量信息。2007年1月独自驾船出海后失踪。
起初Jim Gray是做操作系统研究的，之所以转行研究数据库系统，据Jim Gray自己的说法是这样的：有一次，他上司的上司来到他办公室，对他说“Jim啊，你看现在市场上已经出现了这么多的操作系统，但是还没有一个像样的网络操作系统和数据库系统，如果你真想在IBM做出点成绩的话，研究网络操作系统和数据库系统是很有前途的！”，于是Jim Gray就听从了他的建议。其实当时Jim Gray正在做关于面向对象操作系统的研究，现在看来这个选择也是对的，因为面向对象操作系统这个方向很快就被人们放弃了。
Jim Gray有个好习惯，就是经常记笔记写备忘录。无论何时去旅行，都会写旅行报告；无论何时与人谈话都会把得到的想法做备忘录，凭借这些，他写了许多文章，参加了很多国际会议，并出了名。开发System R时，同事Franco一年写了两万行代码，但Jim Gray经常花时间写作，旅游，一年才写了一万行代码，于是老大经常会去敲他的门说“快点写代码!!-_-”，根据Jim Gray的回忆，整个开发过程中他大概写了五万到七万行代码，主要是涉及并发控制，系统恢复，系统启动，安全性管理等方面。
本文主要参考“Concurrency Control and Recovery in Database Systems”，重点回顾下2PC的相关知识。
]
背景介绍
事务处理的困难源于两个方面：concurrency和failures。为了达到高的性能，并发是必要的。而在现实中，计算机系统会面临各种各样的故障，操作系统可能会出错，硬件也有可能会出错。当这些错误发生时，应用程序可能会在正执行的过程中被打断，而这可能会产生错误的结果。比如用户正在转账，在中间失败可能会导致一个账户上的钱少了，但是另一个账户却没有收到钱的情况。Recovery就是要避免因故障而产生错误结果。所以就引出了Concurrency Control和Recovery这两个概念。
对于一个解决了并发控制和恢复问题的系统来说，在用户看来，所有程序的执行都是原子的(看起来就好像没有其他程序在并行执行)，可靠的(看起来好像并没有故障发生)。这种原子的可靠的程序执行过程就称之为事务。并发控制算法用来保证事务原子性地执行。
一个分布式事务T有一个主节点—即发起事务的那个节点。T首先将它的操作提交给位于主节点上的TM(transaction manager)，之后TM再将这些操作转发给其他对应的节点。比如一个Read(x)或者Write(x)操作将会被转发给x所在的那个节点，然后由那个节点的调度器和DM进行处理，看起来就像是一个本地事务一样。之后会再将操作结果返回给主节点上的TM。因此，除了需要对节点间的请求和响应进行路由外，在一个分布式DBS中对读写操作的处理与一个集中式的系统并没有什么不同。
现在来考虑下T的Commit操作。这个操作需要转发给哪些节点呢？不像Read(x)或者Write(x)操作那样，只需要关注存储了x的那个节点，Commit操作需要关注所有与事务T的处理相关的节点。因此，T的主节点上的TM需要将T中的Commit操作转发给那些T中数据访问涉及的所有节点。对于Abort操作也是一样。也就是说要求单个处理操作(Commit或者Abort)必须作用在分布式DBS的多个节点上，这是集中式与分布式事务处理的一个根本区别。
这个问题比它表面上看起来的要复杂地多。仅仅让分布式事务主节点上的TM给其他所有节点发送Commit操作是不够的。这是因为TM发送了Commit操作并不意味着事务提交完成了，还要DM执行这个Commit操作。虽然TM发送了Commit操作，但是调度器有可能拒绝这个请求，同时将事务Abort。在这种情况下，如果事务是分布式的，那么还需要所有相关节点也都要进行Abort。
集中式与分布式事务的另一个重要的不同点在于它们各自所需关注的错误的属性上。在集中式系统中，错误都是要么不错要么全错(all-or-nothing)，也就是说要么系统正常工作事务正常处理，要么系统出错不会有任何事务完成。但是在分布式系统中，可能出现部分失败(partial failures)的情况，某些节点正常工作但是其他一些节点出错了。
在分布式系统中故障不一定导致严重问题的这种属性为分布式系统提高自身可靠性创造了机会。同时这也是分布式系统倍受推崇的一个属性。但是很少被人提到的是，这种局部失败的情况正是造成分布式系统中很多难解的问题的根源。
在事务处理中就有这样的一个难解问题，即事务终止的一致性。如前所述，分布式事务的Commit或Abort操作必须要保证在事务的数据访问涉及到的所有节点上执行。在允许局部失败的情况下，这个问题变得非常复杂。
我们将可以保证这种一致性的算法称为原子性提交协议(ACP-atomic commitment protocol)。本章我们的主要目标就是介绍这种可以容忍各种错误的ACP协议。在具体介绍之前，我们先详细介绍下分布式系统中存在的各种错误类型。
分布式系统中的故障
分布式系统由两种组件组成：负责处理信息的节点和负责在节点间传递消息的通信链路。通常可以用一个图来进行表示，图的结点代表节点，无向边代表双向的通信链路(如图7-1)。
我们假设图是连通的，即任意结点间都存在一条路径。因此任意两个节点都可以通过它们间的一个或者是多个链路进行通信。我们将这种可以让节点间进行消息传输的软硬件设备统称为计算机网络。我们不需要担心消息是如何被路由的，对于分布式数据库系统来说路由是网络系统提供的基本服务。
节点故障
当节点发生系统故障时，进程将会异常终止同时内存内容会丢失。在这种情况下，我们就说节点发生故障了。当节点从故障中恢复时将会首先执行一个恢复过程，使得节点可以达到一个一致性状态，之后才可以继续正常的处理过程。
在这种故障模型中：站点要么是可以正常工作(称它是operational的)要么是完全无法工作(称之为down)，它永远都不会执行错误的动作，这种类型的行为也被称为fail-stop。很明显这有些理想化。由于软硬件bug的存在，计算机偶尔还是有可能会执行不正确的动作。通过不断的测试以及软硬件内建的冗余，可以构建出一个基本上满足fail-stop的系统。我们并不想在本文中深入讨论这些技术，我们假设节点都是fail-stop的。本章中我们将要讨论的各个协议的正确性将会基于这个假设。
尽管单个节点只有两个状态，要么正常工作要么停止工作，但是不同节点可能处于不同状态。这样仍然会存在一种局部故障(partial failure)的情况：某些节点正常某些节点down掉。如果所有节点都down掉的话就是total failure的情况。
Partial Failure很难处理。从根本上说，这是因为正常工作的节点根本无法确定失败的那些节点的状态。在这些不确定性解决之前，正常节点可能会被阻塞，无法Commit或者Abort一个事务。原子性提交协议的一个重要设计目标就是要尽量将单个节点的故障的影响最小化，使得其他节点可以继续处理。
通信故障
通信链路也有可能发生故障。故障可能使得节点之间无法通信。可能有各种各样的通信故障：消息内容可能会由于链路上的噪声被破坏；链路可能临时失灵，导致单个消息完全丢失；链路可能会中断一段时间，导致通过它的所有消息都丢失。
消息的损坏可以通过错误检测码进行检测，然后在接收者检测到错误的时候进行重传来进行高效地处理。由于链路故障导致的消息丢失可以通过重传丢失的消息进行处理。同时，也可以通过重新路由来降低链路丢包概率。如果消息是从节点A传给节点B的，但是由于链路断开导致网络无法对消息进行传输，那么网络系统会尝试寻找一条新的从A到B的路径。错误检测码，消息重传以及重新路由通常都是由计算机网络协议提供的功能。
不幸的是，即使有自动的重新路由，节点和链路的故障仍可能导致节点间无法通信。当节点间的所有路径上都包含一个有故障的节点或链路时就会出现这种情况。通常称之为网络分区，它会将所有节点分割为两个或者更多个子集，在子集内部的节点相互可以通信，子集之间无法通信。比如，图7-2就展示了图7-1的一个系统分区。图中包含两个分区{B,C}和{D,E}，是由节点A和链路(C,D)(C,E)的故障造成的。
当节点恢复和链路修复后，那些之前无法交换信息的节点的通信就会恢复。比如图7-2，如果节点A恢复或者(C,D)(C,E)中有一个修复了，那么这两个分区就又连接起来了，所有的节点就又可以通信了。
我们可以通过设计一个高度互联的网络来降低网络分区发生的概率，这样部分节点和链路的故障不会导致节点间的路径全部不通。但是，构建一个高度互联的网络需要使用更多的组件，因此成本会更高。此外，网络拓扑还会受到其他因素的限制，比如地理位置和通信媒介。因此，分区是无法完全避免的。
总之，通信故障发生在节点A无法与节点B无法通信时，尽管两个节点都没有down掉。通信故障可能会引发网络分区。如果两个节点可以通信，消息就会被正确地传输。
无法传送的消息
节点和通信故障的存在需要我们能够处理那些不能发送的消息。消息可能会因为接收者down掉或者网络分区的存在，而无法发送。有两种选择：
1. 持久化消息。由网络系统对消息进行存储，在可以发送时再发送
2. 丢失消息。网络系统不再尝试重发
我们选择第2种方式，这也是很多设备采用的方式。第1种方式需要非常复杂的协议，它们本身非常类似于ACPs，基本上等于是将原子性提交问题扩散到了系统中另一个部分。
采用第2种方式的网络系统会尝试通知消息的发送者消息被丢掉了。但是这样也有其固有的不可靠性。如果节点无法对收到的消息进行确认，网络是无法判断出是这个节点根本没有收到消息还是它已经收到了消息只是确认时失败了。即使它能区分出这个不同，对未发送消息的发送者的通知也可能导致无穷递归，比如如果进行通知的消息本身未能发送成功，那么通知的发送者也需要再次被通知，就会再次产生通知消息，如此循环。因此，是不能依赖这种未发送消息的通知机制的。
通过超时检测故障
节点故障和通信故障都可能使得一个节点无法与另一个节点进行通信。也就是说，如果节点A无法与节点B进行通信，那么要么是因为B出问题了，要么是因为A和B分属于不同的分区。通常，A无法区分出这两种情况。它只是知道无法与B进行通信。
那A怎么知道无法与B进行通信呢？通常都是通过超时机制来确定的。A向B发送一个消息，然后等待一个预先确定的时间段，称之为超时时间段。在此期间，如果收到了响应，那么很明显A和B是可以通信的。如果超过了这个时间段，A还没有收到响应，那么A就认为它无法与B完成通信。这个时间段必须是从A到B发送消息加上B处理消息再加上返回给A这三个过程所花费的最大可能时间。找出一个合理的超时时间并不是一件简单的事情。它依赖于很多难以量化的参数：节点和通信链路的物理特性，系统负载，消息路由算法，时钟精度等等很多因素。实践中通常也只是选择一个对大多数情况都算合理的超时时间。在使用超时机制时，我们都是假设已经定好了这样的一个超时时间取值。事实上，即使是还没到超时时间，节点也有可能认为它无法与另一节点通信。这种情况的发生通常是因为时钟不精确导致的。我们通常将这类故障称为timeout failures或者performance failures。与网络分区不同，这类故障可能会导致很奇怪的情况，比如A认为它可以与B进行通信，但是B却认为它无法与A通信；或者是A认为它可以与B通信，同时B认为可以跟C通信，但是A却认为它不能与C进行通信。
原子性提交
考虑一个执行过程涉及到节点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是说节点上事务的执行结果是不可更改的。如果事务一旦提交(或abort)，那么之后它就不能再被abort(或提交)。
AC3是说只有当事务执行中涉及的所有节点都同意时事务才能提交。AC4是AC3的逆的一个弱化版本。它确保了在某些情况下必须达成Commit决定，因此就将那些总是采用选择Abort的平凡解法的协议排除在外了。但是我们也并不要求AC3的逆完全成立。因为就算所有进程都投的是Yes，但是最终还是有可能Abort的(比如发生了故障，进程投的Yes并未被接收到)。关于AC3的一个非常重要的推论是，在进程还未投Yes的情况下，它可以在任意时刻单方面的选择Abort。另一方面，一旦投了Yes它就不能再单方面地采取行动。在进程投了Yes之后到它获取足够的信息来确定最终决定是啥之前，这中间的这个时间段称为进程的不确定区间(uncertainty period)。当进程处在这个时间段时，我们就说进程是不确定的(uncertain)。在这个时间段内，进程既不知道最终决定是要Commit还是Abort，也不能单方面地决定Abort。
场景1：在P处于不确定状态时，故障导致进程P与其他进程不可通信。根据不确定区间的定义，在故障恢复之前进程无法达到决定状态。
在继续处理之前进程必须等待故障被修复，也就是说它被阻塞了。阻塞并不是我们期望的，因为它可能导致进程等待任意长的时间。场景1表明通信故障可能导致进程被阻塞。
场景2：在处于不确定状态时，进程P发生故障。在P恢复时，它无法仅通过它自身决定状态。它必须与其他进程进行通信以确定决定是啥。
我们将进程不需要与其他进程进行通信就能够进行恢复的能力称为独立可恢复性(independent recovery)。这种能力非常吸引人，因为它简单低廉。此外，如果缺乏这种能力那么在所有进程都发生故障的情况下，会导致阻塞。比如，我们假设p是在一个total failure中第一个恢复的进程，因为p处于不确定状态，因此它需要与其他进程进行通信以确定状态，但是其他的都还down着呢，因此它就无法与它们进行通信，因此p就被阻塞了。
这两个场景表明，在进程处于不确定状态时发生的故障可能导致严重的问题。那么我们是否能够设计出一种没有不确定阶段的ACPs？不幸的是，不能。我们有如下一些结论：
1. 如果可能发生通信故障或者完全故障，那么所有的ACPs都可能会导致进程被阻塞
2. 没有一种ACP可以保证故障进程的独立可恢复性
两阶段提交协议
两阶段提交协议是最简单最流行的ACP。在没有故障发生的情况下，它的执行过程如下：
1. 协调者发送一个VOTE-REQ消息给所有的参与者
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。有两个原因，首先在协议的很多点上，进程在继续处理之前必须要等待消息。但是消息可能会由于故障而无法到达。因此，进程可能会无限等待下去。为避免这个问题，需要使用超时机制。当进程的等待因为超时而打断时，进程必须采取特定的动作，称之为超时动作。因此，为满足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来完成。
最简单的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就是参与者节点。那么有如下三种可能：
? DT log中包含一个commit(或abort)记录。那么说明在发生故障之前，参与者已经达成了决定。
? DT log中没有yes记录。那么要么是参与者是在投票前发生的故障，要么投的是No(但是在发生故障前还没有完成abort记录的写入)。(这也是为何yes记录必须要在发送YES消息前写入日志的原因；参考上面的第2点。)因此，它可以单方面地通过向DT log中写入一条abort记录决定进行Abort。
? DT log中包含了yes记录，但是没有commit(或abort)记录。那么说明参与者是在不确定区间内发生的故障。它可以通过使用terminaion protocol来达成决定。回想一下，yes记录中包含了协调者名称以及所有的参与者，这正是terminaion protocol所需要的。
图7-3和7-4给出了2PC协议和cooperative terminaion protocol的具体实现，包括了上面讨论的关于超时处理和DT log相关的处理动作。算法的表达比较随意，但是直接明了。我们采用send和wait来表示进程间通信。比如“send m to p”，m代表一个消息，p代表一个或多个进程，总的意思就是执行进程将m发送给p中的所有进程。“wait for m from p”，m代表一个或多个消息，p代表一个进程，总的意思就是执行进程一直等待，直到收到来自p的消息m。如果消息可能来自多个目标，那么如下两种表示方式，“wait for m from all p”表示进程会一直等待直到收到p中所有进程发送的消息，“wait for m from any p”表示进程会一直等待直到收到p中某个进程发送的消息。为避免无限等待，可以在“wait for”语句后面加上一个“on timeout S”进行限定，S代表某种执行语句。这意味着如果消息在一个预先定义的超时时间内还未收到，那么就不再继续等待，同时语句S将会被执行，之后控制流将会继续正常往下执行，除非S中做了一些特殊控制。如果消息在正常时间内到达，那么S将会被忽略。
尽管我们一直描述的是针对单个事务的ACPs，但是很明显DT log将会包含来自多个事务的与原子性提交相关的记录信息。因此，为防止不同事务间记录信息的混淆，start-2PC,yes,commit和abort记录都会包含一些信息标识它们属于哪个事务。此外，也需要对DT log中的那些过期信息进行垃圾回收。在垃圾回收时，有如下两个基本原则需要遵守：
GC1：至少要等到RM执行了RM-Commit(T)和RM-Abort(T)之后，节点才能将事务T的相关日志记录从它的DT log中删除。
GC2：至少有一个节点在它收到事务T涉及的所有节点都执行了RM-Commit(T)和RM-Abort(T)的消息之前，不会将事务T的相关日志记录从它的DT log中删除。
GC1是说与事务T的执行相关的节点，在该事务作用于该节点之前它必须牢记该事务的存在。GC2是说，与事务T的执行相关的某个节点，在该节点确认事务在所有节点上成功执行之前，必须记住事务T的状态。如果不是这样的话，那么从故障中恢复的一个节点可能会无法获取T的状态，同时它也永远都不能确定事务T的状态，这就违背了AC5。
通过使用每个节点上的本地信息就可以确保GC1。但是GC2需要节点间通信的支持。为了实现GC2通常有两种极端策略：GC2只对一个节点成立，通常都是协调者；GC2对于T的执行相关的所有节点都成立。
我们关于ACP的研究都是从单个事务的角度来看的，这也隐藏了节点恢复时的一些问题。在一个节点恢复时，它必须要为那些故障发生前还未commit或abort的所有事务完成ACP的执行。什么时候节点可以恢复正常的事务处理呢？在一个集中化的DBS恢复后，在重启过程完成之前事务是无法被处理的，因为需要恢复那些已存储的数据库状态。分布式DBS中的节点恢复也与之类似，因为某些事务可能会被阻塞。在这种情况下，在该恢复节点的DBS在所有被阻塞的事务被提交或abort之前也是不可访问的。
避免这种问题的方法取决于所使用的调度器类型。考虑strict 2PL的情况。当节点的恢复过程已经为所有的未阻塞事务完成决定时，它应该通知调度器来重新获取那些在故障发生之前由被阻塞的事务占有的锁。实际上，一个被阻塞的事务T只需要获取它的写锁。问题在于锁表通常是保存在内存中的，因此在系统发生故障时会丢失。为避免丢失这些信息，负责管理T的原子性提交的进程需要将T的写锁也记录到它写入到DT log中的yes记录中。当然如果这些信息可以从该节点的RM维护的日志中获取，就没必要这样做。比如，在第6章描述的undo/redo算法，因为在T投Yes之前，所有的更新都会进入日志。这些记录就可以用来确定T的写锁集合。
针对2PC的评价
我们可以从如下几个维度来对2PC进行评价：
Resiliency：可以容忍哪些故障？
Blocking：进程是否有可能被阻塞？如果是，什么情况下会被阻塞？
时间复杂度：达成决定需要花多长时间？
消息复杂度：达成决定需要多少次消息交换？
前两个维度用来衡量协议的可靠性，后两个用来衡量协议的效率。可靠性和效率是两个冲突的目标：任意一个都可以以另一个为代价来获得。协议如何选择取决于对于特定的应用来说哪个目标更重要。但是，无论协议如何选择，我们都需要尽力对无故障时的情况进行优化—主要是提高系统的正常工作速率。
我们通过对非阻塞情况下节点达成一个决定最坏情况下所需要的消息交换轮数进行计数，来衡量ACP的时间复杂度。轮代表了消息到达目标节点所需的最大时间。用于故障检测的超时机制就是基于这个最大的消息延迟是已知的这样一个假设。需要注意的是，一轮内可能会有很多消息被发送—就看有多少个发送者-接收者对。如果一个消息必须等另一个消息接收到之后才能发送，那么这两个消息就肯定属于不同的轮。比如，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发送的消息数将是：
在n=m时该多项式取得最大值，也就是当所有参与者都在处于不确定区间时超时。因此，terminaion protocol贡献了多达n(3n+1)/2个消息，对于整个2PC协议来说就是n(3n+7)/2。
参考文献
http://stevens0102.blogbus.com/logs/43402056.html
附录
左一Ken Thompson、左二Butler Lampson、右二Jim Gray, 右一Niklaus Wirth
JimGray与它的同事Gianfranco Putzulo and Irving Traiger