一种多粒度锁锁的并发控制算法

一种多粒度锁锁的并发控制算法

实时事务处理算法主要包括两个方面。其中之一是事件发生计划算法，主要是事件分类的确定。另一方面，实时事务的同时控制算法包括悲观事务的同时控制算法和悲观事务的同时控制算法。在对算法性能测试时,根据给出的实时内存数据库的引擎结构,开发出一个实时内存数据库,以测试类对内存数据库三个方面的性能进行了测试。测试分为两次,分别为事务并发控制算法优化前和事务并发控制算法优化后。1宏观并行控制算法内存数据库的一个重要设计问题是并发控制,它由于既要满足事务的时间限制还要维护数据库的一致性而变得复杂定义1:一个调度S定义在一个事务集合T={T定义2:一个调度S中,各个事务的操作执行时不叠加(即一个接着一个发生),则这个调度是串行的。定义3:一个调度S是可串行的,当且仅当S冲突等价于一个串行调度。这种可串行化通常称为冲突等价可串行化。一个并发控制器(或称调度器)的基本功能是产生一个要执行事务的可串行化调度。多数内存数据库系统的并发控制协议均基于串行化理论“读-写”冲突:对同一个数据对象,一个事务正在执行“读”操作,同时另一个事务执行“写”操作而发生冲突;“写-写”冲突:对同一个数据对象,一个事务正在执行“写”操作,同时另一个事务也执行“写”操作而发生冲突。内存数据库中的并发控制协议解决冲突的办法主要有两种策略:(1)等待:终止其中一个事务引起冲突的操作,使其停留在等待状态,直到另一个事务的操作完成为止。在内存数据库事务并发控制的研究中,等待策略有以下三种派生方法:(1)不等待(nowait):等待的事务立即夭折,而不是等到另一个事务操作完为止。(2)损伤等待(woundwait):根据每个事务的达到时间,如果要求得到数据者到达得比较早,则夭折正在使用数据的事务;否则夭折要求得到数据的事务。(3)等待死亡(waitdie):根据每个事务的到达时间,如果要求得到数据者到达得比较早,则该事务可以继续等待,否则夭折这个事务。(2)回滚:撤消事务引起冲突的操作,事务重启,回到开始时的状态根据解决“读写”操作冲突的不同策略,并发控制算法分为悲观并发控制协议PCC(PessimisticConcurrencyControl)和乐观并发控制协议OCC(OptimisticConcurrencyControl)两大类悲观并发控制算法中最广泛使用的是基于锁(Lock)协议的算法,它为数据访问提供数据锁,分为读锁和写锁,读锁又称共享锁(SharedLock),被加读锁的数据对象只能读不能写;写锁又称排它锁(Exclusivelock),被加锁的数据对象只能被加锁事务读写,其他事务不能访问两阶段锁2PL(twophaselock)是悲观并发控制协议算法的重要内容,为解决优先级倒置,派生出了高优先级法2PL-HP(也叫优先级夭折)、优先级继承、有条件优先级继承、数据优先级法PCP及其他衍生协议。乐观并发控制协议认为任何两个并发事务请求同一个数据对象的概率很低,事务对数据库的所有操作在请求时即可进行。乐观并发控制协议的事务处理过程分为:读、验证、提交,验证分为前向验证和后向验证,若在验证阶段发现冲突,则进行事务回滚。如果事务频繁的重启对于内存数据库系统来说会是一个负担并且不利于事务在截止期前完成,因此乐观并发控制协议算法大多是围绕如何减少事务重启而进行改进,派生出了广播算法OCC-BC、WAIT-50、OCC-TI、OCC-DA、多版本协议MCC等。悲观并发控制协议算法具有节约系统资源的特点,在处理时间限制比较严格的硬实时事务时表现优于乐观并发控制协议,而乐观并发控制协议有利于提高系统的并发度2并行化而可串行化数据锁分为读锁(也称共享锁)和写锁(也称独占锁):(1)共享锁Sharedlock:只允许读,简称“S锁”;(2)独占锁Exclusivelock:允许读和修改锁住的数据对象,简称“X锁”。一般使用锁的方式是用完即释放,如以下代码所示:这种使用锁的方式可能会导致不可串行化,而可串行化(serializability)是并发控制最普遍的正确性准则,各个事务对数据对象的操作不交叉存取(即每个事务对数据对象的操作是连续的)两阶段锁算法的规则是:(1)如果事务T想读(修改)一个对象,它首先要获得一个共享(独占)锁;(2)对事务已经持有的封锁,不得重复申请;(3)一个事务必须注意到其他事务所做的封锁;(4)每个事务分做两段:生长期和枯萎期。生长期申请封锁,枯萎期解除封锁,在枯萎期不得申请新封锁;(5)调度器在数据管理器完成对数据对象椭操作后才能释放锁;(6)事务结束时,解除所有封锁。两阶段锁算法规则保证了事务执行的可串行化,锁管理器LM(LockManager)在存取结束时即刻释放锁,提高了事务的并发度。但它存在的问题是可能导致级联退出,所以需要使用严格2PL(stricttwo-phaselocking,简称S2PL),S2PL在数据存取完成的最后阶段释放所有锁。3多粒度锁封装内存数据库中,两阶段锁封锁对象的大小称为封锁的粒度,一般情况下,加锁的粒度越大,加锁的次数就越少,系统资源的开销小,事务之间冲突发生的概率就越高,系统的并发度越低;多粒度锁封锁就是在一个系统中同时支持多种封锁粒度供不同的事务进行选择。采取多粒度锁封锁策略,可以降低冲突发生的概率和事务的夭折数,减少事务重启,有利于满足事务截止期的要求,提高事务的并发度。3.1节点的恶意向锁参考关系数据库的概念,内存数据库中锁的粒度可定义为:数据库DataBase(如果多于一个库,数据库也可以作为粒度的元素)、表Table、页Page、记录Record、元组Tuple。从前到后是一种顺序包含的关系,展开以后其层次结构形成了一棵树。多粒度锁封锁允许对树上的每一个数据项进行封锁。由于节点的这种包含关系,除S锁和X锁外,多粒度锁锁时需要引入以下的意向锁:(1)IS(IntentShareLock):意向共享锁。如果对一个数据对象加IS锁,表示它的子结点拟加S锁。(2)IX(IntentExclusiveLock):意向排它锁。如果对一个数据对象加IX锁,表示它的子结点拟加X锁。(3)SIX(ShareIntentExclusiveLock):共享意向排它锁。如果对一个数据对象加SIX锁,表示对它加S锁,再加IX锁,即SIX=S+IX。例如,对某个表加SIX锁,则表示该事务要读整个表(对该表加S锁),同时会更新个别元组(对该表加IX锁)。多粒度锁锁协议准则:(1)从层次结构的根节点开始封锁;(2)子节点要获得S或IS锁,它的父节点必须持有IS或IX锁;(3)子节点要获得X或IX或SIX锁,它的父节点必须持有IX或SIX锁;(4)必须从由底向上的顺序释放锁。3.2基于锁的运动体系的研究本文提出的多粒度锁的并发控制协议中,采用S2PL-HP算法解决冲突。如果低优先级事务试图申请高优先级事务持有的锁,则阻塞优先级低的事务;如果优先级高的事务到达时申请低优先级事务持有的锁,则将低优先级事务回滚。两阶段锁算法需要构造锁管理器LM,锁管理器管理的锁存放在散列表(HashTable)一类的数据结构中,数据结构中的元素可定义如下:定义4:RTDB={DT定义5:数据的全局标识为GID=f(DB,DTLM:LockManager,即锁表管理器;DM:DataManager,即数据管理器。当事务T(1)进行事务预分析,根据一定的算法规则计算T(2)查看锁表管理器,找到事务T(1)T(2)如果T(3)如果锁粒度是元组,即最小加锁粒度,则跳到第(5)步,否则调整T(3)处理事务,调用数据管理器进行数据读写操作;(4)数据管理器处理完毕,锁表管理器更新对应锁表中的信息,跳到第(6)步;(5)如果有冲突发生,调用S2PL—HP算法规则解决冲突;(6)结束。4算法测试4.1数据库的存储内存数据库Engine是内存数据库的核心,它对实时/历史数据进行管理,它的本质是一个实时事务处理器。关系型数据库采用二维关系表来进行数据的存储,基于磁盘的存储结构,数据存取过程中要进行频繁的磁盘I/O操作。由于磁盘I/O操作时间不确定性,要引入内存数据库中是不现实的。内存数据库将实时数据常驻内存,访问实时数据时无需进行I/O操作,保证了运行速度,有利于满足实时事务截止期的要求。4.2多粒度锁的并发控制测试测试系统环境为:Win7+JDK+NetBeans6.7。事务并发控制算法优化前测试结果如图2所示。