第四章 分布式事务管理和恢复(2010).ppt

1、第四章 分布式事务管理和恢复,一、概述 二、分布式事务的执行与恢复 三、两阶段提交协议 四、分布式数据库的完整性,1、事务,事务：一系列由单个用户或应用程序提交的数据库操作，这些操作是一个不可分割的整体。 例如：基金从一个帐号到另一个帐号就是一个事务，这个事务的所有操作要么都执行 即从一个帐号取出一定数目的钱，同时向另一个帐号存入相同数目的钱的操作 要么都不执行 即两个帐号上的钱数保持不变 对一个事务而言，绝对不能出现事务的一部分操作被执行，而另一部分操作没有执行的情况。,事务概念,事务是访问或更新各种数据项的程序执行单元. 事务必须保证数据库的一致性 事务执行期间数据库可能不一致,事务概念-

2、续,当事务提交（commit）时数据库必须是一致的,事务T开始,事务T结束,事务T的执行,数据库一致,数据库一致,数据库可能临时不一致,事务将数据库从一个一致性状态转变到另一个一致性状态。即事务执行前和执行后，数据库都处于一致性状态。但这种一致性在事务执行过程中将不被保证。,事务概念-续,例如，在基金转帐事务的执行过程中，当一个帐号的基金已转出，而另一个帐号的基金未转入时，数据库就处于不一致的状态，如果正好这时系统发生故障，数据库的一致性将遭到破坏。,事务概念-续,两个问题: 故障 各种软硬件故障 并发执行 多个事物同时执行,DBMS的恢复管理模块的任务：保证在故障发生后将没有提交的事务回退，

3、将数据库恢复到当前活跃事务发生前的状态，从而使数据库处于一致性状态。,事务性质,ACID特性 原子性（Atomicity）：事务内的所有对数据库的操作必须全部完成或都不完成。即一个事务所有操作是不可分割的。 一致性（Consistency）：事务使数据库从一个一致状态转变为另一个一致状态。 隔离性（Isolation）：事务的执行相互独立（互不干扰） 虽然可以有多个事务同时执行，但是单个事务的执行不应该感知其他事物的存在，因此事务执行的中间结果应该对其他并发事务隐藏 一对事务 Ti 和 Tj的执行, 看起来好像是或者 Ti 在Ti 执行结束之后才开始执行，或者Tj,是在 Ti执行结束之后才开始

4、执行 持久性（Durability）：一个已经提交的事务所产生的结果将永久地记录在数据库中。 ACID特性决定了事务的一致性和可靠性。,举例,从账号A向账号B转账 $50: 1. read(A) 2. A := A 50 3. write(A) 4. read(B) 5. B := B + 50 6. write(B),一致性要求 事务执行后A 和 B账号的总金额不变,原子性要求 如果事务在第3步和第6步之间故障, 系统应该保证事务对数据库的修改没有产生,否则将导致不一致性,持久性要求 一旦用户通知说事务已经完成（即$50 转账成功），那么由该事务对数据库的修改就必须保证是永久的，即使是发生故

5、障也如此,隔立性要求 如果在第 3步和第6步之间, 允许其他事务访问被修改的数据库的中间结果, 那么它将见到一个不一致的数据库,事务状态,活动 从事务开始执行的初始状态始， 事务执行中保持该状态 部分提交 事务的最后一个语句执行后进入该状态. 失败 一旦发现事务不能正常执行时进入该状态 夭折 当事务被回滚后，数据库恢复到事务开始执行前的状态。 事务夭折后有两种选择 重启动 仅当没有内部逻辑错误时 杀死 提交 当事务成功执行后.,事务状态-续,应用程序在数据库环境中的执行可看成是一系列原子事务活动。 事务1 事务2 事务3 t0 tn 时间 程序开始 程序结束 非数据库操作 应用程序执行 事务管

6、理模块：监视事务的执行和协调事务向数据库发出的服务请求 调度器：保证事务之间不发生冲突（确保数据库的完整性和一致性)的前提下尽可能地扩大并行度。 事务管理程序和调度器紧密相联，事务管理程序如何处理数据库服务请求依赖于数据库的调度器,事务执行方式,多用户或并发应用程序所引发的事务可按以下两种方式执行： T31 T32 程序1 T21 T22 T23 程序2 T11 T12 T13 程序3 时间 (1)头尾对接执行事务：一个时间段内只有一个事务是活跃的 T31 T32 程序1 T21 T22 T23 程序2 T11 T12 T13 程序3 时间 (2)并发执行事务：事务之间并发执行,例：转帐事务T

7、1：将￥100从帐号x转至帐号y,Begin Transaction T1 read balancex balancex= balancex-100 if balancex0 then begin print insufficient funds abort T1 end write balancex read balancey balancey= balancey+100 write balancey commit T1,操作原语： Begin Transaction 用户或应用程序显式或隐式给出事务开始的命令启动事务执行。 End 或commit 表明事务已经成功完成 Abort H或ro

8、llback 表明事务没有成功完成 事务的非正常回退可能由事务本身引发，也可能由数据库系统引发，如系统故障等,read balancex: Select balancex from ACCOUNT where account-number=x; write balancex: update ACCOUNT set balancex = balancex 100 where account-number=x;,Back,2.分布式事务,在分布式数据库环境中，一个事务可能要访问分布存储在多个站点上的数据，该事务将被划分成多个子事务，每个子事务负责对一个数据存储站点进行访问。 全局事务：一个要求访问

9、多个站点上数据库中数据的请求，但不必关心存放数据的具体地点 全局事务 分布式事务：一个全局事务在执行时将被分解为若干个与相应站点有关的操作序列组成的分布式事务即“子事务”，一个事务可看成若干个不同站点上的子事务组成。 分布事务管理：协调在各站点子事务工作以达到全局任务的原子性。子事务不仅要与相应站点上并发执行的其他本地事务相互协调，还要与分布式系统中全局事务所产生的其他子事务相互协调。因此，分布式数据库给并发控制增加了难度。,例：分布式转帐事务T1：帐号x存储在站点A，帐号y存储于站点B，全局事务T1位于站点A的子事务为T1A，位于站点B的子事务为T1B，T1是一个不可分割的全局事务， T1A

10、、T1B都是其执行站点中不可分割的事务。,Begin Transaction T1 begin Transaction T1A read balancex balancex= balancex-100 if balancex0 then begin print insufficient funds abort T1A end write balancex commit T1A,Begin Transaction T1B read balancey balancey= balancey+100 write balancey commit T1B commit T1,3.分布式事务管理器 分布式系

11、统中负责协调各子事务以保证全局事务的原子性机制。,两个概念: 进程： 进程说明：定义进程的行为模式，包括数据和对数据的一组操作 进程执行：按进程的行为模式启动进程，执行其中的那组操作。 事务代理（Agent）：在分布式数据库系统中，事务或子事务在执行中当要建立子事务时，管理器在每一有关结点上建立一个事务代理，具体负责子事务的执行。 一个事务代理是一个本地进程。,进程的协作：为协调执行分布式应用的全局操作，分布于不同站点的诸事务代理必须进行协调。为考虑事务的特性，把各站点上的诸代理组建成协作进程来完成一个全局应用。并作如下规定：,每个应用均有一个总代理或根代理，建立总代理的站点称为源站点。其工作

12、为： 负责全局事务的启动， 只有总代理才能发出全局事务的开始（begin-transaction)、提交(commit)、撤消(rollback)等原语。 只有总代理才能中止和建立其它新的事务代理； 各站点上的事务都执行成功，总代理才能决定提交该事务，否则总代理将决定撤消该事务。,分布式转帐事务T1应用处理流程,ROOT-AGENT(根代理): 事务开始： 子事务A开始：读帐号x的金额 检查是否有足够的转出资金？ 更新帐号x的存款余额 创建AGENT 向AGENT送消息：转入帐号，金额 等待来自AGENT的消息 Y 成功？ N 提交事务：成功结束 撤销事务：失败结束,AGENT(执行代理):

13、接收来自根代理的信息 更新转入帐号存款余额 发送执行消息给根代理 （成功或失败） 根代理发出begin-transaction, Commit,abort 原语，不仅在根代理的站点具有本地有效性，而且影响到该事务的全部代理,4.分布式事务管理的目标：,事务管理的任务：负责当若干个事务并发执行和事务发生错误时使数据库保持一致状态。 事务T开始 执行事务T 提交事务T,事务管理追求的理想目标： 高执行效率、高并行性、高可靠性,理想目标，往往不可兼得，密切相关，且又相矛盾 如可靠性措施会使效率下降，而且事务运行效率与下列因素有关： CPU和主存的利用率：并发执行多个应用时，CPU和主存会出现瓶颈 控

14、制报文的数目：在分布式数据库中，站点之间交换控制报文的数目是影响效率的因素之一 响应时间：分布式DB中存在站点间通信开销 可用性：发生故障时，如何增强系统的可用性,分布式事务管理的目标：,1、维护事务的原子性、一致性（可串行性）、耐久性、隔离性 2、获得最小的主存和CPU开销，降低控制报文的传输T数，加快事务的响应速度 3、获得最大限度的系统可靠性和可用性,分布式事务的管理： 分两个层次：每个站点上的局部事务管理器（LTM)，整个分布式DB由驻留在各个站点上的分布式事务管理的DTM共同协作，实现对分布事务的管理 LTM功能： 保证本地事务的特性 代替DTM把用于分布式事务执行和恢复的信息记入日

15、志,二、分布式事务的执行和恢复,1.分布式事务的管理 2.分布式事务执行的控制模型 3.分布式数据库系统中的故障 4.事务故障的恢复 5.分布式事务的执行与恢复举例,1、分布式事务的管理,分两个层次 局部事务管理（LTM）： Local Transaction Management 分布式事务管理(DTM) Distributed Transaction Management LTM的功能: 保证本地事务的特性 代替DTM把用于分布式事务执行和恢复的信息记入日志 接收并听从本站点上DTM代理发来的LOG原语，记入日志并执行之 DTM的功能： 保证分布式事务的特性,尤其是执行分布式事务的原子性，

16、使每一站点的子事务都成功执行或都不执行。通过向各站点发LOG原语来实现 支持分布式事务的执行位置透明性分布式事务管理的最基本要求 根据事务内部的逻辑划分为若干子事务，按某种要求分布到相应站点上执行，最后由源发站点提供事务的最终结果。,go,LOG原语,Local Begin-transaction, local commit, local abort,Back,2、分布式事务执行的控制模型,分布式事务执行的控制模型：是指协调分布式事务中各成员DBMS执行其子事务的通用方法。 控制模型有三种：主从控制模型 三角控制模型 层次控制模型,局部事务 管理器 LTM,分布式执行的主从控制模型,分布式事务

17、管理器 主控器 DTM 命令 命令 命令 回答 回答 回答 从属控制器,局部事务 管理器 LTM,局部事务 管理器 LTM,局部LTM 之间所需 信息不能 直 接传送,局部事务 管理器 LTM,分布式执行的三角控制模型,分布式事务管理器 DTM 命令 命令 命令 回答 回答 回答 临时数据,局部事务 管理器 LTM,控制在DTM和LTM 之间分享。局部LTM 之间可以发送和接收 数据，而不必通过 DTM作为中介,DTM,LTM,分布式执行的层次控制模型,命令 命令 回答 回答 命令 命令 命令 命令 回答 回答 回答 回答,数据库,LTM,数据库,LTM,LTM,LTM,LTM,当某个LTM接

18、受 来自另一LTM的 请求时，该LTM 自身即成为全局 事务管理器,3、分布式数据库系统中的故障,事务故障（计算溢出、完整性被破坏、操作员干预、I/O错） 站点故障 系统故障（CPU错、死循环、缓冲区满、系统崩溃） （集中式） 介质故障（DB因介质损坏无法访问等） 故障 通信故障 网络分割（断连）故障 报文错 由网络系统检测和处理 报文故障 报文失序 报文丢失 规定时间内未接到应答， 长时间延迟 分析： （1)是系统发生故障，还是性能不好（响应过慢），还是网络流量过大？ （2)如果系统发生故障，是站点故障，还是报文故障，还是网络分割？ （3)如果是报文故障，是报文丢失还是应答丢失？,4.事务故

19、障的恢复机制,事务本身的故障和系统故障是造成数据库完整性和一致性破坏的主要原因。在故障恢复后保证数据库状态的一致性是任何一个数据库管理系统都应具备的基本能力。当发生一次使数据库状态不一致或可能使数据库状态不一致的失败后，恢复管理机制负责将数据库恢复到一个一致的状态。,事务与恢复,事务是恢复处理的基本单元。 恢复管理机制负责保证事务的永久性和原子性；当系统从失败中恢复以后，恢复管理机制必须保证：一个事务的所有执行结果要么全部都永久记录在数据库中，要么全部都不作永久记录。 并发控制机制负责保证事务的一致性和隔离性；,数据库的写操作不是一个原子过程，可能一事务已提交，但执行结果还未到达数据库。 （临

20、时数据） （永久数据 ） 当一个故障发生在写数据入缓冲区或从缓冲区回写入二级存储器时，恢复机制必须确认引起这次写操作的事务此时所处的状态： 如果一事务已提交后发生故障，为保证事务的一致性，恢复管理机制对事务执行一次REDO操作（重做），使事务的执行结果真正写入数据库中。 如果事务处于活跃状态，为保证事务的原子性，恢复管理机制对事务执行一次UNDO操作（修改复原），消除该事务对数据库的影响。 恢复机制的基本功能就是在发生故障时，识别哪些事务需要REDO操作，而哪些事务需要UNDO操作，然后去执行这些必需的操作。,数据,数据库缓冲区,二级存储器。,事务恢复的原则：,二级存储器。,二级存储器。,4.

21、事务故障的恢复主要依靠日志文件来实现,（1）.恢复机制 日志文件：记录所有事务引发的所有数据库的操作。由日志记录组成，按时间先后排成线性顺序。 操作: 事务开始（ BEGIN Transaction） 写（ Insert, Delete, Update ） 提交事务（ Commit） 终止事务（Rollback 或Abort） 日志记录（记录名，旧记录值（前象），新记录值（后象），事务标识符， 操作类型，LOG记录长度，辅助信息） 每个操作记录一个对应的日志记录 属于同一事务的日志记录，彼此接链 每个数据库管理系统都拥有一个日志文件，在分布式数据库环境中，不同结点拥有各自的日志文件。,（2）档

22、案库,在事务处理率很高的系统中，每天都会产生大量的日志信息，将所有信息都随时随刻联机存储是不现实的，事实上也是完全不必要的。故将日志分成两部分： 当前活动的联机存储器，存放在直接存取设备（磁盘）上 称为直接存取数据集，或数据集（Date Set)。 小失败，立即恢复其相关日志记录，高效 档案存储器，存放在二级存储设备上（如磁带） 每当数据集满时就转存到档案存储设备中 存放日志的档案存储设备称为日志档案库（Log Archive),将联机存储的日志部分分为两个独立的直接访问文件 开始时，日志记录写入第1个文件，当文件达到一定的负荷度时（如95），日志系统打开第2个文件。之后原记录在第1个文件中的

23、事务继续写入第1个文件，而新出现的事务日志记录写入第2个文件。 当第1个文件相应的所有事务都提交完毕时，系统将第1个文件送到日志档案库上。此时，将第2个文件视为新的第1个文件，而刚腾出的第1个文件就成为新的第2个文件 这种方法避免了同一事务的日志记录交叉存储在联机存储器和档案存储器上，使事务的恢复简单。,组织日志存档的一般方法：,数据库、日志和档案库的存储模式,局部事务管理器 （LTM）,本地调度,本地恢复管理器,数据库缓存管理器,数据库缓存,日志缓存,数据库,日志文件,主存,二级存储,DB 档案库,日志 档案库,日志优先协议（或先写日志协议）,对数据库的修改和写日志文件是分别进行的。因而在它

24、们之间也可能发生故障。如果数据库修改后发生故障而不能写日志，则这些修改就不能恢复。所以要先写日志。即使发生故障，等系统恢复后仍可根据日志记录修改数据库，这称为日志优先协议，包括两点内容： 1. 修改数据库时恢复过程必须的信息已在日志中; 2. 事务提交时有关该事务的日志记录已完备。 日志优先协议：日志记录写入日志文件的操作先于其对应的数据库写操作。,（3）检查点Checkpoint,恢复管理机制面临的问题： 在失败后，在日志中要回溯多远以识别哪些事务必须Redo，哪些必须Undo。即判断那些事务在失败前已完成，哪些事务还没有完成 设置检查点： 为减少这个回溯的长度，恢复管理机制周期性设置检查点

25、，因此回溯时只需回溯到上一个检查点。 设置检查点的方式： 同步检查：在检查点的设置系统停止接受新事务直至所有现行执行事务完成； 异步检查：检查点的设置不中断系统进程。,异步检查：检查点的设置不中断系统进程。,TC1,TC2,TC3,TC5,tc 异步检查点,tf 失败,TC5:同TC3处理。 TC4:同TC2处理。 TC3:失败时仍然活跃，UNDO利用日志记录前象。 TC2:可能要Redo，Redo操作使用日志中记录的后象恢复DB。 TC1:永久记录在DB中。,在异步检查点上，系统执行操作： （1）将当前所有活动事务写入日志 （2）将检查点在日志中的地址写入 “重启动文件” （3）所有日志缓冲

26、区和数据库缓冲区 内容都被强制性写入永久存储器,同步检查：检查点的设置处系统停止接受新事务直到所有执行事 务完成 在同步检查点上，系统执行操作：,tc 同步检查点,ff 失败,TC1,TC4,（2）将检查点在日志中的地址写入 “重启动文件” （3）所有日志缓冲区和数据库缓冲区 内容都被强制性写入永久存储器 （1）不必要； 没有任何活跃事务 恢复机制的工作大大减化 但需付出的代价：许多新事务被 延迟启动，直到设置检查点的 工作结束。,TC5,同步检查方式下不会有事务要被REDO和UNDO,与异步检查方式下的处理相同： TC1:永久记录在DB中。 TC4:可能要Redo，Redo操作使用日志中记录

27、的后象恢复DB。 TC5:失败时仍然活跃，UNDO利用日志记录前象。,数据库的更新问题,数据库系统在更新数据时采用的方式： (1）现场写或直接写：在进行数据库操作时，直接将数据从数据库缓冲区中写入数据库。（大多数数据库系统采用这种方式） 优点：当事务提交时，事务对数据库的修改已经到位，无需其他的操作。然而当事务失败时，可能要进行Undo操作。为解决这个问题，许多系统采用了下面的方式。 （2) 影像写或差额文件：事务对数据库的修改结果将被写在基于二级存储器的数据库的一个独立部分（差额文件），而数据库的索引指针并不指向这些数据。当事务提交后，才修改索引指针使之指向这些新数据。旧版本的数据可供恢复管

28、理机制使用，成为日志文件的一部分。 在差额文件方式中，主数据库被视为只读，根本不接受修改。事务对数据库的修改结果被记录在差额文件上。当差额文件的尺寸大到对整体性能带来明显的影响时，其数据就与只读的主数据库合并为一个新的只读主数据库，差额文件恢复为空。,在分布式数据库管理系统中，要兼顾本地事务和全局事务的原子性和一致性，当故障排除后，由局部事务管理器的恢复子系统执行事务恢复。因此，讨论： .集中式恢复协议 四种基本协议： .分布式恢复协议 二阶段提交（2PC:Two-Plase Commitment Protocol) 三阶段提交（3PC),恢复协议,四种基本协议： 4种算法的不同在于失败后是否

29、要求进行Redo、Undo操作 是否采用Redo、 Undo操作，取决于将数据库缓冲区回写入永久性存储器的时机： Undo操作：若在事务执行过程中同步写，则必须进行Undo操作； 若是异步写，则Undo操作就不必了； Redo操作：取决于缓冲区的数据是否在事务提交时同步回写 若是同步回写，无需Redo； 若是异步写， Redo则必要。, .集中式恢复协议,四种基本协议： 这四种算法描述了恢复管理器在事务的不同操作过程中相应的处理动作，事务的操作有： （1) 事务开始（ BEGIN Transaction） （2) 读 （Select) （3) 写（ Insert, Delete, Update

30、 ） （4) 提交事务（ Commit） （5) 终止事务（Rollback 或Abort） 还有一个由恢复带来的附加操作：重启动, .集中式恢复协议,Undo/Redo协议,基于Undo/Redo协议的恢复管理机制是最复杂的，因为在失败后，既要考虑Redo,又要考虑Undo。 优点：允许缓冲区管理器自行确定回写时机，从而减少I/O开销。该算法的整体效果就是以在恢复时的大量集中式的I/O开销为代价，来换取平常状态（没有故障和终止）下的最大性能。,Undo/Redo协议,恢复管理机制在事务各操作阶段的动作： （1) 事务开始（ BEGIN Transaction）：触发数据库管理系统的一些管理功

31、能，如将信事务加入现行活跃事务队列，在日志上开设一个新表项。 （2) 读（Select)：若读操作所需要的数据体在数据库缓冲区中，则将其读出；否则先将数据从数据库读入缓冲区；若只从恢复的角度来看，读操作无需在日志中记录，但可能有其他的原因要求在日志中记录。 （3) 写（ Insert, Delete, Update ）：其结果是修改数据库缓冲区上的数据对象，该数据对象可能已在数据库缓冲区中，也可能临时从数据库中取出。将该数据对象的前像和后像都写入日志中。 （4) 提交事务（ Commit）：在日志中登记一个事务提交记录。 （5) 终止事务（Rollback 或Abort）：Undo这个事务。若

32、采用现场写技术，恢复机制将修改后的数据从数据库中嗲欧数据库缓冲区，并根据日志中记录的前像进行恢复。 （6) 重启动：恢复机制回溯日志Redo所有登记在案的已提交事务，Undo那些只有事务开始记录没有事务提交记录的事务。回溯到上一个检查点。,为使恢复机制能简单判断哪些事务应Undo，哪些事务应Redo，由恢复管理器保存： 一个活跃队列：每个事务开始执行时被加入活跃队列； 一个终止队列：被终止的事务记录在终止队列中； 一个提交队列：记录所有已提交的事务。 这些队列必须保存在永久性存储器上，视为日志的一部分。,（3） （1）从“重启动文件”中读出最近的Checkpoint Record的地址，找到C

33、heckpoint Record在 Log Data Set中的地址 （2）创建REDO表，初态为空，创建UNDO表，将Checkpoint Record中的活动事务表内容复制到UNDO表。 （3）从Checkpoint Record起沿Log向前搜索。 遇begin transaction的Log记录，将对应的事务记入UNDO表。 遇Commit的Log记录，将对应的事务从UNDO表中移入REDO表，直到Log结束。 （4）反向检索Log，做UNDO。 （5）正向检索REDO表中的事务的Log记录，并执行之，直到Commit。,UNDO表,REDO表,Restart File,Log Dat

34、a Set,tc1,故障发生,（5）,活动事务表,（4）,（1）,Checkpoint Record,tf,Begin STEP1：定位最新的检查点记录 read address of last checkpoint record from RESTART file read checkpoint record undo-list=list of transaction from checkpoint record redo-list=empty STEP2：分类 do while not end-of-log read next entry from log into log-record

35、if log-record type=begin transaction or abort transaction then add transaction identifier for log record into undo-list else if log-record type=commit transaction then move transaction identifier for log record from undo-list to redo-list end-if end-if end-do STEP3：恢复 do while not end-of-undo-list (

36、working backwards （回搠，反向检索）) undo transaction end-do do while not end-of-redo-list (working forwards) redo transaction end-do End.,算法1：Undo/Redo协议的重启动过程,在Undo/No_Redo算法下，数据库缓冲区内容在事务提交时同步写入永久性存储器，因此在重启动时无需任何Redo，也无需在日志中保存后像。恢复管理机制只关心失败时仍然活跃的事务，这些事务需要Undo。 具体操作： (1)在事务开始、读、写和事务终止的动作前面UNDO/REDO协议相同。 （2

37、)提交:将所有数据库缓冲区内容在事务提交时回写，同时在日志中记录一个提交记录。若采用提交队列的话，只需简单地将事务标识加入提交队列即可。 （3)重启动：恢复机制必须执行一次全局Undo。,Undo/No_Redo协议,Begin STEP1：定位最新的检查点记录 read address of last checkpoint record from RESTART file read checkpoint record undo-list=list of transaction from checkpoint record STEP2：分类 do while not end-of-log re

38、ad next entry from log into log-record if log-record type=begin transaction or abort transaction then add transaction identifier for log record into undo-list else if log-record type=commit transaction then move transaction identifier for log record from undo-list end-if end-if end-do STEP3：恢复 do wh

39、ile not end-of-undo-list (working backwards （回搠，反向检索）) undo transaction end-do End.,算法2：Undo/No-Redo协议的重启动过程,No-undo/Redo,在这个算法中，事务提交前的修改并不直接写入永久性存储器，缓冲区管理器将被修改数据对象保留在主存的数据库缓冲区中，直到事务提交时才有可能将其修改写入到永久存储器中。 另一种方法是不将修改写入数据库缓冲区，而是直接写入日志。 此时恢复管理器只需处理TC2和TC4这类已提交的事务，发生故障时需Redo，因在提交时其数据没有被写入永久性存储器中。此方法无需Und

40、o，因为没有提交的事务是不会将其修改写入永久性存储器中。,Begin STEP1：定位最新的检查点记录 read address of last checkpoint record from RESTART file read checkpoint record redo-list=empty STEP2：分类 do until checkpoint record in log is reached(working backwards) read next entry from log into log-record if log-record type= commit transaction

41、 then add transaction identifier for log record from redo-list end-if end-do STEP3：恢复 do while not end-of-redo-list (working forwards) redo transaction end-do End.,算法3：No-Undo/Redo协议的重启动过程,No-undo/No-Redo,为了避免Undo事务，恢复管理机制必须保证在提交前，事务的数据修改不得进入永久性存储器； 而为了避免Redo事务，又必须保证在提交前，事务的数据修改先行进入永久性存储器； 解决办法：提交前用

42、一个原子操作实现对数据库的写 采用影像写技术，将修改结果从缓冲区直接写入永久性存储器。避免Undo事务，恢复管理机制必须保证在提交前，事务的数据修改不得进入永久性存储器；,分布事务处理协议 事务T:用户的一个SQL程序形成的事务T，存取分布于N1,N2,N3等站点上的关系数据,从系统内部来看，根代理N1发起一个分布事务，N2.N3等参与代理所管理的基本单位是该分布事务的子事务； 在用户看来，该分布事务在运行后只会有ALL或Nothing两者之一的结果。 在系统内部，该分布事务的运行过程要经历分析SQL程序并生成控制信息、分布各子事务、开始执行。中间处理（包括数据传输等）、结束准备和结束等阶段，

43、围绕这一过程需要有一个基本的处理协议，参与处理的各站点可按照协议一步步正确向前执行，直到该事务结束。 从事务管理的角度，如数据处理这样的中间过程，对维护事务的原子性基本没有影响，主要在对事务的开始与结束的处理上,分布事务处理协议 具体来说事务管理主要在实现事务的开始（Begin Transaction)、提交(Commit)、取消(Abort)等三个关键操作上。抽象地说是通过协议实现三条事务的操作原语： Begin_Transaction Abort_Transaction Commit_Transaction 分布事务管理是在分布环境下实现这三条原语： Begin_Transaction比较

44、容易实现，而后两个原语则存在一致性和可靠性等两个方面的问题： 一致性方面：各结点平等、自治，各个站点上的局部处理可能会有Commit或Abort两种不同的结果。但分布事务的全局结果只有一个，要么Commit，要么Abort，这需要经过协议协调来保证所作决定的唯一性。 可靠性方面：根据事务的原子性，事务的Commit或Abort操作的执行是无条件的。 Abort处理比较容易。要Abort一个分布式事务，只要有参与者结点Abort其有关子事务即可。无论中间出现什么问题，只需要恢复后放弃正在执行的子事务。而对Commit来说要困难一些，要求无论发生什么情况，每个参与者结点都必须保证实现Commit的

45、结果。 分布事务处理协议主要在于实现Abort和Commit等两个操作，而且其中的重点又是Commit. 大多数有关的协议都被称为Commit协议。,分布事务处理协议 -分布系统的恢复变化比较复杂：即要考虑全局事务本身的原子性，又要保证局部事务的原子性。则需考虑： 全局事务不能在其所有子事务成功提交或终止之前提交或终止。 站点失败和数据通信失败, 保证一个站点的失败不能影响其他站点的进程 -由于分布特性，分布事务的整个执行过程只能以协议的方式来完成 分布式数据库环境下的提交协议： （1）二阶段提交（2PC:Two-Plase Commitment Protocol) （2）三阶段提交（3PC)

46、,1.两阶段提交协议（Two-Phase Commitment Protocal) 把本地原子性提交行为的效果扩展到分布式事务，保证了分布式事务提交的原子行，并在系统运行日志无丢失的情况下，实现快速故障恢复，提高分布式数据库系统的可靠性。2PC协议对任何系统故障均有一定的恢复功能 在2PC协议中， 协调者（Coordinator)：分布式事务的根代 理，负责分布事务的提交或中止。 参与者（Participants)：所有其他代理，负责某局部场地的写操作，并向协议者进程提出提交或中止的建议。,协调者,参与者,参与者,日志,日志,日志,命令,应答,基本思想：由协调者质问所有的参与者是否准备好提交事

47、务。如果有一个参与者投了“终止”票或在规定时间内未对协调者作出响应，则协调者将命令所有的参与者终止事务。如果所有的参与者投了“提交”票，则协调者决策所有的参与者提交事务。 2PC的目的：要得到并最终实现一个关于分布事务结束的唯一且一致的决定。 在无故障情况下2PC协议的工作过程为: (1) 协调者送“投票”消息到所有参与者， (2) 当参与者收到投票消息后用”Commit”或”Abort”回答协调者， (3) 若协调者收到的所有参与者的回答是”Commit”且协调者自己也是”Commit” ，则向所有参与者发提交命令;否则发撤回命令， (4)参与者收到c的最后决定后执行。 其中1,2是投票阶段

48、，3,4为决定阶段。从2开始到4是回答Yes的参与者的不确定区间。,2PC分为两个阶段：投票表决阶段和决策执行阶段,投票的有关规则： （1）每个参与者有一次投票机会，可投“Commit”或“Abort” （2）投票一旦进行，参与者不得悔改。 （3）单方面终止：如果一个参与者投“Abort”票，则之后它可立即终止自己的事务。 （4）若一个参与者投“Commit”票，则之后必须等待协调者广播通知：“全局性提交”或“全局性终止”。 （5）若所有参与者都投了“Commit”票，则协调者必须作出“全局性提交”的决策。 （6）所有的参与者必须服从协调者的全局性决策。 2PC存在一个站点等待其他站点信息的可

49、能，协调者和参与者可能进入某些相互等待对方发送消息的状态为避免不必要的阻塞，采用超时检测技术。另一方面是为处理可能的网络延迟或计数设备的长等待队列问题，也要引入超时检测技术。,2PC协调者算法 Begin step C1 发出投票命令 writebegin gllobal commit message to log Send vote message to all participants Do until votes received from all participants wait on timeout go to Step c2b End-do step C2a 全局提交 If al

50、l votes are commit then begin write global commit record to log send global committo all participants end step C2b 全局取消 If at least one participant has voted abot or coordinator has timed out then begin write global abort record to log send global abortto all participants end step C3 终止 Do until ack

51、nowledgement received from all participants wait End-do write end global trasaction record to log finish end,2PC参与者算法 Begin step P0 等待投票命令 Do until vote instruction received from coordinator wait End-do step P1 投票 If votes = commit then send committo coordinator Else send abortgo to step P2b Do unti

52、l global vote received from coordinator wait End-do step P2a 提交 If global vote=commit then perform local commit processing step P2b 取消 at least one participant has voted abot else perform local abort processing end if send acknowledgement to coordinator finish end,协调者,参与者,阶 段 一,在Log中记录begin_commit,

53、向所有参与者发PREPARE消息； 启动Timeout; 收集参与者的应答READY 或ABORT消息； 计算Timeout，若超时 在Log中记录Global-Abort, 向所有参与者发ABORT消息；,等待协调者PREPARE消息； 如果本事务Commit 在Log中记录事务有关信息， 在Log中记录Ready, 向协调者发READY消息; 如果本事务Abort 在Log中记录Abort， 向协调者发ABORT消息;,协调者,参与者,阶 段 二,如果所有参与者均回答COMMIT, 在Log中记录Global-Commit; 向所有参与者发COMMIT命令； 否则在Log中记录Global

54、-Abort, 向所有参与者发ABORT命令； 等待所有参与者的Ack消息； 接收完毕， 在Log中记录end-of-trans,结束,等待协调者命令； 收到协调者命令， 在Log中记录命令； 向协调者发Ack消息;,2. 分布事务处理协议的描述工具,状态图是为了便于对分布事务处理协议进行分析而引入的一种工具。用它较清楚的描述了协议整个发展过程的各个状态。 点：表示协议行进中到达的某一状态。 边：表示状体间的变化,一个状态到另一个状态的条件：发生三个相关事件， 即收到某些特定消息（此消息可为空） 完成了必要信息的操作 发出指定的消息,参与者结点,点：表示协议行进中到 达的某一状态。 边：表示状

55、体间的变化,2.分布事务处理协议的描述工具-状态图,状态:I Initiate W 等待 R Ready A Abort C Commit,消息：PM Prepare RM Ready AA Abort Answer AC Abort Command CM Commit Command,事件：单方面Abort Timeout,3、2PC协议的通信结构,（1）集中式2PC通信结构 协调者 参与者 协调者 参与者 协调者 准备 建议撤消/提交 全局撤消/提交 提交/撤消 第一阶段 第二阶段,通信只发生在协调者和参与者之间，参与者之间不交换消息,这是集中式两阶段提交协议，类似于星型结构：,所有的通信都要 经过协调者。 通信是用直接广 播方法,为了提高集中式2PC协议的性能，提出许多改进方案，如减少信息交互量、提高决策制定过程的速度等。 这些改进依赖于引入不同的信息交换方式或通信拓扑结构,（2）分层式2PC通信结构,协调者 参与者 协调者 参与者 协调者 准备 建议撤消/提交 全局撤消/提交 提交/撤消 第一阶段 第二阶段,1,2,3,4,5,1,2,3,4,5,1,2,2,类似于树型结构，协调者是树根的DTM-代理者。在协调者和参与者之间的通信不用直接广播的方法进行而是使报文在树中上下传播，每个DTM代理者是通信树的一个内部结点。从下层结点处收集报文或向它