数据库系统的并发控制

并发控制在事务一章中,我们已经介绍了由于多个事务并发执行可能引起三种异常：读脏数据、不可重复读、重写未提交的数据。引起这些异常的原因是并发操作破坏了事务的隔离性。并发控制的目的就是用正确的方式调度并发操作，使事务之间不会相互影响，即保证并发运行事务的可串行性。一、基于锁的并发控制协议一个保证可串行性的方法是在互斥的方式下存取数据，即当一个事务存取数据时不允许其他事务修改这个数据项。（一）、锁的概念锁可以分为两种类型：（1）共享锁如果事务T得到了数据项Q上的共享锁，则T可以读这个数据项，但不能写这个数据项。共享锁表示为S。（2）互斥锁如果事务T得到了数据项Q上的互斥锁，则T即可以读这个数据项，也可以写这个数据项每个事务在存取一个数据项之前必须获得这个数据项上的锁。一个事务需要获得的锁的类型取决于它将在数据项上执行什么样的操作。给定各种锁的类型，我们可以如下定义这个锁集合上的相容关系。令A和B表示任意类型的锁，设事务Ti在数据项Q上要求一个A型锁，事务Tj已经在Q上有一个B型锁，如果事务Ti能够获得Q上的A型锁，则说A型锁和B型锁是相容的。下图表示锁相容矩阵sxstruefalsexfalsefalse共享锁可以被多个同时拥有，但对于互斥锁，只有当一个数据项上的所有锁都被释放时，一个事务才能获得在该事务上的互斥锁。二、封锁协议在运用X锁和S锁对数据对象进行加锁时，还需要约定一些规则，例如：何时申请X锁或S锁、持锁时间、何时释放等，这些规则称为封锁协议。对封锁方式规定不同的规则，就形成了各种不同的封锁协议。T1READ(B)B:=B-50WRITE(B)READ(A)A:=A+50WRITE(A)commitT2READ(A)READ(B)DISPLAY(A+B)commitT1完成两个帐户之间的转帐，而T2显示两个帐户的余额之和如果串行执行T2显示的值为300T1T2LOCK_X(B)READ(B)B:=B-50WRITE(B)UNLOCK(B)LOCK_S(A)READ(A)UNLOCK(A)LOCK_S(B)READ(B)UNLOCK(B)DISPLAY(A+B)commitLOCK_X(A)READ（A）A:=A+50WRITE(A)UNLOCK(A)commitS事务T2显示的值为250三、两阶段锁协议两段锁协议要求每个事务分为两个阶段进行数据锁的加锁和解锁。阶段1加锁阶段在这个阶段，事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁阶段2解锁阶段在这个阶段，事务可以释放任何数据项上的任何类型的锁，但是不能申请任何锁。每个事务开始后即进入加锁阶段，申请获得所有的锁，当事务第一次释放锁时，该事务进入解锁阶段。进入解锁阶段的事务不能再申请任何锁。两段锁协议的两种变体：•Stricttwo-phaselockingprotocol（STPL）•Rigoroustwo-phaselockingprotocol(RTPL)STPL在两段锁协议的基础上，又加入了如下附加条件：被一个事务所持有的排它锁必须在该事务提交时才能释放。这一需求保证了任何尚未提交的数据不可能被其它事务所读取。RTPL在两段锁协议的基础上，加入了如下附加条件：一个事务所持有的所有锁只有当提交时才能被释放，可以证明如果使用RTPL，多个事务可以依照提交顺序串行化。T1LOCK_S(A)READ(A)LOCK_X(B)UNLOCK(A)READ(B)B:=B-50WRITE(B)DISPLAY(A+B)UNLOCK(B)COMMITT2LOCK_X(A);READ(A)A:=A+50WRITE(A)UNLOCK(A)COMMITSPTLT1LOCK_S(A)READ(A)LOCK_X(B)READ(B)B:=B-50WRITE(B)DISPLAY(A+B)UNLOCK(B)UNLOCK(A)COMMITT2LOCK_X(A);READ(A)A:=A+50WRITE(A)UNLOCK(A)COMMITRPTLT1READ(a1)READ(a2)•••••••••READ(an)WRITE(a1)commitT2READ(a1)READ(a2)DISPLAY(a1+a2)CommitT1在对a1进行写操作，并且这个操作是事务的最后一个操作，如果为a1开始时就加一个互斥锁，那么只有当T1事务结束之后才能进行事务T2的操作，降低了并行性。我们能够进一步改善两段锁协议，可以设计一个机制实现共享锁和互斥锁之间的转换。当一个事务将共享锁转换为互斥锁时，这个事务可能需要等待其他事务释放在该数据上的锁。T1LOCK_X(B)READ(B)B:=B-50WRITE(B)LOCK_X(A)READ（A）A:=A+50WRITE(A)UNLOCK(A)UNLOCK(B)T2LOCK_S(A);READ(A)LOCK_S(B)READ(B)DISPLAY(A+B)UNLOCK(A)UNLOCK(B)造成了死锁处于永久等待死锁的预防我们可以通过给每个事务一个优先级来预防死锁，确保一个优先级较低的事务等待优先级较高的事务。赋予优先级的一个方法是当事务启动时给每个事务一个时间戳，时间戳越低，优先级越高，即越老的事务优先级越高。如果一个事务Ti在某一数据上请求一个锁，并且事务Tj在该事务上拥有一个互斥锁，锁管理器能采用两种策略之一：Wait-die：如果Ti的优先级更高，它可以等待，否则将被放弃Wound-wait：如果Ti的优先级更高，则放弃Tj，否则Ti等待。上面两种策略，都可以防止死锁。我们应该保证没有一个事务将永远不被执行。采取的策略是当一个事务被放弃时并且重新开始时，它应该被给予与上一次同样的时间戳。DATAT2(10)持有T1（5）T3（15）Wait-idle:T1：WAITT3：ROLLBACKWound-wait:T1:T2ROLLBACKT3:WAIT死锁的检测与处理死锁是比较少见的，并且即使存在，也涉及到较少的事务。因此，与其采取措施来预防死锁，还不如对死锁进行检测，如果出现及时对其处理。为了检测死锁，锁管理器要维护一个等待图，在等待图中的一个节点是对应着一个活动事务，当Ti等待Tj来释放一个锁时，那么在图中出现了一个从Ti到Tj的边。T1T2T3T4S(A)R(A)X(B)W(B)S(B)S(C)R(C)X(C)X(B)X(A)T1T2T4T3封锁的粒度封锁对象的大小称为封锁粒度。以关系数据库为例，封锁对象可以是这样一些逻辑单元：属性值、属性值的集合、元组、关系、索引项、整个索引直至整个数据库。封锁粒度与系统的并发度和并发控制的开销密切相关。封锁的粒度越大，并发度越小，系统开销也小。反之，封锁的粒度越小，并发度高，但系统的开销也大。选择封锁粒度时，应同时考虑系统开销和并发度两个因素，以求达到最大的效果。多粒度封锁多粒度封锁是指在一个系统中同时支持多种封锁粒度。多粒度锁定协议支持多种并发控制粒度的并发控制协议。多重粒度树：多种粒度数表示多种粒度的嵌套。DBA1A2FaFbFcabdcfe多粒度协议允许多重粒度树中的每个节点被独立地加锁。这里我们使用共享和互斥两种类型的锁。一个节点被加锁意味着这个节点的所有后裔节点也被加以同样类型的锁。如果一个事务要对某个节点加锁，那么必须搜索从根到该节点路径上的所有节点，如果在这些节点中的一个或多个上加有互斥锁，则该事务必须等待。这种方法的效率很低，更为有效的方法是引进一个新锁，称为意向锁。任何一个节点被加锁时，它的先辈节点都被先被加以意向锁。意向锁分为三种：一种是共享意向锁，简记为IS另一种是互斥意向锁，简记为IX一种是共享意向互斥锁，简记为SIX。如果一个节点被加以IS锁，则该节点的后裔节点正在被加共享锁；如果一个节点被加以IX锁，则该节点的后裔节点正在被加互斥锁。如果一个节点被加以SIX锁，则以该节点为根的子树已经被加以共享锁，而该节点的后裔正在被加以互斥锁。ISIXSSIXXIStruetruetruetruefalseIXtruetruefalsefalsefalseXtruefalsetruefalsefalseSIXtruefalsefalsefalsefalseXfalsefalsefalsefalsefalse多重粒度锁协议1、必须遵守上面的相容矩阵2、多重粒度树的根首先被加锁，锁的类型不限3、仅当Q的父节点已经被T加以IS或IX锁时，Q才可以被T加S或IS锁。4、仅当Q的父节点已经被T加以IS或SIX型锁时，Q才可以被T加X、SIX或IS型锁。5、仅当T还没有释放过任何锁时，T才可以对节点加锁6、仅当Q的后裔节点都不被T加锁时，T才可以解锁Q。从多重粒度协议可以看出加锁时，采用的从上向下的顺序。而解锁时，采用的是从下向上的顺序。例：假定事务T1读Fa的a记录，T1锁定路径为：databaseA1Fa假定事务T2更新Fa的记录bISISISaSbdatabaseA1FaIXXIXIX假定事务T3读Fa的所有记录。databaseA1FaISISS假设T4要读整个数据库：databaseS上述四个事务中，T1、T3、T4可以并发执行。事务T2可以同事务T1并发执行，但不能同事务T3、T4并发执行。时间印协议时间印协议是另一种保证事务串行性的协议，它与基于锁的协议不同的地方是：事先选择事务的串行顺序。时间印的概念：为系统中的每个事务Ti，我们为其分配一个唯一的确定值，称为时间印，记做TS（Ti）。Ti的时间印是在它运行之前分配的。如果事务Tj在事务Ti的时间印被分配后进入系统，则TS(Ti)TS(Tj)，时间印协议必须保证所产生的调度等价于一个串行调度，在这个串行调度中Ti先于Tj。有两种简单的方法来实现这一机制：1、使用系统时钟值作为时间印2、使用逻辑计数器的值作为时间印为了实现上述时间印协议，为每个数据项分配两个时间印值。（1）、W_TS(Q)=MAX{TS(Ti)Ti成功执行了WRITE(Q)}（2）、R_TS(Q)=MAX{TS(Ti)Ti成功执行了READ（Q）}时间印协议定义如下：（1）、设事务T要执行READ(Q)a、如果TS(T)W_TS(Q),则T所要求的Q值已经被具有较大时间印的事务重写，所以拒绝T的READ(Q)操作，并放弃T。b、如果TS(T)=W_TS(Q),则执行这个READ(Q)命令，并令R_TS(Q)为MAX{R_TS(Q),TS(T)}（2）、设事务T要求执行WRITE(Q)a、如果TS(T)R_TS(Q)，则T要写的Q值已经被一个较大时间印的事务读过，所以拒绝执行这个WRITE(Q)操作，并放弃Tb、如果TS(T)W_TS(Q),则T要写一个已经过时的Q值，所以拒绝执行这个WRITE(Q)操作，并放弃T。c、如果TS(T)不满足（1）和（2）的条件，则执行这个WRITE(Q)操作，令W_TS(Q)=MAX{W_TS(Q),TS(T)}。由上述时间印协议放弃的事务T将重新分配一个新的时间印，并重新启动执行。