分布式数据库系统的并发控制算法综述摘要：并发控制是分布式数据库事务管理中非常重要的一部分,其性能的优劣是衡量分布式数据库系统功能强弱和性能好坏的重要标志之一。

并发控制是分布式数据库系统为了适应多用户操作所必须解决的问题。

分布式数据系统是在集中式数据库系统技术的基础上发展起来的，并发控制也是分布式数据库研究的最关键热点问题之一。

关键词：分布式数据库系统并发控制事务算法一．分布式数据库系统的概述分布式数据库系统是在集中式数据库系统的基础上发展起来的，是计算机技术和网络技术结合的产物。

分布式数据库系统(DDBS)包含分布式数据库管理系统(DDBMS)和分布式数据库(DDB)。

在分布式数据库系统中，一个应用程序可以对数据库进行透明操作，数据库中的数据分别在不同的局部数据库中存储、由不同的 DBMS进行管理、在不同的机器上运行、由不同的操作系统支持、被不同的通信网络连接在一起[1]。

一个应用程序通过网络的连接可以访问分布在不同地理位置的数据库。

它的分布性表现在数据库中的数据不是存储在同一场地。

更确切地讲，不存储在同一计算机的存储设备上。

这就是与集中式数据库的区别。

从用户的角度看，一个分布式数据库系统在逻辑上和集中式数据库系统一样，用户可以在任何一个场地执行全局应用。

就好那些数据是存储在同一台计算机上，有单个数据库管理系统(DBMS)管理一样，用户并没有什么感觉不一样。

分布式数据库系统适合于单位分散的部门，允许各个部门将其常用的数据存储在本地，实施就地存放本地使用，从而提高响应速度，降低通信费用。

分布式数据库系统与集中式数据库系统相比具有可扩展性，通过增加适当的数据冗余，提高系统的可靠性。

在集中式数据库中，尽量减少冗余度是系统目标之一．其原因是，冗余数据浪费存储空间，而且容易造成各副本之间的不一致性．而为了保证数据的一致性，系统要付出一定的维护代价．减少冗余度的目标是用数据共享来达到的。

而在分布式数据库中却希望增加冗余数据，在不同的场地存储同一数据的多个副本,其原因是：①．提高系统的可靠性、可用性当某一场地出现故障时，系统可以对另一场地上的相同副本进行操作，不会因一处故障而造成整个系统的瘫痪。

②．提高系统性能系统可以根据距离选择离用户最近的数据副本进行操作，减少通信代价，改善整个系统的性能。

二．并发控制的概述并发控制是指在多用户的环境先，对数据库进行并发操作进行规范的机制。

并发控制是以事务为单位进行的，其作用主要是协调同一时间访问同一数据库文件的多个事务之间的关系，防止这些事务间发生冲突，产生一个可串行化得调度。

如果不对并发执行的程序进行必要的控制，那么即使没有故障和程序出错也会破坏数据库的一致性和完整性。

因此，一个数据库系统有无并发控制机制，以及并发控制机制的优劣是衡量一个数据库系统功能强弱和性能好坏的重要标志之一。

[2]DBMS的并发控制是以事务为单位进行的。

数据库在执行事务时，要么执行事务中的全部操作，要么一个操作都不执行。

当有多个事务对数据库进行操作时，如果对数据库进行操作的各个事务按顺序执行，即一个事务执行完全结束后，另一个事务才开始，则称这种执行方式为串行访问(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),时标具有唯一性和单调性 ,即同一事务管理程序所产生的两个时标将是单调递增的 ;事务的执行等效于按时标次序串行执行 ;如果发生冲突 ,是通过撤消并重新启动一个事务来解决的 ;事务重新启动时 ,则赋予新的时标。