上海交通大学 高级数据库 课件 陆朝俊ed6ch15.ppt

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

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

3、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显示不一致的总额!,推迟释放锁,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(B) w

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

5、足下列条件才授予 没有事务在Q上持有与M不相容的锁; 没有比T先提出请求且正在等待Q上锁的事务,两阶段封锁协议,要求每个事务分两个阶段来发出封锁与释放请求: 阶段1: 增长阶段 事务可获得锁 但不能释放锁 阶段2: 收缩阶段 事务可释放锁 但不能获得新锁 2PL协议确保冲突可串行化. 试证明: 各事务可按它们的lock point(即调度中各事务获得其最后一个锁的地方)的次序串行化.,两阶段封锁协议 (续),两阶段锁不能确保避免死锁. 两阶段锁不能避免级联回滚. 严格(strict)两阶段封锁协议可避免级联回滚: 事务必须保持它的所有排他锁直至提交/中止. 所有未提交数据都不会被其他事务读取

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

7、X 可将 lock-S 转换为 lock-X (升级) 收缩阶段: 可释放 lock-S 可释放 lock-X 可将 lock-X 转换为 lock-S (降级) 本协议确保冲突可串行化.,锁转换调度例,封锁指令的自动生成,事务Ti 发出标准的读/写操作, 无需使用显式的封锁调用. 对read(D) 的处理如下: if Ti 在D上持有锁 then read(D) else begin lock-S(D); read(D) end,封锁指令的自动生成(续),对write(D)的处理如下: if Ti 在D上有 lock-X then write(D) else if Ti 在D上有lock-S

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

9、加锁仅当Q的父节点当前已被Ti 加锁. 数据项可在任意时刻释放锁. 已被Ti 封锁及释放过的数据项此后不能被Ti 再次封锁,树协议 (续),树协议确保冲突可串行化且可避免死锁. 树协议中释放锁可比两阶段锁协议中更早发生. 较短等待时间, 增加并发度 协议无死锁, 不需回滚 缺点 协议不能保证可恢复性或无级联回滚. 保持排他锁到事务提交/中止. 并发性更好的方法: 引入提交依赖. 仅确保可恢复性. 事务可能不得不对它不存取的数据项加锁. 增加锁开销以及额外的等待时间 潜在的并发度降低 如果没有预先的使用数据的知识, 事务只好对根加锁 树协议可产生两阶段锁协议不能产生的调度, 反之亦然.,死锁处理

10、,考虑下列两个事务: T1: write (X) T2: write(Y) write(Y) write(X) 带来死锁的调度,T1,T2,lock-X on X write (X),lock-X on Y write (X) 等待 lock-X on X,等待lock-X on Y,死锁处理,如果有一个事务集合使得集合中的每个事务都在等待集合中的另一个事务, 则系统死锁. 死锁处理的两类方法: 死锁预防vs死锁检测与恢复. 死锁预防协议确保系统永远不会进入死锁状态. 死锁检测与恢复协议允许死锁发生, 但能检测到并能从死锁恢复. 若系统死锁概率很高, 适合用死锁预防; 否则适合用死锁检测与恢复

11、.,死锁预防策略,两类预防方法: 确保不会发生循环等待的方法 要求每个事务在开始执行之前为其所有数据项加锁. 缺点: 难以预测要用的数据; 数据使用率低. 在所有数据项上施加序, 并要求事务只能按序封锁数据项(如树协议). 利用抢占与回滚的方法: 使用事务时间戳来控制抢占与否. 等待-死亡方案 非抢占式 老事务等待年轻事务释放数据项. 年轻事务永远不会等待老事务, 而是回滚(死亡). 越老越可能等待;年轻事务可能在获得所需数据项之前死亡多次. 伤害-等待方案 抢占式 老事务伤害 (强制回滚)年轻事务而不是等待它. 年轻事务等待老事务. 年轻事务可能比等待-死亡方案有较少的回滚. 在上面两方案中

12、, 回滚的事务重启动时带有原来的时间戳. 老事务因此具有对新事务的优先级, 故避免了饿死.,基于超时的方案,基于封锁超时 事务对一个锁只等待一个指定的时间量. 此后, 等待超时, 事务回滚. 因此即使发生死锁, 也会很快解开. 特点: 实现简单; 适合短事务. 可能有饿死. 难以确定合适的超时间隔.,死锁检测,死锁可用等待图描述, 即G = (V,E ), V 是顶点集合 (即系统中的所有事务) E 是边的集合; 其中每个元素是一有序对Ti Tj. 若Ti Tj 属于E, 则存在从Ti 到Tj 的有向边, 意味着Ti 等待Tj 释放数据项. 当Ti 请求一个正被Tj 持有的数据项时, 边Ti

13、Tj 被插入到等待图中. 当Tj 不再持有Ti 所需的数据项时, 这条边被删除. 系统处于死锁状态当且仅当等待图包含圈. 死锁检测: 系统维护等待图信息, 并周期性地调用死锁检测算法来查找等待图中的圈. 若死锁频繁, 则需更经常调用死锁检测算法;,死锁检测 (续),无圈的等待图,有圈的等待图,死锁恢复,当检测到死锁时: 某些事务必须回滚(作为牺牲品)来打破死锁. 选择导致最小代价的事务作为牺牲品. 事务已计算多久, 还需计算多久; 事务已使用多少数据, 还需使用多少; 回滚将涉及多少事务. 回滚 决定事务回滚多远 完全回滚: 中止事务并重启动. 部分回滚: 只做为打破死锁所必需的回滚. 基于代

14、价因子的系统中, 若同一事务总是被选为牺牲品则发生了饿死. 在代价因子中包括回滚次数以避免饿死,多粒度,同步单位: 单个数据项 vs 一组数据项 允许数据项具有不同大小, 从而定义一个数据粒度层次, 其中细粒度嵌在粗粒度中 可图示为一棵树 (勿与树封锁协议混淆) 树中每个节点都可独立加锁. 当一事务对树中节点显式地加锁, 它也对该节点的所有后裔隐式地加了同样方式的锁. 锁粒度 (封锁所在的树层次): 细粒度 (树中较低层): 高并发度, 高封锁开销 粗粒度 (树中较高层): 低封锁开销, 低并发度,粒度层次例,从顶层开始的各个层次是: database area file record,意向锁

15、方式,多粒度情况下, 如何发现不同粒度数据上的锁冲突? 引入意向锁方式 意向共享(IS): 表示在树的较低层有显式共享锁. 意向排他(IX): 表示在树的较低层有显式排他或共享锁 共享及意向排他(SIX): 以该节点为根的子树加显式共享锁, 并且在子树的某较低层加显式排他锁. 意向锁使得可对较高层节点按S或X方式加锁而无需检查其所有后裔节点.,含意向锁方式的相容矩阵,包括所有封锁方式的兼容性矩阵,多粒度封锁协议,事务Ti 根据下列规则来封锁一个节点Q: 必须遵守锁相容性矩阵. 必须首先对树根加锁, 并且可以任何方式加锁. 仅当节点Q 的父节点当前被Ti 以IX或IS方式封锁时, Q 才可被Ti

16、 以S或IS方式加锁. 仅当节点Q 的父节点当前被Ti 以IX或SIX方式封锁时, Q 才可以被Ti 以X, SIX, 或IX方式加锁. 仅当Ti 先前没有对任何节点开锁时才可以对一个节点加锁(即, Ti 是两阶段的). 仅当Q 的子女当前没有被Ti 封锁时, Ti 才可以对节点Q 开锁. 锁是按从根到叶次序获得的, 但是按从叶到根次序释放的. 此协议确保可串行化. 此协议增强了并发度, 减少了锁开销. 不能避免死锁.,基于时间戳的协议,预先为每个事务定序(可串行化序): 例如使用时间戳. 每个事务进入系统时被赋予唯一且固定的时间戳. 若一个老事务Ti 具有时间戳TS(Ti), 则一个新事务T

17、j 被赋予时间戳TS(Tj) 使得 TS(Ti) TS(Tj). 事务的时间戳决定了可串行化次序: 若TS(Ti) TS(Tj), 则系统必须确保所产生的调度等价于串行调度: Ti Tj 为实现这种方案, 为每个数据Q 维护两个时间戳值: W-timestamp(Q)是成功执行了write(Q)的所有事务中的最大时间戳. R-timestamp(Q)是成功执行了read(Q)的所有事务中的最大时间戳.,基于时间戳的协议 (续),时间戳序协议确保任何冲突的read 和write操作按时间戳序执行. 假设事务Ti 发出read(Q) 若TS(Ti) W-timestamp(Q), 则Ti 需要读的

18、Q的值已经被写覆盖. 因此, read 操作被拒绝, Ti 回滚. 若TS(Ti) W-timestamp(Q), 则执行read操作, 并将R-timestamp(Q) 置为max(R-timestamp(Q), TS(Ti ). 假设事务Ti 发出write(Q) 若TS(Ti) R-timestamp(Q), 则Ti 要产生的Q 值是过去需要的, 而系统假设该值永远不会产生了. 于是, write 操作被拒绝, Ti 回滚. 若TS(Ti) W-timestamp(Q), 则Ti 试图写一个过时的Q 值. 因此, 这个write 操作被拒绝, Ti 回滚. 否则, 执行write操作,

19、且将W-timestamp(Q) 置为TS(Ti). 事务回滚后被赋予新的时间戳, 并重新启动.,协议使用例,以下是具有时间戳1, 2, 3, 4, 5 的五个事务的一个部分调度,T1,T2,T3,T4,T5,read(Y),read(X),read(Y),write(Y),write(Z),read(Z),read(Z),abort,read(X),write(Z),abort,write(Y),write(Z),时间戳序协议的正确性,时间戳排序协议确保了冲突可串行化, 因为优先图中的所有边都形如: 因此, 优先图中没有圈. 存在2PL协议能产生而时间戳序协议不能产生的调度, 反之亦然. 时

20、间戳协议确保不会死锁, 因为没有事务会等待. 长事务可能饿死: 一系列冲突的短事务导致该长事务反复回滚. 可能导致不可恢复调度(见下slide).,较小时间戳 事务,较大时间戳 事务,可恢复性与无级联回滚,时间戳序协议的问题: 假如Ti 中止, 但Tj 已经读了Ti 所写的一个数据项, 则Tj 必须中止; 进一步, 任何读了Tj 所写的数据项的事务必须中止. 这导致级联回滚. 若Tj 已被允许较早提交, 则该调度不可恢复. 解决方法1: 确保可恢复性与无级联回滚性. 在事务结束时一起执行所有写操作. 事务的所有写操作构成一个原子动作: 执行写时, 其他事务不能访问被写数据. 解决方法2: 确保

21、可恢复性与无级联回滚性. 使用一种受限形式的封锁: 对未提交数据的读操作被推迟到更新该数据的事务提交之后. 解决方法3: 确保可恢复性. 跟踪未提交写操作 若Tj 读了Ti 所写数据, 则Tj 必须等Ti 提交之后才能提交. 利用提交依赖,Thomas Write规则,是时间戳序协议的修改版: 某些过时write操作可忽略. 针对read操作的规则与时间戳序协议相同. Thomas write规则: 当Ti 发出write(Q), 若TS(Ti) R-timestamp(Q), 则Ti 要产生的Q 值是过去需要的, 而系统假设该值永远不会产生了. 于是, write 操作被拒绝, Ti 回滚.

22、 若TS(Ti) W-timestamp(Q), 则Ti 正试图写一个过时的Q值. 这时不是按时间戳序协议要求的那样回滚Ti, 而是忽略这个write操作. 否则, 执行write操作, 且将W-timestamp(Q) 置为TS(Ti) Thomas write规则允许更多的潜在并发性. 允许产生某些非冲突可串行化但观察可串行化的调度.,基于有效性检查的协议,当冲突很少发生时, 并发控制的监控开销就显得过大. 例如当大多数事务都是只读事务. 假设事务Ti 的执行分成顺序的三个阶段(只读事务只有两个阶段). 读与执行阶段: 事务Ti 的write操作只写到Ti 的临时局部变量. 有效性检查阶段

23、: 事务Ti 执行“有效性检查”来决定局部变量的值是否可以写到数据库而不破坏可串行化. 写阶段: 若Ti 通过有效性检查, 则更新数据库; 否则Ti 回滚. 并发执行的各事务的三个阶段可以交叉, 但是每个事务必须按顺序通过三个阶段. 也称为乐观并发控制，因为事务执行时完全寄希望于在有效性检查时一切都正常. 封锁与时间戳序都是悲观的: 发现冲突时要么等待, 要么中止.,基于有效性检查的协议(续),每个事务Ti 有三个时间戳 Start(Ti ) : Ti 开始执行的时间 Validation(Ti ): Ti 进入有效性检查阶段的时间 Finish(Ti ) : Ti 完成写阶段的时间 可串行化

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

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

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

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

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

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

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

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

32、想写入的Q写入DB 如果有这样的T,则T中止 否则T提交,并将所有更新写入DB,更新事务的有效性检验(续),先更新者获胜(first updater wins) 事务T更新Q时需要获得Q上的写锁 如果没有并发事务持有Q上的写锁,则T获得锁,并检验更新的有效性: 如果Q已经被T的并发事务T更新,则T中止; 否则T可以更新Q 如果有并发事务T持有Q的写锁,则T不能执行,并按以下规则执行: T等待T中止或提交 如果T中止,则锁被释放,T可获得锁; 如果T提交,则T中止.,快照隔离不能保证可串行化,写偏斜(write skew) T T read(A) read(A) read(B) read(B)

33、write(B) write(A) T和T都可以提交 但是优先图中有TT和TT:T在T写A之前读A,T在T写B之前读B,快照隔离不能保证可串行化(续),考虑如下事务 T T T read(B) read(A) read(A) write(B) read(B) read(B) write(A) 优先图中有TT:T在T写B之前读B. 假设T提交后T仍活动,这时新的只读事务T进入系统. T的快照包括T的更新,不包括T的更新. 优先图中有TT和TT:T在T读B之前写B,T在T写A之前读A,插入与删除操作,迄今考虑的操作仅限于read和write,这将事务局限于数据库已有数据. 事务还需要增加新数据和删除老数据的操作: delete(Q)和insert(Q). 逻辑错误: 当Q被插入前或删除后,事务执行read(Q)或write(Q); 删除不存在的数据. 冲突分析: delete(Q)与read(Q), write(Q), delete(Q), insert(Q)都冲突; insert(Q)与read(Q), write(Q), delete(Q)都冲突. 如果使用两阶段锁协议: 仅当删除数据的事务对被删除数据具有X锁时, delete操作才可执行. 向数据库插入一条新元组的事务对该元组获得X锁. 如果使用时间戳序协议: 对del