第七章 事务管理 7.1 事务 7.2 并发控制 7.3 恢复系统 7.4 长事务和实时事务.

Presentation on theme: "第七章 事务管理 7.1 事务 7.2 并发控制 7.3 恢复系统 7.4 长事务和实时事务."— Presentation transcript:

1 第七章 事务管理 7.1 事务 7.2 并发控制 7.3 恢复系统 7.4 长事务和实时事务

2 7.1 事务 7.1.1 事务概念 ACID特性实现概述 事务调度

3 7.1.1 事务概念 事务是构成单一逻辑工作单元的操作集合。 事务的ACID特性 :
事务概念 事务是构成单一逻辑工作单元的操作集合。 事务的ACID特性 : 原子性(Atomicity)：事务的所有操作在数据库中要么全部正确反映出来要么全部不反映。 一致性(Consistency)：事务的隔离执行（即没有并发执行的其它事务）保持数据库的一致性。 隔离性(Isolation)：多个事务并发执行时，系统必须保证，对任一对事务Ti和Tj，在Ti 看来，Tj或者在Ti开始之前已经停止执行，或者在Ti完成之后开始执行。这样，每个事务都感觉不到系统中有其它事务在并发地执行。 持久性(Durability)：一个事务成功完成后，它对数据库的改变必须是永久的，即使系统可能出现故障。

4 7.1.1 事务概念（2） 事务状态 提交的或中止的事务被称为已经结束的事务。 活动状态：事务执行时所处于的状态
事务概念（2） 事务状态 活动状态：事务执行时所处于的状态 部分提交状态：最后一条语句被执行后 失败状态：发现正常的执行不能继续后 中止状态：事务回滚并且数据库已被恢复到事务开始执行前的状态后 提交状态：事务成功完成后 提交的或中止的事务被称为已经结束的事务。

5 事务概念（3） 部分提交 状态 提交状态 活动状态 失败状态 中止状态

6 7.1.2 ACID特性实现概述   原子性和持久性： 由DBMS的恢复管理部件来实现，保证发生故障时一个事务对数据库的修改要么全部反映到数据库中，要么完全不反映。 早期使用的技术：影子拷贝技术 ==》效率低，不允许并发执行。 当前采用的技术：日志，备份，

7 7.1.2 ACID特性实现概述（2） 一致性： 隔离性： 单个事务的一致性由应用程序员负责。完整性约束的自动检查对此提供支持。
多个事务并发执行的正确性由DBMS的并发控制机制提供支持，通过对并发事务的合理调度来保证每个事务的一致性。

8 7.1.3 事务调度 事务调度概念 可串行化 可串行化的判定 可恢复性 SQL-92标准规定的事务一致性级别

9 7.1.3 事务调度（2） 事务调度概念 调度是指令在系统中执行的时间顺序。一组事务的一个调度必须包含这一组事务的全部指令，并且必须保持指令在各个事务中出现的顺序。 操作系统可能产生许多不同的调度，有些可能使数据库处于不一致状态，DBMS必须保证事务调度执行后数据库总处于一致状态。

10 7.1.3 事务调度（3） 例 T1从帐户A过户￥50到帐户B。 T2从帐户A过户10%的存款 T1： read(A); A:=A-50;
write(A)； read(B); B:=B+50; write(B). T2从帐户A过户10%的存款 余额到帐户B. T2：read(A); temp:=A*0.1; A:=A-temp； write(A)； read(B); B:=B+temp; write(B). 执行前 A：￥1000， B：￥2000

11 7.1.3 事务调度（4） 调度1：串行调度，T2跟在T1之后 执行后 A：￥855， B：￥2145 调度2：串行调度，T1跟在T2之后 执行后 A：￥850， B：￥2150

12 7.1.3 事务调度（5） 调度3：并发调度 等价于调度1，执行后 A：￥855， B：￥2145 T1 T2 read(B);
B:=B+50; write(B). read(A); temp:=A*0.1; A:=A-temp； write(A)； A:=A-50; B:=B+temp;

13 7.1.3 事务调度（6） 调度4：并发调度 不等价于任何串行调度， 执行后 A：￥950， B：￥2100 T1 T2
write(A)；read(B); B:=B+50; write(B). read(A); temp:=A*0.1; A:=A-temp； write(A)； read(B); A:=A-50; B:=B+temp;

14 7.1.3 事务调度（7） 可串行化 考虑哪些调度能保证一致性，哪些不能的问题。 只关心read和write操作。
可串行化：若调度S与一个串行调度的执行有 相同的效果，则称调度S是可串行化的。 基于不同的等价概念，有： 冲突可串行化 视图可串行化

15 7.1.3 事务调度（8） 冲突可串行化 冲突指令：当Ii与Ij是不同事务在相同的数据项上的操作，并且其中至少有一个是write指令时，则称Ii与Ij是冲突的。 冲突等价：如果调度S可以经过一系列非冲 突指令交换转换成S’，则称S与S’是冲突等 价的。

16 7.1.3 事务调度（9） 例 调度3 串行调度1 . . . T1 T2 read(B); write(B)； read(A);
write(A)； read(A); write(A)； read(B); write(B). T1 T2 read(B); read(A); read(A); write(A)； read(B); write(B). write(A)； write(B)； T1 T2 read(A); write(A)； read(B); write(B); read(A)； write(A)； read(B); write(B). . . . 串行调度1

17 7.1.3 事务调度（10） 冲突可串行化：若调度S与一个串行调度冲突等价，则称调度S是冲突可串行化的。
显然冲突可串行化的调度能保证一致性。 例 一个非冲突可串行化的调度 T3 T4 read(Q); write(Q)；

18 7.1.3 事务调度（11） 说明：两个调度产生相同的结果 ，并不意味着两个调度一定冲突等价。 例. 并行调度 与串行调度<T1, T5>不是冲突等价的，但产生相同的结果。 T1 T5 read(A); A:=A-50; write(A)； read(B); B:=B-10； write(B). B:=B+50; write(B)； A:=A+10；

19 7.1.3 事务调度（12） 视图可串行化 视图等价：设有相同事务集的两个调度S与S’，调度S与S’称为视图等价的，若满足下面三个条件
• 对于每个数据项Q，若事务Ti在调度S中读取了Q的初始值，那么在调度S’中Ti也必须读取Q的初始值 • 对于每个数据项Q，若事务Ti在调度S中执行了read(Q)，并且读取的值是由Tj产生的，则在调度S’中Ti读取的值也必须是由Tj产生的。 • 对于每个数据项Q，若在调度S中有事务执行了最后的write(Q)操作，则在调度S’中该事务也必须执行最后的write(Q)操作。

20 7.1.3 事务调度（13） 视图可串行化：若调度S视图等价于一个串行调度，则称调度S是视图可串行化的。 显然视图可串行化的调度能保证一致性。 每个冲突可串行化的调度都是视图可串行化 的。 某调度是视图可串行化的，并不意味着该调 度一定是冲突可串行化的

21 7.1.3 事务调度（14） 例 一个非冲突可串行化的视图可串行化调度
例 一个非冲突可串行化的视图可串行化调度 read(Q); write(Q)； T3 T4 T6 非冲突可串行化的视图可串行化调度中一定存在盲目写操作（写之前未执行读的写操作）

22 7.1.3 事务调度（15） 可串行化的判定 冲突可串行化的判定 视图可串行化的判定

23 7.1.3 事务调度（16） 冲突可串行化的判定 对应于调度S的优先图G=(V，E) V：结点集，每个结点对应于参与调度的一个事务。
E：边集，由满足下列三个条件之一的边Ti→Tj组成： • 在Tj执行read(Q)之前，Ti执行write(Q) • 在Tj执行write(Q)之前，Ti执行read(Q) • 在Tj执行write(Q)之前，Ti执行write(Q)

24 7.1.3 事务调度（17） 例 调度3的优先图 调度1的优先图 调度4的优先图 调度2的优先图 T1 T2 T1 T2 T2 T1 T1

25 7.1.3 事务调度（18） 如果优先图中存在边Ti→Tj，则在任何等价于S的串行调度S’中，Ti必出现在Tj之前。 判定：如果调度S的优先图中无环，则调度S是冲突可串行化的。 判定的时间复杂度O（n2）。 通过拓扑排序得到串行化调度。（可能多个） 反之，如果调度S的优先图中有环，则调度S一定不 是冲突可串行化的。

26 7.1.3 事务调度（19） 视图可串行化的判定 构造对应于调度S的带标记的优先图。
视图可串行化调度的判定是NP-完全问题。 事实上，利用充分条件判定视图可串行化。

27 7.1.3 事务调度（20） 可恢复性 考虑发生事务故障的情况下，什么样的调度是可接受的。 可恢复调度 无级联调度

28 7.1.3 事务调度（21） 可恢复调度 可恢复调度应满足：对于每一对事务Ti和Tj，如果Tj读取了由Ti所写的数据项，则Ti先于Tj提交。
例 一个不可恢复的调度 T T9 read(A); write(A); 提交 read(B);

29 7.1.3 事务调度（22） 无级联调度 级联回滚：因一个事务故障导致一系列事务回滚的现象。 例 T10 T11 T12 read(A);
read(B); write(A);

30 7.1.3 事务调度（23） 无级联调度应满足：对于每对事务Ti和Tj，如果Tj读取了由Ti所写的数据项，则Ti必须在Tj这一读取前提交。 某调度是无级联调度则该调度一定是可恢复调度。

31 7.1.3 事务调度（24） SQL-92标准规定的事务一致性级别 serializable：保证可串行性和不存在级联回滚。（默认的）
repeatable read：只允许读取已提交的记录，并要求一个事务对同一记录的两次读取之间，其它事务不能对该记录进行更新。然而，该事务与其它事务可能是不可串行化的。 read committed：只允许读取已提交的记录，但不要求可重复读。 read uncommitted：允许读取未提交的记录。它是SQL-92标准中允许的最低一致性级别。

32 7.2 并发控制 通过并发控制机制使得对于事务的调度是可串行化的。 基于封锁的方法 基于时间戳的方法 基于有效性确认的方法 乐观的 方法

33 7.2 并发控制（2） 7.2.1 基于封锁的方法 基于时间戳的方法 基于有效性确认的方法 插入与删除操作

34 7.2.1 基于封锁的方法 关于锁的概念 两阶段封锁协议 基于图的协议 死锁处理 多粒度封锁 索引结构的封锁

35 7.2.1 基于封锁的方法（2） 关于锁的概念 基本的锁类型 锁的相容矩阵 共享锁（S），又称读锁 排他锁（X），又称写锁 S X true
false

36 7.2.1 基于封锁的方法（3） 封锁协议: 系统中的每一个事务都必须遵从的关于何时对数据项加何种锁，何时解锁的一组规则。
两阶段封锁协议 基于图的协议 封锁协议限制了可能的调度的数目。

37 7.2.1 基于封锁的方法（4） 死锁和饿死 死锁：如果系统中存在一个事务集，集合中的每个事务在等待该集合中的另一个事务所锁住的数据项，则称系统处于死锁状态。 饿死：某事务T等待对数据项加排他锁，而另一个事务序列中的每一个事务都对该数据项加共享锁，则事务T永远得不到进展，称做饿死。

38 7.2.1 基于封锁的方法（5） 饿死的解决：可以通过按如下方式授权加锁来避免事务饿死。
当事务Ti申请对数据项Q加M型锁时，授权加锁的条件是： 不存在在数据项Q上持有与M型锁冲突的锁的其它事务。 不存在等待对数据项Q加锁且先于Ti申请加锁的事务。

39 7.2.1 基于封锁的方法（6） 两阶段封锁协议 • 两阶段封锁协议 ：要求每个事务分两个阶段提出加锁和解锁申请 ，
• 两阶段封锁协议 ：要求每个事务分两个阶段提出加锁和解锁申请 ， 增长阶段：事务可以获得锁，但不能释放锁。 缩减阶段：事务可以释放锁，但不能获得新锁。

40 7.2.1 基于封锁的方法（7） 两阶段封锁协议保证冲突可串行化，因为若事务都遵守两阶段封锁协议，则调度的优先图中无环。 将各个事务根据它们的封锁点进行排序，这个顺序就是事务的一个可串行性次序。 两阶段封锁协议不保证不发生死锁。 两阶段封锁协议不保证不发生级联回滚。

41 7.2.1 基于封锁的方法（8） • 严格两阶段封锁协议 ：两阶段封锁协议之外，还要求所有的排他锁在事务提交后才能释放。 严格两阶段封锁协议保证不发生级联回滚。 • 强两阶段封锁协议 ：两阶段封锁协议之外，还要求事务提交之前不释放任何锁。 强两阶段封锁协议下，事务可以按其提交的顺序串行化。

42 7.2.1 基于封锁的方法（9） 锁转换 ： 需要时将S锁提升为X锁（只能发生在增长阶段）。 需要时将X锁降级为S锁（只能发生在缩减阶段）。 目的是提高并发度。

43 7.2.1 基于封锁的方法（10） 系统自动进行加锁和解锁 ：一般在DBMS中由系统自动进行加锁和解锁，而不是由应用程序员在程序中进行。 简单的做法：当事务Ti进行read(Q)操作时，系统产生一个lock-S(Q)指令，后接read(Q)指令。当事务Ti进行write(Q)操作时，系统检查Ti是否已在Q上持有共享锁。若有，则系统发出upgrade(Q)指令，后接write(Q)指令。否则系统发出lock-X(Q)指令，后接write(Q)指令。当一个事务提交或回滚后，该事务持有的所有锁都被释放。

44 7.2.1 基于封锁的方法（11） 基于图的协议 研究不要求两阶段封锁协议，又保证冲突可串行化的方法。
前提：要求所有数据项集合D={ d1, d2,…. dn}满足偏序→。如果di→dj，则任何既访问di又访问dj的事务必须首先访问di，然后访问dj。这种偏序可以是数据的逻辑或物理组织的结果，也可以只是为了并发控制而加上的。 偏序意味着集合D可以视为有向无环图，称为数据库图。

45 7.2.1 基于封锁的方法（12） 树形协议：（只使用排他锁lock-X） 每个事务Ti对一数据项最多能加一次锁，并且必须遵从以下规则：
此后，Ti对数据项Q加锁的前提是Ti 持有Q的父项上的锁。 对数据项解锁可以随时进行。 数据项被Ti加锁并解锁后，Ti不能再对该数据项加锁 树形协议保证冲突可串行化，保证不发生死锁。

46 7.2.1 基于封锁的方法（13） 树形协议的优点： 树形协议的缺点： 可以在较早时候释放锁，增加了并发性。 不会产生死锁，毋需回滚。
有时事务必须给那些根本不访问的数据项加锁，导致封锁开销增加， 如果事先没有得到哪些数据项需要加锁的知识，事务将必须给树根加锁，这会大大降低并发性。

47 7.2.1 基于封锁的方法（14） 死锁处理 处理死锁的两种主要方法： 死锁预防：采用死锁预防协议保证系统永不进入死锁状态
死锁检测与死锁恢复：允许系统进入死锁状态，然后进行检测和恢复。

48 7.2.1 基于封锁的方法（15） 死锁预防 死锁预防方法1：对加锁请求加以限制。
要求每个事务开始前封锁它要访问的所有数据项，或要求事务按某个偏序规定的顺序封锁数据项。 死锁预防方法2：强占与事务回滚。 若事务T2所申请的锁已被事务T1持有，则授予T1的锁可能通过回滚事务T1被抢占，并将锁授予T2。

49 7.2.1 基于封锁的方法（16） 死锁预防方法2：强占与事务回滚。
为控制抢占，给每个事务赋一个唯一的时间戳。回滚的事务重启时保持原有的时间戳 利用时间戳的两种不同的死锁预防机制： • wait-die机制，基于非抢占技术。当事务Ti申请的数据项当前被Tj持有，仅当Ti的时间戳小于Tj的时间戳时，允许Ti等待。否则，Ti回滚。 • wound-wait机制，基于抢占技术。当事务Ti申请的数据项当前被Tj持有，仅当Ti的时间戳大于Tj的时间戳时，允许Ti等待。否则，Tj回滚。

50 7.2.1 基于封锁的方法（17） 当事务Tj不再持有事务Ti所需数据项时，这条边从等待图中删除。 系统中存在死锁当且仅当等待图中包含环。
死锁检测与恢复 ----死锁检测 等待图：G=(V，E) V：结点集，由系统中的所有事务组成。 E：边集，边Ti→Tj表示事务Ti在等待Tj释放所需数据项。 当事务Ti申请的数据项当前被Tj持有时，边Ti→Tj被插入等待图中。 当事务Tj不再持有事务Ti所需数据项时，这条边从等待图中删除。 系统中存在死锁当且仅当等待图中包含环。

51 7.2.1 基于封锁的方法（18） ----死锁恢复 发现死锁时，系统采取行动从死锁中恢复。 选择牺牲者
应使事务回滚带来的代价最小。影响事务回滚代价的因素： 事务已计算了多久，在完成之前还将计算多长时间 事务已使用了多少数据项 为完成事务还需使用多少数据项 回滚时将牵涉多少事务 回滚 彻底回滚，或只回滚到可以解除死锁处。

52 7.2.1 基于封锁的方法（19） 基于超时的机制 一种介于死锁预防与死锁检测之间的折中的机制。
申请锁的事务至多等待一个给定的时间。若在此期间内锁未授予该事务，则称该事务超时，此时该事务自己回滚并重启。 如果存在死锁，卷入死锁的一个或多个事务将超时并回滚，允许其它事务继续。

53 7.2.1 基于封锁的方法（20） 多粒度封锁 数据库元素存在层次结构，例如，数据库、表、页面、元组。 DB tab1 tab2 tab3
p11 p12 p13 p91 p92 p93 tup131 tup132 tup133 tup134 tup921 tup921

54 7.2.1 基于封锁的方法（21） 以小的粒度作为封锁单位==》提高并发度 以大的粒度作为封锁单位==》减小封锁开销 根据不同的应用的需求，系统最好支持多种粒度的封锁。 当事务对一个结点加了锁（显式），则该事务也以同样类型的锁封锁了这个结点的所有后代结点（隐含）。

55 7.2.1 基于封锁的方法（22） 问题：当一个事务申请对某数据项加锁时，系统如何判断是否有锁冲突存在。 例1 事务Ti已显式S封锁了tab1，事务Tj申请对tup132加X锁。 例2 事务Ti已显式X封锁了p93 ，事务Tj申请对tab9加S锁。

56 7.2.1 基于封锁的方法（23） 解决：引入新的锁类型 — 意向锁（I） 共享型意向锁（IS）：表示在子元素上获得共享锁的意向。 排他型意向锁（IX）：表示在子元素上获得排他锁的意向。 共享排他型意向锁（SIX）：显式地以共享方式封锁当前元素，并表示在子元素上获得排他锁的意向。

57 7.2.1 基于封锁的方法（24） 相容矩阵： IS IX S SIX X true false

58 7.2.1 基于封锁的方法（25） 多粒度封锁----封锁过程： 要在任何元素上加S或X锁，必须从层次结构的根开始。
如果希望封锁的元素在层次结构中更靠下，那么在这一结点上加一个意向锁；当前结点上的锁被授予后，继续向适当的子结点行进。 重复后两个步骤，直到到达所需结点。

59 X 7.2.1 基于封锁的方法（26） 例1 事务Ti已显式S封锁了tab1，事务Tj申请对tup132加X锁。 Ti ：IS Ti ：S
TJ ：IX X DB TJ ：IX tab1 tab2 tab3 tab9 p11 p12 p13 p91 p92 p93 tup131 tup132 tup133 tup134 tup921 tup921

60 X 7.2.1 基于封锁的方法（27） 例2 事务Ti已显式X封锁了p93 ，事务Tj申请对tab9加S锁。 Ti ：IX TJ ：IS
TJ ：S Ti ：IX DB Ti ：X tab1 tab2 tab3 tab9 p11 p12 p13 p91 p92 p93 tup131 tup132 tup133 tup134 tup921 tup921

61 7.2.1 基于封锁的方法（28） 索引结构的封锁 索引结构并发控制的特殊性： - 访问频繁，成为竞争的焦点。
-不一定要求可串行化，即只要索引查找返回正确的元组集，不一定要求两次索引查找一定看到相同的结构。 因此需要采用特殊的技术。 对B+树的封锁既不采用两阶段封锁协议，也不采用树形协议，而是采用特殊的B+树索引封锁协议。非叶结点上的锁在对B+树的其它任何结点发出加锁请求前被释放，叶结点的封锁遵循两阶段封锁协议以避免幻象。

62 7.2.2 基于时间戳的方法 时间戳 （Timestamp） 调度中考虑的一些情况 时间戳排序协议 多版本时间戳排序协议

63 7.2.2 基于时间戳的方法（2） 时间戳 为系统中的每一个事务Ti赋予唯一的固定的时间戳TS（Ti）。 赋予时间戳的方法：
使用系统时钟值作为时间戳 使用逻辑计数器 事务的时间戳决定了串行化顺序。 若TS(Ti)< TS(Tj)，则系统必须保证所产生的调度等价于事务Ti出现在事务Tj之前的某个串行调度。

64 7.2.2 基于时间戳的方法（3） 每个数据库元素Q与两个时间戳相关：
W-timestamp(Q)：成功执行write(Q)的所有事务的最大时间戳。 R-timestamp(Q)：成功执行read(Q)的所有事务的最大时间戳。

65 7.2.2 基于时间戳的方法（4） 调度中考虑的一些情况
调度器基于事实上实现的动作都应该是各 事务看起来是在它得到时间戳的一瞬间完 成的这一前提，判断事务的某些动作事实 上是不可实现的，或者是不必要做的。 1、过晚的读 2、过晚的写 3、不再有意义的写

66 7.2.2 基于时间戳的方法（5） 1、过晚的读 事务T试图读数据库元素Q，但Q的写时间表明Q现有的值是T理论上执行以后写入的。即TS(T) < W-timestamp(Q)。 例 T1 T2 start read(Q) write(Q)

67 7.2.2 基于时间戳的方法（6） 2、过晚的写 事务T试图写数据库元素Q，但Q的读时间表明另外的某个事务应该读到T写入的值但却读到另外的某个值。 即 TS(T) < R-timestamp (Q)。 例 T1 T2 start write(Q) read(Q)

68 7.2.2 基于时间戳的方法（7） 3、不再有意义的写 事务T试图写数据库元素Q，但Q的写时间表明已有一个比事务T晚开始的某个事务T’写了元素Q，即TS(T) <W-timestamp (Q)，这样T想要写入的值将永远不会被读到。 例 T1 T2 start write(Q)

69 7.2.2 基于时间戳的方法（8） 时间戳排序协议 为保证有冲突的read和write操作按时间戳顺序执行，系统所执行的协议。
1. 假设事务Ti发出read(Q) a. 若TS(Ti)< W-timestamp(Q )，则Ti需读入的Q值已被覆盖。因此，read操作被拒绝，Ti回滚。 b. 若TS(Ti)≥W-timestamp(Q)，则执行read操作，R-timestamp(Q)被设为R-timestamp(Q)与TS(Ti)两者中的较大值。

70 7.2.2 基于时间戳的方法（9） 2. 假设事务Ti发出write(Q) a. 若TS(Ti) < R-timestamp(Q)，则Ti产生的Q值是先前所需要的值，且系统已假定该值不会被产生。因此，write操作被拒绝，Ti回滚。 b. 若TS(Ti) < W-timestamp(Q)，则Ti试图写入的Q值已不再有意义。因此，这个write操作可被忽略。 c. 其它情况（即TS(Ti) >= R-timestamp(Q)且TS(Ti) >= W-timestamp(Q)），执行write操作，将W-timestamp(Q)设为TS(Ti)。

71 7.2.2 基于时间戳的方法（10） 事务Ti如果由于发出read或write操作而被并发控制机制回滚，则被赋予新的时间戳并重新启动。 时间戳排序协议保证冲突可串行化。因为冲突 操作按时间戳顺序进行处理。 时间戳排序协议保证无死锁，因为不存在等待 的事务。 时间戳排序协议可能产生不可恢复的调度。

72 7.2.2 基于时间戳的方法（11） 多版本时间戳排序协议 在事务的并发执行中保存数据项的多个拷贝。
每个write(Q)操作创建Q的一个新版本。 当进行read(Q)操作时，系统选择Q的一个版本进行读取。 并发控制机制必须保证用于读取的版本的选择能保持可串行性。

73 7.2.2 基于时间戳的方法（12） 数据项的多个版本及其时间戳
思想：数据项有多个版本，对数据项的写不覆盖先前写入的值，直到所有可能需要先前的值的事务都已完成。 事务Ti的时间戳为TS(Ti)。

74 7.2.2 基于时间戳的方法（13） 数据项Q的版本序列< Q1，Q2，…Qm>。每个版本Qk包含 • Content: Qk版本的值 • W-timestamp(Qk):创建Qk版本的事务的时间戳 • R-timestamp(Qk)：所有成功地读取Qk版本的事务的最大时间戳

75 7.2.2 基于时间戳的方法（14） 多版本时间戳机制： 当事务Ti发出read(Q)或write(Q)请求时，系统找出Q的版本序列中具有小于或等于TS(Ti)的最大写时间戳的版本Qk， 1. 如果事务Ti发出read(Q)，则返回值是Qk的内容。 2. 如果事务Ti发出write(Q)， 且若TS(Ti) < R-timestamp(Qk)， 则事务Ti回滚； 否则，若TS(Ti)= W- timestamp(Qk)， 则Qk的内容被覆盖； 否则，创建Q的一个新版本。

76 7.2.2 基于时间戳的方法（15） 版本的删除： 不再需要的版本根据以下规则删除，假设有某数据项的两个版本Qk与Qj，这两版本的W-timestamp都小于系统中最老的事务的时间戳。那么Qk和Qj中较旧的版本可以删除。

77 7.2.2 基于时间戳的方法（16） 多版本时间戳排序机制的优点： 读请求从不失败，从不等待。 多版本时间戳排序机制的缺点： 读取数据项需两次磁盘访问。 事务间的冲突通过回滚解决而不是等待。

78 7.2.3 基于有效性确认的方法 基本思想：事务的执行分为三个阶段，在开始写阶段前，事务经过一个“有效性确认阶段”，这时它已经读的和将写的元素集合被用来与其它活跃事务的写集合做比较。如果存在事实上不可实现行为的风险，该事务就被回滚。

79 7.2.3 基于有效性确认的方法（2） 事务执行的三个阶段 事务Ti的三个时间戳 有效性确认规则 三种并发控制方法比较

80 7.2.3 基于有效性确认的方法（3） 事务执行的三个阶段
读阶段：执行事务Ti，各数据项值被读入并保存在事务Ti的局部变量中。所有write操作都是对局部临时变量进行的，并不对数据库进行真正的更新。 有效性确认阶段：事务Ti进行有效性确认，判定是否可以将write操作所更新的临时局部变量值拷入数据库而不违反可串行性。 写阶段：若事务Ti已在第二步通过有效性确认，则实际的更新就可以写入数据库中。否则，事务Ti回滚。

81 7.2.3 基于有效性确认的方法（4） 事务Ti的三个时间戳 事务Ti的时间戳TS(Ti)= Validation(Ti)
Start(Ti)：事务Ti开始执行的时间 Validation(Ti)：事务Ti完成读阶段并开始其有效性确认的时间 Finish(Ti)：事务Ti完成写阶段的时间 事务Ti的时间戳TS(Ti)= Validation(Ti)

82 7.2.3 基于有效性确认的方法（5） 有效性确认规则 事务Tj要通过有效性测试，必须满足：
对于所有满足TS(Ti)<TS(Tj)的事务Ti ，有 Finish(Ti) <Start(Tj) 或Ti所写的数据集与Tj所读数据集不相交，并且Ti 的写阶段在Tj开始其有效性检查阶段之前完成 (Start(Tj)< Finish(Ti)< Validation(Tj))。 不能通过有效性测试的事务被回滚。

83 7.2.3 基于有效性确认的方法（6） 三种并发控制方法比较 性能差异依赖于事务间的相互影响的高低
封锁推迟事务但避免回滚（即使当相互影响高时）。时间戳和有效性确认不推迟事务，但能导致其回滚，而这是一种更严重形式的推迟，且浪费资源。 如果相互影响低，则时间戳和有效性确认都不会导致太多的回滚，并且它们通常比封锁调度器开销小。 当回滚必要时，时间戳比有效性确认更早地捕获问题，有效性确认在考虑一个事务是否必须回滚前总是让其做完所有的内部工作。

84 7.2.4 插入与删除操作 删除 插入 幻象问题

85 7.2.4 插入与删除操作（2） 删除 delete(Q)：从数据库中删除数据项Q 。
两阶段封锁协议下，在一数据项可以删除之前，在该数据项上必须请求加排它锁。 时间戳排序协议下，必须执行类似于为write操作进行的测试。

86 7.2.4 插入与删除操作（3） 插入 insert(Q)：插入一个新的数据项Q到数据库中并赋予Q一个初值。
两阶段封锁协议下，如果Ti执行insert(Q)操作，Ti在新创建的数据项Q上被赋予排它锁。 时间戳排序协议下，如果Ti执行insert(Q)操作，R-timestamp与W-timestamp(Q)的值被设成TS(Ti)。

87 7.2.4 插入与删除操作（4） 幻象问题 幻象指那些可能的，但当时并不存在的元组
为了说明幻象，应该区别两个不同的集合：可能的数据集合D和存在的数据集合D。 显然D  D。差集D - D的元素随时都可以作为新元素加入而成为正在进行的事务的幻象。

88 7.2.4 插入与删除操作（5） 例 事务T1： select sum(balance) from account where branch-name=”Perryridge” 事务T2： insert into account values(”Perryridge”，A-201，900)

89 7.2.4 插入与删除操作（6） 为了避免幻象，仅仅封锁在物理上已存在的数据是不够的，还必须封锁逻辑上可能的数据，即封锁幻象。 较好的解决办法 --- 使用索引封锁技术

90 7.2.4 插入与删除操作（7） 索引封锁协议：利用关系上的索引，通过索引叶结点上封锁的冲突，解决幻象问题。协议如下
 每个关系至少有一个索引。  只有首先在关系的一个或多个索引上找到元组后，这些元组才能被访问。  进行查找的事务Ti必须在它要访问的所有索引叶结点上获得共享锁。  没有更新关系r的所有索引之前，事务Ti不能插入、删除或更新关系r中的元组ti。事务必须获得受插入、删除或更新影响的所有索引叶结点上的排它锁。  必须遵循两阶段封锁协议规则。

91 7.3 恢复系统 7.3.1 概念和记号 undo日志 redo日志 undo/redo日志 检查点

92 7.3.1 概念和记号 故障分类 与事务执行相关的地址空间 事务的原语操作 日志

93 7.3.1 概念和记号（2） 故障分类 • 事务故障 • 系统崩溃，硬件或数据库软件或操作系统故障，易失性存储器内容的丢失，事务处理终止。
逻辑错误，事务由于某些内部条件而无法继续正常执行。 系统错误，系统进入一种不良状态（如，死锁），使事务无法继续正常执行。 • 系统崩溃，硬件或数据库软件或操作系统故障，易失性存储器内容的丢失，事务处理终止。 • 磁盘故障，由于磁头损坏或故障造成磁盘块上的内容丢失。

94 7.3.1 概念和记号（3） 与事务执行相关的地址空间 同数据库交互的三个地址空间： 它们在重要的方面相互影响。
1   保存数据库元素的磁盘块空间 2   缓冲区管理器所管理的虚存或主存地址空间 3   事务的局部地址空间 它们在重要的方面相互影响。

95 7.3.1 概念和记号（4） 事务的局部 地址空间 数据库 缓冲区 磁盘块 空间

96 7.3.1 概念和记号（5） 事务的原语操作 用一种记法来描述使数据在地址空间之间移动的操作：
1．INPUT(X)：将包含数据库元素X的磁盘块拷贝到主存缓冲区。 2．READ(X, t)：将数据库元素X拷贝到事务的局部变量t。 3．WRITE(X, t)：将局部变量t的值拷贝到主存缓冲区中的数据库元素X。 4. OUTPUT(X)：将包含X的缓冲区拷贝回磁盘。

97 7.3.1 概念和记号（6） 日志 日志是日志记录的序列。每个日志记录记载有关某个事务已做的事的某些情况。 日志在事务执行的过程中记录。
不同事务的日志记录在日志文件中可以交错 日志用于保证事务的原子性和持久性

98 7.3.1 概念和记号（7） 几种类型的日志： • undo日志保证事务的原子性 • redo日志保证事务的持久性 • undo/redo日志保证事务的原子性和持久性

99 7.3.1 概念和记号（8） 日志记录的形式： 事务开始记录： <START T> 表示事务T已开始。
事务提交记录： <COMMIT T> 表示事务T已成功完成并且对数据库元素不再会有修改。T对数据库所做任何更新都应反映到磁盘上。 事务中止记录：<ABORT T> 表示事务T不能成功完成。它所做的更新都不能反映到磁盘上。 更新记录：其内容随日志类型的不同而不同。表示事务T改变了数据库元素X，更新记录中可能包括X原来的值和/或X的新值。

100 7.3.1 概念和记号（9） 日志缓冲区： 在内存中开辟的临时保存日志记录的区域。每个缓冲块中能容纳若干个日志记录。 根据需要一次将一个或多个缓冲块写入磁盘，从而减少写磁盘的次数。 写到磁盘中的日志记录顺序必须与写入日志缓冲区的次序完全一致。

101 COBASE日志空间 进程日志记录缓冲 系统日志缓冲区 进程的日志页面读取缓冲 内存 外存 联机日志文件 脱机日志文件

102 7.3.2 undo日志 更新记录 undo日志规则 使用undo日志的恢复

103 7.3.2 undo日志（2） 更新记录 <T, X, v> 含义是，事务T改变了数据库元素X，X原来的值是v。
注意undo日志不记录数据库元素的新值，而只记录旧值。如果在使用undo日志的系统中需要进行恢复时，恢复管理器要做的唯一事情是通过恢复旧值消除事务可能在磁盘上造成的影响。

104 7.3.2 undo日志（3） undo日志规则 U1：如果事务T改变了数据库元素X，那么形如<T, X, v>的日志记录必须在X的新值写到磁盘前写到磁盘。 U2：如果事务提交，则其COMMIT日志记录必须在事务改变的所有数据库元素先写到磁盘后写到磁盘，但应尽快。

105 7.3.2 undo日志（4） 与事务相关的内容按如下顺序写到磁盘： a) 指明所改变数据库元素的日志记录。 b) 改变的数据库元素自身。 c) COMMIT日志记录。 但是，(a)和(b)的顺序是对各个数据库元素单独适用，而不是对事务的更新记录集合整个适用。 立即修改的技术

106 7.3.2 undo日志（5） 例 数据库中有两个元素A和B，这两个元素要满足的约束是在任何一致的状态中它们的值相等。 事务T逻辑上由下述两步构成： A := A*2; B := B*2; 将T表述为六个相关步骤的序列： READ(A, t); t := t*2; WRITE(A, t); READ(B, t); t := t*2; WRITE(B, t); 此外，缓冲区管理器最终将执行OUTPUT步骤，将这些缓冲区写回磁盘。

107 step action t M-A M-B D-A D-B LOG 1 2 3 4 5 6 7 9 10 11 12
<START T> 2 READ(A, t) 8 3 t := t*2 16 4 WRITE(A, t) <T, A, 8> 5 READ(B, t) 6 7 WRITE(B, t) <T, B, 8> FLUSH LOG 9 OUTPUT(A) 10 OUTPUT(B) 11 <COMMIT T> 12

108 7.3.2 undo日志（6） 使用undo日志的恢复 恢复管理器的工作： 从后往前扫描日志，在此过程中
1 记住所有有<COMMIT T>或<ABORT T>的事务。 2 遇到更新记录<T, X, v>时 1）如果T的COMMIT记录已被扫描到，则什么也不做。T已经提交因而不需要撤销。 2）否则，T是一个未完成的事务或一个中止的事务。恢复管理器必须将数据库中X的值改为v 。 最后，为每一个没有扫描到<ABORT T>的未完成事务写一个<ABORT T>日志记录。

109 step action t M-A M-B D-A D-B LOG 1 2 3 4 5 6 7 9 10 11 12
<START T> 2 READ(A, t) 8 3 t := t*2 16 4 WRITE(A, t) <T, A, 8> 5 READ(B, t) 6 7 WRITE(B, t) <T, B, 8> FLUSH LOG 9 OUTPUT(A) 10 OUTPUT(B) 11 <COMMIT T> 12

110 7.3.2 undo日志（7） 恢复过程中的崩溃： 由于undo日志记录的的更新记录中所给的是旧值而不是数据库元素值的改变，因此恢复步骤是幂等的，即将它们重复多次与执行一次效果完成相同。 恢复过程的幂等性对后面所讲的其它日志方式也成立。 由于恢复操作是幂等的，我们再次进行恢复时不必考虑前一次恢复所做更改。

111 7.3.3 redo日志 更新记录 redo日志规则 使用redo日志的恢复 undo日志和redo日志的缺点

112 7.3.3 redo日志（2） 更新记录 <T, X, v,> 含义是事务T改变了数据库元素X的值，其新值为v。

113 7.3.3 redo日志（3） redo日志规则 R1：在修改磁盘上的任何数据库元素X以前，要保证所有与X的这一修改相关的日志记录，包括更新记录<T, X, v>，以及<COMMIT T>记录，都必须出现在磁盘上。

114 7.3.3 redo日志（4） 与事务相关的内容写到磁盘的顺序为： 1）说明对元素进行修改的日志记录 2）COMMIT日志 3）改变的数据库元素自身  延迟修改的技术

115 step action t M-A M-B D-A D-B LOG 1 2 3 4 5 6 7 9 10 11
<START T> 2 READ(A, t) 8 3 t := t*2 16 4 WRITE(A, t) <T, A, 16> 5 READ(B, t) 6 7 WRITE(B, t) <T, B, 16> <COMMIT T> 9 FLUSH LOG 10 OUTPUT(A) 11 OUTPUT(B)

116 7.3.3 redo日志（5） 使用redo日志的恢复 恢复管理器的工作： 1 确定已提交的事务。
2 从首部开始扫描日志。对遇到的每一<T, X , v>记录： 1）如果T是未提交的事务，则什么也不做。 2）如果T是提交的事务，则为数据库元素X写入值v。 3 对每个未完成的事务T，在日志中写入一个<ABORT T>记录并刷新日志。

117 step action t M-A M-B D-A D-B LOG 1 2 3 4 5 6 7 9 10 11
<START T> 2 READ(A, t) 8 3 t := t*2 16 4 WRITE(A, t) <T, A, 16> 5 READ(B, t) 6 7 WRITE(B, t) <T, B, 16> <COMMIT T> 9 FLUSH LOG 10 OUTPUT(A) 11 OUTPUT(B)

118 7.3.3 redo日志（6） undo日志和redo日志的缺点
undo日志要求数据在事务结束后立即写到磁盘，可能增加需要进行的磁盘I/O数。 redo日志要求在事务提交和日志记录刷新以前将所有修改过的块保留在缓冲区中，可能增加事务需要的平均缓冲区数。

119 7.3.4 undo/redo日志 更新记录 undo/redo日志规则 使用undo/redo日志的恢复

120 7.3.4 undo/redo日志 （2） 更新记录 <T, X, v, w> 含义是事务T改变了数据库元素X的值；其改前值为v，新值为w。

121 7.3.4 undo/redo日志 （3） undo/redo日志规则
UR1：在由于某个事务T所做改变而修改磁盘上的数据库元素X前，更新记录<T, X, v, w>必须出现在磁盘上。 立即修改的技术

122 step action t M-A M-B D-A D-B LOG 1 2 3 4 5 6 7 9 10 11
<START T> 2 READ(A, t) 8 3 t := t*2 16 4 WRITE(A, t) <T, A，8，16> 5 READ(B, t) 6 7 WRITE(B, t) <T, B， 8，16> FLUSH LOG 9 OUTPUT(A) 10 <COMMIT T> 11 OUTPUT(B)

123 7.3.4 undo/redo日志 （4） 使用undo/redo日志的恢复
1. 从后往前扫描日志，构造undo-list和redo-list： 对每一个形如<Ti commit>的记录，将Ti 加入redo-list。 对每一个形如<Ti start>的记录，如果Ti不属于redo-list，则将Ti加入undo-list。 2. 由后至前重新扫描日志，对undo-list中的每个事务Ti的每一个日志记录执行undo操作。 3. 由前至后重新扫描日志，并且对redo-list中每个事务Ti的每一个日志记录执行redo操作。

124 step action t M-A M-B D-A D-B LOG 1 2 3 4 5 6 7 9 10 11
<START T> 2 READ(A, t) 8 3 t := t*2 16 4 WRITE(A, t) <T, A，8， 16> 5 READ(B, t) 6 7 WRITE(B, t) <T, B， 8，16> FLUSH LOG 9 OUTPUT(A) 10 <COMMIT T> 11 OUTPUT(B)

125 7.3.4 undo/redo日志 （5） 推迟提交的一个问题： 使用undo/redo日志的系统中可能出现这样的行为：事务在用户看来已经提交，但由于<COMMIT T>记录尚未刷新到磁盘，后来的一次崩溃使该事务被撤销而不是重做。 最好为undo/redo日志使用一条附加的规则： <COMMIT T>记录一旦出现在日志中就必须被刷新到磁盘上。

126 7.3.5 检查点 检查点(checkpoint) 故障恢复时扫描整个日志所带来的问题：
扫描日志耗费时间长 重做所有已提交事务耗费时间长，事实上许多事务对数据库的修改已经写到磁盘，不必再重做。 解决办法：周期性地对日志做检查点，以避免故障恢复时检查整个日志。

127 7.3.5 检查点（2） undo / redo日志检查点的做法：
1）写入日志记录<START CKPT(T1, …, Tk)>，其中T1, …, Tk是所有的活跃事务，并刷新日志。 2）将所有脏缓冲区写到磁盘，脏缓冲区即包含一个或多个修改过的数据库元素的缓冲区。 3）写入日志记录<END CKPT>并刷新日志。

128 7.4 长事务和实时事务 7.4.1 长事务问题 长事务的并发控制 实时事务系统

129 7.4.1 长事务问题 长事务：需要太长时间因而不允许它们保持其它事务所需要的锁的事务。 可能出现长事务的三大类应用： 1 传统的DBMS应用。通常的数据库应用主要运行短事务，但偶尔需要长事务。 2 设计系统。设计被划分为一系列成分，不同的设计者同时工作在不同的成分上，工作时间可能是在若干小时或若干天。 3 工作流系统。一个过程集合，有的过程由软件单独执行，有的过程需要人的交互，而有的过程可能只涉及人的活动。

130 7.4.1 长事务问题（2） A1 A2 A3 Start Reserve money available approve
Create Travel report Reserve money available Dept. Authori- zation approve not enough deny abort abort A4 A6 deny Corporate approval Write check approve abort complete give to assistant approve deny Assistant approval abort A5

131 7.4.1 长事务问题（3） 长事务的特性： • 持续时间长 • 未提交数据的曝光 • 子任务 • 可恢复性 • 性能
长事务的特性： • 持续时间长 • 未提交数据的曝光 • 子任务 • 可恢复性 • 性能 如果由于系统崩溃而使一个交互式的长事务中止，当系统恢复时，该事务必须被恢复到系统崩溃之前不久的某一个状态，而不是事务开始前的状态。 响应时间快（从人的观点看） 响应时间应该是可预知的（即，响应时间的变化应该不大）。

132 7.4.1 长事务问题（4） 要求可串行化调度所面临的困难：
• 两阶段封锁。如果数据项被一个长事务封锁了，则会发生长时间的等待，导致响应时间长，并且发生死锁的可能性增大。 • 基于图的协议。事务对于数据项的封锁必须与一个预先定义的顺序一致，导致事务封锁的数据比它实际需要的多。而且，事务确信某个锁不会再被使用之前，始终会保证该封锁，这样，很容易发生长时间的锁等待。 • 基于时间戳的协议。如果一个长事务被中止了，就会丢失大量的工作。对于交互式事务来说，这不仅是性能问题，而且是用户满意度的问题。 • 有效性确认。长事务中止问题。（与基于时间戳的协议一样）

133 7.4.2 长事务的并发控制 将一个长事务看成一组相关的子事务。 长事务：T＝{t1, t2, …, tn} T上的一个偏序P 有利于提高并发度。 T中的一个子事务ti可以中止，而不必强制地让T也中止。 T可以重新启动ti，也可以决定不运行ti。 如果ti提交了，这一动作并不使ti成为永久的。 ti提交给T，如果T中止，ti可能仍会中止，或者需要补偿。 T的执行不能违反偏序P。 有可能并行地运行几个子事务。 可以不用回滚整个长事务就能处理子事务失败。

134 7.4.2 长事务的并发控制（2） 例 可以将事务T1划分为两个子事务 子事务T1,1,从A中减掉50 子事务T1,2,往B中加上50
read(A); A:=A-50; write(A)； read(B); B:=B-10； write(B). B:=B+50; write(B)； A:=A+10；

135 7.4.2 长事务的并发控制（3） 多级事务：如果允许T的子任务在完成的时候释放锁， T就称作多级事务。代表长事务的多级事务也称作saga。 嵌套事务：如果当T的子事务tI完成时，它所持有的锁自动地赋给T，T就称作嵌套事务。

136 7.4.2 长事务的并发控制（4） 并发控制： 1 可以认为每个子事务自身是一个（短）事务，在执行时使用传统的并发控制机制，如封锁。 2 整个长事务通过“补偿事务”机制来管理。每个子事务有一个“补偿事务”，它是该子事务的逆动作，用于消除子事务的影响。

137 7.4.2 长事务的并发控制（5） 补偿事务： 为减少长时间等待的发生频率，多级事务允许将未提交的更新暴露给其他并发执行的事务。
将未提交数据暴露出去产生了级联回滚的可能性，利用补偿事务的概念帮助处理这一问题。子事务A的补偿事务记为A-1。 直观地：如果执行A，后来又执行A-1，则所产生的数据库状态同A和A-1都未执行前一样。 形式化地：如果D是任一数据库状态，B1B2 ... Bn是动作和补偿事务的任一序列，那么在数据库状态D上运行序列B1B2 ... Bn和AB1B2... Bn A-1所产生的数据库状态一样。

138 7.4.3 实时事务系统 具有截止时间的系统称作实时系统。 截止时间的特性： • 硬的。如果任务在截止时间之后完成，它的价值为零。 • 软的。如果任务在截止时间之后完成，它的价值减少了，随着延误时间的增长其价值趋近于零。 实时系统中的事务管理必须将截止时间考 虑在内。

139 7.4.3 实时事务系统 （2） 支持实时约束的主要困难之一：由于要访问的数据是否在数据库缓冲区中所引起的执行时间的巨大差异。 通常采用的技术：主存数据库