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

1、L/O/G/O第第5章分布式数据库中的并发控制章分布式数据库中的并发控制褚龙现褚龙现软件学院软件学院回回顾顾-两两阶阶段段提提交交协协议议v 基本思想基本思想 将本地原子性提交行为的效果扩展到分布式事务将本地原子性提交行为的效果扩展到分布式事务, , 保保证了分布式事务提交的原子性证了分布式事务提交的原子性, , 并在不损坏并在不损坏LogLog的情况的情况下下, , 实现快速故障恢复实现快速故障恢复, , 提高提高DDBDDB系统的可靠性系统的可靠性. . 第一阶段：表决阶段第一阶段：表决阶段 第二阶段：执行阶段第二阶段：执行阶段v 两类代理两类代理 协调者协调者(Coordinator)(

2、Coordinator)：提交和撤销事务的决定权，一：提交和撤销事务的决定权，一般是总代理般是总代理 参与者参与者(Participants)(Participants)：负责在本地数据库中执行写：负责在本地数据库中执行写操作，并且向协调者提出提交和撤销子事务的意向操作，并且向协调者提出提交和撤销子事务的意向软件学院软件学院回回顾顾-两两阶阶段段提提交交协协议议基基本本思思想想和和内内容容v 表决阶段表决阶段 目的是形成一个共同的决定目的是形成一个共同的决定 首先，协调者给所有参与者发送首先，协调者给所有参与者发送“准备准备”消息，进入等待状态消息，进入等待状态 其次，参与者收到其次，参与者收

3、到“准备准备”消息后，检查是否能够提交本地事务消息后，检查是否能够提交本地事务 如能，给协调者发送如能，给协调者发送“建议提交建议提交”消息消息, ,进入就绪状态进入就绪状态 如不能，给协调者发送如不能，给协调者发送“建议撤销建议撤销”消息，可以单方面撤销消息，可以单方面撤销 第三，协调者收到所有参与者的消息后，他就做出是否提交事务第三，协调者收到所有参与者的消息后，他就做出是否提交事务的决定，的决定， 只要有一个参与者投了反对票，就决定撤销整个事务，发送只要有一个参与者投了反对票，就决定撤销整个事务，发送“全局撤全局撤销销”消息给所有参与者，进入撤销状态消息给所有参与者，进入撤销状态 否则，

4、就决定提交整个事务，发送否则，就决定提交整个事务，发送“全局提交全局提交”消息给所有参与者，消息给所有参与者，进入提交状态进入提交状态v 执行阶段执行阶段 实现表决阶段的决定，提交或者撤销实现表决阶段的决定，提交或者撤销软件学院软件学院回回顾顾-分分布布式式数数据据库库中中的的数数据据更更新新多多站站点点数数据据更更新新 方法方法 ：站点：站点A A上有事务上有事务T T对对X X更新更新, X, X在在B1,BnB1,Bn和和C1,CmC1,Cm上有副本上有副本, , 则也要对这些则也要对这些副本更新副本更新 问题问题 多个站点同时更新不现实多个站点同时更新不现实( (每一个站点某一时刻每一

5、个站点某一时刻与站点与站点A A连通的概率小于连通的概率小于1 1） 对未连通站点上的副本更新增多时出错对未连通站点上的副本更新增多时出错, , 更新的更新的顺序也不一定是连通顺序顺序也不一定是连通顺序软件学院软件学院回回顾顾-分分布布式式数数据据库库中中的的数数据据更更新新主主文文本本更更新新v思想：指定主副本思想：指定主副本, , 修改只对主副本进行修改只对主副本进行, , 修修改辅助副本时改辅助副本时, , 也按在主副本上执行的更新顺也按在主副本上执行的更新顺序执行序执行v问题问题 修改传播必须在短时间内完成修改传播必须在短时间内完成, , 否则将获得否则将获得“过时过时”数据数据 主副

6、本不可用主副本不可用, , 引得其他副本也不可用引得其他副本也不可用软件学院软件学院回回顾顾-分分布布式式数数据据库库中中的的数数据据更更新新快快照照方方法法v 例子例子 Define Snapshot HP-Book as SELECT * FROM Book WHERE Price$100 REFRESH Every dayv 特点特点 快照不考虑数据的辅助副本快照不考虑数据的辅助副本, 只关心主文本和这个只关心主文本和这个主本上定义的多个快照主本上定义的多个快照 快照与视图一样可以定义为一个或多个主副本的部快照与视图一样可以定义为一个或多个主副本的部分或全部分或全部 快照可以完成复杂的查

7、询快照可以完成复杂的查询, 但又不阻止更新但又不阻止更新 查询操作可使用快照，也可使用主文本，对更新操查询操作可使用快照，也可使用主文本，对更新操作还是在主文本上进行作还是在主文本上进行软件学院软件学院并发控制的概念和理论并发控制的概念和理论分布式数据库系统并发控制的封锁技术分布式数据库系统并发控制的封锁技术12教教 学学 内内 容容软件学院软件学院教教 学学 目目 标标难难 点点理解并发控制的概念理解并发控制的概念重重点点 掌握基于封锁的并发控制方法掌握基于封锁的并发控制方法 理解理解2PL协议的实现方法协议的实现方法事务可串行化理论事务可串行化理论多粒度封锁与意向锁多粒度封锁与意向锁软件学

8、院软件学院5.1并并发发控控制制的的概概念念和和理理论论v并发控制的概念并发控制的概念v事务可串行化理论事务可串行化理论v分布式事务的可串行化调度测试分布式事务的可串行化调度测试v并发控制机制的常用方法及其分类并发控制机制的常用方法及其分类软件学院软件学院5.1.1 并并发发控控制制的的概概念念v 通常，数据库总有若干个事务在运行，这些事务可能通常，数据库总有若干个事务在运行，这些事务可能并发地存取相同的数据，称为事务的并发操作。并发地存取相同的数据，称为事务的并发操作。v 当数据库中有多个事务并发执行时，系统必须对并发当数据库中有多个事务并发执行时，系统必须对并发事务之间的相互作用加以控制，

9、这是通过并发控制机事务之间的相互作用加以控制，这是通过并发控制机制来实现的。制来实现的。v 并发控制就是负责正确协调并发事务的执行，保证这并发控制就是负责正确协调并发事务的执行，保证这种并发的存取操作不至于破坏数据库的完整性和一致种并发的存取操作不至于破坏数据库的完整性和一致性，确保并发执行的多个事务能够正确地运行并获得性，确保并发执行的多个事务能够正确地运行并获得正确的结果。正确的结果。v 分布式数据库中的并发控制解决多个分布式事务对数分布式数据库中的并发控制解决多个分布式事务对数据并发执行的正确性，保证数据库的完整性和一致性据并发执行的正确性，保证数据库的完整性和一致性。比集中式并发控制更

10、复杂。比集中式并发控制更复杂。软件学院软件学院5.1.1 并并发发控控制制的的概概念念集集中中式式DB环环境境 T1T1T2T2TnTnDBDB( (一致性一致性约束约束) )软件学院软件学院5.1.1 并并发发控控制制的的概概念念分分布布式式DB环环境境X XY YZ ZT1T1T2T2软件学院软件学院5.1.1 并并发发控控制制的的概概念念并并发发执执行行多处理器多处理器CPU1CPU2T1T2Time软件学院软件学院5.1.1 并并发发控控制制的的概概念念非非并并发发执执行行单处理器单处理器T1t1T2t2T1t3T2t4TimeCPU软件学院软件学院5.1.1 并并发发控控制制的的概概

11、念念并并发发控控制制问问题题之之一：一：丢丢失失更更新新UPDATE x70t6FIND xt2200t7UPDATE xt5x:=x*2t4x:=x-30t3FIND xt1100t0更新事务更新事务T2数据库中数据库中X的值的值更新事务更新事务T1时间时间注：其中注：其中FINDFIND表示从数据库中读值，表示从数据库中读值，UPDATEUPDATE表示把值写回到数据库表示把值写回到数据库T1T2T1T2，结果，结果140140，T2T1,T2T1,结果结果170170，得到结果是得到结果是200200，显然是不对的，显然是不对的，T1T1在在t t7 7丢失更新操作。丢失更新操作。软件学

12、院软件学院5.1.1 并并发发控控制制的的概概念念并并发发控控制制问问题题之之二：二：不不一一致致分分析析FIND xt270t5UPDATE xt4x:=x-30t3FIND xt1100t0更新事务更新事务T2数据库中数据库中A的值的值更新事务更新事务T1时间时间注：在时间注：在时间t5事务事务T2仍认为仍认为x的值是的值是100软件学院软件学院5.1.1 并并发发控控制制的的概概念念并并发发控控制制问问题题之之三：三：读读脏脏数数据据100t6x:=x-10t2ROLLBACKt5FIND x90t4UPDATE xt3FIND xt1100t0更新事务更新事务T2数据库中数据库中A的值

13、的值更新事务更新事务T1时间时间注：注： 事务事务T2依赖于事务依赖于事务T1的未完成更新的未完成更新软件学院软件学院5.1.2 事事务务可可串串行行化化理理论论v 事务事务T Ti i T Ti i= = i i, , i i 其中：其中： i i : : 操作符集合：操作符集合： R Ri i(x(x), ), W Wi i(x(x) U A) U Ai i, , C Ci i A Ai i, , C Ci i 是最后的操作符，只能是其一是最后的操作符，只能是其一1.1. i i : (: (冲突冲突) )操作有序执行，操作有序执行，R Ri i(x(x) ) i i W Wi i(x(x

14、) ) 或或 W Wi i(x(x) ) i i R Ri i(x(x) )软件学院软件学院5.1.2 事事务务可可串串行行化化理理论论v操作符集操作符集 读读Ri(x)和写和写Wi(x)动作序列动作序列v冲突动作冲突动作 R1(A) W2(A) W1(A) W2(A) R1(A) W2(A)v一个调度一个调度事务的一个操作序列称为一个调度，一般用事务的一个操作序列称为一个调度，一般用S表示表示比如，比如，S: R1(x),R2(y),W2(y),R2(x),W1(x),W2(x)软件学院软件学院5.1.2 事事务务可可串串行行化化理理论论例子例子已知：站点已知：站点1有数据有数据X，站点，站

15、点2有数据有数据Y约束：约束：X=Y 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.2 事事务务可可串串行行化化理理论论(X(X站点站点) )(Y(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 调

16、度调度S S1 1事务内事务内事务间事务间软件学院软件学院5.1.2 事事务务可可串串行行化化理理论论并并发发调调度度定定义义令令T= T= T T1 1,T,T2 2,T,Tn n 是一组事务是一组事务. T. T上的调度上的调度 S S 是是具有如下顺序关系具有如下顺序关系 T T的偏序，即的偏序，即S=S= T T , ,T T : :(1) (1) T T= = T Ti i(2) (2) T T i i(3) (3) 对于任意一组冲突操作对于任意一组冲突操作 p,q p,q S, S, 存在存在 p p q q 或或 q pq p关系关系软件学院软件学院5.1.2 事事务务可可串串行

17、行化化理理论论v 调度调度 一组事务的调度必须包含这些事务的所有操作一组事务的调度必须包含这些事务的所有操作 调度中某个事务的操作顺序必须保持与该事务原有调度中某个事务的操作顺序必须保持与该事务原有的顺序相同的顺序相同v 串行调度串行调度 一个事务的第一个动作是在另一个事务的最后一个一个事务的第一个动作是在另一个事务的最后一个动作完成后开始动作完成后开始. . 即调度中事务的各个操作不会交即调度中事务的各个操作不会交叉叉, , 每个事务相继执行每个事务相继执行. .v 一致性调度一致性调度 调度可以使得数据库从一个一致性状态转变为另一调度可以使得数据库从一个一致性状态转变为另一个一致性状态，则

18、称调度为一致性调度个一致性状态，则称调度为一致性调度软件学院软件学院5.1.2 事事务务可可串串行行化化理理论论v 调度等价调度等价 S1S1与与S2S2等价等价, , 也就是说也就是说, , 对于冲突操作对于冲突操作, , , Qi Qj, Qi Qj在在S1S1中成立中成立, , 同时同时 Qi Qj Qi Qj 在在S2S2中也成立中也成立v 可串行化调度可串行化调度 如果一个调度等价于某个串行调度，则该调度称如果一个调度等价于某个串行调度，则该调度称为可串行化调度。为可串行化调度。 也就是说，该调度可以通过一系列非冲突动作的也就是说，该调度可以通过一系列非冲突动作的交换操作使其成为串行

19、调度交换操作使其成为串行调度软件学院软件学院5.1.2 事事务务可可串串行行化化理理论论例例子子T1:Read(x）x=x+10Write(x)Read(y)y=y-15Write(y)mitT2:Read(x）x=x-20Write(x)Read(y)y=y*2Write(y)1. commit两个事务，定义如下：两个事务，定义如下：软件学院软件学院5.1.2 事事务务可可串串行行化化理理论论例例子：子：五五种种调调度度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),C2 S

20、2= 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),C2 S3= 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),C1 S4= 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),C1 S5= R2(x),x=x-20,W2(x), R1(x),x=x+10,

21、W1(x), R2(y),y=y*2,W2(y),C2 ,R1(y),y=y-15,W1(y),C1 软件学院软件学院5.1.2 事事务务可可串串行行化化理理论论v如果将事务提交延迟到两个事务操作完成之后执如果将事务提交延迟到两个事务操作完成之后执行，有：行，有：调度调度S1S1和和S4S4是串行调度是串行调度调度调度S2S2和和S1S1的冲突操作具有相同的顺序，因此的冲突操作具有相同的顺序，因此是等价调度；是等价调度；S2S2是可串行化调度，也是一致性是可串行化调度，也是一致性调度调度调度调度S3S3虽是一致调度，但是它不与虽是一致调度，但是它不与S1S1或或S4S4等价等价，所以，所以S3

22、S3不是可串行化调度不是可串行化调度调度调度S5S5和和S4S4等价，所以等价，所以S5S5是一致调度，也是可是一致调度，也是可串行化调度串行化调度软件学院软件学院5.1.2 事事务务可可串串行行化化理理论论v有以下推论：有以下推论：一个可串行化调度必定与某个串行调度等价，一个可串行化调度必定与某个串行调度等价，且是一致性调度且是一致性调度一致性调度不一定是可串行化调度一致性调度不一定是可串行化调度同一事务集几个可串行化调度，他们的结果未同一事务集几个可串行化调度，他们的结果未必相同必相同软件学院软件学院5.1.3 分分布式布式事务事务的可的可串行串行化调化调度测度测试试优先图优先图 P(S)

23、P(S)v调度调度 S 的优先图是一个有向图的优先图是一个有向图G(N,E) ，其中，其中 N: 一组节点一组节点N=T1T2,Tn, S中的事务中的事务 E: 一组有向边一组有向边E=e1,e2,en, Ti Tj 是图中是图中的一条边，当且仅当的一条边，当且仅当 p Ti, q Tj 使得使得p, q 冲突，并且冲突，并且 p S q软件学院软件学院5.1.3 分分布式布式事务事务的可的可串行串行化调化调度测度测试试测试调度测试调度S S的可串行化的可串行化v 对于调度对于调度 S S中的事务中的事务TiTi，在图中创建一个节点，在图中创建一个节点TiTiv 对于每一种这样的情形：如果对于

24、每一种这样的情形：如果S S中的在中的在TiTi执行了执行了W(X)W(X)操作操作后执行后执行TjTj的的R(X)R(X)操作，那么在优先图中创建一条边（操作，那么在优先图中创建一条边（TiTiTj Tj ）v 对于每一种这样的情形：如果对于每一种这样的情形：如果S S中的在中的在TiTi执行了执行了R(X)R(X)操作操作后执行后执行TjTj的的W(X)W(X)操作，那么在优先图中创建一条边（操作，那么在优先图中创建一条边（TiTiTj Tj ）v 对于每一种这样的情形：如果对于每一种这样的情形：如果S S中的在中的在TiTi执行了执行了W(X)W(X)操作操作后执行后执行TjTj的的W(

25、X)W(X)操作，那么在优先图中创建一条边（操作，那么在优先图中创建一条边（TiTiTj Tj ）v 当且仅当优先图中没有闭环时，调度当且仅当优先图中没有闭环时，调度S S是可串行化的是可串行化的软件学院软件学院5.1.3 分分布式布式事务事务的可的可串行串行化调化调度测度测试试测试调度测试调度S S的可串行化的可串行化v 优先图中存在环路，说明调度是不可串行化的，否则是可优先图中存在环路，说明调度是不可串行化的，否则是可串行化的。串行化的。v 环路是指有向图中每条边的起始节点（第一条边除外），环路是指有向图中每条边的起始节点（第一条边除外），都与前一条边的终止节点连接，而第一条边的起始节点于

26、都与前一条边的终止节点连接，而第一条边的起始节点于最后一条边的终止节点连接，即事务序列是以同一个节点最后一条边的终止节点连接，即事务序列是以同一个节点作为开始和结束的作为开始和结束的v 调度调度S S中事务中事务TiTi在事务在事务TjTj之前，与之前，与S S等价的调度中等价的调度中TiTi也必须也必须在在TjTj之前之前v 某项数据导致了调度中的一条边的生成，就把数据项标注某项数据导致了调度中的一条边的生成，就把数据项标注到优先图中这条边的旁边到优先图中这条边的旁边v 如果调度如果调度S S中不存在环路，那么就可能存在若干个与中不存在环路，那么就可能存在若干个与S S等价等价的串行调度的串

27、行调度软件学院软件学院5.1.3 分分布式布式事务事务的可的可串行串行化调化调度测度测试试S1的优先图的优先图S2的优先图的优先图S3的优先图的优先图S4的优先图的优先图S5的优先图的优先图XYXYXYXYXY存在环路存在环路软件学院软件学院5.1.3 分分布式布式事务事务的可的可串行串行化调化调度测度测试试例例子子v 考虑如下考虑如下3个事务：个事务： T1: Read(x); Write(x); Commit; T2: Write(x); Write(y); Read(z); Commit; T3: Read(x); Read(y); Read(z); Commit; 这这3个事务的一个调

28、度：个事务的一个调度：S= W2(x),W2(y),R2(z),C2,R1(x),W1(x),C1,R3(x), R3(y),R3(z),C3 优先图：优先图： T2 T1 T3无环，无环， S是串行调度。是串行调度。软件学院软件学院5.1.3 分分布式布式事务事务的可的可串行串行化调化调度测度测试试例例子子另外一个调度另外一个调度S:S= W2(x), R1(x),W1(x),C1,R3(x), W2(y), R3(y), R2(z), C2,R3(z),C3 先序图：先序图： T2 T1 T3无环，是可串调度。无环，是可串调度。软件学院软件学院5.1.3 分分布式布式事务事务的可的可串行串

29、行化调化调度测度测试试可可串串性性理理论论扩扩展展v 可串性理论可以直接扩展到无重复副本的分布式数据可串性理论可以直接扩展到无重复副本的分布式数据库中。库中。 事务在每个站点上的执行调度称作事务在每个站点上的执行调度称作局部调度局部调度 如果数据库无重复副本的分布式数据库，并且每个如果数据库无重复副本的分布式数据库，并且每个局部调度都是可串调度，只要这些局部调度的顺序局部调度都是可串调度，只要这些局部调度的顺序一致，则它们的并（全局调度）也是可串调度一致，则它们的并（全局调度）也是可串调度 但是有副本的情况下，就比较复杂。可能局部调度但是有副本的情况下，就比较复杂。可能局部调度是可串行化的，而

30、全局调度不是可串行化的。是可串行化的，而全局调度不是可串行化的。软件学院软件学院5.1.4 并并发控发控制机制机制的制的常用常用方法方法及其及其分类分类v 保证只产生可串行化调度的机制保证只产生可串行化调度的机制v 并发控制机制分类并发控制机制分类 按分配模式按分配模式(数据方式数据方式) 完全复制的完全复制的DBDB 部分复制部分复制DBDB或分片的或分片的DBDB 按网络类型按网络类型(通信方式通信方式) 广播能力的广播能力的 星型网星型网, , 环形网环形网 同步化原则同步化原则 建立在相互排斥地访问共享数据基础上的算法建立在相互排斥地访问共享数据基础上的算法 通过一些准则通过一些准则(

31、 (协议协议) )对事务进行排序的算法对事务进行排序的算法 悲观并发控制法（事务是相互冲突的），乐观并发控制法悲观并发控制法（事务是相互冲突的），乐观并发控制法（没有太多的事务相互冲突）（没有太多的事务相互冲突） 软件学院软件学院并发控制算法并发控制算法悲观法悲观法乐观法乐观法加锁法加锁法集中式加锁集中式加锁分布式加锁分布式加锁时标排序法时标排序法混合法混合法加锁法加锁法时序排序法时序排序法主副本加锁主副本加锁基本时标排序基本时标排序保守时标排序保守时标排序多版本时标排序多版本时标排序软件学院软件学院5.1.4 并并发控发控制机制机制的制的常用常用方法方法及其及其分类分类v 封锁法封锁法 事务

32、的同步化是通过对数据库的片断或者数据项进事务的同步化是通过对数据库的片断或者数据项进行物理或逻辑封锁来实现的行物理或逻辑封锁来实现的 封锁对象的大小通常称为封锁粒度封锁对象的大小通常称为封锁粒度 封锁方法的类型可以根据在哪里进行封锁来进一步封锁方法的类型可以根据在哪里进行封锁来进一步细分细分v 封锁法分类封锁法分类 集中式封锁方法集中式封锁方法 一个站点被指定为主站点，存放对整个数据库的封锁表，一个站点被指定为主站点，存放对整个数据库的封锁表，并且负责对全系统事务进行封锁并且负责对全系统事务进行封锁 主副本封锁法：主副本所在站点封锁主副本封锁法：主副本所在站点封锁 分布式封锁法：网络中的站点共

33、享锁的管理分布式封锁法：网络中的站点共享锁的管理软件学院软件学院5.2 分布分布式数式数据库据库系统系统并发并发控制控制机制机制的封的封锁技锁技术术v基于封锁的并发控制方法概述基于封锁的并发控制方法概述v2PL协议协议v2PL协议的实现方法协议的实现方法v多粒度封锁与意向锁多粒度封锁与意向锁软件学院软件学院5.2.1 基基于封于封锁的锁的并发并发控制控制方法方法概述概述基基本本思思想想和和概概念念v 基本思想基本思想 事务访问数据项之前要对该数据项封锁，如果已经事务访问数据项之前要对该数据项封锁，如果已经被其他事务锁定，就要等待，直到那个事务释放该被其他事务锁定，就要等待，直到那个事务释放该锁

34、为止锁为止v 锁的粒度锁的粒度 锁定数据项的范围锁定数据项的范围 数据项层次数据项层次 数据库记录中的一个字段值数据库记录中的一个字段值 一条数据库记录一条数据库记录 一个磁盘块（页面）一个磁盘块（页面） 一个完整的文件一个完整的文件 整个数据库整个数据库软件学院软件学院5.2.1 基基于封于封锁的锁的并发并发控制控制方法方法概述概述基基本本思思想想和和概概念念v 粒度对并发控制的影响粒度对并发控制的影响 大多数大多数DBMSDBMS缺省设置为记录锁或页面锁缺省设置为记录锁或页面锁 粒度小，并发度高，锁开销大粒度小，并发度高，锁开销大 数据项比较多，锁也多，解锁和封锁操作多，锁表存储空数据项比

35、较多，锁也多，解锁和封锁操作多，锁表存储空间大（如存储读写时间戳）间大（如存储读写时间戳） 粒度大，并发度低，锁开销小粒度大，并发度低，锁开销小 如果是磁盘块，封锁磁盘块中的一条记录如果是磁盘块，封锁磁盘块中的一条记录B B的事务的事务T T必须封必须封锁整个磁盘块锁整个磁盘块 而另外一个事务而另外一个事务S S如果要封锁记录如果要封锁记录C,C,而而C C也在磁盘块中，由也在磁盘块中，由于磁盘块正在封锁中，于磁盘块正在封锁中，S S只能等待只能等待 如果是封锁粒度是一条记录的话，就不用等待了如果是封锁粒度是一条记录的话，就不用等待了软件学院软件学院5.2.1 基基于封于封锁的锁的并发并发控制

36、控制方法方法概述概述基基本本思思想想和和概概念念v如何来确定粒度如何来确定粒度 取决于参与事务的类型取决于参与事务的类型 如果参与事务都访问少量的记录，那么选择如果参与事务都访问少量的记录，那么选择一个记录作为粒度较好一个记录作为粒度较好 如果参与事务都访问同一文件中大量的记录如果参与事务都访问同一文件中大量的记录，则最好采用块或者文件作为粒度，则最好采用块或者文件作为粒度软件学院软件学院5.2.1 基基于封于封锁的锁的并发并发控制控制方法方法概述概述基基本本思思想想和和概概念念v锁的类型：锁的类型： 共享锁：共享锁：ShareShare锁，锁，S S锁或者读锁锁或者读锁 排它锁：排它锁：eX

37、clusiveeXclusive锁，锁，X X锁，拒绝锁或写锁。锁，拒绝锁或写锁。 更新锁：更新锁：UpdateUpdate锁，锁，U U锁锁v锁的选择：锁的选择： 数据项既可以读也可以写数据项既可以读也可以写. .则要用则要用X X锁锁 如果数据项只可以读如果数据项只可以读. .则要用则要用 S S锁锁. .软件学院软件学院5.2.1 基基于封于封锁的锁的并发并发控制控制方法方法概述概述基基本本思思想想和和概概念念v 锁的操作锁的操作 Read_lock(x):读锁读锁 Write_lock(x)：写锁：写锁 unlock(x)：解锁：解锁v 数据项的状态数据项的状态 read_locked

38、: 读锁读锁 Write_locked:写锁写锁v 具体操作方法具体操作方法 在系统锁表中记录关于锁的信息在系统锁表中记录关于锁的信息 锁表中每条记录有四个字段：锁表中每条记录有四个字段： 锁状态是上面两种，没有被封锁的数据项，在系统表中没有锁状态是上面两种，没有被封锁的数据项，在系统表中没有记录记录软件学院软件学院5.2.1 基基于封于封锁的锁的并发并发控制控制方法方法概述概述封封锁锁准准则则和和锁锁的的转转换换v封锁准则：封锁准则： 事务事务T T在执行任何在执行任何read_itemread_item（x x）操作之前，必须先执）操作之前，必须先执行行read_lock(x)read_l

39、ock(x)或者或者write_lock(x)write_lock(x)操作操作 事务事务T T在执行任何在执行任何write_itemwrite_item（x x）操作之前，必须先）操作之前，必须先执行执行write_lock(x)write_lock(x)操作操作 如果事务如果事务T T执行执行read_lock(x)read_lock(x)操作操作, ,数据项数据项x x必须没有加必须没有加锁或者已经加了读锁，否则事务锁或者已经加了读锁，否则事务T T的这个操作不能进行的这个操作不能进行 如果事务如果事务T T执行执行write_lock(x)write_lock(x)操作操作, ,数据

40、项数据项x x必须没有必须没有加锁，否则事务加锁，否则事务T T的这个操作不能进行的这个操作不能进行软件学院软件学院5.2.1 基基于封于封锁的锁的并发并发控制控制方法方法概述概述封封锁锁准准则则和和锁锁的的转转换换v 封锁准则：封锁准则：事务事务T T在完成所有在完成所有read_itemread_item（x x）和）和write_itemwrite_item（x x）操作之后，必须执行操作之后，必须执行unlock(x)unlock(x)操作操作如果事务如果事务T T已经持有数据项已经持有数据项x x上的一个读锁或者一个写上的一个读锁或者一个写锁，那么它不能再执行锁，那么它不能再执行re

41、ad_lock(x)read_lock(x)操作操作如果事务如果事务T T已经持有数据项已经持有数据项x x上的一个读锁或者一个写上的一个读锁或者一个写锁，那么它不能再执行锁，那么它不能再执行write_lock(x)write_lock(x)操作操作如果事务如果事务T T没有持有数据项没有持有数据项x x上的一个读锁或者一个写上的一个读锁或者一个写锁，那么它不能执行锁，那么它不能执行unlock(x)unlock(x)操作操作软件学院软件学院5.2.1 基基于封于封锁的锁的并发并发控制控制方法方法概述概述封封锁锁准准则则和和锁锁的的转转换换v锁的转换锁的转换特定条件下，一个已经在数据项特定条

42、件下，一个已经在数据项x x上持有锁的事务上持有锁的事务T T ，允许将某种封锁状态转换为另外一种封锁状态允许将某种封锁状态转换为另外一种封锁状态比如，一个事务先执行了比如，一个事务先执行了read_lockread_lock（x x）操作，然操作，然后他可以通过执行后他可以通过执行write_lock(x)write_lock(x)操作来升级该锁操作来升级该锁1.1. 同样，一个事务先执行了同样，一个事务先执行了write_lock(x) write_lock(x) 操作，然操作，然后他可以通过执行后他可以通过执行read_lockread_lock（x x） 操作来降级该锁操作来降级该锁软

43、件学院软件学院满足封锁规则不满足封锁规则不能保证产生串行能保证产生串行化调度化调度 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=5

44、0，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的的结果：结果：X=50，Y=50(不可串行化不可串

45、行化)（c）使用锁的一个不可串行化调度的结果）使用锁的一个不可串行化调度的结果软件学院软件学院5.2.1 基基于封于封锁的锁的并发并发控制控制方法方法概述概述分分布布式式数数据据库库基基本本封封锁锁算算法法v简单的分布式封锁方法简单的分布式封锁方法类似集中式，将同一数据的全部副本封锁，然后更新，之后解类似集中式，将同一数据的全部副本封锁，然后更新，之后解除全部封锁除全部封锁缺点是各站点间进行相当大的数据传输，如果有缺点是各站点间进行相当大的数据传输，如果有N N个站点，就有个站点，就有N N个请求封锁的消息个请求封锁的消息N N个封锁授权的消息个封锁授权的消息N N个更新数据的消息个更新数据的

46、消息N N个更新执行了的消息个更新执行了的消息N N个解除封锁的消息个解除封锁的消息软件学院软件学院5.2.1 基基于封于封锁的锁的并发并发控制控制方法方法概述概述分分布布式式数数据据库库基基本本封封锁锁算算法法v主站点封锁法主站点封锁法定义一个站点为主站点，负责系统全部封锁管理定义一个站点为主站点，负责系统全部封锁管理所有站点都向主站点提出封锁和解锁请求，由它去所有站点都向主站点提出封锁和解锁请求，由它去处理处理缺点有：缺点有：所有封锁请求都送往单个站点，容易由于超负荷造成所有封锁请求都送往单个站点，容易由于超负荷造成“瓶颈瓶颈”主站点故障会使系统瘫痪，封锁消息都在这里，制约了系统主站点故障

47、会使系统瘫痪，封锁消息都在这里，制约了系统可用性和可靠性可用性和可靠性软件学院软件学院5.2.1 基基于封于封锁的锁的并发并发控制控制方法方法概述概述分分布布式式数数据据库库基基本本封封锁锁算算法法v主副本封锁法主副本封锁法不指定主站点，指定数据项的主副本不指定主站点，指定数据项的主副本事务对某个数据项进行操作时，先对其主副本进行事务对某个数据项进行操作时，先对其主副本进行封锁，再进行操作封锁，再进行操作主副本封锁，意味着所有的副本都被封锁主副本封锁，意味着所有的副本都被封锁主副本按使用情况，尽量就近分布主副本按使用情况，尽量就近分布可减少站点的负荷可减少站点的负荷, ,使得各站点比较均衡使得

48、各站点比较均衡可减少传输量可减少传输量v快照方法快照方法软件学院软件学院5.2.2 2PL协议协议（两（两阶段阶段封锁封锁协议）协议）基基本本2PL协协议议v 如果一个事务所有的封锁操作（读写）都在第一个解锁操如果一个事务所有的封锁操作（读写）都在第一个解锁操作之前，那么它就遵守作之前，那么它就遵守2PL协议协议v 事务的执行中事务的执行中Lock的管理分成两个阶段的管理分成两个阶段 上升阶段上升阶段(成长阶段成长阶段)：获取：获取Lock阶段（只能获取锁）阶段（只能获取锁） 收缩阶段收缩阶段(衰退阶段）：释放衰退阶段）：释放Lock阶段（只能解锁）阶段（只能解锁）v 封锁点是指事务获得了它所

49、要求的所有锁，并且还没有开封锁点是指事务获得了它所要求的所有锁，并且还没有开始释放任何锁的时刻始释放任何锁的时刻v 如果允许锁的转换，锁的升级必须在成长阶段进行，锁的如果允许锁的转换，锁的升级必须在成长阶段进行，锁的降级必须在锁的衰退阶段进行。降级必须在锁的衰退阶段进行。 2PL可以保证事务执行的可串行性可以保证事务执行的可串行性.软件学院软件学院5.2.2 2PL协议协议（两（两阶段阶段封锁封锁协议）协议）两两阶阶段段封封锁锁协协议议开始开始加锁点加锁点结束结束事务执行过程事务执行过程获得锁获得锁释放锁释放锁软件学院软件学院5.2.2 2PL协议协议（两（两阶段阶段封锁封锁协议）协议）v 基

50、本基本2PL协议实现的难点协议实现的难点 锁管理器必须要知道事务的锁点位置锁管理器必须要知道事务的锁点位置v 级联撤销级联撤销(cascading aborts) 如果事务在开始释放如果事务在开始释放Lock后又后又Abort时时, 将引起级联撤销将引起级联撤销(cascading aborts)（其他访问这个数据项的事务也被撤销）（其他访问这个数据项的事务也被撤销）v 保守保守2PL 要求事务在开始执行之前就持有所有它要访问的数据项上的锁要求事务在开始执行之前就持有所有它要访问的数据项上的锁 事务要预先声明它的读集和写集事务要预先声明它的读集和写集v 大多数大多数2PL调度器实现的是严格调度

51、器实现的是严格2PL(S2PL) 事务在提交或者撤销之前，绝对不释放任何一个写锁事务在提交或者撤销之前，绝对不释放任何一个写锁 事务结束时（提交或者撤销），同时释放所有的锁事务结束时（提交或者撤销），同时释放所有的锁软件学院软件学院5.2.2 2PL协议协议（两（两阶段阶段封锁封锁协议）协议）v 严酷严酷2PL 事务事务T T在提交或撤销之前，不能释放任何一个锁（写锁在提交或撤销之前，不能释放任何一个锁（写锁或者读锁），因此它比严格或者读锁），因此它比严格2PL2PL更容易实现更容易实现v 保守保守2PL与严酷与严酷2PL之间的区别之间的区别 前者，事务必须在开始之前封锁它所需要的所有数据前者

52、，事务必须在开始之前封锁它所需要的所有数据项，因此，一旦事务开始就处在收缩阶段项，因此，一旦事务开始就处在收缩阶段 后者后者, ,直到事务结束（提交或者撤销）后才开始解锁，直到事务结束（提交或者撤销）后才开始解锁，因此，事务一直处于扩张阶段，直到结束因此，事务一直处于扩张阶段，直到结束软件学院软件学院5.2.2 2PL协议协议（两（两阶段阶段封锁封锁协议）协议）开始开始结束结束事务执行阶段事务执行阶段获得锁获得锁释放锁释放锁数据项使用数据项使用 严格严格2PL(Strict Two-phase Locking)协议协议软件学院软件学院5.2.2 2PL协议协议（两（两阶段阶段封锁封锁协议）协议

53、）v 并发控制子系统并发控制子系统可以负责产生读锁和写锁操作（以严格可以负责产生读锁和写锁操作（以严格2PL协议为例）协议为例）当事务当事务T发出发出read_item(x)操作请求时，系统会代表操作请求时，系统会代表T调用调用read_lock(x)操作操作如果如果Lock(x)的状态是被另外一个事务的状态是被另外一个事务T持有写锁，那么系统会把持有写锁，那么系统会把T放到数据项放到数据项X的的等待队列中；否则，系统同意等待队列中；否则，系统同意read_lock(x)的请求，从而允许事务的请求，从而允许事务T执行执行read_item(x)操作操作另外一个方面，如果事务另外一个方面，如果事

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

55、的状态是没有锁，那么系统同意write_lock(x)的请求，进而允许事务的请求，进而允许事务T执行执行write_item(x)操作操作软件学院软件学院5.2.3 2PL协议协议的实的实现方现方法法集集中中式式2PL的的实实现现方方法法v 2PL很容易扩展到分布式很容易扩展到分布式DBMS(无论复制或无复制无论复制或无复制DDB), v 其最简单的方法是选择一个站点其最简单的方法是选择一个站点(主站点主站点)做做Lock管管理器理器, 其他站点上的事务管理器都需要与该选出的站其他站点上的事务管理器都需要与该选出的站点点Lock管理器通信管理器通信, 而不是与本站点而不是与本站点Lock管理器

56、通管理器通信信. 这就是集中式这就是集中式2PL方法方法软件学院软件学院5.2.3 2PL协协议议的的实实现现方方法法术术语语 协调事务管理器协调事务管理器(coordinating TM) ： 事务原发站点事务原发站点 数据处理器数据处理器(data processor，DP) ：其他参与站点其他参与站点 中心站点中心站点LM：主站点锁管理器主站点锁管理器软件学院软件学院5.2.3 2PL协协议议的的实实现现方方法法集集中中式式2PL的的实实现现方方法法参与站点的参与站点的数据处理器数据处理器协调协调 TM中心站点中心站点 LM加锁请求加锁请求允许加锁允许加锁操作操作操作结束操作结束释放封锁

57、释放封锁集中式集中式2PL的通信结构的通信结构中心站点中心站点LMLM不需要不需要向向DPDP发送发送操作操作软件学院软件学院5.2.3 2PL协协议议的的实实现现方方法法主主副副本本2PL的的实实现现方方法法v 是主站点是主站点2PL的直接扩展的直接扩展 选择一组站点做选择一组站点做Lock管理器管理器 每个每个Lock管理器管理一组数据管理器管理一组数据(即每个数据选择一个站点作自即每个数据选择一个站点作自己的己的Lock管理器管理器) 事务管理器根据事务管理器根据Lock申请的数据对象分别向这些数据的申请的数据对象分别向这些数据的LM发发出锁申请出锁申请 必须先为每一个数据项确定一个主副

58、本站点，然后再向那个必须先为每一个数据项确定一个主副本站点，然后再向那个站点上的封锁管理程序发送封锁或释放锁的请求，目录的思站点上的封锁管理程序发送封锁或释放锁的请求，目录的思想想v 为分布式为分布式INGRES版本提出的，每个站点上要有一个版本提出的，每个站点上要有一个复杂的目录复杂的目录软件学院软件学院5.2.3 2PL协协议议的的实实现现方方法法分分布布式式2PL的的实实现现方方法法v 特点特点 每个站点都有每个站点都有LMLM 无副本无副本DDBDDB上如同主副本上如同主副本2PL2PL 有冗余副本有冗余副本DDBDDB上则使用上则使用ROWAROWA控制协议控制协议v 与集中式相似，

59、但有不同与集中式相似，但有不同 集中式中向中心站点封锁管理程序发送的信息，在分布式中集中式中向中心站点封锁管理程序发送的信息，在分布式中发送给所有参与站点的封锁管理程序发送给所有参与站点的封锁管理程序 另外不同之处在于操作并不通过协调者事务管理程序传到数另外不同之处在于操作并不通过协调者事务管理程序传到数据处理器，而是通过参与者的封锁管理程序据处理器，而是通过参与者的封锁管理程序 参与者的数据处理器向协调者的事务管理程序发送参与者的数据处理器向协调者的事务管理程序发送“操作结操作结束束”信息信息 另外一种方法，每个数据处理器执行自身解锁，并通知协调另外一种方法，每个数据处理器执行自身解锁，并通

60、知协调者事务管理程序的封锁管理程序者事务管理程序的封锁管理程序软件学院软件学院5.2.3 2PL协协议议的的实实现现方方法法分分布布式式2PL的的实实现现方方法法参与者参与者 DPs加锁请求加锁请求操作操作分布式分布式2PL的通信结构的通信结构协调者协调者 TM参与者参与者 LMs操作结束操作结束释放锁释放锁软件学院软件学院5.2.4 多多粒粒度度封封锁锁与与意意向向锁锁v 多粒度封锁多粒度封锁 封锁的粒度不是单一的一种粒度，而是有多种粒度封锁的粒度不是单一的一种粒度，而是有多种粒度 可以定义多粒度树，根节点是整个数据库，叶节点表可以定义多粒度树，根节点是整个数据库，叶节点表示最小的封锁粒度示