面向支持向量机的事务调度

面向支持向量机的事务调度

近年来，尽管有许多基于新用户需求的非相关数据库出现，但传统的数据库应用场景（如银行交易、订单交易等）中的关系数据库仍然发挥着非常重要的作用。在网络数据结构中，问题是确保acid属性的重要特征，并以列表形式的形式同时执行和恢复是数据库实现中问题的主要特征。自20世纪70年代以来，已经发表了几篇关于关系数据库全球控制的经典文章，并提交了许多合并协议。其中一些是将商业信息系统最新使用的。在这些协议中，最受欢迎和最受尊敬的是关闭协议。封锁协议并没有规定加锁的具体形式,具体来说封锁协议的实现包括了如何加锁和如何选择加锁的对象.一个直观的想法是物理锁,也就是针对数据库的行、页面、表等物理数据对象进行封锁.物理锁通过表粒度锁来防止幻象,但是表粒度锁只允许一张表上同时拥有一个更新事务,这大大影响了系统的并发度.逻辑谓词锁的概念在20世纪80年代初期由Eswaran和Gray等人提出.逻辑锁在一个逻辑的数据集合上加锁来保证共享数据的串行化访问,逻辑谓词锁很好地解决了幻象读的问题.逻辑锁的方案所带来的优势非常明显.由于逻辑锁只需要比较两个事务之间的谓词而不需要像物理锁那样比较每个访问的元组(往往是数据行项),它能大大降低锁竞争的检测频率.在处理多用户事务的情况时逻辑锁也有物理锁不可比拟的优势.然而在通用数据库的设计中,特别是在复杂查询的应用中,逻辑锁的冲突判断检测代价是非常大的.如果不对输入的谓词加以限定,判断是否冲突的问题将是不可解的,判断谓词冲突的代价也非常高.而Lee和Yeh也指出,逻辑锁会锁住过多的区域,从而导致并发度降低.他们随之提出了一种以冲突判断代价换取并发度的方法,以谋求谓词锁在理论上的最大并发度,防止了数据不必要的封锁.在CarloMeghini和CostantinoThanos的逻辑封锁方案中依然没有解决在多属性N-Attribute上的事务并发问题.近年来,对事务并发问题的研究仍然在继续,如Song等人提出了利用多级网格保护多维索引的幻象读的方法.Lu等人提出了为事务的执行决定一个合适的可低于“可串行化”的隔离级别以提高处理性能的方法.Jorwekar等人则对最近几年里提出的SSI(SerializableSnapshotIsolation)技术进行了研究,并且Ports等人在PostgreSQL上成功实现了用SSI代替传统的基于两阶段封锁协议的可串行化事务隔离级别,获得了并发性能的提升.包括还有一些文献对逻辑谓词锁进行了扩展研究或提出新类型的锁来提高事务的并发:如Klug针对查询语句中的Join提出了能够尽量减少加锁元组数的方法来代替会锁住整个关系的逻辑谓词锁.Brayner扩展了两阶段封锁协议,提出了合作锁的概念来降低锁的等级以获得更高的并行性.Martinenghi等人提出了在数据库事务管理中通过简化完整性约束检查以提高并发性能的方法,并在其中也用到了谓词锁.而本文作者也是对逻辑谓词锁进行扩展研究,提出在特定应用场景下提高并发性能的解决方案.OLTP系统中的事务一般都是由一些简单的、预定义的查询构成,所以数据访问的复杂度通常是可控的.在这种情况下,逻辑锁不仅能避免通用查询实现代价高昂的缺点,还能通过较小的加锁解锁代价保证事务的串行化调度.在此背景下,本文在前人提出的逻辑锁概念基础上,进一步细分锁粒度,以求读写并发的最大化.本文还讨论了属性级别谓词锁的封锁方式,并提出全新的锁模式以及冲突判断方法.此外,我们在国产神通数据库的线程事务框架下实现了TPC-C事务并发场景的模拟,并与传统的物理行锁模块进行了锁模块性能对比实验.1基本语言概念1.1复合比较称谓词的生成谓词是指条件表达式的求值返回真或假的过程.判断两个复杂谓词是否冲突是一个非常困难的操作,从数学逻辑理论上来说,这是一个NP完全问题.但是如果控制谓词的复杂度以及最大深度,判断逻辑冲突是可以在多项式时间内解决.比较谓词为条件表达式中仅含有比较操作的谓词,也是在数据库应用中出现最频繁的谓词操作.本文所有的理论和实现仅考虑和基于以下6种常见的比较谓词:=(等于)、≠(不等于)、≥(大于等于)、≤(小于等于)、>(大于)和<(小于).比较谓词根据比较操作的个数可分为单一比较谓词和复合比较谓词,它们按照下述定义进行区分:定义1.只含有一个比较操作的谓词称为单一比较谓词,而单一比较谓词通过与/或条件联接而成的谓词称为复合比较谓词.谓词实质上是描述和限定了数据的取值条件,因此可将谓词Predicate看作一个函数,而数据S是函数的参数,函数的值域为{True,False}.下面给出谓词和数据之间满足的定义:定义2.一组数据满足一个给定的谓词,当这个谓词中出现的每个域的名称替换成这组数据中的值时,谓词表达式的结果依然是真.基于定义2,有以下定理.定理1.复合比较谓词都可以在多项式时间里判断满足性.谓词是多种多样的,而有一类谓词无论被代入什么样的数据,它们的值总都是假.这样的谓词值域是{False},即谓词是无法满足的.可以给出如下的谓词可满足性定义:定义3.一个谓词是可满足的,当存在一组值能满足这个谓词.谓词之间存在着各种各样的关系,可以用谓词限定的数据来描述这样的关系.定义4.对于两个谓词P和Q,当存在一组值满足P时也满足Q,那么认为谓词P和Q是逻辑冲突的.而当满足谓词P的任意一组值一定也满足谓词Q时,那么谓词P和Q是等价的.定理2.两个长度有限的复合谓词可以在多项式时间内判断是否冲突.2属性：语言链理论2.1种是连续的数据集合属性谓词锁与现今流行的物理锁以及前人早期提出的谓词锁概念之间的最大区别是封锁粒度从行级别降低到属性的级别.封锁粒度降低带来的好处是明显的:不同事务在同一行不同属性的读写可以并发执行.本节将详细介绍属性谓词锁的概念和冲突定义.属性谓词锁的拥有者是事务,一个事务由一个或者多个执行动作组成,执行动作是数据库事务中的原子执行单元:(A1,A2,A3,…,An)∈T,其中,Ai为一个执行动作,而T为某个事务.一个事务中的所有执行动作必定是按序进行.每一个执行动作可能会访问数据库中的若干资源,定义数据库中的数据元为r,事务访问的数据资源集合为D,每个执行动作访问的数据库资源为di,那么有:d1,d2,d3,…,dn=D(ri∈di)以及:Ai=(OP,di),其中,OP为对数据的访问方式,执行动作Ai表示关系中符合条件的数据集di被一个OP操作访问.在实际数据库应用中,谓词可以理解成是对即将访问的数据di的一种条件约束,定义谓词:Predicate=(Relation,Condition)表示在关系Relation中所有符合条件Condition的数据.它可能是关系中现有的数据,也可能是一个尚未存在的幻象数据;可以是离散的数据,也可以是连续的数据,所以它是一个无限的数据集合.根据强二阶段封锁协议,事务在提交前都处于加锁阶段,并且事务的每个执行动作根据不同的操作类型,需要对访问的资源加上相应的锁来保护数据的一致性.所以,我们定义属性谓词锁:APLock=(Relation,Attribute,LockMode,Predicate),其中,Relation为属性关系,Attribute为加锁的属性,LockMode为加锁模式,Predicate为加锁谓词.由于粒度的细化,属性级粒度的谓词锁的锁模式不再区分为简单的读写两种模式.分析标准SQL,DML语句中的选择、更新、插入、删除以及部分DDL操作的内容我们称之为操作部分;而where等条件约束称之为条件部分.前人的逻辑谓词锁的概念都是以条件部分的约束作为谓词锁的谓词部分.然而当粒度细化后,操作类型也需要进行相应的细化.首先考虑单一的谓词.条件部分的谓词约束称之为比较谓词,已在1.1节中分类介绍.然而对于更新、插入、删除等操作,定义一种新概念的谓词——赋值谓词.比较谓词和赋值谓词的分类定义如表1所示,分别是简单比较、属性比较、简单赋值和属性赋值.由于操作部分和条件部分语义的性质不同,谓词属性锁模式也可以分为两类,分别是条件锁模式锁(C)和操作锁模式锁.而操作锁又分为读操作锁(S)和写操作(X)锁.读操作锁/写操作锁都依赖于某个条件锁.读操作锁的谓词部分比较特殊,它是一个空集,或者说读操作锁不需要谓词约束,因为读操作时无法事先知道读取的内容,并且其他锁模式也不关心加读操作锁的执行动作读到的是哪些数据.因此,读谓词锁可以表示为(Relation,Attribute,S,Φ),而写谓词锁可以表示为(Relation,Attribute,X,P),谓词P表示属性域的值发生变动之前的值域和修改后的值域.条件锁可以表示为(Relation,Attribute,C,P),谓词P表示约束条件.3种锁模式之间的冲突关系相比简单的读写模式是复杂的,条件锁模式和读操作锁都不会对数据元属性域的值进行修改,因此,这两种锁模式互相之间并发不会产生冲突.而写操作锁和条件锁会产生明显的读写冲突,无论是前值或者是后值的修改,都会影响前后读取的数据的一致性,从而导致不可重复读和产生幻象数据.而读操作锁和写操作锁、写操作锁和写操作锁之间潜在的“读-写”冲突或者是“写-写”冲突需要通过相依赖的条件锁进行判断.当写和读发生在同一个数据元的同一个属性域上时,写操作锁和读操作锁并发可能会引发脏读.而由于类似的原因,写操作锁和写操作锁并发可能会引发丢失更新.为了杜绝这样的情况发生,当在同一个属性上有读写并发或者写写并发时,需要通过判断两个执行动作的条件约束来确保不会在同一个数据元组的同一个属性域上进行数据的读取和修改,也就是说这需要操作锁依赖条件锁来保证不会发生脏读或者更新丢失的情况.条件锁能判断两个操作所访问的资源是否会产生不可并发的冲突.这里引入了属性锁之间的关系.每一个执行动作中的属性谓词锁是一个整体,互相之间都不是相互独立的,每一个操作锁都有对应依赖的条件锁,可以表示为Action=∪(ManLock(i)→ConLock(i)),ConLock(i)=Rel(ManLock(i)),其中,ManLock代表执行动作中的所有操作锁的一个集合,ConLock代表执行动作中的条件锁集合.Rel()表示依赖关系.定义5.以下两种情况可以认为属性逻辑区间APLock1=(Relation,Attribute,LockMode,Predicate)和APLock2=(Relation′,Attribute′,LockMode′,Predicate′)是冲突的,当且仅当:1)Relation=Relation′,Attribute=Attribute′且LockMode和LockMode′中一个是写操作锁,一个是条件锁,并且谓词Predicate和Predicate′有逻辑冲突.2)Relation=Relation′,Attribute=Attribute′,LockMode和LockMode′都是操作锁模式,且其中任意一个或者两者都为写操作锁,并且它们所依赖的条件锁Rel(APLock1)和Rel(APLock2)的谓词Predicate和Predicate′有逻辑冲突.3种锁模式的相容关系如表2所示,其中√表示相容,×表示不相容,&表示需要通过关联条件谓词判断相容与否.2.2有写操作称谓词锁和复合称谓词时的时常见的布尔条件主要包括AND和OR.在加入AND和OR后,条件锁变成一个复合条件谓词锁.以下给出复合条件锁的定义:定义6.复合条件锁是由简单谓词锁通过and(与关系),or(或关系)组合而成的复合谓词锁.定义包含有N个谓词布尔操作的复合条件锁称为N元复合条件锁.在OLTP场景下,考虑两种复合谓词锁.一种是或关系复合谓词锁,只有由布尔条件OR构建,一种是与关系复合谓词锁,只由布尔条件AND构建.理论上或谓词非常严格,每一个子谓词的逻辑区间都需要封上条件锁.而相比之下与复合谓词情况比较特殊,因为每个子谓词都是整个条件谓词的一部分.当有写操作谓词锁和复合谓词中的一个子谓词产生逻辑区间冲突时有以下两种情况:1)当该复合谓词是或复合谓词时,则认为两者冲突;2)当该复合谓词是与复合谓词时,则需要获得完整的数据以充分判断.然而为了锁冲突检测的高效性,仍然将与谓词的每个子谓词封上条件锁.与单一的简单谓词判断相比,复合条件谓词锁之间的冲突判断较为复杂,特别是出现或关系复合谓词锁时,经常要判断不同属性间的谓词是否冲突,而这样的冲突检测是一个费时的操作.而在优化时,首先要对比相同属性上的两个谓词是否冲突,这能大大降低比较不同属性上的谓词的可能性,因为相同属性上的谓词判断大多数情况下能够得出两个复杂谓词是否冲突的结论.只有在不得已的情况下,才考虑不同属性列上的谓词进行交叠判断.在一般的简单查询场景中主要是与操作谓词之间的判断,而与操作谓词之间只要彼此至少各有一个子谓词不存在交集即可判定为两个与操作谓词不冲突,因此在判定时可以先得到一个属性集的交集S.针对S中任一属于不同复杂谓词的子谓词的逻辑不交叠即可得出锁不冲突的结果.含有或操作谓词的冲突判定会有较高的代价,因为需要将或操作谓词的每一个子谓词都参与判定,因此一个含有N个子谓词的或操作谓词锁和另一个含有M个子谓词的或操作谓词锁判定冲突分别需要作N×M次判定,并且会有大量的不同属性的谓词锁判定.不同属性间的谓词锁判定需要对数据进行扫描操作来保证冲突判断的准确性,这是一个开销十分高昂的操作.幸好的是在实际的OLTP应用场景中需要这样进行数据扫描判定封锁的情况极少.2.3多粒度的属性锁一个执行动作会对数据库中数据表的一整列属性进行某一类的封锁而杜绝某些锁模式的访问,比如数据库的部分DML操作和DDL操作.除此之外,考虑到当某属性列中维护的加锁逻辑区间过多时,可以考虑适当牺牲并发度来维持性能上的尽量高效,从而对整个属性列加上锁.于是,类似物理锁的处理方式,这里同样可以有多粒度的属性锁.在本节前两小节中介绍的是一个属性的逻辑区间上的封锁.在此基础之上,我们再添加一个属性列级别的粗粒度锁.如图1所示,我们把封属性谓词锁动作看作是一种对树状结构的操作.属性级锁为父节点,而属性域中的各个逻辑区间锁看成是子节点.细粒度的锁嵌套在粗粒度的锁之中.在这个层次关系下,如果要对低粒度的单位加锁,必须先在相应的粗粒度的单位上加锁.定义属性列粒度的锁为ALock=(Relation,Attribute,LockMode)属性级锁引入意向锁总共有以下5种锁模式.12阅读锁is当执行动作的读操作部分将在某些属性列上进行或者条件部分落在某些属性列上时,在这些属性列上需要加上意向读锁;2签名ix当执行动作的写操作部分将在某些属性列上进行时,在这些属性列上需要加上意向写操作锁;3ic目标条件锁ic当执行动作的条件部分落在某些属性列上时,在这些属性列上需要加上意向条件锁;4x写作锁x写锁阻止其他任何事务对该列的读或写请求;5属性列的锁a.条件锁阻止其他任何事务对该列的写请求.属性级锁的冲突关系如表3所示:X锁和C锁是相对高级别的锁.某些性能上或者是逻辑上的原因需要锁住整个属性列时会采取这样的封锁方式.当事务对某一列发起一个join操作时,需要将外表的整列进行保护,因此需要加上C条件锁,以防止其他事务对该列数据的修改.而如果事务需要对整列数据进行更新或者删除时,需要对该列加上X锁,防止其他事务在该列上的读或者写.而出于性能上的考虑,当事务在某一列上的写操作锁数量庞大时可以将该列上的IX锁升级成X锁.3属性是语言锁的实现3.1加锁解锁模块属性谓词封锁系统最主要的可以分为两大模块,分别是谓词解析模块和加锁解锁模块,如图2所示:谓词解析模块的主要功能是根据用户输入的执行动作,从语义级别转化为谓词的逻辑表达形式.该模块需要对支持操作类型的谓词的判定以及将语义谓词转换成若干逻辑区间的集合操作的表达方式.加锁解锁模块是实现对各个执行动作并发的管理.图3为加锁解锁模块的一个简要示意图,包括从事务请求锁,到获得锁或者被终止的所有可能.加锁解锁模块分为属性谓词索引子模块、事务等待管理子模块和死锁检测子模块.属性谓词索引子模块用来判断能否获得锁;事务等待管理子模块用来管理和维护事务间的等待和唤醒;死锁检测模块负责发现死锁的事务,并找到合适的事务进行终止回滚.3.2用权索索方式强化属性称谓词锁事务的每个执行动作由谓词解析器把数据库语言翻译成谓词逻辑区间.因此,在加锁解锁模块的谓词锁索引子模块中,谓词区间的操作是所有功能实现的基础.而其中两个同一属性的逻辑区间的交叠判断是谓词锁实现中最基本的操作.可以认为无论是什么类型的属性(可能是整型、布尔型、字符型、时间类型等)都可以用一个给定的规则进行排序,因此可以将每个属性都看作一个(-∞,+∞)的区间,因此谓词交叠判定可转化成逻辑区间的交叠判定.因此对属性谓词锁的管理可以转化为对各个逻辑区间的管理.如图4所示,可以利用树状结构的属性谓词索引来对这些逻辑区间进行管理.事务层每发出一个执行动作可以通过表名和属性列名定位到唯一的一棵谓词逻辑区间索引树,并通过一系列操作判断与已有的锁节点是否冲突.所以这个索引要支持对逻辑区间快速地查找、插入和删除操作.索引树中的每一个节点都代表一个属性上的逻辑区间谓词锁,因此每个节点上都有事务信息、锁模式信息以及逻辑区间信息.考虑到平均操作的时间,采用区间树的结构来对每个属性的逻辑区间进行管理是一个比较合理的方案.区间树的基础树结构是红黑树,每个节点包含一个区间域Interval.Interval的关键字为区间的低端点Interval.LowValue.这样对树进行中序遍历就可以按低端点的次序列出各区间.每个节点上包含MaxHighValue和MaxHighBoundProperty,前者是以Interval节点为根的子树中所有区间的端点最大值,而后者是这个最大值端点的开闭类型.除此之外,每个节点上还记录了事务信息和基本的锁模式信息,每个节点代表着一个属性谓词锁,如果这个节点代表的是条件锁,那么需要包含这个条件锁相关联的操作锁信息(锁模式S或者是X以及对应的属性列号).针对加锁解锁等功能,该索引需要支持以下3种操作.1t，x伊利昂参数将包含区间域的节点x插入到索引T中,用于加锁;2目录删除t，x从索引T中删除节点x,用于解锁;3冲突节点的控制返回一个节点x,x为所有索引T中与i区间重叠并且锁模式冲突的节点,用于锁冲突检测.由于属性谓词索引是红黑树的模型,因此,即使是在最坏情况下,对含有N个节点区间树的插入和删除操作都能控制在O(logN)的时间复杂度之内.3.3加锁的下一步运作当一个事务的一个执行动作发起时,谓词解析器已经解析成加锁解锁模块需要的谓词区间.针对不同的加锁粒度而言,事务必须按照从大到小的原则,即首先要申请属性级锁然后是逻辑区间锁.对于不同的加锁类型来说,先加条件锁再加操作锁.如果加锁失败,比如发现锁冲突,那么需要把本事务的事务号放入冲突事务的等待队列.而如果申请加锁成功,那么可以把自己的锁信息加入到锁表中去.具体的加锁流程如图5所示:对于关联条件,考虑到在同一属性上可能既有写操作锁又有读操作锁,那么每次有新的加锁请求时,首先要依次和潜在冲突的事务的条件锁两两判断冲突关系.而由于关联的条件锁可能是位于同一属性列上或者是不同属性列上,或者分别是条件锁的逻辑与或组合,那么这些冲突关系的判断都是需要支持准确冲突判断的.4实验驱动和环境本实验基于神通数据库的事务线程框架和存储引擎,实现的属性谓词锁模块和神通数据库5.5版本的锁表模块进行对比测试.测试驱动包括TPC-C生产者消费者控制器、线程池和数据发生器.实验的并发环境基于TPC-C标准的数据集和事务,利用TPC-C模拟了一个完善的具有代表意义的OLTP应用环境.4.1tpc-c等3种类型的锁表对数据库中所有表的所有属性列都建立属性谓词索引是一个不明智的选择.针对类似于TPC-C这样的简单查询场景,所有事务的查询条件往往都集中于主键以及少量其他属性上.属性谓词索引结构是为了防止事务之间条件锁和写锁的冲突,所以对于那些在应用中不会在条件查询中出现的属性,我们可以选择不建立谓词索引,只通过属性级锁模式的判断来确定是否会存在对同一行同一属性值的读写冲突或者是写写冲突就能保证所有事务的串行化调度.根据TPC-C的5种事务状况,相应地我们可以为锁表进行定制,情况如下.1热盒子表在属性w_id上建立逻辑谓词索引;2地下通道表在属性d_id,d_w_id上建立逻辑谓词索引;3currentuu出口商在属性c_w_id,c_d_id,c_last和c_id上建立逻辑谓词索引;4表不需要建立逻辑谓词索引;5新建证书在属性no_d_id,no_w_id上建立逻辑谓词索引;6表1布局表在属性o_id,o_d_id,o_w_id,o_c_id上建立逻辑谓词索引;71命令表在属性ol_o_id,ol_d_id,ol_w_id上建立逻辑谓词索引;8表在属性i_id上建立逻辑谓词索引;9表stick表在属性s_i_id,s_w_id,s_quantity上建立逻辑谓词索引.4.2属性称谓词锁的加锁测试5个事务单独运行的加锁次数对比,实验中在设置TPCC的运行参数时,设置其他的事务为sleep状态,并不修改每个事务的执行比率.测试的是在不同性质的事务下平均每个事务加锁数目.由图6所示,除了New-Order事务之外,在其余的4个事务中,采用属性谓词封锁的加锁数目远小于利用物理行锁进行封锁的加锁数目,New-Order事务中属性谓词封锁的加锁次数是物理封锁的两倍左右,New-Order事务所有的查询和更新语句的条件部分都是针对全部主键的等值比较,因此基本上只访问和修改表中的少数几条数据,由于全是单行记录的访问,所以属性谓词锁在这样的事务中并不占优势.为了提高读写的并发,属性谓词锁需要对每个访问的数据属性列都加锁,而物理锁机制只要在对应的行和索引项中加锁,因此在New-Order事务中属性级锁和区间锁加锁次数都要多于物理锁对表锁和行锁的加锁次数.但是在实际加锁过程中,由于New-Order事务有大量的Insert操作,而Insert操作不需要任何的关联条件比较,而且由于只有主键上需要对索引树进行查找和修改,因此加锁非常迅速.其余的4个事务,物理行锁机制下的加锁数目远超过属性谓词锁,尤其是Payment事务和Order-Status事务,加锁次数之比超过300.Payment事务有大量基于非主键的访问,而对于Order-Status这样的只读事务,属性谓词封锁总是可以以固定的加锁代价来达到事务调度的目的.Stock事务全是范围查询,因此属性谓词封锁只需要极少的锁数目.4.3系统的加大和调整设置为测定属性谓词锁系统在综合方面的性能,本实验将TPC-C测试15min,通过测试加锁次数、内存开销和CPU占用时间对物理行锁和属性谓词锁之间进行比较.首先是测试所有事务按照各自比例运行