小组成员周鸿玲彭晓静石子言.ppt

小组成员：周鸿玲 彭晓静 石子言,分布式数据库中的并发控制,并发控制的概念和理论分布式数据库系统并发控制的封锁技术分布式数据库系统中的死锁处理分布式数据库系统并发控制的时标技术分布式数据库系统并发控制的多版本技术分布式数据库系统并发控制的乐观方法英文讲稿transaction,分布式数据库中的并发控制,5.1.1 并发控制的概念：通常情况下在数据库中，总有若干个事务在运行，这些事务可能并发地存取相同的数据，称为事务的并发操作。分布式DBMS事务管理器的基本任务之一是执行分布式事务的并发控制。事务的并发操作提高了系统的运行效率，但也带来了一些问题，主要有以下三种：,图5.1(a)在时间t7丢失了事务T1的更新注：FIND表示从数据库中读值 UPDATE表示把值写回到数据库,1.丢失更新问题,2.不一致分析问题（不可重读）,图5.1（b）在t5时刻，事务T2仍认为x的值是100,3.依赖于未提交更新的问题（读脏数据）,图5.1（c）事务T2依赖于事务T1的未完成更新,T1T2Tn,集中式DB环境,DB(一致性约束),分布式DB环境,X,Y,Z,T1,T2,5.1.2事务可串行化理论的基本概念,事务的可串行性是指若干个事务并发执行的结果与按希望的顺序执行的结果相同时，称诸事务是可串行的。1.分布式事务的一个调度 通常，以Ti表示某个事务，以Ri（x）表示i事务对数据项x的读操作，以Wi（x）表示i事务对数据项x的写操作.事务的一个操作序列称为一个调度（schedule或history），一般以字母S表示。例如：S：R1（x）R2（y）W2（y）R2（x）W1（x）W2（x）S 是关于两个事务T1，T2的一个调度,集中式数据库中所给出的操作冲突的定义，两个同时访问同一数据项x的操作，如果其中至少有一个是写操作，那么称这两个操作是冲突的。注意两点：一.读操作不相互冲突，因此只有两种冲突：读-写冲突（或写-读冲突），及写-写冲突。二.两个操作可以属于同一事务或者两个不同的事 务，在后者的情况下，称为两个事务冲突。如果有两个事务Ti和Tj，Ti 的所有操作都先于Tj 的操作，那么这两个事务为串行执行的，必定不 会有冲突。,2.串行调度 设有一组事务T=T1，T2，Tn，如果事务Ti的所有操作都先于事务Tj的操作，记为TiTj。若一个调度S，其每个事务的执行均有TiTj，对所有的ij，记为S=TiTj 称S是一个串行调度。对一个串行调度来说，它总是可以正确的执行，执行它可以使数据库保持一致状态。因为：1）如果S正确执行完成，则S中的每一个事务都被提交，由于事务的原子性，保证了数据库的一致性。2）如果S在执行时发生故障，若Tk之前的事务都已提交，则夭折Tk，使数据库的状态恢复到Tk前的状态。该数据库也是一致的，因为Tk之前的事务都已提交。3）如果S在执行时发生故障，若Tk之前的事务有被夭,折的，则夭折Tk，重做Tk以前已被提交的事务，撤销Tk以前被夭折的事务，此时数据库也是一致的。3.可串行化调度 串行调度对不会引起冲突的操作要求过高。如果两个操作之间有冲突，这两个操作的执行顺序就很重要；可见事务的并发控制主要是正确处理并发执行的事务对数据库的冲突操作。串行化调度，是让有冲突的操作串行执行，非冲突的操作并行执行。5.1.3分布式事务的可串行化理论 1.事务 一个事务是一个偏序集：Ti=i，i，其中：1）i是操作符集合，包含Rix，Wix/x为 数据项 Ai，Ci；,2）Ai或Ci是i中的最后一个操作符，且只能出现 其中之一个；Ai为撤销（abort），Ci为提交（commit）；3）如果Rix，Wix i则它们必满足Rix iWix或Wix i Rix 4）Rix，Wix，Ai，Ci或公式的每一个都是事务Ti操作符序列中的一个操作。简单的说事物是一个读和写操作的序列2.冲突操作 如果有两个操作P和Q对同一数据x进行操作，其中有一个是写操作Wx则P和Q称为冲突操作。r1(A)w2(A)w1(A)w2(A)r1(A)w2(A),3.并发事务的一个调度（简称并发调度）如果T=T1，T2，Tn是一组并发执行事务，S是它的一个调度，则S=T，T简单的说调度就是事务操作的执行序列 其中：1）2）3）对任意两个冲突操作P，Q S，则有PP。一组事务的调度必须包含这些事务的所有操作调度中某个事务的操作顺序必须保持与该事务原有的顺序相同,4.串行调度如果一个调度S中的任意两个事务Ti和Tj，ij,若则称调度S为串行调度。即一个调度中不同事务的各个操作不会互相交叉，每个事务是相继执行的。简单的理解就是一个事务的第一个操作是在另一个事务的最后一个操作完成后开始.即调度中事务的各个操作不会交叉,每个事务相继执行.5.一致性调度 如果执行一个调度S，使数据库从一个一致状态变到另一个一致状态，则称调度S为一致性调度。显然，串行调度是一致性调度。,6.两个调度等价（冲突等价）两个调度S1和S2是等价的充分条件是：对于两个有冲突的操作Oi和Oj，若：Oi,OjS1，且OiOj,则Oi,Oj S2，且也有OiOj7.可串行化调度 与串行调度等价的调度称为可串行化调度。例5.1 考虑两个事务，分别定义为 T1：Read（x）T2:Read（x）xx+10 xx-20 Write（x）Write（x）Read（y）Read（y）y y-15 y y*2 Write（y）Write（y）Commit Commit,对于这两个事务，可产生如下五种调度：,如果将事务提交延迟到两事务操作完成之后执行，那么就有1）调度S1和S4是串行调度，也是一致性调度；2）调度S2和S1的冲突操作具有相同的序，因此也是等价调度；S2是可串行化调度也是一致调度；,3）调度S3虽是一个一致调度，但它不与S1或S4等 价，所以S3不是可串行化调度；4）调度S5和S4等价，所以S5是一致调度，也是可 串行化调度。由此可见：1）同一事务集上的可串行化调度，结果未必相同；S5和S22）一个可串行化调度必定与某个串行调度等价，且 是一致调度；3）一致调度不一定是可串行化调度；S34）同一事务集的几个可串行化调度，它们的结果未 必相同。,5.1.4 分布式事务的可串行化调度 1.使用优先图判别可串行化调度 算法5.1测试调度S的可串行化1）对于调度S中的事务T1，在图中创建一个节点T1。2）对于每一种这样的情形：如果S中在Ti执行了W（x）操作后执行Tj的R（x）操作，那么在优先图中创建一条边（Ti-Tj）。3）对于每一种这样的情形：如果S中在Ti执行了R（x）操作后执行Tj的W（x）操作，那么在优先图中创建一条边（Ti-Tj）。4）对于每一种这样的情形：如果S中在Ti执行了W（x）操作后执行Tj的W（x）操作，那么在优先图中创建一条边（Ti-Tj）5）当且仅当优先图中没有环路时，调度S是可串行化的。,2.分布式数据库中可串行化理论的扩展可串性理论可以直接扩展到无重复副本的分布式数据库中。事务在每个站点上的执行调度称作局部调度如果数据库无重复副本的分布式数据库，并且每个局部调度都是可串调度，只要这些局部调度的序一致，则它们的并（全局调度）也是可串调度3.单副本可串行化一个单副本可串行化的全局调度必须满足以下条件：1）每一个局部调度必须是可串行化的2）两个冲突操作在他们同时出现的各个局部调度中，必须具有相同的相对顺序。,4.读一个/写全部副本控制协议 对逻辑数据项x上的一个读操作，只映射到x的某个物理数据项xj上，而对逻辑数据项x的写操作，则映射到x的物理数据项的全集上，此协议通常称为“读一个/写全部”（ROWA）协议5.1.5并发控制机制的常用方法及其分类 1.使用协议或规则保证调度是可串行化的 常用的协议有：两阶段封锁协议，它基于的是对数据项进行封锁，以阻止并发事务受到其他 事务的干扰,2.并发控制机制常用的方法及其分类 并发控制机制划分为两种类型：悲观并发控制法和乐观并发控制法 悲观算法使事务的并发执行在执行生命周期的开始就同步化，而乐观算法则将同步化延迟到事务执行周期的结束。,并发控制算法的分类,5.2分布式数据库系统并发控制的封锁技术,5.2.1基于封锁的并发控制方法概述 基于封锁（locking）的并发控制方法的基本思想：事务访问数据项前要对该数据项封锁，如果已被其它事务锁定，就要等待，直到那个事务释放该锁为止。1.锁的粒度、类型和操作 锁的粒度是指锁定数据项的范围：一个数据项可以是下列的任何一种：1）一个数据库记录；2）数据库记录中的一个字段值；3）一个磁盘块（页面）；4）一个完整的文件；5）整个数据库；,数据项尺寸越大，允许的并发程度越低 数据项尺寸越小，数据库中项的数量越多。（2）锁的类型 在读/写封锁模式中，分为共享锁（shared-S锁，也称读锁）排他锁（exclusive-X锁，也称拒绝锁或写锁）（3）锁的操作 在读/写封锁模式中，存在三种锁的操作，分别是 read-lock（x）（读封锁）write-lock（x）（写封锁）unlock（x）（解锁）,2.封锁准则和锁的转换（1）封锁准则 采用共享/排他封锁模式时，系统必须实施下列规则：1）事务T在执行任何read-item（x）操作之前，必须先执行read-lock（x）操作或write-lock（x）操作。2）事务T在执行任何write-item（x）操作之前，必须先执行write-lock（x）操作。3）如果事务T执行任何read-lock（x）操作，数据项X必须没有加锁或者已经加了读（共享）锁，否则事务T的这个操作不能执行。4）如果事务T执行任何write-lock（x）操作，数据项X必须没有加锁，否则事务T的这个操作不能执行。5）事务T在完成所有read-item（x）操作和write-item（X）操作之后，必须执行unlock（x）操作,6）如果事务T已经持有数据项X上的一个读（共享）锁或者一个写（排他）锁，那么unlock（X）操作。7）如果事务T已经持有数据项X上的一个读（共享）锁或者一个写（排他）锁，那么它不能再执行 write-lock（X）操作。8）如果事务T没有持有数据项X上的一个共享（读）锁或者一个排他（写）锁，那么它不能执行unlock（X）操作。上述的规则也称锁的相容性规则。（2）锁的转换 一个事务T先执行了read-lock（X）操作，然后它可以通过执行write-lock（X）操作来升级（Upgrade）该锁。,如果当事务T要执行write-lock（X）操作时，它是持有数据项X上读锁的唯一事务，那么该锁就可以被升级；否则，事务必须等待。一个事务T也可能执行write-lock（X）操作，之后它可以通过执行read-lock（X）操作来降级（Downgrade）该锁。如下图5.4 不遵守两阶段封锁协议的两个事务,3.基本封锁算法（1）简单的分布式封锁方法 数据更新时，要将同一数据的全部副本封锁，然后 对其进行更新，更新完成后解除全部上述封锁。（2）主站点封锁法 模拟集中式，选定一个站点定义为“主站点”，负责系统全部封锁管理。所有站点都向这个主站点提出封锁和解锁请求，所有封锁和解锁信息都被传送到那个主站点管理和保存，然后有主站点去处理封锁事宜。（3）主副本封锁法 该方法不指定主站点，而对每个数据项指定一个主副本，不同数据项的主副本放在不同的站点上。,当处理程序对某个数据项进行操作时，先对此数据项的主副本进行封锁，然后再进行操作，这就意味着对此数据项的所有副本都封锁。（4）快照方法快照方法类似于视图的一种导出关系，但又与视图不同。它是实际数据的暂时凝聚，是数据库的一种存储方式。快照方法不考虑数据的复制，只考虑每一数据的“主副本”和定义在这些“主副本”上的任意多个快照。快照可以定义为一个或多个“主副本”的部分拷贝，也可以定义为某个或某些“主副本”的全拷贝。,5.2.2两阶段封锁协议,基本2PL协议,如果一个事务所有的封锁操作（读封锁和写封锁）都放在第一个解锁操作之前，那么就说该事务遵守两阶段封锁协议。事务的执行中Lock的管理分成两个阶段上升阶段(生长阶段)获取Lock阶段收缩阶段 释放Lock阶段 2PL可以保证事务执行的可串性.,开始,加锁点,结束,事务执行过程,获得锁,释放锁,两阶段锁协议,一个著名的理论是：遵守2PL规则的并发控制算法所产生的调度都是可串行化的，也就不再需要检测调度的可串行化性。,基本2PL协议实现的难点是,锁管理器必须要知道事务的锁点位置如果事务在开始释放Lock后又Abort时,将引起连锁夭折(cascading aborts)大多数2PL调度器实现的是严格2PL(S2PL)2.保守的、严格的、严酷的两阶段封锁协议 严格的2PL协议中，事务T在提交或撤销之前，绝对不释放任何一个排他（写锁）锁；在事务结束时（提交或撤销），同时释放所有的锁。如下图所示,开始,结束,事务执行阶段,获得锁,释放锁,严格2PL(Strict Two-phase Locking)协议,数据项使用,保守的2PL要求事务在开始执行之前就持有所有它要访问的数据项上的锁。在严酷2PL中，事务在提交或撤销之前，不能释放任何一个锁（排他的或共享的）。注意保守2PL与严酷2PL之间的区别是：前者，事务必须在开始之前封锁它所需要的所有数据项，因此，一旦事务开始就处在收缩阶段；而对后者，直到事务结束（提交或撤销）后才开始解锁，因此事务一直处于扩张阶段，直到结束。,5.2.3两阶段封锁协议的实现方法1.集中式两阶段锁(C2PL)协议的实现方法 主站点2PL算法：把封锁管理程序的职责仅限定到某个单独的站点上。这就意味着只有一个站点拥有封锁管理程序，而其他站点上的事务管理程序是同这个封锁管理程序进行通信，而不是同它们自己站点上的封锁管理程序（协调TM）进行通信。,2.主副本两阶段锁协议的实现方法 主副本2PL(PC2PL)实现方法是对集中式2PL实现方法的扩展，这种方法是在一些站点上实现封锁管理，每一个封锁管理程序管理所指定的一组封锁单元上的锁。事务管理程序向封锁管理程序发出对某一特定封锁单元的封锁和释放的请求。因此这一算法把每一个数据项的副本都作为其主要副本。3.分布式两阶段锁协议的实现方法分布式两阶段锁（D2PL）协议实现方法力求在每个站点实现封锁管理程序。如果数据库没有被复制，分布式两段锁降级为主副本两阶段锁算法。如果数据已被复制，事务将执行ROWA副本控制协议。,分布式2PL事务管理算法与C2PL-TM（集中式两阶段锁事务管理算法）相似，但有两处重大的改进。,参与者 DPs,加锁请求,操作,分布式2PL的通信结构,协调者 TM,参与者 LMs,操作结束,释放锁,1）在 C2PL-TM中，向中心站点封锁管理程序发送的信息，在D2PL中，将发送给所有参与站点的封锁管理程序。2）操作并不通过协调者事务管理程序传到数据处理器，而是通过参与者的封锁管理程序。5.2.3多粒度封锁与意想锁 1.多粒度封锁 多粒度树的根节点是整个数据库，表示最大的封锁数据粒度，叶节点表示最小的封锁数据粒度。,数据库,段1,段,.,多级粒度树,关系nn,关系11,.,.,多粒度封锁协议允许多粒度树中的每个节点被独立地封锁。对一个节点封锁意味着这个节点的所有后裔节点也被加以同样类型的锁。显示封锁：是因事务的要求直接对数据对象封锁；隐式封锁：是该数据对象没有直接独立封锁，是由于其上级节点封锁而使该数据对象加上了锁。2.意向锁 意向锁的含义是如果对一个节点加意向锁，则说明该节点的下层节点正在被封锁；意向锁的思想是：对于一个事务，沿着从根节点到目标节点的路径，指出将在该节点的某个后代节点上需要锁的类型（共享或排他）。,T2,T1,X,SIX,S,IX,IS,Y=yes，表示相容的请求 N=no，表示不相容的请求,(a)数据锁的相容矩阵,(b)锁的强度的偏序关系,锁的相容矩阵,存在三种类型的意向锁：1）意向共享锁（IS）2）意向排他锁（IX）3）共享意向排他锁（SIX）,多粒度封锁协议：1）必须遵守锁的相容性规则。2）必须首先封锁树的根节点，可以用任何一种方式的锁。3）只有当节点N的父节点已经被事务T以IS或IX方式封锁后，节点N才可以被T以S或IS方式封锁。4）只有当节点N的父节点已经被事务T以IX或SIX方式封锁后，节点N才可以被T以X、IX或SIX方式封锁。5）只有当事务T还没有释放任何节点时，T才可以封锁一个节点（为了保证2PL协议）6）只有当事务T当前没有封锁节点N的任何子节点时，T才可以为节点N解锁。,db,f1,f2,P11,P12,P1n,P21,P22,r111r11j,P2n,r121r12j,r1n1r1nj,r211r21j,r221r22j,r2n1r2nj,多粒度级别封锁的粒度层次结构,为了说明MGL协议如上图考虑以下三个事务：1）T1要更新记录r111和记录r211；2）T2要更新页P12的所有记录；3）T3要读取记录r11j和整个f2文件；,