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

/1101.并发控制的概念和理论2.分布式数据库系统并发控制的封锁技术3.分布式数据库系统中的死锁处理4.分布式数据库系统并发控制的时标技术5.分布式数据库系统并发控制的多版本技术6.分布式数据库系统并发控制的乐观方法分布式数据库中的并发控制1/110•通常，数据库总有若干个事务在运行，这些事务可能并发地存取相同的数据，称为事务的并发操作。•当数据库中有多个事务并发执行时，系统必须对并发事务之间的相互作用加以控制，这是通过并发控制机制来实现的。•并发控制就是负责正确协调并发事务的执行，保证这种并发的存取操作不至于破坏数据库的完整性和一致性，确保并发执行的多个事务能够正确地运行并获得正确的结果。•分布式数据库中的并发控制解决多个分布式事务对数据并发执行的正确性，保证数据库的完整性和一致性。比集中式并发控制更复杂。1.1并发控制的概念1并发控制的概念和理论2/110集中式DB环境T1T2…TnDB(一致性约束)1.1并发控制的概念1并发控制的概念和理论3/110分布式DB环境XYZT1T21.1并发控制的概念1并发控制的概念和理论4/110•多处理器CPU1CPU2T1T2Time1.1并发控制的概念1并发控制的概念和理论并发执行5/110•单处理器T1t1T2t2T1t3T2t4TimeCPU1.1并发控制的概念1并发控制的概念和理论非并发执行6/110UPDATEx70t6FINDxt2200t7UPDATExt5x:=x*2t4x:=x-30t3FINDxt1100t0更新事务T2数据库中X的值更新事务T1时间注：其中FIND表示从数据库中读值，UPDATE表示把值写回到数据库T1T2，结果140，T2T1,结果170，得到结果是200，显然是不对的，T1在t7丢失更新操作。1.1并发控制的概念1并发控制的概念和理论并发控制问题之一：丢失更新7/110FINDxt270t5UPDATExt4x:=x-30t3FINDxt1100t0更新事务T2数据库中A的值更新事务T1时间注：在时间t5事务T2仍认为x的值是1001.1并发控制的概念1并发控制的概念和理论并发控制问题之二：不一致分析8/110100t6x:=x-10t2ROLLBACKt5FINDx90t4UPDATExt3FINDxt1100t0更新事务T2数据库中A的值更新事务T1时间注：事务T2依赖于事务T1的未完成更新1.1并发控制的概念1并发控制的概念和理论并发控制问题之三：依赖于未提交更新（读脏数据）9/110•事务TiTi={i,i}其中：1.i:操作符集合：{Ri(x),Wi(x)}U{Ai,Ci}2.Ai,Ci是最后的操作符，只能是其一3.i:(冲突)操作有序执行，Ri(x)iWi(x)或Wi(x)iRi(x)1.2事务可串行化理论1并发控制的概念和理论10/110•操作符集读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并发控制的概念和理论11/110T1T21(T1)aX5(T2)cX2(T1)Xa+1006(T2)X2c3(T1)bY7(T2)dY4(T1)Yb+1008(T2)Y2d先序关系例子已知：站点1有数据X，站点2有数据Y约束：X=Y1.2事务可串行化理论1并发控制的概念和理论12/110(X站点)(Y站点)1(T1)aX2(T1)Xa+1005(T2)cX3(T1)bY6(T2)X2c4(T1)Yb+1007(T2)dY8(T2)Y2d初值:X=Y=0,结果:X=Y=200调度S1事务内事务间13/110令T={T1,T2,…,Tn}是一组事务.T上的调度S是具有如下顺序关系T的偏序，即S={T,T}:(1)T=Ti(2)Ti(3)对于任意一组冲突操作p,qS,存在pq或qp关系并发调度定义i=1NNi=11.2事务可串行化理论1并发控制的概念和理论14/110•调度–一组事务的调度必须包含这些事务的所有操作–调度中某个事务的操作顺序必须保持与该事务原有的顺序相同•串行调度–一个事务的第一个动作是在另一个事务的最后一个动作完成后开始.即调度中事务的各个操作不会交叉,每个事务相继执行.•一致性调度–调度可以使得数据库从一个一致性状态转变为另一个一致性状态，则称调度为一致性调度1.2事务可串行化理论1并发控制的概念和理论15/110•调度等价–S1与S2等价,也就是说,对于冲突操作,Oi,Oj,OiOj在S1中成立,同时OiOj在S2中也成立•可串行化调度–如果一个调度等价于某个串行调度，则该调度称为可串行化调度。–也就是说，该调度可以通过一系列非冲突动作的交换操作使其成为串行调度1.2事务可串行化理论1并发控制的概念和理论16/110例子•两个事务，定义如下：T1:1.Read(x）2.x=x+103.Write(x)4.Read(y)5.y=y-156.Write(y)7.commit1.2事务可串行化理论1并发控制的概念和理论T2:1.Read(x）2.x=x-203.Write(x)4.Read(y)5.y=y*26.Write(y)7.commit17/110五种调度：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}S2={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,W1(x),R2(y),y=y*2,W2(y),C2,R1(y),y=y-15,W1(y),C1}1.2事务可串行化理论1并发控制的概念和理论18/110•如果将事务提交延迟到两个事务操作完成之后执行，有：–调度S1和S4是串行调度–调度S2和S1的冲突操作具有相同的顺序，因此是等价调度；S2是可串行化调度，也是一致性调度–调度S3虽是一致调度，但是它不与S1或S4等价，所以S3不是可串行化调度–调度S5和S4等价，所以S5是一致调度，也是可串行化调度1.2事务可串行化理论1并发控制的概念和理论19/110•有以下推论：–一个可串行化调度必定与某个串行调度等价，且是一致性调度–一致性调度不一定是可串行化调度–同一事务集几个可串行化调度，他们的结果未必相同1.2事务可串行化理论1并发控制的概念和理论20/110优先图P(S)•调度S的优先图是一个有向图G(N,E)，其中–N:一组节点N={T1T2,…,Tn},S中的事务–E:一组有向边E={e1,e2,…,en},TiTj是图中的一条边，当且仅当pTi,qTj使得p,q冲突，并且pSq1.3分布式事务的可串行化调度测试1并发控制的概念和理论21/110测试调度S的可串行化•对于调度S中的事务Ti，在图中创建一个节点Ti•对于每一种这样的情形：如果S中的在Ti执行了W(X)操作后执行Tj的R(X)操作，那么在优先图中创建一条边（Ti→Tj）•对于每一种这样的情形：如果S中的在Ti执行了R(X)操作后执行Tj的W(X)操作，那么在优先图中创建一条边（Ti→Tj）•对于每一种这样的情形：如果S中的在Ti执行了W(X)操作后执行Tj的W(X)操作，那么在优先图中创建一条边（Ti→Tj）•当且仅当优先图中没有闭环时，调度S是可串行化的1.3分布式事务的可串行化调度测试1并发控制的概念和理论22/110测试调度S的可串行化•优先图中存在环路，说明调度是不可串行化的，否则是可串行化的。•环路是指有向图中每条边的起始节点（第一条边除外），都与前一条边的终止节点连接，而第一条边的起始节点于最后一条边的终止节点连接，即事务序列是以同一个节点作为开始和结束的•调度S中事务Ti在事务Tj之前，与S等价的调度中Ti也必须在Tj之前•某项数据导致了调度中的一条边的生成，就把数据项标注到优先图中这条边的旁边•如果调度S中不存在环路，那么就可能存在若干个与S等价的串行调度1.3分布式事务的可串行化调度测试1并发控制的概念和理论23/1101.3分布式事务的可串行化调度测试1并发控制的概念和理论T1T2T1T2T1T2T1T2T1T2S1的优先图S2的优先图S3的优先图S4的优先图S5的优先图XYXYXYXYXY存在环路24/110举例•考虑如下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}优先图：T2T1T3无环，S是串行调度。1.3分布式事务的可串行化调度测试1并发控制的概念和理论25/110另外一个调度S’:S={W2(x),R1(x),W1(x),C1,R3(x),W2(y),R3(y),R2(z),C2,R3(z),C3}先序图：T2T1T3无环，是可串调度。1.3分布式事务的可串行化调度测试1并发控制的概念和理论26/110可串性理论扩展•可串性理论可以直接扩展到无重复副本的分布式数据库中。–事务在每个站点上的执行调度称作局部调度–如果数据库无重复副本的分布式数据库，并且每个局部调度都是可串调度，只要这些局部调度的顺序一致，则它们的并（全局调度）也是可串调度–但是有副本的情况下，就比较复杂。可能局部调度是可串行化的，而全局调度不是可串行化的。1.3分布式事务的可串行化调度测试1并发控制的概念和理论27/110•保证只产生可串行化调度的机制•并发控制机制分类–按分配模式(数据方式)•完全复制的DB•部分复制DB或分片的DB–按网络类型(通信方式)•广播能力的•星型网,环形网–同步化原则•建立在相互排斥地访问共享数据基础上的算法•通过一些准则(协议)对事务进行排序的算法•悲观并发控制法（事务是相互冲突的），乐观并发控制法（没有太多的事务相互冲突）1.4并发控制机制的常用方法及其分类1并发控制的概念和理论28/110并发控制算法悲观法加锁法集中式加锁主副本加锁分布式加锁时标排序法基本时标排序多版本时标排序保守时标排序混合法乐观法加锁法时序排序法并发控制算法的分类29/110•基于封锁法–事务的同步化是通过对数据库的片断或者数据项进行物理或逻辑封锁来实现的–封锁对象的大小通常称为封锁粒度–封锁方法的类型可以根据在哪里进行封锁来进一步细分•封锁法分类–集中式封锁方法•一个站点被指定为主站点，存放对整个数据库的封锁表，并且负责对全系统事务进行封锁–主副本封锁法：主副本所在站点封锁–分布式封锁法：网络中的站点共享锁的管理1.4并发控制机制的常用方法及其分类1并发控制的概念和理论30/110•基于时标法–事物的顺序是由时标排序的方法组织的，并在内部维护一致性–排序是通过对事务和数据项进行分配时标来实现的•封锁法分类–基本时标排序算法–多版本时标排序算法–保守时标排序算法•混合方法1.4并发控制机制的常用方法及其分类1并发控制的概念和理论31/110基本思想和概念•基本思想–事务访问数据项之前要对该数据项封锁，如果