第八章分布式并发控制

第八章分布式并发控制基本概念并发控制问题并发控制定义基本锁的并发控制方法锁的类型封锁规则锁的兼容性锁的粒度第八章分布式并发控制两段封锁协议（2PL）基本的两段封锁协议严格的两段封锁协议（2PL）并发控制理论基础事务执行过程的形式化描述集中库的可串行化问题分布式事务的可串行化问题分布库并发控制方法1、并发控制问题并发控制是分布式事务管理的基本任务之一，目的是保证分布式数据库系统中的多个事务的高效并发执行。多个事务并发执行，就有可能产生操作冲突，Concurrencycontrolensurestheconsistencyandreliabilitypropertiesoftransactions.如：出现重复读错误或读取了脏数据等，造成数据库数据的不一致。§8.1基本概念§8.1基本概念（1）丢失修改错误初始x=100,若并行执行，执行结果为：T1：x=90；T2：x=80，最终结果x=80；结果导致T2的执行结果破坏了T1执行的结果，该种现象也称丢失修改错误。§8.1基本概念（2）重复读错误例8.1.2有两个并发执行的事务T1和T2，其中x是数据库中的一个属性，T1和T2操作序列如下所示：如：一事务（如：T1）重复读一数据项（x）时，得到不同的结果，该种现象称重复读错误。也称一个事务的执行受到了其它事务的干扰。§8.1基本概念（3）读脏数据错误例8.1.3有两个并发执行的事务T1和T2，其中x是数据库中的一个属性，T1和T2操作序列如下所示：可看到如下现象：事务T2读取了T1废弃的数据x，该种现象称读脏数据。应尽量避免读脏数据。因为，当事务T1废弃时，T2也必须废弃，即所谓的级联废弃。通常读脏数据会导致级联废弃。§8.1基本概念2、并发控制定义并发控制就是利用正确的方式调度并发操作，避免造成数据的不一致性，防止一个事务的执行受到其它事务的干扰，保证事务并发执行的可串行性。§8.1基本概念锁的基本思想是要求事务在对一数据项进行操作之前必须首先申请对该数据项进行加锁，申请成功后才可对其操作。如果该数据项已被其它事务加锁，则出现操作冲突，该事务必须等待，直到该数据项被解锁为止。§8.2基本锁的并发控制方法1、锁的类型锁一般分两种类型，排它锁（exlusive）和共享锁（shared）。排它锁常称为X锁或写锁；共享锁称为S锁或读锁。排它锁指当事务T对数据A施加排它锁之后，只允许事务T自己读写A，其它事务都不可读写A。共享锁指当事务T对数据A施加共享锁之后，其它事务和其它事务只能读取A。即共享锁允许多个事务同时访问同一数据项A。§8.2基本锁的并发控制方法2、封锁规则事务在执行过程中需对其访问的数据项进行加锁，访问结束要及时释放其对数据项加的锁，以便供其它事务访问，保证多个事务高度正确并行执行。具体封锁规则为：(1)事务T在对数据项A进行读/写操作之前，必须对数据项A施加读/写锁，访问后立即释放已申请的锁；(2)如果事务T申请不到希望的锁，事务T需等待，直到申请到所需要的锁，之后方可继续执行§8.2基本锁的并发控制方法3锁的兼容性锁一般分读锁和写锁。读锁是进行读操作时加的锁，允许多个事务同时完成读操作，即具有共享性；写锁是进行写操作时加的锁，只允许申请该锁的事务进行写操作，所以，写锁不具有共享性，而具有排它性。写锁和读锁的相容性见下表：§8.2基本锁的并发控制方法4、锁的粒度封锁数据对象的单位称锁的粒度，即指被封锁的数据对象的大小。锁的粒度也称锁的大小。系统根据自己的实际情况确定锁的粒度，锁的粒度可以是关系的字段属性、关系的元组、关系（也称文件）或整个数据库等。锁粒度的大小对系统的并发度和开销有一定影响，锁粒度越大，，系统的开销越小，但降低了系统的并发度。针对并发控制，系统的并发度与锁粒度成反比。如下表所示：§8.2基本锁的并发控制方法两段封锁协议（2PL）是数据库系统中解决并发控制的重要算法之一。遵循两段锁协议规则的系统可保证事务的可串行性调度。两段封锁协议的实现思想是将事务中的加锁操作和解锁操作分两阶段完成，并要求并发执行的多个事务要在对数据操作之前进行加锁，且每个事务中的所有加锁操作要在解锁操作以前完成。通常两段封锁协议分为基本的两段封锁协议和严格的两段封锁协议。在两段封锁协议实现中，系统的加锁方式分两种，一种为显示锁方式，另一种为隐式锁方式。显示锁方式是由系统加封锁命令实现；隐式锁方式是由系统自动加锁实现。§8.3两段封锁协议（2PL）1、基本的两段封锁协议基本的两段封锁协议的内容分两阶段，加锁阶段和解锁阶段。具体规则描述如下：阶段1：加锁阶段•事务在读写一个数据项之前，必须对其加锁；•如果该数据项被其它使用者已加上不相容的锁，则必须等待。阶段2：解锁阶段•事务在释放锁之后，不允许再申请其它锁；§8.3两段封锁协议（2PL）在事务执行过程中，两段封锁协议（2PL）的加锁、解锁示意图（图8.1）如下：§8.3两段封锁协议（2PL）例8.1.1中描述了事务T1和T2并行执行时产生了丢失修改错误。若采用两段封锁协议进行并行控制，如下图所示：从上图可见，当事务T1、T2申请写锁时，均申请不到，必等待，直到另一事务释放对数据项x的锁为止。如：T2废弃，释放读锁；则T1得到写锁，完成写操作。事务T2重启动后，读取x(事务T1执行的结果)，直至完成操作。因此，不会出现丢失修改错误。§8.3两段封锁协议（2PL）（1）不能重复读错误例8.1.2中描述了事务T1和T2并行执行时产生了重复读错误。若采用两段封锁协议进行并行控制，如下图所示：从上图可见，当事务T2申请写锁时，不能申请成功，必等待，当事务T1再次读数据项x时，读取的x值与第一次读到的值相同，不会出现重复读错误。§8.3两段封锁协议（2PL）§8.3两段封锁协议（2PL）2、严格的两段封锁协议（2PL）严格的两段封锁协议与基本的两段封锁协议内容基本上是一致的，只是解锁时刻不同。严格的两段封锁协议（2PL）是在事务结束时才启动解锁，保证了事务所更新数据的永久性。采用两段封锁协议（2PC）的事务执行过程为：begin_transaction→加锁→操作→提交/废弃（commit/abort）→解锁。§8.3两段封锁协议（2PL）提交/废弃（commit/abort）时解锁过程具体如下：（1）对commit的处理•释放读锁；•写日志；•释放写锁。（2）对abort的处理•释放读锁；•(反做)undo；•释放写锁；§8.3两段封锁协议（2PL）§8.3两段封锁协议（2PL）1、事务执行过程的形式化描述并发控制的主要目的是保证分布事务及分布式数据库的一致性。并发控制既要实现分布事务的可串行性，又要保持事务具有良好的并发度。无论集中式数据库，还是分布式数据库的并发控制均是以串行化理论为基础，并以它为模型来检验方法的正确性。按串行化理论，一个在数据库上运行的事务的所有操作，按其性质分为读和写两类。通常，一个事务Ti对数据项x的读操作和写操作记为Ri(x)和Wi(x)。一个事务Ti所读取数据项的集合，称为Ti的读集，所写的数据项的集合，称为的写集，分别记为R（Ti）和W（Ti）。§8.4并发控制理论基础例8.4.1设有事务T1，完成的操作如下：T1：x=x+1；y=y+1；其中x、y为数据库中的两个数据项。则：T1的操作可表示为：R1i(x)W1(x)R1(y)W1(y)；R（T1）={x，y}；W（T1）={x，y}；在一个数据库上，各个事务所执行的操作组成的序列，称为事务的历程，记为H，有时也称调度。其记录了各事务的操作顺序。对于一个历程上的任何两个事务，Ti和Tj，如果Ti的最后一个操作在Tj的第一个操作之前完成，或反之，则称该历程为串行执行的历程，简称为串行历程，否则称为并行历程。系统通常希望事务历程中的各个事务是并发的，但同时又等价于一个串行的事务历程，即事务历程是可串行化的。§8.4并发控制理论基础例8.4.2设有事务T1和T2，T1和T2完成的操作为：T1：R1(x)R1(y)W1(x)W1(y)；T2：R2(x)W2(y)；设有：历程H1和H2，H1和H2分别为：H1：R1(x)R1(y)W1(x)W1(y)R2(x)W2(y)H2：R1(x)R2(x)R1(y)W1(x)W1(y)W2(y)历程H1和H2也可用下图等价表示：在历程H1中，事务T1的所有操作都是在事务T2的操作之前完成的，因此该历程是串行历程。而在历程H2不满足串行历程的定义，因此是并行历程。§8.4并发控制理论基础2、集中库的可串行化问题无论在集中式数据库系统中，还是在分布式数据库系统中，事务的并发调度都要解决并行执行事务对数据库的冲突操作，使冲突操作串行执行，非冲突操作并行执行。只是在分布式数据库系统中，事务是分解为各个场地上的子事务的执行实现的。因此，分布式事务之间的冲突操作，转化为了同一场地上的子事务的冲突操作，分布事务的可串行性调度转化为了子事务的可串行性调度。下面先介绍可串行化涉及的概念，然后介绍集中库的可串行化问题。（1）可串行化定义定义在集中式数据库系统中的一个历程H，如果等价于一个串行历程，则称历程H是可串行化的。由可串行化历程H所决定的事务执行顺序，记为SR（H）。§8.4并发控制理论基础（2）事务的执行顺序事务的并发调度就是要解决并行执行事务对数据库的冲突操作。定义如果分别属于两个事务的两个操作Oi和Oj，操作同一个数据项，且至少其中一个操作为写操作，则Oi和Oj这两个操作是冲突的。如：R1(x)W2(x)和W1(x)W2(x)均为冲突操作。若在一个串行历程中，“”表示先于关系，对分别属于Ti和Tj的两个冲突操作Oi和Oj，若存在OiOj，则TiTj。§8.4并发控制理论基础（3）历程等价的判别方法如果一个历程H等价于一个串行历程，则称历程H是可串行化的。判断两个历程等价的定理和引理如下：定理8.1对于任意两个历程H1和H2等价的充要条件为：①在H1和H2中，每个读操作读出的数据是由相同的写操作完成的；②在H1和H2中，每个数据项上最后的写操作是相同的。引理对于两个历程H1和H2，如果每一对冲突操作Oi和Oj，在H1中有OiOj，在H2中也有OiOj，则H1和H2是等价的。§8.4并发控制理论基础例8.4.3设有三个历程H1、H2和H3，分别为：H1：R1(x)R1(y)W1(x)W1(y)R2(x)W2(x)；H2：R1(x)R1(y)W1(x)R2(x)W1(y)W2(x)；H3：R1(x)R1(y)R2(x)W1(x)W1(y)W2(x)。要求：判断历程H2和H3是否为可串行化的历程。从上面的历程H1中可看出，事务T1的所有操作都是在事务T2的操作之前完成的，因此可判断，历程H1是串行历程。§8.4并发控制理论基础下面根据两历程等价引理分别判断H2和H3是否与历程H1等价，若等价，则该历程是可串行化的历程。判别如下：①首先找出历程H1、H2和H3的冲突操作；②分别找出历程H2和H3中与历程H1的等价冲突操作，用“”表示。则结果有如下所示：H2的冲突操作H1的冲突操作H3的冲突操作R1(x)W2(x)R1(x)W2(x)R1(x)W2(x)W1(x)R2(x)W1(x)W2(x)R2(x)W1(x)W1(x)W2(x)W1(x)R2(x)W1(x)W2(x)可知，历程H2与历程H1等价，因此历程H2是可串行化的历程；历程H3与历程H1不等价，因此历程H3不是可串行化的历程。§8.4并发控制理论基础3、分布式事务的可串行化问题定义在分布式事务执行过程中，每个场地Si上的子事务执行序列，称为局部历程，用H（Si）表示。在分布式数据库系统中，将分布事务的可串行性调度转化为了以场地为基础的子事务的可串行性调度。用下面定理或引理判断分布式事务是否是可串行化的。§8.4并发控制理论基础定理对于n个分布式事务T1、T2、…Tn在m个场地上S1、S2、…Sm上的并发执行，记为E。如果E是可串行化的，则必须满足以下条件：（1）每个场地Si上局部历程H（Si）是