《第8章并发控制》由会员分享，可在线阅读，更多相关《第8章并发控制（96页珍藏版）》请在金锄头文库上搜索。
1、第第8章章 并发控制并发控制Silberschatz, Korth and Sudarshan16.2Database System Concepts 3rd Edition主要内容主要内容nIntroduction to IsolationnDependency Model of IsolationnTransaction Dependency Relationsn基于锁的协议基于锁的协议n基于时间戳的协议基于时间戳的协议n基于验证的协议基于验证的协议n多粒度多粒度n多版本多版本n死锁处理死锁处理n插入与删除操作插入与删除操作n索引结构中的并发索引结构中的并发Silberschatz, Ko
2、rth and Sudarshan16.3Database System Concepts 3rd EditionIntroduction to Isolationn系统状态系统状态vs. 不变式不变式(invariant) “如果向如果向EMP 插入一个记录，相应地必须向插入一个记录，相应地必须向ZIP 插入一条记录。插入一条记录。” “如果如果EMP的一个副本被更新的一个副本被更新,其余副本也必须以同样的方式被更新。其余副本也必须以同样的方式被更新。” “如果一个程序改变了帐户余额，有关的修改必须记录在案。如果一个程序改变了帐户余额，有关的修改必须记录在案。”n如果满足所有这些不变式，如果
3、满足所有这些不变式，则则系统状态被认为是一致的系统状态被认为是一致的n通常一个状态在向另外一个新的且一致性状态转换时，通常一个状态在向另外一个新的且一致性状态转换时，可能会出现短暂的不一致可能会出现短暂的不一致n例如，例如，向向EMP 表插入一条记录，不可能使表插入一条记录，不可能使EMP 以及以及ZIP 索引的插入完全同步索引的插入完全同步n几乎任何一个涉及多个对象更新的变换，都会使它们之几乎任何一个涉及多个对象更新的变换，都会使它们之间有短暂的不一致性间有短暂的不一致性Silberschatz, Korth and Sudarshan16.4Database System Concepts
4、 3rd EditionIntroduction to Isolationn为了应付这些短暂的不一致性，为了应付这些短暂的不一致性，将多个相关将多个相关操作以组的方式形成事务，以操作以组的方式形成事务，以保持一致性的约束保持一致性的约束.一个从一致性的系统状态开始的事务，其间会导致临时一个从一致性的系统状态开始的事务，其间会导致临时的不一致状态，但是在事务结束时系统会进入一个新的一致状态的不一致状态，但是在事务结束时系统会进入一个新的一致状态n事务是一致性的单位事务是一致性的单位，这这就就是事务是事务ACID特性中特性中的的C (一致性一致性)的含义的含义n如果事务是隔离地一一在运行，那么每一
5、个事务可以知道其上一个事务所如果事务是隔离地一一在运行，那么每一个事务可以知道其上一个事务所导致的一致性状态导致的一致性状态n但是，但是， 如果多个事务并发执行，那么某些事务的输入和后续行为或许会不如果多个事务并发执行，那么某些事务的输入和后续行为或许会不一致，即使每一个隔离执行的事务都是正确的一致，即使每一个隔离执行的事务都是正确的,并发事务的执行必须加以控并发事务的执行必须加以控制以便正确的程序不会失效制以便正确的程序不会失效n这就是事务这就是事务ACID特性中特性中的的I(隔离性隔离性)的含义的含义Silberschatz, Korth and Sudarshan16.5Database
6、 System Concepts 3rd EditionIntroduction to Isolationn实现隔离最简单的方式就是一次只运行一个程序实现隔离最简单的方式就是一次只运行一个程序 (事务事务,前提是前提是:n如果所有的程序都很短小，如果所有数据可以集中存放如果所有的程序都很短小，如果所有数据可以集中存放在主存中，且如果所有的数据都由一个处理器来存取，在主存中，且如果所有的数据都由一个处理器来存取，这时没必要考虑并发来存取这时没必要考虑并发来存取这些程序可以简单地以这些程序可以简单地以顺序方式执行顺序方式执行n问题是，这些情况中包含了太多的问题是，这些情况中包含了太多的”如果如果”
7、n因此，系统必须以某种方式提供并发控制，保证隔离性，因此，系统必须以某种方式提供并发控制，保证隔离性，使之满足并发的第一法则使之满足并发的第一法则n人们已经尝试过许多种提供自动隔离的方法人们已经尝试过许多种提供自动隔离的方法n其中，一个公认可行的解决方案就是封锁其中，一个公认可行的解决方案就是封锁Silberschatz, Korth and Sudarshan16.6Database System Concepts 3rd EditionIntroduction to Isolationn对封锁方法，仍有一系列费解的问对封锁方法，仍有一系列费解的问题题n如果并发控制机制代价过高，会使得代价高
8、于收益。通如果并发控制机制代价过高，会使得代价高于收益。通常，复杂的算法实现起来和执行起来也比较复杂常，复杂的算法实现起来和执行起来也比较复杂n第二法则主张使用简单的算法第二法则主张使用简单的算法Silberschatz, Korth and Sudarshan16.7Database System Concepts 3rd EditionIntroduction to Isolationn最简单的封锁协议是给每个对象加一个锁。如果这个需要锁同时授最简单的封锁协议是给每个对象加一个锁。如果这个需要锁同时授于另外一个事务，该事务将等待这个锁被释放于另外一个事务，该事务将等待这个锁被释放n封锁是一
9、种实现串行化的机制，这样就确保任一时刻仅仅只有一个封锁是一种实现串行化的机制，这样就确保任一时刻仅仅只有一个事务在存取一个对象事务在存取一个对象n通过细化锁的粒度（锁覆盖的数据多少），可以提高并发度通过细化锁的粒度（锁覆盖的数据多少），可以提高并发度n锁的概念可以追溯到几千年以前，它是紧接着门之后的发明锁的概念可以追溯到几千年以前，它是紧接着门之后的发明n现在这个概念（思想）在操作系统领域里已经很普遍了现在这个概念（思想）在操作系统领域里已经很普遍了, 在该领域在该领域中，锁又被称为中，锁又被称为: 信号量（信号量（ semaphores），）， 管程（管程（ monitors） 临界区（临界
10、区（ critical sections ），）， 串行重用资源（串行重用资源（ serially reuseable reuseable resources ）Silberschatz, Korth and Sudarshan16.8Database System Concepts 3rd EditionIntroduction to Isolationn事务系统对并发控制的主要贡献是，进一步提炼了原有事务系统对并发控制的主要贡献是，进一步提炼了原有的这些思想，纳入了自动封锁以及把事务的这些思想，纳入了自动封锁以及把事务undo/redo 算算法同封锁算法结合起来法同封锁算法结合起来n这种方
11、法给应用程序开发者一个极简单的并发控制和异这种方法给应用程序开发者一个极简单的并发控制和异常处理的模型常处理的模型n事务处理系统自动地申请加锁并且登录日志以维护事务处理系统自动地申请加锁并且登录日志以维护ACID 特性特性n应用程序设计人员可能疏忽并发控制问题，除非存在着应用程序设计人员可能疏忽并发控制问题，除非存在着许多事务存取同一个对象而引起的性能问题许多事务存取同一个对象而引起的性能问题,所谓的热点所谓的热点（hotspots hotspots）n隔离性理论是允许自动封锁而带来的重要结果隔离性理论是允许自动封锁而带来的重要结果Silberschatz, Korth and Sudarsh
12、an16.9Database System Concepts 3rd EditionDependency Model of Isolationn理解隔离性结果最简单的方式，是根据事务的输入和输理解隔离性结果最简单的方式，是根据事务的输入和输出来理解出来理解n事务要么读一个对象查看其状态，要么写一个对象改变事务要么读一个对象查看其状态，要么写一个对象改变对象的状态对象的状态n设想创建和消除对象只不过是改写其状态而已。以这种设想创建和消除对象只不过是改写其状态而已。以这种粗略的方式来看，事务可以看作是一连串对象的读写操粗略的方式来看，事务可以看作是一连串对象的读写操作作n两个不同事务对同一个对象的
13、读操作不会破坏一致性，两个不同事务对同一个对象的读操作不会破坏一致性，因为读操作不会改变对象的状态（假定其状态初始是一因为读操作不会改变对象的状态（假定其状态初始是一致的）致的）n因此，只有写操作有可能带来问题因此，只有写操作有可能带来问题Silberschatz, Korth and Sudarshan16.10Database System Concepts 3rd EditionDependency Model of Isolationn同一事务对同一个对象的两个写操作也不会违反同一事务对同一个对象的两个写操作也不会违反一致性，一致性， ACID特性假定事务知道它正在干什么特性假定事务知
14、道它正在干什么nACID特性假定：如果事务隔离地运行，最终会特性假定：如果事务隔离地运行，最终会正确地转换系统状态正确地转换系统状态n因此，只有两个并发事务之间同写操作有关联的因此，只有两个并发事务之间同写操作有关联的的交叉操才可能造成不一致性或是违背隔离性的交叉操才可能造成不一致性或是违背隔离性Silberschatz, Korth and Sudarshan16.11Database System Concepts 3rd EditionDependency Model of IsolationSilberschatz, Korth and Sudarshan16.12Database S
15、ystem Concepts 3rd EditionStatic vs. Dynamic AllocationSilberschatz, Korth and Sudarshan16.13Database System Concepts 3rd EditionStatic vs. Dynamic Allocationn动态分配系统中，每一个事务都被看作是一系列动态分配系统中，每一个事务都被看作是一系列的行为动作而不是输入输出集的行为动作而不是输入输出集n每个动作的请求都在其出现时按需调度。当一个每个动作的请求都在其出现时按需调度。当一个动作存取一个特定的对象时，对象被动态地分配动作存取一个特定的
16、对象时，对象被动态地分配给事务给事务n例如，只有银行帐户记录和其它的一些特别的事例如，只有银行帐户记录和其它的一些特别的事务将要存取的记录分配给该事务务将要存取的记录分配给该事务, 出纳员才能运出纳员才能运行一个银行事务行一个银行事务n这样针对不同帐户的事务可以并发地且隔离地执这样针对不同帐户的事务可以并发地且隔离地执行行Silberschatz, Korth and Sudarshan16.14Database System Concepts 3rd EditionTransaction Dependency Relationsn图中显示了两个在对象图中显示了两个在对象e 上的事务上的事务T
17、1 和和T2 ，所可能有，所可能有的三种读写执行序列操作的三种读写执行序列操作READ-WRITE, WRITE-READ, WRITE-WRITEn没有没有READ-READ 依赖，因为读同一个版本的多个事依赖，因为读同一个版本的多个事务不会产生对另外一个版本的依赖务不会产生对另外一个版本的依赖Silberschatz, Korth and Sudarshan16.15Database System Concepts 3rd EditionTransaction Dependency Relationsn一个依赖图可以看作一个时间序列一个依赖图可以看作一个时间序列:如果事务如果事务T1 到事
18、务到事务T2 有一条边，那么有一条边，那么T1 访问的对象随后会被访问的对象随后会被T2 访访问，并且这些访问中至少有一个产生一个新的版本问，并且这些访问中至少有一个产生一个新的版本在这种意义上，在这种意义上， 在这种意义上，在这种意义上，T1 在在 T2之前运行之前运行在事务的纯顺序执行之中，在事务的纯顺序执行之中， T1运行结束，再运行运行结束，再运行T2 T结束，所有的结束，所有的依赖箭头都是从依赖箭头都是从T1 指向指向T2 n隔离定理的主要结论是：任何一个没有环的依赖图都暗示了隔离定理的主要结论是：任何一个没有环的依赖图都暗示了事务的一种隔离执行方式事务的一种隔离执行方式Silber
19、schatz, Korth and Sudarshan16.16Database System Concepts 3rd EditionThe Three BadThe Three BadTransaction DependenciesTransaction Dependenciesn一个令人惊奇的结论是：这三种不一致的基本形式覆盖了所一个令人惊奇的结论是：这三种不一致的基本形式覆盖了所有的情况，如果他们可以被防止发生，那将不会有并发异常，有的情况，如果他们可以被防止发生，那将不会有并发异常，事务将表现为隔离运行的状态事务将表现为隔离运行的状态Silberschatz, Korth and S
20、udarshan16.17Database System Concepts 3rd EditionFormal Model of Isolationn为了更精确地描述并发和恢复的问题，需要一个为了更精确地描述并发和恢复的问题，需要一个形式化的模型。因为，这些问题是复杂而又微妙形式化的模型。因为，这些问题是复杂而又微妙的，的，而而形式化有助于摆脱描述形式化有助于摆脱描述问题问题n“隔离性隔离性”的几种等价定义的几种等价定义直观定义直观定义:依据用户事务特性，直观定义是为依据用户事务特性，直观定义是为了方便了方便应用程序设应用程序设计人员和用户用来描述系统的行为计人员和用户用来描述系统的行为形式形
21、式化定义化定义:依据系统执行的过程和依赖图，依据系统执行的过程和依赖图，形式形式化定义是为化定义是为了了陈述和证明隔离性的性质。陈述和证明隔离性的性质。操作上的定义操作上的定义:依据封锁协议，操作上的定义是为依据封锁协议，操作上的定义是为了了用来指导系用来指导系统的实现。统的实现。n下面下面将要对冲突可串行性作形式化描述，将要对冲突可串行性作形式化描述，给出给出严严格定义格定义Silberschatz, Korth and Sudarshan16.18Database System Concepts 3rd Edition插曲插曲:画的圆没有说的圆圆画的圆没有说的圆圆n把想明白的事情把想明白的
22、事情表达表达清楚是作科研的基本功清楚是作科研的基本功,下面是下面是从从Let开始开始的一种下定义的方法。的一种下定义的方法。n例如例如:圆的定义圆的定义定义定义1:右边的图形称为圆右边的图形称为圆(通俗，通俗，但但不及格不及格)定义定义2:到一点的距离相等的轨迹称为圆到一点的距离相等的轨迹称为圆(及格及格)定义定义3:在一个平面上到一点的距离相等的轨迹称为圆在一个平面上到一点的距离相等的轨迹称为圆(良良)定义定义4:Let O be a point over planet P, R = 0, and d(x, y) be the distance between points x and y.
23、Then the set C=x | x in P , d(x,O)=R is said to be the circle with center O and radius R. (信息完整信息完整,严格规范严格规范,所以所以:优优)n严格定义好处严格定义好处:有了符号体系（模型），为后续研究奠定基础有了符号体系（模型），为后续研究奠定基础Silberschatz, Korth and Sudarshan16.19Database System Concepts 3rd EditionFormal Model of Isolationn隔离性隔离性(用户定义用户定义1):n事务处理系统可以并发
24、地执行事务，但它的结果事务处理系统可以并发地执行事务，但它的结果如同顺序执行一样。就应用程序而言，事务好象如同顺序执行一样。就应用程序而言，事务好象是在没有并发的情况下运行；事务的确切执行顺是在没有并发的情况下运行；事务的确切执行顺序是由系统控制的，系统行为等价于事务的某种序是由系统控制的，系统行为等价于事务的某种顺序执行，其造成的表面现象是一个事务执行完顺序执行，其造成的表面现象是一个事务执行完毕后，下一个事务才开始执行毕后，下一个事务才开始执行Silberschatz, Korth and Sudarshan16.20Database System Concepts 3rd Edition
25、Formal Model of Isolationn隔离性隔离性(用户定义用户定义2)：这是更为程序化的定义，称：这是更为程序化的定义，称事务事务T与其它事务是隔离的，如果：与其它事务是隔离的，如果：（0） T不会重写其它事务的脏数据不会重写其它事务的脏数据（1） T所写的数据，在所写的数据，在T提交（提交（COMMIT WORK ）之前，不会被其它事）之前，不会被其它事务读或者写务读或者写（2） T不读脏数据不读脏数据（3）在）在T提交之前，其它事务不会写提交之前，其它事务不会写T所要读的数据所要读的数据条件条件(0) 和和 (1)排除了丢失修改排除了丢失修改, (2) 防止了读脏数据防止了
26、读脏数据 (3)防止了不可重复防止了不可重复读读n用用Bernstein, Hadzilacos, Goodman1987,p.36 的记法，定义的记法，定义1是是SR ，定义，定义2是两阶段封锁（是两阶段封锁（ 2PL）n SR 2PL ：一些隔离性方法比这里描述的封锁机制更具一般性一些隔离性方法比这里描述的封锁机制更具一般性Silberschatz, Korth and Sudarshan16.21Database System Concepts 3rd EditionFormal Model: Actions and TransactionsSilberschatz, Korth and
27、 Sudarshan16.22Database System Concepts 3rd EditionFormal Model: Simple Transactionn系统支持系统支持对象上的动作对象上的动作READ，WRITE ，XLOCK ，SLOCK ，UNLOCK三个一般性的动作三个一般性的动作 BEGIN ，COMMIT，ROLLBACKn一个简化事务是由一个简化事务是由READ，WRITE， XLOCK，SLOCK，UNLOCK 等动作组成的等动作组成的Silberschatz, Korth and Sudarshan16.23Database System Concepts 3r
28、d EditionLocks Cover Actions(10/21)Silberschatz, Korth and Sudarshan16.24Database System Concepts 3rd EditionWell Formed and Two-PhasedWell Formed and Two-PhasedTransactionsTransactionsSilberschatz, Korth and Sudarshan16.25Database System Concepts 3rd EditionWell Formed and Two-PhasedWell Formed and
29、 Two-PhasedTransactionsTransactionsSilberschatz, Korth and Sudarshan16.26Database System Concepts 3rd EditionTransaction Historyn一组事务的所有动作序列，在保持各自顺序的情况下，一组事务的所有动作序列，在保持各自顺序的情况下，归并成的一个单一序列，我们称之为这组事务的一个归并成的一个单一序列，我们称之为这组事务的一个调调度度n最简单的调度是首先运行一个事务的所有动作，然后再最简单的调度是首先运行一个事务的所有动作，然后再运行另外一个事务的所有动作，如此一直下去，这样的
30、运行另外一个事务的所有动作，如此一直下去，这样的“一次一个事务一次一个事务”的调度称为的调度称为串行调度串行调度(serial history)n调度的定义暗指了每个动作作为对象状态的一个调度的定义暗指了每个动作作为对象状态的一个ACID 转转换：即每个动作是当作一个换：即每个动作是当作一个ACID 步骤来执行的步骤来执行的n下面的问题是，对给定的一组下面的问题是，对给定的一组ACID 动作，如何既能并发动作，如何既能并发执行这些动作，而又保持事务的隔离性执行这些动作，而又保持事务的隔离性Silberschatz, Korth and Sudarshan16.27Database System
31、 Concepts 3rd EditionSummary of Definitionsn事务是在对象上的事务是在对象上的 READ，WRITE ，SLOCK和和XLOCK 动作的序列，它以动作的序列，它以COMMIT 或或 ROLLBACK动作结尾动作结尾n含含COMMIT或或ROLLBACK的一般事务可以转化成为简化的一般事务可以转化成为简化事务，它只含事务，它只含READ, WRITE,SLOCK,XLOCK和和 UNLOCK动作动作n如果事务的每个如果事务的每个READ，WRITE，UNLOCK 都被相应的都被相应的锁覆盖，且所有的锁都是在事务结束时释放，那么我们锁覆盖，且所有的锁都是在
32、事务结束时释放，那么我们称这样的事务是称这样的事务是规范的规范的n如果一个事务可以分成两个阶段，只请求封锁的扩展阶如果一个事务可以分成两个阶段，只请求封锁的扩展阶段，和只释放封锁的收缩阶段，那么我们称之为段，和只释放封锁的收缩阶段，那么我们称之为两阶段两阶段的事务的事务Silberschatz, Korth and Sudarshan16.28Database System Concepts 3rd Edition基于锁的协议基于锁的协议Silberschatz, Korth and Sudarshan16.29Database System Concepts 3rd Edition基于锁的协
33、议基于锁的协议Silberschatz, Korth and Sudarshan16.30Database System Concepts 3rd Edition基于锁的协议基于锁的协议n锁兼容性矩阵锁兼容性矩阵n如果事务对某数据项的锁请求与其他事务在该数据项上如果事务对某数据项的锁请求与其他事务在该数据项上已有的锁兼容已有的锁兼容, 则请求被批准则请求被批准n任意数目的事务可对同一数据持有共享锁任意数目的事务可对同一数据持有共享锁; 但若一事务但若一事务对某数据持有排他锁对某数据持有排他锁, 则其他事务不得持有该数据上的则其他事务不得持有该数据上的任何锁任何锁n若不能授予锁若不能授予锁, 则
34、使请求事务等待持有不兼容锁的所有则使请求事务等待持有不兼容锁的所有其他事务释放锁其他事务释放锁. 然后才可授予锁然后才可授予锁Silberschatz, Korth and Sudarshan16.31Database System Concepts 3rd Edition基于锁的协议基于锁的协议n执行封锁的事务例执行封锁的事务例: T2: lock-S(A); read (A); unlock(A); lock-S(B); read (B); unlock(B); display(A+B)n上例中的封锁不足以保证可串行化上例中的封锁不足以保证可串行化 若若A和和B 在读操作之间被修改在读操作
35、之间被修改, 则显示的总和是错误的则显示的总和是错误的n锁协议锁协议是所有事务在请求与释放锁时遵守的规则集合是所有事务在请求与释放锁时遵守的规则集合n锁协议对可能出现的调度集合加以限制锁协议对可能出现的调度集合加以限制Silberschatz, Korth and Sudarshan16.32Database System Concepts 3rd Edition基于锁的协议的陷阱基于锁的协议的陷阱(死锁死锁)n考虑下面的部分调度考虑下面的部分调度nT3 和和T4 都不能继续都不能继续 执行执行lock-S(B) 使使T4 等待等待T3 释放它持有的释放它持有的B上的锁上的锁, 而执行而执行
36、lock-X(A) 使使T3 等待等待T4 释放它持有的释放它持有的A上的锁上的锁n这种情形称为死锁这种情形称为死锁n为处理死锁为处理死锁, T3 或或T4 必须回滚并释放它持有的锁必须回滚并释放它持有的锁Silberschatz, Korth and Sudarshan16.33Database System Concepts 3rd Edition基于锁的协议的陷阱基于锁的协议的陷阱(死锁死锁)n多数锁协议中都存在潜在的死锁可能性多数锁协议中都存在潜在的死锁可能性. 但为了锁机制但为了锁机制的好处的好处, 这个缺陷的引入是可以容忍的这个缺陷的引入是可以容忍的n如果并发控制管理器设计的不好还
37、可能出现如果并发控制管理器设计的不好还可能出现饿死饿死n例如例如:一个事务可能在等待给数据项加一个事务可能在等待给数据项加X-锁锁, 同时一系列其他事务在同时一系列其他事务在请求并被授予同一数据项上的请求并被授予同一数据项上的S-锁锁同一事务因死锁而被重复回滚同一事务因死锁而被重复回滚n并发控制管理器可设计成能够防止饿死并发控制管理器可设计成能够防止饿死Silberschatz, Korth and Sudarshan16.34Database System Concepts 3rd Edition两阶段锁协议两阶段锁协议 n两阶段封锁协议预备两阶段封锁协议预备: 封锁资源与获得服务的直观解释
38、封锁资源与获得服务的直观解释Silberschatz, Korth and Sudarshan16.35Database System Concepts 3rd Edition两阶段锁协议两阶段锁协议 n两阶段封锁协议预备两阶段封锁协议预备:封锁资源与获得服务的直观解释封锁资源与获得服务的直观解释Silberschatz, Korth and Sudarshan16.36Database System Concepts 3rd Edition两阶段锁协议两阶段锁协议 n两阶段封锁协议预备两阶段封锁协议预备: 封锁资源与获得服务的直观解释封锁资源与获得服务的直观解释Silberschatz, K
39、orth and Sudarshan16.37Database System Concepts 3rd Edition两阶段锁协议两阶段锁协议 n两阶段封锁协议预备两阶段封锁协议预备:封锁资源与获得服务的直观解释封锁资源与获得服务的直观解释Silberschatz, Korth and Sudarshan16.38Database System Concepts 3rd Edition两阶段锁协议两阶段锁协议 n两阶段锁不能避免死锁两阶段锁不能避免死锁n两阶段锁不能避免级联回滚两阶段锁不能避免级联回滚n但用但用严格严格(strict)两阶段锁两阶段锁的改进协议可避免的改进协议可避免: 事务必须
40、保持它的所有排他锁直至提交事务必须保持它的所有排他锁直至提交/夭折夭折n严密严密(rigorous)两阶段锁两阶段锁更加严格更加严格: 所有锁都必所有锁都必须保持到事务提交须保持到事务提交/夭折夭折,在这种协议中事务可按在这种协议中事务可按它们提交的次序串行化它们提交的次序串行化Silberschatz, Korth and Sudarshan16.39Database System Concepts 3rd Edition两阶段锁协议两阶段锁协议n存在用两阶段锁不能得到的冲突可串行化调度存在用两阶段锁不能得到的冲突可串行化调度n即即: 给定不遵守两阶段锁的事务给定不遵守两阶段锁的事务Ti,
41、可以找到使可以找到使用两阶段锁的事务用两阶段锁的事务Tj 及及Ti 与与Tj 的一个不是冲突的一个不是冲突可串行化的调度可串行化的调度n然而然而, 在缺少额外信息在缺少额外信息(如数据存取次序如数据存取次序)的情况的情况下下, 两阶段锁对冲突可串行化要求来说是必要的两阶段锁对冲突可串行化要求来说是必要的Silberschatz, Korth and Sudarshan16.40Database System Concepts 3rd Edition锁转换锁转换n带有锁转换的两阶段锁带有锁转换的两阶段锁: 第一阶段第一阶段: （趋势：扩大封锁，减少共享）（趋势：扩大封锁，减少共享） 可获得可获得
42、 lock-S可获得可获得 lock-X可转换可转换 lock-S 到到 lock-X (升级升级) 第二阶段第二阶段:（趋势：扩大共享，减少封锁）（趋势：扩大共享，减少封锁）可释放可释放 lock-S可释放可释放 lock-X可转换可转换 lock-X 到到 lock-S (降级降级)n本协议确保可串行化本协议确保可串行化, 但仍依靠程序员插入各种封锁指令但仍依靠程序员插入各种封锁指令Silberschatz, Korth and Sudarshan16.41Database System Concepts 3rd Edition锁的自动获得锁的自动获得n事务事务Ti 发出标准的读发出标准的
43、读/写指令写指令, 无需使用显式的封锁调用无需使用显式的封锁调用n操作操作read(D) 的处理如下的处理如下:(把方便留给用户，把困难留给系统） if Ti 在D上有锁 then read(D) else begin 如有必要则等待直至没有事务在如有必要则等待直至没有事务在D上有上有lock-X 授予授予Ti 在在D上的上的lock-S; read(D) endSilberschatz, Korth and Sudarshan16.42Database System Concepts 3rd Edition锁的自动获得锁的自动获得nwrite(D) 如下处理如下处理: if Ti 在在D上有
44、上有 lock-X then write(D) else begin 如有必要则等待直至没有事务在如有必要则等待直至没有事务在D上有任何锁上有任何锁, if Ti 在在D上有上有lock-S then 将将D上的锁升级到上的锁升级到 lock-X else 授予授予Ti 在在D上的上的 lock-X write(D) end;n所有锁在提交所有锁在提交/夭折之后释放夭折之后释放Silberschatz, Korth and Sudarshan16.43Database System Concepts 3rd Edition锁管理器锁管理器n锁管理器锁管理器可实现为单独的进程可实现为单独的进程,
45、 事务向它发送加锁与释事务向它发送加锁与释放锁请求放锁请求n锁管理器通过发送锁授予消息来回答锁请求锁管理器通过发送锁授予消息来回答锁请求(或死锁时或死锁时发送请事务回滚的消息发送请事务回滚的消息)n请求事务等待请求事务等待, 直至它的请求被回答直至它的请求被回答n锁管理器维护一个称为锁管理器维护一个称为锁表锁表的数据结构来记录授予的锁的数据结构来记录授予的锁和挂起的请求和挂起的请求n锁表通常实现为以被锁数据项的名字为索引的内存散列锁表通常实现为以被锁数据项的名字为索引的内存散列表表Silberschatz, Korth and Sudarshan16.44Database System Con
46、cepts 3rd Edition锁管理器锁管理器Silberschatz, Korth and Sudarshan16.45Database System Concepts 3rd Edition锁表锁表 (Hash(Hash表实现表实现表实现表实现, , 高效高效高效高效) )n黑色矩形表示已授予的锁黑色矩形表示已授予的锁, 白色白色矩形表示等待的请求矩形表示等待的请求n锁表记录授予或请求的锁的类型锁表记录授予或请求的锁的类型n新请求加入到对某数据项的请求新请求加入到对某数据项的请求队列的末尾队列的末尾, 并且如果与所有以并且如果与所有以前的锁兼容则被授予前的锁兼容则被授予n释放锁请求导致
47、请求被删除释放锁请求导致请求被删除, 并并且其后的请求被检查看看现在是且其后的请求被检查看看现在是否可以授予否可以授予n如果事务夭折如果事务夭折, 则该事务的所有则该事务的所有等待或已批准的请求都被删除等待或已批准的请求都被删除n锁管理器可能保存每个事务持有锁管理器可能保存每个事务持有的锁的列表的锁的列表, 以便对此高效地实以便对此高效地实现现Silberschatz, Korth and Sudarshan16.46Database System Concepts 3rd Edition锁表锁表 ( (HashHash表实现表实现表实现表实现, , 高效高效高效高效) )Silberscha
48、tz, Korth and Sudarshan16.47Database System Concepts 3rd Edition基于图的协议基于图的协议n基于图的协议是相对于两阶段锁协议的另一选基于图的协议是相对于两阶段锁协议的另一选择择n在所有数据项集合在所有数据项集合D = d1, d2 ,., dh 上定义一上定义一个偏序个偏序(读作goes to 或先于先于)如果如果di dj 则存取则存取di 和和dj 的任何事务都必须先存取的任何事务都必须先存取di 后存取后存取dj集合集合D可视为可视为有向无圈图有向无圈图(特例为树特例为树(有根的图有根的图),表示表示数据的加工流程数据的加工流
49、程)称为数据库图称为数据库图n树协议树协议是图协议的一种简单形式是图协议的一种简单形式Silberschatz, Korth and Sudarshan16.48Database System Concepts 3rd Edition树协议树协议Silberschatz, Korth and Sudarshan16.49Database System Concepts 3rd Edition树协议树协议n树协议确保冲突可串行化且可避免死锁树协议确保冲突可串行化且可避免死锁n树协议中释放锁可比两阶段锁协议更早发生树协议中释放锁可比两阶段锁协议更早发生较短等待时间较短等待时间, 增加并发度增加并发
50、度协议无死锁协议无死锁, 不需回滚不需回滚事务的夭折仍然可能导致级联回滚事务的夭折仍然可能导致级联回滚 (教材中对此有改进方法教材中对此有改进方法)n然而然而, 在树封锁协议中在树封锁协议中, 事务可能对它不需要存取的数据项事务可能对它不需要存取的数据项加锁加锁(可能诛连可能诛连(冤枉封锁了冤枉封锁了)太多子孙，诛九族太多子孙，诛九族)增加锁开销以及额外的等待时间增加锁开销以及额外的等待时间潜在的并发度降低潜在的并发度降低n树协议可产生两阶段锁协议不能产生的调度树协议可产生两阶段锁协议不能产生的调度, 反之亦然反之亦然.树协议与树协议与2PL没绝对的强弱，各有用武之地没绝对的强弱，各有用武之地
51、Silberschatz, Korth and Sudarshan16.50Database System Concepts 3rd Edition基于时间戳的协议基于时间戳的协议n两种时间戳，分别对事务，对数据两种时间戳，分别对事务，对数据n每个事务进入系统时被赋予一个时间戳，若一个老事务每个事务进入系统时被赋予一个时间戳，若一个老事务Ti 具有时间戳具有时间戳TS(Ti)，则一个新事务，则一个新事务Tj 被赋予时间戳被赋予时间戳TS(Tj) 使得使得TS(Ti) TS(Tj) n该协议管理并发执行该协议管理并发执行, 使得时间戳决定了串行化次序使得时间戳决定了串行化次序n为了保证这种行为为
52、了保证这种行为, 该协议为每个数据该协议为每个数据Q维护两个时间戳值维护两个时间戳值W-timestamp(Q):成功执行了成功执行了write(Q)的所有事务中的最大时间戳的所有事务中的最大时间戳R-timestamp(Q):成功执行了成功执行了read(Q)的所有事务中的最大时间戳的所有事务中的最大时间戳n注注:学习时间戳协议的方法学习时间戳协议的方法听讲课，有时不能立即反应和理解听讲课，有时不能立即反应和理解需用例子，画出时间轴，调度，需要细心体会需用例子，画出时间轴，调度，需要细心体会Silberschatz, Korth and Sudarshan16.51Database Syst
53、em Concepts 3rd Edition基于时间戳的协议基于时间戳的协议n假设事务假设事务Ti 发出了发出了read(Q) 1. 若若TS(Ti) W-timestamp(Q)，则，则Ti 需要读需要读Q 的已经的已经被写覆盖了的一个值，因此，被写覆盖了的一个值，因此， read 操作被拒绝，操作被拒绝， Ti 回滚回滚 2. 若若TS(Ti) R-timestamp(Q)，则，则read 操作执行，并操作执行，并且且R-timestamp(Q) 置为置为R-timestamp(Q) 与与TS(Ti)的的最大值最大值n时戳读法则：读旧回卷（时戳读法则：读旧回卷（Roll Back原义，电
54、影胶片卷原义，电影胶片卷回重放）回重放）Silberschatz, Korth and Sudarshan16.52Database System Concepts 3rd Edition基于时间戳的协议基于时间戳的协议n假设事务假设事务Ti 发出发出write(Q):若若TS(Ti) R-timestamp(Q), 则则Ti 要产生的要产生的Q 值是值是过去曾需要的过去曾需要的, 而系统假设该值永远不会产生而系统假设该值永远不会产生. 于是于是, write 操作被拒绝操作被拒绝, Ti 回滚回滚若若TS(Ti) W-timestamp(Q), 则则Ti 试图写一个过时试图写一个过时的的Q值
55、值,因此因此, 这个这个write 操作被拒绝操作被拒绝, Ti 回滚回滚否则否则,执行执行write 操作操作, 且且W-timestamp(Q) 置为置为TS(Ti)n时间戳写法则：写先于读或以旧盖新，否则回卷时间戳写法则：写先于读或以旧盖新，否则回卷n结论结论: 时间戳排序协议可确保任何冲突的时间戳排序协议可确保任何冲突的read 和和write 操作都能按照时间戳序执行操作都能按照时间戳序执行Silberschatz, Korth and Sudarshan16.53Database System Concepts 3rd Edition协议例协议例n针对若干数据项的、时间戳为针对若干
56、数据项的、时间戳为1, 2, 3, 4, 5的事务的一个部分调度的事务的一个部分调度Silberschatz, Korth and Sudarshan16.54Database System Concepts 3rd Edition时间戳排序协议的正确性时间戳排序协议的正确性n时间戳保证了可串行性，有绝对时间戳，等候图不会有循环（时间戳保证了可串行性，有绝对时间戳，等候图不会有循环（ 按按资历分配资源）资历分配资源） n因此因此, 优先图中没有圈优先图中没有圈n时间戳协议确保没有死锁时间戳协议确保没有死锁, 因为没有事务会等待因为没有事务会等待n但是但是, 调度可能导致级联回滚调度可能导致级联
57、回滚, 并且甚至可能不可恢复并且甚至可能不可恢复n先生没有晋升成功，后生晋升后也要作废先生没有晋升成功，后生晋升后也要作废较小时间戳事务较大时间戳事务Silberschatz, Korth and Sudarshan16.55Database System Concepts 3rd Edition可恢复性与避免级联回滚可恢复性与避免级联回滚n时间戳排序协议的问题时间戳排序协议的问题:假如假如Ti 夭折，但夭折，但Tj 已经读了已经读了Ti 所写的一个数据项所写的一个数据项则则Tj 必须夭折，若必须夭折，若Tj 已被允许较早提交，则该调度是不可恢复已被允许较早提交，则该调度是不可恢复的的进一步，
58、任何读了进一步，任何读了Tj 所写的数据项的事务必须夭折所写的数据项的事务必须夭折这可能导致级联回滚：即一个回滚链这可能导致级联回滚：即一个回滚链Silberschatz, Korth and Sudarshan16.56Database System Concepts 3rd Edition可恢复性与避免级联回滚可恢复性与避免级联回滚n解决方案解决方案:1.事务事务到到最后才写最后才写(at the end of its processing)2.所有写动作作为一个原子（定先进所有写动作作为一个原子（定先进和和发奖金一起写盘）发奖金一起写盘）3.事务中止后重新开始，且重新给时间戳事务中止后重
59、新开始，且重新给时间戳Silberschatz, Korth and Sudarshan16.57Database System Concepts 3rd EditionThomas写规则写规则n是时间戳排序协议的修正版本，其中过时是时间戳排序协议的修正版本，其中过时write 操作在操作在某些情况下可以忽略某些情况下可以忽略n当当Ti 试图写数据项试图写数据项Q, 若若 TS(Ti) W-timestamp(Q), 则则Ti 正试图写一个过时的正试图写一个过时的Q值。因此，不是按时间戳排序值。因此，不是按时间戳排序协议要求的那样回滚协议要求的那样回滚Ti，这个，这个write 操作可以忽略（
60、其操作可以忽略（其他情况下此协议与按时间戳排序协议相同）他情况下此协议与按时间戳排序协议相同）nThomas写规则允许更多的潜在并发性，但不同于前面写规则允许更多的潜在并发性，但不同于前面的协议，它允许做某些非冲突可串行化但是视图可串行的协议，它允许做某些非冲突可串行化但是视图可串行化的调度（即最终结果等价于某个串行调度）化的调度（即最终结果等价于某个串行调度）Silberschatz, Korth and Sudarshan16.58Database System Concepts 3rd Edition基于有效性检查的协议基于有效性检查的协议n思路思路:大胆先做，做了再验证，即不要坐而论道
61、，迟迟不大胆先做，做了再验证，即不要坐而论道，迟迟不动动n事务事务Ti 的执行分成三个阶段的执行分成三个阶段: 1. 读与执行阶段读与执行阶段: 事务事务Ti 的的write操作只写到临时局部变操作只写到临时局部变量量 2. 有效性检查阶段有效性检查阶段: 事务事务Ti 执行执行“有效性检查有效性检查”来决定局来决定局部变量的值是否可以写到数据库而不违反可串行化部变量的值是否可以写到数据库而不违反可串行化 3. 写阶段写阶段: 若若Ti 通过有效性检查通过有效性检查, 则更新数据库则更新数据库; 否则否则Ti 回滚回滚Silberschatz, Korth and Sudarshan16.59
62、Database System Concepts 3rd Edition基于有效性检查的协议基于有效性检查的协议n并发执行的各事务的三个阶段可以交叉并发执行的各事务的三个阶段可以交叉, 但是每但是每个事务必须按顺序通过三个阶段个事务必须按顺序通过三个阶段n也称为也称为乐观并发控制乐观并发控制，因为事务执行时完全寄，因为事务执行时完全寄希望于在有效性检查时一切都好希望于在有效性检查时一切都好n乐观控制，适合乐观控制，适合”成多败少成多败少”的场合的场合Silberschatz, Korth and Sudarshan16.60Database System Concepts 3rd Editio
63、n基于有效性检查的协议基于有效性检查的协议n每个事务每个事务Ti 有三个时间戳有三个时间戳-Start(Ti): Ti 开始执行的时间开始执行的时间-Validation(Ti): Ti 进入有效性检查阶段的时间进入有效性检查阶段的时间- Finish(Ti): Ti 完成写阶段的时间完成写阶段的时间n为了增加并发性，可串行化次序由有效性检查时的时间为了增加并发性，可串行化次序由有效性检查时的时间戳次序决定戳次序决定, 因此因此TS(Ti) 被赋予被赋予 Validation(Ti)的值的值n如果冲突的概率较小如果冲突的概率较小, 本协议很有用本协议很有用, 能带来更大程度能带来更大程度的并发
64、性的并发性, 这是因为可串行化次序不是预先决定的这是因为可串行化次序不是预先决定的, 只只有相对较少的事务会被回滚有相对较少的事务会被回滚Silberschatz, Korth and Sudarshan16.61Database System Concepts 3rd Edition事务事务Tj 的有效性检查的有效性检查n若对所有满足若对所有满足TS (Ti) TS (Tj)的的Ti 都有下列任一条件都有下列任一条件成立成立:finish(Ti) start(Tj) start(Tj) finish(Ti) validation(Tj) 并且并且Ti 所写的数据项集所写的数据项集合与合与Tj
65、 所读的数据项集合不相交所读的数据项集合不相交 则通过有效性检查则通过有效性检查, Tj 可以提交可以提交;否则有效性检查失败否则有效性检查失败, Tj 夭折夭折n正确性说明正确性说明: 要么满足第一个条件要么满足第一个条件, 没有重叠的执行没有重叠的执行; 要要么满足第二个条件么满足第二个条件, 并且并且 1. Tj 的写不影响的写不影响Ti 的读的读, 因为它们发生在因为它们发生在Ti 开始读操作之后开始读操作之后 2. Ti 的写不影响的写不影响Tj 的读的读, 因为因为Tj 不读不读Ti 所写的任何数据项所写的任何数据项Silberschatz, Korth and Sudarshan
66、16.62Database System Concepts 3rd Edition事务事务Tj 的有效性检查的有效性检查Silberschatz, Korth and Sudarshan16.63Database System Concepts 3rd Edition有效性检查所产生的调度有效性检查所产生的调度T14T15read(B)read(B)B:- B-50read(A)A:- A+50read(A)(validate)display (A+B)(validate)write (B)write (A)Silberschatz, Korth and Sudarshan16.64Datab
67、ase System Concepts 3rd Edition多粒度多粒度n允许数据项具有不同大小，从而定义一个数据粒度层次允许数据项具有不同大小，从而定义一个数据粒度层次, 小粒度嵌入在大粒度中小粒度嵌入在大粒度中n可图示为一棵树可图示为一棵树C (勿与树封锁协议混淆勿与树封锁协议混淆)n当一事务对树中节点当一事务对树中节点显式显式加锁，它也加锁，它也隐含地隐含地对该节点的对该节点的所有后裔加了同样的锁所有后裔加了同样的锁n锁粒度锁粒度 (封锁发生的树层次封锁发生的树层次):细粒度细粒度 (树中较低层树中较低层): 高并发度高并发度, 高锁开销高锁开销粗粒度粗粒度 (树中较高层树中较高层):
68、 低锁开销低锁开销, 低并发度低并发度Silberschatz, Korth and Sudarshan16.65Database System Concepts 3rd Edition多粒度多粒度Silberschatz, Korth and Sudarshan16.66Database System Concepts 3rd Edition粒度层次粒度层次:例例n例中最高层是整个数据库例中最高层是整个数据库n低层依次是低层依次是area, file 和和recordSilberschatz, Korth and Sudarshan16.67Database System Concepts
69、3rd Edition意向锁方式意向锁方式n除了除了S 和和X 锁方式锁方式, 还有另外三种多粒度的锁方还有另外三种多粒度的锁方式式:意向共享意向共享 (IS): 表示在树的低层有显式加共享锁表示在树的低层有显式加共享锁意向排他意向排他 (IX):表示在树的低层有显式加排他或共享表示在树的低层有显式加排他或共享锁锁共享及意向排他共享及意向排他 (SIX): 以该节点为根的子树被显式以该节点为根的子树被显式加共享锁加共享锁, 并且在子树的低层显式加排他锁并且在子树的低层显式加排他锁n意向锁允许高层节点按意向锁允许高层节点按S或或X方式加锁而不需检方式加锁而不需检查所有后裔节点查所有后裔节点Sil
70、berschatz, Korth and Sudarshan16.68Database System Concepts 3rd Edition意向锁方式的兼容性矩阵意向锁方式的兼容性矩阵n对所有锁方式的兼容性矩阵如下对所有锁方式的兼容性矩阵如下: ISIXSS IXX ISIXSS IXX Silberschatz, Korth and Sudarshan16.69Database System Concepts 3rd Edition多粒度锁方案多粒度锁方案n事务事务Ti 可以根据下列规则来锁一个节点可以根据下列规则来锁一个节点Q: 1. 必须遵守锁兼容性矩阵必须遵守锁兼容性矩阵 2. 树的
71、根必须首先加锁树的根必须首先加锁, 并且可以任何方式加锁并且可以任何方式加锁 3. 仅当节点仅当节点Q 的父节点当前被的父节点当前被Ti 以以IX或或IS方式加锁时方式加锁时, Q 才可被才可被Ti 以以S或或IS方式加锁方式加锁 4. 仅当节点仅当节点Q 的父节点当前被的父节点当前被Ti 以以IX或或SIX方式加锁时方式加锁时, Q 才可以被才可以被Ti 以以X, SIX, 或或IX方式加锁方式加锁 5. 仅当仅当Ti 先前没有对任何节点开锁时才可以对一个节点加锁先前没有对任何节点开锁时才可以对一个节点加锁(即即, Ti 是是两阶段的两阶段的) 6. 仅当仅当Q 的子女没有正被的子女没有正被
72、Ti 加锁时加锁时, Ti 才可以对节点才可以对节点Q 开锁开锁n注意锁是按从根到叶次序获得的注意锁是按从根到叶次序获得的, 但是按从叶到根次序释放但是按从叶到根次序释放Silberschatz, Korth and Sudarshan16.70Database System Concepts 3rd Edition多粒度锁方案多粒度锁方案Silberschatz, Korth and Sudarshan16.71Database System Concepts 3rd EditionMultiversion Schemesn思路思路:Multiversion schemes keep old
73、 versions of data item to increase concurrency 保持数据项的保持数据项的旧版本来加强并发性旧版本来加强并发性Multiversion Timestamp Ordering多版本时间戳多版本时间戳Multiversion Two-Phase Locking 多版本多版本2PLEach successful write results in the creation of a new version of the data item written 每次写成每次写成功，则创一新版本功，则创一新版本Use timestamps to label vers
74、ions 用时间戳标识用时间戳标识新版本新版本Silberschatz, Korth and Sudarshan16.72Database System Concepts 3rd EditionMultiversion Schemesn直观例子直观例子: 申请课题时，多人共改一份申请书，希望并申请课题时，多人共改一份申请书，希望并发而少错发而少错n最麻烦是误以旧压新，解决方法用多版本时间戳最麻烦是误以旧压新，解决方法用多版本时间戳n方法方法1 :以文件为粒度，以文件为粒度， 文件名称文件名称: application09057A.docn问题问题: 能区分新旧，但并发度小能区分新旧，但并发度小
75、n方法方法2： 减小粒度，加大并发，逻辑上以段落为粒度减小粒度，加大并发，逻辑上以段落为粒度（物理上仍然是（物理上仍然是DOC)，每段上规定修改人次序，有时，每段上规定修改人次序，有时间戳表，依次送审（多文件多线索）如：间戳表，依次送审（多文件多线索）如：n张张: “最后更新最后更新1999-05-17-16:25” （时间戳）（时间戳）n李李:Silberschatz, Korth and Sudarshan16.73Database System Concepts 3rd EditionMultiversion SchemesnWhen a read(Q) operation is iss
76、ued, select an appropriate version of Q based on the timestamp of the transaction, and return the value of the selected version.n读时读时,选用选用Q 的的合适的新版本（根据事务时间戳）合适的新版本（根据事务时间戳） nreads never have to wait as an appropriate version is returned immediatelyn由于可以直接得到适当的版本，所以由于可以直接得到适当的版本，所以reads 不不需等待需等待Silbe
77、rschatz, Korth and Sudarshan16.74Database System Concepts 3rd EditionMultiversion Timestamp OrderingnEach data item Q has a sequence of versions nEach version Qk 有三要素有三要素: 何值何值, 何时写何时写,何时读何时读Content - the value of version QkW-timestamp(Qk) - timestamp of the transaction that created (wrote) version
78、Qk写时间戳写时间戳R-timestamp(Qk) - largest timestamp of a transaction that successfully read version Qk最后最后被读时间戳被读时间戳Silberschatz, Korth and Sudarshan16.75Database System Concepts 3rd EditionMultiversion Timestamp Orderingnwhen a transaction Ti creates a new version Qk of Q, Qks W-timestamp and R-timestamp
79、 are initialized to TS(Ti).n新建时，保证三戳一致新建时，保证三戳一致nR-timestamp of Qk is updated whenever a transaction Tj reads Qk, and TS(Tj) R-timestamp(Qk) n被读后被读后R-timestamp 与时俱进与时俱进Silberschatz, Korth and Sudarshan16.76Database System Concepts 3rd EditionMultiversion Timestamp Ordering(10/26)nThe multiversion ti
80、mestamp scheme presented next ensures serializability 下列多版本时间戳协议保证可串行性下列多版本时间戳协议保证可串行性nSuppose that transaction Ti issues a read(Q) or write(Q) operation. nLet Qk denote the version of Q whose write timestamp is the largest write timestamp less than or equal to TS(Ti) 1. If transaction Ti issues a r
81、ead(Q), then the value returned is the content of version Qk 2. If transaction Ti issues a write(Q), and if TS(Ti) R-timestamp(Qk), then transaction Ti is rolled back 3. Otherwise, if TS(Ti) = W-timestamp(Qk), the contents of Qk are overwritten 4. Otherwise a new version of Q is createdSilberschatz,
82、 Korth and Sudarshan16.77Database System Concepts 3rd EditionMultiversion Timestamp OrderingnReads always succeed; a write by Ti is rejected if some other transaction Tj that (in the serialization order defined by the timestamp values) should read Tis write, has already read a version created by a t
83、ransaction older than Ti.Silberschatz, Korth and Sudarshan16.78Database System Concepts 3rd EditionMultiversion Two-Phase LockingnDifferentiates between read-only transactions and update transactions 即只读事务和更新事务有区别即只读事务和更新事务有区别（更新修订先读后写）（更新修订先读后写）nUpdate transactions 获得读写锁，直到最后才释放获得读写锁，直到最后才释放即严格即严格2
84、PL成功的成功的write产生新版本产生新版本版本号由版本号由 ts-counter递增计算递增计算nRead-only transactions 时间戳即时间戳即ts-counter的值的值Silberschatz, Korth and Sudarshan16.79Database System Concepts 3rd EditionMultiversion Two-Phase LockingnWhen an update transaction wants to read a data item, it obtains a shared lock on it, and reads the
85、 latest version. 更新事务读数据时，共享锁之，读其最更新事务读数据时，共享锁之，读其最新版本新版本, 防止读半被写防止读半被写nWhen it wants to write an item, it obtains X lock on; it then creates a new version of the item and sets this versions timestamp to .更新事务想写数更新事务想写数据时，排他锁之，建立新版本，把其时间戳改为据时，排他锁之，建立新版本，把其时间戳改为 nWhen update transaction Ti completes,
86、 commit processing occurs:当更新事务完成时，进行提交当更新事务完成时，进行提交:Ti sets timestamp on the versions it has created to ts-counter + 1 版本号为版本号为ts-counter + 1Ti increments ts-counter by 1 计数器计数器 ts-counter增加增加1Silberschatz, Korth and Sudarshan16.80Database System Concepts 3rd EditionMultiversion Two-Phase Locking n
87、Read-only transactions that start after Ti increments ts-counter will see the values updated by Ti 后面的其它只读事务只看见更新后的数据后面的其它只读事务只看见更新后的数据nRead-only transactions that start before Ti increments the ts-counter will see the value before the updates by Ti. 之前的其它只读事务可以看之前的其它只读事务可以看到更新提交前的数据到更新提交前的数据nOnly s
88、erializable schedules are produced 因此只产因此只产生可串行的调度生可串行的调度Silberschatz, Korth and Sudarshan16.81Database System Concepts 3rd Edition死锁处理死锁处理n考虑下列两个事务考虑下列两个事务: T1: write (X) T2: write(Y) write(Y) write(X)n有死锁的调度有死锁的调度T1T2lock-X on Xwrite (X) lock-X on Ywrite (Y) wait for lock-X on Xwait for lock-X on
89、YSilberschatz, Korth and Sudarshan16.82Database System Concepts 3rd Edition死锁处理死锁处理n如果有一个事务集合使得集合中的每个事务都在等待集如果有一个事务集合使得集合中的每个事务都在等待集合中的另一个事务合中的另一个事务, 则系统死锁则系统死锁n死锁预防死锁预防协议确保系统永远不会进入死锁状态协议确保系统永远不会进入死锁状态. 一些预一些预防策略如下防策略如下:要求每个事务在开始执行为其所有数据项加锁要求每个事务在开始执行为其所有数据项加锁 (预声明预声明),即每个即每个事务锁定所需资源才开始事务锁定所需资源才开始施加
90、所有数据项上的偏序施加所有数据项上的偏序, 并要求一个事务只能按偏序指定的并要求一个事务只能按偏序指定的次序锁数据项次序锁数据项 (基于图的协议基于图的协议)直观解释直观解释:修房子不要边施工，修房子不要边施工， 边申请地皮、水、电、气边申请地皮、水、电、气Silberschatz, Korth and Sudarshan16.83Database System Concepts 3rd Edition更多死锁预防策略更多死锁预防策略n下列方案仅为死锁预防目的使用事务时间戳下列方案仅为死锁预防目的使用事务时间戳n等待等待-死亡死亡方案方案 非抢占式非抢占式老事务可能等待年轻事务释放数据项老事务
91、可能等待年轻事务释放数据项. 年轻事务永远不会等待年轻事务永远不会等待老事务老事务, 而是回滚而是回滚.一个事务可能在获得所需数据项之前死亡若干次一个事务可能在获得所需数据项之前死亡若干次n击伤击伤-等待等待方案方案 抢占式抢占式老事务击伤老事务击伤 (强制回滚强制回滚)年轻事务而不是等待它年轻事务而不是等待它年轻事务可能等待老事务年轻事务可能等待老事务可能比等待可能比等待-死亡方案有较少的回滚死亡方案有较少的回滚n在在wait-die 和和wound-wait 方案中方案中, 回滚的事务重启动回滚的事务重启动时带有原来的时间戳时带有原来的时间戳. 老事务因此具有对新事务的优先老事务因此具有对
92、新事务的优先级级, 故避免了饿死故避免了饿死Silberschatz, Korth and Sudarshan16.84Database System Concepts 3rd Edition死锁预防死锁预防n基于超时的方案基于超时的方案（不耐烦法）（不耐烦法）事务对一个锁只等待一个指定的时间量事务对一个锁只等待一个指定的时间量. 此后此后, 等待超等待超时时, 事务回滚事务回滚.因此死锁是不可能的因此死锁是不可能的实现简单，但可能有饿死实现简单，但可能有饿死. 另外难以确定合适的超时另外难以确定合适的超时间隔间隔Silberschatz, Korth and Sudarshan16.85Da
93、tabase System Concepts 3rd Edition死锁检测死锁检测n死锁可用死锁可用等待图等待图描述描述, 即一个二元组即一个二元组G = (V,E), V 是顶点集合是顶点集合 (即系统中的所有事务即系统中的所有事务)E 是边的集合是边的集合; 其中每个元素是一有序对其中每个元素是一有序对Ti Tj. n若若Ti Tj 属于属于E, 则存在从则存在从Ti 到到Tj 的有向边的有向边, 意意味着味着Ti 等待等待Tj 释放数据项释放数据项n当当Ti 请求一个正被请求一个正被Tj 持有的数据项时持有的数据项时, 边边Ti Tj 被插入到等待图中被插入到等待图中. 仅当仅当Tj
94、不再持有不再持有Ti 所需的数所需的数据项时据项时, 这条边才被删除这条边才被删除n系统处于死锁状态当且仅当等待图有圈系统处于死锁状态当且仅当等待图有圈. 必须必须周期性地调用死锁检测算法来查找圈周期性地调用死锁检测算法来查找圈Silberschatz, Korth and Sudarshan16.86Database System Concepts 3rd Edition死锁检测死锁检测没有圈的等待图没有圈的等待图有圈的等待图有圈的等待图Silberschatz, Korth and Sudarshan16.87Database System Concepts 3rd Edition死锁恢复
95、死锁恢复n当检测到死锁时当检测到死锁时某些事务必须回滚某些事务必须回滚(作为牺牲品作为牺牲品) 来打破死锁来打破死锁. 选择导选择导致最小代价的事务作为牺牲品致最小代价的事务作为牺牲品回滚回滚 决定事务回滚多远决定事务回滚多远完全回滚完全回滚: 夭折事务并重启动夭折事务并重启动更有效的是只做为打破死锁所必须的回滚更有效的是只做为打破死锁所必须的回滚若同一事务总是被选为牺牲品则发生了饿死若同一事务总是被选为牺牲品则发生了饿死. 在代价在代价因子中包括回滚次数以避免饿死因子中包括回滚次数以避免饿死Silberschatz, Korth and Sudarshan16.88Database Syst
96、em Concepts 3rd Edition插入与删除操作插入与删除操作n如果使用两阶段锁如果使用两阶段锁仅当删除元组的事务对删除元组具有排他锁时仅当删除元组的事务对删除元组具有排他锁时, delete 操作才可以被执行操作才可以被执行向数据库插入一条新元组的事务对该元组获得向数据库插入一条新元组的事务对该元组获得X锁锁n插入和删除可能导致插入和删除可能导致幻影现象幻影现象扫描关系的事务扫描关系的事务 (例如查找所有例如查找所有Perryridge的账户的账户) 和向关系中插入元组的事务和向关系中插入元组的事务 (例如在例如在 Perryridge插插入一条新元组入一条新元组)尽管不存取任何
97、共同的元组也可能冲尽管不存取任何共同的元组也可能冲突突类似于还没钓到鱼，就谈论是红烧，还是清蒸类似于还没钓到鱼，就谈论是红烧，还是清蒸Silberschatz, Korth and Sudarshan16.89Database System Concepts 3rd Edition插入与删除操作插入与删除操作n扫描关系的事务正在读指明扫描关系的事务正在读指明“关系中包含什么元组关系中包含什么元组”的信的信息息, 而插入元组的事务则更新这同一信息而插入元组的事务则更新这同一信息,因此该信息应该因此该信息应该封锁封锁.n一种解决方法一种解决方法: 将关系与一个数据项相关联将关系与一个数据项相关联,
98、 该数据项表示该数据项表示“关系中包含什么元组关系中包含什么元组”的信息的信息扫描关系的事务获得该数据项上的共享锁扫描关系的事务获得该数据项上的共享锁插入或删除元组的事务获得该数据项上的排他锁插入或删除元组的事务获得该数据项上的排他锁. (注注: 该数据项上该数据项上的锁与各个元组上的锁不冲突的锁与各个元组上的锁不冲突.)n上述协议对插入上述协议对插入/删除操作提供了较低的并发性删除操作提供了较低的并发性n索引封锁协议索引封锁协议提供了较高的并发性同时防止了幻影现象提供了较高的并发性同时防止了幻影现象, 此协议要求对某些对索引桶加锁此协议要求对某些对索引桶加锁Silberschatz, Kor
99、th and Sudarshan16.90Database System Concepts 3rd Edition索引封锁协议索引封锁协议n前提前提: 每个关系必须具有至少一个索引每个关系必须具有至少一个索引, 对关系的存取对关系的存取只能通过关系上的一个索引进行只能通过关系上的一个索引进行n执行查找的事务执行查找的事务Ti 必须以共享方式锁住它存取的所有索必须以共享方式锁住它存取的所有索引桶引桶n执行插入的事务执行插入的事务Ti 在更新所有在更新所有r 上索引之前不能向关系上索引之前不能向关系r 中插入元组中插入元组ti n执行更新的事务执行更新的事务Ti 必须对每个索引执行查找以找到所有必
100、须对每个索引执行查找以找到所有可能包含指向元组可能包含指向元组ti 的指针的索引桶的指针的索引桶, 如果已经存在的如果已经存在的话话, Ti 还必须获得它所更新的所有索引桶上的还必须获得它所更新的所有索引桶上的X锁锁.n必须遵守两阶段封锁协议必须遵守两阶段封锁协议Silberschatz, Korth and Sudarshan16.91Database System Concepts 3rd Edition弱一致性级别弱一致性级别n二级一致性二级一致性: 不同于两阶段封锁不同于两阶段封锁, S锁可以随时释放锁可以随时释放, 并并且锁可以在任何时候获得且锁可以在任何时候获得X锁必须保持到事务结
101、束锁必须保持到事务结束不能保证可串行化不能保证可串行化, 程序员必须确保不会发生错误的数据库状态程序员必须确保不会发生错误的数据库状态n游标稳定性游标稳定性: 对于读操作对于读操作, 对每条元组加对每条元组加S锁锁, 读读, 立即释放锁立即释放锁X锁持有到事务结束锁持有到事务结束二级一致性的特例二级一致性的特例Silberschatz, Korth and Sudarshan16.92Database System Concepts 3rd EditionSQL中的弱一致性级别（略）中的弱一致性级别（略）nSQL92允许非可串行化的执行允许非可串行化的执行可串行化可串行化: 默认级别默认级别可
102、重复读可重复读: 只允许读已提交记录只允许读已提交记录, 并且事务中的重复并且事务中的重复读应返回相同的值读应返回相同的值(因此读锁应该保持因此读锁应该保持)然而然而, 不需要防止幻影现象不需要防止幻影现象T1 可以看到可以看到T2插入的某些记录插入的某些记录, 但可能看不到但可能看不到T2插入的另一些记录插入的另一些记录读已提交读已提交: 与二级一致性相同与二级一致性相同, 但是多数系统将它实但是多数系统将它实现为游标稳定性现为游标稳定性读未提交读未提交: 允许读到未提交数据允许读到未提交数据Silberschatz, Korth and Sudarshan16.93Database Sys
103、tem Concepts 3rd EditionConcurrency in Index Structuresn索引结构的并发，索引结构的并发， 无方法性或思想性的要点无方法性或思想性的要点(略或自学略或自学)nIndices are unlike other database items in that their only job is to help in accessing data.nIndex-structures are typically accessed very often, much more than other database items. nTreating in
104、dex-structures like other database items leads to low concurrency. Two-phase locking on an index may result in transactions executing practically one-at-a-time.nIt is acceptable to have nonserializable concurrent access to an index as long as the accuracy of the index is maintained.nIn particular, t
105、he exact values read in an internal node of a B+-tree are irrelevant so long as we land up in the correct leaf node.nThere are index concurrency protocols where locks on internal nodes are released early, and not in a two-phase fashion.Silberschatz, Korth and Sudarshan16.94Database System Concepts 3
106、rd EditionConcurrency in Index Structures (Cont.)nExample of index concurrency protocol:nUse crabbing instead of two-phase locking on the nodes of the B+-tree, as follows. During search/insertion/deletion:First lock the root node in shared mode.After locking all required children of a node in shared
107、 mode, release the lock on the node.During insertion/deletion, upgrade leaf node locks to exclusive mode.When splitting or coalescing requires changes to a parent, lock the parent in exclusive mode.nAbove protocol can cause excessive deadlocks. Better protocols are available; see Section 16.9 for one such protocol, the B-link tree protocolEnd of ChapterSilberschatz, Korth and Sudarshan16.96Database System Concepts 3rd Edition任务任务: Derby Derby 并发控制实现分析并发控制实现分析n参考:Derby v10 source code
