（计算机应用技术专业论文）本地封闭世界假设下数据分布策略的研究.pdf

大连理工大学硕士学位论文 摘要 事务是由一组数据库操作序列组成的，具有a c i d 特性。然而，在大规模分布式应 用环境下，传统的事务模型是不适用的。在考虑系统性能的情况下，并不总是采用完全 的隔离性级别，即可串行化调度。分布式数据库系统是在集中式数据库系统的基础上发 展起来的，是数据库技术与网络技术结合的产物。在分布式数据库中，很重要的一点是 数据的分段和分配。关系数据库可以看作是由每个元组以及外键参照关系构成的有向 图。为了方便数据的复制以及共享，在进行数据分段时，尽量把语义上相关的数据分在 一起，并且使分在一起的数据逻辑上尽量独立。 封闭世界假设是一种假设，该假设认为当前未知的事物都为假。本文基于本地封闭 世界假设( l o c a lc l o s e dw o r l da s s u m p t i o n ) ，结合数据复制技术，提出了一种适用于分 布式数据库的分布式事务模型，该模型将本地的数据分成可控制数据和引用数据，进而 阐述了该事务模型的特点、并发控制的策略，给出了该事务模型的正确性证明，并用一 个简化的教学管理系统说明该事务模型。 数据分布包括数据分段和数据分配。本文在本地封闭世界假设事务模型下，提出了 一种基于多根树的、与数据库模式无关的数据分段的方法。用这种数据分段方法，以一 个控制节点作为中心，提取出与其语义相关的子多根树代替传统分布式数据库的水平分 段与垂直分段。本文将多根树之间的联系作为数据分段的语义，将多根树作为逻辑独立 的数据集，给出了数据分段的方法，并在o r a c l e 数据库中，使用t p c c 的数据库结构 对该方法进行测试与分析，从而验证该算法的有效性和通用性。在数据分段完成之后， 需要再对数据进行分配，也就是将已分段的数据如何分配到各个站点。本文采用得益与 估量的方法对数据进行分配。 最后简要介绍了云计算，并用开源工具搭建一个云平台。 关键词：本地封闭世界假设；事务模型；多根树；数据分段；云计算 本地封闭世界假设下数据分布策略的研究 t h er e s e a r c ho f f r a g m e n ta n d d i s t r i b u t i o ns t r a t e g i e sb a s e do nl c w a a b s t r a c t a 仃趾1 s a c t i o nc o n s i s t so fas e r i a lo fo p e r a t i o n s ，a n dh a sa c i dp r o p e r t i e s h o w e v e r , i n l a r g e - s c a l ed i s t r i b u t e da p p l i c a t i o n s ，t h et r a d i t i o n a lt r a n s a c t i o nm o d e li sn o ta p p l i c a b l e w 曲a c e n t r a l i z e dd a t a b a s es y s t e md e v e l o p i n g ，d i s t r i b u t e dd a t a b a s es y s t e mh a sb e e nd e v e l o p i n g ，a n d i ti st h ep r o d u c to fd a t a b a s et e c h n o l o g ya n dn e t w o r kt e c h n o l o g y 1 1 1 ef r a g m e n ta n dd i s t r i b u t i o n o fd a t ai nt h ed i s t r i b u t e dd a t a b a s ea r ev e r yi m p o r t a n t ar e l a t i o n a ld a t a b a s ec a l lb ev i e w e da sa d i r e c t e dg r a p hc o n s t r u c t e db yt u p l e sa n df o r e i g nk e yr e f e r e n c e s at r a n s a c t i o nm o d e lb a s e do nl o c a lc l o s e dw o r l d a s s u m p t i o n ，t h em o d e ld i v i d et h ed a t a i nt h el o c a li n t ot h ec o n t r o l l e dd a t aa n dt h er e f e r e n c e dd a t a , a sw e l la sd a t ar e p l i c a t i o n ，i s p r o p o s e d i t sf e a t u r e s ，c o n c u r r e n c yc o n t r o la n dc o r r e c t n e s sa r ea l s oi n v e s t i g a t e da n d d e m o n s t r a t e d t 1 1 i st r a n s a c t i o nm o d e li si l l u s t r a t e dw i t ha t e a c h i n gm a n a g e m e n ts y s t e m ，n l i sp 印e rp r o p o s e sam e t h o do fd a t ae x t r a c t i o nb a s e do nm u l t i - r o o tt r e e ，i n s t e a do f t r a d i t i o n a lh o r i z o n t a lf r a g m e n ta n dv e r t i c a lf r a g m e n to fd a t a t h em e t h o do fd a t ae x t r a c t i o n p r o p o s e db yt h i sp a p e ri sd i f f e r e n tf r o md a t ae x t r a c t i o na tt h ep r e s e n ts t a g e t of a c i l i t a t ed a t a r e p l i c a t i o na n ds h a r i n g ，s e m a n t i c - r e l a t i v i t ya n dl o g i c a l l yi n d e p e n d e n c es h o u l db es a t i s f i e d w h e nr e l a t i o n a ld a t ai se x t r a c t e d m u l t i - t r e es t r u c t u r e sa r ee m p l o y e da sc l u s t e r so fs u c hd a t a e x t r a c t e df r o mar e l a t i o n a ld a t a b a s ei nt h i sp a p e r t h e nt h ec o r r e s p o n d i n gd a t ae x t r a c t i o n a p p r o a c hi sp r o p o s e da n di m p l e m e n t e d w ee v a l u a t et h ee x t r a c t i o na l g o r i t h mo nat p c - c d a t a b a s ei no r a c l e ，d e m o n s t r a t i n gt h ee f f e c t i v e n e s sa n dg e n e r a l i z a t i o no ft h ea p p r o a c h a f t e r t h ed a t ae x t r a c t i o n , t h ed a t am u s tb ea s s i g n e dt os i t e ss u i t a b l y t i l i sp a p e ri n t r o d u c e sam e t h o d o fb e n e f i ta n de s t i m a t i o nf o ra s s i g n i n gd a t a f i n a l l y ，t h ep a p e ri n t r o d u c e st h ef r a m eo fac l o u dp l a t f o r ma n ds e tu pi t 、) l ，i 也t h eo p e n s o u r c et o o l s k e yw o r d s ：l c w a ；t r a n s a c t i o nm o d e t ；m u t t i - r o o t st r e e ；f r a g m e n t s ；c t o u d c o m p u t i n g i l - 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：至幽兰望! ! 圣垒至亟堑羔臣经鲎暨兰丑缸 作者签名- 一盐鱼虫丛 日期：互旦互一年堡月军日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 大连理工大学硕士学位论文 1 绪论 1 1 研究背景 传统事务是由一组数据库操作序列组成，具有包括隔离性在内的a c i d 特性。然而， 在考虑系统性能的情况下，并不总是采用完全的隔离级别。传统数据库技术都是基于封 闭世界假设( c w a ) 的，但在大规模的分布式数据库环境下，这种假设是不适用的。 一个分布式系统由若干个地理上分散的站点组成，要想让这些站点都同时正常工 作，并且网络不出现任何故障是不现实的。因此，完全了解、控制整个分布式数据库状 态的是非常困难的，即使实现了，也大大降低了系统的可用性。另外，分布式数据库系 统越来越大，越来越开放，确定系统的边界也越来越难。可见，在这种情况下，封闭世 界假设就不适用了。但是在一定范围内，比如在当前站点的本地数据库中，仍然与封闭 世界假设一样，完全控制本地数据库中的数据。也就是说，封闭世界假设在一定的范围 内仍然成立。 在分布式数据库中，在不同的应用条件下，数据有不同的分段和分配的方法。如何 对数据进行更好的分段和分配是急需解决的问题。传统的分布式数据库用水平分段、垂 直分段、导出式分段对数据进行分段，采用诸如最佳适应法等方法对数据进行分配。数 据提取技术在信息处理领域有着重要的作用，系统经常遇到数据提取、复制、共享的问 题。数据提取是数据复制的前提，提取后的数据可以加载到数据仓库中、可以作为交换 的数据给其他的系统共享、也可以作为分段的单位。目前数据提取技术研究的热点大多 都是非结构化、半结构化的w e b 数据提取。结构化数据提取工具主要是各大厂商的e t l 工具，提取时还要进行转换、加载。很多应用系统也有数据提取的功能，但是大都与数 据库的设计有关，在不同的应用间不通用。本文为结构化数据提供一种基于多根树的、 与模式无关的数据提取方法，并用该方法代替传统分布式数据库中的数据分段方法。 1 2 国内外研究现状 传统的事务是由一个平坦数据库操作序列组成的。然而，在有些大规模分布式、实 时应用环境下，却不太适用。对此，研究人员提出了不同于传统事务的其他事务模型， 以便适用于其他领域。文献【l 】提出了一种支持实时应用的嵌套事务模型：文献【2 j 根据传 感器网络中实时数据库应用的协作特性，放松事务的严格a c i d 要求，运用控制区域的 概念提出一种基于事务的行为语义控制区域的事务模型；移动a g e n t 机制具有自治性、 本地交互性、移动性等优点，十分适合于建立大规模复杂的分布式事务模型。文献1 3 j 针 对a g e n t 不仅可以移动到远程站点，与远程站点上的数据库进行本地交互，而且还可以 本地封闭世界假设下数据分布策略的研究 自主地决定对事务的处理的特点，提出了能保证事务的a c i d 特性的、基于移动a g e n t 的分布式事务模型。 由于传统的并发控制协议如2 p l 、多粒度封锁、乐观的并发控制机制、时间戳排序、 多版本并发机制等，这些方法都在一定程度上存在死锁、夭折率高等弊端。肖迎元、刘 云生提出了确保时态一致性的实时并发控制协议【4 】：韩启龙、郝忠孝提出了基于数据时 态特性的实时事务并发控制1 5 j 。 随着网络技术的日趋成熟，传统的集中式数据库系统越来越不能满足人们处理数据 的要求，因此分布式数据库系统应运而生，并且得到迅速发展。然而在大型分布式数据 库中想要让事务真正实现全局串行化，几乎是不可能的。甚至连现阶段流行的o r a c l e 、 s q l s e r v e r 等大型关系数据库在事务执行时都没有采用严格的串行化标准。文献1 6 7 j 提出 事务应用程序在比串行化更低的隔离性级别上执行是为了提高吞吐率和减少响应时间。 调度的结果可能不是串行化的，因此，也不一定是正确的。应用程序的语义决定应用程 序是否能在更低的隔离性级别上运行。这个问题常常以非形式化的形式讨论。文献【6 7 j 提出一种比串行化更低的语义正确性标准来研究正确性。在a n s i i s o 的基础上，增加 了“先提交先赢 和“快照 隔离性级别【_ 7 1 。封闭世界假设是一种假设当前未知的 事物都为假。沈一栋在该假设下判定数据库的一致性【8 】。马学强、施伯乐对“封闭世晃 假设从新的角度进行了解释，据此提出了知识库系统模型，并给出了一种通用失败求 反规则( g n a f ) 和一个多项式时间的知识库设计的递归算法 9 1 。 数据提取技术在信息处理领域有着重要的作用，不论是系统之间还是内部子系统之 间都会经常碰到数据提取、复制、共享的问题。目前数据提取技术研究的热点是非结构 化、半结构化的w e b 数据的提取【1 m 1 2 1 。结构化数据提取工具主要是各大厂商的e t l t l 3 】 工具，这些工具大都侧重单表提取，提取时还要进行转换、加载。很多应用系统内也有 数据提取功能，但大都与数据库模式有关，在不同的应用间不通用。传统的分布式数据 库都用水平分段、垂直分段、导出式分段对数据进行分段，采用得益与估量的方法对数 据进行分配。 关于云计算技术上的研究主要包括两个方面，一个是如何构建分布式平台的基础设 施，另一个是如何帮助开发人员在云计算的分布式平台上进行编程。 在分布式平台的基础设施研究上，主要包括微软的d r y a d 框架、a m a z o n 公司的 d y n a m o 框架、c o m 公司的n e p t u n e 框架。微软公司为了方便应用程序开发人员进行分 布式程序的开发，提供了一个平台d r y a d m 】，以支持有向无环图类型数据流的并行程序。 d r y a d 是一个一般化的框架，能够支持m a p r e d u c e 类型的应用程序以及关系代数的一些 操作。d r y a d 的整体框架则根据程序的要求完成调度工作，自动完成任务在各个节点上 大连理工大学硕士学位论文 的运行。a m a z o n 公司的研究人员研究了如何通过集群的技术快速存取大量的键值，数 据对的问题，即k e y ，v a l u e 对，并建立d y n a m o 1 s l 系统来维护这些信息。由于a m a z o n 公司的特殊性，其公司内部的应用程序在很多情况下需要处理键值，数据对，并且需要 扩展到大规模集群上。在对于读写控制方面，传统的读写处理方式是尽量简化读的操作， 而将复杂性放在写操作上，d y n a m o 系统则将复杂性放在读的方面，将整个系统设计成 总是可以写入的，以提高网络用户购物的体验。d y n a m o 主要使用结构化的p 2 p 结构一 致性哈希算法来对数据进行划分与存储，使用向量时钟的方式帮助完成数据读取，并采 用哈希树与g o s s i p 协议等一些手段对错误进行处理。应用于a s k 。e o m 的n e p t t m e 1 6 j 技 术则针对大量数据进行归并。总体框架首先将数据分布到大规模集群网络上，每一个网 络中的节点只需保存一部分数据即可。而后每一个节点在数据上做相应的操作，将操作 输出的中间结果进行归并操作即可获得最终的结果。这种归并方式在网络数据处理的应 用上非常广泛【1 7 j 。 1 3 本文的工作 为了方便d b a 对分布式数据库系统级的管理，本文将本地封闭世界假设引入到数 据库事务处理模型中，提出基于本地封闭世界假设的事务模型，该模型将本地数据分为 可控制数据和引用数据，并给出这种事务模型的特性及正确性证明。对该事务模型的并 发控制协议进行了讨论，用一个简化的教学管理例子说明，并指出该模型的局限性。 分布式数据库很重要的一点是关系的分段和分配，那么在该事务模型下，本文提出 了一种基于多根树的、与数据库模式无关的数据分段方法。此方法提取的结果是一棵子 多根树，用这种子多根树作为一个单元，代替传统的水平分段、垂直分段与导出式分段。 本文在该模型基础上将数据库的模式图、数据图看成多根树，以便利用多根树的思想实 现基于多根树的数据提取，进而进行数据分段，在满足语义完整性、参照完整性的基础 上，实现了该提取算法，并验证了该算法的有效性，进而将提取出的子多根树作为一个 数据分配的单元，进行数据分配，本文以对数据的检索和更新次数为主要依据，采用费 用和待益的估量来分配数据。 最后将上述的算法在自己搭建的云平台上做试验，但是由于时间关系，只将上述内 容在w i n d o w s 平台下实现，如何在云平台上进行试验，有待进一步研究。 1 4 本文的组织 本文共分五章，主要介绍了事务模型、事务的并发控制算法，提出了基于本地封闭 世界假设的事务模型；介绍了数据提取的概念，并以多根树为语义，实现了通用的基于 本地封闭世界假设下数据分布策略的研究 多根树的数据分段算法，并在此基础上进行数据的分配；最后，介绍了云计算的相关概 念，并利用相关的开源工具，搭建了一个云平台。 第一章绪论部分阐述了传统事务的局限性，介绍了不同于传统事务、应用于其他领 域的事务模型，以及一些新的并发控制算法；还介绍了基于多根树的数据提取和云计算 的研究现状。 第二章介绍了传统事务的概念、基于页模型下事务并发控制的三个经典问题，并针 对这些问题阐述了隔离型级别：还介绍了并发控制算法，其中详细介绍了两段锁协议、 顺序检测图和多版本并发控制的方法。 第三章介绍了本文的重点工作之一，提出了基于本地封闭世界假设的事务模型。给 出了该事务模型的定义、并在该模型下提出相应的并发控制算法，最后举一个简单的教 学关系系统的例子说明该模型。 第四章也是本文的重点工作之一，在本地封闭世界假设下，实现了基于多根树的、 与数据模式无关的数据分段算法，在分段之后，将其作为一个单元，利用最佳适应法进 行分配，并与传统的分配方法进行理论上的比较分析。 第五章介绍了一个较为时髦的云计算，简单阐述云计算的相关概念及其优缺点，最 后将第四章的算法在自己搭建的云平台上做实验，但是由于时间关系，并未将三、四章 所提出算法在上面实现，有待进一步研究。 大连理工大学硕士学位论文 2 数据库并发控制 同时处理不同用户提交的任务是现代数据库系统一个很主要的需求。并发控制算法 的主要目的就是寻找一个可以同步、正确、有效的处理共享数据资源的方法。近二十年， 研究人员探讨了数据库并发控制算法的标准和效率。本章节回顾数据库系统中并发控制 的相关概念及并发控制算法。 2 1事务 事务是访问并可以更新各种数据项的一个程序执行单元。事务通常由高级数据操纵 语言或编程语言( 如s q l 、c o b o l 、c 、c + + 或者j a v a ) 书写的用户程序的执行所引 起，并用形如b e g i nt r a n s a c t i o n 和e n dt r a n s a c t i o n 的语句来界定。事务由事务开始与事务 结束之间执行的全体操作组成。 为了保证数据完整性，要求数据库系统维持以下四个事务性质( a c i d 特性) ： ( 1 ) 原子性( a t o m i c i t y ) ：事务是数据库的逻辑工作单位，事务的所有操作在数 据库中要么全部正确反映出来，要么全部都不反映。 ( 2 ) 一致性( c o n s i s t e n c y ) ：事务隔离执行时( 即在没有其他事务并发执行的情 况下) 保持数据库的一致性。事务执行的结果必须是使数据库从一个一致性状态变到另 一个一致性状态。 ( 3 ) 隔离性( i s o l a t i o n ) ：尽管多个事务可以并发执行，但是系统保证，对于任 何一对事务t i 和t i ，在t i 看来，t j 或者在t i 开始之前已经停止执行，或者在t i 完成之 后开始执行。这样，每个事务都感觉不到系统中有其他事务在并发的执行。 ( 4 ) 持久性( d u r a b i l i t y ) ：一个事务成功完成后，它对数据库的改变是永久的， 接下来的其他操作或者故障不应该对其执行结果有任何影响。 总而言之，一个事务的执行是一个读、写操作组成的序列，并且它以c o m m i t 或者 a b o r t 结束。a c i d 特性保证了数据库系统的安全性和一致性。 2 2 并发事务的隔离性 2 2 1 典型的并发控制问题 由于事务并发执行，有些数据可能会被不同事务的某些操作访问。如果两个事务， 访问同一数据项，至少有一个是写操作，就说这两个操作彼此冲突。如果没有合适的并 发控制，那么冲突的操作就会破坏事务的a c i d 特性。本段介绍五个典型的现象来说明 并发控制问题。 本地封闭世界假设下数据分布策略的研究 ( 1 ) 读脏数据 t l ：w ( 功 a b o r t t 2 ：r 0 0w ) c o m m i t x 是一个银行账户，z 是非负数并且此刻值为1 0 0 ，假设a 和b 都有访问账户z 的 权限。在同一时刻，a 发起事务t l ，b 发起事务t 2 ，首先a 存入1 0 0 元到x 中，此时z 应为2 0 0 元。然后b 试图取出2 0 0 元，在此之前，系统必须检查账户余额是否大于等于 2 0 0 ，因为没有并发控制，b 取出2 0 0 元，t 2 提交。之后a 撤销了t l ，结果x 变为负数。 “读脏数据 现象就是一个事务读取了另一个事务写的但是还未提交的数据。其发 生是由于对数据项的读操作没有合适的并发控制方法，通过撤消操作，未提交的对数据 项的修改被放弃了，数据库的一致性被破坏了，从而导致“读脏数据”现象的发生。 ( 2 ) 丢失修改 t 1 ：r 0 )w 0 0 c o m m i t t 2 ：r w c o m m i t x 是一个银行账户，初始值为1 0 0 。x 能够被a 和b 同时访问。在同一时刻，a 发 起事务t i ，b 发起事务t 2 ，t 2 读出x ，并且取出1 0 0 元，此时x 为0 ，t 1 读出石，并存 入1 0 0 元，提交后变为2 0 0 元。由于没有并发控制，银行损失了1 0 0 元。 “丢失修改 现象就是一个事务的对同一数据项的修改覆盖了另一个事务对该数据 项的修改，导致第一个修改丢失了。 ( 3 ) 不可重复读 不可重复读是指事务t l 读取一条数据后，事务t 2 执行更新操作，无法再现前一次 的结果。具体的说，不可重复读包括两种情况：事务t l 读取一条数据后，事务t 2 对其 做了修改，当事务再次读取该数据时，得到与前一次不同的值；事务t l 读取一条数据 后，事务t 2 对其做了删除，当事务再次读取该数据时，返回空值。 ( 4 ) 幻象 - 事务t l 的查询结果是一个数据集合，这个集合满足某个查询条件，事务t 2 创建数 据项，并且这些数据项都满足的查询条件。如果事务t 1 重复相同的查询，那么此时获 取的数据与第一次读取的不同。 ( 5 ) 更新丢失 两个事务都同时更新一行数据但是第二个事务却中途失败退出，导致对数据两次修 改都失效了这时系统没有执行任何锁操作，因此并发事务并没有被隔离开来。 并发控制必须保证并发事务正确的执行。下一节给出事务并发执行正确性的标准。 大连理工大学硕士学位论文 2 2 2 隔离性级别 为了避免上面出现几种情况，a n s is q l 规范定义了四种事务隔离级别，不同隔离 级别对事务处理不同。 ( 1 ) 串行化：提供严格的事务隔离，它要求事务顺序执行，事务只能一个接着一 个地执行，但不能并发执行。事务隔离的最高级别是事务之间完全隔离。如果事务在可 串行化的隔离级别上运行，则可以保证任何并发重叠事务均是串行的。 在上一节的例子中，错误是由不同事务对同一数据项的操作交叉执行引起的。为了 避免这个问题，必须控制事务间的交叉操作。一种方法就是让事务顺序执行。然而，顺 序执行事务，会有很多缺陷。如d b m s 效率低下，并且资源不能够共享。为了能够并 发、正确的处理多个事务，只要求多个事务并发执行的结果和这些事务顺序执行时的结 果一样即可。这样的执行叫做可串行化。因为事务顺序执行是正确的，串行化执行的结 果和顺序执行是一样的，所以串行化执行也是正确的。 和上面提及的串行化的概念相比，视图串行化是一种特殊的串行化标准，并且对于 多版本数据的并发控制尤为有效。 考虑两个调度s 和s ，参与调度的事务集是相同的，如果满足以下三个条件，称调 度s 和s 视图等价。 对于每个数据项q ，若事务t i 在调度s 中读取了q 的初始值，那么在调度s 中，t i 也必须读取q 的初始值。 对于每个数据项q ，若事务t i 在调度s 中执行了r e a d ( q ) 并且读取的值是由瓦 产生的w r i t e ( q ) ，则t i 在调度s 中读取的值也必须是由1 ：i 产生的w r i t e ( q ) 。 对于每个数据项q ，若在调度s 中有事务执行了最后的写操作w r i t e ( q ) ，则在调 度s i 中该事务也必须执行最后的写操作w r i t e ( q ) 。 在视图等价的三个条件中，前两个条件保证了两个调度中的每个事务都读取了相同 的值，从而才能进行相同的计算。第三个条件和前两个条件一起保证了两个调度能够得 到相同的最终系统状态。 视图等价的概念引出了视图可串行化的概念。如果某个调度视图等价于一个串行调 度，则说这个调度是视图可串行化的。但是验证一个调度是否是视图可串行化的问题已 经被证明是n p 困难问题，意味着要花很多的时间去检验一个数据库的操作序列是否违 背视图可串行化的正确性标准，因此，它不适合作为一个评判标准。 现在考虑一个调度s ，其中含有分别属于t i 和t i 的两条连续的指令i i 和i j ( i j ) 。 如果i i 和i i 引用不同的数据项，则交换i i 和i i 不会影响调度中任何指令的结果。然而， 本地封闭世界假设下数据分布策略的研究 若i i 和i j 引用相同的数据项，则两者的顺序至关重要。当i i 和i j 是不同事务在相同的数 据项上的操作，并且其中至少有一个是写指令时，i i 和i j 是冲突的。 设i j 和i i 是调度s 的两条连续指令，若i i 和i j 是属于不同事务的指令且不冲突，则 可以交换i i 和i i 的顺序得到一个新的调度s ，则称s 和s 等价。如果调度s 可以经过一 系列非冲突指令交换转换成s ，那么称s 和s 。是冲突等价的。 由冲突等价的概念引出了冲突可串行化的概念，若一个调度s 与一个串行调度冲突 等价，那么称调度s 是冲突可串行化的。 冲突串行化和视图串行化的最大区别在于前者能够被很好的检测。冲突串行化可以 通过相应的顺序图表示出来。从事务t i 指向瓦的有向边表示了操作p t i 和操作g t j 是冲突的。考虑以下的调度： s = r i ( y ) r 3 ( p ) r 2 ( y ) w 2 ( y ) w 3 ( x ) r 2 ( q ) c 2 w 3 ( q ) c 3 w 1 ( p ) c z 冲突( r i ，w 2 0 , ) ) 和( r 2 固) ，w 3 国) ) 意味着t i t 2 t 3 然而，冲突( r 3 仞) ，w l ) ) 意 味着t 3 先于t 】执行。很明显，这不可能同时满足，调度s 的顺序图中会产生环。 如果调度s 的顺序图无环，则调度s 是冲突可串行化的。 相比于视图可串行化，冲突可串行化限制性更强，一个调度如果是冲突可串行化的， 那么它也是视图可串行化的，但是一个调度是视图可串行化的，它不一定是冲突可串行 化的。 ( 2 ) 可重复读取：禁止“不可重复读取 和“读脏数据 。但是有时可能出现幻 影数据，这可以通过“读锁和“写锁 实现，读取数据事务将会禁止写事务( 但允许 读事务) ，写事务则禁止任何其他事务。在此隔离级别下，用s e l e c t 命令读取的数 据在整个命令执行过程中不会被更改。 ( 3 ) 授权读取：也称提交读。允许不可重复读取但不允许读脏数据。这可以通过 “瞬间共享读锁”和“排他锁”实现，读取数据的事务允许其他事务继续访问该行数据， 但是未提交写事务将会禁止其他事务访问该行。s q ls e r v e r 默认的级别。在此隔离级下， s e l e c t 命令不会返回尚未提交的数据，也不能返回脏数据。 ( 4 ) 未授权读取：也称未提交读。允许读脏数据但不允许更新丢失，如果一个事 务已经开始写数据则另外一个数据则不允许同时进行写操作但允许其他事务读此数据。 该隔离级别可以通过“排他锁实现。事务隔离的最低级别，仅可保证不读取物理损坏 的数据。与r e a dc o m m i t t e d 隔离级相反，它允许读取已经被其它用户修改但尚未 提交确定的数据。 表2 1 展示了不同的隔离级别的封锁协议和对应的现象之间的关系。 大连理工大学硕士学位论文 表2 1 不同级别的封锁协议 t a b 2 1d i f f e r e n tl e v e l so fl o c k i n gp r o t o c o l 一级封锁协议：事务t 在修改数据之前必须先对其加写锁，直到事务结束才释放。 这种协议可以防止“丢失修改 。 二级封锁协议：一级封锁协议加上事务t 在读取数据之前必须对其加读锁，读完后 即可释放。这种协议可以防止“丢失修改”和“读脏数据”。 三级封锁协议：一级封锁协议加上事务t 在读取数据之前必须先对其加读锁，直到 事务结束才释放。这种封锁协议可以防止“丢失修改 、“读脏数据 和“不可重复读 。 表2 2 展示了不同的隔离性级别能用怎样的封锁协议实现。 表2 2 隔离性级别与锁的对应 t a b 2 2 d e g r e e so f c o n s i s t e n c ya n dl o c k i n g 2 3 并发控制算法 ， 数据库并发控制算法根据处理冲突的方法，可以分为两类。一类是乐观并发控制算 法，其中的乐观指的是系统认为事务之间不会发生数据访问冲突，因此该算法允许事务 无阻碍地执行直到全部操作完成，然后在提交之前进行验证，如果通过了验证就提交， 否则就重启或者夭折。另一种是悲观并发控制算法，其中的悲观指的是系统认为事务之 间会发生数据冲突，当两个事务之间存在冲突时，一个事务将阻止另一个事务的执行。 本章节回顾了属于乐观协议和悲观协议的主要数据库并发控制算法。 一9 一 本地封闭世界假设下数据分布策略的研究 通过加锁和释放锁来管理共享数据，如果数据项被一个事务加锁了，那么另一个事 务只有等到该事务释放锁时才能再对其加锁。在事务t 被允许访问数据项x 之前，调度 器检查z 是否被其他事务加锁，如果x 已被加锁，那么事务t 必须等待z 上的锁被释放 后才能对z 加锁；如果x 未被加锁，那么事务t 可以直接对彳加锁。加锁完成之后，t 就可以对x 进行读写操作。当t 不再需要对x 进行访问时，就释放x 上的锁。所有的悲 观协议都是基于上面描述的锁机制。不同的算法控制着不同种类的锁。 迄今为止，一直默认假设调度器运行在一个冲突事件频繁发生的事务环境下，因此 采取的措施必须总是能有效地处理这些问题。对于每个新到达的步骤，调度器必须当场 决定，是执行、拒绝还是阻塞。基于这些假设的调度器称为悲观调度器，另一种不同的 调度器则是基于相反的假设，它假设冲突总是很少发生，其本质是让新达到的操作只是 简单通过，有时检测一下迄今产生的调度是否仍然是可串行化的。为了确认到目前为止 调度器已经做了什么，如何做的，不能在终端调度产生，但是可以在事务自身中创建这 种有效性确认。 。 为此，需要搞清楚事务的执行过程的三个阶段，读阶段：执行事务，但是将事务的 所有结果放在事务各自私有的工作空间内，而不放在数据库里。因此，事务写的私有版 本数据项对其他事务是不可见的。有效性确认阶段：验证准备提交的事务。即，调度器 检测它的执行在冲突可串行化的意义上是否已经是“正确的 ，以及事务的结果可以复 制到数据库中。如果上述情况不正确，则取消事务，否则进入下一阶段。写阶段：将私 有工作空间的内容传送到数据库中，接受事务提交的结果。 2 3 1 两段锁协议 两段锁是在数据库系统中最常用的并发控制算法。基于事务的页模型，锁被分为两 种，分别是读锁( i u ) 和写锁( w l ) 。当事务t 需要读或者写数据项x 时，必须在x 上加读锁或者写锁。类似于不同事务在同一数据项上的冲突，锁与锁之间也是有冲突的。 两个操作中至少有一个有写操作，那么这两个操作是冲突的，因此写锁又叫做排他锁， 读锁叫做共享锁。 两段锁协议是指所有事务必须分两个阶段对数据项加锁和解锁。每个事务在对任何 数据进行读、写操作之前，首先要申请并获得该数据的封锁；在释放一个封锁之后，事 务不能再申请和获得任何其他封锁。所谓“两段 的含义是，事务分为两个阶段，第一 阶段是封锁阶段，也称为扩展阶段，在这个阶段里，事务可以申请获得任何数据项上的 任何类型的所，但是不能释放任何锁。第二阶段是释放封锁，也称为收缩阶段，在这个 阶段里，事务可以释放任何数据项上的任何类型的锁，但是不能再申请任何锁。 大连理工大学硕士学位论文 下面给出一个例子说明两段锁协议如何工作。假设事务t l ，t 2 ，t 3 在两段锁协议下 并发运行，每个事务的操作顺序如下： t l ： r 1 0 )w i )w 1 ( z ) c l t2ibibw 2 ( x ) c 2 t 3 ：r 3 ( z )w 3 c 3 那么这个调度s 可以表示为： r l 3 ，r 3 ，r l r ( x ) ，r l ( x ) ，r l 2 0 , ) ，i b ，w l l ，w l i x ) ，砜，w 3 国，r l 2 b l o c k e d ， w l l ( z ) b l o c k e d , w l 2 ( x ) b l o c k e d ，c 3 ，r l 3 r e l e a s e d , w l i ( z ) ，w l 仂，c 1 ，w l l ) r e l e a s e d ，w l l ( z ) r e l e a s e d ，r l 2 ( x ) ，r 2 ( x ) ，w l 2 ( 功，w 2 ( x ) ，c 2 很明显，由于锁协议，某些操作被暂停了，事务的并发执行可以等价于t 3 r 1q ， 顺序图中没有出现环，因此这个调度是冲突可串行化的。 在两段锁协议下，一个事务只有在它需要的所有锁都得到之后，才会开始释放锁。 如果些事务需要的锁一直被其他事务占有，那么这些事务将永远暂停。举一个最简单 的例子，事务t l 和t 2 ，t 1 所占有的锁正是t 2 需要申请的锁，这意味着t 2 必须等待 t 1 ；而t 2 所占有的锁正是t l 需要申请的锁，这意味着t l 必须等待t 2 。从而t l 和t 2 相互阻止，并且都不能继续进行。这种现象称为死锁。死锁是两段锁协议的一个弊端。 此时，系统唯一的补救措施是采取激烈的动作，如回滚某些陷于死锁的事务，事务有可 能只部分回滚，即事务回滚到得到锁的那一点之前，而释放该锁就可以解决死锁。 处理死锁问题有两种主要的方法，一是可以用死锁预防协议保证系统永远不进入死 锁状态。二是，允许系统进入死锁状态，然后试着用死锁检测与死锁恢复机制进行恢复。 两种方法均会引起事务回滚。如果系统进入死锁状态的概率相对较高，则通常使用死锁 预防机制；否则，使用检测与恢复机制会更有效。 预防死锁有两种方法。第一种方法，通过对加锁请求进行排序或要求同时获得所有 的锁来保证不会发生循环等待。另一种方法比较接近死锁恢复，每当等待有可能导致死 锁时，进行事务回滚而不是等待加锁。 死锁的检测与恢复也有两种方法，一种是基于超时机制，给定一个超时期限，若超 时则该事务回滚并重启。第二种方法是用等待图来精确描述。 等待图由g = ( v ，e ) 对组成，其中v 是顶集，e 是边集。顶点集由系统中的所有 事务组成，边集e 的每一元素是一个有序对t i t i 。如果t i t i 属于e ，则存在从事务 t j 到t i 的一条有向边，表示事务t i 在等待t i 释放所需的锁。当事务t i 申请的数据项当 前被t i 持有时，边t i t i 被插入等待图中。只有当事务t i 不再持有事务t i 所需数据项 时这条边才从等待图中删除。当且仅当等待图中包含环时，系统中存在死锁。在该环中 本地封闭世界假设下数据分布策略的研究 的每个事务被称为处于死锁状态。要检测死锁，系统需要维护等待图，并周期性地调用 一个在等待图中搜索环的算法。 当检测算法判定存在死锁时，系统必须从死锁中恢复( r e c o v e r ) 。解除死锁最通常 的做法是回滚一个或多个事务。需采取三个动作： ( 1 ) 选择牺牲者。给定处于死锁状态的事务集，为解除死锁，必须决定回滚哪一 个( 或哪一些) 事务以打破死锁。应使事务回滚带来的代价最小。 ( 2 ) 回滚。一旦决定了要回滚哪个事务，必须决定该事务回滚多远。最简单的方 法是全部回滚，中止该事务，然后重新开始。然而，事务只回滚到可以解除死锁处会更 有效。 ( 3 ) 饿死。在系统中，如果选择牺牲者主要基于代价因素，有可能同一事务总是 被选为牺牲者，这样就发生饿死。 2 3 2 顺序检测图( s g t ) 顺序图能够很清楚的描述调度的冲突串行化，如果顺序图无环，那么相应的调度是 冲突可串行化的。顺序图检测( s g t ) 作为一种乐观算法被提出。按照顺序图的定义， 图中的所有节点都是已提交的事务。而在s g t 中，节点都是处于活动状态的事务，当 事务开始或者结束时，相应的节点被加入或移除图。 当执行到t i 的一个操作p 缸) 并且没有提交时，它可以被执行，如果p i 是t i 的第 一个操作，那么将在s g t 中创造一个节点，如果p 舡) 和其他操作冲突的话，将冲突边 也加入图中；如果v i ( x ) 提交，将检测图中是否有环，如果有环的话，t i 将被夭折，否则 t i 提交。对应事务t i 的节点和与它有关的所有边都将从图中移除。对于一个已提交的事 务，只要它是一个源点( 没有指出去的边) ，就可以被移除。 假设事务t l ，t 2 ，t 3 并发运行，每个事务的操作顺序如下： t 1 ：r 1 w k x )w l f y ) c l t 2 ： r 2 f y )r 2 ( x )w 2 c 2 t 3 ：r 3 ( z )w 3 ( z ) c 3 在c i 执行之前，冲突( w l ，r 2 ) 意味着t l t 2 ，( r 2 ，w l ) 意味着t 2 - - t i ， 当执行到c l 时，s g 中有环，因此t l 被夭折，并且与之相关的边也被移除。当执行到 c 2 时，s g 是t 3 一t 2 ，图无环意味着t 2 可以提交，但是t 2 不是源节点，它不能从图中 移除，当执行到c 3 时，t 3 也可以提交，由于t 3 是一个源节点，可以从图中移除。通过 夭折违背冲突串行化的事务t l ，保证了t 2 、t 3 的执行。 s g t 是一种直接、重要的算法，大多数与图相关的并发控制算法都以此为基础。 大连理工大学硕士学位论文 2 3 3 多版本并发控制 事务读取的数据通常都是当前数据库的最新值。在多版本并发控制中，每个数据可 以具有多个版本，读操作中事务可以读取没有被覆盖的旧版本来保证调度的可串行性。 这样可以增加了事务的并发度，减少了拒绝操作。如果一个事务读取了另一个活动事务 产生的数据版本i 可恢复性要求该事务必须在生成该数据版本的活动事务之后提交；如 果这个活动事务夭折，则该事务也必须夭折。虽然数据具有多版本，但是从用户的角度 来看，数据还是单版本的，不会破坏数据库的单版本视图。 多版本两阶段封锁协议希望多版本并发控制的优点与两阶段封锁的优点结合起来， 该协议对只读事务与更新事务加以区分。更新事务执行强两阶段封锁协议，即它们持有 全部锁直到事务结束。因此，它们可以按提交的次序进行串