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

1,并发控制的概念和理论分布式数据库系统并发控制的封锁技术分布式数据库系统中的死锁处理分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的多版本技术分布式数据库系统并发控制的乐观方法,分布式数据库中的并发控制,2,通常，数据库总有若干个事务在运行，这些事务可能并发地存取相同的数据，称为事务的并发操作。当数据库中有多个事务并发执行时，系统必须对并发事务之间的相互作用加以控制，这是通过并发控制机制来实现的。并发控制就是负责正确协调并发事务的执行，保证这种并发的存取操作不至于破坏数据库的完整性和一致性，确保并发执行的多个事务能够正确地运行并获得正确的结果。分布式数据库中的并发控制解决多个分布式事务对数据并发执行的正确性，保证数据库的完整性和一致性。比集中式并发控制更复杂。,3,集中式DB环境,T1T2Tn,DB(一致性约束),4,分布式DB环境,X,Y,Z,T1,T2,5,多处理器,并发执行,6,单处理器,非并发执行,7,UPDATEx,70,t6,FINDx,t2,200,t7,UPDATEx,t5,x:=x*2,t4,x:=x-30,t3,FINDx,t1,100,t0,更新事务T2,数据库中X的值,更新事务T1,时间,注：其中FIND表示从数据库中读值，UPDATE表示把值写回到数据库T1T2，结果140，T2T1,结果170，得到结果是200，显然是不对的，T1在t7丢失更新操作。,并发控制问题之一：丢失更新,8,FINDx,t2,70,t5,UPDATEx,t4,x:=x-30,t3,FINDx,t1,100,t0,更新事务T2,数据库中A的值,更新事务T1,时间,注：在时间t5事务T2仍认为x的值是100,并发控制问题之二：不一致分析,9,100,t6,x:=x-10,t2,ROLLBACK,t5,FINDx,90,t4,UPDATEx,t3,FINDx,t1,100,t0,更新事务T2,数据库中A的值,更新事务T1,时间,注：事务T2依赖于事务T1的未完成更新,并发控制问题之三：依赖于未提交更新（读脏数据）,10,事务TiTi=i,i其中：i:操作符集合：Ri(x),Wi(x)UAi,CiAi,Ci是最后的操作符，只能是其一i:(冲突)操作有序执行，Ri(x)iWi(x)或Wi(x)iRi(x),11,操作符集读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),12,T1T21(T1)aX5(T2)cX2(T1)Xa+1006(T2)X2c3(T1)bY7(T2)dY4(T1)Yb+1008(T2)Y2d,先序关系,例子已知：站点1有数据X，站点2有数据Y约束：X=Y,13,(X站点)(Y站点)1(T1)aX2(T1)Xa+1005(T2)cX3(T1)bY6(T2)X2c4(T1)Yb+1007(T2)dY8(T2)Y2d初值:X=Y=0,结果:X=Y=200,调度S1,事务内事务间,14,令T=T1,T2,Tn是一组事务.T上的调度S是具有如下顺序关系T的偏序，即S=T,T:(1)T=Ti(2)Ti(3)对于任意一组冲突操作p,qS,存在pq或qp关系,并发调度定义,i=1,N,N,i=1,15,调度一组事务的调度必须包含这些事务的所有操作调度中某个事务的操作顺序必须保持与该事务原有的顺序相同串行调度一个事务的第一个动作是在另一个事务的最后一个动作完成后开始.即调度中事务的各个操作不会交叉,每个事务相继执行.一致性调度调度可以使得数据库从一个一致性状态转变为另一个一致性状态，则称调度为一致性调度,16,调度等价S1与S2等价,也就是说,对于冲突操作,OiOj在S1中成立,同时OiOj在S2中也成立可串行化调度如果一个调度等价于某个串行调度，则该调度称为可串行化调度。也就是说，该调度可以通过一系列非冲突动作的交换操作使其成为串行调度,17,例子两个事务，定义如下：T1:Read(x）x=x+10Write(x)Read(y)y=y-15Write(y)commit,T2:Read(x）x=x-20Write(x)Read(y)y=y*2Write(y)commit,18,五种调度：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,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,19,如果将事务提交延迟到两个事务操作完成之后执行，有：调度S1和S4是串行调度调度S2和S1的冲突操作具有相同的顺序，因此是等价调度；S2是可串行化调度，也是一致性调度调度S3虽是一致调度，但是它不与S1或S4等价，所以S3不是可串行化调度调度S5和S4等价，所以S5是一致调度，也是可串行化调度,20,有以下推论：一个可串行化调度必定与某个串行调度等价，且是一致性调度一致性调度不一定是可串行化调度同一事务集几个可串行化调度，他们的结果未必相同,21,优先图P(S),调度S的优先图是一个有向图G(N,E)，其中N:一组节点N=T1T2,Tn,S中的事务E:一组有向边E=e1,e2,en,TiTj是图中的一条边，当且仅当pTi,qTj使得p,q冲突，并且pTj），才允许Ti等待否则，Ti比Tj年老（Ti等待EX的事务号分布式死锁检测算法使用局部信息建造LWFG,该LWFG包含EX节点对每次接收到的信息,执行如下对LWFG的修改对报文中的每个事务,若LWFG中不存在,则将其加入从EX节点开始,按照报文所给的信息,建立一个到下一个事务的边在新的LWFG中寻找不含EX的Loop,若存在,则检测到死锁在新的LWFG中找到含有EX的Loop,于是有潜在的死锁,再按规定向外传送信息,78,基本概念不通过互斥来支持串行性，而是通过在事务启动时赋给时标（时间戳）来实现时标是用来唯一识别每个事务并允许排序的标识如果ts(T1)ts(T2)ts(Tn),则调度器产生的序是:T1,T2,.Tn规则如果T1的操作O1(x)和T2的操作O2(x)是冲突操作,那么,O1在O2之前执行,当且仅当ts(T1)XTS(C)=CTS(F)=本地计数器本地计数器(或时钟)(或时钟),报文1,报文2,计数器,站点,83,基本时标法,规则每个事务在本站点开始时赋予一个全局唯一时标在事务结束前，不对数据库进行物理更新事务的每个读操作或写操作都具有该事务的时标对每个数据项x,记下写和读操作的最大时标，记为WTM(x)和RTM(x)如果事务被重新启动，则被赋予新的时标,84,基本时标法执行过程令read_TS是事务对x进行读操作时的时标若read_TSWTM(x)，则拒绝该操作,事务重新启动否则,执行,令RTM(x)=maxRTM(x),read_TS令write_TS是事务对x进行写操作时的时标若write_TSRTM(x)或write_TSWTM(x),则拒绝该操作,事务重新启动否则,执行,令WTM(x)=maxWTM(x),write_TS缺点是重启动多,85,基本思想一种消除重启动的方法通过缓冲年轻的操作，直至年长的操作执行完成，因此操作不会被拒绝，事务也绝不被重启动规则每个事务只在一个站点执行,它不能激活远程的程序,但是可以向远程站点发读/写请求站点i接收到来自不同站点j的读/写请求必须按时标顺序，即每个站点必须按时标顺序发送读/写数据请求，在传输中也不会改变这个顺序每个站点都为其它站点发来的读/写操作开辟一个缓冲区,分别保存接收到的读/写申请,86,假定某个站点k上,各个缓冲区队列都已不为空，即每个站点都已向它至少发送了一个读和一个写操作，就停止接收，处理在缓冲区中的操作假定站点i至少有一个缓冲的读和缓冲的写来自网中其它站点,根据规则2,Sitei知道没有年老的请求来自其它Site(因为按序接收,所以不可能有比此更年老的请求到来,年老的比年轻的先到),87,例子已知站点i的缓冲区队列中有来自所有站点的读/写请求如下所示:站点1站点2站点3站点nR11R21R31Rn1R12R22R32R13R23R24W11W21W31Wn1W22W32Wn2W23,88,执行步骤:(1)设RT=min(Rij),WT=min(Wij)(2)按下法处理缓冲区中的Rij和Wija.若队列中有(Rij)WT的Rij,则顺序执行这些Rij，执行完删掉b.若队列中有(Wij)当Tj验证时也正处于验证的事务cTj本身,106,对于所有TS(Ti)Tj的读集和写集bTj启动时TNC的值,称为Start(Tj)cTj结束其读段时的TNC值,称为Finish(Tj)TS(Tj)：只有在写段之后(验证成功)才把此唯一的时标赋给Tj,仅当将TS(Tj)赋给Tj后,TNC值才增值.Finish(Tj)与Start(Tj)无变化,说明在其执行期间没有事务完成写段验证方式集中式分布式,108,集中式验证Finish(Ti)Finish(Tj)时Ti写集(Tj写集UTj读集)=,TS(Ti)Start(Tj)时,不需要验证,Ti,Tj,写/写冲突,Start(Tj)每个站点进行每一个本地子事务的本地验证c对每个子事务Tij,在局部验证时收集信息,建立在j站点上,Tij之前已发出的Ti集HB(Tij)d全局