分布式实时数据库的事务恢复机制.doc

分布式实时数据库的事务恢复机制摘要分布式技术与实时数据库技术二者的结合产生了分布式实时数据库。分布式实时数据库广泛应用在电子商务、电子信息服务和智能电信系统等领域。由于分布式实时数据库不是分布式技术与实时数据库技术功能的简单相加，所以增加了事务并发控制和数据库恢复的难度，特别是事务提交协议在分布式实时数据库的应用中存在很多问题，比如典型的“优先级倒置”问题，死锁问题等等。传统的事务提交协议在提交分布式事务时，在不同阶段及不同的参与结点之间交换各种信息，同时也会产生一些日志记录，其中有些必须写回磁盘，这对于实时数据库的实时性将有很大影响。因此，如何选择提交协议在设计一个分布式实时数据库系统中成为最重要的决定之一。本论文在对分布式实时数据库恢复技术和国内外现存的各种分布式实时数据库的事务提交协议进行分析和比较的基础上，提出了一种新的事务提交协议2scep( 即double space commit early prepare)协议。2scep协议从两个方面来提高其实时性能。一方面，对于处于预提交状态的事务，不仅健康的事务可以借出其所持有的数据，而且非健康事务也可借出其数据给其提交依赖集中的事务，因此提高了借出程度；另一方面，将提交处理的第一阶段与数据处理阶段交叉执行，增加了借出时间，减少了参与者处于预提交状态的等待时间，提高了系统的实时性能。本文详细阐述了2scep协议的协议机制、特点、事务提交处理及系统集成，并在一定的并发控制机制(基于改进的2pl-hp协议)之上构建了一个分布式实时数据库模型，分别实现了2sc协议及2scep协议，最后对2sc和2scep协议的性能进行了分析和比较，得出了有益的结果。关键词：分布式实时数据库，事务恢复，分布式实时事务提交协议，2scep协议study of the transactions recovery of distributed real-time databaseabstractdistributed real-time database system comes into being, which is widely employed in many fields such as e-commerce and information services as well as intelligent telecom systems. however, such a system is not a simple combination of real-time database technology and distributing technology. in such a system, difficulties of transaction concurrency control and transaction recovery grow up a lot. currently, commit protocol in this system is the one of the hard ones, with which much is still left to be done. for instance, the typical priority inversion problem and deadlock problem. traditional commit protocol requires exchange of various messages in multiple phases between the participating sites where a distributed transaction executes. in addition, several log records are generated, some of which must be “forced”，that is，flushed to disk immediately. such an action will definitely affect the performance of the real-time system. therefore, an effective commit protocol is a must in the establishment of a real-time database system with high performance. after a detailed technical analysis of the recovery mechanism of real-time database system and a further comparative study of current commit protocol, this dissertation comes up with a new commit protocol named 2scep(short form for double space commit early prepare). it gains good performance. on the one hand, when a cohort in preparing (to commit) want to enter committing phase, not only a healthy transaction could lend its data, but an unhealthy transaction could lend its data to transactions which is in its commit dependency set. on the other hand, the first phase of commit processing is overlapped with the data processing phase, which reduce the overheads of waiting time in preparing state and increase the time for lending. so it enhances the real-time performance of the drtdbs.this dissertation discusses the features, protocol mechanics, system integration and data processing phase of 2scep protocol. and based on it, a simulation model is established with one concurrency control protocol (improved two phase lock-high priority, 2pl-hp), and a further extensive experiment with 2sc protocol, is carried out to compare its performance with beneficial results concluded. key words: distributed real-time database(drtdb)，transaction recovery，distributed real-time transaction commit protocol，2scep protocolii目录 序 言1第1章集中式数据库的事务恢复机制31.1事务恢复31.2 基于运行记录的恢复技术31.3 运行记录的结构4第2章分布式数据库的事务恢复机制62.1 故障模型62.1.1集中式数据库系统的故障模型62.1.2分布式数据库系统的通讯故障模型62.2分布式数据库中的事务提交协议72.2.12pc协议72.2.2 3pc协议122.3 分布式数据库中对故障的处理13第3章分布式实时数据库的事务提交协议163.1分布式实时数据库的事务提交163.1.1分布式实时数据库163.1.2分布式实时数据库的事务提交173.2分布式实时数据库中的事务提交协议173.2.1 prompt协议183.2.2 ddcr协议193.2.3 2sc协议223.2.4 几种协议的比较23第4章2scep协议254.12scep协议特点254.1.1 一段提交处理254.1.2预提交数据的借出254.1.3解决恶意借出和死锁问题264.1.4数据冲突解决机制284.1.5cohorts的内在的主动终止284.1.6内在的基于进度的优先级增加294.22scep协议机制294.32scep协议的提交处理314.4系统集成32第5章实验模型的构建345.1实验模型的构建原则345.1.1数据库模型355.1.2时限分配355.1.3事务执行355.1.4优先级分配365.1.5并发控制365.1.6日志375.1.7性能参数375.2模型的构建375.2.1开发平台375.2.2 分布式实时数据库系统模型的整体结构385.2.3分布式实时数据库模型的设计395.2.4分布式实时数据库系统模型事务管理层的设计40总结与展望47参考文献48致 谢50攻读硕士学位期间发表的学术论文目录5152中南民族大学硕士学 位 论文序 言实时系统和数据库结合产生的实时数据库技术在工厂生产自动控制、电话交换、电力或数据网络管理、雷达跟踪、cims(computer integrated manufacturing system)、证券交易等领域应用日益广泛。同时，随着网络技术和分布式计算的蓬勃发展应运而生的电子商务、电子信息服务和智能电信系统等，要求实时数据存贮在分布的结点上。这就产生了分布式实时数据库。由于分布式实时数据库增加了事务并发控制和数据库恢复的难度，因此它不可能是二者功能的简单相加。特别是分布事务提交协议在分布式实时数据库的应用中存在很多问题，比如典型的“优先级倒置”问题，死锁问题等等。传统的事务提交协议要求在不同阶段，在不同的参与结点之间交换各种信息。同时，会产生一些日志记录，其中有些必须写回磁盘。这对实时数据库的实时性将有很大影响。因此，选择提交协议在设计一个分布式实时数据库系统中成为最重要的决定之一。分布式实时数据库系统中的事务提交处理是当前rtdbs（real-time database systems）和rtss（real-time systems symposium）两大年会研究的重点所在。本论文重点分析、研究了目前国内外分布式实时数据库事务提交协议的最新研究成果，并提出了一种新的事务提交协议2scep协议(for double space commit early prepare)。2scep协议从两个方面来改进其实时性能：一方面，对于处于预提交状态的事务，不仅健康的事务可以借出其所持有的数据，即使是非健康事务也可借出数据给其提交依赖集中的事务，因此增加了借出程度；另一方面，将提交处理的第一阶段与数据处理阶段交叉执行，增加了借出时间，减少了参与者处于预提交状态的等待时间，因此提高了系统的实时性能。作为验证，构建了一个分布式实时数据库模型，在一定的并发控制机制之上(扩展的2plhp协议)实现了2sc协议及2scep协议。本论文的整体框架如下：首先介绍了传统的集中式数据库的事务恢复机制；然后介绍了分布式数据库的事务恢复机制，说明了它与集中式数据库的事务恢复机制的异同及其所具有的难度，并详细介绍了分布式数据库的事务提交协议（2pc协议和3pc协议）；接下来介绍了在分布式实时数据库中使用传统分布式数据库的事务提交协议（2pc）所带来的问题，并分别介绍了为解决这些问题而提出的适用于分布式实时数据库的事务提交协议：prompt、pep、ddcr、2sc协议等；然后基于以上的分析、比较，提出了一种新的分布式实时事务提交协议2scep协议，并详细介绍了2scep协议的协议机制，分析其可能出现的问题，提供了解决方案；为了验证2scep协议的性能，我们构建了一个实验模型，并给出了其详细的构建过程；最后通过实验结果分析，得出了有益的结论。第1章集中式数据库的事务恢复机制1.1事务恢复事务是数据库管理系统（dbms）的执行单位，事务应满足acid（原子性，一致性，隔离性，持久性）准则。保证事务在故障时满足acid准则的技术称为恢复。要恢复丢失的数据，数据必须有后备的复本。对于恢复，数据冗余是必需的。恢复技术大致分为下列3种：1.单纯以后备复本为基础的恢复技术 即周期性地把磁盘上的数据库转储(dump)到磁带上，磁带上的数据库复本称为后备复本。当数据库失效时，可取最近的后备复本来恢复数据库。 此种恢复技术实现简单，但不能恢复到数据库的最近一致状态。 2.以后备复本和运行记录（log或journal）为基础的恢复技术运行记录是供恢复用的数据库运行情况的记录。当数据库失效时，可取出最近后备复本，然后根据运行记录，对未提交的事务用前像卷回；对已提交的事务，必要时用后像重做。由于此种恢复技术可使数据库恢复至最近的一致状态，在数据库系统中用得最多。3.基于多复本的恢复技术如果系统中有多个数据库复本，而且这些复本具有独立的失效模式(指各个复本不致因同一故障而一起失效)，则可利用这些复本互为备份，用于恢复。近来由于硬件价格下降，在某些可靠性要求高的系统中，采用镜像磁盘技术，即数据库以双复本的形式存于两个独立的磁盘系统中。由于第二种恢复技术在数据库系统中用得最多，大部分商品化的dbms都支持这种恢复技术，以下我们对这种恢复技术进行详细介绍。1.2 基于运行记录的恢复技术运行记录王能斌编著，数据库系统原理，电子工业出版，2000年1月，136-161是供恢复用的数据库运行情况的记录。一般包括下列3个内容：1.前像（before image,bi）：当数据库被一个事务更新时，所涉及的物理块更新前的映像（image）称为该事务的前像。前像以物理块为单位。有了前像，如果需要，可以使数据库恢复到更新前的状态，即撤消更新，这种操作在恢复技术中称为撤消（undo）。 2.后像（after image,ai）：当数据库被一个事务更新时，所涉及的物理块更新后的映像（image）称为该事务的后像。后像以物理块为单位。有了后像，即使更新的数据丢失了，仍可以使数据库恢复到更新后的状态，相当于重做一次更新，这种操作在恢复技术中称为重做（redo）。3.事务状态：记录每个事务的状态，以便在恢复时做不同的处理。每个事务从交付dbms到结束为止，其状态的变迁如图1-1所示。每个事务有两种可能的结局：一是经提交（commit）而结束，这标志着事务已成功地执行（这相当于all），只有在事务提交后，事务对数据库的更新才能被其它事务访问；另一种结局是由于事务本身或外部的原因，事务失败，要消除事务对数据库的影响(这相当于nothing)。对事务的这种处理称为卷回（rollback或abort）。对恢复来说，不必记下图1-1中的每个状态，但是至少要区分出一个事务是提交的，还是未提交的。事务结束图1-1事务状态变迁图事务开始活动状态操作结束事务提交事务失败卷回事务结束当数据库失效时，可取出最近后备复本，然后根据运行记录，对未提交的事务用前像卷回，这叫向后恢复（backward recovery）；对已提交的事务，必要时用后像重做，这叫向前恢复（forward recovery）。用这种恢复技术，必须有运行记录。 1.3 运行记录的结构运行记录一般不能和数据库放在同一磁盘上，以免在磁盘损坏时，两者同归于尽。运行记录的结构因数据库管理系统（dbms）而异。下面列出运行记录中的一些基本内容，实际dbms的运行记录还可能包括若干其它细节，具体结构也不一定相同。1. 活动事务表活动事务表（active transaction list, 简称为atl）记录所有正在执行，尚未提交的事务的标识符（transaction identifier，简称tid）。2. 提交事务表提交事务表（committed transaction list,简称ctl）记录所有已提交的事务的标识符。在提交时，应先将要提交的tid列入提交事务表，然后再从活动事务表中删除该tid。如果先从活动事务表中删除tid，再将tid加入提交事务表，则可能冒如下的危险：即tid刚从活动事务表中删除后，该事务的状态在系统中将无任何记录。3. 前像文件前像文件可以看成一个堆文件，每个物理块有个块标识符（block identifier,简称bid）。设bid由tid、关系名和逻辑块号所组成，其中tid表示执行更新操作的事务，关系名表示被更新的关系，逻辑块号表示该块是关系中哪块的前像。逻辑块号在关系中是唯一的，即使一个块被删除了，它的逻辑块号也不允许重新使用。如果一个关系需要卷回，可从前像文件中找出该事务的所有前像块，按照逻辑块号写入关系的对应块中，从而消除该事务对数据库所产生的影响。必须注意：undo操作是满足幂等（idempotent）性的，即undo(undo(undo（x）)=undo(x)因此，即使数据库中的某块还没有来得及更新，在恢复时对它做一次undo操作也无妨，无非在这一块上写入同样的内容而已。4. 后像文件结构与前像文件相仿，不过其中记的是后像。在恢复时，可按提交事务表中的事务次序，按逻辑块号写入其后像。这相当于按提交的次序，重做各个事务。redo操作也满足幂等性。第2章分布式数据库的事务恢复机制2.1 故障模型2.1.1集中式数据库系统的故障模型局部场地上的数据库系统，就是一个集中式数据库系统，其恢复主要是针对数据的丢失。其故障的类型主要可以分为以下几类：1. 不丢失信息的故障。这一类故障主要由于命令无法执行引起事务中止，而不会对存储介质上的数据产生不正确的操作。这一类的故障很容易恢复，重启事务即可。2. 丢失主存信息的故障。此时，主存中的数据库处于一种不正确状态，即部分或全部数据丢失或出错。但在辅存上的数据库仍处于正确的状态，如事务未正确提交或中止，破坏了事务原子性。这一类故障可利用恢复机制对其进行恢复。3. 丢失辅存中信息的故障。这一类故障对于数据库系统是致命的，此时由于主存中数据是不一致的，而辅存中数据丢失，使故障按常规方法不可能恢复，只能重建数据库。我们的恢复策略主要解决第二类故障。2.1.2分布式数据库系统的通讯故障模型除上述可能发生的故障外，分布式数据库系统还具有自己特有的故障模型，主要体现在系统中场地间的通讯故障。通讯故障可以分为以下两种：报文丢失和网络分割。1. 报文丢失是指传送过程中报文的丢失导致数据不正确。这时必然得不到肯定的回答，或者报文正确传送了，而应答信息未正确传到。这种报文丢失造成系统的等待状态可以通过一有限的协议加以解决，即传送的报文的数目是有限的。传送的过程一定在一有限的时间内完成。因此当一段时间的延迟以后仍收不到回答则认为报文丢失，此时将重发报文。若重发若干次后仍得不到回答，则认为网络发生故障或通讯中的另一场地故障，这时进入相应的恢复处理。2. 网络分割是指通讯网络中一部分场地和另一部分场地之间完全失去联系。当出现网络分割时，两个分别在分离后的网络的两个(或若干个)部分中的场地间不可以直接进行通讯，且也不能经过第三方场地进行通讯。当出现网络分割时，系统处理要复杂一些，但出现网络分割的情况是非常少的。把故障的恢复处理的难度从小到大排列分为三类：一是场地故障；二是场地故障和丢失报文，但无网络分割；三是场地故障，丢失报文及网络分割。第一类恢复处理只处理局部场地的故障，假设通讯网络是永远正确的，这主要基于集中式数据库系统的恢复策略；当出现通讯故障后则束手无策。第二类处理报文丢失和场地故障。第三类可处理除第二类故障外的网络分割故障。2.2分布式数据库中的事务提交协议在分布式数据库系统中，全局事务可以分解为若干子事务，分布在不同的结点上。系统不但要保证子事务的原子性，还要保证全局事务的原子性。这需要在结点间进行协调。因此提出了二步提交协议（two-phase commit，2pc）和三步提交协议（three-phase commit，3pc）。当一个事务分布在多个结点上执行时，各结点须保持一致，要么都提交，要么都卷回。为了保持多结点协调一致，可以指定其中一个结点的事务管理器（以下简称结点）为协调者（coordinator/master），其他结点的事务管理器为参与者（participant/cohort）。2.2.12pc协议1. 2pc协议原理2pc协议 j.gray,notes on database operating systems,operating systems:an advanced course,lecture notes in computer science,60,1978.是一种用于故障恢复的方法，在系统运行日志无丢失的情况下，2pc协议对任何故障均有一定的恢复能力。两步提交协议由于其简单、实用和可靠，在分布式数据库系统中得到广泛的应用，已成为事实上的工业标准。参与者协调者prepareok/not okcommit/rollbackack图2-1两步提交协议2pc协议的基本思想是为全部的参与者做出提交或中止全部局部子事务的唯一决定。在结束本事务时，协调者与参与者以如图2-1所示的通信过程相互应答。协调者在日志中写入“预提交”命令并记录所有参与者的子事务标识符发送“预提交(prepare)”命令给所有参与者且开始计时等待接收所有参与者的应答消息并检查限时if超时或收到至少一个“夭折”thenbegin在日志中记入“全部夭折”向所有的子事务发“夭折(rollback)”命令endelsebegin收到全部“准备提交”在日志中记入“全局提交”向所有的参与者发“提交(commit)” end等待接收所有场地的“执行”信息在日志中记入“完成”参与者等待“预提交”命令if参与者可以提交thenbegin 在日志中写入子事务的记录在日志中写入“准备提交”向协调者发“准备提交(ok)”end elsebegin在日志中写入“夭折”向协调者发“夭折（not ok）”信息end等待协调者的命令根据命令在日志中记入“夭折”或“提交”向协调者发送“执行”信息，然后执行“提交”或“夭折”命令图2-22pc协议原理图2pc将提交分为两个阶段：第一阶段，做出提交或中止全部子事务的决定，称之为决定阶段；第二阶段实现第一阶段的决定，称之为执行阶段，所以称为两段提交协议。参与者在回答ok之前，可以自行决定中止子事务的执行；可是在回答ok以后，参与者就没有权力自行中止子事务，而必须听命于协调者。2pc协议的工作原理如图2-2所示（图中虚线箭头表示时间轴）。在2pc协议的第一阶段，协调者要求所有的参与者均进入准备提交阶段（有时也称为预提交阶段），若参与者准备好了并愿意提交，就回答“提交”。在发送预提交命令前，协调者在日志中记入“预提交”记录及所有参与者的子事务标识符，并进入等待回答状态且开始计时。当一个参与者回答“准备提交”应答时，在日志中要记录该子事务的全部运行记录及该子事务已准备就绪的事实。协调者从各参与者接收消息，若超时或收到一个“夭折”回答，则决定“夭折”事务，否则收到所有的“准备提交”回答，决定提交事务。在2pc协议的第二阶段，当协调者做出决定后，在日志中记入相应的记录，将“全部提交”或“全部夭折”写入运行记录。这表明不论发生什么情况，分布式事务最终将“提交”或“夭折”，然后协调者向所有的参与者发送“提交”或“夭折”命令。所有的参与者根据协调者的命令在本场地日志中写入“提交”或“中止”记录。从此时起，局部恢复程序保证不丢失该子事务的实施，执行“提交”或“中止”命令向协调者发“执行”信息。协调者从所有参与者处收到执行报文，在日志中记入“完成”记录，此时分布事务的2pc完成。在恢复算法的下一检查点之后，日志中关于此事务的全部记录可以离线。2. 2pc协议的实现算法2pc协议的实现算法按各参与者之间的通讯结构可以分为以下四种。(1)线性的2pc协议线性的2pc协议中，事务的始发场地构造一个线性有序的场地表，在进行事务的提交过程时，事务的始发场地首先进入“准备提交”状态以后，向表中的下一场地参与者发“准备提交”命令。若该场地已准备好且愿意提交，则由该场地把“准备提交”记入日志，向上一场发送“准备提交回答”，自己变为当前场地，继续向下一场地发“准备提交”命令。依次类推直到最后一个场地为止。如图2-3所示。图2-3表示有5个节点，开始时前一节点作为协调者，下一节点作为参与者，当消息传到最后一个节点时，最后一个节点充当了协调者，向前一个节点发送消息，而前一个节点作为参与者。图2-3线性2pc(2)集中式的2pc协议首先选一个场地作为协调者(一般由事务的始发场地充当)，提交的初始化工作由始发场地完成。首先，协调者把所有参与者的标识写入到日志中，然后向所有的参与者发送“预提交”报文征求各参与者的意向。各参与者收到“预提交”命令后，若准备好提交则发赞同应答并进入就绪状态，否则发否决报文。协调者收到一个拒绝报文就决定中止，在日志中记入“夭折”记录并向各参与者发夭折命令，然后进入夭折状态；否则收到所有的赞同应答，决定提交，将提交记录写入日志，向各参与者提交命令进入提交状态。处于就绪状态的参与者收到提交命令，便把“提交”记录记入日志，并向协调者发提交应答报文撤消子事务，若参与者收到中止命令，则处于就绪状态的参与者要恢复子事务，将中止记录写入日志向协调者发送中止应答报文。如图2-4所示。图2-4中节点做为初始节点，即为协调者，其余的节点作为参与者。(应答)(提交或夭折)(准备提交或夭折)(预提交) 图2-4集中式2pc(3)分层的2pc协议分层的2pc协议中，协调者所在场地称为树的根。参与者场地构成树的中间结点或叶结点，在树型结构中上一层的结点可以向下一层的结点发送信息或收集应答消息。中间结点在收集了其下一层结点的回答作出决定向上一层结点发送报文，直至根结点。集中式2pc是分层2pc协议的一个特例，其中无中间结点。在分层2pc协议中，信息的传送除了上述方法外还允许一个结点向其它的结点广播发送信息。(4)全分布式2pc协议全分布式2pc协议中，事务的所有参与者均可以建立相应的联系，每一场地上的参与者均可以决定事务的提交或中止。事务的提交过程是：事务的始发场地进行提交的初始化工作，然后向所有的参与者广播“预提交”报文，每个参与者收到命令后做出决定向所有的参与者发应答报文，每一场地的参与者根据其它参与者的应答做出提交或夭折事务。这种协议通讯费用巨大实际应用中很少采用。在以上四种2pc协议中，系统开销是以报文传送的个数与网络延迟给予评估的。若参与者的个数是n，则报文的个数为：线性2pc协议为2n个，集中式或分层2pc协议为4n个，而全布式的2pc协议为n（n1）个。线性协议中无执行（ack）报文，全分布式协议中执行（ack）报文已无意义。若报文从一个场地传送到另一个场地的延迟为t，则线性2pc的延迟为2nt，集中式2pc为4t，全分布式2pc延迟为2t，分层2pc为4t到2nt之间。总之，线性2pc的报文传输最少，响应效率最低，通讯代价较高的系统可以采用。全分布式2pc的报文传输最多，响应效率最高，适合传输代价较小的系统采用。集中式或分层式2pc介于上述两者之间。而且集中式2pc协议易于用c/s（客户端/服务器）结构实现，所以我们在实验模型的构建中采用集中式的通讯结构。3. 2pc协议的改进2pc协议中协调者与参与者之间要交换信息，还要写各种日志消息，如果减少这两方面的时间消耗，就可以改进其性能。所以可以从以下几个方面加以改进：1. 单方面的中止能力2pc协议允许参与者在给出“赞成提交”回答前中止它的子事务。这种场地的自治特性对局部管理系统来说是很重要的。一旦参与者做出“准备就绪”回答，局部管理系统就无法控制参与者了。2. 预提交报文的消除。在基本2pc协议中，其第一阶段可以结合到事务的执行中，当参与者完成了操作以后，可以直接发送“准备提交”报文而不必等协调者发送“预提交”命令后才发送。当协调者完成其相应的操作以后，也就知道其它参与者已“准备提交”，这时可以做出决定，而不必先发“预提交”命令等待其它参与者的回答(称为一段提交协议，1pc)。这样消除了“预提交”命令的发送，并将第一阶段结合到事务的执行中，提高了运行效率。然而它使参与者失去单方面中止自己子事务的能力，且在发出“准备提交”命令后等待协调者的回答，当协调者故障时会出现阻塞。因此，这种方法阻塞的可能性增加且降低了局部自治能力。3. 使用缺省提高效率。如果在日志中找不到该事务的任何信息，就认为缺省为“提交”或“中止”。这些协议称为“假定提交”（pc） c.mohan,b.lindsay and r.obermarck,”transaction management system”,acm tods,11(4),1986.和“假定终止”（pa）协议。2.2.2 3pc协议1.3pc协议工作过程在2pc协议中，可能出现阻塞状态。所谓阻塞是指，当参与者等待协调者的应答时，如果协调者出现故障，则参与者就必须阻塞。为了克服此缺点，提出了三步提交协议（简称为3pc协议） nonblocking commit protocols,s.son,data engineering,13(4),december 1990.。协调者参与者start xactyes/noackok/not okprepare图2-53pc协议commit/abort3pc协议在2pc的基础上增加了一个阶段，则将事务提交分为三个阶段，其通讯过程如图2-5所示。具体工作过程可描述如下：第一阶段，协调者向所有的参与者发“开始提交（start xact）”报文，由每个参与者据自己的情况进行投票，只有收到所有的参与者均赞成提交才进入第二阶段和第三阶段；第二阶段，协调者向所有的参与者发“准备提交（prepare）”报文，参与者收到该报文后若已经准备提交，则回答“准备就绪(ok)”报文，否则进行夭折处理；第三阶段，当协调者收到所有的参与者“准备就绪”的回答，就向所有的参与者发“提交(commit)”报文，此时每个参与者知道其它的参与者将“赞成”提交，因此它可以收到“提交”报文后就进行提交。2. 3pc解决阻塞问题在3pc协议的第三阶段中，当协调者收到全部的“准备就绪”的回答时才向所有的参与者发“提交”报文，此时，所有的参与者均知道其它的参与者已经进入“准备提交”状态。达到这一点，每个参与者均可以自己做出决定或夭折或提交，而不必因等待协调者的回答而进入阻塞状态，因为即使此时发生故障，系统的恢复机制迟早会恢复到故障前一刻的状态，即各参与者的子事务总会提交。因此，三步提交协议可以避免阻塞问题。虽然3pc协议可以避免阻塞，但实现比较复杂，通信次数也比较多，不适合于实时系统，所以在此我们不做详细介绍。郑振楣等编，分布式数据库，科学出版社，1998年7月，120-1332.3 分布式数据库中对故障的处理当分布式数据库系统发生故障时，要恢复丢失的数据，只要在事务提交时严格遵守分布式事务提交协议，就可以对各种故障进行恢复。如果采用2pc协议，则对各类故障的恢复可描述如下：1. 场地故障(1)当一参与者在写入“准备提交”前发生故障时，该参与者无法向协调者发回答信息，因此当协调者等待超时后，将决定中止事务。当该故障恢复后，重启动过程无须收集其他场地的信息即可中止事务。(2)参与者进程在写入“准备提交”后发生故障，这时其他的参与者可以正常的结束该事务“提交”或“夭折”，因为协调者可以根据收到的应答决定“提交”或“夭折”。因此，故障恢复后，重启动过程要访问协调者或参与者，以了解事务已做出的决定，然后执行相应的操作“提交”或“中止”。这里我们假设在日志中写入“准备提交”记录和发送“准备提交”信息给协调者。这两个动作具有原子性，要么都执行，要么都不执行。(3)协调者在日志中写入“预提交”记录后，写入“全部提交”或“全部夭折”前发生故障，这时已发出“准备提交”信息的参与者将等待协调者恢复。协调者的重启动过程从头恢复提交协议，从“预提交”记录中读出参与者的标识符，重发“预提交”报文给参与者，重新执行提交过程。(4)协调者在写入“全部提交”或“全部夭折”记录以后，在写入“完成”记录以前发生故障。在这种情况下，协调者恢复时必须给所有的参与者重发其决定，未收到信息的参与者不得不等待协调者的恢复。和(3)一样，参与者不应因收到两次一样的命令而受影响。(5)协调者在日志中写入“完成”记录后发生故障。这种情况下事务已结束，不需恢复处理。2.丢失报文 丢失报文的故障一般出现以下几种情况：(1) 来自参与者的回答报文(“准备提交”或“夭折”)至少丢失了一个。在这种情况下，协调者将等待回答而超时，整个事务被夭折。这种情况只由协调者发现，但它无法决定是场地故障还是通讯故障，而参与者正确执行，它不会启动恢复过程。(2) 丢失“预提交”报文，由于至少一个参与者收不到“预提交”命令，因此参与者处于等待状态，而协调者也等待参与者的回答，所以协调者会因为等待超时而夭折事务。这种情况和上述一样。(3) 丢失“提交”或“夭折”报文，这种情况下参与者处于等待协调者命令的状态下，当未收到命令时会因等待而超时，这时向协调者发请求重发该命令的信息。(4) 丢失了“执行”报文，当协调者未收到全部的“执行”报文时，协调者会因等待而超时，这时协调者重发命令报文给参与者，这时参与者必须给予“执行”报文回答，即使此时相应的子事务已不在活动也要重发。3.网络分割 假设在出现网络分割时，整个网被分为两个组，包含协调者的组称为协调者组，其它的则组成参与者组。这种情况下对于协调者来说相当于参与者组中的多个参与者同时发生故障，这时协调者可以作出决定，然后把命令发给协调者组中的参与者，因此这些场地上的子事务可以结束。这与场地故障中的(1)和(2)两种情况类似。对于参与者失去联系，这时它们认为协调者出现故障。这时它们认为协调者出现故障。这种情况与场地故障中的(3)和(4)相似。 从以上论述可以看出，对于处理分布式事务的站点来说，其恢复过程要比集中式数据库复杂。在集中式数据库中，只有两种可能，事务要么提交要么不提交，所以恢复机构执行相应的重做或取消动作。在分布式数据库还可能有其他情况：(1)一个参与者就绪(场地故障中的(2)(3)。由于在日志文件中有一预备记录而无提交或终止记录 ，所以恢复机构要能识别这种情况。(2)协调者已启动第一阶段(场地故障中的(4)。因为在日志文件中有一预备记录，没有“全局性提交”或“全局性终止”记录，所以恢复机构要能识别这种情况。(3)协调者已启动第二阶段(场地故障中的(5)。由于在运行记录中有预备记录和全局性“提交”或“终止”记录，而无事务的结束记录，所以恢复机构能识别这种情况。第3章分布式实时数据库的事务提交协议3.1分布式实时数据库的事务提交3.1.1分布式实时数据库1. 定义分布式实时数据库 王琳，喻成，实时数据库的现状与发展，河北理工大学学报，2003,4是一组实时数据集，逻辑上属于同一系统，而物理上这组实时数据集分散在用计算机网络连接的多个场地上，并统一由一个分布式实时数据库管理系统进行管理。2. 分布式实时数据库与实时数据库实时数据库系统刘云生著，现代数据库技术，国防工业出版社，2001年3月第1版，108-196 (real-time database system，rtdbs)是管理有时间限制的数据和有时间限制的事务，整个系统的正确性不仅依赖于逻辑结果，而且还依赖于逻辑结果产生的时间，也就是说系统宁可接受在时限内的不准确的数据，也不接受超过时限的准确的数据。分布式实时数据库是分布在多个结点上的实时数据库系统，但各实时数据库在逻辑上是统一的，不同于集中式的实时数据库。3. 分布式实时数据库与分布式数据库分布式数据库是计算机网络环境中各场地（site）或节点（node）上数据库的逻辑集合。但是传统分布式数据库中的存储及处理的数据不是实时数据，不能适应实时性要求高的场合，比如，随着网络技术和分布式计算的蓬勃发展而应运而生的电子商务、电子信息服务和智能电信系统等。即分布式实时数据库不是分布式数据库和实时数据库的简单相加，它增加了事务并发控制和数据库恢复的难度。又比如，在实时数据库中不同的数据和事务有定时限制，引入了优先级的概念，不同时限的事务具有不同的优先级，因此在事务处理时必须考虑优先级，但在传统分布式数据库中并没有考虑这个问题。再比如，事务提交问题，在分布式数据库系统中，一般采用经典的2pc协议来保证多个结点数据更新的原子性，如第2章所述，但在不同的提交阶段，2pc协议需要在不同的结点之间交换各种消息，而且还要产生许多日志记录，甚至其中的有些记录是必须立即写回磁盘的，因此增加了事务处理时间。但在分布式实时数据库系统中，对于时限的要求是非常严格的，所以传统的事务提交协议不适用于分布式实时数据系统，它有可能造成“优先级倒置”问题（即高优先级事务等待低优先级事务）和死锁问题(所有的事务均不能申请到全部的锁而进入永远的相互等待状态)。如何选择提交协议在设计一个分布式实时数据库系统中成为一个重要的决定，需要研究适合于实时环境的事务提交协议。3.1.2分布式实时数据库的事务提交前面也提到，分布式实时数据库系统中的事务提交问题是难点也是重点，因此，分布式实时数据库系统中的事务提交处理是当前rtdbs（real-time database systems）和rtss（real-time systems symposium）两大年会研究的重点所在。目前提出的协议有opt，prompt，ddcr，pep，2sc等等。所有这些协议都是对dbms中原有的事务处理层进行某些修改和扩展，使其支持实时事务的概念。当前学术界在这方面具体的研究重点有：(1) 新的事务提交处理协议及理论框架的提出；(2) 新的事务提交处理协议和原有协议的全面性能比较；(3) 新协议的实现对事务管理层的影响程度，相应的优缺点和实现难度分析；(4) 由于(2)和(3)都涉及到测试数据的采集分析，因此分布实时数据库系统的模拟测试模型的研究也是一个重点。本论文从分布式实时数据库中的事务提交协议入手，对分布式实时数据库系统中的事务提交进行研究。 commit processing in distributed real-time database systems,ramesh gupta jayant haritsa.(1996)3.2分布式实时数据库中的事务提交协议为了适合实时性要求，保证分布式实时数据库事务提交的原子性，研究者们提出了一些实时乐观提交协议，允许处于预提交状态的事务所持有的数据乐观地借出，并乐观地相信此事务最终会提交。我们把此类协议统称为乐观提交协议。在文献9中，提出了“opt”协议 gupta r,haritsa j,ramamritha ketal,commit processing in distributed real-time database systems.in:proc the 17th ieee real-time systems symposium, 1996. washington, dc, 123-133，该协议允许申请者访问处于“准备”状态的事务锁住的数据，因此事务的并发度得到了提高。但它会导致串联夭折从而最终影响系统的性能。在文献10中，提出了“shadow-opt”和“healthy-opt”协议 more optimistic about real-time distributed commit processing,in:proc the 18th ieee real-time systems symposium,california,1997，减少了串联夭折。为了对处理进行优化，减少阻塞发生的机率，有的研究者使用快照机制，即当事务要访问的数据被处于预提交状态的事务所持有时，后者拷贝生成快照，前者对快照进行读写访问，事务继续执行而无需阻塞等待 钟远明，奚建清，基于snapshot加锁机制的事务模型的研究，计算机工程，2001.4，74-78钟远明，奚建清，分布实时数据库系统中事务处理的研究，计算机应用研究，2002.2，75-78。但是它增加了快照的开销，增加了管理的复杂度。下面对国内外目前最新的分布式实时数据库事务提交协议进行分析、比较。3.2.1 prompt协议前面也提到，处于预提交