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

第章分布式数据库中的并发控制回顾-并发控制的概念和理论并发控制的概念事务可串行化理论分布式事务的可串行化调度测试并发控制机制的常用方法及其分类回顾-分布式数据库系统并发控制机制的封锁技术基于封锁的并发控制方法概述2PL协议2PL协议的实现方法多粒度封锁与意向锁分布式数据库系统中的死锁处理分布式数据库系统并发控制的时标技术12教学内容分布式数据库系统并发控制的多版本技术分布式数据库系统并发控制的乐观方法34教学目标难点掌握死锁的预防、检测和解决方法重点理解基于时标的并发控制方法理解基于时标的多版本技术采用验证锁的多版本两阶段封锁保守时标法否否否当事务T持有这个写锁时，其他事务可以继续读X的已提交版本基于时标的并发控制方法为避免不必要的通信，可对无读写操作请求的站点，发送一个时标很大的空操作如果至少包含一条回路，它会选择一个或者多个事务，把它们取消并恢复，释放资源，使得其它事务继续进行。如果还有上层死锁检测器，将经过简化的有关潜在全局回路的信息发送给它上一层死锁检测器，由上一层死锁检测器再进行合并，找出任何全局回路冲突的事务是少数（查询为主的系统中，冲突少于5%）(Wij)<RT的Wij,则顺序执行这些Wij，执行完删掉回顾-并发控制的概念和理论b.全局唯一时间的形成与调整Write_TS(Xi):写时标，写入版本Xi的值的事务的时标本地计数器本地计数器等待-死亡(Wait-Die)：总是重启较年轻的事务(非占先权)(4)重复上述(2)和(3),直到没有满足条件的操作,或者:5.3分布式数据库系统中的死锁处理全局死锁与等待图死锁的预防方法死锁的检测和解决方法全局死锁与等待图死锁发生的条件互斥条件：事务请求对资源的独占控制等待条件：事务已持有分配给它的资源,又去申请并等待别的资源非抢占条件：直到资源被持有它的事务释放前,不可能将资源强制从持有它的事务夺去循环等待条件：存在事务互相等待的等待圈死锁分类局部死锁：仅在一个站点上发生的死锁全局死锁：涉及多个站点的死锁(即等待圈由多个站点组成)死锁预防，使引起死锁的必要条件不成立对每个数据项x,记下写和读操作的最大时标，记为WTM(x)和RTM(x)但是，一旦T准备提交，它必须在能够提交之前，得到持有写锁的数据项上的验证锁，要等写锁释放之后时标AD时标算法假定：读集写集，即写必须先读理解基于时标的多版本技术假定某个站点k上,各个缓冲区队列都已不为空，即每个站点都已向它至少发送了一个读和一个写操作，就停止接收，处理在缓冲区中的操作分布式数据库系统并发控制的多版本技术如果一个站点从来不向某个站点发送操作的话，那么执行过程中的假定就不符合，操作就无法进行。但不允许较年轻的事务去等待较年老的事务每个事务赋一个唯一的时标，事务的执行等效于按时标次序串行执行在新的LWFG中找到含有EX的Loop,于是有潜在的死锁,再按规定向外传送信息在新的LWFG中找到含有EX的Loop,于是有潜在的死锁,再按规定向外传送信息读封锁（read_locked）当事务T持有这个写锁时，其他事务可以继续读X的已提交版本全局死锁与等待图事务T1持有对x的锁事务T2请求对x的锁事务T2持有对y的锁事务T1请求对y的锁站点A站点BT2等待T1完成释放对x的锁T1等待T2完成释放对y的锁相互等待引起的全局死锁全局死锁与等待图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：read(z),write(x)多副本引起的三个站点间的死锁全局死锁与等待图等待图一种用来表示事务之间相互等待关系的有向图,是分析死锁的有用工具节点表示事务带有箭头的有向边表示“等待”关系如果等待图有回路，就说明有死锁等待图分类局部等待图(LWFG)全局等待图(GWFG)全局死锁与等待图T1T3T2yxzT1等待T2释放对y的共享锁(s)T2等待T3释放对z的共享锁(s)T3等待T1释放对x的共享锁(s)上例的GWFG等待图全局死锁与等待图(a)(b)T2T1T1T2T4T3T4T3站点1站点2LWFG和GWFG之间的不同事务间的等待关系T1→T2→T3→T4死锁的预防方法解决死锁的方法死锁预防，使引起死锁的必要条件不成立所有资源排序,按资源序列申请将所有并发事务排序,按标识符或开始时间有死锁危险时，事务退出已占有的资源，有两种方法等待-死亡(Wait-Die)：总是重启较年轻的事务(非占先权)受伤-等待(Wound-Wait)：年轻的等待年老的,较年轻的重启,而重启事务并不一定是目前正申请的事务(占先权)死锁检测即检测死锁时循环等待的圈死锁的预防方法等待-死亡模式如果Ti对已被Tj封锁的一数据项请求封锁的话，则只有在Ti比Tj年老时（Ti<Tj），才允许Ti等待如果Ti比Tj年轻（Ti>Tj），则Ti被终止并带有同一时间戳重新启动最好总是重新启动较年轻的事务允许较年老的事务去等待已持有资源的较年轻的事务但不允许较年轻的事务去等待较年老的事务受伤-等待模式如果Ti对已被Tj封锁的一数据项请求封锁的话，则只有在Ti比Tj年轻时（Ti>Tj），才允许Ti等待否则，Ti比Tj年老（Ti<Tj），则Tj被终止并带有同一时间戳重新启动,而Ti得锁执行只有年轻的等待年老的死锁的检测和解决方法集中式死锁检测选择一个站点负责整个系统的死锁检测,死锁检测器放到这个站点每个站点的锁管理器周期性地将本站点的LWFG传送给死锁检测器,死锁检测器构造GWFG,并在其中寻找回路或者，其它每个站点上的锁管理器周期性地把记录本站点上事务的开始时间，对锁的持有、请求情况变化的动态表，发送给负责处理封锁的站点，由它维护一张全局封锁动态表，形成GWFG,并在其中寻找回路如果至少包含一条回路，它会选择一个或者多个事务，把它们取消并恢复，释放资源，使得其它事务继续进行。选择的标准是尽可能使撤销并恢复的代价最小，如撤销年轻的事务，撤销占有较少资源的事务，撤销具有最短运行时间的事务，撤销具有最长运行时间的事务等，使系统情况而定死锁的检测和解决方法层次式死锁检测以层次方式组织成员DBMS中的死锁检测器死锁发生时,常常只涉及部分站点层次检测的层次结构与网络拓扑结构有关减少了对中心站点的依赖性，从而减少了传输开销死锁的检测和解决方法层次式死锁检测的步骤树叶是各站点的局部死锁检测器，在本站点建立局部等待图本站点的死锁检测器找出本站点局部等待图中的任何回路，并把有关潜在全局回路的信息发送给上一层死锁检测器每个非本地死锁检测器只对它所涉及的紧挨下层进行死锁检测，合并这些接收到的有关潜在全局回路的信息，并找出任何回路如果还有上层死锁检测器，将经过简化的有关潜在全局回路的信息发送给它上一层死锁检测器，由上一层死锁检测器再进行合并，找出任何全局回路这样，逐层检测，直到最高层。死锁的检测和解决方法层次式死锁检测方法示意图第0层死锁检测器第i层死锁检测器第i层死锁检测器局部死锁检测器局部死锁检测器局部死锁检测器局部死锁检测器简化潜在死锁图简化潜在死锁图简化潜在死锁图简化潜在死锁图简化潜在死锁图简化潜在死锁图死锁的检测和解决方法分布式检测每个站点的检测死锁责任相同,站点之间交换信息(LWFG)，是为了确定全局死锁EX是指的本地事务正在等待的其他事务所在的还不确定的站点例子站点1站点2T1T2T4T3EXEX死锁的检测和解决方法分布式死锁检测算法使用局部信息建造LWFG,该LWFG包含EX节点对每次接收到的信息,执行如下对LWFG的修改对报文中的每个事务,若LWFG中不存在,则将其加入从EX节点开始,按照报文所给的信息,建立一个到下一个事务的边在新的LWFG中寻找不含EX的Loop,若存在,则检测到死锁在新的LWFG中找到含有EX的Loop,于是有潜在的死锁,再按规定向外传送信息5.4

分布式数据库系统并发控制的时标技术基于时标的并发控制方法基本时标法保守时标法基于时标的并发控制方法基本概念 不通过互斥来支持串行性，而是通过在事务启动时赋给时标（时间戳）来实现时标是用来唯一识别每个事务并允许排序的标识如果ts(T1)<ts(T2)…<ts(Tn),则调度器产生的序是:T1,T2,...Tn

规则如果T1的操作Q1(x)和T2的操作Q2(x)是冲突操作,那么,Q1在Q2之前执行,当且仅当ts(T1)<ts(T2)基于时标的并发控制方法时标分配方法

全局时标使用全局的单调递增的计数器全局的计数器维护是个难题局部时标每个站点基于其本地计数器自治地指定一个时标标识符由两部分组成：〈本地计数器值，站点标识符〉站点标识符是次要的，主要是本地计数器值可以使用站点系统时钟来代替计数器值基于时标的并发控制方法时标法思想

每个事务赋一个唯一的时标，事务的执行等效于按时标次序串行执行如果发生冲突，是通过撤销并重新启动一个事务来解决事务重新启动时，则赋予新的时标优点是没有死锁，不必设置锁封锁和死锁检测引起的通信开销也避免了但要求时标在全系统中是唯一的基于时标的并发控制方法时标性质唯一性单调性全局唯一时间的形成与调整每个站点设置一个计数器,每发生一个事务,计数器加一发送报文时包含本地计数器值,近似同步各站点计数器基于时标的并发控制方法计数器X初值X=0计数器Y初值Y=10

站点1站点2

时标AD时标

TS(A)=<1,1>TS(D)=<11,2>

因为X<YETS(E)=<12,2>

改X=Y+1=11BTS(B)=<11,1>F因为Y>XTS(C)=<12,1>CTS(F)=<13,2>

本地计数器本地计数器

(或时钟)(或时钟)报文1报文2计数器站点基本时标法

规则每个事务在本站点开始时赋予一个全局唯一时标在事务结束前，不对数据库进行物理更新事务的每个读操作或写操作都具有该事务的时标对每个数据项x,记下写和读操作的最大时标，记为WTM(x)和RTM(x)如果事务被重新启动，则被赋予新的时标基本时标法

基本时标法执行过程令read_TS是事务对x进行读操作时的时标若read_TS<WTM(x)，则拒绝该操作,事务重新启动否则,执行,令RTM(x)=max{RTM(x),read_TS}令write_TS是事务对x进行写操作时的时标若write_TS<RTM(x)或write_TS<WTM(x),则拒绝该操作,事务重新启动否则,执行,令WTM(x)=max{WTM(x),write_TS}缺点是重启动多保守时标法基本思想一种消除重启动的方法通过缓冲年轻的操作，直至年长的操作执行完成，因此操作不会被拒绝，事务也绝不被重启动规则每个事务只在一个站点执行,它不能激活远程的程序,但是可以向远程站点发读/写请求站点i接收到来自不同站点j的读/写请求必须按时标顺序，即每个站点必须按时标顺序发送读/写数据请求，在传输中也不会改变这个顺序每个站点都为其它站点发来的读/写操作开辟一个缓冲区,分别保存接收到的读/写申请保守时标法假定某个站点k上,各个缓冲区队列都已不为空，即每个站点都已向它至少发送了一个读和一个写操作，就停止接收，处理在缓冲区中的操作假定站点i至少有一个缓冲的读和缓冲的写来自网中其它站点,根据规则2,Sitei知道没有年老的请求来自其它Site(因为按序接收,所以不可能有比此更年老的请求到来,年老的比年轻的先到)保守时标法例子

已知站点i的缓冲区队列中有来自所有站点的读/写请求如下所示:

站点1站点2站点3……站点nR11R21R31Rn1R12R22R32R13R23R24W11W21W31……Wn1W22W32…Wn2W23保守时标法执行步骤:(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.5分布式数据库系统并发控制的多版本技术多版本概念和思想基于时标的多版本技术采用验证锁的多版本两阶段封锁多版本概念和思想基本思想保存了已更新数据项的旧值维护一个数据项的多个版本通过读取数据项的较老版本来维护可串行性，使得系统可以接受在其他技术中被拒绝的一些读操作写数据项时，写入一个新版本，老版本依然保存缺点需要更多的存储来维持数据库数据项的多个版本模式分类基于时标排序基于两阶段封锁但要求时标在全系统中是唯一的有死锁危险时，事务退出已占有的资源，有两种方法死锁预防，使引起死锁的必要条件不成立T1等待T2释放对y的共享锁(s)使用局部信息建造LWFG,该LWFG包含EX节点若write_TS<RTM(x)或write_TS<WTM(x),则拒绝该操作,事务重新启动否否写段/提交：验证阶段通过，则把事务的更新应用于数据库，对数据进行更新，否则，忽略所有更新，并重新开始该事务T1→T2→T3→T4如果还有上层死锁检测器，将经过简化的有关潜在全局回路的信息发送给它上一层死锁检测器，由上一层死锁检测器再进行合并，找出任何全局回路T1→T2→T3→T4假定站点i至少有一个缓冲的读和缓冲的写来自网中其它站点,根据规则2,Sitei知道没有年老的请求来自其它Site(因为按序接收,所以不可能有比此更年老的请求到来,年老的比年轻的先到)但是，一旦T准备提交，它必须在能够提交之前，得到持有写锁的数据项上的验证锁，要等写锁释放之后每个站点基于其本地计数器自治地指定一个时标维护一个数据项的多个版本基于时标的多版本技术数据项X的多版本X1,X2,X3,…,Xk系统保存的值Xi的值两种时标Read_TS(Xi):读时标，成功读取版本Xi的事务的时标，最大的一个Write_TS(Xi):写时标，写入版本Xi的值的事务的时标基于时标的多版本技术多版本规则如果事务T发布一个write_item(X)操作，并且X的版本Xi具有X所有版本中最高的write_TS(Xi),同时write_TS(Xi)<=TS(T)且read_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)中较大的一个基于时标的多版本技术图示写值v1v2v3…Vn-1Vn5102092100若读TS(Ri)=95,则读<92,Vn-1>的值若写TS(Wk)=93,则出现了v1v2v3…Vn-1Vn510209210093v于是要拒绝TS(Wk),否则TS(Ri)=95读的就是Vn-1,而不是v的值,但是按规定TS(Ri)=95应该读的是v值采用验证锁的多版本两阶段封锁三种锁方式读，写，验证四种锁状态读封锁（read_locked）写封锁（write_locked）验证封锁（certify_locked）未封锁（unlocked）锁相容性标准模式锁相容性（写锁和读锁）验证模式锁相容性（写锁、读锁和验证锁）采用验证锁的多版本两阶段封锁

(a)读/写封锁模式的相容性表读写读写是否否否读写验证读写是是否是否否验证否否否

(b)读/写/验证封锁模式的相容性表采用验证锁的多版本两阶段封锁多版本2PL的思想当只有一个单独的事务T持有数据项上的写锁时，允许其他事务T’读该项X，这是通过给予每个项X的两个版本来实现的一个版本X是由一个已提交的事务写入的另一个版本X’是每个事务T获得该数据项上写锁时创建的当事务T持有这个写锁时，其他事务可以继续读X的已提交版本事务T可以写X’的值，而不影响X已提交版本的值但是，一旦T准备提交，它必须在能够提交之前，得到持有写锁的数据项上的验证锁，要等写锁释放之后一旦获得验证锁，数据项的已提交版本X被置为版本X’的值，版本X’被丢弃，验证锁被释放。5.6分布式数据库系统并发控制的乐观方法基本思想和假设执行阶段划分使用数据项和事务上的时标只使用事务上的时标基本思想和假设

基本思想对于冲突操作不像悲观方法那样采取挂起或拒绝的方法，而是让一个事务执行直到完成基于如下假设冲突的事务是少数（查询为主的系统中，冲突少于5%）大多数事务可以不受干扰地执行完毕执行阶段划分验证读/计算写/提交读/计算验证写/提交乐观法事务执行的各个阶段悲观法事务执行的各个阶段执行阶段划分事务的三个阶段读段/计算：在数据对象的局部副本上执行事务，这时其他事务不能存取此副本。事务从DB读数据，执行计算，并且确定写集数据项的新值。写操作总是对局部副本，仅当验证通过后，在事务结束处，才将其写入DB。验证段：检验并发事务的可串性，该阶段验证修改应用是否引起完整性（一致性）的丢失，验证阶段通过，才能进入写段，否则事务重启动写段/提交：验证阶段通过，则把事务的更新应用于数据库，对数据进行更新，否则，忽略所有更新，并重新开始该事务这样，逐层检测，直到最高层。等待-死亡(Wait-Die)：总是重启较年轻的事务(非占先权)Read_TS(Xi):读时标，成功读取版本Xi的事务的时标，最大的一个冲突的事务是