上海交通大学高级数据库课件ed6ch

1、16.1 n基于锁的协议 n死锁处理 n多粒度 n基于时间戳的协议 n基于有效性检查的协议 n多版本方案 n快照隔离 n插入,删除操作与谓词读 n实践中的弱一致性级别 16.2 n确保隔离性的一种方法: 以互斥的方式访问数据项, 即当一个事务正在访问数据 项Q时, 其他事务不能修改Q. n锁是最常用的实现互斥访问的方法: 事务只能访问它持有锁的数据项. n两种锁方式(mode): l共享(S)方式: 只能读数据项; l排它(X)方式: 数据项可读可写. n事务必须向并发控制管理器请求锁. 仅当事务被授予锁之后才能执行相应读写 操作. l数据项Q上的S-锁用 lock-S(Q)指令请求. l数据

2、项Q上的X-锁用 lock-X(Q)指令请求. 16.3 n锁相容性矩阵 n如果事务对Q的锁请求与其他事务在Q上已有的锁相容, 则可授予锁 l任意数目的事务可对同一数据持有S-锁 l若一事务对Q持有X-锁, 则其他事务不得持有Q上的任何锁. l不相容锁对应于冲突指令(ch.14) n若不能授予锁, 则发出请求的事务只能等待, 直至其他事务持有的所有不相容 锁被释放. l释放数据项Q上的锁用unlock(Q)指令 16.4 T1 T2 并发控制管理器 lock-X(B) grant-X(B, T1) read(B) B:=B-50 write(B) unlock(B) lock-S(A) gra

3、nt-S(A, T2) read (A) unlock(A) lock-S(B) grant-S(B, T2) read (B) unlock(B) display(A+B) lock-X(A) grant-X(A, T1) read(A) A:=A+50 write(A) unlock(A) T2显示不一致的总额! 16.5 T3 T4 lock-X(B) lock-S(A) read(B) read (A) B:=B-50 lock-S(B) write(B) read (B) lock-X(A) display(A+B) read(A) unlock(A) A:=A+50 unlock(

4、B) write(A) unlock(B) unlock(A) T4不会显示不一致的总额! 16.6 n考虑调度 nT3 和T4 都不能继续 执行lock-S(B) 使T4 等待T3 释放它持有的B上的锁, 而执 行 lock-X(A) 使T3 等待T4 释放它持有的A上的锁. n这种情形称为死锁死锁. l为处理死锁, T3 或T4 必须回滚并释放它持有的锁. 16.7 n如果并发控制管理器设计的不好还可能出现饿死饿死. 例如: l一个事务可能在等待给数据项加X-锁, 同时一系列其他事务在请 求并被授予同一数据项上的S-锁. l同一事务因死锁而被重复回滚. n并发控制管理器可设计成能够防止饿死

5、: 当事务T请求lock-M(Q), 仅 当满足下列条件才授予 l没有事务在Q上持有与M不相容的锁; l没有比T先提出请求且正在等待Q上锁的事务 16.8 n要求每个事务分两个阶段来发出封锁与释放请求: l阶段1: 增长阶段 4事务可获得锁 4但不能释放锁 l阶段2: 收缩阶段 4事务可释放锁 4但不能获得新锁 n2PL协议确保冲突可串行化. l试证明: 各事务可按它们的lock point(即调度中各事务获得其最后 一个锁的地方)的次序串行化. 16.9 n两阶段锁不能确保避免死锁. n两阶段锁不能避免级联回滚. l严格严格(strict)两阶段封锁协议两阶段封锁协议可避免级联回滚: 事务必

6、须保持它的所 有排他锁直至提交/中止. 4所有未提交数据都不会被其他事务读取 n强强(rigorous)两阶段封锁协议两阶段封锁协议更加严格: 所有锁都必须保持 到事务提交/中止. l事务可按它们提交的次序串行化. 16.10 n存在用两阶段封锁不能产生的冲突可串行化调度. n然而, 在没有关于事务的额外信息或对数据施加某种结构 或序的情况下, 两阶段封锁对冲突可串行化按如下意义是 必要的: 给定不遵守两阶段封锁的事务Ti, 总可以找到遵守两阶段封 锁的事务Tj 使得存在Ti 与Tj 的非冲突可串行化调度. n在缺乏有关数据项被存取的方式的信息的情况下, 两阶段 封锁协议对确保冲突可串行化是充

7、分必要的. 16.11 n允许锁转换的两阶段封锁协议: 增长阶段: l可获得 lock-S l可获得 lock-X l可将 lock-S 转换为 lock-X (升级) 收缩阶段: l可释放 lock-S l可释放 lock-X l可将 lock-X 转换为 lock-S (降级) n本协议确保冲突可串行化. 16.12 16.13 n事务Ti 发出标准的读/写操作, 无需使用显式的封锁调用. n对read(D) 的处理如下: if Ti 在D上持有锁 then read(D) else begin lock-S(D); read(D) end 16.14 n对write(D)的处理如下: i

8、f Ti 在D上有 lock-X then write(D) else if Ti 在D上有lock-S then upgrade(D); write(D) else lock-X(D); write(D) end; n所有锁在事务提交/中止之后释放 16.15 n存在事务存取数据的额外信息时, 可以构造非两阶段封锁协议, 仍保持 冲突可串行化. n例如基于图的协议: 预先知道对数据的处理次序 n在所有数据项的集合D = d1, d2 ,., dh 上施加一个偏序. l如果di dj 则同时存取di 和dj 的事务必须先存取di 后存取dj. l集合D可视为有向无圈图, 称为数据库图. n树协

9、议是图协议的一种简单形式. 16.16 n只允许排他锁. nTi 的第一个锁可以加在任何数据项上. 其后, Ti 可对数据Q 加锁仅当Q的 父节点当前已被Ti 加锁. n数据项可在任意时刻释放锁. n已被Ti 封锁及释放过的数据项此后不能被Ti 再次封锁 16.17 n树协议确保冲突可串行化且可避免死锁. n树协议中释放锁可比两阶段锁协议中更早发生. l较短等待时间, 增加并发度 l协议无死锁, 不需回滚 n缺点 l协议不能保证可恢复性或无级联回滚. 4保持排他锁到事务提交/中止. 4并发性更好的方法: 引入提交依赖. 仅确保可恢复性. l事务可能不得不对它不存取的数据项加锁. 4增加锁开销以

10、及额外的等待时间 4潜在的并发度降低 4如果没有预先的使用数据的知识, 事务只好对根加锁 n树协议可产生两阶段锁协议不能产生的调度, 反之亦然. 16.18 n考虑下列两个事务: T1: write (X) T2: write(Y) write(Y) write(X) n带来死锁的调度 T1T2 lock-X on X write (X) lock-X on Y write (X) 等待 lock-X on X 等待lock-X on Y 16.19 n如果有一个事务集合使得集合中的每个事务都在等待集合中的另一个 事务, 则系统死锁. n死锁处理的两类方法: 死锁预防vs死锁检测与恢复. l死

11、锁预防死锁预防协议确保系统永远不会进入死锁状态. l死锁检测与恢复死锁检测与恢复协议允许死锁发生, 但能检测到并能从死锁恢复. n若系统死锁概率很高, 适合用死锁预防; 否则适合用死锁检测与恢复. 16.20 n两类预防方法: l确保不会发生循环等待的方法 4要求每个事务在开始执行之前为其所有数据项加锁. 缺点: 难以预测要用的数据; 数据使用率低. 4在所有数据项上施加序, 并要求事务只能按序封锁数据项(如树协议). l利用抢占与回滚的方法: 使用事务时间戳来控制抢占与否. 4等待等待-死亡死亡方案 非抢占式 老事务等待年轻事务释放数据项. 年轻事务永远不会等待老事务, 而是回滚( 死亡).

12、 越老越可能等待;年轻事务可能在获得所需数据项之前死亡多次. 4伤害伤害-等待等待方案 抢占式 老事务伤害 (强制回滚)年轻事务而不是等待它. 年轻事务等待老事务. 年轻事务可能比等待-死亡方案有较少的回滚. 4在上面两方案中, 回滚的事务重启动时带有原来的时间戳. 老事务因此 具有对新事务的优先级, 故避免了饿死. 16.21 n基于封锁超时 l事务对一个锁只等待一个指定的时间量. 此后, 等待超时, 事务回滚. l因此即使发生死锁, 也会很快解开. l特点: 4实现简单; 适合短事务. 4可能有饿死. 4难以确定合适的超时间隔. 16.22 n死锁可用等待图描述, 即G = (V,E ),

13、 lV 是顶点集合 (即系统中的所有事务) lE 是边的集合; 其中每个元素是一有序对Ti Tj. n若Ti Tj 属于E, 则存在从Ti 到Tj 的有向边, 意味着Ti 等待Tj 释放数据 项. n当Ti 请求一个正被Tj 持有的数据项时, 边Ti Tj 被插入到等待图中. n当Tj 不再持有Ti 所需的数据项时, 这条边被删除. n系统处于死锁状态当且仅当等待图包含圈. n死锁检测: 系统维护等待图信息, 并周期性地调用死锁检测算法来查找 等待图中的圈. l若死锁频繁, 则需更经常调用死锁检测算法; 16.23 无圈的等待图 有圈的等待图 16.24 n当检测到死锁时: 某些事务必须回滚(

14、作为牺牲品)来打破死锁. l选择导致最小代价的事务作为牺牲品. 4事务已计算多久, 还需计算多久; 4事务已使用多少数据, 还需使用多少; 4回滚将涉及多少事务. l回滚 决定事务回滚多远 4完全回滚: 中止事务并重启动. 4部分回滚: 只做为打破死锁所必需的回滚. l基于代价因子的系统中, 若同一事务总是被选为牺牲品则发生了饿 死. 4在代价因子中包括回滚次数以避免饿死 16.25 n同步单位: 单个数据项 vs 一组数据项 n允许数据项具有不同大小, 从而定义一个数据粒度层次, 其中细粒度嵌 在粗粒度中 n可图示为一棵树 (勿与树封锁协议混淆) n树中每个节点都可独立加锁. n当一事务对树

15、中节点显式地加锁, 它也对该节点的所有后裔隐式地加了 同样方式的锁. n锁粒度 (封锁所在的树层次): l细粒度 (树中较低层): 高并发度, 高封锁开销 l粗粒度 (树中较高层): 低封锁开销, 低并发度 16.26 从顶层开始的各个层次是: ldatabase larea lfile lrecord 16.27 n多粒度情况下, 如何发现不同粒度数据上的锁冲突? n引入意向锁方式 l意向共享意向共享(IS): 表示在树的较低层有显式共享锁. l意向排他意向排他(IX): 表示在树的较低层有显式排他或共享锁 l共享及意向排他共享及意向排他(SIX): 以该节点为根的子树加显式共享锁, 并且在

16、 子树的某较低层加显式排他锁. n意向锁使得可对较高层节点按S或X方式加锁而无需检查其所有后裔节 点. 16.28 n包括所有封锁方式的兼容性矩阵 IS IXSS IXX IS IX S S IX X 16.29 n事务Ti 根据下列规则来封锁一个节点Q: l必须遵守锁相容性矩阵. l必须首先对树根加锁, 并且可以任何方式加锁. l仅当节点Q 的父节点当前被Ti 以IX或IS方式封锁时, Q 才可被Ti 以S或IS方 式加锁. l仅当节点Q 的父节点当前被Ti 以IX或SIX方式封锁时, Q 才可以被Ti 以X, SIX, 或IX方式加锁. l仅当Ti 先前没有对任何节点开锁时才可以对一个节点

17、加锁(即, Ti 是两阶段 的). l仅当Q 的子女当前没有被Ti 封锁时, Ti 才可以对节点Q 开锁. n锁是按从根到叶次序获得的, 但是按从叶到根次序释放的. n此协议确保可串行化. n此协议增强了并发度, 减少了锁开销. 1.不能避免死锁. 16.30 n预先为每个事务定序(可串行化序): 例如使用时间戳. n每个事务进入系统时被赋予唯一且固定的时间戳. l若一个老事务Ti 具有时间戳TS(Ti), 则一个新事务Tj 被赋予时间戳 TS(Tj) 使得 TS(Ti) TS(Tj). n事务的时间戳决定了可串行化次序: 若TS(Ti) TS(Tj), 则系统必须确保 所产生的调度等价于串行

18、调度: Ti Tj n为实现这种方案, 为每个数据Q 维护两个时间戳值: lW-timestamp(Q)是成功执行了write(Q)的所有事务中的最大时间戳 . lR-timestamp(Q)是成功执行了read(Q)的所有事务中的最大时间戳. 16.31 n时间戳序协议时间戳序协议确保任何冲突的read 和write操作按时间戳序执行. n假设事务Ti 发出read(Q) l若TS(Ti) W-timestamp(Q), 则Ti 需要读的Q的值已经被写覆盖. n因此, read 操作被拒绝, Ti 回滚. l若TS(Ti) W-timestamp(Q), 则执行read操作, 并将R-tim

19、estamp(Q) 置为 max(R-timestamp(Q), TS(Ti ). n假设事务Ti 发出write(Q) l若TS(Ti) R-timestamp(Q), 则Ti 要产生的Q 值是过去需要的, 而系统假设 该值永远不会产生了. n于是, write 操作被拒绝, Ti 回滚. l若TS(Ti) W-timestamp(Q), 则Ti 试图写一个过时的Q 值. n因此, 这个write 操作被拒绝, Ti 回滚. l否则, 执行write操作, 且将W-timestamp(Q) 置为TS(Ti). 1.事务回滚后被赋予新的时间戳, 并重新启动. 16.32 以下是具有时间戳1,

20、2, 3, 4, 5 的五个事务的一个部分调度 T1T2T3T4T5 read(Y) read(X) read(Y) write(Y) write(Z) read(Z) read(Z) abort read(X) write(Z) abort write(Y) write(Z) 16.33 n时间戳排序协议确保了冲突可串行化, 因为优先图中的所有边都形如: 因此, 优先图中没有圈. l存在2PL协议能产生而时间戳序协议不能产生的调度, 反之亦然. n时间戳协议确保不会死锁, 因为没有事务会等待. n长事务可能饿死: 一系列冲突的短事务导致该长事务反复回滚. n可能导致不可恢复调度(见下slid

21、e). 较小时间戳 事务 较大时间戳 事务 16.34 n时间戳序协议的问题: l假如Ti 中止, 但Tj 已经读了Ti 所写的一个数据项, 则Tj 必须中止; l进一步, 任何读了Tj 所写的数据项的事务必须中止. 这导致级联回滚. l若Tj 已被允许较早提交, 则该调度不可恢复. n解决方法1: 确保可恢复性与无级联回滚性. l在事务结束时一起执行所有写操作. l事务的所有写操作构成一个原子动作: 执行写时, 其他事务不能访问被写数 据. n解决方法2: 确保可恢复性与无级联回滚性. l使用一种受限形式的封锁: 对未提交数据的读操作被推迟到更新该数据的 事务提交之后. n解决方法3: 确保

22、可恢复性. l跟踪未提交写操作 l若Tj 读了Ti 所写数据, 则Tj 必须等Ti 提交之后才能提交. 4利用提交依赖 16.35 n是时间戳序协议的修改版: 某些过时write操作可忽略. n针对read操作的规则与时间戳序协议相同. nThomas write规则: 当Ti 发出write(Q), l若TS(Ti) R-timestamp(Q), 则Ti 要产生的Q 值是过去需要的, 而系统假设 该值永远不会产生了. 4于是, write 操作被拒绝, Ti 回滚. l若TS(Ti) W-timestamp(Q), 则Ti 正试图写一个过时的Q值. 4这时不是按时间戳序协议要求的那样回滚T

23、i, 而是忽略这个write操作. l否则, 执行write操作, 且将W-timestamp(Q) 置为TS(Ti) nThomas write规则允许更多的潜在并发性. l允许产生某些非冲突可串行化但观察可串行化的调度. 16.36 n当冲突很少发生时, 并发控制的监控开销就显得过大. l例如当大多数事务都是只读事务. n假设事务Ti 的执行分成顺序的三个阶段(只读事务只有两个阶段). l读与执行阶段读与执行阶段: 事务Ti 的write操作只写到Ti 的临时局部变量. l有效性检查阶段有效性检查阶段: 事务Ti 执行“有效性检查”来决定局部变量的值是否可以 写到数据库而不破坏可串行化.

24、l写阶段写阶段: 若Ti 通过有效性检查, 则更新数据库; 否则Ti 回滚. n并发执行的各事务的三个阶段可以交叉, 但是每个事务必须按顺序通过三个阶 段. n也称为乐观并发控制乐观并发控制，因为事务执行时完全寄希望于在有效性检查时一切都正 常. 1.封锁与时间戳序都是悲观的: 发现冲突时要么等待, 要么中止. 16.37 n每个事务Ti 有三个时间戳 lStart(Ti ) : Ti 开始执行的时间 lValidation(Ti ): Ti 进入有效性检查阶段的时间 lFinish(Ti ) : Ti 完成写阶段的时间 n可串行化次序由有效性检查时间戳次序决定. l即: TS(Ti )被赋予

25、Validation(Ti ) 的值. l若TS(Ti) TS(Tj), 则系统必须确保所产生的调度等价于串行调度: Ti Tj l采用Validation(Ti )而非Start(Ti )可以提高并发度, 如果冲突发生率确 实很低的话. n如果冲突的概率较小, 本协议很有用, 能带来更大程度的并发性. l因为可串行化次序不是预先决定的, 且 1.相对较少的事务会被回滚. 16.38 n若对所有满足TS(Ti ) TS(Tj )的Ti 都有下列任一条件成立: lFinish(Ti ) Start(Tj ) lStart(Tj ) Finish(Ti ) Validation(Tj ), 并且T

26、i 所写的数据项集合与 Tj 所读的数据项集合不相交. 则通过有效性检查, Tj 可以提交; 否则有效性检查失败, Tj 中止. n正确性说明: 要么满足第一个条件, 没有交叉的执行; 要么满足第二个 条件, 使得 nTj 的写不影响Ti 的读, 因为它们发生在Ti 完成读操作之后. nTi 的写不影响Tj 的读, 因为Tj 不读Ti 所写的任何数据项. n有效性检查协议自动防止了级联回滚: 实际写发生在事务提交后. n长事务可能饿死: 一系列短事务导致长事务反复重启. 16.39 n利用有效性检查产生的可串行化调度例: 假设TS(T14 )TS(T15 ) T14T15 read(B) re

27、ad(B) B:= B-50 read(A) A:= A+50 read(A) (validate) display (A+B) (validate) write (B) write (A) 16.40 n多版本并发控制方案保存数据项的老版本以增加并发性. l多版本时间戳序 l多版本两阶段锁 n每个成功的write(Q)创建Q的一个新版本. l用时间戳标记不同版本. n当发出read(Q) 操作时, 基于事务的时间戳来选择Q 的合适版本, 并返回 所选版本的值. 合适是指能确保可串行化. lread 永远不必等待, 可以立即返回一个合适的版本. 16.41 n每个数据项Q 具有一系列版本. 每

28、个版本Qk 包含三个数 据字段: l内容内容 版本Qk 的值. lW-timestamp(Qk) 创建(写)版本Qk 的事务的时间戳 lR-timestamp(Qk) 成功读取版本Qk 的事务的最大时间戳 n当事务Ti 创建Q 的一个新版本Qk 时, Qk的W-timestamp 与R-timestamp 初始化为TS(Ti). n每当事务Tj 读Qk, 并且TS(Tj) R-timestamp(Qk)时, Qk 的R-timestamp被 更新. 16.42 n假设事务Ti 发出read(Q) 或write(Q) 操作. 令Qk 表示Q 的具有小于或等于TS(Ti)的最大写 时间戳的版本.

29、l若事务Ti 发出read(Q), 则所返回的值是版本Qk 的内容. l若事务Ti 发出write(Q) 4若TS(Ti) R-timestamp(Qk), 则事务Ti 回滚. 4若TS(Ti) = W-timestamp(Qk), 则Qk 的内容被覆盖 4否则创建Q 的一个新版本. n可看出 l读操作总能成功, 且无需等待; l如果有事务本该读取Ti 所写的值却去读取了比Ti 老的另一事务所创建的版本, 则Ti 的写操作被拒绝. l读操作也导致一次写R-timestamp. l冲突是通过回滚而非等待来化解的. n此协议确保可串行化; 但不确保可恢复性与无级联回滚性. 1.删除不再需要的版本:

30、 设W-timestamp(Qj )W-timestamp(Qk )TS(Toldest ), 则Qj 可被删除. 16.43 n区分只读事务和更新事务 n更新事务获得读锁和写锁,遵循强(rigorous)两阶段封锁协议, 即将所有 锁保持到事务结束. l每个成功的write创建所写数据项的一个新版本. l数据项的每个版本都有单一时间戳, 其值得自于计数器ts-counter, 此计数器的值在每个事务提交处递增. 4因为所有事务可按其提交顺序串行化. n只读事务开始执行之前, 系统通过读取ts-counter的当前值赋予事务一 个时间戳; 执行读操作时遵循多版本时间戳序协议. 16.44 n当

31、更新事务要读取一个数据项时 l需获得其上的共享锁, 并读取最近的版本. n当更新事务要写一个数据项时 l需获得其上的X锁, 然后创建该数据项的一个新版本并设置新版本的时间戳 为. n当更新事务Ti 完成后, 进行提交处理: lTi 将它创建的版本上的时间戳设置为ts-counter + 1 lTi 将ts-counter 加1 n在Ti 递增ts-counter之后开始的只读事务将看到被Ti 更新的值. n在Ti 递增ts-counter之前开始的只读事务将看到Ti 更新之前的值. n只产生可串行化调度. 确保可恢复性与无级联回滚性. n删除无用版本: 同多版本时间戳序协议. 16.45 n事

32、务开始执行时获得一个数据库快照,然后对该快 照进行操作,与其他事务完全隔离. l快照中只包括已提交事务所写的数据值. l只读事务无需等待,也不会被中止. l更新事务的更新操作发生在事务的私有工作空间,知道 提交才写入DB 4写入DB之前需要处理与其他事务的冲突 4所有写操作必须作为一个原子操作执行,以确保其他事务的快照 要么包括该事务的所有更新,要么不包括该事务的任何更新. 16.46 n丢失更新问题:两个事务都提交并将自己的更新写 入DB,可能导致前一个事务的更新被覆盖. n先提交者获胜(first committer wins) l事务T进入部分提交状态时,以原子操作的方式执行以下 操作

33、4检查是否有与T并发执行的事务T,T已经将T想写入的Q写入DB 4如果有这样的T,则T中止 4否则T提交,并将所有更新写入DB 16.47 n先更新者获胜(first updater wins) l事务T更新Q时需要获得Q上的写锁 l如果没有并发事务持有Q上的写锁,则T获得锁,并检验更 新的有效性: 4如果Q已经被T的并发事务T更新,则T中止; 4否则T可以更新Q l如果有并发事务T持有Q的写锁,则T不能执行,并按以下 规则执行: 4T等待T中止或提交 如果T中止,则锁被释放,T可获得锁; 如果T提交,则T中止. 16.48 n写偏斜(write skew) T T read(A) read(A) read(B) read(B) write(B) write(A) lT和T都可以提交 l但是优先图中有TT和TT:T在T写A之前读A,T在T 写B之前读B 16.49 n考虑如下事务 T T T read(B) read(A) read(A) write(B) read(B) read(B) write(A) l优先图中有TT:T在T写B之前读B. l假设T提交后T仍活动,这时新的只读事务T进入系统. lT的快照包括T的更新,不包括T的更新. l优先图中有TT和TT:T在T读B之前写B,T