《事务管理》PPT课件 (2).ppt

第7章 事务管理,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,第7章 事务管理,恢复保证事务在并发执行时满足ACID准则的技术。 并发控制保证事务在并发执行时满足ACID准则的技术。,事务管理（transaction management）：,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,7.1 恢复引论,故障的可能性总是存在的。解决故障的措施有二：一是尽可能提高可靠性；二是恢复。,这里主要讨论发生故障后，恢复数据库至一致状态的技术，即恢复技术。,系统发生故障时，可能会导致数据的丢失(loss)，要恢复丢失的数据，必须有后备副本。,对于恢复，数据冗余是必需的！,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,1.单纯以后备副本为基础的恢复技术 2.以后备副本和运行记录为基础的恢复 3.基于多副本的恢复技术,恢复技术大致可以分为下列三种,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,1.单纯以后备副本为基础的恢复技术,从文件系统继承而来，周期性的把磁盘上的数据库转储（dump）到脱机存放的磁带上。,失效,取后备副本,取后备副本,取后备副本,更新丢失,更新丢失,增量转储（ID）,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,单纯以后备副本为基础的恢复技术： 优点：实现简单，不增加数据库正常运行时的开销。 缺点：不能恢复到数据库的最近一致的状态。,多用于文件系统以及小型的不重要的数据 库系统。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,2.以后备副本和运行记录为基础的恢复,运行记录（log或journal）由系统维护，一般包括下列内容：,（1）前像（Before Image,BI） 当数据库被一个事务更新时，所涉及的物理块更新前的映像（image）称为该事务的前像（BI），前像以物理块为单位；有了前像可以使数据库恢复到更新前状态，对应操作undo(撤销)。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,（2）后像(After Image,AI) 当数据库被一个事务更新时，所涉及的物理块更新后的映像（image）称为该事务的后像（AI），后像也以物理块为单位；有了后像，即便更新的数据丢失了，仍然可以使数据库恢复到更新后的状态，相当于重做一次更新，对应操作redo(重做) 。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,问题：前像(BI)、后像(AI)和事务操作的关系？,修改有前像 有后像 插入没前像 有后像 删除有前像 没后像,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,（3）事务状态,记录每个事务的状态，以便在恢复时作不同的处理（COMMIT和NOT COMMIT）。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,提交(Commit)成功执行(do all)。 回卷(Rollback或Abort)消除事务对数据库的影响(do nothing)。,对恢复而言，至少要区分一个事务是否提交！,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,实现方法,最近后备副本,运 行 记 录,基于后备副本与运行记录的恢复如上图所示，当数据库失效时，取出最近后备副本，然后根据运行记录，对未提交的事务用前像卷回向后恢复(backward recovery)；对已提交的事务，必要时用后像重做向前恢复(forward recovery)。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,这种恢复技术，需保持运行记录，这将会影响数据库的正常工作速度，但可以使数据库恢复到最近一致状态。大多数商品化DBMS采用这种恢复技术。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,3.基于多副本的恢复技术,如果系统中有多个DB副本，且这些副本具有独立的失效模式(independent failure mode)，则可利用这些副本互为备份，用于恢复。,此技术在分布式数据库系统中应用的较多。,近年来，由于硬件价格的下降，也采用镜像磁盘(mirrored disks)技术。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,写数据时，两个磁盘都写入同样的内容。 当一个磁盘的数据丢失时，可以用另一个磁盘的数据来恢复。（两盘同时故障的概率可以假设为零！）,下面主要讨论第二种恢 复技术。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,7.2 运行记录的结构,运行记录的存储要避免与数据库“全军覆没”。,运行记录(log)一般不能和数据库放在同一磁盘上，以免两者皆失。（假设log和DBMS同时失效的概率为零；一般假设log不会损坏，若运行中DBMS测得log损坏，则采取强制措施，例如拒绝新事务，完成已提交事务，停止运行，修复log）。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,运行记录的结构因DBMS而异 Log基本内容,1.活动事务表（active transaction list-ATL）,记录所有正在执行，尚未提交的事务的标识符 (transaction identifier-TID)。,2.提交事务表（committed transaction list-CTL）,记录所有已提交事务的标识符。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,3.前像文件,可以看成一个堆文件。每个物理块有个块标识符BID（block identifier）。BID由TID、关系名和逻辑块号组成。逻辑块号在关系中是唯一的。如果一个事务需要卷回，可以在前像文件中找出该事务的所有前像块，按照逻辑块号写入到关系的对应块，从而消除该事务对数据库的影响。,undo满足幂等性: undo(undo(undoundo(x)=undo(x),因此，undo失败可以再undo!,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,4.后像文件,结构与前像文件相仿，不过记的是后像。在恢复时，可按提交事务表中的事务次序，按逻辑块号，写入其后像。这相当于按提交的次序重做各个事务。,redo满足幂等性: redo(redo(redoredo(x)=redo(x),制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,取后备复本后，之前的运行记录就失去了价值，对恢复来说，只要保留最近后备复本以后的运行记录。但运行记录仍可能很大。可采用下列措施减小运行记录规模。,1.不保留已提交事务的前像 2.有选择性的保留后像 3.合并后像（对给定逻辑块号的物理块，如多次更新，可只保留最近的后像）,如何判断该做undo还是redo呢？下一节，将解决这 个问题。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,7.3 更新事务的执行与恢复,1 提交规则（Commit Rule） 后像必须在事务提交前，写入非易失性存储器（DB 或log）。,更新事务执行时，应遵守下两条规则：,2 先记后写规则（Log Ahead Rule） 如果后像在事务提交前写入数据库，则必须把前像先写入log。,在执行一个更新事务时，按后像写入DB的时间，有三种可能的方案。,即后像不能仅留在内存中！,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,三种更新策略,a) 后像在事务提交前完全写入DB TID active list B.I Log (按Log Ahead Rule) A.I DB TID commit list delete TID from active list,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,在这种情况下，如果出现故障，如何恢复？,Restart时，对每个TID，查两个list：,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,b) 后像在事务提交后写入数据库 TID active list A.I Log (按commit rule) TID commit list A.I DB delete TID from active list,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,在这种情况下，如果出现故障，如何恢复,Restart时，对每个TID，查两个list：,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,c) 后像在事务提交前后写入数据库 TID active list A.I, B.I Log (按2 rules) A.I DB (partially done) TID commit list A.I DB (completed) delete TID from active list,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,在这种情况下，如果出现故障，如何恢复？,Restart时，对每个TID，查两个list：,思考：方案3均匀的将写入DB的I/O操作分散在事务提交前后，有什么优点？,有利于磁盘均衡负载,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,7.5 消息的处理,一个事务常常要给用户发送有影响的消息(message)，不是指需要用户输入的指示消息。,例如：“付款2000元”以及“立即执行下一步处理”等。,发送消息也是事务执行结果的一部分，应该遵循“要么不做，要么全做”的原则。但是，消息往往难以用“undo”操作来消除其影响。,因此，在事务结束前，消息不能发出，只有等事务结束后才能发出。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,消息发送委托消息管理（message manager-MM）子系统执行。,事务执行时，将需要发送的消息转给MM,MM为每个事务建立一个消息队列。,MM,Ti,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,当事务正常结束时（包括提交和回卷），事务通知MM发送消息；当事务因故障被撤销时，MM将把该事务的消息丢弃。,为了保证消息能可靠的发送给有关用户，MM采用“发送-确认”方式传递。,MM对事务委托发送的消息，在事务正常结束前，允许事务增加和删除；一旦事务结束，MM就把消息存于不易失存储器中。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,7.6 失效的类型及恢复的对策,一种恢复方法通常只对某些类型的失效有用。,通常的失效可以分为以下三类：,1.事务失效(transaction failure) 事务应不可预知的原因而夭折。 例如：数据库中没有要访问的数据、输入数据类型不对、除数为零等。,事务失效时DB未被破坏，系统控制在手。且事务失效 一定发生在事务提交前。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,恢复措施： MM丢弃该事务的消息队列； 如果需要，进行undo操作； 从ATL删除该事务的TID，释放该事务所占资源。,2.系统失效(system failure) 系统(包括OS和DBMS)崩溃，需要重新启动(restart)，DB未被破坏，但系统失去控制。 例如：掉电、除数据库存储介质以外的软、硬件故障等。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,恢复措施： 重新启动OS和DBMS； 恢复DB致一致状态（对未提交的事务进行undo操作 对已提交的事务进行redo操作）。,只有当数据库恢复到一致状态后，才允许用户访问数据库。,系统中，活动事务表(ATL)的长度是有限的；由于累积效应，提交事务表（CTL）可能很长。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,为了减少恢复时大量redo操作的工作量，在运行过程中，DBMS每隔一定时间在运行记录中设置一个检查点(checkpointCP)，在检查点，DBMS强制写入所有已提交事务的后像。,显然，在最近检查点以前提交的 事务，恢复时，不用redo。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,取CP过程一般如下：,暂停事务的执行； 写入上一个CP以后所提交事务的后像； 在log的CTL中记下检查点； 恢复事务的执行。,取CP很影响系统的正常运行，而只有在发生系统失 效时，才有其减少redo工作量的效益。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,3.介质失效(media failure) 磁盘发生故障，DB被破坏。,修复系统，必要时更新磁盘； 如果系统（OS和DBMS）崩溃，重新启动系统； 加载最近后备副本； 用log中的后像重做取最近后备副本后提交的所有事务。,恢复措施：,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,7.7 并发控制,7.7.1 数据库系统中的并发,1.串行访问(serial access)事务顺序执行。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,2.并发访问(concurrent access)DBMS可同时接纳多个事务，事务可在时间上重叠执行。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,交叉并发（interleaved concurrency）单CPU系 统，各个事务交叉使用CPU。,同时并发（simultaneous concurrency）多CPU 系统，多个事务在CPU中同时运行。,7.7.2 并发的目的,1.提高系统资源利用率；,2.改善短事务响应时间。,例如，两个事务T1和T2， T1长，先交付； T2短，稍后交付，如果串行执行，则T2必须等T1，响应时间很长。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,7.7.3 并发引起的问题,事务若不加控制的并发执行，会产生什么问题？,1.丢失更新（lost update）,T1 Read(x) x:=x+1 Write(x),T2 Read(x) x:=2*x Write(x),Read(x),Read(x),x:=x+1,Write(x),x:=2*x,Write(x),制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,2.读脏数据（dirty read）,T1 write(t) rollback,T2 read(tx) read(ty),read(tx),write(t),read(ty),rollback,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,3. 读值不可复现（unrepeatable read),T1 read(x) read(x),T2 Write(x),Read(x),Write(x),Read(x),制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,事务并发执行时可能会有两种冲突： 写写、读写； 写写冲突在任何情况下都应避免，读写冲突一般情况下应避免，但某些应用场合可以容忍。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,7.7.4 并发控制的正确性准则,思考：多个事务并发执行，结果怎么估计？,假设数据库系统中，某一时刻并发执行的事务集为T1,T2,Tn，调度(Schedule)S是对n个事务所有操作的顺序的一个安排。,在S中，不同事物的操作可以交叉，但必须保持各个事务的操作的原有次序。（注意：操作是调度的基本单位！）,设Write简写为W，Read为R，R和W用其所属事务号为下标，上图的调度可表示为： S=R1(x)W2(x)R1(x),制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,对同一事务集,可能有很多种调度。 如果其中两个调度S1和S2，在数据库的任何初始状态下，所有读出的数据都一样，留给数据库的最终状态也一样，则称S1和S2是等价的，又称为目标等价(view equivalence)。,偏重语义，难以判断！,还有一种更实用的等价定义，称为冲突等价(conflict equivalence)。,容易实现！,冲突操作有读-写冲突和写-写冲突两种，可表示为： Ri(x)和Wj(x) Wi(x)和Wj(x) (ij),制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,冲突操作的执行次序会影响执行结果，不冲突操作的次序可以互换，不致影响执行结果。,凡是通过调换S中不冲突操作得到的新的调度，称为S的冲突等价调度。,如果两个调度是冲突等价的，一定是目标等价的；反之未必！,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,若调度S在数据库中产生的效果，与这组事务的某个串行执行序列的结果相同，则称这个调度S是可串行化的（serializable）。,例如，对事务集T1,T2,T3的一个调度： S = R2(x) W3(x) R1(y) W2(y),S是串行调度，故S是冲突可串行化的，也是目标可串 行化的！,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,冲突可串行化的调度一定是目标可串行化的吗？,目标可串行化的调度一定是冲突可串行化的吗？,目标可串行化的调度未必是冲突可串行化！,例如，调度S=R1(x)W2(x)W1(x)W3(x) 无冲突等价调度，但却可以找到一个调度S： S=R1(x)W1(x)W2(x)W3(x)与S目标等价。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,目标可串行化,冲突可串行化,多个事务串行执行后，DB仍保持一致状态。可串行化调度与事务的某个串行执行等价。当然也保持数据库的一致状态，因此，在一般的DBMS中，都是以可串行化作为并发控制的正确性准则！,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,可串行化并发控制的正确性准则,问题：不同的调度不同的等价串行序列不同的执行结果？(n!),制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,关于目标等价与冲突等价,调度：是系统对n个并发事务的所有操作的顺序的一个安排。 目标等价：两个调度s1和s2，如果在同样的初始条件下执行，对数据库产生的效果完全相同，则称s1和s2是目标等价的。 冲突操作：R-W、W-W。冲突操作的执行顺序会影响执行效果。 不冲突操作：R-R 虽有写操作，但作用对象不同，如Ri(x)和Wj(y)。 冲突等价：凡是通过调换s中的不冲突操作所得的新调度，称为s的冲突等价调度。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,性质：如两调度是冲突等价的，则一定是目标等价的；反之未必正确。 串行化也分为目标可串行化和冲突可串行化。 例1：对事务集T1,T2,T3的一个调度s s=R2(x)W3(x)R1(y)W2(y)R1(y)R2(x)W2(y)W3(x)=s 因为s是串行调度，所以s是冲突可串行化的。 例2：s=R1(x)W2(x)W1(x)W3(x) 无冲突等价调度，但却可以找到一个调度s s=R1(x)W1(x)W2(x)W3(x) 与s目标等价。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,目标可串行化的测试算法是NP难度的，冲突可串行化覆盖了绝大部分可串行化的调度实例，所以今后如无特别说明，可串行化均指冲突可串行化。,前趋图 有向图G= V顶点的集合，包含所有参与调度的事务。 E边的集合，通过分析冲突操作来决定。如果下列条件之一成立，可在E中加边TiTj： Ri(x)在Wj(x)之前 Wi(x)在Rj(x)之前 Wi(x)在Wj(x)之前 最后，看构造好的前趋图中是否有环路，如果有，则该调度不可串行化；否则，可串行化。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,可串行化时，决定等价串行调度序列的算法：,由于无环路，必有入度为0的顶点。将它们及其有关的边从图中移去并将这些顶点存入一个队列。 对剩下的图作同样处理，不过移出的顶点要队列中已有顶点之后。 重复1，2直至所有顶点移入队列为止。 例对T1,T2,T3,T4的一个调度s S= W3(y)R1(x)R2(y)W3(x)W2(x)W3(z)R4(z)W4(x) 它是否可串行化？如可串行化找出其等价的串行执行序列。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,S= W3(y)R1(x)R2(y)W3(x)W2(x)W3(z)R4(z)W4(x),并发控制的任务就是对并发执行的事务加以控制，使之按某种可串行化的调度序列来执行。,T1,T2,T3,T4,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,7.8 加锁协议Lock Protocol,封锁法是最基本的并发控制方法之一，它可以有多种实现方式。 X locks：Only one type of lock, for both read and write,相容矩阵： NLno lock XX lock Y 相容 N不相容,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,防止连锁卷回现象的发生（多米诺骨牌） 事务结束(EOT),制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,*Two Phase Locking,Def1: In a transaction, if all locks precede all unlocks, then the transaction is called two phase transaction. This restriction is called two phase locking protocol. Def2: In a transaction, if it first acquires a lock on the object before operating on it, it is called well-formed.,2PL,not 2PL,Theorem: If S is any schedule of well-formed and 2PL transactions, then S is serializable. (王书p151证明),制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,结论：,Well-formed+2PL: serializable Well-formed+2PL+unlock update at EOT: serializable and recoverable.(不会有多米诺现象) Well-formed+2PL+holding all locks to EOT: strict two phase locking transaction.,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,(S,X) 锁 S lockif read access is intended. X lockif update access is intended.,1.使用(S,X) 锁要防止活锁现象发生 2.规定“先生请，先服务”,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,(S,U,X) 锁,U 锁update lock. For an update access the transaction first acquires a U-lock and then promote it to X-lock. 目的：减少排他时间，提高并发度，减少死锁。,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,7.9 死锁的检测处理和防止,死锁：循环等待，谁也无法得到全部资源。 活锁：虽然其它事务都在有限长的时间内释放了资源，但某事务就是无法得到想要的资源。,活锁较简单，只需稍加修改调度策略，如FIFO 死锁：(1)防(不允许发生)；(2)治(允许，能消除),制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,死锁的检测,超时法: 某事务等待时间超过某个定值，便认为发生了死锁，该事务被终止。 等待图法 G= V 事务集 Ti|Ti is a transaction in DBS (i=1,2,n) E |Ti waits for Tj (i j) 若图中有环路则说明已经发生死锁。 何时检测? 一旦某个事务等待. 周期性进行,制作：倪巍伟 东南大学计算机科学与工程学院数据库课程组,死锁的处理,如何处理死锁? 选出牺牲事务(最年轻、卷回代价最小) 终止牺牲事务释放它所有的锁及资源 该事务等待一段时间 重启动该事务(系统进行 or 用户进行