基于封锁的事务并发控制概述
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于封锁的事务并发控制概述范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要:叙述了关系型数据库管理系统中的事务管理和基于锁的事务并发控制方法。详细介绍了事务的串行化调度方法中的锁技术和锁协议,并深入讨论了锁的管理、死锁处理、幻影问题和其它加锁过程中可能出现的一些问题。
关键词:数据库管理系统;事务;并发控制;封锁
中图分类号:TP311.131 文献标识码:A文章编号:1007-9599 (2010) 04-0000-03
Lock-Based Transaction Concurrency Control Overview
Lu Chenglang,Xu Hupeng
(Wenzhou University,Oujiang College,Wenzhou325035,China)
Abstract:An overview on the management of lock-based concurrency control of transactions is presented in this paper.The locking protocols and locking techniques of the transaction concurrency control are investigated in detail, and the approach to avoiding phantom problem as well as the way for handling dead-locking are discussed in depth.
Keywords:Database management systems;Transaction;Concurrency control;Lock
一、引言
事务是用户定义的一组数据库操作序列。事务的执行结果将使数据库从一个一致性状态转变到另一个一致性状态。为了提高吞吐量,系统中常常是多个事务并发执行。这会产生多个事务同时存取同一数据的情况,从而破坏数据库的一致性。所以数据库管理系统(Database Management System,DBMS)必须提供并发控制机制,使得并发的事务在冲突的时候被串行化执行。这种调度称为可串行化调度。其中基于封锁的并发控制机制是一种被广泛应用于商业DBMS中的并发控制机制。
二、事务的特性和并发的数据不一致性
事务具有ACID特性:原子性(Atomicity),一致性(Consistency),隔离性(Isolation)和持续性(Durability)。原子性指:事务包含的所有操作要么全部被执行,要么都不被执行;一致性指:事务的执行结果必须使数据库从一个一致性状态变到另一个一致性状态;隔离性指:在事务被提交以前,其操作结果对于其他事务不可见;持续性指:一旦事务成功提交,其对数据库中数据的改变是永久的。事务是并发控制的基本单位,保证事务的ACID特性是事务处理的重要任务。然而,事务的并发执行可能会破坏事务的ACID特性,而导致数据的不一致性:
(一)Write-Write冲突,丢失更新。它是由于事务之间的写冲突造成的。两个事务T1和T2同时读入同一数据并修改,T2的提交破坏了T1的提交结果,导致T1的修改丢失。
(二)Read-Write冲突,也称不一致读。不一致读是指事务T1读取数据后,事务T2执行更新操作,使T1无法再现前一次读取结果。它包括三种情况:1.T1读取某一数据后, T2对其做了修改,当T1再次读取该数据时,得到与前一次不同的值;2.T1按一定的条件从数据库中读取了某些记录后,T2删除其中部分记录,当T1再次按相同条件读取数据时,发现某些记录神秘的消失了;3.T1按一定的条件从数据库中读取了某些记录后,T2插入了一些记录,当T1再次按相同条件读取数据时,发现多了一些记录。后两种情况也称幻影现象。
(三)Write-Read冲突,也称读脏数据。读脏数据指事务T1修改某数据,事务T2读取同一数据后,T1由于某种原因被撤销,这时T1已修改过的数据恢复原值,T2读到的数据就与数据中的数据不一致,则称T2读到的数据就为脏数据。
三、基于封锁的事务并发控制机制
(一)锁的类型
封锁是实现并发控制的一个非常重要的技术。所谓封锁就是事务T在对某个数据对象例如表,记录等操作之前,先向系统发出请求,对其加锁。加锁后事务T就对该数据对象有了一定的控制,在事务T释放它之前,其他事务不能更新该数据对象。下面介绍DBMS涉及的锁:
1.互斥锁(Exclusive Lock):用于写操作,又称写锁或者排他锁,记做X锁。若事务T对数据对象A加上X锁,则只允许T读写A,其他事务都不能对A加任何锁,直到T释放A上的锁。
2.共享锁(Shared Lock):用于读操作,又称读锁,记做S锁。若事务T对数据对象A加上S锁,则T可读A但不能写A,其他事务只能对A加S锁,而不能加X锁,直到T释放锁。
3.更新锁(Update Lock):用于更新操作。等价于先加共享锁,在真正执行更新操作时,将共享锁升级为互斥锁。大部分DMBS 都不使用这种锁。
4.增量锁(Increment Lock):用于增量操作,如果一个对象被上了增量锁,除增量操作以外任何读写操作都是被禁止的。即增量锁之间不排斥。因同时对某一对象的数值进行加一或者减一操作时,其结果与操作先后顺序是无关的,可以交换。这种锁使用并不广泛。
5.意向锁(Intention Lock):它是因为引入多粒度对象而产生的,又可细分为:意向共享锁,意向排他锁和共享意向排他锁。
在DBMS 中被广泛使用的是共享锁,互斥锁和意向锁。为了保证写操作的互斥性,不同事务对同一数据对象加锁时需要进行冲突检测。检测可以借助锁的相容矩阵来判断,如图1(a)所示。从中可以发现5种锁的强度偏序关系,如图1(b)所示。
(二)加锁管理和锁转换
DBMS中处理事务加锁事宜的部分被称为锁管理器。锁管理器维护着一个锁表,这是一个以数据对象标志为码的哈希表。DBMS也在事务表中维护着每个事务的描述信息项,该记录中包含一个指向事务拥有的锁列表的指针。在请求锁之前要检查这个列表,以确定不会对同一个锁请求两次。
加锁表中的每一项针对某个数据对象(可以是一页,一条记录等等),它包括下面的信息:拥有数据对象锁的事务数目,锁的属性(共享锁、互斥锁等)和一个指向加锁请求队列的指针。
1.加锁和解锁请求的实现。当事务需要某个对象的锁时,需要将请求提交给锁管理器。如果请求的是共享锁,当前请求队列为空,而且该对象没有处于互斥锁状态时,锁管理器就将同一加锁请求,并更新该对象的相应的锁表数据项。如果请求的是互斥锁,并且没有事务拥有该对象的锁,那么锁管理器可以同意加锁请求,并更新该对象的相应锁表数据项。对于其它情况,加锁请求不能立刻得到满足,加锁请求将被添加到该对象的加锁请求队列中,同时挂起请求加锁的事务。当事务中止或者提交时,会释放自己拥有的锁。当某个对象被释放时,锁管理器更新相应锁表数据项,并检查该对象的加锁请求队列。如果请求能被接受,请求锁的事务将被唤醒并得到锁。其中,加锁和解锁操作必须是原子操作。为确保这两个操作的原子性,锁管理器需要使用操作系统的同步机制来小心的访问锁表。
2.锁转换。事务可能需要对已经获得了共享锁的对象再请求排他锁。此时,如果没有其他事务拥有该对象的共享锁,可以立即对事务的锁进行升级满足互斥锁请求,否则将该加锁请求加到等待队列的最前面。但是,使用锁的升级不能避免由冲突更新操作导致的死锁。例如,如果两个事务已经获得了一个对象的共享锁,又请求排他锁,就会导致死锁。一个更好的法子是不进行锁升级,而是在开始时首先获得排他锁,当知道只需要共享锁就足够了时,再对锁降级。但该方法又将会导致在某型情况下事务并需要排他锁时,降低了系统的并发度。但是从整体来讲,它通过减少死锁改善了吞吐量。因此该方法在目前的商用DBMS中被广泛使用。并发度的问题可以通过引入前面提到的更新锁来改善。在事务开始时申请更新锁而不是排他锁,就可以防止与读操作的冲突。一旦确定不要对对象进行更新,就可以将锁降级为共享锁。如果需要更新对象,则可以将锁升级为排他锁。
3.并发调度的可串行性和两段锁协议。计算机系统对并发事务中并发操作的调度是随机的,而不同的调度可能会产生不同的结果。其正确性的评判标准是:并发调度的可串行性。即多个事务的并发执行是正确的,当且仅当其结果与按某一次序串行的执行它们时的结果相同。
两段锁(Two Phase Locking,简称2PL)协议就是保证并发调度可串行性的封锁协议。所谓“两段”的含义是,事务分为两个阶段,第一阶段是获得封锁,也成为扩张阶段。在该阶段,事务可以申请获得任何数据项上的任何类型的锁,但不能释放任何锁。第二阶段是释放锁,也成为收缩阶段。在该阶段,事务可以释放其拥有的数据项上的任何类型的锁,但是不能再申请任何锁。但是由于一个事务是由若干操作组成的,因此在实际执行过程中,很难判断一个事务还会不会再提出锁请求。一种比较实用的方案就是:事务将一直保持它在执行过程中获得的所有的锁,直到该事务被提交或者撤销时才释放它们。
两阶段锁协议的工作流程可概括为:开始事务;在读数据前获得共享锁,在写操作前获得互斥锁,并在获取锁时进行锁的冲突检测;进行读/写操作;释放事务拥有的共享锁;结束事务(提交或者撤销);释放所有的本事务所持有的互斥锁。
4、封锁的粒度。封锁对象的大小称为粒度。目前,在商用DBMS中,最小锁定对象是记录,最大对象是表。锁定的对象可以是一张数据表,一个页面或一条记录,甚至是一条记录中的某个字段。封锁粒度与系统的并发度和并发控制的开销密切相关。封锁的粒度越大,数据所能够封锁的数据单元就越少,并发度就越小,系统开销也越小;反之,封锁的粒度越小,并发度越高,系统开销也越大。因此,如果在一个系统中同时支持多种封锁力度是比较理想的,这种封锁方法称为多粒度锁。
多粒度锁虽然灵活,但也带来了一个新的问题:具有隶属关系的锁定对象如何检测到对方的存在。比如对于一个被上了表级写锁的数据表,尽管该表中的记录并没有被显示加锁,但应禁止对其包含的记录进行读写。反之,对已经加了记录级写锁的记录,也不能对它所属的表再加读锁。为此人们引入了意向锁来解决这个问题。
意向锁的含义是如果对一个对象上意向锁,则说明它的某个下一级对象要被加锁。显然,要对小粒度对象上锁,必须先对其所属的上级对象加意向锁;要释放小粒度对象的锁,必须先释放本身,然后释放其上层对象的意向锁。意向锁有三类:IS,IX 和SIX。如果对一个数据对象加IS锁,表示它的下一级对象拟加S锁,比如想对某记录上读锁,那么就需先对其所属的表加IS锁,然后再对指定记录加读锁;如果对一个数据对象加IX锁,表示它的下一级对象拟加X锁;如果要对一个数据对象加SIX锁,表示对它加S锁,再加IX锁。如对某个表加SIX锁,则表示该事务要读整个表(所以要对该表加S锁),同时会更新个别元组(所以要对该表加IX锁)。具有意向锁的多粒度封锁方法提高了系统的并发度,减少了加锁和解锁的开销,它已经在实际的DBMS产品中得到了广泛的应用。
5.死锁处理。当有两个或者多个事务都已封锁了一些数据对象,然后又都请求对已为其它事务封锁的数据对象封锁,从而出现死等待,即陷入死锁。死锁可能发生在普通的上锁操作时,也可能发生在断言锁和锁升级时。因此对锁协议,必须进行死锁处理,方法有预防法和检测法两大类。具体地讲有五类:
1.一次封锁法。其要求每个事务必须一次将所有要使用的数据全部加锁,否则就不能继续执行,必须挂起等待。一次封锁法虽然可以有效地防止死锁,但也存在问题。首先,一次就将以后要用到的全部数据加锁,势必扩大了封锁的范围,从而降低了系统的并发度。第二,数据库中数据是不断变化的,原来不要求封锁的数据,在执行过程中可能会成为封锁对象,所以很难事先精确的确定每个事务所要封锁的数据对象,为此只能扩大封锁范围,这又将进一步降低了并发度。
2.顺序封锁法。其预先对数据对象规定一个封锁顺序,所有事务都按这个顺序实行封锁。但由于数据系统的封锁对象极多,并且是不断变化的,要维护这样的资源的封锁顺序非常困难,代价太高。并且事务封锁请求可以随着事务的执行而动态的决定,很难事先确定每一个事务要封锁哪些对象,因此很难按规定的顺序去封锁。
3.时标法。系统在启动事务的时候,为事务分配一个时标,时标表示了事务启动的时间,同时也表明了事务的优先级。通常,时标小的表示先启动,具有高优先级。当一个事务T1必须等待另一个事务T2所持有的锁的时候,系统认为存在发展成死锁的可能性。处理方法有两种:①等待―死亡,如果T1的优先级比T2的高,那么T1等待,T2不被处理;如果T1的优先级比T2低,T1被立即撤销;②伤害―等待,如果T1比T2优先级高,那么T2立即撤销;否则T1等待。这两种方法中,为了使被撤销的事务的优先级不断被提高,被撤销的事务在重新启动的时候维持原始的时标不变。显然,“等待―死亡”最终都能够保证每一事务都必然能被完成,而“伤害―等待”中回滚的事务会比较少(因为一般老的事务抢夺新事务的锁的情况较少)。两种方法都属于保守算法,会产生误判,撤销一些其实并没有发生死锁的事务。以上三种方法都是属于死锁的预防。
4.超时法。如果一个事务的等待时间超过了规定的时间,就认为发生了死锁。超时法实现简单,但不足明显。一是有可能误判,系统因为其它的原因使等待时间超过了时限,系统会误认为发生了死锁。二是时限若设置太长,死锁不能及时发现。
5.等待图法。事务等待图是一个有向图G = ( T,U)。T为节点的集合,每个节点表示正运行的事务;U为边的集合,每条边表示事务等待的情况。若T1等待T2,则T1和T2之间划一条有向边,从T1指向T2。事务等待图动态的反映了所有事务的等待情况。并发控制系统周期性的监测事务等待图,如果发现图中存在回路,则表示系统中出现了死锁。该两种方法属于死锁的检测。DBMS的并发控制系统一旦监测到了死锁,就要设法解除。通常采用的方法是选择一个处理死锁代价最小的事务,将其撤销,释放该事务持有的所有锁,使其它事务得以继续运行。
四、结束语
事务的并发控制的算法很多,这里仅仅介绍了基于锁的控制方法。因为它实现简单,协议可靠,被广泛使用到网络数据库管理系统中。锁算法的一个缺点就是加锁时可能出现死锁,因此需要进行死锁处理。此外,幻影问题需要借助索引锁或者断言锁来解决。事务并发控制的方法还有乐观算法,时标(Time Stamp)协议,多版本(Multi Version)协议等。
乐观算法认为冲突的事务是少数,将事务执行分三个步骤:读数据,验证冲突和提交。它最大特点是每个事务拥有自己的私有数据空间,没有被提交的事务不直接写数据库,只有经过验证,不与其它事务冲突后才提交结果,使数据生效。验证通常是通过比较事务时标进行的;在时标协议中,每个事务被分配一个时标,每个数据对象也被分配一个读写时标,数据对象的时标在它被读写后更改。通过检查事务和数据对象时标来判断是否发生事务冲突;多版本协议主要是为了保证读数据的事务不被阻塞,每个事务在读操作时,都在自己的私有空间内建立一个数据对象的最新副本,以后每个事务只修改自己副本。提交前需要通过事务的时标进行冲突检测,不冲突的事务才能被提交。
参考文献:
[1]Yannakakis M., Papadimitiou C. H., Kung H. T. Locking Protocols: Safety and Freedom from Deadlock [C] Yannakakis M. // Proceedings of the IEEE Symposium on the Foundations of Computer Science, IEEE Computer Society, 1979,105-114
[2]Kedem Z. M., Siberschatz A. Locking Protocols: From Exclusive to Shared Locks [J].Journal of the ACM, 1983, 30: 79-98
[3]Korth H. F. Locking Primitives in a Database System [J]. Journal of the ACM,1983,30:99-114
[4]Buckley G.,Silberschatz A. Concurrency Control in Graph Protocols by Using Edge Locks [C].Buckley G. // Proceedings of the 3rd ACM SIGMACT- SIGMOD Symposium on the Principles of Database Systems,1984,18-29
[5]Raghu R.,Johannes G. Database Management Systems (2nd Edition) [M]. 北京: 清华大学出版社,2000,79-189
[6]Weikum G.,Vossen G. Transactional Information Systems: Theory Algorithms and the Practice of Concurrency Control and Recovery [M]. Morgan Kaufmann,2001
[7]Raghu Ramakrishnam,Johannes Gehrke著,周立柱,张志强等译.数据库管理系统原理与设计.北京:清华大学出版社,2004:389～425
[8]萨师煊,王珊.数据库系统概论[M].北京:高等教务出版社,2000: 264-279
[9]刘云生.现代数据库技术[M].北京:国防工业出版社,2001:166-175
[10]陈凌,余建桥,张尉.一种基于2PL新的封锁协议的研究[J].西南农业大学学报(自然科学版).2006,2:97-99
作者简介:
卢成浪(1982-),男,浙江省苍南县,硕士,助理实验师,研究方向:并行程序设计和数据库。
徐湖鹏(1982-),男,浙江省永嘉县,硕士,助理实验师,研究方向:软件工程。