（计算机应用技术专业论文）xml事务模型及并发控制研究.pdf

x m l 事务模型及并发控制 术。该技术采用与常用的锁升格或人工指定加锁级别等技术完全不同的思路， 根据系统当前操作冲突情况，只有在真正需要时才进行锁降格操作。因此，在 一般情况下，系统只需要加很少数量的锁就可以实现并发控制的目的，且不会 降低并发度。本文首先使用子树锁提出了一个具体的自适应粒度锁调度器实现， 而后建立了通用的自适应粒度锁理论模型，将这一技术加以推广，理论上能够 对所有基于加锁的x m l 调度器进行优化，大幅减少加锁次数和维护锁对象古 用的内存开销。 为测试本文提出的协议和算法的有效性，我们还进行了大量的实验，结果 表明本文提出的并发控制协议能够非常有效的降低事务回滚率和提高系统吞吐 率，使用自适应粒度锁技术在x m l 数据层次结构比较丰富时也能在很大程度 上消除不必要的加锁操作，从而提高系统性能和降低并发控制带来的开销。 关键词：x m l ，事务，并发控制 a b s t r a c t x m lh a sg 越i l e dg r e a tp o p u l a r i t yi nr e c e my e a 鹕a i l de m e r g e da san e w s t a n d a r df o rd a t ar e p r e s e n t a t i o na n de x c l l 踟l g eu n d e r ，e s p e c i 胡l y lb yt h ep r o m o _ t i o no fw 3 ca i l dl e a d i i l gc o m p u t e rc o m p a n i e s x m li sb e i gu s e di nm o r ea n d m o r e8 r e a s w i t ht h er a p i da d o p t i o no fx m l ，t h ei n t e r e th 8 sb et u r n e di n t oa g 培a n t i cd a t a b a s e 口a d u m l 矿 w i t ht h ei n c r e 8 s eo ft h ea m o u n t0 fd a t aa v a i l a b l ei nx m l i 1 1 f b m a t i o nm a i l a g e m e n tt e c l l n i q u e sf b rx m ld a t ab e c o m ee s p e c i 8 j 1 yd e m a 丑d i n g t o d a ym o s t r e l a t i o n a l ，o b j e c t o r i e n t e do ro b j e c t r d a t i o a 1d b m sh a sp r o v i d e de x t e n 8 i o n sf o r x m l a n da tt h es 锄et i m e ，t h ed a t a b 8 s et 缸1 0 r e df o rx m l ，n 锄e l yx m ln 孙 t i v ed a t a b a s e ，g a i l l sm o r ea n dm o r ea t t e n t i o no fb o t hr e s e 缸c h e r sa n dp r o d u c e r 8 h o w e v e r ，f r 0 】ad a t 8 b a s ep o j n t0 fv i e w ，a l 】n a t j v ex m ld 8 t a b a s e st o d a ya 糟 f a rf r o mp e r f e c t a m o n g 础lo ft h ed e 丘d e n c i e s ，t r a n s a c t i o nm a n a g e m e n ta n d c o n c u r r e i l c yc o n t r o lt e c h n i q u ei so n eo ft h eb i g g e s to n e s ，i nt h i ss i t u a t i o n ，i t s o fg r e a ti m p o r t 粕c et h a tw ei n v e s t i g a t et h et r 8 肛8 a c t i o nm o d e la i l dc o n c u r r e n c y c o n t r o lt e c h n i q u ef o rx m l f i r 8 t ，w ep r o p o s eag e n e r 8 jx m lt r a n s a c t i o nm o d e l i nc o n t r a s tt oo 恤e r t r a n s 8 c t i o nm o d e l 8 ，t h em o d e lw ep r e s e n t e dt r e a t sx m ld o c u m e n ta n dp a t hi n _ d i c e si nt h es a i n ew a * a n dw ep r o p o s e dau n i f i e do p e r a t i o nm o d e lw h i c hc a n d e s c r i b es e v e r a la c c e s sm e t h o ( 1 s ，s u c ha sd o m ，x p a t ha n ds e a r c h i n gv i ap a t h i n d i c e s w 爸t h 曲舀v eat h o r o u g ha n a | y s i so ft h ec o m p l 喇t yw i t hd i f f e r e n tc h a 卜 a c t e r i s t i co fo p e r a t i o l l s b a s e do nt h er e s u l t ，w et h e np r 叩o s eac o n c i s ec o r e o p e r a t i o nm o d e l ，w h i c hc a 血b ei m p l e m e n t e de a s i l ya n dg u a r a n t e e sh i g hc o n _ c u r r e n c ya s 、e u 、 km 8 0d i s t i n g u i s hb e t w e e nw e a ks e r i a l i z a b i l i t ya n ds t r o n g s e r i 出i z a b i l i t y ，f o ro r d e ri n 8 e n 8 i t i v ea j l do r d e rs e i l s i t i v e 印p l i c a t i o n sr e s p e c t i v e l y b a s e do nt h et r a n s a c t i o nm o d e lw ep r o p o s e d ，w ed e s i g n e dt w oc o n c l l r r e n c y c o n t r 0 1p r o t o c o l s ，n a 腼e l ym s p x wa n dm s p x - s m s p x _ wi sf o rw e a ks e r i 出i z a b i t i l ya n dm s p x - si sf o r8 t r o i l gs e r i a l i z a b i l i t 矿w ei n t e f a t e dt h es t r o n g p o i n to f m u l t i v e r 8 i o n i n ga n ds e m a n t i cc o n c u r r e n c yc o n t r o li n t ot h e 8 et w op r o t o c o l s w i t h x m l 事务模型及并发控制 t h ee m p l o y m e n to fs e v e r 出n o t d b l ef e a t u r e ss u c l la sp a t hl o c ka n dr 8 n g ei o c k ，t h e m s p xs e r i e so fp r ( ) t o c o l sc a ng u a r a n t e eg o o dc o n c u r r e n c y ，w i t h o u tb r i n gt o o m u c hc o m p l e x i t ya n db u r d e nt ot h e8 y s t e m f i n 址l y ，w ep r o p o s et h ea d a p t i v el o c kg r a n u l a r i t ys c h e d u l e r ，w h i c hi sai n - n o v 砒i v et e c h n i q u et h a tc a nr e d u c e1 0 c ko p e r a t i o n sa n dt h em e m o r yu 8 e df o r m a i n t a i n i n gl o c ko b j e c t s f i r s t ，w ed e s i g n e dac o c r e t el o c kp r o t o c o lb a s e do n s u b t r e el o c k i n g a n ds e c o n d l y 】w e 舀v et h ef o l m a lt h e o r yo fa d a p t i v e1 0 c kg r 锄一 u l a r i t ys d l e d u l e r ，w h i c he 妯e n d st h i st e c h n i q u ei n t oi t sg e n e r a lf b r m w ea j s oc o n d u c t e dp l e n t yo fe v a l u a t i o n s t h er e s l l l ts h o w st h a tt h em s p x s e r i e so fp r o t o c o l sw ep r o p o s e dc a nr e d u c et r a n s a c t i o nm l l b a c k 8 舢1 di n c r e a s e s y s t e mt h r o u 曲p u t i ta j s o8 h o w st h ep o w e ro ft h ea d a p t i v el o c k 盯a n u l a r i t y s c h e d u l e ri nc a s eo ft y p i c a lx m le n v i r o n m e n tt h a tt h ed a t ai 8h i e r a r c h i c a j k e y w o r d s ：x m l ，t 功田s a c t i o n ，c o n c l l r r e n c yc o n t r 0 1 表格 3 1 图3 1 所示文档模型的节点值 3 2d o m 操作的x p a t h 语义描述 4 1m s p x 一8 协议锁相容性矩阵 4 ，2 数据参数配置 4 3 操作参数配置， 4 4 事务参数配置 4 5 实验中使用的配置说明 46 m p x w 协议锁模式相容性矩阵 5 1 子树锁模式相容矩阵 52 “按需锁降格”调度器工作流程示例 5 3 自适应粒度锁实验配置说明， 毖如 弘缸舵够“ 韶g 插图 3 ，1 x m l 文档示例 3 2x m l 文档示例， 3 3 “0 0 1 ”效应示例， 3 4 “1 1 0 ”效应示例 3 5 线性操作“0 0 1 ”效应示例， 3 6 线性路径“1 1 0 ”效应示例 3 7 次序相关操作“0 0 1 ”效应示例 3 8 多个f o n 蕊分s i b l i n g 轴向“0 0 1 ”效应示例 3 9 多个f o l l o w i n 乎8 i b l i n g 轴向“1 l o ”效应示例 4 1 幻象处理示例 4 2m s p x w 访问操作运行示例 4 3 弱可串行性：更新事务概率， 4 4 弱可串行性：事务长度， 4 5 弱可串行性：并发事务数 4 6 弱可串行性；配置b ， 4 ，7 弱可串行性v s 强可串行性：插入操作比率 4 8 强可串行性：更新事务概率 4 9 强可串行性：事务长度 4 1 0 强可串行性：并发事务数 4 1 1 弱可串行性：配置a ， 5 1 “按需锁降格”原理示例， 52x m a c l l 目录示例， ， 5 3 图书目录示例， 5 4 “按需锁降格”原理示例 姐驰凹弘弘；霉盯勰 蚯舳盯鹋伯订仡蔼他孔 馋5 = s ： x m l 事务模型及并发控制 5 5 自适应粒度锁： 5 6 自适应粒度锁： 5 7 自适应粒度锁： 5 8 自适应粒度锁： 5 9 自适应粒度锁： 5 ，1 0 白适应粒度锁： 更新事务概率 事务长度 并发事务数 配置6 实验结果 配置c 实验结果， 前一章配置b 实验结果 1 0 2 1 0 2 1 0 3 1 0 3 1 0 4 1 0 4 1 1 研究目的与意义 第一章绪论 可扩展标记语言x m l ( e x t e n 8 i b l em 8 r k u pl a n “a g e ) 由w 3 c 于1 9 9 8 年 提出，目前已经成为i n t e m e t 上数据交换和数据表示的事实标准。虽然x m l 的 出发点相当简单一将数据加上表示其含义的标签一但却带来了异常深远的 影响。将数据编码为x m l 格式的w e b 服务器和应用程序将发现信息能够以 一种简单可用的方式加以表达，这些信息的提供者也能非常简便的提供互操作 性；将内容与其表示相分离使得x m l 能更专注于表示数据的语义信息；基于 x m l 的简单性，通用而高效的x m l 解析器和访问接口在各个平台上都易于获 取，开发基于x m l 的应用变得异常简单；用户自定义标签和无限嵌套的能力 赋予x m l 无限的可扩展性，几乎可以清晰自然的表示各类数据。 鉴于x m l 的上述优势，x m l 在各个领域都得到的广泛的应用。基于x m l 的行业标记语言，如数据领域的m a t h m l i m 9 9 、化学领域的c m l c ml 】比比 皆是；在电子商务等领域中逐渐代替传统的e d i 技术，成为数据交换的新标 准；成为蓬勃发展的w 曲s e r 、，i c e 技术的基石：业界领先的软件提供商提供面 向x m l 的工具和产品；众多企业和研究者以x m l 格式发布他们的数据；以 x m l 为基础的精确搜索技术有望革命性的提高信息检索的效率和准确度。种 种现象表明，x m l 数据及面向x m l 数据的应用将继续快速发展。 由于x m l 的广泛应用，一个更为激动人心的事实是x m l 币逐步将w 如 转化为一个巨大的数据库。但将数据表示为x m l 只是对w 如这一巨大数据库 进行有效处理的第一步，如何对大量的x m l 数据进行有效管理和检索，对传 统的数据管理技术提出了巨大挑战，也为数据库研究提供了良好的机遇。 数据库产商对这一新的需求迅速作出了响应。目前大多数商业化的关系、 面向对象和对象关系数据库系统都提供了各种x m l 数据的扩展和插件，与此 同时，为x m l 数据管理量身打造的x m l 原生数据库系统也不断涌现。构建于 传统数据库之上的x m l 数据管理系统( 即x m l 使能数据库) 与x m l 原生数 据库各有其合适的应用场合。x m l 使能数据库构造于成熟的传统数据库产品 之上，充分利用了现有产品存储管理、事务、索引等各项功能支持，在将原有的 2 x m l 事务模型及并发控制 关系数据发布为x m l 格式和处理格式比较规整的x m l 数据时占具优势；但 对于面向文档的数据、结构复杂、有很深的嵌套层次、规则性不好、次序相关的 x m l 数据时( 如目录信息、制造业零件信息、b 2 b 事务日志等) ，则x m l 原生 数据库是比较好的选择。虽然x m l 原生数据库并不会取代现有的数据库系统， 但作为x m l 数据管理方式的选择之一，对特定的x m l 应用有明显的优势，因 此，研究x m l 原生数据库技术具有重要的意义，这一技术也也引起了众多研 究人员的关注。 然而，从数据库的角度，现有的x m l 原生数据库产品还远非完善。对数据 更新的支持不足一直是现有x m l 原生数据库系统最大的弱项之一，众多系统 只支持文档级的更新，只有少数系统提供专有的更新语言或接口支持。但作为 数据库产品，数据更新及事务支持问题不容忽视，据业界领先的x m l 原生数据 库提供商s o f t w a r ea g 公司研究人员b r y 8 1 1q u i n n 统计 q u i 0 5 】，为成为一个成 熟的数据库产品，现有的x m l 原生数据库系统在很多方面还亟待加强，其中最 主要的就是事务管理和对标准c r u d 操作( 即c r e a t e 、m 划、u p d a t e 、d e l e t e ) 的支持。众多x m l 应用中也确实存在多用户并发访问的问题，一个典型的例 子是w 曲s e i c e s 中的服务注册中心，需要同时处理对已经注册服务的查询以 及处理服务的加入和删除。 现在x m l 原生数据库系统缺少对事务的支持固然与x m l 缺乏一种标准 的数据更新语言有很大关系，但同样重要的是更新必然导致并发问题，而目前 并没有一种成熟的x m l 并发控制技术存在。虽然近两年来一些研究人员已经 对此展开了研究，并提出一些x m l 并发控制技术，但总体来说，对x m l 事务 处理技术的研究还处于初级阶段，在x m l 产品中的应用更是处于萌芽状态，因 此，本文对这一问题进行比较深入的研究和探讨。 1 2x m l 基础及相关标准 x m l 是w 3 c 提出的标准【b p s m + 9 8 l ，主要特点是支持任意嵌套的层次结 构及允许用户自定义标签。由于其强大的数据表示能力及易于处理的优点，在 短短几年就在各领域得到广泛的应用。 虽然x m l 最初的设计目的是一种应用于万维网表示数据和进行数据交换 的标记语言，但以后的发展证明了它同时也是连接数据库的桥梁。从数据库研 究的角度看，x m l 数据是典型的半结构化数据( s e i s t r u c t l l r e dd a t a ) ，拥有 众多只有数据库才具备的特征： 第一章绪论 3 1 x m l 数据呈现出明显的统一的结构，一个x m l 文档的数据通过元素的 互相包含关系构成树形结构； 2 x m l 可拥有d t d 或s c h e m a 【f w 0 4 】，指定了x m l 数据必需满足的结构 和内容需求，相当于关系数据库中的表模式定义； 3 x m l 拥有自己的数据模型，目前处于主流地位的有d o m 【h h w + 0 4 】和 x d m 【f m m 十0 5 】； x m l 的操作和访问接口也非常丰富，分为过程式和陈述式两大类。过 程式接口的代表是d o m 和s a x 。d o m ( d o c u m e n t0 b j e c tm o d e l ) 定义了 x m l 的一个抽象数据模型及对该模型的个操作集，包括遍历和更新功 能。s a x ( s i m p l ea p if o rx m l ) 则是一个简单的基于事件触发的l 访问接 口【s a x 】。 陈述式接口即查询语言。由于x m l 丰富的功能以及应用领域的广泛，制 定一个优秀的x m l 查询语言难度很高。因此曾经有一个长期的“群雄割据” 时代，研究者提出了l o r e l f a q m + 9 7 】、q l l i l t f c r f o o 】、x m k q l d f f + 9 8 】等众 多x m l 查询语言，并各自获得一定程度的流行。直到w 3 c 于2 0 0 1 年2 月 1 5 日推出x m l 官方查询语言x q u e r y 一的草案后这一现象才逐渐缓解， 但x q u e r y 目前仍未成为正式标准【b c f + 0 5 卜x q u e r y 语言是一种陈述式语 言，基本的结构为f l 、v r 表达式，表达能力非常强大，可以完成非常复杂的连 接、分组、排序、结果构造等功能。x q u e r y 的基础是x p a t h 语言，定义了路 径表达式功能及其语义【c d 9 9 o 另一个目前应用比较广泛的x m l 查询语言是 x s u 【c 1 a 9 9 l ，同样基于x p a t h ，主要功能是进行x m l 格式转换。目前x m l 查 询语言在对数据更新的支持上落后于对查询的支持，由于x q u e r y 在相当长一 段时间内没有提供更新功能，研究者已经提出了几种“非官方”的x m l 更新语 言【t i h w 0 1 ，l m o o ，l l j w 0 3 1 ，主要提供节点的插入、删除和值修改功能，最近 w 3 c 也提出了x q u e r yu p d a t e i u t y 的工作草案 c r f 0 6 】，还支持节点的重 命名等功能。 1 3 x m l 数据管理 由于x m l 的流行，与x m l 相关的数据管理产品不计其数，著名的x m l 数据库研究者及顾问r 舳a l db o i l r r e t 在【b o u 0 6 1 中将v f l 数据管理产品分 4 x m l 事务模型及并发控制 为中间件、i d e 和编辑器、x m l 使能数据库( x m l e a b l e dd a t a b a s e ，简称 x e d ) 、x m l 原生数据库( x m l 广n a t i v e dd a t a b a s e ，简称n x d ) 、x m l 服务器、 包装器、内容管理系统、x m l 查询处理引擎、x m l 数据绑定等9 大类，其中与 数据库技术密切相关的是x e d 、n x d 和x m l 查询处理引擎。 x e d 为以扩展形式提供x m l 支持的传统数据管理产品，一般构建于关 系数据库之上，为现有系统提供了支持x m l 数据的快速便捷的方式，因此 引起了研究者的大量关注和主流数据库厂商的青睐。x e d 的核心是x m l 数 据关系存储映射技术，研究者提出了众多l 数据到关系数据的映射策略， 可分为模式不敏感映射和模式敏感映射两大类。模式不敏感映射使用关系表 示节点间的父子关系【f k 9 9 ，s k w w o o ，g r u 0 2 ，y a s u 0 1 】：模式敏感映射根据 x m l 模式定义、人工指定的映射配置文件或某种数据挖掘方法确定映射方式 s t z + 9 9 【b f i 玛0 2 】【d f s 9 9 卜由于模式敏感映射利用了部分x m l 语义信息，效 率一般比较高，因此o r 蒯e 、d b 2 、s q ls e r v e r 等商业化数据库中都采用这一 方式。由于x e d 系统对外提供x m l 操作界面，底层却以关系模型等实现，因 此还需要进行咀l 查询到s q l 查询的转换，而这一转换就可能导致一部分语 义信息的丢失，使得对部分查询难以进行有效的优化 k k n 0 4 】。 n x d 是为存储与查询x m l 数据而特殊设计的数据库管理系统。目前 这样的系统有很多，可以在【b o u 0 6 】中获得它们的列表，其中产品主要有 b e r k e l e yd bx m l 、i p e d o 、n e o c o r ex m s 、x i n d i c e 等，研究性系统主要有 l o r e 、t i m b e r 、n a t i ) 【、t 眦i n o 【s c h o l 】等。 各种n x d 系统的具体实现技术大不相同，但总体来说，存储系统和x m l 查询处理技术是目前n x d 研究的重点。存储系统是x m l 原生数据库的基础 要解决的主要问题是如何将x m l 文档中的节点组合成物理记录。组合方式主 要可分为三大类。第一类是基于文档的组合，如a p a c h e 的开源x m l 原生数 据库管理系统x i n d i c e 【x i 】就采用这种方法，即一个文档就对应一条物理记录， 采用相同模式的文档被组合在一起。第二类是基于元素的组合，即将同类元素 组合，采用这种方式的系统有l o r e 【m a g + 9 7 】和t i m b e r 【p a k c + 0 3 1 等。第三 类是基于子树的组合，即尽量将属于同一子树的节点组合存储在一条物理记录 中，这方面的代表是n a t 议系统【f h k + 0 2 】，中国人民大学开发的x m l 原生数 据库o r i e n t x 中使用的l p b c 方法也是一种基于子树的组合方法m l l a 0 3 卜 为提高空间效率，数据压缩技术也在n x d 存储的研究热点之一【l s 9 9 ，t h 0 2 】6 第一章绪论 5 查询处理是数据库的核心，因此对x m l 查询求解技术的研究也非常活跃， 包括查询代数、执行算子、代价估计、索引设计、等价变换和代数优化等多个方 面。索引是提高查询求解效率的关键技术，目前n x d 系统中采用主要有值索 引、边索引和路径索引等，其中路径索引最为重要，也最为复杂，是x m l 索引 技术研究的绝对热点。路径索引首先是在面向对象数据库中提出的b e r 9 4 1 ，但 在x m l 数据库中应用更为普遍。路径索引是原x m l 文档的简化表示，典型的 有d a t a g u i d e g w 9 7 1 ，1 一i n d e x ，f b i n d 口f l ( b n k 0 2 1 等，f k b n k 0 2 1 中的半相 似性概念为路径索引研究提供了主要理论工具。执行算予研究中最突出的是结 构化联接技术【a k j p + 0 2 ，c v z + 0 2 】，该技术主要优化两个节点集之间祖先后 裔关系的匹配，是x m l 查询处理技术的特点之一。 但以数据库的视角审视现有的n x d 系统及其研究，可以发现n x d 技术要 达到成熟，还有很长一段路要走，其中的一个障碍就是事务管理。研究者已经 提出了一些x m l 事务模型和并发控制方式，但现有x m l 产品基本上不提供 事务支持，或只依赖于传统的存储系统提供，因而丧失了一部分并发度( 详见第 二章) 。 1 4 本文组织 本文组织如下：第一章分析了本文的研究目的和意义，并简述了与本文相 关的x m l 基础知识和数据管理技术；第二章综述传统并发控制技术和现有的 x m l 并发控制协议，讨论传统并发控制技术应用于x m l 数据的不足，并对现 有x m l 并发控制协议进行评价；第三章提出通用的x m l 事务模型，综合考虑 了路径索引检索、d o m 、x p a t h 等常用访问接口，明确提出x m l 强弱两类可 串行性，并对x m l 调度器的实现复杂度进行了深入分析，而后提出一个切实 可行的x m l 核心操作模型：第四章在第三章基础之上，提出两个具体的并发 控制协议，并进行实验验证协议的效率；第五章介绍自适应粒度锁调度器的实 现，应用按需锁降格技术对基于加锁的x m l 调度器进行优化，降低加锁的开 销。最后第六章总结全文并给出未来的研究方向。 第二章并发控锎理论及x m l 并发控镧 2 1 传统并发控制理论 传统的并发控制理论经过约三十年的发展，已经形成一套非常完善的理论 体系，g e r h 8 r d 、e i k u m 的经典教科书对传统并发控制理论做了非常严谨和全 面的介绍 w v 0 2 l ，若未加特殊说明，本节的内容来自于对该书的概括。 2 1 1 并发控制理论基础 传统并发控制理论的基础是页模型，该模型假设数据库为一个“数据页”的 集合，且这一集合是固定的，“页”既不会产生，也不会消亡，对“页”的只有读 和写两种操作。这里的“数据页”是一个逻辑上的概念，应用到关系数据库则物 理上通常对应于记录、关系等具体实例。 事务被定义成多个读写操作的序列加上一个位于最后的提交或回滚操作， 多个事务操作的任意交叉执行序列称为历史，历史的前缀称为调度。并发控制 的主要目的是保证调度的正确性。 因此，首先需要建立的是调度的正确性标准。在所有的事务正确性标准中， 使用最广泛的是冲突可串行性。冲突可串行性的基础是操作之间的冲突关系定 义，在页模型中，一般认为对同一数据项的读写或写写操作是冲突的。基于操作 冲突定义，冲突可串行性要求正确的调度必须与某串行调度有着相同的冲突关 系。验证冲突可串行性的两个重要技术分别是冲突图和交换等价。冲突图技术 使用图表示冲突关系，只要调度的冲突图无环，则该调度是冲突可串行化的；交 换等价技术则指出一个调度可冲突可串行化当且仅当通过交换该调度中不冲突 的操作的颞序可将该调度变换为某串行调度。另一个比较重要的正确性标准是 视图可串行化，要求正确的调度必须与某串行事务有相同的数据读取关系( 即 读操作读取到相同的值) 及各“数据页”终值相同。 2 1 2 单版本并发控制 为保证调度的正确性，研究者提出了众多并发控制协议，分为悲观和乐观 两类。 8 x m l 事务模型及并发控制 悲观类协议在操作可能导致不能串行化时阻止操作进行，主要有基于加锁 的协议、基于时间戳的协议和串行化图检测。 基于加锁的协议中最常用的是两阶段锁协议( 2 p l ) ，要求事务加锁活动 分为上升和下降两个阶段，第一个阶段为上升阶段，事务只能进行加锁操作，在 事务进行第一个放锁操作后进入下降阶段，事务只能释放锁。2 p l 能保证冲突 可串行性。2 p l 有很多变种，包括严格2 p l ( s 2 p l ，要求排它锁保持到事务结 束) 和强2 p l ( s s 2 p l ，要求所有锁保持到事务结束) 。非两阶段封锁协议中最 主要的是树协议，认为“数据页”之间存在虚拟的父子关系，构成树形结构，同 时要求事务在获得子节点的锁之前必须获得对父节点的锁。最初的树协议是只 考虑写操作的w t l 协议，r 、v t l 协议对其进行扩展，增加对读操作的支持。 时间戳排序协议( t o ) 为事务设定一个时间戳( 通常是事务开始时一个全 局计数器的值) ，并为数据项分别记录读取和写入它的最高事务时间戳，通过这 些机制，系统可以检测出读写操作是否按事务的时间戳序发生，如果不是，则调 度器拒绝将要进行的操作。 串行化图检测协议( s g t ) 维护事务之间的冲突图，并保证图中不包含环。 理论上可产生所有的冲突可串行化调度( 2 p l 、w t l 和t o 都不能产生所有冲 突可串行化调度) ，但却难以实现，因为事务提交时也不可将其从冲突图中移 走。 乐观类协议将事务执行分为三个阶段。在读阶段执行事务包含的操作，但 将写操作的结果放在事务的私有工作空间内；第二个阶段为有效性确认阶段， 验证调度是否冲突可串行：通过验证的事务进行第三个阶段即写阶段，将私有 工作空间内的写结果发布到数据库中。乐观类协议中常见的有b o c c 协议和 f o c c 协议，主要是有效性确认的方法不同，b o c c 协议中进行有效性确认的 事务执行与所有已提交事务的冲突检测，f o c c 协议中进行有效性确认的事务 执行与所有处于读阶段的事务进行冲突检测。 2 1 3 多版本并发控制 多版本并发控制技术假设数据项存在多个版本，写操作产生新版本，读操 作则可以根据一定的规则选择一个版本读取其内容。由于读操作有了更多的选 择，多版本并发控制协议通常能获得更好的并发度。常用的多版本并发控制协 议主要有多版本时间戳排序、多版本两阶段锁、多版本串行化图检测和只读协 第二章并发控制理论及x m l 并发控制 9 议多版本协议。 多版本两阶段锁协议( m v 2 p l ) 将版本分为三类，提交版本为已提交事务 创建的版本，当前版本为最新的提交版本，未提交版本为当前活动事务创建的 版本。对读操作，m v 2 p l 为其指定一个当前版本或未提交版本，对写操作，只 有没有其它事务创建的未提交版本时才被允许。在事务提交时，m v 2 p l 需要等 待所有已经读取当前事务写过的数据项的当前版本的事务( 因为这些事务读取 的是以前的版本) 及所有当前事务读取的版本的创建者提交后( 防止脏读) 才 提交当前事务。 多版本时间戳排序协议( m v t o ) 的基本思想是通过调度使事务并发执 行的结果与事务按其开始时间戳大小顺序的结果等价。每个事务都有一个时间 戳，每个版本也带有一个时间戳，与创建该版本的事务的时间戳相同。对于读 操作，m v t o 调度器为其指定一个先前的版本。对于写操作，调度器检查系统 某些时间戳太于当前事务的事务是否已经读取了时间戳小于当前事务的版本， 若是，则拒绝这一写操作并回退事务( 因为这些事务本应读取当前事务写操作 产生的版本) ，否则产生一个新版本。在事务提交时，为防止级联回滚，要求事 务等待所有它读取过的版本的创建者提交之后才能提交。 只读事务的多版本协议( r o m v ) 区分事务为只读事务和更新事务。对只 读事务，使用m v t o 类似的协议，事务被指定一个时间戳，调度器为其读操作 始终指定数据项中小于当前事务时间戳的最新版本；对更新操作，则使用常规 的两阶段封锁。只读事务多版本协议保证只读事务与更新事务不相互阻塞，且 协议本身实现简单，在o r a c l e 等实际的数据库中得到广泛应用。 多版本串行化图( m v s g t ) 是单版本串行化图检测协议( s g t ) 在多版本 系统中的扩展，保证多版本冲突图无环。 2 1 4 经典并发控镧协议总结 由前两节的介绍可以看到，传统的并发控制协议可分为两大类，即单版本 并发控制协议和多版本并发控制协议。可以使用如下的结构表示： 单版本并发控制协议 一悲观类协议 基于加锁的协议：s p l ( s 2 p l 、s s 2 p l ) 、w t l ( r w t l ) 1 0 x m l 事务模型及并发控制 + 时间戳排序：t o + 串行化图检测：s g t 一乐观类协议：b o c c 、f o c c 多版本并发控制协议 一不限定版本数：m v t o 、m v 2 p l 、m v s g t 、r o m v 一限定版本数：2 v 2 p l 2 1 5 关系数据库中的并发控制技术 上述传统的并发控制理论假设页模型包含的“数据页”集合是衡定的，主要 目的是解决事务交叉执行时产生的读脏数据、丢失修改和不可重复读问题。但 对实际的关系数据库系统，这假设是不现实的。若考虑到新数据的插入操作， 则运用上述传统并发控制技术会出现幻象问题。为解决幻象问题，通常需要付 出巨大的代价，若没有其它信息可用，则为防止幻象，事务必须锁定整个数据 库。 在关系数据库中解决幻象问题的最早的方法是使用谓词锁技术【e g 1 7 6 t 该方法通过判断d m l 语句包含的谓词是否兼容来决定锁之间的相容性。由于 即使对于简单的谓词( 如比较操作的布尔组合) ，判断其可满足性也是个n p 问 题【h r 7 9 】，因此谓词锁并不是一个实际的方法。p r e c i s i o nl o c k i n g 是对谓词锁技 术的简化，不检测谓词的可满足性，而是检测系统实际读取或更新的数据项是 否满足其它事务的谓词条件 j b b 8 1 1 但仍是一种代价很大的方法。解决幻象问 题的第二类方法是基于关系数据库中更新事务的i d m ( i n s e r t i o n 、d d e t i o n 、 m o d i 矗c a t i o n ) 模型【a v 8 8 】，根据这些事务的语义，定义出操作的可交换性( 如 两个i n 8 e r t 事务可交换) 并发展出一套精巧的并发控制理论。然而，这两类协 议虽然有理论研究价值，却难以有效实现。 解决幻象问题真正可行的方法来自于对系统所处理的谓词条件进行简 化，只考虑处理单个等值谓词或范围谓词，这一受限的谓词形式在索引结构 的支持下可以获得高效的实现。这部分工作的基础称为前键封锁( p r e v i o u s k e yl o c k i n g ) ，由j i mg r a y 等提出 g r 9 3 】，这一协议要求插入操作对插入的 键值和前一键值加锁，删除操作对前一键值加锁。与此相对应的协议称为后 键封锁( n e x tk e yl o c k i n g ) ，主要由m o h a n 等提出【m o h 9 2 ，m o h 9 6 。最初这 第二章并发控制理论及x m l 并发控制 些协议只应用于b + 树索引，但最近研究者已将其推广到其它索引结构中 l s 9 7 ，k m h 9 7 1 。可以说，基于对索引结构的并发控制，幻象问题已经有了比较 完善的解决方案。 关系数据库并发控制中另一常用技术是多粒度锁，由j i mg r a y 等提出 f g l p t 7 5 】，目的是减少加锁的时间和空间开销。这一技术的基础是意向锁，要 求当事务想加细粒度锁时，需要先在粗粒度上加意向锁。意向锁标识了一条粒 度层次结构的路径，通向真正被加上共享或排它锁的数据项。这时对于其它事 务就可以很容易的进行冲突检测。使用多粒度锁协议，事务开始时加细粒度的 锁，当事务拥有的细粒度锁数量超过一定阈值时，升格( 1 0 c ke s c a l a t j o n ) 到粗粒 度锁。 由于严格保证可串行性对系统的性能影响较大，实际的关系数据库通常都 支持低于可串行性的隔离级别。在s q l 标准i b b g + 9 5 】中定义了四种隔离级 别：读未提交、读已提交、可重复读和可串行化，这些隔离级别通过对两阶段加 锁协议进行简单的修改就可得到。另一个常用的隔离级别是基于多版本的快照 隔离b b g + 9 5 】，要求事务读取到最近版本且并发的更新事务写集合无交集。 2 1 6 基于语义的并发控制 c a d 或c a s e 等高级的数据库应用导致了面向对象数据库的诞生，也对 并发控制提出了新的需求，如支持长事务、支持用户控制、支持协作过程等。这 些问题产生的根本原因是传统并发控制技术对数据及操作进行了过度抽象，无 法利用应用层的语义信息。相反，如果能充分利用应用层语义，就可能从根本 上提高事务的并发度，为此研究者针对这些高级数据库应用，提出众多改进协 议，可统称为基于语义的并发控制技术。 基于语义的并发控制技术可分为两大类：基于事务语义的并发控制和基于 抽象数据类型语义的并发控制。基于事务语义的并发控制中有代表性是有利它 锁、快照验证、嵌套事务、多层事务等。利它锁【s g m a 8 7 】是对两阶段锁协议 的扩展，该技术利用事务数据存取模式信息，将事务不再需要访问的数据项上 的锁提前捐赠( d o a t e ) 出来，允许其它事务提前获得对这些数据项的访问能 力。利它锁主要是对长事务导致的加锁时间过长问题进行优化。快照验证技术 | p s u 8 6 】是对传统乐观并发控制技术的扩展，将冲突划分为严重冲突和非严重 冲突，严重冲突导致调度不再可串行化，因此产生严重冲突时事务必须重启， x m l 事务模型及并发控制 非严重冲突不破坏可串行性，不需要处理。嵌套事务是对平面结构事务的扩展， 允许事务内部的并发。多层事务 w e i 9 1 】将事务的操作分成多层，上一层的一个 操作包含下一层的多个操作，对不同的层，可使用不同的并发控制协议。如b + 树加锁协议可看作是这一技术的应用，在记录层使用后键封锁坍议，在页层则 使用锁耦合、链接等技术b s 7 7 ，l y 8 1 1 。基于抽象数据类型语义的并发控制根 据操作的语义定义其冲突性，如对于一个队列，其r e m o v e 操作和a p p e n d 操作 是不冲突的，尽管这两个操作都修改了同一个队歹i j 对象。定义操作之间冲突关 系的依据主要有可交换性、序列依赖等。 2 1 7 关系数据库产品中的并发控制协议 关系数据库产品中使用的并发控制协议主要是二阶段锁或多版本协议 f s k s 0 1 1 。商业数据库中s q ls e r v e r 与d b 2 使用基于二阶段锁的协议。s q l s e r v e r 支持多种锁粒度，包含数据库、表、页和记录。为减少加锁的开销，系统 根据隔离级别、扫描方式、选择率等条件在操作执行前确定合适的加锁粒度，同 时也支持锁升格。d b 2 支持表级锁和记录级锁，使用后键封锁技术防止幻象。 基于多版本的并发控制技术在关系数据库系统中也得到了广泛应用。商 业数据库中使用的有0 r a c l e 和s q ls e r v e r2 0 0 5 版本，o r a c k