第5章_分布式数据库中的并发控制

.,第5章分布式数据库中的并发控制,褚龙现chulongxian,.,回顾-并发控制的概念和理论,并发控制的概念事务可串行化理论分布式事务的可串行化调度测试并发控制机制的常用方法及其分类,.,回顾-分布式数据库系统并发控制机制的封锁技术,基于封锁的并发控制方法概述2PL协议2PL协议的实现方法多粒度封锁与意向锁,.,分布式数据库系统中的死锁处理,分布式数据库系统并发控制的时标技术,1,2,教学内容,分布式数据库系统并发控制的多版本技术,分布式数据库系统并发控制的乐观方法,3,4,.,教学目标,难点,掌握死锁的预防、检测和解决方法,重点,理解基于时标的并发控制方法,理解基于时标的多版本技术,采用验证锁的多版本两阶段封锁,保守时标法,.,5.3分布式数据库系统中的死锁处理,全局死锁与等待图死锁的预防方法死锁的检测和解决方法,.,5.3.1全局死锁与等待图,死锁发生的条件互斥条件：事务请求对资源的独占控制等待条件：事务已持有分配给它的资源,又去申请并等待别的资源非抢占条件：直到资源被持有它的事务释放前,不可能将资源强制从持有它的事务夺去循环等待条件：存在事务互相等待的等待圈死锁分类局部死锁：仅在一个站点上发生的死锁全局死锁：涉及多个站点的死锁(即等待圈由多个站点组成),.,5.3.1全局死锁与等待图,事务T1持有对x的锁,事务T2请求对x的锁,事务T2持有对y的锁,事务T1请求对y的锁,站点A,站点B,T2等待T1完成释放对x的锁,T1等待T2完成释放对y的锁,相互等待引起的全局死锁,.,5.3.1全局死锁与等待图,多副本引起的三个站点间的死锁,.,5.3.1全局死锁与等待图,等待图一种用来表示事务之间相互等待关系的有向图,是分析死锁的有用工具节点表示事务带有箭头的有向边表示“等待”关系如果等待图有回路，就说明有死锁等待图分类局部等待图(LWFG)全局等待图(GWFG),.,5.3.1全局死锁与等待图,T1,T3,T2,y,x,z,T1等待T2释放对y的共享锁(s)T2等待T3释放对z的共享锁(s)T3等待T1释放对x的共享锁(s),上例的GWFG等待图,.,5.3.1全局死锁与等待图,(a),(b),T2,T1,T1,T2,T4,T3,T4,T3,站点1,站点2,LWFG和GWFG之间的不同,事务间的等待关系T1T2T3T4,.,5.3.2死锁的预防方法,解决死锁的方法死锁预防，使引起死锁的必要条件不成立所有资源排序,按资源序列申请将所有并发事务排序,按标识符或开始时间有死锁危险时，事务退出已占有的资源，有两种方法等待-死亡(Wait-Die)：总是重启较年轻的事务(非占先权)受伤-等待(Wound-Wait)：年轻的等待年老的,较年轻的重启,而重启事务并不一定是目前正申请的事务(占先权)死锁检测即检测死锁时循环等待的圈,.,5.3.2死锁的预防方法,等待-死亡模式如果Ti对已被Tj封锁的一数据项请求封锁的话，则只有在Ti比Tj年老时（TiTj），则Ti被终止并带有同一时间戳重新启动最好总是重新启动较年轻的事务允许较年老的事务去等待已持有资源的较年轻的事务但不允许较年轻的事务去等待较年老的事务受伤-等待模式如果Ti对已被Tj封锁的一数据项请求封锁的话，则只有在Ti比Tj年轻时（TiTj），才允许Ti等待否则，Ti比Tj年老（TiTj），则Tj被终止并带有同一时间戳重新启动,而Ti得锁执行只有年轻的等待年老的,.,5.3.3死锁的检测和解决方法,集中式死锁检测选择一个站点负责整个系统的死锁检测,死锁检测器放到这个站点每个站点的锁管理器周期性地将本站点的LWFG传送给死锁检测器,死锁检测器构造GWFG,并在其中寻找回路或者，其它每个站点上的锁管理器周期性地把记录本站点上事务的开始时间，对锁的持有、请求情况变化的动态表，发送给负责处理封锁的站点，由它维护一张全局封锁动态表，形成GWFG,并在其中寻找回路如果至少包含一条回路，它会选择一个或者多个事务，把它们取消并恢复，释放资源，使得其它事务继续进行。选择的标准是尽可能使撤销并恢复的代价最小，如撤销年轻的事务，撤销占有较少资源的事务，撤销具有最短运行时间的事务，撤销具有最长运行时间的事务等，使系统情况而定,.,5.3.3死锁的检测和解决方法,层次式死锁检测以层次方式组织成员DBMS中的死锁检测器死锁发生时,常常只涉及部分站点层次检测的层次结构与网络拓扑结构有关减少了对中心站点的依赖性，从而减少了传输开销,.,5.3.3死锁的检测和解决方法,层次式死锁检测的步骤树叶是各站点的局部死锁检测器，在本站点建立局部等待图本站点的死锁检测器找出本站点局部等待图中的任何回路，并把有关潜在全局回路的信息发送给上一层死锁检测器每个非本地死锁检测器只对它所涉及的紧挨下层进行死锁检测，合并这些接收到的有关潜在全局回路的信息，并找出任何回路如果还有上层死锁检测器，将经过简化的有关潜在全局回路的信息发送给它上一层死锁检测器，由上一层死锁检测器再进行合并，找出任何全局回路这样，逐层检测，直到最高层。,.,5.3.3死锁的检测和解决方法,层次式死锁检测方法示意图,.,5.3.3死锁的检测和解决方法,分布式检测每个站点的检测死锁责任相同,站点之间交换信息(LWFG)，是为了确定全局死锁EX是指的本地事务正在等待的其他事务所在的还不确定的站点例子,站点1,站点2,T1,T2,T4,T3,EX,EX,.,5.3.3死锁的检测和解决方法,分布式死锁检测算法使用局部信息建造LWFG,该LWFG包含EX节点对每次接收到的信息,执行如下对LWFG的修改对报文中的每个事务,若LWFG中不存在,则将其加入从EX节点开始,按照报文所给的信息,建立一个到下一个事务的边在新的LWFG中寻找不含EX的Loop,若存在,则检测到死锁在新的LWFG中找到含有EX的Loop,于是有潜在的死锁,再按规定向外传送信息,.,5.4分布式数据库系统并发控制的时标技术,基于时标的并发控制方法基本时标法保守时标法,.,5.4.1基于时标的并发控制方法,基本概念不通过互斥来支持串行性，而是通过在事务启动时赋给时标（时间戳）来实现时标是用来唯一识别每个事务并允许排序的标识如果ts(T1)ts(T2)ts(Tn),则调度器产生的序是:T1,T2,.Tn规则如果T1的操作Q1(x)和T2的操作Q2(x)是冲突操作,那么,Q1在Q2之前执行,当且仅当ts(T1)XTS(C)=CTS(F)=本地计数器本地计数器(或时钟)(或时钟),报文1,报文2,计数器,站点,.,5.4.2基本时标法,规则每个事务在本站点开始时赋予一个全局唯一时标在事务结束前，不对数据库进行物理更新事务的每个读操作或写操作都具有该事务的时标对每个数据项x,记下写和读操作的最大时标，记为WTM(x)和RTM(x)如果事务被重新启动，则被赋予新的时标,.,5.4.2基本时标法,基本时标法执行过程令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缺点是重启动多,.,5.4.3保守时标法,基本思想一种消除重启动的方法通过缓冲年轻的操作，直至年长的操作执行完成，因此操作不会被拒绝，事务也绝不被重启动规则每个事务只在一个站点执行,它不能激活远程的程序,但是可以向远程站点发读/写请求站点i接收到来自不同站点j的读/写请求必须按时标顺序，即每个站点必须按时标顺序发送读/写数据请求，在传输中也不会改变这个顺序每个站点都为其它站点发来的读/写操作开辟一个缓冲区,分别保存接收到的读/写申请,.,5.4.3保守时标法,假定某个站点k上,各个缓冲区队列都已不为空，即每个站点都已向它至少发送了一个读和一个写操作，就停止接收，处理在缓冲区中的操作假定站点i至少有一个缓冲的读和缓冲的写来自网中其它站点,根据规则2,Sitei知道没有年老的请求来自其它Site(因为按序接收,所以不可能有比此更年老的请求到来,年老的比年轻的先到),.,5.4.3保守时标法,例子已知站点i的缓冲区队列中有来自所有站点的读/写请求如下所示:站点1站点2站点3站点nR11R21R31Rn1R12R22R32R13R23R24W11W21W31Wn1W22W32Wn2W23,.,5.4.3保守时标法,执行步骤:(1)设RT=min(Rij),WT=min(Wij)(2)按下法处理缓冲区中的Rij和Wija.若队列中有(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=0,.,5.4.3保守时标法,存在问题和解决方法如果一个站点从来不向某个站点发送操作的话，那么执行过程中的假定就不符合，操作就无法进行。解决办法是，周期性的发送带有时标的空操作此方法要求网络上所有站点都连通，这在大系统中很难办到。为避免不必要的通信，可对无读写操作请求的站点，发送一个时标很大的空操作此方法过分保守，一律按照时序来进行，其中包括了不冲突的操作,.,5.5分布式数据库系统并发控制的多版本技术,多版本概念和思想基于时标的多版本技术采用验证锁的多版本两阶段封锁,.,5.5.1多版本概念和思想,基本思想保存了已更新数据项的旧值维护一个数据项的多个版本通过读取数据项的较老版本来维护可串行性，使得系统可以接受在其他技术中被拒绝的一些读操作写数据项时，写入一个新版本，老版本依然保存缺点需要更多的存储来维持数据库数据项的多个版本模式分类基于时标排序基于两阶段封锁,.,5.5.2基于时标的多版本技术,数据项X的多版本X1,X2,X3,Xk系统保存的值Xi的值两种时标Read_TS(Xi):读时标，成功读取版本Xi的事务的时标，最大的一个Write_TS(Xi):写时标，写入版本Xi的值的事务的时标,.,5.5.2基于时标的多版本技术,多版本规则如果事务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(Xi)中较大的一个,.,5.5.2基于时标的多版本技术,图示,写值,若读TS(Ri)=95,则读的值若写TS(Wk)=93,则出现了,v1,v2,v3,Vn-1,Vn,5,10,20,92,100,93,v,于是要拒绝TS(Wk),否则TS(Ri)=95读的就是Vn-1,而不是v的值,但是按规定TS(Ri)=95应该读的是v值,.,5.5.3采用验证锁的多版本两阶段封锁,三种锁方式读，写，验证四种锁状态读封锁（read_locked）写封锁（write_locked）验证封锁（certify_locked）未封锁（unlocked）锁相容性标准模式锁相容性（写锁和读锁）验证模式锁相容性（写锁、读锁和验证锁）,.,5.5.3采用验证锁的多版本两阶段封锁,.,5.5.3采用验证锁的多版本两阶段封锁,多版本2PL的思想当只有一个单独的事务T持有数据项上的写锁时，允许其他事务T读该项X，这是通过给予每个项X的两个版本来实现的一个版本X是由一个已提交的事务写入的另一个版本X是每个事务T获得该数据项上写锁时创建的当事务T持有这个写锁时，其他事务可以继续读X的已提交版本事务T可以写X的值，而不影响X已提交版本的值但是，一旦T准备提交，它必须在能够提交之前，得到持有写锁的数据项上的验证锁，要等写锁释放之后一旦获得验证锁，数据项的已提交版本X被置为版本X的值，版本X被丢弃，验证锁被释放。,.,5.6分布式数据库系统并发控制的乐观方法,基本思想和假设执行阶段划分使用数据项和事务上的时标只使用事务上的时标,.,5.6.1基本思想和假设,基本思想对于冲突操作不像悲观方法那样采取挂起或拒绝的方法，而是让一个事务执行直到完成基于如下假设冲突的事务是少数（查询为主的系统中，冲突少于5%）大多数事务可以不受干扰地执行完毕,.,5.6.2执行阶段划分,.,5.6.2执行阶段划分,事务的三个阶段读段/计算：在数据对象的局部副本上执行事务，这时其他事务不能存取此副本。事务从DB读数据，执行计算，并且确定写集数据项的新值。写操作总是对局部副本，仅当验证通过后，在事务结束处，才将其写入DB。验证段：检验并发事务的可串性，该阶段验证修改应用是否引起完整性（一致性）的丢失，验证阶段通过，才能进入写段，否则事务重启动写段/提交：验证阶段通过，则把事务的更新应用于数据库，对数据进行更新，否则，忽略所有更新，并重新开始该事务,.,5.6.3使用数据项和事务上的时标,使用数据项和事务上的时标假设是一个完全冗余的