（计算机软件与理论专业论文）分布式数据库中数据分配策略的研究.pdf

哈尔滨1 ：稃大学硕士学位论文 摘要 解决数据分配问题的目的是使整个分布式数据库系统的总体代价最优， 这也是在数据分配设计时需要考虑的首要问题。为了更好地解决数据分配问 题，本文的作者主要综合了启发式添加副本法和启发式试消副本法的优点， 同时也采纳了分组局部优化法和基于代价得益的启发式数据片段分配方法 的长处，提出了一种基于数据片段访问特性的分配策略。 统计信息是解决数据分配问题的基本信息。在本文的策略中，首先按照 三条原则选择了代价公式中要使用的统计信息，然后确定了以事务处理代价 为主的代价公式，最后，提出了“基于数据片段访问特性的分配策略”。该 策略根据数据片段的访问特性( 更新检索比) 来区别对待不同的数据片段， 这一点在分配步骤的所有环节上都有所体现。本文提出的策略概括起来主要 分两步：第一步，确定对于部分应用最优的初始分配并将数据片段按更新 检索比排序；第二步，按上一步排好的顺序调整分配，平衡整个系统的更新 代价和检索代价。这样可以尽量达到全局代价最优，即系统事务处理总代价 最小。最终获得一个能使更新、检索总代价尽可能小的近似最优分配方案。 在本文的最后，通过实验验证了该策略。实验表明应用该策略能够得到 比使用启发式试消副本法和启发式添加副本法更接近最优解的结果，并且由 于存在可并行的步骤也使得本策略中的算法效率得以提高。该策略简单、易 行，总体性能更为优秀。 关键词：分布式数据库；片段分配：代价公式：统计信息 哈尔滨下程大学硕士学位论文 a b s t r a c t t h ea i mo fs o l v i n gf r a g m e n ta l l o c a t i o ni s o p t i m i z i n gt h et o t a lc o s to f d i s t r i b u t e dd a t a b a s es y s t e m t h i si sa l s ot h em o s ti m p o r t a n tp r o b l e mi nt h ed e s i g n o fd a t aa l l o c a t i o n f o rs o l v i n gt h ep r o b l e mo fd a t aa l l o c a t i o nb e n 盯t h ea u t h o ro f t h i sp a p e rs y n t h e s i z e dh e u r i s t i cr e m o v ef r a g m e n tc o p i e sa l l o c a t i o na l g o r i t h ma n d h e u r i s t i ca d df r a g m e n tc o p i e sa l l o c a t i o na l g o r i t h mm a i n l y m e a n w h i l e ，l o c a l o p t i m i z a t i o n d a t aa l l o c a t i o n a l g o r i t h m a n db e n e f i t - e n s th e u r i s t i c f r a g m e n t a l l o c a t i o nm e t h o d 瓣a l s oa d o p t e d f i n a l l yt h ea u t h o rp r o p o s e daf r a g m e n t a l l o c a t i o ns t r a t e g yb a s e do nt h ea c c e s s i n gc h a r a c t e r i s t i co f d a t af r a g m e n t s t a t i s t i c a li n f o r m a t i o ni st h eb a s i ci n f o r m a t i o nf o rs o l v i n gt h ep r o b l e mo f d a t aa l l o c a t i o n i nt h i ss t r a t e g y ，t h es t a t i s t i c a li n f o r m a t i o nw h i c hw i l lb eu s e di n t h ec o s tf o r m u l ai sc h o o s e dt h r o u g ho b e y i n gt h r e ep r i n c i p l e sf i r s t l y s e c o n d l y ，t h e c o s tf o r m u l aw h i c hi sm a i n l ya b o u tt h ec o s to f t r a n s a c t i o np r o c e s s i n gi sc o n f i r m e d f i n a l l y ，af r a g m e n ta l l o c a t i o na l g o r i t h mb a s e do i lt h ea c c e s s i n gc h a r a c t e r i s t i co f d a t af r a g m e n ti sp r o p o s e d t h i ss t r a t e g yt r e a t sd a t af r a g m e n td i f f e r e n t l yb yt h e a c c e s s i n gc h a r a c t e r i s t i ca n dt h i sp o i n ti si n c a r n a t e di ne v e r ys t e p t h i ss t r a t e g y c a l lb ed i v i d e di n t ot o ws t e p s t h ef a s ts t e pi sm a l d n gai n i t i a la l l o c a t i o na n d s o r t i n gt h ed a t af r a g m e n t sb yt h er a t i oo f u p d a t ea n dr e a do n l y t h es e c o n ds t e pi s a d j u s t i n ga l l o c a t i o nb yt h ep r e v i o u so r d e r , b a l a n c i n gt h ee n t i r es y s t e mc o s to f u p d a t ea c c e s sa n dr e a do n l ya c 4 ：e s s t h e n , i ta l m o s tb a no p t i m i z et h et o t a lc o s t , t h a ti st h et o t a lc o s to f t r a n s a c t i o np r o c e s s i n gi sn e a r l ym i n i m a l a tt h ee n do ft h i sp 鳓t h i ss t r a t e g yi sv a l i d a t e dt h r o u g he x p e r i m e n t t h e e x p e r i m e n ts h o w st h a tab e t t e rr e s u l tc a nb eg a i n e db yu s i n gt h i ss t r a t e g yt h a n u s i n gh e u r i s t i cr e m o v ef r a g m e n tc o p i e sa l l o c a t i o na l g o r i t h mo rh e u r i s t i ca d d f r a g m e n tc o p i e sa l l o c a t i o na l g o r i t h m a g o r i t h me f f i c i e n c yi si m p r o v e db c c a u $ e t h e r ea r es o m es t e p sw h i c hc a nb ee x e c u t e dp a r a l l e l l y i th a sb e e np r o v e dt h a ti ti s s i m p l e ，c o m p r e h e n s i v e ，p r a c t i c a l ，a n dm o r ee x c e l l e n ti nc o l l e c t i v i t y 哈尔滨丁稃大学硕士学位论文 k e y w o r d s ：d i s i b u t c dd a t a b a s e ；f r a g m e n ta l l o c a t i o n ；c o s tf o r m u l a ；s t a t i s t i c a l 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中己 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ： 日期：7 咖7 年 垄埠 ，月) 日 | 哈尔滨1 ：程大学硕十学位论文 第1 章绪论 1 1 选题的背景和研究意义 分布式数据库系统( d i s t r i b u t e dd a t a b a s es y s t e m ，d d b s ) 是计算机网络 技术与数据库技术互相渗透和有机结合的产物，具有数据独立性、集中与自 制相结合的控制机制、适当增加数据冗余、事务管理的分布性等特点“1 。分布 式数据库系统是分散存放在许多台计算机上的数据的集合，它在逻辑上是一 个单一的、集中管理的数据库，但在物理上却存放在多个场地上，既允许局 部的数据访问，同时又实行全局管理。一个完整可靠的分布式数据库系统能 够随时随地提供可靠的信息，用户可以随时灵活地访问信息而不必关心数据 存放的地点和方法w 。效率是能极大地影响分布式数据库迅速推广和应用的关 键点。在分布式数据库系统中，数据不是集中存放的，而是分开存放在网络的 各个节点上，这是和集中式数据库最大的不同之处。 分布式数据库系统在2 0 多年的发展历史中，取得了很多研究成果，许多 问题被提出并得以解决。与此同时，在数据库技术和网络技术相互渗透和有 机融合的过程中也产生很多新的、由分布式环境造成的固有技术难题。但是 鉴于分布式数据库系统在社会生产、生活的多方面( 如交通”1 、多媒体应用“、 无线通信m 等) 都有深刻的应用背景，各国还是在分布式数据库系统的研制方 面投入了大量的人力、物力、财力，如：德国斯图加特大学研制的p o r e l ； 美国i b m 公司的s a nj o s e 研究室研制的r 和s y s t e mr ；美国加州大学伯克 利分校研制的d i n g r e s 等等“。在我国，虽然分布式数据库系统的研究和 应用明显落后于发达国家，但是随着人们对分布式数据库系统认识的提高， 以及社会生产生活中基于分布式数据库系统的应用的增加。国内对于分布式 数据库系统的研究和应用也将飞速发展。 分布式数据库系统中的分布式数据库设计较之普通数据库设计具有自己 的特色。在分布式数据库设计中，大部分问题都是由数据的分布性而引起的， 它对整个应用系统的可用性、可靠性及数据的存取效率都产生很大的影响， l 哈尔滨t 程大学硕士学位论文 同时又与分布式数据库系统设计的其它方面问题密切相关，尤其是分布式查 询处理与更新处理问题往往与它交织在一起。分布式数据库设计的主要目标 之一是数据处理的本地性，即使数据尽可能存放在使用它们的应用所在的节 点，从而减少远程访问。由此产生了“数据冗余”这一能为检索访问提供便 利但却给维护数据的一致性带来麻烦的“双刃剑”。所以，在分布式数据库 系统的优化设计中，数据分布问题就显得特别重要。数据分布问题包括两个 方面的内容：数据逻辑分割( 数据分片) 和片段物理分配( 数据分配) 。本 文不过多地涉及数据分片方面的研究而会将重点放在数据分配问题上。 数据分配问题对整个分布式数据库应用系统的改进、数据的可用性、分 布式数据库的效率和可靠性有很大影响。若数据片段分配得好，整个应用系 统的性能、数据的可用性以及分布式数据库( d i s t r i b u t e dd a t a b a s e ，d d b ) 的 效率和可靠性都会处于一个良好的状态，否则，就体现不出分布式数据库的 优越性。国内外学者研究该问题的最终目的都是希望得到一个使由远程访问 通信代价和局部事务处理代价组成的总代价最小的最优解决方案，从而明确 得出全局关系划分后的逻辑片段应该放置的最佳场地。对于分布式数据库系 统的数据分配问题的研究具有相当大的学术及实用意义，它能在将分布式数 据库系统融入企业的运作和发展、节约投入和增强竞争力等方面起到积极的 推动作用n ，。 1 2 国内外研究现状 在分布式数据库系统的设计中，数据分配主要是解决数据片段在分布式 系统各节点上的分布。当然，解决方案应满足一定的优化标准，其实质是要 得到一个最优分配方案。不过这样的问题因其复杂性太大被列为n p 难题”。 在很多实际应用中，其实也并不一定要得到最优分配方案，一个足够接近最 优分配方案的近似最优分配方案往往也可以满足要求。 国内外学者在数据分配的基本原则上是有两点共识的。 ( 1 ) 数据应尽可能靠近要使用它的站点，并用负载平衡方法找出一个系 统性能的全局优化： ( 2 ) 检索事务应尽量局部化；更新事务所涉及的数据片段的副本不宜过 2 哈尔滨t 稃大学硕士学位论文 多，以减少保持数据一致性的代价。 对于分布式数据库系统的应用需求和理论研究，国外都要领先于国内。 对于数据分配问题的研究，国外学者在基础理论方面贡献颇多，如文献 8 中提出的方法对于避免由于系统i o 瓶颈造成的效率下降提供了帮助。 国内学者在对该问题的研究上虽然起步较晚，但是也逐步跟上领先者的 步伐，获得不少研究成果，如“启发式试消副本法”在降低分配算法的复杂 度方面有很好的效果。 数据片段的分配方法可分为非冗余分配和冗余分配两种。 ( 1 ) 非冗余分配将每个数据片段只存放在一个站点上，数据片段无冗余 副本存在，常用的非冗余分配方法是最佳适应法( b e s t - f i t ) ； ( 2 ) 冗余的分配允许将一个数据片段的不同副本存放在几个不同的站点 上。冗余分配具有较为复杂的分配设计问题和分配算法，常用的冗余分配方 法有选择所有收益场地法( a l lb e n e f i c i a ls i t e s ) 和添加副本法( a d d i t i o n a l r e p l i c a t i o n ) 。 采用哪种分配方法由应用的性质决定。一般说来，对于检索应用占多数 的片段可以采用冗余分配，以减少远程访问，即减少站点问数据传送的通信 量，提高数据的读取速度。对于更新应用较多的片段应采用非冗余分配，以 避免为使多个副本之间保持一致而付出的巨大开销。 关于优化的定义，通常有两个度量标准。 ( 1 ) 最小代价：代价函数包括在站点存储每个片段r 的代价、在站 点& 检索片段毋的代价、在所有存储片段易的站点上的更新代价以及数据 通讯代价； ( 2 ) 性能：两个著名的标准是最小化响应时间和最大化每个站点的系统 吞吐量。 在优化的度量问题上，国内外学者均偏向于代价优化。提出的优化函数 也大多基于代价函数m 。当然也有部分学者致力于性能优化的研究，如文献 9 中，为最小化平均响应时间提出了有效的方法。 分布式数据库系统中数据分配方法的复杂性很大程度上是由分布式环境 及分布式应用决定的，关于分布式环境及分布式应用的一些准确的统计信息 对分配方法及代价公式的建立和优化都有很大影响。统计信息的选取原则和 3 啥尔滨工稃大学硕士学位论文 研究者的具体研究环境有关，有的侧重于网络传输代价、有的侧重于数据动 态性u o ，、有的侧重于拓扑结构m 1 等等。虽然国内外学者在选择统计信息时各有 不同的侧重，选择的统计信息也不尽相同，但是这些统计信息归结起来不外 乎四种：数据库信息、应用信息、站点信息、网络信息“- 。 由于不同学者对各种统计信息的侧重不同，他们所提出的代价函数都有 着不同的重点，在此仅举三例。 文献 7 中提出的代价函数为：m i n ( t o t a l c o s t ) 。其中t o m l c o s t 包含两 部分：查询处理和存储。 文献 1 2 中提出的代价函数为：m i i l 够c o st + 口c o st ) ，即使更新和检 索代价最小。 文献 1 3 中提出的代价函数为：b ( ，- ，) = c n ( ，) 一c y ( ，) 。其中， b 够_ ，) 是分配到节点_ ，的得益，c y _ ，) 是分配片段，到节点歹的局部代 价，c n ，) 是不分配片段，到节点_ ，的局部代价。 如何选择并量化这些在数据分配时需要考虑的统计信息是解决数据分配 问题重要的一环；如何将统计信息考虑进一个分配模型( 目标函数) 中并求 出最优解，更是一个n p 难题。所以，一些启发式算法，如背包问题方案、 o 1 整数编程m ，、得益一代价启发式分配方法“一，还有遗传算法“等也被用来解 决数据分配问题。分布式数据库中的数据分配问题在理论上都是采用启发式 算法和优化算法来解决的。 1 3 本文的研究内容 作者查阅了大量的相关文献，阅读了国内外学者有关数据分配方面的论 文资料，总结了各种启发式分配算法的优缺点，认为首先本课题的入手点应 放在合理选择统计信息上。选择统计信息应该主要考虑以下几点。 ( 1 ) 统计信息对代价公式的准确性的影响； ( 2 ) 获取统计信息的代价； ( 3 ) 统计信息对代价公式的复杂性的影响。 实际情况中统计信息的种类繁多、数量庞大，获取的难度也是千差万别； 同一统计信息对不同的实际系统的重要性也不尽相同：获得一个统计信息的 4 哈尔滨1 ：程大学硕士学位论文 难度代价与考虑该统计信息对分配的好处之间也存在着制约关系。忽略获取 难度过大的和对分配结果影响甚小的统计信息，是减小分配方法的复杂性的 好办法。 接下来作者确定了代价公式是由更新代价和检索代价组成的。 然后作者提出了“基于数据片段访问特性的数据分配策略”，该数据分 配策略的出发点放在数据片段的更新检索特性上，根据更新检索特性来决 定数据片段的初始分配方法和分配调整策略，以代价与得益之间的关系作为 添加副本或消除副本的依据。最终目的是获得一个检索和更新总代价尽可能 小的分配方案，即近似最优分配方案。该策略能够在一定程度上减小解空间， 算法步骤有一定并行性，使得该分配策略简单、易行，获得的分配方案也更 合乎实际。 在本文的最后通过分析和实验结果表明使用本论文提出的分配策略得到 的片段分配方案更接近最优分配，分配效率更高，总体的性能优于启发式添 加副本法和启发式试消副本法。 1 4 本文的组织结构 作者首先在第l 章中介绍了本论文的选题背景、研究意义、国内外研究 现状和本文研究的内容，其次在第2 章中，从分布式数据库和分布式数据库 系统的基础知识入手，逐步深入到数据分配的理论与方法，然后在第3 章中 具体分析了国内外学者提出的四种典型数据分配方法，接着在第4 章中提出 了新的分配策略以求在更小的时间复杂度下求得更接近最优解的数据分配方 案，并且以一个实例来说明该分配策略的详细过程，最后在第5 章中设计了 一组实验来验证新的分配策略。 哈尔滨t 程大学硕十学位论文 第2 章分布式数据库系统简介 为了能使读者更好地理解分布式数据库的数据分配问题，在正式切入本 文主题数据分配问题之前，有必要先对分布式数据库系统做一个简要的 介绍。 2 1 分布式数据库和分布式数据库系统 分布式数据库简单来说，是计算机网络环境中各场地上的数据库( 为了 与集中式数据库相区别，称场地上的数据库为局部数据库l o c a ld a t a b a s e ， l d b ) 的逻辑集合，也就是说分布式数据库是一组数据集，它们与传统的数 据库一样也是结构化的数据集合，它们在逻辑上属于一个系统，在物理上分 布在网络的不同节点上。分布式数据库强调这组数据集的分布性和逻辑协调 性。所谓分布性，是说数据不是存放在单一场地为单个计算机配置的存储设 备上，而是按应用的需要将整体数据分成一定结构的子集，分散存储在各个 场地上。逻辑协调性是说各场地间的数据相互之间有严密的约束规则，子集 在逻辑上是一个整体“”。 正是因为分布式数据库有着逻辑整体性和物理分布性，所以可以把分布 式数据库看作是各个局部数据库的逻辑集成，即分布式数据库是虚拟的( 逻 辑的) ，数据的真正存放地是分散在计算机网络上的各个节点中的物理数据 库。于是，在分布式数据库中出现了全局数据库( g l o b a ld a t a b a s e ) 和局部 数据库这样的术语。全局数据库是逻辑的，局部数据库是物理的。 分布式数据库管理系统( d i s t d b u t c dd a t a b a s em a n a g e m e n ts y s t e m ， d d b m s ) 是分布式数据库系统中的一个软件“”，它是由局部数据库管理系统 和全局数据库管理系统共同构成。它负责管理分布式环境下数据的存取、一 致性、有效性、完整性等。数据库的分布性特征要求分布式数据库管理系统 除了拥有数据库管理系统共有的控制功能外，还必须拥有在网络通信协议上 的分布管理能力。 在分布式数据库系统中，被计算机网络联接的每个逻辑单位，称为站点 6 哈尔滨下稃大学硕士学位论文 ( s i t e ) 或节点( n o d e ) 。所谓地理位置上分散是指各站点分散在不同的地 方，大可为不同国家，小可为同一建筑物中的不同位置。所谓逻辑上集中是 指各站点之间不是互不相关的，它们是一个逻辑整体，并由一个统一的数据 库管理系统进行管理，这个数据库管理系统称为分布式数据库管理系统。 因此，所谓分布式数据库系统，是物理上分散而逻辑上集中的数据库系 统。分布式数据库系统使用计算机网络将地理位置分散而管理和控制又需要 不同程度集中的多个逻辑单位( 通常是集中式数据库系统) 联接起来，共同 组成一个统一的数据库系统。因此，分布式数据库系统可以看成是计算机网 络技术与数据库技术的有机结合 2 2 分布式数据库系统的分类 根据分布式数据库系统的体系结构和建立原则，可以将其分为两类： ( 1 ) 同构型分布式数据库系统：各个站点都采用同一类型的数据模型( 例 如，都是关系型) 。它类似于一个集中式数据库，只不过是将数据存放在网 络中的不同节点内，而不是存放在一个节点内。根据数据库管理系统的不同， 同构型分布式数据库系统又可分为同构同质型和同构异质型。 ( 2 ) 异构型分布式数据库系统：各个站点的数据库管理系统的型号不同， 甚至数据模型的类型也不同( 例如，有关系型的、有面向对象类型的) 。这 种分布式数据库系统的特点是在各个节点上运行着不同的数据库管理系统。 它也可以分为两个子类：一类是完全在本系统中进行集成；另一类是还要通 过网关与其它系统实现连接。 随着计算机网络技术的发展，异种机联网问题已经得到较好的解决，此 时依靠异构型分布式数据库管理系统就能存取全网中各种异构局部库中的数 据“1 。 按分布式数据库系统的全局控制系统的类型可以将分布式数据库系统分 为以下三类”1 。 ( 1 ) 集中型分布式数据库系统：分布式数据库系统中的全局信息位于一 个中心站点上； ( 2 ) 分散型分布式数据库系统：分布式数据库系统中的每一个站点上都 7 哈尔滨1 = 程大学硕士学位论文 包含全局控制信息的副本； ( 3 ) 可变型分布式数据库系统：分布式数据库系统中的所有站点分为两 组：一组站点包含全局控制信息副本，称为主站点；另一组站点不包含全局 控制信息的副本，称为副站点。 分布式数据库系统的分类还有其他多种方式，可参考文献 2 4 ，这里不 再赘述。 2 3 分布式数据库系统的特点 在分布式数据库系统中，局部用户( 也称为局部应用) 是指一个用户只 访问他注册的那个站点上的数据；全局用户( 也称为全局应用) 是指用户的 访问涉及两个或两个以上的站点中的数据。 从实际的分布式环境及应用的角度出发，一个分布式数据库系统应该具 有如下特点。 ( 1 ) 物理分布性：分布式数据库系统的数据不是存储在一个站点上，而 是分散地存储在由计算机网络联接起来的多个站点上。所以，分布式数据库 系统的数据具有物理分布性，这是与集中式数据库系统的最大差别之一。 ( 2 ) 逻辑整体性：分布式数据库系统中的数据在物理上是分散在各个站 点中的，但这些分散的数据在逻辑上却是一个整体。它们被分布式数据库系 统的所有用户共享，并由一个分布式数据库管理系统统一管理。因此，分布 式数据库系统中就有了全局数据库和局部数据库的概念。局部数据库由局部 数据库管理系统进行管理，所谓局部是从各个站点的角度出发来看的“”。 ( 3 ) 站点自治性：站点自治性也称场地自治性，各站点上的数据由本地 的数据库管理系统来管理，具有自治处理能力，完成本站点的应用( 局部应 用) 。 以上是分布式数据库系统的三个基本特点，也是判断一个系统是否为分 布式数据库系统的依据。另外，分布式数据库系统还具有如下特点。 ( 1 ) 数据独立性：数据独立性是数据库方面追求的主要目标之一。在集 中式数据库系统中，数据独立性包括两个方面：数据的逻辑独立性与数据的 物理独立性。其含义是用户程序与数据的逻辑结构及数据的存储结构无关。 3 哈尔滨下程大学硕士学位论文 分布式数据库系统与集中式数据库系统一样具有这个特点。 ( 2 ) 分布独立性：在分布式数据库系统中，数据独立性具有更多的内容。 除了数据的逻辑独立性与物理独立性外，还有数据的分布独立性。所谓数据 的分布独立性是指用户或用户程序可以像使用集中式数据库那样来使用分布 式数据库，不必关心全局数据的分布情况，包括：全局数据的站点位置分配 情况以及各站点上数据库的数据模型等。也就是说，全局数据的物理位置分 配、各站点数据库的数据模型等情况对用户和用户程序透明。所以，数据分 布独立性也称为数据分布透明性( d i s t r i b u t i o nt r a n s p a r e n c y ) 。 从分布式数据库的体系结构和分布透明性的定义可以看出，分布透明性 包括两个层次： 位置透明性( l o c a t i o nt r a n s p a r e n c y ) ，也称分配透明性，是分布透明 性的中间层。实际上，位置透明性包含了两种情形：一种是各对象被复制的 情况，即每一对象是否被复制、复制了几个副本；另一种是对象及其各副本 的站点位置分配情况。前者也称复制透明性或数据冗余透明性。当分布式数 据库具有位置透明性时，用户编写应用程序要了解全局数据的数据分布情况， 首先要对系统中的数据分布情况进行规划设计，并根据规划设计，将要分布 的对象进行复制，分别在相应的站点上建立其副本，从而实现数据对象的位 置透明性。 局部数据模型透明性( l o c a ld a t at r a n s p a r e n c y ) ，也称局部映像透明 性( l o c a lm a p p i n gt r a n s p a r e n c y ) ，是分布透明性的最底层。当分布式数据 库只具有局部数据模型透明性时，用户编写应用程序不但要了解全局数据的 逻辑分布情况，还要了解各逻辑对象的副本复制情况、以及各对象和副本的 站点位置分配情况，当某个站点上数据库的数据模型改变时，只要改变分配 模式到该站点局部概念之间的映像。这样可以使应用程序不受影响，从而实 现了局部数据模型透明性。显然，在同构分布式数据库系统中，其各站点上 的数据模型相同，且有可能全局数据库的数据模型就采用局部数据库的数据 模型，此时，将大大减少这种映像的复杂性m 一。 ( 3 ) 集中与自治相结合的控制机制：在分布式数据库系统中，数据共有 两个层次：一是局部共享，即同一站点上的用户可共享本站点上局部数据库 中的数据，以完成局部应用；二是全局共享，即分布式数据库系统上的用户 9 哈尔滨工程大学硕十学位论文 都可共享在分布式数据库系统的各个站点存储的数据，以完成全局应用。因 此，分布式数据库系统常常采用集中和自治相结合的控制机制。各局部数据 库管理系统可以独立地管理局部数据库，具有自治的功能。同时，系统又设 有集中控制机制，协调各局部数据库管理系统的工作，执行全局管理功能m 。 ( 4 ) 事务管理的分布性：数据的分布性必然造成事务执行和管理的分布 性，即一个全局事务的执行可分解为若干个站点上子事务的执行。同样事务 的原予性，一致性、可串行性、隔离性和永久性也要考虑分布性的问题m - 。 2 4 分布式数据库系统的环境 分布式数据库系统的环境如图2 1 所示，是由多个计算机设备并使用通 讯设备以及相关的网络通信协议连接而组成的计算机网络。同时，数据库的 内容也必须渗透到网络环境中。它的主要组成是节点场地( 如图中的s i t e1 ) 和通讯设备，以及支持节点场地间通讯的网络通讯软件与协议。 图2 1分布式数据库系统的环境 1 节点场地 具有主动处理能力的单一计算机( 包括那些有多个终端机或远程终端机) 称为节点；由多台计算机组成的节点称为场地。 1 0 哈尔滨t 稃大学硕士学位论文 节点应包括一定的软、硬件成分，硬件成分主要是计算机处理设备及网 络接口设备，配置可根据应用的需要设定。根据节点能力的大小，相应的软 件配置亦有不同。 节点在正常情况下应该是联网状态，即正常工作、发送命令、完成某种 调度，也可能是非联网状态，处于故障离网或维修中离网。联网或离网对于 节点来说一般是动态的。 2 通讯设备 通讯设备包括连接节点的物理链路和一组通讯协议。通讯设备应该知道 每个节点状态，每个节点连接的多种物理路径，以及节点发送报文的协议。 通讯设备的基本功能是在任何一个节点上运行一个进程，可以向在此网络中 任何其它节点上运行的另一个进程发送消息或报文。进程发送或接收报文的 方式可以是点到点的，也可以是广播式的。 3 网络通讯协议 网络中任何两个节点要交换报文，其进程必须遵守某些规则才能得以实 现。网络报文的发送和接收规则称为网络通讯协议，协议规定两个节点的通 讯只能在同层上进行逻辑对话n - 。 2 5 分布式数据库系统的模式结构 模式是对数据库信息的描述m ，。为了使用户能逻辑地、抽象地处理数据， 而不必关心数据在计算机中的具体表示方式，集中式数据库系统采用了三级 模式结构：内模式，概念模式，外模式。通过三个模式之间的相互映像完成 对数据库的操作。众所周知，分布式数据库是基于计算机网络联接的集中式 数据库的逻辑集合，因此分布式数据库系统的模式结构在集中式数据库系统 的基础上又增加了部分新的内容”。 分布式数据库的模式结构如图2 2 所示。在分布式数据库系统中，一般 可以将模式结构分为四层。 ( 1 ) 全局外层，即全局外模式； ( 2 ) 全局概念层，包括全局概念模式、分片模式、分配模式； ( 3 ) 局部概念层，即局部概念模式； 哈尔滨下程大学硕+ 学位论文 ( 4 ) 局部内层，即局部内模式。 图2 2 分布式数据库模式结构 映像l 映像2 映像3 映像4 映像5 各个模式之间由数据库管理系统提供的多次映像来实现转换。 全局概念模式描述分布式数据库中全局数据的逻辑结构，与集中式数据 库中的概念模式相同。如果数据库采用关系模型，则全局概念模式包括一组 全局关系( 表或视图) 的定义( 如名称、字段、字段类型等) 、完整性定义 ( 主键、外键以及其它约束) 等。 全局外模式是全局概念模式的一个子集，它是与之相应的用户所关心的 本地站点上的数据库的描述。 分片模式描述数据分片或定义片段，以及全局关系与片段之间的映像， 这种映像是一对多的，即一个关系可以对应多个片段，但是一个片段只能来 自一个全局关系。 分配模式根据选定的数据分布策略来定义各片段的物理存放站点，即定 义片段映像的类型、确定分布式数据库是冗余的还是非冗余的以及冗余的程 1 2 哈尔滨：r 程大学硕七学位论文 度。 一个全局概念模式( 例如一个全局关系) 经过逻辑划分成一个或多个逻 辑片段，每个逻辑片段可以被分配在一个或多个站点上，称为该逻辑片段在 某个站点上的物理映像或物理片段，分配在同一个站点上的不同的全局概念 模式的一个或多个片段就构成了该全局概念模式在该站点上的一个物理映 像，该站点上全部物理映像的集合称为该站点上的局部概念模式，或者说， 一个站点上的局部概念模式是所有全局概念模式在该站点上的物理映像的集 合。 局部内模式同集中式数据库的内模式相同”1 。 2 6 分布式数据库的数据分片与数据分配 数据分片与数据分配是分布式数据库设计中的两个重要环节，在此先做 一个简要的介绍。 2 6 1 分布式数据库的数据分片 数据分片也称数据分割，是分布式数据库的特征之一。在一个分布式数 据库中，全局数据库是各个站点上局部数据库的逻辑集合，而各个局部数据 库中的数据是由全局数据库按某种逻辑分割而来的。例如，以关系数据库管 理系统为例，一个关系( 表或视图) 描述了某些数据之间的逻辑相关性，但 是，因为不同站点的用户需要访问的该关系中的元组( 记录) 可能不同，所 以需要对这个关系进行分割，将分割后得到的每个部分元组( 记录) 都称为 该关系的一个逻辑片段，存放在相应的站点上。这样可以减少网络通信量， 从而提高效率。 数据分片有三种基本方法。 ( 1 ) 水平分片：按特定条件把全局关系的所有元组分成若干个互不相交 的子集，每一个子集为全局关系的一个逻辑片段，简称为片段。它们通过对 全局关系施加选择运算得到，并可通过对这些片段的合并操作来恢复该全局 关系。 ( 2 ) 垂直分片：将全局关系( 表或视图) 的属性集( 字段集) 中的若干 哈尔滨= 程大学硕十学位论文 属性作投影运算，即得到全局关系的一个垂直分片，要求全局关系的每一个 属性至少映射到一个垂直片段中，且每一个垂直分片都包含全局关系的键。 ( 3 ) 混合分片：水平分片和垂直分片的混合”1 。 对数据库的各种分片方法，都应满足如下原则。 ( 1 ) 完备性原则：全局关系中的所有数据项必须映射到各个分片中，不 允许有属于全局关系的数据却不属于其它的任何一个片段。 ( 2 ) 重构性原则：所有的数据片段必需能重构( 逆操作) 成全局关系。 因为数据片段是分布式数据库的基本关系，通过重构操作才能建立全局数据 库。这是分布式数据库的基本要求。 ( 3 ) 不相交原则：不相交原则不是必需的，但是有这条原则可以使划分 不致引起太复杂的冗余。划分时不相交，则分配的冗余可以得到控制。有时 允许键属性相交，使重构操作简单w 。 2 6 2 分布式数据库的数据分配 数据分配的目的是通过一定的冗余片段在各节点上的分布，提高系统的 可靠性，缩短局部应用的响应时间，尽可能地提高数据的安全性，减少系统 的数据通信代价。 1 数据分配准则 ( 1 ) 处理局部性：数据分布应以尽量满足局部操作为主，即尽量使大部 分操作在局部场地完成。这就要求划分数据，并将数据片段尽量放置在访问 它们最频繁的场地或最接近的场地上，以减少通信开销。可以按存取方式将 应用分成局部存取和远程存取两类，一旦应用的源场地己知，则存取的局部 性与远程性只依赖于数据的分布。最好的完全局部化应用是请求完全在原场 地执行的应用。若处理的局部性高，则系统的可用性与可靠性也高，而且能 减少远程通信与系统控制代价，缩短响应时间，从而提高系统性能。 ( 2 ) 数据可用性和可靠性：尽量提高数据检索应用的可靠性，减少因数 据检索和更新不同步造成的“脏数据”或“过时数据”。尽可能提高系统的 可用性，使系统的管理和存储代价降低。 ( 3 ) 工作负荷分布均匀性：使各节点的负载( 各节点所担负的全局应用 1 4 哈尔滨下程大学硕士学位论文 和局部应用的规模) 均匀化，尽量提高系统的并行处理能力，但这有可能降 低处理的局部性，增加系统的通信开销。 一般情况下，上述的三个准则很难同时满足，应该根据具体的客户需求 和系统的主要目标，以一个为主要目标，其它的可以作为约束条件m ，。 2 。数据分配类型 ( 1 ) 集中式：数据有划分，但是划分后的逻辑片段依然完全集中在一个 节点，即有分片无分配，且没有数据副本存在。严格说来，这不能算作是分 布式数据库； ( 2 ) 划分式：数据按应用需求和来源，分布在各个节点上，彼此之间没 有重复数据； ( 3 ) 全重复式：每个节点都有一个全部数据的副本，可以完全做到数据 检索的局部访问，但更新代价太大： ( 4 ) 部分重复式：分片后的逻辑片段接用户需求和应用需要分配，需要 共享的片段通过数据复制产生副本放置到不同的节点，私有的片段只放置在 需要的节点上n ”一。 表2 1 中给出了各种数据分配类型的比较。 一 表2 i 数据分配类型的比较 数据分配类型集中式划分式全重复式 部分重复式 存储代价很小小很大大 检索代价很大很小很小 由更新检索 更新代价小很小很大 比确定 可靠性 很差 差 好般 复杂性很低低一般高 灵活性很小小一般大 体现d d b s 的特点无不充分一般充分 数据分布引起的问题无少一般多 常用的数据分配方法有非冗余分配方法和冗余分配方法两种。 ( 1 ) 非冗余分配方法是将每个数据片段都无冗余地分配到网络中的一个 场地上，这种方法比较简单。常用的非冗余分配方法是最佳适应法m ，。 ( 2 ) 冗余分配方法允许将一个数据片段同时分配到多个不同的场地上， 哈尔滨工程大学硕士学位论文 这种分配方法由于涉及到查询或更新时选择哪一个副本的问题，同时，每个 数据片段的冗余度也是一个变量，所以比较复杂。常用的冗余分配方法有选 择所有收益场地法和添加副本法m 一。 本文将要提出的分配策略，主要是从数据片段的更新检索比( u q ) 出 发：对于u q l 的数据片段，尽量集中管理，以减少为 保持多个副本之间一致性而付出的更新代价m ，。 2 7 本章小结 这一章主要讲述了分布式数据库系统的基础理论和相关概念。首先对分 布式数据库和分布式数据库系统的定义、分布式数据库系统的特点、环境及 模式结构进行了介绍，然后着重对分布式数据库系统设计的目标、策略以及 数据分片和数据分配等概念进行了较详细的介绍。本章将本文的焦点逐步由 分布式数据库应用大环境聚焦到分布式数据库中的数据分配问题，详述了数 据分配准则和数据分配类型，并提出了本文所要提出的策略的出发点，为理 解后续章节中的相关理论奠定了基础。 1 6 哈尔滨1 ：程大学硕+ 学位论文 第3 章分布式数据库设计中的数据分配问题 在分布式数据库的设计中，数据分片和数据分配都是极为重要的环节。 其中数据分配问题能否成功解决直接影响着整个分布式数据库的可用性、可 靠性和系统效率。本章将详细讨论分布式数据库的数据分配问题，列举出四 种典型的数据分配方法并对每种方法进行优缺点分析。 3 1 分布式数据库中的数据分配问题 数据分配问题其实就是要解决以一种怎样的方式将所有的数据片段分布 到分布式数据库系统的各个站点上，使得代价最小，这是分布式数据库的设 计者们在考虑数据分配问题时的不变的准则。假设有卅个数据分片和一个站 点，在既考虑非冗余分配也考虑冗余分配的情况下共有( 2 4 1 ) j 种分配方法， 其中只有一种是最优的分配方法。很明显，当掰和打的值都较小时，使用穷 举求解法是可行的，但是当m 和r 的值都较大时，穷举求解法是无能为力的。 这时，摆在设计者面前的是一个n p 完全问题- 。当然很多时候设计者并不要 求一定要求出最优解，近似最优解也可以满足设计需要m 。但是即便如此， 数据分配问题本身仍旧是复杂而庞大的。所以，从理论上说，分布式数据库 设计中的数据分配问题都应采用启发式算法来得到解决。 在分配数据片段时，也可能有其它因素需要考虑。比如，均衡系统的负 载，提高分布式数据库的可用性，增强系统的可靠性以及减少存储数据的代 价等。在进行数据分配时，需要根据实际的情况选择一个因素来优先考虑。 关系型分布式数据库是由一组关系组成的，这组关系在逻辑上是一个整 体，在物理上是由全局关系划分出的若干个子关系( 片段) ，这些片段必须 冗余或非冗余地被分别存储在分布式数据库系统中的各个节点上。 3 1 1 数据分配问题的描述 在深入分析分布式数据库数据分配问题之前，先对数据分配问题作如下 哈尔滨丁= 程大学硕十学位论文 定义：设有一个由站点集转( s i ，& ，) 构成的网络，该网络上运行 一个事务集弘( 乃，乃，死) ，存储着一个片段集，k ( 一，乃，一) 。 按照一定的方式将每个片段r 的不同副本分配到不同的站点& 上的分配方 案，表示为a f ，p ，就是所谓的片段分配问题。 3 1 2 数据分配方法优劣的度量 关于优化通常有两个度量标准。 ( 1 ) 最小代价：代价函数包括在节点( s ) 存储每个片段乃( 乃 e f ) 的代价；在节点& 检索处理片段毋的代价：在所有存储片段e 的节点 上的更新处理代价； ( 2 ) 性能：两个著名的标准是最小化响应时间和最大化每个节点的系统 吞吐量u t 。 一般来说，不同的分配方法所使用的最优化模型中采用不同的优化度量， 但是严格来说，考虑最优化问题应该兼顾优化和性能两个因素，即分配结果 能使分布式数据库系统达到最小的响应时间或最大系统吞吐量而同时又保持 处理代价最小。然而这样兼顾优化和性能的模型至今尚未开发出来，究其根 本原因就是复杂性。 代价最小的分配问题的描述如下： 设分配方案a f ，p 存在存储代价$ c o s