（计算机应用技术专业论文）xml并发控制协议的设计.pdf

浙江大学硕士学位论文 摘要 摘要 随着互联网技术的发展，订l 已经成为数据表达和交换的新标准。事务性 能是衡量一个数据库管理系统( d b m s ) 的关键指标之一，而并发控制是改善一 个d b m s 事务性能的重要机制。随着订l 数据库管理系统( l d b m s ) 研究的 日益深入，研究基于树型结构的儿数据的并发控制协议变得十分重要。 捌l 数据是动态变化的树型结构数据，而前人提出的树加锁协议是基于静态 树结构数据而定义的，这就需要新的基于动态变化的并发控制协议。针对) ( m l 数 据的特点，定义一个操作集，它可以将一个树型结构的) 【m l 文档变化为另外一个 合法的树型结构的】( m l 文档。在这个操作集基础上定义了x m l 动态树协议x d t p ， 并证明了该协议能继续保持静态树协议的优良特性：可串行化和无死锁。在实际 的数据集上进行了实验，结果表明】【d t p 有着较好的性能。 本文主要内容：分析了) ( m l 数据操作的特点，定义了新的操作集，从树自动机 的角度，定义了这些操作改变x 札文档状态的特点。定义了新的动态捌l 并发控制 加锁协议。证明了上述新的并发控制加锁协议的可串行化和无死锁特性。 为测试本文提出的协议和算法的有效性，我们还进行了大量的实验，结果表 明本文提出的并发控制协议能够非常有效的降低事务回滚率和提高系统吞吐率。 在) m 几数据层次结构比较丰富时也能在很大程度上消除不必要的加锁操作，从 而提高系统性能和降低并发控制带来的开销。 关键词x 儿，事务，并发控制，x 儿动态树协议，串行化，死锁 浙江大学硕士学位论文 a b s 仃a c t a b s t r a c t w i t h t h ed e v e l o p m 龃t o f m 锄鸭礼h a s g a i l l e dg r e a t p o ”l a r i t y i nr e c 衄ty e 鹕 卸d 锄明 e d 船an e w s t a l l d a r df 研d a t ar 印0 髂锄t a t i o n 如de x c h a l l g e 舶d e s p e c i a l 耽 b y t l l ep r o m o t i o no f w 3 c 锄dl e a d i n gc o m p u t e rc o m p a m 瞄x m li sb 曲玛l l s c di n m o a n dm o a 勰w i mt h er a p i da d o p t i o f ) m 几，t h eh l t e m e tl 娜b e 饥t i l 】m c d i n _ t oa 百g a 面c 出血i b 嬲eg r a d u a l l y w i t hm ed c v e l o p m e n to f r e s e a r c h 珊l 血t a b 勰em 蝴g 锄e n ts y s t 锄s ( 仉 d b m s ) ，c o n c u 础l tp r o c e s s i l l g0 nm s sx m l d a t am a k e si tv e 巧i m p o n a n tt os t u d y t 1 1 ec o n c u 鳓l c yc o m r o lp r o t o c o l sb 硒e d 衄仃e e - s 伽l c 删x m ld a l a t h e 拄l o c k i l l g p r o t o c o l ，w 勰d e 丘n e db 鹪c do ns t a t i c 仃c e - s 垃l l c t u r e dda _ hh o w e v d l d a t ai t 锄s a r et h ed y n 锄i c a l l yc h a i l g i i l g 仃e e - 曲m c t u r e d 纰h la c c o r d a n c ew i t ht l l ep 加l p 硎髓o f 咀。d a 饥as e to f o p e m t i o 璐a d e f i n e d ，w h i c hc 趾b e 珊e dt oc h a n g c 札 d o c 啪吼t 丘o m 彻e 仃e e - s t m c t l l r e df o m lt oa n o l h 盯l e g a l 仃e e - s t r i i c t l l r e d 向咖t h e m o s td i s t i n g u i s h c df e a t l l ：o f t h i ss e to f 叩e r a t i o mi st h a ti t s 叩e r a t i n go b j e c ti sa 鼬饥圮，n o tas i n 9 1 e d eo f t h e 札d o c 删n t j 1 1 1 i sc h 撇c t 甜s t i c 丘t sf o rt h e 讧i ld a t av e r ym u c h ，b e c a 璐et l l ev a i u a b l e i n 缸m a t i o f 血d o c l me n t 打e ea l l l i e si ni 拓1 e a v e s b 鹤e d t 量l i ss e to f 叩e r a t i 咄， 觚讧ld y n 锄i c 仃p r o t o c o l ( ) 口) t p ) i sp 陀s e m c d 锄di ti sp r o v e dt h a tt 1 1 i sp m t o c o l ， j l l s tl i l 【ei t ss t a t i cc o u n t c i p a i t 仃p m t o c o l ，c o n 曲u e st o 哪u f es e r i a h z a b i l i 够a n d d e a d l o c k 眈c d o mi l ll h ep r e s c eo f m e s e0 p e r a t i o 璐e x p e r j 妇c i l t sa r ec o n d u c t c do n m ed b l p 讧ld a t as e t t h er e s u l 协o f t h e 麟p c r i m e l l t sd c i i l 伽劬a t e m tt h e 讧l d y m m i c 仃l 粥p r o t o c 0 1 ) a ) t pp e r f o msv e r yw c l l i nn l i sc i 形啪s t a i l c e k e y w o r d s 订l ，亿哪a c 垃o n ，c o n c u n 锄c yc o n 仃0 1 ，沮，d ) i i l a l l l i c 在p r o t o c o l ， s e f i a l i z a b i l i 饥d e a d l o 桃 浙江大学硕士学位论文图目录 图目录 图1 1 本文组织结构框架图。7 图2 1 数据库中事务并发执行模型示意图9 图2 - 2 传统并发控制理论结构1 6 图4 - l 讧l 文档树结构。2 6 图4 - 2 加锁矩阵3 0 图4 - 3 顺序一索引链接表3 1 图5 1 讧l 动态加锁协议) t p 实验环境4 8 图5 2 单位时间吞吐量5 0 图5 3 平均响应时间5 0 图5 - 4 单位时间事务回滚率5 l 图5 5 吞吐率一高更新率5 2 图5 6 平均响应时间一高更新率5 3 图5 7 事务回滚率一高更新率5 3 图5 8 吞吐率一低更新率5 4 图5 9 平均响应时间一低更新率5 5 图5 1 0 事务回滚率一低更新率。5 6 浙江大学硕士学位论文表目录 表目录 表1 1 l 数据库存储策略比较5 表2 1 四种加锁机制比较1 1 表4 1 各种锁的兼容性：3 4 表4 - 2 事务t 1 和事务t 2 的一个并发调度。3 5 表4 3 事务t 3 和事务t 4 的一个并发调度。3 6 表5 1 数据参数配置4 5 表5 2 操作参数配置4 6 表5 3 事务参数配置4 6 表5 - 4 事务参数配置4 7 浙江大学硕士学位论文 第l 章绪论 第1 章绪论 1 1 课题背景 1 9 9 6 年1 1 月，波士顿s g 札( s t a n d a r dg e n e r a lm a r k u pl a n g u a g e ) 世界年会产 生一项重大变革，与会代表一致同意将目前i n t e r n e th o m e p a g e 撰写标准h t m l 宣 告终结，而采用全新的电子文件格式化通用标准一x m l 。】( m l 即可扩展标记语言 ( e x t e n s i b l em a r k u pl a n g u a g e ) ，是一种基于s g m l ( 标准通用标签语言) 的简单灵 活的语言，被誉为构成未来w e b 的新工具。 可扩展标记语言儿由w 3 c 于1 9 9 8 年提出，目前已经成为h 锄e t 上数据交换 和数据表示的事实标准。讧l i 匠来逐渐成为因特网上数据表示和数据交换的新标 准，帆用标记表示数据的意义和数据实体之间的复杂嵌套关系，而不像删i ， 那样，仅仅用来规定数据的显示方式，所以，) m m 既可以表示结构化的数据，如 关系和对象数据，也能够表示半结构化的数据，如w e b 数据，) a l 将内容和形式 相分离，使得那些将数据以订l 格式编码的w c b 服务和应用程序可以迅速地以一 种简单、有效的格式提供这些数据信息，这些w 西服务和应用程序之间也可以很 容易地进行交互；并且可以通过x s l 等对同一数据内容提供多种数据表示形式， 所以，可以说，f g h 架起了一座各类数据之间的桥梁，是各类数据之间进行交 换、集成的中间表示形式，另一方面，) ( m l 突破了h t m l 的固定标记集合的约束，用 户可以根据需要定义任何一种标签来描述文档中的数据元素，给用户带来极大的 方便。 在) ( m l 数据库系统的研究过程中，越来越多的学者倾向于将) ( m l 文档视为树型 结构，而将相应的) ( m l 数据库看成是一个有根、有序、带标记的树组成的森林。 显然，研究基于树型结构的x m l 数据的并发控制协议变得十分重要。 s i l b e r s c h a t z 和k e d e m 在其早期文献中提出了针对树型结构数据的并发加锁 协议，也就是著名的树协议( t r e e ”o t o c 0 1 ) ，后来，u l l m a n 在其著作中将树协 议归纳为两种形式，即只锁当前结点的简单锁协议和隐含锁子树的“警告” ( w a r n i n g ) 协议但是，上述树加锁协议，都只能被称之为“静态”树协议因 为，它们都基于一个重要的前提假设：所操作的树型数据是静态的，不考虑插入、 删除、调整结构等可能改变当前树型数据及其结构的操作而我们知道，对l 浙江大学硕士学位论文第l 章绪论 树型结构数据的插入、删除、调整结构是不可避免的。这样，静态树加锁协议显 得不能适应这就需要新的基于动态变化的并发控制协议。 1 2 ) 眦基础简介 ) ( m l 是由w 3 c 定义的一种语言。它是一种雌t al a n g u a g e ，可依据不同应用领 域。以不同方式来描述文档类型与数据结构，简单来说x m l 是一种简单、标准、 可扩展的方式，将各种文字、电子表格、数字等数据以r 趼d a t a 的方式保存。而 且加上可识别的特殊标记，以供进一步的数据处理。 从技术角度讲，) 眦和关系数据库同属数据管理的手段。狭义的x m l 仅仅指一 种语言和采用该语言所描述的x 儿文档，广义的】( m l 包括瑚l 语言、) 【m l 文档及所有 与x m l 相关的技术和工具。如) ( 1 i l 解析器、】( i l 转换技术等。广义的】( m l 和d b m s 具有 大致相似的作用。它们的相同之处： 提供数据存储。酬l 以文件系统为基础，而关系数据库以数据库为手段提 供数据存储。 提供对数据直接存取访问。) 【m l 采用x q l 、) 【p a t h 、x q u e r y ( w 3 c 于2 0 0 1 年 2 月1 5 日推出儿官方查询语言) 等查询语言作为直接操作圳l 的工具。 关系数据库一般都支持s q l 查询。 提供对数据模式的描述。x i l l 采用d t d ( d o c u m e n tt y p ed e f i n i t i o n ，文档 类型定义) 或捌l s c h e 舱( x 肌规范) 来描述数据的逻辑结构。关系数据库通 过关系模式来描述数据的逻辑结构。 提供应用逻辑接口：x m l 采用d o m ( d o c u m e n to b j e c tm o d e l ，文档对象模 型) 或s a ) 【( s i m p l ea p if o r 删l ) 定义应用编程接口，是应用程序能够访 问和更新】( m l 文档的样式、结构、内容；关系数据采用o d b c 、j d b c 、o l 印b 等接口。 支持) ( 1 j l 的数据库将删 l 和关系数据库的优点结合起来，目的是使二者都能发 挥其最大的优点。但这种方式的结合也并不是完美无缺的，由于) ( m l 和关系数据 库在组织上的差异，在存储转换过程中可能丢失一些有用的信息，而且转换过程 本身也会增加系统的开销，影响数据库的效率，增加复杂性。随着x m l 技术的迅 速发展和完善，x i l l 和关系数据库结合的前景是很光明的，同时这个领域也有很 多问题有待我们去研究和解决。 2 浙江大学硕士学位论文第1 章绪论 1 3x 虬数据存储方法 x 虬数据库的存储策略主要有四种：利用文件系统的平面文件、利用成熟的 关系数据库管理系统( r e l a t i o n a ld a t a b a s el l a n a g e m e n ts y s t 鲫，r d b m s ) 、利用 对象管理器或面向对象数据库管理系统( o b j e c t 0 r i e n t e dd a t a b a s e m a n a g e 腿n ts y s t e m ，0 0 d b m s ) 、采用全新的n a t i v e 硎l 数据库管理系统( n a t i v ex 儿 d a t a b a s em a n a g e m e n ts y s t e m ，x b m s ) 。 1 3 1 文件系统的平面文件 利用文本文件来存储x m l 文档数据是最直接和最简单的存储方式，由于这种 存储方式与数据被理解的方式一致，所以能自然地反映对象之间的嵌套和所属关 系对采用这种存储方式的x m l 文档，应用程序可以通过d o m ( d o c 姗e n to b j e c t m o d e l ) 和s a ) 【( s i m p l ea p if o r ) ( m l ) 等编程接口直接进行存取。 1 3 2 关系数据库 将删l 半结构化数据转换为结构化数据后以二维表形式存入关系数据库中， 然后，利用r d _ - b m s 来实现对) ( m l 数据的存储和管理。这种方式可以充分利用r d b m s 强大的数据存储管理功能，但是，由于捌l 和r d b 数据模式之间存在着互异性，所 以不能简单地将x 帆文档存储于关系数据表中为了实现在】( m l 文件和数据库之间 的数据交换，必须提供一个捌l 映射层，将】( m l 文档模式( d t d ，】( m ls c h e 吼) 映射 到关系数据库模式。事实上，实现x m l 文档在关系型数据库中的存储，关键是耍 弄清楚) 【m l 结构与关系型数据库结构之间的映射关系。即要先创建用于存储删l 文 档的r d b 模式，然后拆分x m l 文档，最后将其中的数据存储于已创建的r d b 模式中。 对数据的操作主要利用r d b m s 提供的方法( 如：s q l ) ，当然也可以使用x h i l 方法( 如： x p a t h ，d o m 或s a x ) 1 3 3 面向对象数据库 面向对象的i l 存储方法以对象数据库作为底层存储，在面向对象数据模型 中，所有现实世界中的实体和概念都模拟为对象，利用面向对象数据库，x m l 将 不再被拆分而是被描述成一个对象存人数据库面向对象的方法首先利用d t d 或 浙江大学硕士学位论文第l 章绪论 x m ls c h e 岫建立) 函几数据的0 0 d b 模式，然后按照口一定的规则将x 札文档的元 素映射成为对象数据库中的一系列对象。x m l 文档结构中的元素和属性被映射成 类或列，元素和属性的关系被映射为类和列之间的关系，元素问的关系则映射为 类问的关系。面向对象的存储方法支持复杂数据类型，可以较为直观地建立x m i 数据的对象模式，从而可以利用对象查询语言( 0 q l ) 实现对x m l 数据的结构化查 询，具有较高的存储与查询效率。 1 3 4 原生) n 也数据库 删l 数据库是可以对) ( l l 文档进行存取管理和查询的数据库，一个x m l 数据库 是) 【 i l 文档及其部件的集合，并通过一个具有能力管理和控制这个文档集合本身 及其所表示信息的系统来维护。和其它数据库一样，它也应该支持事务管理、安 全、多用户访问、编程a p i 和查询语言等。 列l 数据库系统分为两类：支持x i 也的数据库( x l l e n a b l e dd a t a b a s e ，x e d ) 和原生) ( i i l 数据库( n a t i v ex 札d a t a b a s e ，n x d ) 。x e d 是在传统数据库的基础上 增加对x i l l 的支持，以便保存和输出瑚l 形式的文档，通过适当的x m la p i 对x m l 文档进行查询和修改，即前述( 2 ) 、( 3 ) 两种情况可以划归这一类而n x d 则是专 门设计用于存储和管理x i j l 文档的数据库，它直接以捌l 文档作为数据库的存储 单元进行操作和管理 4 浙江大学硕士学位论文第l 章绪论 1 3 5 ) 明。存储的存储小结 对煳l 各种存储方法的比较： 表1 - 1 ) m 也数据库存储策略比较 存储方法存储方式性能比较主要缺点 文件系统a s c i i 文本文件 易管理、易存储、适用访问和更新困难 于) ( m l 数据文档较小时 关系数据库表可扩展性、可靠性、强简单的查询也需 大的安全机制及易实要多重链接来实 现现 0 0 o r 数据库 表和对象 易实现、支持抽象数据】( m l 文档分解困 类型难，无法映射。没 有d t d 或s c h e m a 的 x m l 文档 n a t i v e 捌l 数特殊抽象数据模型具有灵活性，又很高的和商业数据库相 据库或典型数据库模型访问和查询速度比还不够成熟 浙江大学硕士学位论文 第l 章绪论 1 4 本文组织 本文组织如下： 第一章为绪论，对) 也发展历史，国内外研究的背景以及研究的目的和意 义做了简要的阐述，简要说明) 姒l 原型数据库系统中基于锁机制的并发控制技 术的研究理论和现实意义以及一些有关) 0 咀。的基础知识。即说明为什么要研究 该课题，以及本文的研究角度，研究内容和研究框架。 第二章到第五章为具体研究，说明本文研究课题的理论技术背景，新理论模 型和算法的提出、证明、实现以及验证结果。 第二章为传统并发控制理论技术综述；第三章为现有的订l 并发控制理论 的介绍，第二章和第三章的知识为第四章基于动态变化的并发控制协议理论模型 和算法的提出作了良好的铺垫。 第四章提出了本文的理论模型基于动态变化的并发控制协议模型和算法，并 从理论角度验证了模型和算法的正确性以及有效性。本章是本论文研究的核心内 容。 第五章为用实验对模型和算法的验证，为此做了原型系统，用大量数据事实 定量地给出本文提出模型和算法的有效性。 最后第六章本论文的研究进行总结，并指出本论文研究的不足和未来可能的 研究方向。 针对上述的主要研究内容，本文的组织结构如下图1 1 所示： 6 浙江大学硕士学位论文第l 章绪论 图1 1 本文组织结构框架图 7 浙江大学硕士学位论文第2 章传统并发拧制理论 第2 章传统并发控制理论 2 1 事务 事务( 仃a i l s a c t i o n ) 是构成整个单一逻辑工作单元的操作集合。不论有无故障， 数据库系统必须保证事务的正确执行执行事务或者属于该事务的操作一个 也不执行。此外，数据库系统必须以一种能避免引入不一致性的方式来管理事务 的并发执行。 事务是访问并可能更新各种数据项的一个程序执行单元。事务通常由高级数 据操纵语言或编程语言( 如s q l c o b o l 、c 、c + + 或j a v a ) 书写用户程序的执 行所引起，并用行如b e g i i lt r a n s a c t i 伽和e n d 仃a n s a t i o n 的语句( 或函数调用) 来 界定。事务由事务开始( b e 百n 仃a l l s 孔t i o n ) 与事务结束( e n d 蜘1 s a c t i o n ) 之间执 行的全体操作组成。为了保证数据完整性，事务具有以下特性： 原子性：事务的所有操作在数据库中要么全部正确反映出来要么全部不 反映。 一致性：事务隔离执行时( 即在没有其他事务并发执行的情况下) 保持 数据库的一致性。 隔离性：尽管多个事务可以完全并发执行，但系统保证，对于任何一对 事务。a 和b ，在a 看来，b 或者在a 开始之前已经停止执行，或者在 a 完成之后开始执行。这样每个事务都感觉不倒系统中有其他事务在并 发地执行。 持久性：一个事务成功完成后，它对数据库地改变必须是永久地，即使 是系统出现故障时也是如此。 下面时数据库系统事务并发执行地简单示意图： 浙江大学硕士学位论文第2 章传统并发控制理论 图2 1 数据库中事务并发执行模型示意图 数 据 服 务 嚣 2 2 加锁机制 一个事务所操作的数据库表资源往往有多个，而事务的原则性要求组成事务 的所有操作要么全做，要么全不做，只有这样才能有效地保证数据库操作结果的 正确性，使得数据库由先前的一致状态转化为一种新的一致状态。为此必须在该 事务的所有操作进行之前申请到这些数据库表的锁，即对这些表加锁。在事务的 增长阶段( 申请封锁阶段) ，要对本事务所操作的所有数据表依次进行加锁，如果 加锁成功则表明抢占资源成功，继续进行该事务对这些表数据的操作，直到所有 操作完成后提交数据库，以进入缩减阶段( 释放封锁阶段) 。如果对该进程所操 作的表序列进行加锁过程中出现某个表加锁失败的情况，则表明该表数据资源正 在被其他进程占用，那么本进程对其申请的表数据资源的此次抢占宣告失败，此 时就会出现锁等待，甚至是死锁现象。 9 浙江大学硕士学位论文第2 章传统并发控制理论 2 2 1 夭折事务算法 夭折事务法是一种传统的处理锁等待和预防死锁的方法。该方法的基本思想 是在出现锁等待时，就认为系统资源此时不可占用，从而夭折本事务( 进程) 。采 用这种方法的最大优点是能够最大程度的预防和避免死锁。但其缺点也是显而易 见的，因为夭折事务后到重新启动事务期间，系统等待了可能较长的时间从而很 大程度上降低了系统的执行效率，用户的满意度也会大大地降低。 2 2 2 连续申请资源法 连续申请资源法是另一种传统的处理锁等待的方法。该方法的基本思想是在 出现锁等待时并不夭折本事务，而是继续不问断地申请表数据资源的锁，直到申 请成功为止。很显然，在申请锁的过程中，如果该表资源一旦空闲，那么事务对 该表资源的锁申请会立即成功，本事务不会在系统资源空闲后出现任何等待，从 而大大地提高了系统的执行效率。但是，此时出现锁等待的原因如果是2 个进程 长时间抢占同一表数据资源，或者是两个进程在抢占对方已经占用的表数据资源 的状况，那么系统则可能进入了死锁状态。这也是连续申请资源法容易引起系统 死锁的缺点所在。 2 2 3 随机等待加锁法 很显然，夭折事务法和连续申请资源法都是在出现锁等待时采用了走极端的 处理机制。而随机等待加锁法对于这种申请锁失败的情况既没有继续无限制的申 请，也没有天折本进程，而是夭折了本次加锁过程。然后系统等待一个随机时间， 重新启动加锁过程。如果此次加锁过程仍然失败，继续夭折这次加锁过程再重 新开始加锁。如此这般循环一定的次数，以达到成功申请资源的目的。 在每次申请锁失败之后的随机等待时间里，被其他进程所占用的表数据资源 就可能已经被释放。这样就不会因夭折进程并重新启动进程而降低系统的执行效 率也不会出现因两个进程长时间抢占同一表数据资源或者是两个进程互相抢 占对方已经占用的表数据资源的死锁状态。 2 2 4 按标识排序加锁法 按标识符排序加锁法的基本思想是，对本进程所操作的所有数据对象先按照 1 0 浙江大学硕士学位论文第2 章传统并发控制理论 数据的标识符( 例如表加锁以表名作为标识符) 进行排序，然后再依次申请他们 的锁。正是由于按标识符排序的原因，使得排序靠前的表资源锁总是先被申请， 所以此方法的最大优点是能够较早发现锁等待的发生，从而很大程度上提高了系 统的执行效率。 2 2 5 加锁机制小结 以上所述加锁机制的总结如下表： 表2 1 四种加锁机制比较 加锁法加锁机制优点缺点 夭折事务法天折事务，重启事死锁几率低系统执行效率低 务 连续申请资源法不间断申请锁系统执行效率高易引起死锁 随机等待加锁法夭折本次加锁过系统执行效率高死锁几率低 程，等待一个随机 时间后重启加锁 过程 按标识符排序加按标识符排序后较早发现等待，系死锁几率低 锁法再申请加锁统执行效率高 新江大学硕士学位论文第2 章传统并发控制理论 2 3 并发控制基础理论 数据库系统是面向多用户的系统，事务并发可以提高系统的吞吐量，所以并 发控制在保证系统正确性的同时，并发机制的好坏也直接影响系统的性能，是 d b m s 的关键技术。 并发控制技术的实现通常依赖于底层的并发控制机制，一般我们称其为同步 机制。操作系统提供了多种同步对象，如事件e v e n t 、互斥锁m u t e x 和条件变量 c o n d 、信号量s e 腿p h o r e 、读写锁r w l o c k 、自旋锁s p i n l o c k 等。不同的数据库系 统采用了不同的同步对象，如p o s t g r e s q l 采用信号量，i n n o d b 采用事件或是互斥 锁。性能上这些同步对象都存在较大的差别，并适用于不同的场合。 并发控制机制( c o n c u r r 锄c y - c 叫昀ls c h e m c ) 是多个事务同时到来时，数据库系 统控制事务之间的相互影响，防止他们破坏数据库的一致性的所应用机制。传统 的并发控制协议可分为两大类，即单版本并发控制协议和多版本并发控制协议。 2 4 单版本并发控制协议 为保证调度的正确性，研究者提出了众多并发控制协议。其中的单版本并发 控制协议总体上可概括为两类：悲观类和乐观类。 悲观类协议是当检测到一个冲突时，就强迫事务等待或者回滚，即使该调度 有可能是冲突可串行化的，即在冲突操作可能导致不能串行化时就阻止操作进 行。主要代表有基于锁的协议、基于时间戳的协议和串行化图检测三种。 基于锁的协议可分为两阶段封锁协议和非两阶段封锁协议。其中最常用的是 两阶段封锁协议( t w o 巾h a s el o c k i i l gp r o t o c o l ，简称2 p l ) 。 两阶段封锁协议要求每个事务分两个阶段提出加锁和解锁申请：第一个阶段 为增长阶段，事务在这个阶段只能进行加锁操作，不能释放锁：在事务进行第一 个放锁操作后进入第二个阶段，即缩减阶段，事务在这个阶段只能释放锁，不能 获得新锁。2 p l 有很多变种，包括严格两阶段封锁协议( 耐c tt r o - p h 髂e1 0 d d n g p r o t o c 0 1 ，简称s 2 p l ，除了要求封锁是两阶段之外，还要求事务持有的所有排它 锁必须在事务提交后方可释放) 和强两阶段封锁协议( r i g o r o u s 帆o - p h 嬲e1 0 c k i n g p r o t o c o l ，简称s s 2 p l ，它要求事务提交之前不得释放任何锁) 。以上几种两阶段 1 2 浙江大学硕士学位论文第2 章传统并发控制理论 封锁协议都能保证事务的冲突可串行化。 非两阶段封锁协议中最主要的是树协议，认为“数据”之间存在虚拟的父子 关系，构成树形结构，同时要求事务在获得子节点的锁之前必须获得对父节点的 锁。最初的树协议是只考虑写操作的w r i t 1 yt r c ei 础i n g ( 即w t l ) 协议。后 来提出的r c 缸w n t et r l o c k j n g ( 即则盯l ) 协议是对w r l 协议的扩展，增加了 对读操作的支持。 基于时间戳的协议有时间戳排序协议( 石m e s t a r n p o m c r i n gp r o t o c o l ，简称 i o ) 。系统为每一个事务都设定一个时间戳( 通常是事务开始时一个全局计数器 的值) ，并为数据项分别记录读取和写入它的最大事务时间戳。通过这些机制， 系统可以检测出读写操作是否按事务的时间戳顺序发生，如果不是，则调度器拒 绝执行将要进行的操作。如果事务被并发控制机制回滚，则系统赋予它新的时间 戳并重新启动。时间戳排序协议同样也能保证事务的冲突可串行化。 串行化图检测协议( s e r i a 硅z a t i o n g r a p h t c s t i n g ，简称s g t ) 维护事务之间 的冲突图，并保证图中不包含环。理论上可产生所有的冲突可串行化调度( 2 p l 、 w t l 和1 d 都不能产生所有的冲突可串行化调度) ，但却难以实现，因为事务提 交时也不可马上将其从冲突图中移走。 乐观类协议将事务执行分为三个阶段。在读阶段执行事务包含的操作，但将 写操作的结果放在事务的私有工作空间内；第二个阶段为有效性确认阶段，验证 调度是否冲突可串行；通过验证的事务进行第三个阶段即写阶段，将私有工作空 间内的写结果发布到数据库中。 乐观类协议中常见的有b a c k w a r d 耐c n t e do p t i i i l i s 6 cc c ( b o c c ) 协议和 f o 研a r d 耐e n t e d0 p t i l l l i s t i cc c ( f o c c ) 协议，主要是有效性确认的方法不同， b o c c 协议中进行有效性确认的事务执行与所有已提交事务的冲突检测，f o c c 协议中进行有效性确认的事务执行与所有处于读阶段的事务进行冲突检测。 2 5 多版本并发控制协议 多版本并发控制( 砌l t i v e r s i o nc 蝴c yc o n 舡d 1 ) 技术假设数据项存在多个 版本，每个写操作产生一个新版本。当事务发出一个读操作时，则并发控制管理 器根据一定的规则选择一个版本读取其内容。由于读操作有了更多的选择，多版 本并发控制协议通常能获得更好的并发度。常用的多版本并发控制协议主要有多 浙江大学硕士学位论文第2 章传统并发控制理论 版本时间戳排序协议、多版本两阶段封锁协议、多版本串行化图检测协议和多版 本只读协议。 多版本两阶段封锁协议( m v 2 p l ) 将版本分为三类，提交版本为已提交事务 创建的版本；当前版本为最新的提交版本；未提交版本为当前活动事务创建的版 本。对读操作，m v 2 p l 为其指定一个当前版本或未提交版本；对写操作，只有 没有其它事务创建的未提交版本时才被允许。在事务提交时，m v 2 p l 需要等待 所有已经读取当前事务写过的数据项的当前版本的事务( 因为这些事务读取的是 以前的版本) 及所有当前事务读取的版本的创建者提交后( 防止脏读) 才提交当 前事务。 多版本时间戳排序协议( m v t d ) 的基本思想是通过调度使事务并发执行 的结果与事务按其开始时间戳大小顺序的结果等价。每个事务都有一个时间戳， 每个版本也带有一个时间戳，与创建该版本的事务的时间戳相同。对于读操作， m 、，t o 调度器为其指定一个先前的版本。对于写操作，调度器检查系统某些时间 戳大于当前事务的事务是否已经读取了时间戳小于当前事务的版本，若是，则拒 绝这一写操作并回退事务( 因为这些事务本应读取当前事务写操作产生的版本) ， 否则产生一个新版本。在事务提交时，为防止级联回滚，要求事务等待所有它读 取过的版本的创建者提交之后才能提交。 多版本串行化图( m v s g t ) 是单版本串行化图检测协议( s g t ) 在多版本系 统中的扩展，保证多版本冲突图无环。 只读事务的多版本协议( r ( ) m v ) 区分事务为只读事务和更新事务。对只读 事务，在执行时遵从m v l o 协议，事务被指定一个时间戳，调度器为其读操作 始终指定数据项中小于当前事务时间戳的最新版本；对更新事务，则使用强两阶 段封锁协议，因此，它们可以按提交的次序进行串行化。只读事务多版本协议保 证只读事务与更新事务不相互阻塞，且协议本身实现简单，在o m c l e 等实际的数 据库中得到广泛应用。 版本删除类似于多版本时间戳排序中采用的方式。假设某数据项的两个版本 的时间戳都小于系统中最老的只读事务的时间错，则两个版本中较旧那个版本的 将会被删除。 4 浙江大学硕士学位论文第2 章传统并发控制理论 2 6 传统并发控制协议在数据库中的应用 基于锁机制的并发控制协议在实现时常用的技术有多粒度锁机制。它是由 j i mg 姐y 等提出的，目的是减少加锁的时间和空间开销。这一技术的基础是意向 锁，要求当事务想加细粒度锁时，需要先在粗粒度上加意向锁。意向锁标识了一 条粒度层次结构的路径，通向真正被加上共享或排它锁的数据项。这样其它事务 就可以很容易的进行冲突检测。 使用多粒度锁协议，事务开始时加细粒度的锁，当事务拥有的细粒度锁数量 超过一定阈值时，升格( 1 0 c k 鼯c a l 撕o n ) 到粗粒度锁。 实现时如果要严格保证可串行性，则对系统的性能影响较大。实际的关系数 据库通常都支持低于可串行性的隔离级别。s q l 标准中定义了四种隔离级别： 读未提交、读已提交、可重复读和可串行化，这些隔离级别通过对两阶段加锁协 议进行简单的修改就可得到。另一个常用的隔离级别是基于多版本的快照隔离， 要求事务读取到最近版本且并发的更新事务写集合无交集。 关系数据库产品中使用的并发控制协议主要有二阶段封锁协议和多版本协 议。 商业数据库中s q ls e r v e r 与d b 2 使用基于二阶段封锁的协议。s q ls e n ，盯 支持多种锁粒度，包含数据库级、表级、页级以及记录级的锁。为减少加锁的开 销，系统根据隔离级别、扫描方式、选择率等条件在操作执行前确定合适的加锁 粒度，同时也支持锁升格。d b 2 支持表级锁和记录级锁。 基于多版本的并发控制技术在关系数据库系统中也得到了广泛应用。商业数 据库中使用此类协议的有0 r a c l e 和s q ls e r v 盱2 0 0 5 版本。0 r a c l e 中的协议类似 于r o m v ，其中时间戳被称为s c n ( s y s t 锄c h 锄g en m b 日) 。s q ls e n ，e r2 0 0 5 中的多版本并发控制技术实现了快照隔离。开源数据库中使用多版本技术的也有 不少，包括p o s t g r e s q l 、m y s q l ( 特指h d b 存储引擎) 、f i r e b i r d ，可以说， 基于多版本的并发控制技术在关系数据库的应用是相当成功的。 浙江大学硕士学位论文第2 章传统并发控制理论 2 7 本章小结 由前两节的介绍可以看到，传统的并发控制协议可分为两大类，即单版本并 发控制协议和多版本并发控制协议。传统的并发控制协议结构如2 2 图所示： 图2 - 2 传统并发控制理论结构 1 6 浙江大学硕士学位论文第3 章x m l 并发控制理论 第3 章) n 几并发控制理论 3 1 ) 强也并发控制理论基础 并发控制是改善数据库系统事务性能最重要的机制，它允许多个事务并发执 行并保证事务的隔离性( i s 0 1 a t i o n ) 和可串行性( s e r i a l i z a b i l i t y ) 。在传统的数 据库管理系统领域，已经广泛地研究了多种并发控制机制以确保并发调度的可 串行化，其中，两阶段锁协议( 2 p l ) 是商业传统数据库广泛采用的一种锁机制在 ) 【m l 成为互连网标准语言之后，研究x m l 数据库并发控制的课题也随之产生 一种普遍的思想是将) ( m l 文档映射到传统的数据库，利用传统数据库完善的 事务机制保证) ( i l l 的多用户并发访问控制。然而，过去的研究表明，这种思想在 多数情况下并不能真正实现多个用户对单个文档的并发访问控制。另一方面，在 x 儿原型数据库( n a t i v ex m ld a t a b a s e s ) 领域，并发控制机制的研究才刚刚开始。 目前正在研究的x m l 并发控制技术有：基于锁机制的并发控制协议、基于 时间戳的并发控制协议、基于有效性检查的并发控制协议、多版本并发控制协议 和多粒度并发控制协议。 对订l 文档中的数据进行加锁控制是现有的v i l 并发控制协议中最广泛采 用的技术之一。目前，这类基于锁机制的并发控制协议己被提出的有十余种，可 分为基于实例加锁的订l 并发控制技术和基于路径索引的x m l 并发控制技术两 大类。 3 2 基于实例加锁的并发控制技术 基于实例加锁的讧l 并发控制技术根据其面向应用的不同可分为两类： 第一类协议面向d o m 应用的，一般使用共享锁、排它锁等简单的锁类型； 第二类协议是面向x p a 也访问的，在锁对象中包含复杂的路径和谓词条件。 3 2 1 面向d 删的协议 第一类协议最早的是s h e l l n 盱等人提出的基于d o m 树的n o d e 2 p l 、 n 0 2 p l 和0 0 2 p l 三种协议。n o d e 2 p l 是传统并发控制技术中的2 p l 协议的简 1 7 浙江大学硕士学位论文第3 章) 口札并发控制理论 单移植，该协议要求对事务访问的节点的父节点加共享锁，对修改的节点的父节 点加排它锁( 对父节点加锁而非对节点本身加锁是为了防止幻像) 。n 0 2 p l 对操 作涉及的边所在的节点加锁，如插入一个最左的子节点需要对其父节点和原最左 子节点加锁，因为这一操作修改了父节点指向第一个子节点的指针及原最左子节 点的指向左兄弟的指针。0 0 2 p l 则是对访问或修改的指针本身加锁，包含指向 第一个子节点、最后一个子节点、左右兄弟等四种指针类型，每个类型又有共享 和排它两种模式，因此在0 0 2 p l 中总共有8 种锁模式。n d d e 2 p l 、n 0 2 p l 和 0 0 2 p l 三种协议本质上是传统数据库并发控制中的2 p l 协议在x m l 数据库的 应用。 n o d c 2 p l 系列协议使用特殊的锁机制来处理d 砌弧跳转问题，要求在这种 情况下需要锁住所有可跳转到这一节点的节点，同时删除一棵子树的时候也要搜 索整个子树，锁住所有拥有d 属性的节点防止其它事务跳转到一个被删除的子 树中去。这两个缺陷使得d c 2 p l 系列协议很难有效应用于实际的系统。 文献l i 班咐e i g h tm u l t i 鲫u l 撕t yl o c l 【i i l gf b r 仃a n 鼢c t i 蚴删眦l g c m e n ti n 讧l d 北l b 嬲es y s t e i i l s 中提出使用对跳转( 或通过索引访问) 目标节点的所有祖先节点 加意向锁解决这一问题。 为高效实现对一个节点所有祖先节点的加锁，需要采用一种支持根据子节点 的d 快速计算出其父节点的d 的x m l 节点编码算法。目前研究者提出了多 种编码机制，如d 洲e y d 、s q l s e e r 中的o r d p 删节点编码，支持这一需求。 根据这些编码方式，实现对祖先节点加意向锁这一过程可以不需要访问物理数 据。目前这一技术是讧l 并发控制协议中的标准方法。 n o d e 2 p l 系统协议虽然是面向d o m 应用提出的，却是相对通用的协议，然 而正因为通用，其并发度并不理想，其中主要的原因是这些协议都忽略了讧l 数 据和对讧l 数据所进行的操作所具有的特点。m p h a u s t e i n 等研究者提出的 t a d o m 系列协议针对d o m 操作的并发控制进行了更多的优化。t a d o m 系列协 议包括t a