第7章 事务管理 事务管理（transaction management）： 恢复——保证事务在并发执行时满足ACID准则的技术。

Presentation on theme: "第7章 事务管理 事务管理（transaction management）： 恢复——保证事务在并发执行时满足ACID准则的技术。"— Presentation transcript:

1 第7章 事务管理 事务管理（transaction management）： 恢复——保证事务在并发执行时满足ACID准则的技术。

2 7.1 恢复引论 故障的可能性总是存在的。解决故障的措施有二：一是尽可能提高可靠性；二是恢复。 一致 状 态
这里主要讨论发生故障后，恢复数据库至一致状态的技术，即恢复技术。 系统发生故障时，可能会导致数据的丢失(loss)，要恢复丢失的数据，必须有后备副本。 对于恢复，数据冗余是必需的！

3 恢复技术大致可以分为下列三种 1.单纯以后备副本为基础的恢复技术 2.以后备副本和运行记录为基础的恢复 3.基于多副本的恢复技术

4 1.单纯以后备副本为基础的恢复技术 从文件系统继承而来，周期性的把磁盘上的数据库转储（dump）到脱机存放的磁带上。 增量转储（ID） 失效
更新丢失 取后备副本 取后备副本 取后备副本 失效 增量转储（ID） 更新丢失 取后备副本 ID 失效

5 单纯以后备副本为基础的恢复技术： 优点：实现简单，不增加数据库正常运行时的开销。 缺点：不能恢复到数据库的最近一致的状态。 多用于文件系统以及小型的不重要的数据 库系统。

6 2.以后备副本和运行记录为基础的恢复 运行记录（log或journal）由系统维护，一般包括下列内容：
（1）前像（Before Image,BI） 当数据库被一个事务更新时，所涉及的物理块更新前的映像（image）称为该事务的前像（BI），前像以物理块为单位；有了前像可以使数据库恢复到更新前状态，对应操作undo(撤销)。

7 （2）后像(After Image,AI) 当数据库被一个事务更新时，所涉及的物理块更新后的映像（image）称为该事务的后像（AI），后像也以物理块为单位；有了后像，即便更新的数据丢失了，仍然可以使数据库恢复到更新后的状态，相当于重做一次更新，对应操作redo(重做) 。

8 问题：前像(BI)、后像(AI)和事务操作的关系？
修改——有前像 有后像 插入——没前像 有后像 删除——有前像 没后像

9 记录每个事务的状态，以便在恢复时作不同的处理（COMMIT和NOT COMMIT）。
（3）事务状态 记录每个事务的状态，以便在恢复时作不同的处理（COMMIT和NOT COMMIT）。 事务失败 事务开始 活动状态 操作结束 事务提交 回卷 事务结束

10 提交(Commit)——成功执行(do all)。
回卷(Rollback或Abort)——消除事务对数据库的影响(do nothing)。 对恢复而言，至少要区分一个事务是否提交！

11 实现方法 最近后备副本 运 行 记 录 失效 运 行 记 录 最近后备副本 基于后备副本与运行记录的恢复如上图所示，当数据库失效时，取出最近后备副本，然后根据运行记录，对未提交的事务用前像卷回——向后恢复(backward recovery)；对已提交的事务，必要时用后像重做——向前恢复(forward recovery)。

12 这种恢复技术，需保持运行记录，这将会影响数据库的正常工作速度，但可以使数据库恢复到最近一致状态。大多数商品化DBMS采用这种恢复技术。

13 3.基于多副本的恢复技术 如果系统中有多个DB副本，且这些副本具有独立的失效模式(independent failure mode)，则可利用这些副本互为备份，用于恢复。 此技术在分布式数据库系统中应用的较多。 近年来，由于硬件价格的下降，也采用镜像磁盘(mirrored disks)技术。

14 当一个磁盘的数据丢失时，可以用另一个磁盘的数据来恢复。（两盘同时故障的概率可以假设为零！）
写数据时，两个磁盘都写入同样的内容。 当一个磁盘的数据丢失时，可以用另一个磁盘的数据来恢复。（两盘同时故障的概率可以假设为零！） 磁盘1 磁盘2 控制器1 控制器2 CPU1 CPU2 镜像磁盘系统 下面主要讨论第二种恢 复技术。

15 7.2 运行记录的结构 运行记录的存储要避免与数据库“全军覆没”。
运行记录(log)一般不能和数据库放在同一磁盘上，以免两者皆失。（假设log和DBMS同时失效的概率为零；一般假设log不会损坏，若运行中DBMS测得log损坏，则采取强制措施，例如拒绝新事务，完成已提交事务，停止运行，修复log）。

16 运行记录的结构因DBMS而异 Log基本内容 1.活动事务表（active transaction list---ATL）
记录所有正在执行，尚未提交的事务的标识符 (transaction identifier---TID)。 2.提交事务表（committed transaction list---CTL） 记录所有已提交事务的标识符。

17 问题：某事务需要提交时，该按照什么顺序对ATL和CTL进行更新？
注意：提交时，先将要提交事务的TID加入CTL，再从ATL中删除相应的TID。否则，一旦发生故障，该事务的状态将丢失！

18 3.前像文件 可以看成一个堆文件。每个物理块有个块标识符BID（block identifier）。BID由TID、关系名和逻辑块号组成。逻辑块号在关系中是唯一的。如果一个事务需要卷回，可以在前像文件中找出该事务的所有前像块，按照逻辑块号写入到关系的对应块，从而消除该事务对数据库的影响。 undo满足幂等性: undo(undo(undo…undo(x)))=undo(x) 因此，undo失败可以再undo!

19 4.后像文件 结构与前像文件相仿，不过记的是后像。在恢复时，可按提交事务表中的事务次序，按逻辑块号，写入其后像。这相当于按提交的次序重做各个事务。 redo满足幂等性: redo(redo(redo…redo(x)))=redo(x) 问题：undo操作需要按照事务的次序吗？为什么？

20 取后备复本后，之前的运行记录就失去了价值，对恢复来说，只要保留最近后备复本以后的运行记录。但运行记录仍可能很大。可采用下列措施减小运行记录规模。
1.不保留已提交事务的前像 2.有选择性的保留后像 3.合并后像（对给定逻辑块号的物理块，如多次更新，可只保留最近的后像） 如何判断该做undo还是redo呢？下一节，将解决这 个问题。

21 7.3 更新事务的执行与恢复 更新事务执行时，应遵守下两条规则： 1 提交规则（Commit Rule）
后像必须在事务提交前，写入非易失性存储器（DB 或log）。 即后像不能仅留在内存中！ 2 先记后写规则（Log Ahead Rule） 如果后像在事务提交前写入数据库，则必须把前像先写入log。 在执行一个更新事务时，按后像写入DB的时间，有三种可能的方案。

22 三种更新策略 a) 后像在事务提交前完全写入DB TID →active list B.I →Log (按Log Ahead Rule)
A.I →DB ┇ TID →commit list delete TID from active list

23 在这种情况下，如果出现故障，如何恢复？ Restart时，对每个TID，查两个list： Commit list Active list
undo delete TID from active list nothing to do

24 b) 后像在事务提交后写入数据库 TID →active list A.I →Log (按commit rule) ┇ TID →commit list A.I →DB delete TID from active list

25 在这种情况下，如果出现故障，如何恢复 Restart时，对每个TID，查两个list： Commit list Active list
delete TID from active list redo, delete TID from active list nothing to do

26 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

27 在这种情况下，如果出现故障，如何恢复？ Restart时，对每个TID，查两个list： Commit list Active list
undo redo, delete TID from active list nothing to do 思考：方案3均匀的将写入DB的I/O操作分散在事务提交前后，有什么优点？ 有利于磁盘均衡负载

28 7.5 消息的处理 一个事务常常要给用户发送有影响的消息(message)，不是指需要用户输入的指示消息。
例如：“付款2000元”以及“立即执行下一步处理”等。 发送消息也是事务执行结果的一部分，应该遵循“要么不做，要么全做”的原则。但是，消息往往难以用“undo”操作来消除其影响。 因此，在事务结束前，消息不能发出，只有等事务结束后才能发出。 带来什么问题？

29 消息发送委托消息管理（message manager--MM）子系统执行。
事务执行时，将需要发送的消息转给MM,MM为每个事务建立一个消息队列。 MM Ti 消息1 消息2

30 MM对事务委托发送的消息，在事务正常结束前，允许事务增加和删除；一旦事务结束，MM就把消息存于不易失存储器中。
消息（MSG） MM 终端 确认（ACK）

31 7.6 失效的类型及恢复的对策 一种恢复方法通常只对某些类型的失效有用。 通常的失效可以分为以下三类：
1.事务失效(transaction failure) 事务应不可预知的原因而夭折。 例如：数据库中没有要访问的数据、输入数据类型不对、除数为零等。 事务失效时DB未被破坏，系统控制在手。且事务失效 一定发生在事务提交前。

32 恢复措施： MM丢弃该事务的消息队列； 如果需要，进行undo操作； 从ATL删除该事务的TID，释放该事务所占资源。 2.系统失效(system failure) 系统(包括OS和DBMS)崩溃，需要重新启动(restart)，DB未被破坏，但系统失去控制。 例如：掉电、除数据库存储介质以外的软、硬件故障等。

33 恢复DB致一致状态（对未提交的事务进行undo操作 对已提交的事务进行redo操作）。
恢复措施： 重新启动OS和DBMS； 恢复DB致一致状态（对未提交的事务进行undo操作 对已提交的事务进行redo操作）。 只有当数据库恢复到一致状态后，才允许用户访问数据库。 系统中，活动事务表(ATL)的长度是有限的；由于累积效应，提交事务表（CTL）可能很长。 由于事务可以在提交前和提交后将数据的后像分别写入数据库， 因而对CTL中的事务只能全部做redo，很费时（可能CTL中的很 多事务已经完成将后像写入数据库，但鉴别代价很大）。 思考：系统失效时，要做undo和redo 操作；然而ATL长度有限，CTL可能较长。 这将导致什么结果？

34 为了减少恢复时大量redo操作的工作量，在运行过程中，DBMS每隔一定时间在运行记录中设置一个检查点(checkpoint—CP)，在检查点，DBMS强制写入所有已提交事务的后像。
最近后备副本 失效 运行记录 运行记录 CP CP CP CP CP 失效 最近后备副本 显然，在最近检查点以前提交的 事务，恢复时，不用redo。

35 取CP过程一般如下： 暂停事务的执行； 写入上一个CP以后所提交事务的后像； 在log的CTL中记下检查点； 恢复事务的执行。 取CP很影响系统的正常运行，而只有在发生系统失 效时，才有其减少redo工作量的效益。

36 3.介质失效(media failure) 磁盘发生故障，DB被破坏。 恢复措施： 修复系统，必要时更新磁盘； 如果系统（OS和DBMS）崩溃，重新启动系统； 加载最近后备副本； 用log中的后像重做取最近后备副本后提交的所有事务。

37

38 7.7 并发控制 7.7.1 数据库系统中的并发 1.串行访问(serial access)——事务顺序执行。 DBMS T3T2T1 T1
时 间

39 2.并发访问(concurrent access)——DBMS可同时接纳多个事务，事务可在时间上重叠执行。
时 间 T1 T2 T3

40 7.7.2 并发的目的 交叉并发（interleaved concurrency）——单CPU系 统，各个事务交叉使用CPU。
同时并发（simultaneous concurrency）——多CPU 系统，多个事务在CPU中同时运行。 7.7.2 并发的目的 1.提高系统资源利用率； 2.改善短事务响应时间。 例如，两个事务T1和T2， T1长，先交付； T2短，稍后交付，如果串行执行，则T2必须等T1，响应时间很长。

41 7.7.3 并发引起的问题 事务若不加控制的并发执行，会产生什么问题？ 1.丢失更新（lost update） 时间 T1 T2
Read(x) x:=x+1 Write(x) T2 x:=2*x Read(x) 丢失 Read(x) x:=x+1 Write(x) x:=2*x 问题：为什么会发生丢失更新？ Write(x) 由两个事务对同一数据并发写入引起，称为“写-写冲突”(write-write conflict)

42 2.读脏数据（dirty read） 时间 T1 T2 问题：为什么会发生读脏数据？ T1 T2 write(t) read(t[x])
rollback T2 read(t[x]) read(t[y]) read(t[x]) write(t) 脏数据 read(t[y]) rollback 问题：为什么会发生读脏数据？ 由于一个事务读取另一个更新事务尚未提交的数据引起，称为“读-写冲突”(read-write conflict)

43 3. 读值不可复现（unrepeatable read)
时间 T1 T2 T1 read(x) T2 Write(x) Read(x) Write(x) X已改变 Read(x) 问题：为什么会发生读值不可重现？ 由两个事务对同一数据并发读写引起，问题出在“写”操作上

44 事务并发执行时可能会有两种冲突： 写－写、读－写； 写－写冲突在任何情况下都应避免，读－写冲突一般情况下应避免，但某些应用场合可以容忍。

45 7.7.4 并发控制的正确性准则 思考：多个事务并发执行，结果怎么估计？
假设数据库系统中，某一时刻并发执行的事务集为{T1,T2,…Tn}，调度(Schedule)S是对n个事务所有操作的顺序的一个安排。 在S中，不同事物的操作可以交叉，但必须保持各个事务的操作的原有次序。（注意：操作是调度的基本单位！） 设Write简写为W，Read为R，R和W用其所属事务号为下标，上图的调度可表示为： S=…R1(x)…W2(x)…R1(x)…

46 对同一事务集,可能有很多种调度。 如果其中两个调度S1和S2，在数据库的任何初始状态下，所有读出的数据都一样，留给数据库的最终状态也一样，则称S1和S2是等价的，又称为目标等价(view equivalence)。 ——偏重语义，难以判断！ 还有一种更实用的等价定义，称为冲突等价(conflict equivalence)。 ——容易实现！ 冲突操作有读-写冲突和写-写冲突两种，可表示为： Ri(x)和Wj(x) Wi(x)和Wj(x) (ij)

47 冲突操作的执行次序会影响执行结果，不冲突操作的次序可以互换，不致影响执行结果。
凡是通过调换S中不冲突操作得到的新的调度，称为S的冲突等价调度。 如果两个调度是冲突等价的，一定是目标等价的；反之未必！

48 若调度S在数据库中产生的效果，与这组事务的某个串行执行序列的结果相同，则称这个调度S是可串行化的（serializable）。
例如，对事务集{T1,T2,T3}的一个调度： S = R2(x) W3(x) R1(y) W2(y) S’= R1(y) R2(x) W2(y) W3(x) S’是串行调度，故S是冲突可串行化的，也是目标可串 行化的！

49 冲突可串行化的调度一定是目标可串行化的吗？
目标可串行化的调度一定是冲突可串行化的吗？ 目标可串行化的调度未必是冲突可串行化！ 例如，调度S=R1(x)W2(x)W1(x)W3(x) 无冲突等价调度，但却可以找到一个调度S’： S’=R1(x)W1(x)W2(x)W3(x)与S目标等价。

50 目标可串行化 冲突可串行化 多个事务串行执行后，DB仍保持一致状态。可串行化调度与事务的某个串行执行等价。当然也保持数据库的一致状态，因此，在一般的DBMS中，都是以可串行化作为并发控制的正确性准则！

51 可串行化——并发控制的正确性准则 问题：不同的调度→不同的等价串行序列→不同的执行结果？(n!)

52 关于目标等价与冲突等价 调度：是系统对n个并发事务的所有操作的顺序的一个安排。
目标等价：两个调度s1和s2，如果在同样的初始条件下执行，对数据库产生的效果完全相同，则称s1和s2是目标等价的。 冲突操作：R-W、W-W。冲突操作的执行顺序会影响执行效果。 不冲突操作：①R-R ②虽有写操作，但作用对象不同，如Ri(x)和Wj(y)。 冲突等价：凡是通过调换s中的不冲突操作所得的新调度，称为s的冲突等价调度。

53 性质：如两调度是冲突等价的，则一定是目标等价的；反之未必正确。
串行化也分为目标可串行化和冲突可串行化。 例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目标等价。

54 目标可串行化的测试算法是NP难度的，冲突可串行化覆盖了绝大部分可串行化的调度实例，所以今后如无特别说明，可串行化均指冲突可串行化。
前趋图 有向图G=<V,E> V——顶点的集合，包含所有参与调度的事务。 E——边的集合，通过分析冲突操作来决定。如果下列条件之一成立，可在E中加边Ti→Tj： Ri(x)在Wj(x)之前 Wi(x)在Rj(x)之前 Wi(x)在Wj(x)之前 最后，看构造好的前趋图中是否有环路，如果有，则该调度不可串行化；否则，可串行化。

55 可串行化时，决定等价串行调度序列的算法：
由于无环路，必有入度为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) 它是否可串行化？如可串行化找出其等价的串行执行序列。

56 S= W3(y)R1(x)R2(y)W3(x)W2(x)W3(z)R4(z)W4(x)
T2 T3 T4 队列:T1 T2 T4 队列:T1,T3 T2 T1 T4 T3 T4 队列:T1,T3,T2 等价串行序列：T1→T3→T2→T4 空 并发控制的任务就是对并发执行的事务加以控制，使之按某种可串行化的调度序列来执行。

57 7.8 加锁协议—Lock Protocol 封锁法是最基本的并发控制方法之一，它可以有多种实现方式。
X locks：Only one type of lock, for both read and write 相容矩阵： NL－no lock X－X lock Y －相容 N－不相容 X_lock R wait Read R ┇ TB X_lock R Update R ┇ X_unlock R EOT TA 待加 已有 NL X Y N

58 防止连锁卷回现象的发生（多米诺骨牌） 事务结束(EOT)

59 *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. T1 Lock A Lock B Lock C ┇ Unlock A Unlock B Unlock C T2 Theorem: If S is any schedule of well-formed and 2PL transactions, then S is serializable. (王书p151证明) Growing phase Shrinking phase 2PL not 2PL

60 结论： 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.

61 S lock——if read access is intended.
(S,X) 锁 S lock——if read access is intended. X lock——if update access is intended. 待加 已有 NL S X Y N 1.使用(S,X) 锁要防止活锁现象发生 2.规定“先生请，先服务”

62 (S,U,X) 锁 U 锁——update lock. For an update access the transaction first acquires a U-lock and then promote it to X-lock. 目的：减少排他时间，提高并发度，减少死锁。 待加 已有 NL S U X Y N X (S,X) (S,U,X) concurrency

63 7.9 死锁的检测处理和防止 死锁：循环等待，谁也无法得到全部资源。
活锁：虽然其它事务都在有限长的时间内释放了资源，但某事务就是无法得到想要的资源。 X_lock R1 ┇ X_lock R2 wait TA TB R T1: S-lock T2: S-lock ┇ T: x-lock 活锁较简单，只需稍加修改调度策略，如FIFO 死锁：(1)防(不允许发生)；(2)治(允许，能消除)

64 死锁的检测 超时法: 某事务等待时间超过某个定值，便认为发生了死锁，该事务被终止。 等待图法 G=<V,E>
V — 事务集 {Ti|Ti is a transaction in DBS (i=1,2,…n)} E － {<Ti,Tj>|Ti waits for Tj (i ≠ j)} 若图中有环路则说明已经发生死锁。 何时检测? 一旦某个事务等待. 周期性进行

65 死锁的处理 如何处理死锁? 选出牺牲事务(最年轻、卷回代价最小…) 终止牺牲事务释放它所有的锁及资源 该事务等待一段时间
重启动该事务(系统进行 or 用户进行)

66 死锁的防止 一次性申请所有锁 将数据对象编号，按序号加锁 一旦冲突，便终止相关事务 卷回重执

67 每个事务有唯一的时标.若在TA在某个已被TB加锁的数据对象上申请锁，采用下面的一种策略:
等待-死亡（Wait-die）: 若TA比TB老，TA等待 ，否则 TA“死亡”， i.e. 隔一段时间， TA 将重运行（仍用原时间标记） 击伤-等待（Wound-wait）:若TA比TB年轻，TA等待 ，否则，TA “击伤” TB, i.e. TB 被终止，隔一段时间，将重运行（仍用原时间标记） 上述方法中，都只有一个方向的等待，年老→ 年轻或年轻→年老，所以不会出现循环等待，从 而避免了死锁的发生。

68 7.10 多粒度封锁 Lock Granularities
所以大数据库中封锁单位分几级： DB－File－Record－Field 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.

69 所以多级封锁有两种锁法： Explicit lock Implicit lock

70 意向锁 如何检查implicit locks？
IBM的intention lock：提供IS、IX和SIX三种意向锁。例如低级某对象加了S锁，则在它所属的高级各对象上加IS锁，作为警告信息。这样在高级某对象上要加X锁时，就可以发现隐含的冲突。 DB File Record Field IS IS－Intention share lock IX－Intention exclusive lock SIX－S＋IX IS S

71 加锁原则： Locks are requested from root to leaves and released from leaves to root. 加锁顺序 DB File Record Field 例： record file DB (1) S IS (2) X IX (3) All read and some write SIX IX, IS 对要写的record加X锁 以强代弱

72 多级封锁时的相容矩阵： 加锁时可以以强(排他性)代弱，但不能以弱代强。 X SIX IX S IS NL 强 弱 排他性 NL IS IX
待加 已有 NL IS IX S SIX X Y N 加锁时可以以强(排他性)代弱，但不能以弱代强。