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