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

分布式数据库系统及其应用,并发控制的概念和理论 分布式数据库系统并发控制的封锁技术 分布式数据库系统中的死锁处理 分布式数据库系统并发控制的时标技术 分布式数据库系统并发控制的多版本技术 分布式数据库系统并发控制的乐观方法,分布式数据库中的并发控制,第5章,通常，数据库总有若干个事务在运行，这些事务可能并发地存取相同的数据，称为事务的并发操作。 当数据库中有多个事务并发执行时，系统必须对并发事务之间的相互作用加以控制，这是通过并发控制机制来实现的。 并发控制就是负责正确协调并发事务的执行，保证这种并发的存取操作不至于破坏数据库的完整性和一致性，确保并发执行的多个事务能够正确地运行并获得正确的结果。 分布式数据库中的并发控制解决多个分布式事务对数据并发执行的正确性，保证数据库的完整性和一致性。比集中式并发控制更复杂。,集中式DB环境,T1 T2 Tn,DB (一致性 约束),分布式DB环境,X,Y,Z,T1,T2,多处理器,并发执行,单处理器,非并发执行,UPDATE x,70,t6,FIND x,t2,200,t7,UPDATE x,t5,x:=x*2,t4,x:=x-30,t3,FIND x,t1,100,t0,更新事务T2,数据库中X的值,更新事务T1,时间,注：其中FIND表示从数据库中读值，UPDATE表示把值写回到数据库 T1T2，结果140，T2T1,结果170， 得到结果是200，显然是不对的，T1在t7丢失更新操作。,并发控制问题之一：丢失更新,FIND x,t2,70,t5,UPDATE x,t4,x:=x-30,t3,FIND x,t1,100,t0,更新事务T2,数据库中A的值,更新事务T1,时间,注：在时间t5事务T2仍认为x的值是100,并发控制问题之二：不一致分析,100,t6,x:=x-10,t2,ROLLBACK,t5,FIND x,90,t4,UPDATE x,t3,FIND x,t1,100,t0,更新事务T2,数据库中A的值,更新事务T1,时间,注： 事务T2依赖于事务T1的未完成更新,并发控制问题之三：依赖于未提交更新（读脏数据）,事务Ti Ti= i, i 其中： i : 操作符集合：Ri(x), Wi(x) U Ai, Ci Ai, Ci 是最后的操作符，只能是其一 i : (冲突)操作有序执行，Ri(x) i Wi(x) 或 Wi(x) i Ri(x),操作符集 读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),T1 T2 1 (T1) a X 5 (T2) c X 2 (T1) X a+100 6 (T2) X 2c 3 (T1) b Y 7 (T2) d Y 4 (T1) Y b+100 8 (T2) Y 2d,先序关系,例子 已知：站点1有数据X，站点2有数据Y 约束：X=Y,(X站点) (Y站点) 1 (T1) a X 2 (T1) X a+100 5 (T2) c X 3 (T1) b Y 6 (T2) X 2c 4 (T1) Y b+100 7 (T2) d Y 8 (T2) Y 2d 初值: X=Y=0 , 结果: X=Y=200,调度S1,事务内 事务间,令T= T1,T2,Tn 是一组事务. T上的调度 S 是具有如下顺序关系T的偏序，即S=T ,T : (1) T= Ti (2) T i (3) 对于任意一组冲突操作 p,q S, 存在 p q 或 q p关系,并发调度定义,i=1,N,N,i=1,调度 一组事务的调度必须包含这些事务的所有操作 调度中某个事务的操作顺序必须保持与该事务原有的顺序相同 串行调度 一个事务的第一个动作是在另一个事务的最后一个动作完成后开始. 即调度中事务的各个操作不会交叉, 每个事务相继执行. 一致性调度 调度可以使得数据库从一个一致性状态转变为另一个一致性状态，则称调度为一致性调度,调度等价 S1与S2等价, 也就是说, 对于冲突操作, , Oi Oj在S1中成立, 同时 Oi Oj 在S2中也成立 可串行化调度 如果一个调度等价于某个串行调度，则该调度称为可串行化调度。 也就是说，该调度可以通过一系列非冲突动作的交换操作使其成为串行调度,例子 两个事务，定义如下： T1: Read(x） x=x+10 Write(x) Read(y) y=y-15 Write(y) commit,T2: Read(x） x=x-20 Write(x) Read(y) y=y*2 Write(y) commit,五种调度： 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,如果将事务提交延迟到两个事务操作完成之后执行，有： 调度S1和S4是串行调度 调度S2和S1的冲突操作具有相同的顺序，因此是等价调度；S2是可串行化调度，也是一致性调度 调度S3虽是一致调度，但是它不与S1或S4等价，所以S3不是可串行化调度 调度S5和S4等价，所以S5是一致调度，也是可串行化调度,有以下推论： 一个可串行化调度必定与某个串行调度等价，且是一致性调度 一致性调度不一定是可串行化调度 同一事务集几个可串行化调度，他们的结果未必相同,优先图 P(S),调度 S 的优先图是一个有向图G(N,E) ，其中 N: 一组节点N=T1T2,Tn, Ti是S中的事务 E: 一组有向边E=e1,e2,en, Ti Tj 是图中的一条边，当且仅当 p Ti, q Tj 使得p, q 冲突，并且 p S q,测试调度S的可串行化,对于调度 S中的事务Ti，在图中创建一个节点Ti 对于每一种这样的情形：如果S中的在Ti执行了W(X)操作后执行Tj的R(X)操作，那么在优先图中创建一条边（TiTj ） 对于每一种这样的情形：如果S中的在Ti执行了R(X)操作后执行Tj的W(X)操作，那么在优先图中创建一条边（TiTj ） 对于每一种这样的情形：如果S中的在Ti执行了W(X)操作后执行Tj的W(X)操作，那么在优先图中创建一条边（TiTj ） 当且仅当优先图中没有闭环时，调度S是可串行化的,测试调度S的可串行化,优先图中存在环路，说明调度是不可串行化的，否则是可串行化的。 环路是指有向图中每条边的起始节点（第一条边除外），都与前一条边的终止节点连接，而第一条边的起始节点于最后一条边的终止节点连接，即事务序列是以同一个节点作为开始和结束的 调度S中事务Ti在事务Tj之前，与S等价的调度中Ti也必须在Tj之前 某项数据导致了调度中的一条边的生成，就把数据项标注到优先图中这条边的旁边 如果调度S中不存在环路，那么就可能存在若干个与S等价的串行调度,存在环路,举例,考虑如下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 优先图： T2 T1 T3 无环， S是串行调度。,另外一个调度S: S=W2(x), R1(x),W1(x),C1,R3(x), W2(y), R3(y), R2(z), C2,R3(z),C3 先序图： T2 T1 T3 无环，是可串调度。,可串性理论扩展,可串性理论可以直接扩展到无重复副本的分布式数据库中。 事务在每个站点上的执行调度称作局部调度 如果数据库无重复副本的分布式数据库，并且每个局部调度都是可串行化调度，只要这些局部调度的顺序一致，则它们的并（全局调度）也是可串行化调度 但是有副本的情况下，就比较复杂。可能局部调度是可串行化的，而全局调度不是可串行化的。,保证只产生可串行化调度的机制 并发控制机制分类 按分配模式(数据方式) 完全复制的DB 部分复制DB或分片的DB 按网络类型(通信方式) 广播能力的 星型网, 环形网 同步化原则 建立在相互排斥地访问共享数据基础上的算法 通过一些准则(协议)对事务进行排序的算法 悲观并发控制法（事务是相互冲突的），乐观并发控制法（没有太多的事务相互冲突）,并发控制算法的分类,封锁法 事务的同步化是通过对数据库的片断或者数据项进行物理或逻辑封锁来实现的 封锁对象的大小通常称为封锁粒度 封锁方法的类型可以根据在哪里进行封锁来进一步细分 封锁法分类 集中式封锁方法 一个站点被指定为主站点，存放对整个数据库的封锁表，并且负责对全系统事务进行封锁 主副本封锁法：对主副本所在站点封锁 分布式封锁法：网络中的站点共享锁的管理,基本思想和概念,基本思想 事务访问数据项之前要对该数据项封锁，如果已经被其他事务锁定，就要等待，直到那个事务释放该锁为止 锁的粒度 锁定数据项的范围 数据项层次 数据库记录中的一个字段值 一条数据库记录 一个磁盘块（页面） 一个完整的文件 整个数据库,基本思想和概念,粒度对并发控制的影响 大多数DBMS缺省设置为记录锁或页面锁 粒度小，并发度高，锁开销大 数据项比较多，锁也多，解锁和封锁操作多，锁表存储空间大（如存储读写时间戳） 粒度大，并发度低，锁开销小 如果是磁盘块，封锁磁盘块中的一条记录B的事务T必须封锁整个磁盘块 而另外一个事务S如果要封锁记录C,而C也在磁盘块中，由于磁盘块正在封锁中，S只能等待 如果是封锁粒度是一条记录的话，就不用等待了,基本思想和概念,如何来确定粒度 取决于参与事务的类型 如果参与事务都访问少量的记录，那么选择一个记录作为粒度较好 如果参与事务都访问同一文件中大量的记录，则最好采用块或者文件作为粒度,锁的类型： 共享锁：Share锁，S锁或者读锁 排它锁：eXclusive锁，X锁，拒绝锁或写锁。 更新锁：Update锁，U锁 锁的选择： 数据项既可以读也可以写.则要用X锁 如果数据项只可以读.则要用 S锁.,基本思想和概念,锁的操作 Read_lock(x):读锁 Write_lock(x)：写锁 unlock(x)：解锁 数据项的状态 read_locked: 读锁 Write_locked:写锁 具体操作方法 在系统锁表中记录关于锁的信息 锁表中每条记录有四个字段： 锁状态是上面两种。没有被封锁的数据项，在系统表中没有记录,基本思想和概念,封锁准则： 事务T在执行任何read_item（x）操作之前，必须先执行read_lock(x)或者write_lock(x)操作 事务T在执行任何write_item（x）操作之前，必须先执行write_lock(x)操作 如果事务T执行read_lock(x)操作,数据项x必须没有加锁或者已经加了读锁，否则事务T的这个操作不能进行 如果事务T执行write_lock(x)操作,数据项x必须没有加锁，否则事务T的这个操作不能进行,封锁准则和锁的转换,封锁准则： 事务T在完成所有read_item（x）和write_item（x）操作之后，必须执行unlock(x)操作 如果事务T已经持有数据项x上的一个读锁或者一个写锁，那么它不能再执行read_lock(x)操作 如果事务T已经持有数据项x上的一个读锁或者一个写锁，那么它不能再执行write_lock(x)操作 如果事务T没有持有数据项x上的一个读锁或者一个写锁，那么它不能执行unlock(x)操作,封锁准则和锁的转换,锁的转换 特定条件下，一个已经在数据项x上持有锁的事务T ，允许将某种封锁状态转换为另外一种封锁状态 比如，一个事务先执行了read_lock（x）操作，然后他可以通过执行write_lock(x)操作来升级该锁 同样，一个事务先执行了write_lock(x) 操作，然后他可以通过执行read_lock（x） 操作来降级该锁,封锁准则和锁的转换,满足封锁规则不能保证产生串行化调度,简单的分布式封锁方法 类似集中式，将同一数据的全部副本封锁，然后更新，之后解除全部封锁 缺点是各站点间进行相当大的数据传输，如果有N个站点，就有： N个请求封锁的消息 N个封锁授权的消息 N个更新数据的消息 N个更新执行了的消息 N个解除封锁的消息,分布式数据库基本封锁算法,主站点封锁法 定义一个站点为主站点，负责系统全部封锁管理 所有站点都向主站点提出封锁和解锁请求，由它去处理 缺点有： 所有封锁请求都送往单个站点，容易由于超负荷造成“瓶颈” 主站点故障会使系统瘫痪，封锁消息都在这里，制约了系统可用性和可靠性,分布式数据库基本封锁算法,主副本封锁法 不指定主站点，指定数据项的主副本 事务对某个数据项进行操作时，先对其主副本进行封锁，再进行操作 主副本封锁，意味着所有的副本都被封锁 主副本按使用情况，尽量就近分布 可减少站点的负荷,使得各站点比较均衡 可减少传输量 快照方法 和上一章讲的类似,分布式数据库基本封锁算法,基本2PL协议,如果一个事务所有的封锁操作（读写）都在第一个解锁操作之前，那么它就遵守2PL协议 事务的执行中Lock的管理分成两个阶段 上升阶段(成长阶段)：获取Lock阶段（只能获取锁） 收缩阶段(衰退阶段）：释放Lock阶段（只能解锁） 封锁点是指事务获得了它所要求的所有锁，并且还没有开始释放任何锁的时刻 如果允许锁的转换，锁的升级必须在成长阶段进行，锁的降级必须在锁的衰退阶段进行。 2PL可以保证事务执行的可串行性.,开始,加锁点,结束,事务执行过程,获得锁,释放锁,两阶段封锁协议,基本2PL协议实现的难点 锁管理器必须要知道事务的锁点位置 级联撤销(cascading aborts) 如果事务在开始释放Lock后又Abort时, 将引起级联撤销(cascading aborts)（其他访问这个数据项的事务也被撤销） 保守2PL 要求事务在开始执行之前就持有所有它要访问的数据项上的锁 事务要预先声明它的读集和写集 大多数2PL调度器实现的是严格2PL(S2PL) 事务在提交或者撤销之前，绝对不释放任何一个写锁 事务结束时（提交或者撤销），同时释放所有的锁,严格2PL 事务T在提交或撤销之前，不能释放任何一个锁（写锁或者读锁），因此它比严格2PL更容易实现 保守2PL与严格2PL之间的区别 前者，事务必须在开始之前封锁它所需要的所有数据项，因此，一旦事务开始就处在收缩阶段 后者,直到事务结束（提交或者撤销）后才开始解锁，因此，事务一直处于扩张阶段，直到结束,开始,结束,事务执行阶段,获得锁,释放锁,严格2PL(Strict Two-phase Locking)协议,数据项使用,并发控制子系统 可以负责产生读锁和写锁操作（以严格2PL协议为例） 当事务T发出read_item(x)操作请求时，系统会代表T调用read_lock(x)操作 如果Lock(x)的状态是被另外一个事务T持有写锁，那么系统会把T放到数据项X的等待队列中；否则，系统同意read_lock(x)的请求，从而允许事务T执行read_item(x)操作 另外一个方面，如果事务T发出write_item（x）操作请求时，系统会代表T调用write_lock(x)操作 如果Lock(x)的状态是被另外一个事务T持有读锁或写锁，那么系统会把T放到数据项X的等待队列中； 如果Lock(x)的状态是读锁，并且事务T本身就是持有x上的读锁的唯一事务，那么系统将该锁升级为写锁，并且允许T执行write_item(x)操作 如果Lock(x)的状态是没有锁，那么系统同意write_lock(x)的请求，进而允许事务T执行write_item(x)操作,集中式2PL的实现方法,2PL很容易扩展到分布式DBMS(无论复制或无复制DDB), 其最简单的方法是选择一个站点(主站点)做Lock管理器, 其他站点上的事务管理器都需要与该选出的站点Lock管理器通信, 而不是与本站点Lock管理器通信. 这就是集中式2PL方法,术语 协调事务管理器(coordinating TM) ： 事务原发站点 数据处理器(data processor，DP) ：其他参与站点 中心站点LM：主站点锁管理器,参与站点的 数据处理器,协调 TM,中心站点 LM,加锁请求,允许加锁,操作,操作结束,释放封锁,集中式2PL的通信结构,中心站点LM不需要向DP发送操作,集中式2PL的实现方法,主副本2PL的实现方法,是主站点2PL的直接扩展 选择一组站点做Lock管理器 每个Lock管理器管理一组数据(即每个数据选择一个站点作自己的Lock管理器) 事务管理器根据Lock申请的数据对象分别向这些数据的LM发出锁申请 必须先为每一个数据项确定一个主副本站点，然后再向那个站点上的封锁管理程序发送封锁或释放锁的请求，目录的思想 为分布式INGRES版本提出的，每个站点上要有一个复杂的目录,特点 每个站点都有LM 无副本DDB上如同主副本2PL 有冗余副本DDB上则使用ROWA控制协议 与集中式相似，但有不同 集中式中向中心站点封锁管理程序发送的信息，在分布式中发送给所有参与站点的封锁管理程序 另外不同之处在于操作并不通过协调者事务管理程序传到数据处理器，而是通过参与者的封锁管理程序 参与者的数据处理器向协调者的事务管理程序发送“操作结束”信息 另外一种方法，每个数据处理器执行自身解锁，并通知协调者事务管理程序的封锁管理程序,分布式2PL的实现方法,参与者 DPs,加锁请求,操作,分布式2PL的通信结构,协调者 TM,参与者 LMs,操作结束,释放锁,分布式2PL的实现方法,多粒度封锁 封锁的粒度不是单一的一种粒度，而是有多种粒度 可以定义多粒度树，根节点是整个数据库，叶节点表示最小的封锁粒度 直接封锁 事务对要进行读/写的数据对象直接申请加锁 分层封锁 DB中各数据对象从大到小存在一种层次关系, 例如划分为DB, 段, 关系, 元组, 字段等 当封锁了外层数据对象时, 蕴含着也同时封锁了它的所有内层数据对象 数据项的显式封锁和隐式封锁,数据库,段1,段n,.,多级粒度树,关系nn,关系11,.,.,用来说明多粒度级别封锁的粒度层次结构,例子 假定事务T1要更新文件f1中的所有记录，T1请求并获得了f1上的一个写锁 那么f1下面的页面和记录就获得了隐式写锁 如果这时候，事务T2想从f1中的某个页面中读某个记录，那么T2就要申请该记录上的读锁 但是要确认这个读锁和已经存在锁的相容性，确认的方法就是要遍历该树：从记录到页，到文件最后到数据库，如果在任意时刻，在这些项中的任意一个上存在冲突锁，那么对记录的封锁请求就被拒绝，T2被阻止，要等待。,意向锁 如果对一个节点加意向锁，则说明该节点的下层节点正在被封锁 对任一节点封锁时，必须先对它的上层节点加意向锁 意向锁的类型 意向共享锁(IS)：指示在其后代节点上将会请求共享锁，即如果对某个对象加IS锁，表示它的后代节点拟加共享锁 意向排它锁(IX)：指示在其后代节点上将会请求排他锁，即如果对某个对象加IX锁，表示它的后代节点拟加排他锁 共享意向排它锁(SIX)：指示当前节点处在共享方式的封锁中，但是在它的某些后代节点中将会请求排他锁。即如果对一个数据对象加SIX锁,表示对它加共享锁，再加IX锁（SIX=S+IX）。例如：对某个表加SIX锁，则表示该事务要读整个表（加S锁），同时会更新个别元组（加IX锁）,T2,T1,Y,Y,Y,Y,Y,Y,-,Y,N,N,Y,N,N,SIX,Y,N,Y,Y,N,N,IX,Y,Y,Y,Y,N,Y,IS,Y,N,N,N,N,N,X,Y,N,N,Y,N,Y,S,-,SIX,IX,IS,X,S,X,SIX,S,IX,IS,Y=yes，表示相容的请求 N=no，表示不相容的请求,(a)数据锁的相容矩阵,(b)锁的强度的偏序关系,锁的相容矩阵,锁的强度：对其它锁的排斥程度,多粒度封锁协议的规则 必须遵守锁的相容性规则 必须首先封锁树的根节点，可以用任何一种方式的锁 只有当节点N的父节点已经被事务T以IS或IX方式封锁后，节点N才可以被T以S或者IS方式封锁 只有当节点N的父节点已经被事务T以IX或SIX方式封锁后，节点N才可以被T以X,IX或者SIX方式封锁 只有当事务T还没有释放任何节点时，T才可以封锁一个节点 只有当事务T当前没有封锁节点N的任何子节点时，T才可以为节点N解锁。,总结 具有意向锁的多粒度加锁方法中，任意事务T要对一个数据对象加锁，必须先对它的上层节点加意向锁 申请封锁时应该按自上而下的次序进行 释放锁时则应该按自下而上的次序进行 具有意向锁的多粒度加锁方法提高了系统的并发度, 减少了加锁和释放锁的开销 它已经在实际的DBMS系统中广泛应用，例如Oracle中,死锁发生的条件 互斥条件：事务请求对资源的独占控制 等待条件：事务已持有分配给它的资源, 又去申请并等待别的资源 非抢占条件：直到资源被持有它的事务释放前, 不可能将资源强制从持有它的事务夺去 循环等待条件：存在事务互相等待的等待圈 死锁分类 局部死锁：仅在一个站点上发生的死锁 全局死锁：涉及多个站点的死锁(即等待圈由多个站点组成),事务T1持有 对x的锁,事务T2请求 对x的锁,事务T2持有 对y的锁,事务T1请求 对y的锁,站点A,站点B,T2等待T1完成 释放对x的锁,T1等待T2完成 释放对y的锁,相互等待引起的全局死锁,T1,T2,T3,站点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),T1,T3,T2,y,x,z,T1等待T2释放对y的共享锁(s) T2等待T3释放对z的共享锁(s) T3等待T1释放对x的共享锁(s),上例的GWFG等待图,(a),(b),T2,T1,T1,T2,T4,T3,T4,T3,站点1,站点2,LWFG和GWFG之间的不同,事务间的等待关系 T1T2T3T4,解决死锁的方法 死锁预防，使引起死锁的必要条件不成立 所有资源排序, 按资源序列申请 将所有并发事务排序, 按标识符或开始时间 有死锁危险时，事务退出已占有的资源，有两种方法 等待-死亡(Wait-Die)：总是重启较年轻的事务(非占先权) 受伤-等待(Wound-Wait) ：年轻的等待年老的, 较年轻的重启,而重启事务并不一定是目前正申请的事务 (占先权) 死锁检测 即检测死锁时循环等待的圈,等待-死亡模式 如果Ti对已被Tj封锁的一数据项请求封锁的话，则只有在Ti比Tj年老时（TiTj），则Ti被终止并带有同一时间戳重新启动 最好总是重新启动较年轻的事务 允许较年老的事务去等待已持有资源的较年轻的事务 但不允许较年轻的事务去等待较年老的事务 受伤-等待模式 如果Ti对已被Tj封锁的一数据项请求封锁的话，则只有在Ti比Tj年轻时（TiTj），才允许Ti等待 否则，Ti比Tj年老（TiTj），则Tj被终止并带有同一时间戳重新启动,而Ti得锁执行 只有年轻的等待年老的,集中式死锁检测 选择一个站点负责整个系统的死锁检测,死锁检测器放到这个站点 每个站点的锁管理器周期性地将本站点的LWFG传送给死锁检测器, 死锁检测器构造GWFG, 并在其中寻找回路 或者，其它每个站点上的锁管理器周期性地把记录本站点上事务的开始时间，对锁的持有、请求情况变化的动态表，发送给负责处理封锁的站点，由它维护一张全局封锁动态表，形成GWFG, 并在其中寻找回路 如果至少包含一条回路，它会选择一个或者多个事务，把它们取消并恢复，释放资源，使得其它事务继续进行。 选择的标准是尽可能使撤销并恢复的代价最小，如撤销年轻的事务，撤销占有较少资源的事务，撤销具有最短运行时间的事务，撤销具有最长运行时间的事务等，使系统情况而定,层次式死锁检测 以层次方式组织成员DBMS中的死锁检测器 死锁发生时, 常常只涉及部分站点 层次检测的层次结构与网络拓扑结构有关 减少了对中心站点的依赖性，从而减少了传输开销,层次式死锁检测的步骤 树叶是各站点的局部死锁检测器，在本站点建立局部等待图 本站点的死锁检测器找出本站点局部等待图中的任何回路，并把有关潜在全局回路的信息发送给上一层死锁检测器 每个非本地死锁检测器只对它所涉及的紧挨下层进行死锁检测，合并这些接收到的有关潜在全局回路的信息，并找出任何回路 如果还有上层死锁检测器，将经过简化的有关潜在全局回路的信息发送给它上一层死锁检测器，由上一层死锁检测器再进行合并，找出任何全局回路 这样，逐层检测，直到最高层。,第0层 死锁检测器,第i层 死锁检测器,第i层 死锁检测器,局部 死锁检测器,局部 死锁检测器,局部 死锁检测器,局部 死锁检测器,简化潜在 死锁图,简化潜在 死锁图,简化潜在 死锁图,简化潜在 死锁图,简化潜在 死锁图,简化潜在 死锁图,层次式死锁检测方法示意图,分布式检测 每个站点的检测死锁责任相同, 站点之间交换信息(LWFG)，是为了确定全局死锁 EX是指的本地事务正在等待的其他事务所在的还不确定的站点 例子,站点1,站点2,T1,T2,T4,T3,EX,EX,信息传递方向 此处规定一种, 以避免多次重复传递 EX等待的事务号 等待EX的事务号 分布式死锁检测算法 使用局部信息建造LWFG, 该LWFG包含EX节点 对每次接收到的信息, 执行如下对LWFG的修改 对报文中的每个事务, 若LWFG中不存在, 则将其加入 从EX节点开始, 按照报文所给的信息, 建立一个到下一个事务的边 在新的LWFG中寻找不含EX的Loop, 若存在, 则检测到死锁 在新的LWFG中找到含有EX的Loop, 于是有潜在的死锁, 再按规定向外传送信息,基本概念 不通过互斥来支持串行性，而是通过在事务启动时赋给时标（时间戳）来实现 时标是用来唯一识别每个事务并允许排序的标识 如果 ts(T1) ts(T2) ts(Tn), 则调度器产生的序是: T1,T2, . Tn 规则 如果T1的操作O1(x)和T2的操作O2(x)是冲突操作, 那么, O1在O2之前执行, 当且仅当ts(T1)ts(T2),时标分配方法 全局时标 使用全局的单调递增的计数器 全局的计数器维护是个难题 局部时标 每个站点基于其本地计数器自治地指定一个时标 标识符由两部分组成：本地计数器值，站点标识符 站点标识符是次要的，主要是本地计数器值 可以使用站点系统时钟来代替计数器值,时标法思想 每个事务赋一个唯一的时标，事务的执行等效于按时标次序串行执行 如果发生冲突，是通过撤销并重新启动一个事务来解决的 事务重新启动时，则赋予新的时标 优点是没有死锁，不必设置锁 封锁和死锁检测引起的通信开销也避免了 但要求时标在全系统中是唯一的,时标性质 唯一性 单调性 全局唯一时间的形成与调整 每个站点设置一个计数器, 每发生一个事务, 计数器加一 发送报文时包含本地计数器值, 近似同步各站点计数器,计数器X 初值X=0 计数器Y 初值Y=10 站点1 站点2 时标 A D 时标 TS(A)= TS(D)= 因为X 改X=Y+1=11 B TS(B)= F 因为YX TS(C)= C TS(F)= 本地计数器 本地计数器 (或时钟) (或时钟),报文1,报文2,计数器,站点,基本时标法,规则 每个事务在本站点开始时赋予一个全局唯一时标 在事务结束前，不对数据库进行物理更新 事务的每个读操作或写操作都具有该事务的时标 对每个数据项x, 记下写和读操作的最大时标，记为WTM(x)和RTM(x) 如果事务被重新启动，则被赋予新的时标,基本时标法执行过程 令read_TS是事务对x进行读操作时的时标 若read_TSWTM(x)，则拒绝该操作, 事务重新启动 否则, 执行, 令RTM(x)=maxRTM(x), read_TS 令write_TS是事务对x进行写操作时的时标 若write_TS RTM(x) 或 write_TS WTM(x) ,则拒绝该操作, 事务重新启动 否则, 执行, 令WTM(x) = maxWTM(x), write_TS 缺点是重启动多,基本思想 一种消除重启动的方法 通过缓冲年轻的操作，直至年长的操作执行完成，因此操作不会被拒绝，事务也绝不被重启动 规则 每个事务只在一个站点执行, 它不能激活远程的程序, 但是可以向远程站点发读/写请求 站点i接收到来自不同站点j的读/写请求必须按时标顺序，即每个站点必须按时标顺序发送读/写数据请求，在传输中也不会改变这个顺序 每个站点都为其它站点发来的读/写操作开辟一个缓冲区, 分别保存接收到的读/写申请,假定某个站点k上,各个缓冲区队列都已不为空，即每个站点都已向它至少发送了一个读和一个写操作，就停止接收，处理在缓冲区中的操作 假定站点i至少有一个缓冲的读和缓冲的写来自网中其它站点, 根据规则2, Site i 知道没有年老的请求来自其它Site(因为按序接收, 所以不可能有比此更年老的请求到来, 年老的比年轻的先到),例子 已知站点i的缓冲区队列中有来自所有站点的读/写请求如下所示: 站点1 站点2 站点3 站点n R11 R21 R31 Rn1 R12 R22 R32 R13 R23 R24 W11 W21 W31 Wn1 W22 W32 Wn2 W23,执行步骤: (1) 设RT=min(Rij), WT= min(Wij) (2) 按下法处理缓冲区中的Rij和Wij a. 若队列中有 (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,存在问题和解决方法 如果一个站点从来不向某个站点发送操作的话，那么执行过程中的假定就不符合，操作就无法进行。解决办法是，周期性的发送带有时标的空操作 此方法要求网络上所有站点都连通，这在大系统中很难办到。为避免不必要的通信，可对无读写操作请求的站点，发送一个时标很大的空操作 此方法过分保守，一律按照时序来进行，其中包括了不冲突的操作,基本思想 保存了已更新数据项的旧值 维护一个数据项的多个版本 通过读取数据项的较老版本来维护可串行性，使得系统可以接受在其他技术中被拒绝的一些读操作 写数据项时，写入一个新版本，老版本依然保存 缺点 需要更多的存储来维持数据库数据项的多个版本 模式分类 基于时标排序 基于两阶段封锁,数据项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)，那么撤销并回滚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)中较大的一个,图示,写值,若读 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值,三种锁方式 读，写，验证 四种锁状态 读封锁（read_locked） 写封锁（write_locked） 验证封锁（certify_locked） 未封锁（unlocked） 锁相容性 标准模式锁相容性（写锁和读锁） 验证模式锁相容性（写锁、读锁和验证锁）,多版本2PL的思想 当只有一个单独的事务T持有数据项上的写锁时，允许其他事务T读该项X，这是通过给予每个项X的两个版本来实现的 一个版本X是由一个已提交的事务写入的 另一个版本X是每个事务T获得该数据项上写锁时创建的 当事务T持有这个写锁时，其他事务可以继续读X的已提交版本 事务T可以写X的值，而不影响X已提交版本的值 但是，一旦T准备提交，它必须在能够提交之前，得到持有写锁的数据项上的验证锁，要等写锁释放之后 一旦获得验证锁，数据项的已提交版本X被置为版本X的值，版本X被丢弃，验证锁被释放。,基本思想 对于冲突操作不像悲观方法那样采取挂起或拒绝的方法，而是让一个事务执行直到完成 基于如下假设 冲突的事务是少数（查询为主的系统中，冲突少于5%） 大多数事务可以不受干扰地执行完毕,事务的三个阶段 读段/计算：在数据对象的局部副本上执行事务，这时其他事务不能存取此副本。事务从DB读数据，执行计算，并且确定写集数据项的新值。写操作总是对局部副本，仅当验证通过后，在事务结束处，才将其写入DB。 验证段：检验并发事务的可串性，该阶段验证修改应用是否引起完整性（一致性）的丢失，验证阶段通过，才能进入写段，否则事务重启动 写段/提交：验证阶段通过，则把事务的更新应用于数据库，对数据进行更新，否