分布式数据库系统的并发控制算法综述.doc

分布式数据库系统的并发控制算法综述摘要：并发控制是分布式数据库事务管理中非常重要的一部分,其性能的优劣是衡量分布式数据库系统功能强弱和性能好坏的重要标志之一。并发控制是分布式数据库系统为了适应多用户操作所必须解决的问题。分布式数据系统是在集中式数据库系统技术的基础上发展起来的，并发控制也是分布式数据库研究的最关键热点问题之一。关键词：分布式数据库系统 并发控制 事务 算法一分布式数据库系统的概述分布式数据库系统是在集中式数据库系统的基础上发展起来的，是计算机技术和网络技术结合的产物。分布式数据库系统(DDBS)包含分布式数据库管理系统(DDBMS)和分布式数据库(DDB)。在分布式数据库系统中，一个应用程序可以对数据库进行透明操作，数据库中的数据分别在不同的局部数据库中存储、由不同的 DBMS进行管理、在不同的机器上运行、由不同的操作系统支持、被不同的通信网络连接在一起1。一个应用程序通过网络的连接可以访问分布在不同地理位置的数据库。它的分布性表现在数据库中的数据不是存储在同一场地。 更确切地讲，不存储在同一计算机的存储设备上。 这就是与集中式数据库的区别。从用户的角度看，一个分布式数据库系统在逻辑上和集中式数据库系统一样，用户可以在任何一个场地执行全局应用。就好那些数据是存储在同一台计算机上，有单个数据库管理系统(DBMS)管理一样，用户并没有什么感觉不一样。分布式数据库系统适合于单位分散的部门，允许各个部门将其常用的数据存储在本地，实施就地存放本地使用，从而提高响应速度，降低通信费用。分布式数据库系统与集中式数据库系统相比具有可扩展性，通过增加适当的数据冗余，提高系统的可靠性。在集中式数据库中，尽量减少冗余度是系统目标之一其原因是，冗余数据浪费存储空间，而且容易造成各副本之间的不一致性而为了保证数据的一致性，系统要付出一定的维护代价减少冗余度的目标是用数据共享来达到的。而在分布式数据库中却希望增加冗余数据，在不同的场地存储同一数据的多个副本,其原因是： 提高系统的可靠性、可用性当某一场地出现故障时，系统可以对另一场地上的相同副本进行操作，不会因一处故障而造成整个系统的瘫痪。 提高系统性能系统可以根据距离选择离用户最近的数据副本进行操作，减少通信代价，改善整个系统的性能。二并发控制的概述并发控制是指在多用户的环境先，对数据库进行并发操作进行规范的机制。并发控制是以事务为单位进行的，其作用主要是协调同一时间访问同一数据库文件的多个事务之间的关系，防止这些事务间发生冲突，产生一个可串行化得调度 。如果不对并发执行的程序进行必要的控制，那么即使没有故障和程序出错也会破坏数据库的一致性和完整性。因此，一个数据库系统有无并发控制机制，以及并发控制机制的优劣是衡量一个数据库系统功能强弱和性能好坏的重要标志之一。2DBMS的并发控制是以事务为单位进行的。数据库在执行事务时，要么执行事务中的全部操作，要么一个操作都不执行。当有多个事务对数据库进行操作时，如果对数据库进行操作的各个事务按顺序执行，即一个事务执行完全结束后，另一个事务才开始，则称这种执行方式为串行访问(Serial access)。如果DBMS可以同时接纳多个事务，事务可以在时间上重叠执行，则称这种执行方式为并发访问(Concurrent access)。在单CPU系统中，同一时间只能有一个事务占用CPU，若各个事务交叉使用CPU，则称这种并发方式为交叉并发。在多CPU系统中，可以允许多个事务同时占用CPU，这种并发方式称为同时并发。1. 并发控制的单位事务事务是数据库的逻辑工作单位，它是用户定义的一组操作序列。一个事务可以是一组SQL语句、一条SQL语句或整个程序。事务的开始和结束都可以由用户显示的控制，如果用户没有显式地定义事务，则由数据库系统按缺省规定自动划分事务。事务应该具有4种属性：原子性、一致性、隔离性和持久性。（1）原子性事务的原子性保证事务包含的一组更新操作是原子不可分的，也就是说这些操作是一个整体，对数据库而言全做或者全不做，不能部分的完成。这一性质即使在系统崩溃之后仍能得到保证，在系统崩溃之后将进行数据库恢复，用来恢复和撤销系统崩溃处于活动状态的事务对数据库的影响，从而保证事务的原子性。系统对磁盘上的任何实际数据的修改之前都会将修改操作信息本身的信息记录到磁盘上。当发生崩溃时，系统能根据这些操作记录当时该事务处于何种状态，以此确定是撤销该事务所做出的所有修改操作，还是将修改的操作重新执行。（2）一致性一致性要求事务执行完成后，将数据库从一个一致状态转变到另一个一致状态。它是一种以一致性规则为基础的逻辑属性，例如在转账的操作中，各账户金额必须平衡，这一条规则对于程序员而言是一个强制的规定，由此可见，一致性与原子性是密切相关的。事务的一致性属性要求事务在并发执行的情况下事务的一致性仍然满足。它在逻辑上不是独立的，它由事务的隔离性来表示。（3） 隔离性隔离性意味着一个事务的执行不能被其他事务干扰。即一个事务内部的操作及使用的数据对并发的其他事务是隔离的，并发执行的各个事务之间不能互相干扰。它要求即使有多个事务并发执行，看上去每个成功事务按串行调度执行一样。这一性质的另一种称法为可串行性，也就是说系统允许的任何交错操作调度等价于一个串行调度。串行调度的意思是每次调度一个事务，在一个事务的所有操作没有结束之前，另外的事务操作不能开始。由于性能原因，我们需要进行交错操作的调度，但我们也希望这些交错操作的调度的效果和某一个串行调度是一致的。 DM实现该机制是通过对事务的数据访问对象加适当的锁，从而排斥其他的事务对同一数据库对象的并发操作。（4）持久性系统提供的持久性保证要求一旦事务提交，那么对数据库所做的修改将是持久的，无论发生何种机器和系统故障都不应该对其有任何影响。例如，自动柜员机（ ATM）在向客户支付一笔钱时，就不用担心丢失客户的取款记录。事务的持久性保证事务对数据库的影响是持久的，即使系统崩溃。正如在讲原子性时所提到的那样，系统通过做记录来提供这一保证。DM没有提供显式定义事务开始的语句，第一个可执行的SQL语句(除CONNECT语句外)隐含事务的开始，但事务的结束可以由用户显式的控制。在DM中以下几种情况都结束 (正常，非正常)某一事务：（1）当某一连接的属性设置为自动提交，每执行一条语句都会提交；（2）遇到COMMIT/ROLLBACK语句，便提交/回滚一事务；（3）当系统的 DDL自动提交开关打开时（缺省为打开），遇到DDL语句则自动提交该DDL语句和以前的DML和DDL操作； （4）事务所在的程序正常结束和用户退出； （5）系统非正常终止时；三.并发的目的并发控制是分布式数据库系统中分布式事务管理的基本任务之一，在数据库管理系统中对事务采用并发机制的主要目的有两个：1、改善系统的资源利用率对于一个事务来讲，在不同的执行阶段需要的资源不同，有时需要CPU，有时需要访问磁盘，有时需要I/O、有时需要通信如果事务串行执行，有些资源可能会空闲；如果事务并发执行，则可以交叉利用这些资源，有利于提高系统资源的利用率2、改善短事务的响应时间设有两个事务T1 和T2，其中T1是长事务，交付系统在先；T2是短事务，交付系统比T1稍后。如果串行执行，则须等T1执行完毕后才能执行T2。而T2的响应时间会很长。一个长事务的响应时间长一些还可以得到用户的理解，而一个短事务的响应时间过长，用户一般难以接受。如果T1 和T2并发执行，则T2可以和T1重叠执行，可以较快地结束，明显地改善其响应时间。3二 .现行的并发控制算法目前在分布式数据库系统应用中传统的并发控制算法有两阶段封锁法、多粒度封锁法、时标排序法、多版本并发控制和乐观的并发控制 4。 2.1两阶段封锁法“两段”锁的含义事务分为两个阶段，第一阶段是获得封锁，也称为扩展阶段； 第二阶段是释放封锁，也称为收缩阶段。封锁是事项并发控制的一个非常重要的技术。所谓封锁就是事务T在对某个数据对象，例如，在标、记录等操作之前，先向系统发出请求，对其加锁。加锁后事务T就对数据库对象有了一定的控制，在事务T释放它的锁之前，其他事务不能更新此数据对象。2.2封锁类型DBMS通常提供了多种数据类型的封锁。一个事务对某个数据对象加锁后究竟拥有什么样的控制是由封锁类型决定的。基本的封锁类型有两种：排他锁（exclusive lock，简记为X锁）和共享锁（share lock简记为S锁）排他锁又称为写锁。若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他任何事务都不能再对A加任何类型的锁，直到T释放A上的锁。这就保证了其他事务在T释放A上的锁之前不能再读取和修改A。共享锁又称为读锁。若事务T对数据对象A加上S锁，则其他事务只能再对A加S锁，而不能加X锁，直到T释放A上的锁。这就保证了其他事务可以读A，但在T释放A上的S锁之前不能对A做任何修改。排他锁与共享锁的控制方式可以用下图的相容矩阵来表示。 在下图的封锁类型相容矩阵中，最左边一列表示事务T1已经获得的数据对象上的锁的类型，其中横线表示没有加锁。最上面一行表示另一事务T2对同一数据对象发出的封锁请求。T2的封锁请求能否被满足用Y和N表示，其中Y表示事务T2的封锁要求与T1已持有的锁相容，封锁请求可以满足。N表示T2的封锁请求与T1已持有的锁冲突，T2请求被拒绝。基于封锁的并发控制算法 ,是一种最常见的并发控制算法 ,其基本思想是事务访问数据项前要对该数据项封锁 ,如果已被其他事务锁定 ,就要等待 ,直到那个事务释放该锁为止。两阶段封锁算法的基本思想是一个事务可以被分成两个阶段 :成长阶段。事务只能获得新的数据项锁 ,而不能释放任何已持有的锁。 衰退阶段。事务只能释放已经持有的锁 ,而不能获得任何的新锁。两阶段封锁法保证了事务调度的可串行化 ,且限制了一个调度中可以发生的并发事务的数量。它的优点是实用 ,且可以避免由于并发冲突操作引起的数据错误 ;缺点是可能产生饥饿和死锁。传统的两阶段封锁方法有 :集中式两阶段封锁法、主副本两阶段封锁法和分布式两阶段封锁法。 2.2多粒度封锁法多粒度封锁法就是封锁的粒度不是单一的一种粒度 ,而是有多种粒度 ;允许多粒度树中的每个节点被独地封锁。在一个系统中同时支持多种封锁粒度供不同的事务选择封锁对象可以很大也可以很小，例如可以对整个数据库加锁，也可以对某个属性值加锁。封锁对象的大小成为封锁的粒度。粒度会影响并发控制和恢复的性能。多粒度树是以树形结构来便是多级封锁粒度，其根结点是整个数据库，表示最大的数据粒度，叶结点表示最小的数据粒度。选择封锁粒度的原则：封锁的粒度大小系统被封锁的对象少多并发度小高系统开销小大2.3时标排序法基于时标排序的并发控制算法的基本思想是选择一个事先的串行次序依次执行事务 ;为建立这个次序,在每个事务初始化时 ,事务管理器给每个事务 Ti分配一个在整个系统中唯一的时标 TS(Ti),时标具有唯一性和单调性 ,即同一事务管理程序所产生的两个时标将是单调递增的 ;事务的执行等效于按时标次序串行执行 ;如果发生冲突 ,是通过撤消并重新启动一个事务来解决的 ;事务重新启动时 ,则赋予新的时标。它的优点是无死锁 ,不必设置锁 ;它的缺点是重启动次数多。传统的时标排序法有基本时标排序法和保守时标排序法。时标和封锁技术之间的基本区别是封锁是使一组事务的并发执行（即交叉执行）同步，使用它等价于这些事务的某一串行操作；时标法也是使用一组事务的交叉执行同步，但是使它等价于这些事务的一个特定的串行执行，即由时标的时序所确定的一个执行。如果发生冲突，是通过撤销并重新启动一个事务解决的。事务重新启动，则赋予新的时标。 2.4 多版本并发控制多版本并发控制的基本思想是通过读数据项的一个较老的版本来维护可串行性 ,使得系统可以接受在其他技术中被拒绝的一些读操作 ;当某事务写一个数据项时 ,它写入了一个新版本 ,但是该数据项的老版本仍然被保存。它的缺点是需要更多的存储来维持数据库数据项的多个版本。传统的多版本并发控制算法有基于时间戳排序的多版本算法和两阶段封锁的多版本算法。多版本并发控制技术被很多数据库或存储引擎采用，如Oracle，MS SQL Server 2005+, PostgreSQL, Firebird, InnoDB, Falcon, PBXT, Maria等等。新的数据库存储引擎，几乎毫无例外的使用多版本而不是单版本加锁的方法实现并发控制，可以说多版本已经成为未来的发展趋势。52.5乐观的并发控制算法乐观的并发控制算法就是对于冲突操作 ,让一个事务执行直到完成。乐观并发控制算法的前提是冲突的事务是少数，大多数事务是可以不受干扰地执行完毕；读集包含写集，不存在对一个数据项只写二不读，数据库采用完全冗余方式储存数据。在乐观并发控制中，用户读数据时不锁定数据。在执行更新时，系统进行检查，查看另一个用户读过数据后是否更改了数据。如果另一个用户更新了数据，将产生一个错误。一般情况下，接收错误信息的用户将回滚事务并重新开始。该方法主要用在数据争夺少的环境内，以及偶尔回滚事务的成本超过读数据时锁定数据的成本的环境内，因此称该方法为乐观并发控制。它的优点是并行程度高。他的缺点是存储开销大，不必要的重启动程度高。2.6并发控制带来的一些问题 事务的并发操作提高了系统的运行效率，但也带来了一些问题，一下是并发控制带来的三个问题：1.丢失更新问题，两个事务T1和T2读入同一个数据并修改，事务T2提交的修改结果覆盖了事务T1提交的修改结果，导致事务T1的修改结果丢失。例如：时间更新事务T1数据库中x的值更新事务T2 t0 100 t1 FIND x t2 FIND x t3 x:=x-30 t4 x:=x * 2 t5UPDATE x t6 70 UPDATE x t7 2002.不一致分析问题（不可重读）事务T1读取数据后，事务T2执行更改操作，使事务T1无法再现前一次读取的结果。不可重复读包括以下几种情况:1. 事务T1读取某一数据之后，事务T2对其进行修改，使事务T1再次读取该数据时，读取的结果与上次不同;2. 事务T1按一定的条件读取某些数据记录以后，事务T2删除了其中的部分记录，使事务T1按相同的条件再次读取这些数据记录时，发现某些记录不存在了;3. 事务T1按一定的条件读取某些数据记录以后，事务T2插入了一些记录，使事务T1按相同的条件再次读取这些数据记录时，发现增加了某些记录。后两种关于记录的不可重复读现象也被称为幻象读(phantom read)现象。例如：时间更新事务T1数据库中x的值更新事务T2 t0 100 t1 FIND x t2 FIND x t3 x:=x-30 t4UPDATE x t5 70 3.依赖于未提交更新的问题（读脏数据）事务T1更改某一数据，并写入数据库，事务T2读取同一数据，但事务T1由于某种原因被撤销，此时事务T1更改过的数据恢复原来的值，使事务T2读取到的值与数据库中的值不同，只是操作过程中的一个过渡性的、不需要的、脏的数据。例如：时间更新事务T1数据库中x的值更新事务T2 t0 100 t1 FIND x t2 x:=x-10 t3 UPDATE x t4 90（脏数据） FIND x t5ROLLBACK t6 1003.其它并发控制算法3.1 PSL并发控制算法 PSL（Primary Site Locking）算法6的基本思想是：事务对一个文件的所有副本的访问都是由一个 PS(Primary Site Locking)事务控制，不同的文件可能会有不同的PS；事务在访问文件之前必须得到该文件的 PS的许可；当一个新事物启动时，它首先向访问文件的PS发送请求锁定信号 ,然后等待PS的回答;PS根据文件当前状况 ,或者允许事务的锁定请求信号 ,或者让事务排在等待队列中等待该文件锁定的解除。它的优点是不存在事务重新启动的问题。 3.2 EWP并发控制算法 EWP(Exclusive Writer Protocol)算法的基本思想是:事务对一个文件所有副本的访问都由一个EW事务控制 ,该事务不仅负责控制事务对该文件的访问 ,而且只有它才能实现对该文件的写操作 ;对含写操作的事务发生冲突时采取抛弃处理。它的优点是简单 ,不存在事务重新启动和死锁 ;它的缺点是不能实现事务整体上的可串行性 ,应用范围较窄。 3.3 EWL并发控制算法 EWL并发控制算法 7的基本思想是 :事务对一个文件所有副本的访问都由一个 EW/PS事物控制 ,当一个新事务启动的时候 ,它总是以 EWP算法机制运行,如果该新事务有更新操作 ,则向 EW/PS发送文件检测有无冲突 ;若没有冲突 ,则按 EWP算法执行下去;若有冲突 ,则 EW/PS将该请求放入该文件的等待队列中 ,重新启动该事物并动态切换到 PSL算法机制。它的优点是事务重新启动的次数少 ,每个事务最多重新启动一次 ,能保持事务整体上的可串行性 ,不存在数据库回溯问题。 3.4高优先级两阶段封锁法分布式高优先级两阶段封锁法 就是每个局部节点都有一个锁调度机制 ,该机制负责对该节点数据对象的加锁请求 ;当事务要访问某节点的数据对象时 ,它通过该节点的锁调度机智来对它所需的数据对象进行加锁。当该数据对象已被其他事务加锁时 ,就要按优先级来比较 ,优先级高的事务将重新获得加锁权,而优先级低的事务将被迫重启 ,局部事务将局部重启 ,全局事务将全局重启。 3.5扩充相容性多粒度多版本封锁法扩充相容性多粒度多版本封锁法的基本思想是8:将只读事务和更新事务分别处理 ,只读事务在执行时遵守多版本时间戳排序协议 ,而更新事务的执行将按基于两阶段有序相容性封锁的多粒度封锁协议进行 ,同时 为数据项的每个版本配置一个时间戳 ,该时间戳是一个计数器用于在事务提交时增加计数。其中,有序相容性封锁遵守以下规则 :在一组事务调度中 ,对于任意 2个并发访问同一数据对象 X的冲突操作 Pi(X)和 Qj(X),如果事务Ti的操作 Pi(X)的封锁先于 Tj中的操作 Qj(X)的封锁执行 ,则 Pi(X)必须先于 Qj(X)执行 ,此时称 Pi(X)的封锁有序相容于操作 Qj(X)的封锁。如果事Tj以有序相容性封锁方式从是事务 Ti处获得数据对象 X的封锁 ,则在事务Ti释放封锁之前 ,事务Tj不能释放任何封锁。 4.并发控制算法衡量准则分布式并发控制算法是复杂的,对其性能的分析,可以采用定性的、比较的方法 ,即根据某些尺度来比较各种方法的性能。例如 :可以根据系统吞吐量和响应时间来判断。而决定并发控制算法的因素有以下4个: (1)站点间通信的开销。它的衡量尺度是总的通信量、站点间相互通信的次数和站点间距离、网络结构和队列效应等； (2)局部处理的开销。它的衡量尺度是同步信息的维护和处理 ,同步信息包括锁、时间戳和版本数 ; (3)由该算法所引起的事务重启动的次数和费用 ; (4)由该算法所引起的事务阻塞的数量和每次阻塞的延迟时