第15章 事务.ppt

《第15章 事务.ppt》由会员分享，可在线阅读，更多相关《第15章 事务.ppt（35页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Silberschatz,Korth and Sudarshan15.1Database System ConceptsChapter 15:事务事务n事务概念n事务状态n原子性与持久性的实现n并发执行n可串行性n可恢复性n隔离性的实现nSQL中事务的定义n检测可串行性Silberschatz,Korth and Sudarshan15.2Database System Concepts事务概念事务概念n事务事务是程序的逻辑运行单位n事务必须保持数据库的一致性n在事务执行过程中,数据库可能处于不一致状态n当事务提交时,数据库必须处于一致状态n要处理的两个问题:各种故障,如硬件故障和系统崩溃多个

2、事务的并发执行Silberschatz,Korth and Sudarshan15.3Database System ConceptsACID 性质性质nAtomicity.事务的操作要么完全执行,要么全不做nConsistency.在隔离状态下事务的执行保持数据库的一致性nIsolation.尽管多个事务可以并发执行,每个事务必须不了解其他并发执行的事务.事务的中间结果对其他并发事务是不可见的nDurability.事务成功结束后,对数据库所做的更新将永久化,即使再发生系统故障也不受影响.为保持数据一致性,数据库系统必须确保:Silberschatz,Korth and Sudarshan1

3、5.4Database System Concepts转账例转账例n从账户A 转移$50到账户B:1.read(A)2.A:=A 503.write(A)4.read(B)5.B:=B+506.write(B)n一致性要求 事务执行前后 A 与 B 之和保持不变.n原子性要求 若事务在第3步之后及第6步之前失败,系统应确保事务所做更新不被反映到数据库中,否则会出现不一致.Silberschatz,Korth and Sudarshan15.5Database System Concepts转账例转账例(续续)n持久性要求 一旦用户被告知事务已经完成(即,$50 转账已经发生),则即使发生故障,

4、事务对数据库的更新也必须持久化.n隔离性要求 若在第3步与第6步之间允许另一事务存取部分更新的数据库,该事务将看到不一致的数据库(A+B 小于正确值).可通过串行(即一个接一个)执行事务来确保隔离性.但是并发执行多个事务具有很多好处.Silberschatz,Korth and Sudarshan15.6Database System Concepts事务状态事务状态nActive,初始状态;事务执行时也处于此状态nPartially committed,最后一条语句执行之后.nFailed,发现不能继续正常执行之后.nAborted,事务已回滚并且数据库已恢复到事务开始前的状态之后.此后有两

5、种选择:重启事务 仅当非内部逻辑错误时杀死事务nCommitted,事务成功结束之后.Silberschatz,Korth and Sudarshan15.7Database System Concepts事务状态事务状态(续续)Silberschatz,Korth and Sudarshan15.8Database System Concepts原子性与持久性的实现原子性与持久性的实现n数据库系统的恢复管理部件负责实现对原子性与持久性的支持.nshadow-database 方案:假设每次只有一个事务处于激活状态.指针db_pointer 总是指向当前的数据库的一致拷贝.所有更新都是对数据库

6、的一份shadow copy 进行的,仅当事务到达部分提交状态并且所有更新页都已写回磁盘db_pointer 才指向更新后的shadow copy.如果事务失败,db_pointer所指向的旧的一致拷贝仍可用,而shadow copy 则被删除.Silberschatz,Korth and Sudarshan15.9Database System Concepts原子性与持久性的实现原子性与持久性的实现原子性与持久性的实现原子性与持久性的实现(续续续续)n假设磁盘不出故障n可用于文本编辑器,但对大型数据库极端低效:执行一个事务就需要拷贝整个数据库.shadow-database 方案:Silb

7、erschatz,Korth and Sudarshan15.10Database System Concepts并发执行并发执行n多个事务可同时运行.好处是:增加处理器和磁盘的利用率增加处理器和磁盘的利用率,导致更好的事务吞吐量:一个事务正在使用CPU而另一个正在读写磁盘减少事务的平均响应时间减少事务的平均响应时间:短事务不应等在长事务之后.n并发控制方案 达到隔离性的机制,即控制并发事务的交互以防止它们破坏数据库的一致性第14章介绍Silberschatz,Korth and Sudarshan15.11Database System Concepts调度调度n调度 并发事务的指令按时间顺

8、序执行的序列事务集合的一个调度必须包括所有事务的所有指令必须保持各个事务内部的指令顺序Silberschatz,Korth and Sudarshan15.12Database System Concepts调度例调度例n令T1 从A 转账$50到B,T2 从A 转账余额的10%到B.下列是一个串行调度(教材中的Schedule 1),先T1 后T2.Silberschatz,Korth and Sudarshan15.13Database System Concepts调度例调度例(续续)n令T1 与T2 如前定义.下列调度(教材中的Schedule 3)不是串行调度,但与Schedule

9、1等价.Schedule 1 和3都保持和A+B.Silberschatz,Korth and Sudarshan15.14Database System Concepts调度例调度例(续续)n下列并发调度(教材中的Schedule 4)未能保持和A+B.Silberschatz,Korth and Sudarshan15.15Database System Concepts可串行化可串行化n基本假定 每个事务都保持数据库的一致性.n故一组事务的串行执行也保持数据库的一致性.n一个(并发)调度是可串行化的当且仅当它与一个串行调度等价.不同形式的调度等价定义(冲突等价和观察等价)导致不同的可串行

10、化概念:1.冲突可串行化2.观察可串行化n我们忽略除read和write之外的操作指令,并且假设在读和写之间事务对局部缓冲区内的数据可以执行任意的计算.简化的调度只包含 read与write指令.Silberschatz,Korth and Sudarshan15.16Database System Concepts冲突可串行化冲突可串行化n事务Ti 和Tj的指令li 和lj 冲突冲突 当且仅当 存在li 和lj 都存取的数据项Q,且至少有一条写Q 的指令.1.li=read(Q),lj=read(Q).li 与 lj 不冲突.2.li=read(Q),lj=write(Q).冲突.3.li=

11、write(Q),lj=read(Q).冲突4.li=write(Q),lj=write(Q).冲突n直观地,li 与lj 之间的冲突强制要求它们之间要有一个(逻辑上的)时间顺序.如果 li 与 lj 在一个调度中是连续的且不冲突,则即使交换其顺序也会保持相同结果.Silberschatz,Korth and Sudarshan15.17Database System Concepts冲突可串行化冲突可串行化(续续)n若调度S 通过一系列交换非冲突指令可转换成调度S,则称S 与S 冲突等价冲突等价.n若调度S 与一个串行调度冲突等价,则称调度S是冲突可串行冲突可串行化的化的n非冲突可串行化调度

12、例:T3T4read(Q)write(Q)write(Q)不可能通过交换上面这个调度的指令而得到串行调度 或.Silberschatz,Korth and Sudarshan15.18Database System Concepts冲突可串行化冲突可串行化(续续)n通过一系列交换非冲突指令,下面的Schedule 3 可转换成串行调度(Schedule 1).因此Schedule 3 是冲突可串行化的.Silberschatz,Korth and Sudarshan15.19Database System Concepts观察可串行化观察可串行化n令S 与S 是相同事务集合的两个调度.S 和S

13、 称为 观察等价观察等价当且仅当满足下列三个条件:1.对每个数据项Q,如果在调度S中事务Ti 读到Q 的初始值,则在调度S 中事务Ti 也必须读到Q 的初始值.2.对每个数据项Q,如果在调度S中事务Ti 执行了read(Q),而该值是由事务Tj 产生的,则在调度S 中事务Ti 也必须读到由事务Tj 产生的Q值.3.对每个数据项Q,在调度S中执行最后一条write(Q)的事务在调度S 中也必须执行最后一条write(Q).显然,观察等价也是纯粹基于read和write 的.Silberschatz,Korth and Sudarshan15.20Database System Concepts观

14、察可串行化观察可串行化(续续)n如果调度S 观察等价于一个串行调度,则称之为观察可串行化的观察可串行化的.n每个冲突可串行化的调度也是观察可串行化的.n教材中的Schedule 9 观察可串行化但非冲突可串行化的调度.n每个观察可串行化而非冲突可串行化的调度必有盲写盲写(blind write),即未执行读操作.Silberschatz,Korth and Sudarshan15.21Database System Concepts可串行化的其他概念可串行化的其他概念n教材中的Schedule 8 可产生与串行调度相同的结果,但两者既不是冲突等价的也不是观察等价的.n确定这种等价性需要分析读写

15、之外的操作.Silberschatz,Korth and Sudarshan15.22Database System Concepts可恢复性可恢复性n可恢复调度可恢复调度 若事务Tj 读事务Ti 先前写过的数据项,则的Ti 提交操作出现在Tj 的提交操作之前.n下列调度(Schedule 11)不是可恢复的,如果T9 在读操作后立即提交n如果T8 夭折,T9 则读了一个数据库的不一致状态(并可能将结果显示给了用户).因此数据库必须确保调度是可恢复的.需要考虑事务失败对并发执行的事务的影响.Silberschatz,Korth and Sudarshan15.23Database System

16、 Concepts可恢复性可恢复性(续续)n级联回滚级联回滚 单个事务失败导致一系列事务回滚.考虑下列调度,其中没有事务已提交(因此该调度是可恢复的)若T10 失败,T11 和T12 也必须回滚.n导致大量工作的取消Silberschatz,Korth and Sudarshan15.24Database System Concepts可恢复性可恢复性(续续)n无级联回滚调度无级联回滚调度 不会发生级联回滚;对每一对事务Ti 与Tj,若Tj 读取Ti 先前写过的数据项,则Ti 的提交操作必须出现在Tj 的读操作之前.n每个无级联回滚调度也是可恢复的调度n有必要将调度限制为无级联回滚调度Silb

17、erschatz,Korth and Sudarshan15.25Database System Concepts隔离性的实现隔离性的实现n为保证数据库的一致性,调度必须是冲突或观察可串行化的,可恢复的,并且最好是无级联回滚的.n一次只允许一个事务执行的策略产生的都是串行调度,但并发度太差.n并发控制方案在它所允许的并发程度与带来的开销之间进行折衷.n某些方案只允许产生冲突可串行化的调度,而另一些则允许非冲突可串行化但观察可串行化的调度.Silberschatz,Korth and Sudarshan15.26Database System ConceptsSQL中的事务定义中的事务定义n数据

18、操纵语言必须包含用来说明组成事务的操作集合的构造.n在SQL标准中,事务是隐式开始的.n在SQL中事务的结束是通过:Commit work 提交当前事务并开始一个新事务.Rollback work 导致当前事务夭折.nSQL-92中的一致性级别:Serializable 缺省Repeatable readRead committedRead uncommittedSilberschatz,Korth and Sudarshan15.27Database System ConceptsSQL-92中的一致性级别中的一致性级别nSerializable 缺省级别nRepeatable read 只

19、能读已提交记录,并且对同一记录的重复读必须返回相同值(即其间不允许其他事务更新该记录).然而,事务可能不是可串行化的 它可能读到一些被另一已提交事务插入的记录.nRead committed 只能读已提交记录,但对记录的重复读可能返回不同值.nRead uncommitted 可能读到未提交的记录.较低级别的一致性对获得数据库的近似信息是有用的,如用于查询优化的统计信息.Silberschatz,Korth and Sudarshan15.28Database System Concepts检测可串行化检测可串行化n考虑事务集合T1,T2,.,Tn 的某个调度n优先图优先图 以事务为顶点的一种

20、有向图.n如果两事务Ti 和Tj 冲突并且Ti 较早存取引起冲突的数据项,则从Ti 到Tj 画弧.n可以用被存取的数据项标记弧.n例例 1xySilberschatz,Korth and Sudarshan15.29Database System Concepts调度例调度例(Schedule A)T1 T2 T3 T4 T5read(X)read(Y)read(Z)read(V)read(W)read(W)read(Y)write(Y)write(Z)read(U)read(Y)write(Y)read(Z)write(Z)read(U)write(U)Silberschatz,Korth

21、and Sudarshan15.30Database System ConceptsSchedule A的优先图的优先图T3T4T1T2Silberschatz,Korth and Sudarshan15.31Database System Concepts检测冲突可串行化检测冲突可串行化n一个调度是冲突可串行化的当且仅当它的优先图是无圈的.n存在时间复杂度阶为n2的循环检测算法,其中n 是图中顶点数.(更好的算法阶为n+e,其中e 为边数)n如果优先图是无圈的,可由该图的一个拓扑序得到可串行化序.即与图的偏序一致的线性序.例如,Schedule A的一个可串行化序可以是T5 T1 T3 T2

22、 T4.Silberschatz,Korth and Sudarshan15.32Database System Concepts拓扑排序示意图拓扑排序示意图Silberschatz,Korth and Sudarshan15.33Database System Concepts检测观察可串行化检测观察可串行化n对冲突可串行化的优先图检测必须经过修改才可用于检测观察可串行化.n检测一个调度是否观察可串行化的问题属于NP-complete问题类.因此不大可能存在一个高效算法.但是仅检测观察可串行化的某些充分条件的实用算法仍可用.Silberschatz,Korth and Sudarshan15.34Database System Concepts并发控制并发控制并发控制并发控制 vs.vs.可串行化检测可串行化检测可串行化检测可串行化检测n在调度已经执行之后再来检测它的可串行化太迟了!n目标 开发能确保可串行化的并发控制协议.一般不检查优先图;而是由协议施加约束来避免非可串行化调度.我们将在第16章学习这些协议.n检测可串行化有助于理解为什么一个并发控制协议是正确的.End of Chapter