分布式数据库中的并发控制.ppt

《分布式数据库中的并发控制.ppt》由会员分享，可在线阅读，更多相关《分布式数据库中的并发控制.ppt（110页珍藏版）》请在三一办公上搜索。

1、分布式数据库系统及其应用,并发控制的概念和理论分布式数据库系统并发控制的封锁技术分布式数据库系统中的死锁处理分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的多版本技术分布式数据库系统并发控制的乐观方法,分布式数据库中的并发控制,第5章,通常，数据库总有若干个事务在运行，这些事务可能并发地存取相同的数据，称为事务的并发操作。当数据库中有多个事务并发执行时，系统必须对并发事务之间的相互作用加以控制，这是通过并发控制机制来实现的。并发控制就是负责正确协调并发事务的执行，保证这种并发的存取操作不至于破坏数据库的完整性和一致性，确保并发执行的多个事务能够正确地运行并获得正确的结果。分布式数据

2、库中的并发控制解决多个分布式事务对数据并发执行的正确性，保证数据库的完整性和一致性。比集中式并发控制更复杂。,集中式DB环境,T1T2Tn,DB(一致性约束),分布式DB环境,X,Y,Z,T1,T2,多处理器,并发执行,单处理器,非并发执行,UPDATE x,70,t6,FIND x,t2,200,t7,UPDATE x,t5,x:=x*2,t4,x:=x-30,t3,FIND x,t1,100,t0,更新事务T2,数据库中X的值,更新事务T1,时间,注：其中FIND表示从数据库中读值，UPDATE表示把值写回到数据库T1T2，结果140，T2T1,结果170，得到结果是200，显然是不对的，

3、T1在t7丢失更新操作。,并发控制问题之一：丢失更新,FIND x,t2,70,t5,UPDATE x,t4,x:=x-30,t3,FIND x,t1,100,t0,更新事务T2,数据库中A的值,更新事务T1,时间,注：在时间t5事务T2仍认为x的值是100,并发控制问题之二：不一致分析,100,t6,x:=x-10,t2,ROLLBACK,t5,FIND x,90,t4,UPDATE x,t3,FIND x,t1,100,t0,更新事务T2,数据库中A的值,更新事务T1,时间,注：事务T2依赖于事务T1的未完成更新,并发控制问题之三：依赖于未提交更新（读脏数据）,事务Ti Ti=i,i 其中

4、：i:操作符集合：Ri(x),Wi(x)U Ai,Ci Ai,Ci 是最后的操作符，只能是其一i:(冲突)操作有序执行，Ri(x)i Wi(x)或 Wi(x)i Ri(x),操作符集 读Ri(x)和写Wi(x)动作序列冲突动作 R1(A)W2(A)W1(A)W2(A)R1(A)W2(A)一个调度事务的一个操作序列称为一个调度，一般用S表示比如，S:R1(x),R2(y),W2(y),R2(x),W1(x),W2(x),T1 T21(T1)a X 5(T2)c X2(T1)X a+100 6(T2)X 2c3(T1)b Y 7(T2)d Y4(T1)Y b+100 8(T2)Y 2d,先序关系,

5、例子已知：站点1有数据X，站点2有数据Y约束：X=Y,(X站点)(Y站点)1(T1)a X 2(T1)X a+100 5(T2)c X 3(T1)b Y6(T2)X 2c 4(T1)Y b+100 7(T2)d Y 8(T2)Y 2d 初值:X=Y=0,结果:X=Y=200,调度S1,事务内事务间,令T=T1,T2,Tn 是一组事务.T上的调度 S 是具有如下顺序关系T的偏序，即S=T,T:(1)T=Ti(2)T i(3)对于任意一组冲突操作 p,q S,存在 p q 或 q p关系,并发调度定义,i=1,N,N,i=1,调度一组事务的调度必须包含这些事务的所有操作调度中某个事务的操作顺序必须

6、保持与该事务原有的顺序相同串行调度 一个事务的第一个动作是在另一个事务的最后一个动作完成后开始.即调度中事务的各个操作不会交叉,每个事务相继执行.一致性调度调度可以使得数据库从一个一致性状态转变为另一个一致性状态，则称调度为一致性调度,调度等价S1与S2等价,也就是说,对于冲突操作,Oi Oj在S1中成立,同时 Oi Oj 在S2中也成立可串行化调度如果一个调度等价于某个串行调度，则该调度称为可串行化调度。也就是说，该调度可以通过一系列非冲突动作的交换操作使其成为串行调度,例子两个事务，定义如下：T1:Read(x）x=x+10Write(x)Read(y)y=y-15Write(y)comm

7、it,T2:Read(x）x=x-20Write(x)Read(y)y=y*2Write(y)commit,五种调度：S1=R1(x),x=x+10,W1(x),R1(y),y=y-15,W1(y),C1,R2(x),x=x-20,W2(x),R2(y),y=y*2,W2(y),C2S2=R1(x),x=x+10,W1(x),R2(x),x=x-20,W2(x),R1(y),y=y-15,W1(y),C1,R2(y),y=y*2,W2(y),C2S3=R1(x),x=x+10,W1(x),R2(x),x=x-20,W2(x),R2(y),y=y*2,W2(y),C2,R1(y),y=y-15,

8、W1(y),C1S4=R2(x),x=x-20,W2(x),R2(y),y=y*2,W2(y),C2,R1(x),x=x+10,W1(x),R1(y),y=y-15,W1(y),C1S5=R2(x),x=x-20,W2(x),R1(x),x=x+10,W1(x),R2(y),y=y*2,W2(y),C2,R1(y),y=y-15,W1(y),C1,如果将事务提交延迟到两个事务操作完成之后执行，有：调度S1和S4是串行调度调度S2和S1的冲突操作具有相同的顺序，因此是等价调度；S2是可串行化调度，也是一致性调度调度S3虽是一致调度，但是它不与S1或S4等价，所以S3不是可串行化调度调度S5和S4

9、等价，所以S5是一致调度，也是可串行化调度,有以下推论：一个可串行化调度必定与某个串行调度等价，且是一致性调度一致性调度不一定是可串行化调度同一事务集几个可串行化调度，他们的结果未必相同,优先图 P(S),调度 S 的优先图是一个有向图G(N,E)，其中N:一组节点N=T1T2,Tn,Ti是S中的事务E:一组有向边E=e1,e2,en,Ti Tj 是图中的一条边，当且仅当 p Ti,q Tj 使得p,q 冲突，并且 p S q,测试调度S的可串行化,对于调度 S中的事务Ti，在图中创建一个节点Ti对于每一种这样的情形：如果S中的在Ti执行了W(X)操作后执行Tj的R(X)操作，那么在优先图中创

10、建一条边（TiTj）对于每一种这样的情形：如果S中的在Ti执行了R(X)操作后执行Tj的W(X)操作，那么在优先图中创建一条边（TiTj）对于每一种这样的情形：如果S中的在Ti执行了W(X)操作后执行Tj的W(X)操作，那么在优先图中创建一条边（TiTj）当且仅当优先图中没有闭环时，调度S是可串行化的,测试调度S的可串行化,优先图中存在环路，说明调度是不可串行化的，否则是可串行化的。环路是指有向图中每条边的起始节点（第一条边除外），都与前一条边的终止节点连接，而第一条边的起始节点于最后一条边的终止节点连接，即事务序列是以同一个节点作为开始和结束的调度S中事务Ti在事务Tj之前，与S等价的调度中

11、Ti也必须在Tj之前某项数据导致了调度中的一条边的生成，就把数据项标注到优先图中这条边的旁边如果调度S中不存在环路，那么就可能存在若干个与S等价的串行调度,存在环路,举例,考虑如下3个事务：T1:Read(x);Write(x);Commit;T2:Write(x);Write(y);Read(z);Commit;T3:Read(x);Read(y);Read(z);Commit;这3个事务的一个调度：S=W2(x),W2(y),R2(z),C2,R1(x),W1(x),C1,R3(x),R3(y),R3(z),C3 优先图：T2 T1 T3无环，S是串行调度。,另外一个调度S:S=W2(x)

12、,R1(x),W1(x),C1,R3(x),W2(y),R3(y),R2(z),C2,R3(z),C3 先序图：T2 T1 T3无环，是可串调度。,可串性理论扩展,可串性理论可以直接扩展到无重复副本的分布式数据库中。事务在每个站点上的执行调度称作局部调度如果数据库无重复副本的分布式数据库，并且每个局部调度都是可串行化调度，只要这些局部调度的顺序一致，则它们的并（全局调度）也是可串行化调度但是有副本的情况下，就比较复杂。可能局部调度是可串行化的，而全局调度不是可串行化的。,保证只产生可串行化调度的机制并发控制机制分类按分配模式(数据方式)完全复制的DB部分复制DB或分片的DB按网络类型(通信方式

13、)广播能力的星型网,环形网同步化原则建立在相互排斥地访问共享数据基础上的算法通过一些准则(协议)对事务进行排序的算法悲观并发控制法（事务是相互冲突的），乐观并发控制法（没有太多的事务相互冲突）,并发控制算法的分类,封锁法事务的同步化是通过对数据库的片断或者数据项进行物理或逻辑封锁来实现的封锁对象的大小通常称为封锁粒度封锁方法的类型可以根据在哪里进行封锁来进一步细分封锁法分类集中式封锁方法一个站点被指定为主站点，存放对整个数据库的封锁表，并且负责对全系统事务进行封锁主副本封锁法：对主副本所在站点封锁分布式封锁法：网络中的站点共享锁的管理,基本思想和概念,基本思想事务访问数据项之前要对该数据项封锁

14、，如果已经被其他事务锁定，就要等待，直到那个事务释放该锁为止锁的粒度锁定数据项的范围数据项层次数据库记录中的一个字段值一条数据库记录一个磁盘块（页面）一个完整的文件整个数据库,基本思想和概念,粒度对并发控制的影响大多数DBMS缺省设置为记录锁或页面锁粒度小，并发度高，锁开销大数据项比较多，锁也多，解锁和封锁操作多，锁表存储空间大（如存储读写时间戳）粒度大，并发度低，锁开销小如果是磁盘块，封锁磁盘块中的一条记录B的事务T必须封锁整个磁盘块而另外一个事务S如果要封锁记录C,而C也在磁盘块中，由于磁盘块正在封锁中，S只能等待如果是封锁粒度是一条记录的话，就不用等待了,基本思想和概念,如何来确定粒度取

15、决于参与事务的类型如果参与事务都访问少量的记录，那么选择一个记录作为粒度较好如果参与事务都访问同一文件中大量的记录，则最好采用块或者文件作为粒度,锁的类型：共享锁：Share锁，S锁或者读锁排它锁：eXclusive锁，X锁，拒绝锁或写锁。更新锁：Update锁，U锁锁的选择：数据项既可以读也可以写.则要用X锁如果数据项只可以读.则要用 S锁.,基本思想和概念,锁的操作Read_lock(x):读锁Write_lock(x)：写锁unlock(x)：解锁数据项的状态read_locked:读锁Write_locked:写锁具体操作方法在系统锁表中记录关于锁的信息锁表中每条记录有四个字段：锁状态

16、是上面两种。没有被封锁的数据项，在系统表中没有记录,基本思想和概念,封锁准则：事务T在执行任何read_item（x）操作之前，必须先执行read_lock(x)或者write_lock(x)操作事务T在执行任何write_item（x）操作之前，必须先执行write_lock(x)操作如果事务T执行read_lock(x)操作,数据项x必须没有加锁或者已经加了读锁，否则事务T的这个操作不能进行如果事务T执行write_lock(x)操作,数据项x必须没有加锁，否则事务T的这个操作不能进行,封锁准则和锁的转换,封锁准则：事务T在完成所有read_item（x）和write_item（x）操作之

17、后，必须执行unlock(x)操作如果事务T已经持有数据项x上的一个读锁或者一个写锁，那么它不能再执行read_lock(x)操作如果事务T已经持有数据项x上的一个读锁或者一个写锁，那么它不能再执行write_lock(x)操作如果事务T没有持有数据项x上的一个读锁或者一个写锁，那么它不能执行unlock(x)操作,封锁准则和锁的转换,锁的转换特定条件下，一个已经在数据项x上持有锁的事务T，允许将某种封锁状态转换为另外一种封锁状态比如，一个事务先执行了read_lock（x）操作，然后他可以通过执行write_lock(x)操作来升级该锁同样，一个事务先执行了write_lock(x)操作，然

18、后他可以通过执行read_lock（x）操作来降级该锁,封锁准则和锁的转换,满足封锁规则不能保证产生串行化调度,简单的分布式封锁方法类似集中式，将同一数据的全部副本封锁，然后更新，之后解除全部封锁缺点是各站点间进行相当大的数据传输，如果有N个站点，就有：N个请求封锁的消息N个封锁授权的消息N个更新数据的消息N个更新执行了的消息N个解除封锁的消息,分布式数据库基本封锁算法,主站点封锁法定义一个站点为主站点，负责系统全部封锁管理所有站点都向主站点提出封锁和解锁请求，由它去处理缺点有：所有封锁请求都送往单个站点，容易由于超负荷造成“瓶颈”主站点故障会使系统瘫痪，封锁消息都在这里，制约了系统可用性和可

19、靠性,分布式数据库基本封锁算法,主副本封锁法不指定主站点，指定数据项的主副本事务对某个数据项进行操作时，先对其主副本进行封锁，再进行操作主副本封锁，意味着所有的副本都被封锁主副本按使用情况，尽量就近分布可减少站点的负荷,使得各站点比较均衡可减少传输量快照方法和上一章讲的类似,分布式数据库基本封锁算法,基本2PL协议,如果一个事务所有的封锁操作（读写）都在第一个解锁操作之前，那么它就遵守2PL协议事务的执行中Lock的管理分成两个阶段上升阶段(成长阶段)：获取Lock阶段（只能获取锁）收缩阶段(衰退阶段）：释放Lock阶段（只能解锁）封锁点是指事务获得了它所要求的所有锁，并且还没有开始释放任何锁

20、的时刻如果允许锁的转换，锁的升级必须在成长阶段进行，锁的降级必须在锁的衰退阶段进行。2PL可以保证事务执行的可串行性.,开始,加锁点,结束,事务执行过程,获得锁,释放锁,两阶段封锁协议,基本2PL协议实现的难点锁管理器必须要知道事务的锁点位置级联撤销(cascading aborts)如果事务在开始释放Lock后又Abort时,将引起级联撤销(cascading aborts)（其他访问这个数据项的事务也被撤销）保守2PL要求事务在开始执行之前就持有所有它要访问的数据项上的锁事务要预先声明它的读集和写集大多数2PL调度器实现的是严格2PL(S2PL)事务在提交或者撤销之前，绝对不释放任何一个写

21、锁事务结束时（提交或者撤销），同时释放所有的锁,严格2PL事务T在提交或撤销之前，不能释放任何一个锁（写锁或者读锁），因此它比严格2PL更容易实现保守2PL与严格2PL之间的区别前者，事务必须在开始之前封锁它所需要的所有数据项，因此，一旦事务开始就处在收缩阶段后者,直到事务结束（提交或者撤销）后才开始解锁，因此，事务一直处于扩张阶段，直到结束,开始,结束,事务执行阶段,获得锁,释放锁,严格2PL(Strict Two-phase Locking)协议,数据项使用,并发控制子系统可以负责产生读锁和写锁操作（以严格2PL协议为例）当事务T发出read_item(x)操作请求时，系统会代表T调用re

22、ad_lock(x)操作如果Lock(x)的状态是被另外一个事务T持有写锁，那么系统会把T放到数据项X的等待队列中；否则，系统同意read_lock(x)的请求，从而允许事务T执行read_item(x)操作另外一个方面，如果事务T发出write_item（x）操作请求时，系统会代表T调用write_lock(x)操作如果Lock(x)的状态是被另外一个事务T持有读锁或写锁，那么系统会把T放到数据项X的等待队列中；如果Lock(x)的状态是读锁，并且事务T本身就是持有x上的读锁的唯一事务，那么系统将该锁升级为写锁，并且允许T执行write_item(x)操作如果Lock(x)的状态是没有锁，那

23、么系统同意write_lock(x)的请求，进而允许事务T执行write_item(x)操作,集中式2PL的实现方法,2PL很容易扩展到分布式DBMS(无论复制或无复制DDB),其最简单的方法是选择一个站点(主站点)做Lock管理器,其他站点上的事务管理器都需要与该选出的站点Lock管理器通信,而不是与本站点Lock管理器通信.这就是集中式2PL方法,术语协调事务管理器(coordinating TM)：事务原发站点数据处理器(data processor，DP)：其他参与站点中心站点LM：主站点锁管理器,参与站点的数据处理器,协调 TM,中心站点 LM,加锁请求,允许加锁,操作,操作结束,释

24、放封锁,集中式2PL的通信结构,中心站点LM不需要向DP发送操作,集中式2PL的实现方法,主副本2PL的实现方法,是主站点2PL的直接扩展选择一组站点做Lock管理器每个Lock管理器管理一组数据(即每个数据选择一个站点作自己的Lock管理器)事务管理器根据Lock申请的数据对象分别向这些数据的LM发出锁申请必须先为每一个数据项确定一个主副本站点，然后再向那个站点上的封锁管理程序发送封锁或释放锁的请求，目录的思想为分布式INGRES版本提出的，每个站点上要有一个复杂的目录,特点每个站点都有LM无副本DDB上如同主副本2PL有冗余副本DDB上则使用ROWA控制协议与集中式相似，但有不同集中式中向

25、中心站点封锁管理程序发送的信息，在分布式中发送给所有参与站点的封锁管理程序另外不同之处在于操作并不通过协调者事务管理程序传到数据处理器，而是通过参与者的封锁管理程序参与者的数据处理器向协调者的事务管理程序发送“操作结束”信息另外一种方法，每个数据处理器执行自身解锁，并通知协调者事务管理程序的封锁管理程序,分布式2PL的实现方法,参与者 DPs,加锁请求,操作,分布式2PL的通信结构,协调者 TM,参与者 LMs,操作结束,释放锁,分布式2PL的实现方法,多粒度封锁封锁的粒度不是单一的一种粒度，而是有多种粒度可以定义多粒度树，根节点是整个数据库，叶节点表示最小的封锁粒度直接封锁事务对要进行读/写

26、的数据对象直接申请加锁分层封锁DB中各数据对象从大到小存在一种层次关系,例如划分为DB,段,关系,元组,字段等 当封锁了外层数据对象时,蕴含着也同时封锁了它的所有内层数据对象数据项的显式封锁和隐式封锁,数据库,段1,段n,.,多级粒度树,关系nn,关系11,.,.,用来说明多粒度级别封锁的粒度层次结构,例子假定事务T1要更新文件f1中的所有记录，T1请求并获得了f1上的一个写锁那么f1下面的页面和记录就获得了隐式写锁如果这时候，事务T2想从f1中的某个页面中读某个记录，那么T2就要申请该记录上的读锁但是要确认这个读锁和已经存在锁的相容性，确认的方法就是要遍历该树：从记录到页，到文件最后到数据库

27、，如果在任意时刻，在这些项中的任意一个上存在冲突锁，那么对记录的封锁请求就被拒绝，T2被阻止，要等待。,意向锁如果对一个节点加意向锁，则说明该节点的下层节点正在被封锁对任一节点封锁时，必须先对它的上层节点加意向锁意向锁的类型意向共享锁(IS)：指示在其后代节点上将会请求共享锁，即如果对某个对象加IS锁，表示它的后代节点拟加共享锁意向排它锁(IX)：指示在其后代节点上将会请求排他锁，即如果对某个对象加IX锁，表示它的后代节点拟加排他锁共享意向排它锁(SIX)：指示当前节点处在共享方式的封锁中，但是在它的某些后代节点中将会请求排他锁。即如果对一个数据对象加SIX锁,表示对它加共享锁，再加IX锁（S

28、IX=S+IX）。例如：对某个表加SIX锁，则表示该事务要读整个表（加S锁），同时会更新个别元组（加IX锁）,T2,T1,Y,Y,Y,Y,Y,Y,-,Y,N,N,Y,N,N,SIX,Y,N,Y,Y,N,N,IX,Y,Y,Y,Y,N,Y,IS,Y,N,N,N,N,N,X,Y,N,N,Y,N,Y,S,-,SIX,IX,IS,X,S,X,SIX,S,IX,IS,Y=yes，表示相容的请求 N=no，表示不相容的请求,(a)数据锁的相容矩阵,(b)锁的强度的偏序关系,锁的相容矩阵,锁的强度：对其它锁的排斥程度,多粒度封锁协议的规则必须遵守锁的相容性规则必须首先封锁树的根节点，可以用任何一种方式的锁只有

29、当节点N的父节点已经被事务T以IS或IX方式封锁后，节点N才可以被T以S或者IS方式封锁只有当节点N的父节点已经被事务T以IX或SIX方式封锁后，节点N才可以被T以X,IX或者SIX方式封锁只有当事务T还没有释放任何节点时，T才可以封锁一个节点只有当事务T当前没有封锁节点N的任何子节点时，T才可以为节点N解锁。,总结具有意向锁的多粒度加锁方法中，任意事务T要对一个数据对象加锁，必须先对它的上层节点加意向锁申请封锁时应该按自上而下的次序进行释放锁时则应该按自下而上的次序进行具有意向锁的多粒度加锁方法提高了系统的并发度,减少了加锁和释放锁的开销它已经在实际的DBMS系统中广泛应用，例如Oracle

30、中,死锁发生的条件互斥条件：事务请求对资源的独占控制等待条件：事务已持有分配给它的资源,又去申请并等待别的资源非抢占条件：直到资源被持有它的事务释放前,不可能将资源强制从持有它的事务夺去循环等待条件：存在事务互相等待的等待圈死锁分类局部死锁：仅在一个站点上发生的死锁全局死锁：涉及多个站点的死锁(即等待圈由多个站点组成),事务T1持有对x的锁,事务T2请求对x的锁,事务T2持有对y的锁,事务T1请求对y的锁,站点A,站点B,T2等待T1完成释放对x的锁,T1等待T2完成释放对y的锁,相互等待引起的全局死锁,T1,T2,T3,站点A：x1,y1,站点C：z3,站点B：y2,z2,等待释放对y 的锁

31、,等待释放对x 的锁,等待释放对z 的锁,站点A：存储x和y的副本，发出事务T1：read(x),write(y)站点B：存储y和z的副本，发出事务T2：read(y),write(z)站点C：存储z的副本，发出事务T3：read(z),write(x),多副本引起的三个站点间的死锁,等待图一种用来表示事务之间相互等待关系的有向图,是分析死锁的有用工具节点表示事务带有箭头的有向边表示“等待”关系如果等待图有回路，就说明有死锁等待图分类局部等待图(LWFG)全局等待图(GWFG),T1,T3,T2,y,x,z,T1等待T2释放对y的共享锁(s)T2等待T3释放对z的共享锁(s)T3等待T1释放对

32、x的共享锁(s),上例的GWFG等待图,(a),(b),T2,T1,T1,T2,T4,T3,T4,T3,站点1,站点2,LWFG和GWFG之间的不同,事务间的等待关系T1T2T3T4,解决死锁的方法死锁预防，使引起死锁的必要条件不成立所有资源排序,按资源序列申请将所有并发事务排序,按标识符或开始时间有死锁危险时，事务退出已占有的资源，有两种方法等待-死亡(Wait-Die)：总是重启较年轻的事务(非占先权)受伤-等待(Wound-Wait)：年轻的等待年老的,较年轻的重启,而重启事务并不一定是目前正申请的事务(占先权)死锁检测 即检测死锁时循环等待的圈,等待-死亡模式如果Ti对已被Tj封锁的一

33、数据项请求封锁的话，则只有在Ti比Tj年老时（TiTj），则Ti被终止并带有同一时间戳重新启动最好总是重新启动较年轻的事务允许较年老的事务去等待已持有资源的较年轻的事务但不允许较年轻的事务去等待较年老的事务受伤-等待模式如果Ti对已被Tj封锁的一数据项请求封锁的话，则只有在Ti比Tj年轻时（TiTj），才允许Ti等待否则，Ti比Tj年老（TiTj），则Tj被终止并带有同一时间戳重新启动,而Ti得锁执行只有年轻的等待年老的,集中式死锁检测选择一个站点负责整个系统的死锁检测,死锁检测器放到这个站点每个站点的锁管理器周期性地将本站点的LWFG传送给死锁检测器,死锁检测器构造GWFG,并在其中寻找回路

34、或者，其它每个站点上的锁管理器周期性地把记录本站点上事务的开始时间，对锁的持有、请求情况变化的动态表，发送给负责处理封锁的站点，由它维护一张全局封锁动态表，形成GWFG,并在其中寻找回路如果至少包含一条回路，它会选择一个或者多个事务，把它们取消并恢复，释放资源，使得其它事务继续进行。选择的标准是尽可能使撤销并恢复的代价最小，如撤销年轻的事务，撤销占有较少资源的事务，撤销具有最短运行时间的事务，撤销具有最长运行时间的事务等，使系统情况而定,层次式死锁检测以层次方式组织成员DBMS中的死锁检测器死锁发生时,常常只涉及部分站点层次检测的层次结构与网络拓扑结构有关减少了对中心站点的依赖性，从而减少了传

35、输开销,层次式死锁检测的步骤树叶是各站点的局部死锁检测器，在本站点建立局部等待图本站点的死锁检测器找出本站点局部等待图中的任何回路，并把有关潜在全局回路的信息发送给上一层死锁检测器每个非本地死锁检测器只对它所涉及的紧挨下层进行死锁检测，合并这些接收到的有关潜在全局回路的信息，并找出任何回路如果还有上层死锁检测器，将经过简化的有关潜在全局回路的信息发送给它上一层死锁检测器，由上一层死锁检测器再进行合并，找出任何全局回路这样，逐层检测，直到最高层。,第0层死锁检测器,第i层死锁检测器,第i层死锁检测器,局部死锁检测器,局部死锁检测器,局部死锁检测器,局部死锁检测器,简化潜在死锁图,简化潜在死锁图,

36、简化潜在死锁图,简化潜在死锁图,简化潜在死锁图,简化潜在死锁图,层次式死锁检测方法示意图,分布式检测每个站点的检测死锁责任相同,站点之间交换信息(LWFG)，是为了确定全局死锁EX是指的本地事务正在等待的其他事务所在的还不确定的站点例子,站点1,站点2,T1,T2,T4,T3,EX,EX,信息传递方向 此处规定一种,以避免多次重复传递EX等待的事务号 等待EX的事务号分布式死锁检测算法使用局部信息建造LWFG,该LWFG包含EX节点对每次接收到的信息,执行如下对LWFG的修改对报文中的每个事务,若LWFG中不存在,则将其加入从EX节点开始,按照报文所给的信息,建立一个到下一个事务的边在新的LW

37、FG中寻找不含EX的Loop,若存在,则检测到死锁在新的LWFG中找到含有EX的Loop,于是有潜在的死锁,再按规定向外传送信息,基本概念不通过互斥来支持串行性，而是通过在事务启动时赋给时标（时间戳）来实现时标是用来唯一识别每个事务并允许排序的标识如果 ts(T1)ts(T2)ts(Tn),则调度器产生的序是:T1,T2,.Tn 规则如果T1的操作O1(x)和T2的操作O2(x)是冲突操作,那么,O1在O2之前执行,当且仅当ts(T1)ts(T2),时标分配方法全局时标使用全局的单调递增的计数器全局的计数器维护是个难题局部时标每个站点基于其本地计数器自治地指定一个时标标识符由两部分组成：本地计

38、数器值，站点标识符站点标识符是次要的，主要是本地计数器值可以使用站点系统时钟来代替计数器值,时标法思想每个事务赋一个唯一的时标，事务的执行等效于按时标次序串行执行如果发生冲突，是通过撤销并重新启动一个事务来解决的事务重新启动时，则赋予新的时标优点是没有死锁，不必设置锁封锁和死锁检测引起的通信开销也避免了但要求时标在全系统中是唯一的,时标性质唯一性单调性全局唯一时间的形成与调整每个站点设置一个计数器,每发生一个事务,计数器加一发送报文时包含本地计数器值,近似同步各站点计数器,计数器X 初值X=0 计数器Y 初值Y=10 站点1 站点2 时标 A D 时标 TS(A)=TS(D)=因为X 改X=Y

39、+1=11 B TS(B)=F 因为YX TS(C)=C TS(F)=本地计数器 本地计数器(或时钟)(或时钟),报文1,报文2,计数器,站点,基本时标法,规则每个事务在本站点开始时赋予一个全局唯一时标在事务结束前，不对数据库进行物理更新事务的每个读操作或写操作都具有该事务的时标对每个数据项x,记下写和读操作的最大时标，记为WTM(x)和RTM(x)如果事务被重新启动，则被赋予新的时标,基本时标法执行过程令read_TS是事务对x进行读操作时的时标若read_TSWTM(x)，则拒绝该操作,事务重新启动否则,执行,令RTM(x)=maxRTM(x),read_TS令write_TS是事务对x进

40、行写操作时的时标若write_TS RTM(x)或 write_TS WTM(x),则拒绝该操作,事务重新启动否则,执行,令WTM(x)=maxWTM(x),write_TS缺点是重启动多,基本思想一种消除重启动的方法通过缓冲年轻的操作，直至年长的操作执行完成，因此操作不会被拒绝，事务也绝不被重启动规则每个事务只在一个站点执行,它不能激活远程的程序,但是可以向远程站点发读/写请求站点i接收到来自不同站点j的读/写请求必须按时标顺序，即每个站点必须按时标顺序发送读/写数据请求，在传输中也不会改变这个顺序每个站点都为其它站点发来的读/写操作开辟一个缓冲区,分别保存接收到的读/写申请,假定某个站点k

41、上,各个缓冲区队列都已不为空，即每个站点都已向它至少发送了一个读和一个写操作，就停止接收，处理在缓冲区中的操作假定站点i至少有一个缓冲的读和缓冲的写来自网中其它站点,根据规则2,Site i 知道没有年老的请求来自其它Site(因为按序接收,所以不可能有比此更年老的请求到来,年老的比年轻的先到),例子 已知站点i的缓冲区队列中有来自所有站点的读/写请求如下所示:站点1 站点2 站点3 站点n R11 R21 R31 Rn1 R12 R22 R32 R13 R23 R24 W11 W21 W31 Wn1 W22 W32 Wn2 W23,执行步骤:(1)设RT=min(Rij),WT=min(Wi

42、j)(2)按下法处理缓冲区中的Rij和Wij a.若队列中有(Rij)WT的Rij,则顺序执行这些Rij，执行完删掉 b.若队列中有(Wij)RT的Wij,则顺序执行这些Wij，执行完删掉(3)修改 RT=min(Rij),WT=min(Wij)，此时的Rij和Wij是队列中剩余的(4)重复上述(2)和(3),直到没有满足条件的操作,或者:a.若某个或某些R队列为空时,RT=0;b.若某个或某些W队列为空时,WT=0,存在问题和解决方法如果一个站点从来不向某个站点发送操作的话，那么执行过程中的假定就不符合，操作就无法进行。解决办法是，周期性的发送带有时标的空操作此方法要求网络上所有站点都连通，

43、这在大系统中很难办到。为避免不必要的通信，可对无读写操作请求的站点，发送一个时标很大的空操作此方法过分保守，一律按照时序来进行，其中包括了不冲突的操作,基本思想保存了已更新数据项的旧值维护一个数据项的多个版本通过读取数据项的较老版本来维护可串行性，使得系统可以接受在其他技术中被拒绝的一些读操作写数据项时，写入一个新版本，老版本依然保存缺点需要更多的存储来维持数据库数据项的多个版本模式分类基于时标排序基于两阶段封锁,数据项X的多版本X1,X2,X3,Xk系统保存的值Xi的值两种时标Read_TS(Xi):读时标，成功读取版本Xi的事务的时标，最大的一个Write_TS(Xi):写时标，写入版本X

44、i的值的事务的时标,多版本规则如果事务T发布一个write_item(X)操作，并且X的版本Xi具有X所有版本中最高的write_TS(Xi),同时write_TS(Xi)TS(T)，那么撤销并回滚T；否则创建X的一个新版本，并且令read_TS(Xi)=write_TS(Xi)=TS(T)如果事务T发布一个read_item(X)操作，并且X的版本Xi具有X所有版本中最高的write_TS(Xi),同时write_TS(Xi)=TS(T)，把Xi的值返回给事务T,并且将read_TS(Xi)的值置为TS(T)和当前read_TS(Xi)中较大的一个,图示,写值,若读 TS(Ri)=95,则读

45、 的值若写TS(Wk)=93,则出现了,v1,v2,v3,Vn-1,Vn,5,10,20,92,100,93,v,于是要拒绝TS(Wk),否则 TS(Ri)=95读的就是Vn-1,而不是v的值,但是按规定 TS(Ri)=95应该读的是v值,三种锁方式读，写，验证四种锁状态读封锁（read_locked）写封锁（write_locked）验证封锁（certify_locked）未封锁（unlocked）锁相容性标准模式锁相容性（写锁和读锁）验证模式锁相容性（写锁、读锁和验证锁）,多版本2PL的思想当只有一个单独的事务T持有数据项上的写锁时，允许其他事务T读该项X，这是通过给予每个项X的两个版本来

46、实现的一个版本X是由一个已提交的事务写入的另一个版本X是每个事务T获得该数据项上写锁时创建的当事务T持有这个写锁时，其他事务可以继续读X的已提交版本事务T可以写X的值，而不影响X已提交版本的值但是，一旦T准备提交，它必须在能够提交之前，得到持有写锁的数据项上的验证锁，要等写锁释放之后一旦获得验证锁，数据项的已提交版本X被置为版本X的值，版本X被丢弃，验证锁被释放。,基本思想对于冲突操作不像悲观方法那样采取挂起或拒绝的方法，而是让一个事务执行直到完成基于如下假设冲突的事务是少数（查询为主的系统中，冲突少于5%）大多数事务可以不受干扰地执行完毕,事务的三个阶段读段/计算：在数据对象的局部副本上执行

47、事务，这时其他事务不能存取此副本。事务从DB读数据，执行计算，并且确定写集数据项的新值。写操作总是对局部副本，仅当验证通过后，在事务结束处，才将其写入DB。验证段：检验并发事务的可串性，该阶段验证修改应用是否引起完整性（一致性）的丢失，验证阶段通过，才能进入写段，否则事务重启动写段/提交：验证阶段通过，则把事务的更新应用于数据库，对数据进行更新，否则，忽略所有更新，并重新开始该事务,验证使用数据项和事务上的时标只使用事务时标,使用数据项和事务上的时标假设是一个完全冗余的DB，事务在读期间把更新写入一个更新表事务时标：事务在启动执行时接受的具有唯一性的时标数据项时标：对该数据项最后写入的事务的时

48、间戳算法假定：读集 写集，即写必须先读,读阶段末，事务产生一个更新表u，包括读集的数据项，带有自身的时标写集数据项的新值该事务自身的时标验证阶段把更新表发送到每一站点，每个站点对是否确认该更新表进行表决，并把表决结果送回到该事务的源站点如源站点收到多数肯定票，则决定事务提交并通知各站点如多数表决是否定的，则把放弃更新表的决定通知所有站点，然后重新启动该事务,表决规则比较更新表u中数据项的时标与本地库中相应数据项的时标,全部相等则投赞成票不相等,投反对票,因为此时可能本地写入数据项之前或之后,又有事务对数据项做了写操作表决结果若赞成票是大多数,则考虑Commit,并将结论发送给每个Site否则,

49、其更新表无效,事务重启动,更新表冲突表决规则比较u表中读集中数据项的时标与数据库中对应数据项的时标，如果不等，投否定票若相等，Site j在对u表做表决时,若存在Site k上的u表传送到Site j,使Site j处于对u的表决中若u中有与u冲突的更新表,当u中的时标大时,则反对 当u中的时标小时,则延迟表决若与u中无冲突数据项,则赞成,原发Site,投票 Site j,事务Tj的验证过程检验由一些事务给出的执行调度是否可以成为一个按时标串行执行的调度.参与验证的事务有:a 已经提交的事务b 当Tj验证时也正处于验证的事务c Tj本身,对于所有TS(Ti)TS(Tj)的事务Ti,Tj验证必须

50、满足如下三个条件Ti在Tj开始其读段前已完成其写段(严格串行)Ti的写集与Tj的读集不相交,并且Ti在Tj开始其写段时已完成其写段(Ti与Tj不冲突)Ti的写集与Tj的写集不相交,并且Ti在Tj读段完成前已结束其读段(写/写不冲突),Start(T),Finishi(T),TS(T),验证 在Tj执行期间记录下列信息:a Tj的读集和写集 b Tj启动时TNC的值,称为Start(Tj)c Tj结束其读段时的TNC值,称为Finish(Tj)TS(Tj)：只有在写段之后(验证成功)才把此唯一的时标赋给Tj,仅当将TS(Tj)赋给Tj后,TNC值才增值.Finish(Tj)与Start(Tj)无