并发控制的概念和理论分布式数据库系统并发控制的封锁技术

《并发控制的概念和理论分布式数据库系统并发控制的封锁技术》由会员分享，可在线阅读，更多相关《并发控制的概念和理论分布式数据库系统并发控制的封锁技术（110页珍藏版）》请在装配图网上搜索。

1、1.1.并发控制的概念和理论并发控制的概念和理论2.2.分布式数据库系统并发控制的封锁技术分布式数据库系统并发控制的封锁技术3.3.分布式数据库系统中的死锁处理分布式数据库系统中的死锁处理4.4.分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术5.5.分布式数据库系统并发控制的多版本技术分布式数据库系统并发控制的多版本技术6.6.分布式数据库系统并发控制的乐观方法分布式数据库系统并发控制的乐观方法分布式数据库中的并发控制分布式数据库中的并发控制 第第5章章通常，数据库总有若干个事务在运行，这些事务可能并发地存取相同的数据，称为事务的并发操作。当数据库中有多个事务并发执行时，

2、系统必须对并发事务之间的相互作用加以控制，这是通过并发控制机制来实现的。并发控制就是负责正确协调并发事务的执行，保证这种并发的存取操作不至于破坏数据库的完整性和一致性，确保并发执行的多个事务能够正确地运行并获得正确的结果。分布式数据库中的并发控制解决多个分布式事务对数据并发执行的正确性，保证数据库的完整性和一致性。比集中式并发控制更复杂。1.1 并发控制的概念并发控制的概念1 1 并发控制的概念和理论并发控制的概念和理论集中式DB环境 T1T2TnDB(一致性约束)1.1 并发控制的概念并发控制的概念1 1 并发控制的概念和理论并发控制的概念和理论分布式DB环境XYZT1T21.1 并发控制的

3、概念并发控制的概念1 1 并发控制的概念和理论并发控制的概念和理论 多处理器CPU1CPU2T1T2Time1.1 并发控制的概念并发控制的概念1 1 并发控制的概念和理论并发控制的概念和理论并发执行并发执行 单处理器T1t1T2t2T1t3T2t4TimeCPU1.1 并发控制的概念并发控制的概念1 1 并发控制的概念和理论并发控制的概念和理论非并发执行非并发执行UPDATE x70t6FIND xt2200t7UPDATE xt5x:=x*2t4x:=x-30t3FIND xt1100t0更新事务T2数据库中X的值更新事务T1时间注：其中FIND表示从数据库中读值，UPDATE表示把值写回

4、到数据库T1T2，结果140，T2T1,结果170，得到结果是200，显然是不对的，T1在t7丢失更新操作。1.1 并发控制的概念并发控制的概念1 1 并发控制的概念和理论并发控制的概念和理论并发控制问题之一：丢失更新并发控制问题之一：丢失更新FIND xt270t5UPDATE xt4x:=x-30t3FIND xt1100t0更新事务T2数据库中A的值更新事务T1时间注：在时间t5事务T2仍认为x的值是1001.1 并发控制的概念并发控制的概念1 1 并发控制的概念和理论并发控制的概念和理论并发控制问题之二：不一致分析并发控制问题之二：不一致分析100t6x:=x-10t2ROLLBACK

5、t5FIND x90t4UPDATE xt3FIND xt1100t0更新事务T2数据库中A的值更新事务T1时间注：事务T2依赖于事务T1的未完成更新1.1 并发控制的概念并发控制的概念1 1 并发控制的概念和理论并发控制的概念和理论并发控制问题之三：依赖于未提交更新（读脏数据）并发控制问题之三：依赖于未提交更新（读脏数据）事务Ti Ti=i,i 其中：1.i:操作符集合：Ri(x),Wi(x)U Ai,Ci 2.Ai,Ci 是最后的操作符，只能是其一3.i:(冲突)操作有序执行，Ri(x)i Wi(x)或 Wi(x)i Ri(x)1.2 事务可串行化理论事务可串行化理论1 1 并发控制的概念

6、和理论并发控制的概念和理论操作符集 读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)1.2 事务可串行化理论事务可串行化理论1 1 并发控制的概念和理论并发控制的概念和理论 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先序关系例子例子已知：站点1有数据X，站点2有数据Y约束：X=Y1.2

7、事务可串行化理论事务可串行化理论1 1 并发控制的概念和理论并发控制的概念和理论(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=1NNi=11.2 事务可串行化理论事务可串行化理论1 1 并发控

8、制的概念和理论并发控制的概念和理论调度一组事务的调度必须包含这些事务的所有操作调度中某个事务的操作顺序必须保持与该事务原有的顺序相同串行调度 一个事务的第一个动作是在另一个事务的最后一个动作完成后开始.即调度中事务的各个操作不会交叉,每个事务相继执行.一致性调度调度可以使得数据库从一个一致性状态转变为另一个一致性状态，则称调度为一致性调度1.2 事务可串行化理论事务可串行化理论1 1 并发控制的概念和理论并发控制的概念和理论调度等价S1与S2等价,也就是说,对于冲突操作,Oi Oj在S1中成立,同时 Oi Oj 在S2中也成立可串行化调度如果一个调度等价于某个串行调度，则该调度称为可串行化调度

9、。也就是说，该调度可以通过一系列非冲突动作的交换操作使其成为串行调度1.2 事务可串行化理论事务可串行化理论1 1 并发控制的概念和理论并发控制的概念和理论例子两个事务，定义如下：T1:1.Read(x）2.x=x+103.Write(x)4.Read(y)5.y=y-156.Write(y)mit1.2 事务可串行化理论事务可串行化理论1 1 并发控制的概念和理论并发控制的概念和理论T2:1.Read(x）2.x=x-203.Write(x)4.Read(y)5.y=y*26.Write(y)mit五种调度：S1=R1(x),x=x+10,W1(x),R1(y),y=y-15,W1(y),C

10、1,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,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

11、=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),C11.2 事务可串行化理论事务可串行化理论1 1 并发控制的概念和理论并发控制的概念和理论如果将事务提交延迟到两个事务操作完成之后执行，有：调度S1和S4是串行调度调度S2和S1的冲突操作具有相同的顺序，因此是等价调度；S2是可串行化调度，也是一致性调度调度S3虽是一致调度，但是它不与S1或S4等价，所以S3不是可串行化调度调度S5和S4等价，所以S5是一致调度，也是可串行化调度1.2 事务可串行化理论事务可串行化理论1 1 并发控制的概念和理论并发控

12、制的概念和理论有以下推论：一个可串行化调度必定与某个串行调度等价，且是一致性调度一致性调度不一定是可串行化调度同一事务集几个可串行化调度，他们的结果未必相同1.2 事务可串行化理论事务可串行化理论1 1 并发控制的概念和理论并发控制的概念和理论优先图 P(S)调度 S 的优先图是一个有向图G(N,E)，其中N:一组节点N=T1T2,Tn,S中的事务E:一组有向边E=e1,e2,en,Ti Tj 是图中的一条边，当且仅当 p Ti,q Tj 使得p,q 冲突，并且 p S q1.3 分布式事务的可串行化调度测试分布式事务的可串行化调度测试1 1 并发控制的概念和理论并发控制的概念和理论测试调度S

13、的可串行化对于调度 S中的事务Ti，在图中创建一个节点Ti对于每一种这样的情形：如果S中的在Ti执行了W(X)操作后执行Tj的R(X)操作，那么在优先图中创建一条边（TiTj）对于每一种这样的情形：如果S中的在Ti执行了R(X)操作后执行Tj的W(X)操作，那么在优先图中创建一条边（TiTj）对于每一种这样的情形：如果S中的在Ti执行了W(X)操作后执行Tj的W(X)操作，那么在优先图中创建一条边（TiTj）当且仅当优先图中没有闭环时，调度S是可串行化的1.3 分布式事务的可串行化调度测试分布式事务的可串行化调度测试1 1 并发控制的概念和理论并发控制的概念和理论测试调度S的可串行化优先图中存

14、在环路，说明调度是不可串行化的，否则是可串行化的。环路是指有向图中每条边的起始节点（第一条边除外），都与前一条边的终止节点连接，而第一条边的起始节点于最后一条边的终止节点连接，即事务序列是以同一个节点作为开始和结束的调度S中事务Ti在事务Tj之前，与S等价的调度中Ti也必须在Tj之前某项数据导致了调度中的一条边的生成，就把数据项标注到优先图中这条边的旁边如果调度S中不存在环路，那么就可能存在若干个与S等价的串行调度1.3 分布式事务的可串行化调度测试分布式事务的可串行化调度测试1 1 并发控制的概念和理论并发控制的概念和理论1.3 分布式事务的可串行化调度测试分布式事务的可串行化调度测试1 1

15、 并发控制的概念和理论并发控制的概念和理论T1T2T1T2T1T2T1T2T1T2S1的优先图S2的优先图S3的优先图S4的优先图S5的优先图XYXYXYXYXY存在环路存在环路举例考虑如下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是串行调度。1.3 分布式事务的可

16、串行化调度测试分布式事务的可串行化调度测试1 1 并发控制的概念和理论并发控制的概念和理论另外一个调度S:S=W2(x),R1(x),W1(x),C1,R3(x),W2(y),R3(y),R2(z),C2,R3(z),C3 先序图：T2 T1 T3无环，是可串调度。1.3 分布式事务的可串行化调度测试分布式事务的可串行化调度测试1 1 并发控制的概念和理论并发控制的概念和理论可串性理论扩展可串性理论可以直接扩展到无重复副本的分布式数据库中。事务在每个站点上的执行调度称作局部调度如果数据库无重复副本的分布式数据库，并且每个局部调度都是可串调度，只要这些局部调度的顺序一致，则它们的并（全局调度）也

17、是可串调度但是有副本的情况下，就比较复杂。可能局部调度是可串行化的，而全局调度不是可串行化的。1.3 分布式事务的可串行化调度测试分布式事务的可串行化调度测试1 1 并发控制的概念和理论并发控制的概念和理论保证只产生可串行化调度的机制并发控制机制分类按分配模式(数据方式)完全复制的DB部分复制DB或分片的DB按网络类型(通信方式)广播能力的星型网,环形网同步化原则建立在相互排斥地访问共享数据基础上的算法通过一些准则(协议)对事务进行排序的算法悲观并发控制法（事务是相互冲突的），乐观并发控制法（没有太多的事务相互冲突）1.4 并发控制机制的常用方法及其分类并发控制机制的常用方法及其分类1 1 并

18、发控制的概念和理论并发控制的概念和理论并发控制算法悲观法乐观法加锁法集中式加锁分布式加锁时标排序法混合法加锁法时序排序法主副本加锁基本时标排序保守时标排序多版本时标排序并发控制算法的分类封锁法事务的同步化是通过对数据库的片断或者数据项进行物理或逻辑封锁来实现的封锁对象的大小通常称为封锁粒度封锁方法的类型可以根据在哪里进行封锁来进一步细分封锁法分类集中式封锁方法一个站点被指定为主站点，存放对整个数据库的封锁表，并且负责对全系统事务进行封锁主副本封锁法：主副本所在站点封锁分布式封锁法：网络中的站点共享锁的管理1.4 并发控制机制的常用方法及其分类并发控制机制的常用方法及其分类1 1 并发控制的概念

19、和理论并发控制的概念和理论基本思想和概念基本思想事务访问数据项之前要对该数据项封锁，如果已经被其他事务锁定，就要等待，直到那个事务释放该锁为止锁的粒度锁定数据项的范围数据项层次数据库记录中的一个字段值一条数据库记录一个磁盘块（页面）一个完整的文件整个数据库2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术基本思想和概念粒度对并发控制的影响大多数DBMS缺省设置为记录锁或页面锁粒度小，并发度高，锁开销大数据项比较多，锁也多，解锁和封锁操作多，锁表存储空间大（如存储读写时间戳）粒度大，并发度低，锁开销小如

20、果是磁盘块，封锁磁盘块中的一条记录B的事务T必须封锁整个磁盘块而另外一个事务S如果要封锁记录C,而C也在磁盘块中，由于磁盘块正在封锁中，S只能等待如果是封锁粒度是一条记录的话，就不用等待了2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术基本思想和概念如何来确定粒度取决于参与事务的类型如果参与事务都访问少量的记录，那么选择一个记录作为粒度较好如果参与事务都访问同一文件中大量的记录，则最好采用块或者文件作为粒度2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机

21、制的封锁技术分布式数据库系统并发控制机制的封锁技术锁的类型：共享锁：Share锁，S锁或者读锁排它锁：eXclusive锁，X锁，拒绝锁或写锁。更新锁：Update锁，U锁锁的选择：数据项既可以读也可以写.则要用X锁如果数据项只可以读.则要用 S锁.2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术基本思想和概念锁的操作Read_lock(x):读锁Write_lock(x)：写锁unlock(x)：解锁数据项的状态read_locked:读锁Write_locked:写锁具体操作方法在系统锁表中记录

22、关于锁的信息锁表中每条记录有四个字段：锁状态是上面两种，没有被封锁的数据项，在系统表中没有记录2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术基本思想和概念封锁准则：事务T在执行任何read_item（x）操作之前，必须先执行read_lock(x)或者write_lock(x)操作事务T在执行任何write_item（x）操作之前，必须先执行write_lock(x)操作如果事务T执行read_lock(x)操作,数据项x必须没有加锁或者已经加了读锁，否则事务T的这个操作不能进行如果事务T执行wr

23、ite_lock(x)操作,数据项x必须没有加锁，否则事务T的这个操作不能进行2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术封锁准则和锁的转换封锁准则：事务T在完成所有read_item（x）和write_item（x）操作之后，必须执行unlock(x)操作如果事务T已经持有数据项x上的一个读锁或者一个写锁，那么它不能再执行read_lock(x)操作如果事务T已经持有数据项x上的一个读锁或者一个写锁，那么它不能再执行write_lock(x)操作如果事务T没有持有数据项x上的一个读锁或者一个写

24、锁，那么它不能执行unlock(x)操作2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术封锁准则和锁的转换锁的转换1.特定条件下，一个已经在数据项x上持有锁的事务T，允许将某种封锁状态转换为另外一种封锁状态2.比如，一个事务先执行了read_lock（x）操作，然后他可以通过执行write_lock(x)操作来升级该锁3.同样，一个事务先执行了write_lock(x)操作，然后他可以通过执行read_lock（x）操作来降级该锁2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分

25、布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术封锁准则和锁的转换2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术 T1 T2read_lock(Y);read_item(Y);unlock(Y);write_lock(X);read_item(X);X:=X+Y;write_item(X);unlock(X);read_lock(X);read_item(X);unlock(X);write_lock(Y);read_item(Y);Y:=Y+X;write_item(Y

26、);unlock(Y);（a）两个事务T1和T2初始值：X=20，Y=30串行调度T1，T2的结果：X=50，Y=80串行调度T2，T1的结果：X=70，Y=50（b）T1和T2可能的串行调度的结果 T1 T2read_lock(Y);read_item(Y);unlock(Y);write_lock(X);read_item(X);X:=X+Y;write_item(X);unlock(X);read_lock(X);read_item(X);unlock(X);write_lock(Y);read_item(Y);Y:=Y+X;write_item(Y);unlock(Y);这个调度S的结

27、果：X=50，Y=50(不可串行化)（c）使用锁的一个不可串行化调度的结果满足封锁规则不满足封锁规则不能保证产生串行能保证产生串行化调度化调度简单的分布式封锁方法类似集中式，将同一数据的全部副本封锁，然后更新，之后解除全部封锁缺点是各站点间进行相当大的数据传输，如果有N个站点，就有：N个请求封锁的消息N个封锁授权的消息N个更新数据的消息N个更新执行了的消息N个解除封锁的消息2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术分布式数据库基本封锁算法主站点封锁法定义一个站点为主站点，负责系统全部封锁管理所

28、有站点都向主站点提出封锁和解锁请求，由它去处理缺点有：所有封锁请求都送往单个站点，容易由于超负荷造成“瓶颈”主站点故障会使系统瘫痪，封锁消息都在这里，制约了系统可用性和可靠性2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术分布式数据库基本封锁算法主副本封锁法不指定主站点，指定数据项的主副本事务对某个数据项进行操作时，先对其主副本进行封锁，再进行操作主副本封锁，意味着所有的副本都被封锁主副本按使用情况，尽量就近分布可减少站点的负荷,使得各站点比较均衡可减少传输量快照方法和上一章讲的类似2.1 基于封锁

29、的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术分布式数据库基本封锁算法基本基本2PL协议协议如果一个事务所有的封锁操作（读写）都在第一个解锁操作之前，那么它就遵守2PL协议事务的执行中Lock的管理分成两个阶段上升阶段(成长阶段)：获取Lock阶段（只能获取锁）收缩阶段(衰退阶段）：释放Lock阶段（只能解锁）封锁点是指事务获得了它所要求的所有锁，并且还没有开始释放任何锁的时刻如果允许锁的转换，锁的升级必须在成长阶段进行，锁的降级必须在锁的衰退阶段进行。2PL可以保证事务执行的可串行性.2.2 2PL 2PL协议

30、（两阶段封锁协议）协议（两阶段封锁协议）2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术开始加锁点结束事务执行过程获得锁释放锁两阶段封锁协议2.2 基本基本2PL2PL协议协议2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术基本2PL协议实现的难点锁管理器必须要知道事务的锁点位置级联撤销(cascading aborts)如果事务在开始释放Lock后又Abort时,将引起级联撤销(cascading aborts)（其他访问这个数据项的事务也被撤销）保守2PL要求事务在开始执行之前就持有所有它要访问的数据项上的锁事务要预先

31、声明它的读集和写集大多数2PL调度器实现的是严格2PL(S2PL)事务在提交或者撤销之前，绝对不释放任何一个写锁事务结束时（提交或者撤销），同时释放所有的锁2.2 2PL 2PL协议协议2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术严酷2PL事务T在提交或撤销之前，不能释放任何一个锁（写锁或者读锁），因此它比严格2PL更容易实现保守2PL与严酷2PL之间的区别前者，事务必须在开始之前封锁它所需要的所有数据项，因此，一旦事务开始就处在收缩阶段后者,直到事务结束（提交或者撤销）后才开始解锁，因此，事务一直处于扩张阶段，直到结束2.2 2PL 2PL协议协议2

32、2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术开始结束事务执行阶段获得锁释放锁 严格2PL(Strict Two-phase Locking)协议数据项使用2.2 2PL 2PL协议协议2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术并发控制子系统可以负责产生读锁和写锁操作（以严格2PL协议为例）当事务T发出read_item(x)操作请求时，系统会代表T调用read_lock(x)操作如果Lock(x)的状态是被另外一个事务T持有写锁，那么系统会把T放到数据项X的等待队列中；否则，系统同意read_lock(x)的请求，从

33、而允许事务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)的状态是没有锁，那么系统同意write_lock(x)的请求，进而允许事务T执行write_item(x)操作2.2 2PL 2PL协议协议2 2 分布式数据库系统并发控制机制的封锁

34、技术分布式数据库系统并发控制机制的封锁技术集中式集中式2PL的实现方法的实现方法2PL很容易扩展到分布式DBMS(无论复制或无复制DDB),其最简单的方法是选择一个站点(主站点)做Lock管理器,其他站点上的事务管理器都需要与该选出的站点Lock管理器通信,而不是与本站点Lock管理器通信.这就是集中式2PL方法2.3 2PL 2PL协议的实现方法协议的实现方法2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术术语协调事务管理器(coordinating TM)：事务原发站点数据处理器(data processor，DP)：其他参与站点中心站点LM：主站点锁管

35、理器2.3 2PL 2PL协议的实现方法协议的实现方法2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术参与站点的数据处理器协调 TM中心站点 LM加锁请求允许加锁操作操作结束释放封锁集中式2PL的通信结构中心站点LM不需要向DP发送操作2.3 2PL 2PL协议的实现方法协议的实现方法2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术集中式集中式2PL的实现方法的实现方法主副本主副本2PL的实现方法的实现方法是主站点2PL的直接扩展选择一组站点做Lock管理器每个Lock管理器管理一组数据(即每个数据选择一个站点作自己的Lo

36、ck管理器)事务管理器根据Lock申请的数据对象分别向这些数据的LM发出锁申请必须先为每一个数据项确定一个主副本站点，然后再向那个站点上的封锁管理程序发送封锁或释放锁的请求，目录的思想为分布式INGRES版本提出的，每个站点上要有一个复杂的目录2.3 2PL 2PL协议的实现方法协议的实现方法2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术特点每个站点都有LM无副本DDB上如同主副本2PL有冗余副本DDB上则使用ROWA控制协议与集中式相似，但有不同集中式中向中心站点封锁管理程序发送的信息，在分布式中发送给所有参与站点的封锁管理程序另外不同之处在于操作并不通

37、过协调者事务管理程序传到数据处理器，而是通过参与者的封锁管理程序参与者的数据处理器向协调者的事务管理程序发送“操作结束”信息另外一种方法，每个数据处理器执行自身解锁，并通知协调者事务管理程序的封锁管理程序2.3 2PL 2PL协议的实现方法协议的实现方法2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术分布式分布式2PL的实现方法的实现方法参与者 DPs加锁请求操作分布式2PL的通信结构协调者 TM参与者 LMs操作结束释放锁2.3 2PL 2PL协议的实现方法协议的实现方法2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术分

38、布式分布式2PL的实现方法的实现方法多粒度封锁封锁的粒度不是单一的一种粒度，而是有多种粒度可以定义多粒度树，根节点是整个数据库，叶节点表示最小的封锁粒度直接封锁事务对要进行读/写的数据对象直接申请加锁分层封锁DB中各数据对象从大到小存在一种层次关系,例如划分为DB,段,关系,元组,字段等 当封锁了外层数据对象时,蕴含着也同时封锁了它的所有内层数据对象数据项的显式封锁和隐式封锁2.4 多粒度封锁与意向锁多粒度封锁与意向锁2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术数据库段1段n.多级粒度树关系nn关系11.2.4 多粒度封锁与意向锁多粒度封锁与意向锁2 2

39、 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术2.4 多粒度封锁与意向锁多粒度封锁与意向锁2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术dbf1f2p11P12.p1nr111r11j r121r12j r1n1r1njp21P22.p2nr211r21j r221r22j r2n1r2nj用来说明多粒度级别封锁的粒度层次结构用来说明多粒度级别封锁的粒度层次结构例子假定事务T1要更新文件f1中的所有记录，T1请求并获得了f1上的一个写锁那么f1下面的页面和记录就获得了隐式写锁如果这时候，事务T2想从f1中的某个页面中读某个记

40、录，那么T2就要申请该记录上的读锁但是要确认这个读锁和已经存在锁的相容性，确认的方法就是要遍历该树：从记录到页，到文件最后到数据库，如果在任意时刻，在这些项中的任意一个上存在冲突锁，那么对记录的封锁请求就被拒绝，T2被阻止，要等待。2.4 多粒度封锁与意向锁多粒度封锁与意向锁2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术意向锁如果对一个节点加意向锁，则说明该节点的下层节点正在被封锁对任一节点封锁时，必须先对它的上层节点加意向锁意向锁的类型意向共享锁(IS)：指示在其后代节点上将会请求共享锁，即如果对某个对象加IS锁，表示它的后代节点拟加共享锁意向排它锁(I

41、X)：指示在其后代节点上将会请求排他锁，即如果对某个对象加IX锁，表示它的后代节点拟加排他锁共享意向排它锁(SIX)：指示当前节点处在共享方式的封锁中，但是在它的某些后代节点中将会请求排他锁。即如果对一个数据对象加SIX锁,表示对它加共享锁，再加IX锁（SIX=S+IX）。例如：对某个表加SIX锁，则表示该事务要读整个表（加S锁），同时会更新个别元组（加IX锁）2.4 多粒度封锁与意向锁多粒度封锁与意向锁2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术T2T1YYYYYY-YNNYNNSIXYNYYNNIXYYYYNYISYNNNNNXYNNYNYS-SIX

42、IXISXSXSIXSIXISY=yes，表示相容的请求 N=no，表示不相容的请求(a)数据锁的相容矩阵(b)锁的强度的偏序关系 锁的相容矩阵锁的相容矩阵2.4 多粒度封锁与意向锁多粒度封锁与意向锁2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术锁的强度：对其锁的强度：对其它锁的排斥程度它锁的排斥程度多粒度封锁协议的规则必须遵守锁的相容性规则必须首先封锁树的根节点，可以用任何一种方式的锁只有当节点N的父节点已经被事务T以IS或IX方式封锁后，节点N才可以被T以S或者IS方式封锁只有当节点N的父节点已经被事务T以IX或SIX方式封锁后，节点N才可以被T以X,

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

44、向锁2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术死锁发生的条件互斥条件：事务请求对资源的独占控制等待条件：事务已持有分配给它的资源,又去申请并等待别的资源非抢占条件：直到资源被持有它的事务释放前,不可能将资源强制从持有它的事务夺去循环等待条件：存在事务互相等待的等待圈死锁分类局部死锁：仅在一个站点上发生的死锁全局死锁：涉及多个站点的死锁(即等待圈由多个站点组成)3.1 全局死锁与等待图全局死锁与等待图3 3 分布式数据库系统中的死锁处理分布式数据库系统中的死锁处理事务T1持有对x的锁事务T2请求对x的锁事务T2持有对y的锁事务T1请求对y的锁站点A站点B

45、T2等待T1完成释放对x的锁T1等待T2完成释放对y的锁相互等待引起的全局死锁3.1 全局死锁与等待图全局死锁与等待图3 3 分布式数据库系统中的死锁处理分布式数据库系统中的死锁处理T1T2T3站点A：x1,y1站点C：z3站点B：y2,z2等待释放对y 的锁等待释放对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)多副本引起的三个站点间的死锁3.1 全局死锁与等待图全局死锁与等待图3 3 分布式数据库系统

46、中的死锁处理分布式数据库系统中的死锁处理等待图一种用来表示事务之间相互等待关系的有向图,是分析死锁的有用工具节点表示事务带有箭头的有向边表示“等待”关系如果等待图有回路，就说明有死锁等待图分类局部等待图(LWFG)全局等待图(GWFG)3.1 全局死锁与等待图全局死锁与等待图3 3 分布式数据库系统中的死锁处理分布式数据库系统中的死锁处理T1T3T2yxzT1等待T2释放对y的共享锁(s)T2等待T3释放对z的共享锁(s)T3等待T1释放对x的共享锁(s)上例的GWFG等待图3.1 全局死锁与等待图全局死锁与等待图3 3 分布式数据库系统中的死锁处理分布式数据库系统中的死锁处理(a)(b)T2

47、T1T1T2T4T3T4T3站点1站点2LWFG和GWFG之间的不同3.1 全局死锁与等待图全局死锁与等待图3 3 分布式数据库系统中的死锁处理分布式数据库系统中的死锁处理事务间的等待关系事务间的等待关系T1T2T3T4解决死锁的方法死锁预防，使引起死锁的必要条件不成立所有资源排序,按资源序列申请将所有并发事务排序,按标识符或开始时间有死锁危险时，事务退出已占有的资源，有两种方法等待-死亡(Wait-Die)：总是重启较年轻的事务(非占先权)受伤-等待(Wound-Wait)：年轻的等待年老的,较年轻的重启,而重启事务并不一定是目前正申请的事务(占先权)死锁检测 即检测死锁时循环等待的圈3.2

48、 死锁的预防方法死锁的预防方法3 3 分布式数据库系统中的死锁处理分布式数据库系统中的死锁处理等待-死亡模式如果Ti对已被Tj封锁的一数据项请求封锁的话，则只有在Ti比Tj年老时（TiTj），则Ti被终止并带有同一时间戳重新启动最好总是重新启动较年轻的事务允许较年老的事务去等待已持有资源的较年轻的事务但不允许较年轻的事务去等待较年老的事务受伤-等待模式如果Ti对已被Tj封锁的一数据项请求封锁的话，则只有在Ti比Tj年轻时（TiTj），才允许Ti等待否则，Ti比Tj年老（Ti 等待EX的事务号分布式死锁检测算法使用局部信息建造LWFG,该LWFG包含EX节点对每次接收到的信息,执行如下对LWFG

49、的修改对报文中的每个事务,若LWFG中不存在,则将其加入从EX节点开始,按照报文所给的信息,建立一个到下一个事务的边在新的LWFG中寻找不含EX的Loop,若存在,则检测到死锁在新的LWFG中找到含有EX的Loop,于是有潜在的死锁,再按规定向外传送信息3.3 死锁的检测和解决方法死锁的检测和解决方法3 3 分布式数据库系统中的死锁处理分布式数据库系统中的死锁处理基本概念不通过互斥来支持串行性，而是通过在事务启动时赋给时标（时间戳）来实现时标是用来唯一识别每个事务并允许排序的标识如果 ts(T1)ts(T2)ts(Tn),则调度器产生的序是:T1,T2,.Tn 规则如果T1的操作O1(x)和T

50、2的操作O2(x)是冲突操作,那么,O1在O2之前执行,当且仅当ts(T1)ts(T2)4.1 基于时标的并发控制方法基于时标的并发控制方法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术时标分配方法全局时标使用全局的单调递增的计数器全局的计数器维护是个难题局部时标每个站点基于其本地计数器自治地指定一个时标标识符由两部分组成：本地计数器值，站点标识符站点标识符是次要的，主要是本地计数器值可以使用站点系统时钟来代替计数器值4.1 基于时标的并发控制方法基于时标的并发控制方法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术时标法思想每个事务赋

51、一个唯一的时标，事务的执行等效于按时标次序串行执行如果发生冲突，是通过撤销并重新启动一个事务来解决的事务重新启动时，则赋予新的时标优点是没有死锁，不必设置锁封锁和死锁检测引起的通信开销也避免了但要求时标在全系统中是唯一的4.1 基于时标的并发控制方法基于时标的并发控制方法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术时标性质唯一性单调性全局唯一时间的形成与调整每个站点设置一个计数器,每发生一个事务,计数器加一发送报文时包含本地计数器值,近似同步各站点计数器4.1 基于时标的并发控制方法基于时标的并发控制方法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统

52、并发控制的时标技术4.1 基于时标的并发控制方法基于时标的并发控制方法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术 计数器X 初值X=0 计数器Y 初值Y=10 站点1 站点2 时标 A D 时标 TS(A)=TS(D)=因为XY E TS(E)=改X=Y+1=11 B TS(B)=F 因为YX TS(C)=C TS(F)=本地计数器 本地计数器 (或时钟)(或时钟)报文1报文2计数器计数器站点站点基本时标法基本时标法规则每个事务在本站点开始时赋予一个全局唯一时标在事务结束前，不对数据库进行物理更新事务的每个读操作或写操作都具有该事务的时标对每个数据项x,记下写

53、和读操作的最大时标，记为WTM(x)和RTM(x)如果事务被重新启动，则被赋予新的时标4.2 基本时标法基本时标法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术基本时标法执行过程令read_TS是事务对x进行读操作时的时标若read_TSWTM(x)，则拒绝该操作,事务重新启动否则,执行,令RTM(x)=maxRTM(x),read_TS令write_TS是事务对x进行写操作时的时标若write_TS RTM(x)或 write_TS WTM(x),则拒绝该操作,事务重新启动否则,执行,令WTM(x)=maxWTM(x),write_TS缺点是重启动多4.2 基本

54、时标法基本时标法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术基本思想一种消除重启动的方法通过缓冲年轻的操作，直至年长的操作执行完成，因此操作不会被拒绝，事务也绝不被重启动规则每个事务只在一个站点执行,它不能激活远程的程序,但是可以向远程站点发读/写请求站点i接收到来自不同站点j的读/写请求必须按时标顺序，即每个站点必须按时标顺序发送读/写数据请求，在传输中也不会改变这个顺序每个站点都为其它站点发来的读/写操作开辟一个缓冲区,分别保存接收到的读/写申请4.3 保守时标法保守时标法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术假定某个站

55、点k上,各个缓冲区队列都已不为空，即每个站点都已向它至少发送了一个读和一个写操作，就停止接收，处理在缓冲区中的操作假定站点i至少有一个缓冲的读和缓冲的写来自网中其它站点,根据规则2,Site i 知道没有年老的请求来自其它Site(因为按序接收,所以不可能有比此更年老的请求到来,年老的比年轻的先到)4.3 保守时标法保守时标法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术例子 已知站点i的缓冲区队列中有来自所有站点的读/写请求如下所示:站点1 站点2 站点3 站点n R11 R21 R31 Rn1 R12 R22 R32 R13 R23 R24 W11 W21 W

56、31 Wn1 W22 W32 Wn2 W234.3 保守时标法保守时标法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术执行步骤:(1)设RT=min(Rij),WT=min(Wij)(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

57、.若某个或某些W队列为空时,WT=04.3 保守时标法保守时标法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术存在问题和解决方法如果一个站点从来不向某个站点发送操作的话，那么执行过程中的假定就不符合，操作就无法进行。解决办法是，周期性的发送带有时标的空操作此方法要求网络上所有站点都连通，这在大系统中很难办到。为避免不必要的通信，可对无读写操作请求的站点，发送一个时标很大的空操作此方法过分保守，一律按照时序来进行，其中包括了不冲突的操作4.3 保守时标法保守时标法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术基本思想保存了已更新数据项的

58、旧值维护一个数据项的多个版本通过读取数据项的较老版本来维护可串行性，使得系统可以接受在其他技术中被拒绝的一些读操作写数据项时，写入一个新版本，老版本依然保存缺点需要更多的存储来维持数据库数据项的多个版本模式分类基于时标排序基于两阶段封锁5.1 多版本概念和思想多版本概念和思想5 5 分布式数据库系统并发控制的多版本技术分布式数据库系统并发控制的多版本技术数据项X的多版本X1,X2,X3,Xk系统保存的值Xi的值两种时标Read_TS(Xi):读时标，成功读取版本Xi的事务的时标，最大的一个Write_TS(Xi):写时标，写入版本Xi的值的事务的时标5.2 基于时标的多版本技术基于时标的多版本

59、技术5 5 分布式数据库系统并发控制的多版本技术分布式数据库系统并发控制的多版本技术多版本规则如果事务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

60、(Xi)中较大的一个5.2 基于时标的多版本技术基于时标的多版本技术5 5 分布式数据库系统并发控制的多版本技术分布式数据库系统并发控制的多版本技术图示写值v1v2v3Vn-1Vn5102092100若读 TS(Ri)=95,则读 的值若写TS(Wk)=93,则出现了v1v2v3Vn-1Vn510209210093v于是要拒绝TS(Wk),否则 TS(Ri)=95读的就是Vn-1,而不是v的值,但是按规定 TS(Ri)=95应该读的是v值三种锁方式读，写，验证四种锁状态读封锁（read_locked）写封锁（write_locked）验证封锁（certify_locked）未封锁（unlock

61、ed）锁相容性标准模式锁相容性（写锁和读锁）验证模式锁相容性（写锁、读锁和验证锁）5.3 采用验证锁的多版本两阶段封锁采用验证锁的多版本两阶段封锁5 5 分布式数据库系统并发控制的多版本技术分布式数据库系统并发控制的多版本技术5.3 采用验证锁的多版本两阶段封锁采用验证锁的多版本两阶段封锁5 5 分布式数据库系统并发控制的多版本技术分布式数据库系统并发控制的多版本技术 (a)读/写封锁模式的相容性表 读 写 读 写 是 否 否 否 读 写 验证 读 写 是 是 否 是 否 否 验证 否 否 否 (b)读/写/验证封锁模式的相容性表多版本2PL的思想当只有一个单独的事务T持有数据项上的写锁时，允

62、许其他事务T读该项X，这是通过给予每个项X的两个版本来实现的一个版本X是由一个已提交的事务写入的另一个版本X是每个事务T获得该数据项上写锁时创建的、当事务T持有这个写锁时，其他事务可以继续读X的已提交版本事务T可以写X的值，而不影响X已提交版本的值但是，一旦T准备提交，它必须在能够提交之前，得到持有写锁的数据项上的验证锁，要等写锁释放之后一旦获得验证锁，数据项的已提交版本X被置为版本X的值，版本X被丢弃，验证锁被释放。5.3 采用验证锁的多版本两阶段封锁采用验证锁的多版本两阶段封锁5 5 分布式数据库系统并发控制的多版本技术分布式数据库系统并发控制的多版本技术基本思想对于冲突操作不像悲观方法那

63、样采取挂起或拒绝的方法，而是让一个事务执行直到完成基于如下假设冲突的事务是少数（查询为主的系统中，冲突少于5%）大多数事务可以不受干扰地执行完毕6.1 基本思想和假设基本思想和假设6 6 分布式数据库系统并发控制的乐观方法分布式数据库系统并发控制的乐观方法6.2 执行阶段划分执行阶段划分6 6 分布式数据库系统并发控制的乐观方法分布式数据库系统并发控制的乐观方法 验证 读/计算 写/提交 读/计算 验证 写/提交 乐观法事务执行的各个阶段 悲观法事务执行的各个阶段事务的三个阶段读段/计算：在数据对象的局部副本上执行事务，这时其他事务不能存取此副本。事务从DB读数据，执行计算，并且确定写集数据项

64、的新值。写操作总是对局部副本，仅当验证通过后，在事务结束处，才将其写入DB。验证段：检验并发事务的可串性，该阶段验证修改应用是否引起完整性（一致性）的丢失，验证阶段通过，才能进入写段，否则事务重启动写段/提交：验证阶段通过，则把事务的更新应用于数据库，对数据进行更新，否则，忽略所有更新，并重新开始该事务6.2 执行阶段划分执行阶段划分6 6 分布式数据库系统并发控制的乐观方法分布式数据库系统并发控制的乐观方法验证使用数据项和事务上的时标只使用事务时标6.3 验证分类验证分类6 6 分布式数据库系统并发控制的乐观方法分布式数据库系统并发控制的乐观方法使用数据项和事务上的时标假设是一个完全冗余的D

65、B，事务在读期间把更新写入一个更新表事务时标：事务在启动执行时接受的具有唯一性的时标数据项时标：对该数据项最后写入的事务的时间戳算法假定：读集 写集，即写必须先读6.3 使用数据项和事务上的时标使用数据项和事务上的时标6 6 分布式数据库系统并发控制的乐观方法分布式数据库系统并发控制的乐观方法读阶段末，事务产生一个更新表u，包括读集的数据项，带有自身的时标写集数据项的新值该事务自身的时标验证阶段把更新表发送到每一站点，每个站点对是否确认该更新表进行表决，并把表决结果送回到该事务的源站点如源站点收到多数肯定票，则决定事务提交并通知各站点如多数表决是否定的，则把放弃更新表的决定通知所有站点，然后重

66、新启动该事务6.3 使用数据项和事务上的时标使用数据项和事务上的时标6 6 分布式数据库系统并发控制的乐观方法分布式数据库系统并发控制的乐观方法表决规则比较更新表u中数据项的时标与本地库中相应数据项的时标,全部相等则投赞成票不相等,投反对派票,因为此时可能本地写入数据项之前或之后,又有事务对数据项做了写操作表决结果若赞成票是大多数,则考虑Commit,并将结论发送给每个Site否则,其更新表无效,事务重启动6.3 使用数据项和事务上的时标使用数据项和事务上的时标6 6 分布式数据库系统并发控制的乐观方法分布式数据库系统并发控制的乐观方法更新表冲突表决规则比较u表中读集中数据项的时标与数据库中对应数据项的时标，如果不等，投否定票若相等，Site j在对u表做表决时,若存在Site k上的u表传送到Site j,使Site j处于对u的表决中若u中有与u冲突的更新表,当u中的时标大时,则反对 当u中的时标小时,则延迟表决若与u中无冲突数据项,则赞成原发Site投票 Site j更新表uDBU6.3 使用数据项和事务上的时标使用数据项和事务上的时标6 6 分布式数据库系统并发控制的乐观方法分