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

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-10t2ROL

5、LBACKt5FIND 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 事务可串行

6、化理论事务可串行化理论1 1 并发控制的概念和理论并发控制的概念和理论 操作符集 读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 (T

7、2) Y 2d先序关系例子例子已知：站点1有数据X，站点2有数据Y约束：X=Y1.2 事务可串行化理论事务可串行化理论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) 对于任意一

8、组冲突操作 p,q S, 存在 p q 或 q p关系并发调度定义i=1NNi=11.2 事务可串行化理论事务可串行化理论1 1 并发控制的概念和理论并发控制的概念和理论 调度 一组事务的调度必须包含这些事务的所有操作 调度中某个事务的操作顺序必须保持与该事务原有的顺序相同 串行调度 一个事务的第一个动作是在另一个事务的最后一个动作完成后开始. 即调度中事务的各个操作不会交叉, 每个事务相继执行. 一致性调度 调度可以使得数据库从一个一致性状态转变为另一个一致性状态，则称调度为一致性调度1.2 事务可串行化理论事务可串行化理论1 1 并发控制的概念和理论并发控制的概念和理论 调度等价 S1与S

9、2等价, 也就是说, 对于冲突操作, , Oi Oj在S1中成立, 同时 Oi Oj 在S2中也成立 可串行化调度 如果一个调度等价于某个串行调度，则该调度称为可串行化调度。 也就是说，该调度可以通过一系列非冲突动作的交换操作使其成为串行调度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

10、-203. Write(x)4. Read(y)5. y=y*26. Write(y)7. 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=

11、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=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是可串行化调

12、度，也是一致性调度调度S3虽是一致调度，但是它不与S1或S4等价，所以S3不是可串行化调度调度S5和S4等价，所以S5是一致调度，也是可串行化调度1.2 事务可串行化理论事务可串行化理论1 1 并发控制的概念和理论并发控制的概念和理论有以下推论：一个可串行化调度必定与某个串行调度等价，且是一致性调度一致性调度不一定是可串行化调度同一事务集几个可串行化调度，他们的结果未必相同1.2 事务可串行化理论事务可串行化理论1 1 并发控制的概念和理论并发控制的概念和理论优先图 P(S) 调度 S 的优先图是一个有向图G(N,E) ，其中 N: 一组节点N=T1T2,Tn, S中的事务 E: 一组有向边E

13、=e1,e2,en, Ti Tj 是图中的一条边，当且仅当 p Ti, q Tj 使得p, q 冲突，并且 p S q1.3 分布式事务的可串行化调度测试分布式事务的可串行化调度测试1 1 并发控制的概念和理论并发控制的概念和理论测试调度S的可串行化 对于调度 S中的事务Ti，在图中创建一个节点Ti 对于每一种这样的情形：如果S中的在Ti执行了W(X)操作后执行Tj的R(X)操作，那么在优先图中创建一条边（TiTj ） 对于每一种这样的情形：如果S中的在Ti执行了R(X)操作后执行Tj的W(X)操作，那么在优先图中创建一条边（TiTj ） 对于每一种这样的情形：如果S中的在Ti执行了W(X)操

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

15、优先图中这条边的旁边 如果调度S中不存在环路，那么就可能存在若干个与S等价的串行调度1.3 分布式事务的可串行化调度测试分布式事务的可串行化调度测试1 1 并发控制的概念和理论并发控制的概念和理论1.3 分布式事务的可串行化调度测试分布式事务的可串行化调度测试1 1 并发控制的概念和理论并发控制的概念和理论T1T2T1T2T1T2T1T2T1T2S1的优先图S2的优先图S3的优先图S4的优先图S5的优先图XYXYXYXYXY存在环路存在环路举例 考虑如下3个事务： T1: Read(x); Write(x); Commit; T2: Write(x); Write(y); Read(z); C

16、ommit; 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 分布式事务的可串行化调度测试分布式事务的可串行化调度测试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 分布式事务的

17、可串行化调度测试分布式事务的可串行化调度测试1 1 并发控制的概念和理论并发控制的概念和理论可串性理论扩展 可串性理论可以直接扩展到无重复副本的分布式数据库中。 事务在每个站点上的执行调度称作局部调度 如果数据库无重复副本的分布式数据库，并且每个局部调度都是可串调度，只要这些局部调度的顺序一致，则它们的并（全局调度）也是可串调度 但是有副本的情况下，就比较复杂。可能局部调度是可串行化的，而全局调度不是可串行化的。1.3 分布式事务的可串行化调度测试分布式事务的可串行化调度测试1 1 并发控制的概念和理论并发控制的概念和理论 保证只产生可串行化调度的机制 并发控制机制分类 按分配模式(数据方式)

18、 完全复制的DB 部分复制DB或分片的DB 按网络类型(通信方式) 广播能力的 星型网, 环形网 同步化原则 建立在相互排斥地访问共享数据基础上的算法 通过一些准则(协议)对事务进行排序的算法 悲观并发控制法（事务是相互冲突的），乐观并发控制法（没有太多的事务相互冲突） 1.4 并发控制机制的常用方法及其分类并发控制机制的常用方法及其分类1 1 并发控制的概念和理论并发控制的概念和理论并发控制算法悲观法乐观法加锁法集中式加锁分布式加锁时标排序法混合法加锁法时序排序法主副本加锁基本时标排序保守时标排序多版本时标排序并发控制算法的分类 封锁法 事务的同步化是通过对数据库的片断或者数据项进行物理或逻

19、辑封锁来实现的 封锁对象的大小通常称为封锁粒度 封锁方法的类型可以根据在哪里进行封锁来进一步细分 封锁法分类 集中式封锁方法 一个站点被指定为主站点，存放对整个数据库的封锁表，并且负责对全系统事务进行封锁 主副本封锁法：主副本所在站点封锁 分布式封锁法：网络中的站点共享锁的管理1.4 并发控制机制的常用方法及其分类并发控制机制的常用方法及其分类1 1 并发控制的概念和理论并发控制的概念和理论基本思想和概念 基本思想 事务访问数据项之前要对该数据项封锁，如果已经被其他事务锁定，就要等待，直到那个事务释放该锁为止 锁的粒度 锁定数据项的范围 数据项层次 数据库记录中的一个字段值 一条数据库记录 一

20、个磁盘块（页面） 一个完整的文件 整个数据库2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术基本思想和概念 粒度对并发控制的影响 大多数DBMS缺省设置为记录锁或页面锁 粒度小，并发度高，锁开销大 数据项比较多，锁也多，解锁和封锁操作多，锁表存储空间大（如存储读写时间戳） 粒度大，并发度低，锁开销小 如果是磁盘块，封锁磁盘块中的一条记录B的事务T必须封锁整个磁盘块 而另外一个事务S如果要封锁记录C,而C也在磁盘块中，由于磁盘块正在封锁中，S只能等待 如果是封锁粒度是一条记录的话，就不用等待了2.1

21、基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术基本思想和概念 如何来确定粒度 取决于参与事务的类型 如果参与事务都访问少量的记录，那么选择一个记录作为粒度较好 如果参与事务都访问同一文件中大量的记录，则最好采用块或者文件作为粒度2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术 锁的类型： 共享锁：Share锁，S锁或者读锁 排它锁：eXclusive锁，X锁，拒绝锁或写锁。 更新锁：Update锁，U锁 锁的选

22、择： 数据项既可以读也可以写.则要用X锁 如果数据项只可以读.则要用 S锁.2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术基本思想和概念 锁的操作 Read_lock(x):读锁 Write_lock(x)：写锁 unlock(x)：解锁 数据项的状态 read_locked: 读锁 Write_locked:写锁 具体操作方法 在系统锁表中记录关于锁的信息 锁表中每条记录有四个字段： 锁状态是上面两种，没有被封锁的数据项，在系统表中没有记录2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法

23、概述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执行write_lock(x)操作,数据项x必须没有加锁，否则事务T的这个操作不能进行2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2

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

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

26、的并发控制方法概述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);unlock(Y);（a）两个事务T1和T2初始值：X=20，Y=30串行调度T1，T2的结果： X=50，Y=80串行

27、调度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的结果：X=50，Y=50(不可串行化)（c）使用锁的一个不可串行化调度的结果满足封锁规则不满足封锁规则不能保证产

28、生串行能保证产生串行化调度化调度简单的分布式封锁方法类似集中式，将同一数据的全部副本封锁，然后更新，之后解除全部封锁缺点是各站点间进行相当大的数据传输，如果有N个站点，就有：N个请求封锁的消息N个封锁授权的消息N个更新数据的消息N个更新执行了的消息N个解除封锁的消息2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术分布式数据库基本封锁算法主站点封锁法定义一个站点为主站点，负责系统全部封锁管理所有站点都向主站点提出封锁和解锁请求，由它去处理缺点有：所有封锁请求都送往单个站点，容易由于超负荷造成“瓶颈”主

29、站点故障会使系统瘫痪，封锁消息都在这里，制约了系统可用性和可靠性2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术分布式数据库基本封锁算法主副本封锁法不指定主站点，指定数据项的主副本事务对某个数据项进行操作时，先对其主副本进行封锁，再进行操作主副本封锁，意味着所有的副本都被封锁主副本按使用情况，尽量就近分布可减少站点的负荷,使得各站点比较均衡可减少传输量快照方法和上一章讲的类似2.1 基于封锁的并发控制方法概述基于封锁的并发控制方法概述2 2 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发

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

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

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

33、封锁技术开始结束事务执行阶段获得锁释放锁 严格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)的请求，从而允许事务T执行read_item(x)操作 另外一个方面，如果事

34、务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 分布式数据库系统并发控制机制的封锁技术分布式数据库系统并发控制机制的封锁技术集中式集中式2P

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

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

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

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

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

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

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

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

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

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

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

46、数据库系统中的死锁处理事务T1持有对x的锁事务T2请求对x的锁事务T2持有对y的锁事务T1请求对y的锁站点A站点BT2等待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：re

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

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

49、 受伤-等待(Wound-Wait) ：年轻的等待年老的, 较年轻的重启,而重启事务并不一定是目前正申请的事务 (占先权) 死锁检测 即检测死锁时循环等待的圈3.2 死锁的预防方法死锁的预防方法3 3 分布式数据库系统中的死锁处理分布式数据库系统中的死锁处理 等待-死亡模式 如果Ti对已被Tj封锁的一数据项请求封锁的话，则只有在Ti比Tj年老时（TiTj），则Ti被终止并带有同一时间戳重新启动 最好总是重新启动较年轻的事务 允许较年老的事务去等待已持有资源的较年轻的事务 但不允许较年轻的事务去等待较年老的事务 受伤-等待模式 如果Ti对已被Tj封锁的一数据项请求封锁的话，则只有在Ti比Tj年轻

50、时（TiTj），才允许Ti等待 否则，Ti比Tj年老（Ti 等待EX的事务号 分布式死锁检测算法 使用局部信息建造LWFG, 该LWFG包含EX节点 对每次接收到的信息, 执行如下对LWFG的修改 对报文中的每个事务, 若LWFG中不存在, 则将其加入 从EX节点开始, 按照报文所给的信息, 建立一个到下一个事务的边 在新的LWFG中寻找不含EX的Loop, 若存在, 则检测到死锁 在新的LWFG中找到含有EX的Loop, 于是有潜在的死锁, 再按规定向外传送信息3.3 死锁的检测和解决方法死锁的检测和解决方法3 3 分布式数据库系统中的死锁处理分布式数据库系统中的死锁处理 基本概念 不通过互

51、斥来支持串行性，而是通过在事务启动时赋给时标（时间戳）来实现 时标是用来唯一识别每个事务并允许排序的标识 如果 ts(T1) ts(T2) ts(Tn), 则调度器产生的序是: T1,T2, . Tn 规则 如果T1的操作O1(x)和T2的操作O2(x)是冲突操作, 那么, O1在O2之前执行, 当且仅当ts(T1)ts(T2)4.1 基于时标的并发控制方法基于时标的并发控制方法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术 时标分配方法 全局时标 使用全局的单调递增的计数器 全局的计数器维护是个难题 局部时标 每个站点基于其本地计数器自治地指定一个时标 标识符由

52、两部分组成：本地计数器值，站点标识符 站点标识符是次要的，主要是本地计数器值 可以使用站点系统时钟来代替计数器值4.1 基于时标的并发控制方法基于时标的并发控制方法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术 时标法思想 每个事务赋一个唯一的时标，事务的执行等效于按时标次序串行执行 如果发生冲突，是通过撤销并重新启动一个事务来解决的 事务重新启动时，则赋予新的时标 优点是没有死锁，不必设置锁 封锁和死锁检测引起的通信开销也避免了 但要求时标在全系统中是唯一的4.1 基于时标的并发控制方法基于时标的并发控制方法4 4 分布式数据库系统并发控制的时标技术分布式数据库

53、系统并发控制的时标技术 时标性质 唯一性 单调性 全局唯一时间的形成与调整 每个站点设置一个计数器, 每发生一个事务, 计数器加一 发送报文时包含本地计数器值, 近似同步各站点计数器4.1 基于时标的并发控制方法基于时标的并发控制方法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术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

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

55、(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 基本时标法基本时标法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术 基本思想 一种消除重启动的方法 通过缓冲年轻的操作，直至年长的操作执行完成，因此操作不会被拒绝，事务也绝不被重启动 规则 每个事务只在一个站点执行

56、, 它不能激活远程的程序, 但是可以向远程站点发读/写请求 站点i接收到来自不同站点j的读/写请求必须按时标顺序，即每个站点必须按时标顺序发送读/写数据请求，在传输中也不会改变这个顺序 每个站点都为其它站点发来的读/写操作开辟一个缓冲区, 分别保存接收到的读/写申请4.3 保守时标法保守时标法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术 假定某个站点k上,各个缓冲区队列都已不为空，即每个站点都已向它至少发送了一个读和一个写操作，就停止接收，处理在缓冲区中的操作 假定站点i至少有一个缓冲的读和缓冲的写来自网中其它站点, 根据规则2, Site i 知道没有年老的请

57、求来自其它Site(因为按序接收, 所以不可能有比此更年老的请求到来, 年老的比年轻的先到)4.3 保守时标法保守时标法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术例子 已知站点i的缓冲区队列中有来自所有站点的读/写请求如下所示: 站点1 站点2 站点3 站点n R11 R21 R31 Rn1 R12 R22 R32 R13 R23 R24 W11 W21 W31 Wn1 W22 W32 Wn2 W234.3 保守时标法保守时标法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术执行步骤: (1) 设RT=min(Rij), WT= m

58、in(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. 若某个或某些W队列为空时, WT=04.3 保守时标法保守时标法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术存在问题和解决方

59、法 如果一个站点从来不向某个站点发送操作的话，那么执行过程中的假定就不符合，操作就无法进行。解决办法是，周期性的发送带有时标的空操作 此方法要求网络上所有站点都连通，这在大系统中很难办到。为避免不必要的通信，可对无读写操作请求的站点，发送一个时标很大的空操作 此方法过分保守，一律按照时序来进行，其中包括了不冲突的操作4.3 保守时标法保守时标法4 4 分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的时标技术 基本思想 保存了已更新数据项的旧值 维护一个数据项的多个版本 通过读取数据项的较老版本来维护可串行性，使得系统可以接受在其他技术中被拒绝的一些读操作 写数据项时，写入一个新版本

60、，老版本依然保存 缺点 需要更多的存储来维持数据库数据项的多个版本 模式分类 基于时标排序 基于两阶段封锁5.1 多版本概念和思想多版本概念和思想5 5 分布式数据库系统并发控制的多版本技术分布式数据库系统并发控制的多版本技术 数据项X的多版本 X1, X2, X3, Xk 系统保存的值 Xi的值 两种时标 Read_TS(Xi): 读时标，成功读取版本Xi的事务的时标，最大的一个 Write_TS(Xi): 写时标，写入版本Xi的值的事务的时标5.2 基于时标的多版本技术基于时标的多版本技术5 5 分布式数据库系统并发控制的多版本技术分布式数据库系统并发控制的多版本技术 多版本规则 如果事务