（计算机系统结构专业论文）分布式数据库中数据分配方法的研究.pdf

重庆大学硕士学位论文 中文摘要 摘要 计算机网络的日益发展和普及以及跨地域分布的企业组织机构使得数据的存 储和应用越来越分布化。分布式数据库( d i s t r i b u t e dd a t a b a s e ) 技术就是在这种 环境下应运而生的。基于这种技术的系统在可靠性、可用性和时间响应方面较传 统的集中式数据库系统有更多的优越性，因此在实际中有着更广泛的应用。 分布式数据库系统中数据不是集中存放，而是根据实际应用的需要分布于网 络的各个节点上，因此存在数据的划分问题，即数据的逻辑分割( 分片) 和片段 的物理分配问题。在分布式数据库系统中需要冗余的数据，即增加数据副本以提 高数据处理的本地性和效率，同时还可以增加系统的可靠性和可用性。分布式数 据库设计的主要目标之就是数据处理的本地性，即使数据尽可能存放在使用它 们的应用所在的节点上，从而减少远程访问所需的通信代价。 怎样合理地分布数据，这是数据分配设计需要考虑的问题。数据分配问题对 整个应用系统的改进、数据的可用性、提高d d b 的效率和可靠性有很大影响，数 据片段分配得好，整个系统的性能才会处于一个良好的状态。国内外专家和学者 一直致力于基于分布式数据库的数据分配问题的研究，由于其复杂性，一直还没 有找到一个兼顾代价和性能最优的通用数据分配方法。虽然大量的研究学者也提 出了一些分配模型和算法，但是大多数模型和算法非常复杂难于理解，因而很难 应用于实际环境。本论文主要基于文献中提出的得益一代价启发式分配方法 1 ”，对 其不合理之处进行改进，提出了一种启发式试消副本片段分配方法。 在该方法中，首先归纳出影响选择统计信息的几个主要因素，然后确定以事 务处理通信代价为主的代价公式，最后，提出了“启发式试消副本分配算法”，该 算法第一步通过只满足只读的本地性，确定一个最优初始分配；第二步考虑在初 始化片段分配表基础上试消副本，以在只读事务和更新事务代价之间获得折中， 消除副本的条件为只读事务和更新事务总代价是否减少，最终目的是获得一个对 只读和更新总代价最小的分配方案。最后通过实验实现了算法，实验表明该方法 能够在一定程度上减小解空间，并且简单、易行，获得的分配方案也更合乎实际。 关键词：分布式数据库，片段分配，统计信息，代价公式，启发式分配算法 重庆大学硕士学位论文英文摘要 a b s t r a c t t h es t o r a g ea n da p p l i c a t i o no fd a t ab e c o m ed i s t r i b u t e d i n c r e a s i n g l yw i t h t h e d e v e l o p m e n to fc o m p u t e rn e t w o r ka n dd i s t r i b u t e dl o c a t i o no ft h ec o r p o r a t i o n sa n d o r g a n i z a t i o n s d i s t r i b u t e dd a t a b a s et e c h n o l o g ya p p e a r e db a s e do nt h a te n v i r o n m e n t s t h a tt e c h n o l o g yh a sm o r ea d v a n t a g e st h a nt h a ti nt r a d i t i o n a lc e n t r a l i z e dd a t a b a s ei n a s p e c to f r e l i a b i l i t y , u s a b i l i t ya n dt i m er e s p o n s e ，s oi ti sa p p l i e dw i d e l yi nt h er e a lw o r l d d a t ai sn o ts t o r e d c e n t r a l l yb u t t ob ed i s t r i b u t e di nd i f f e r e n ts i t e s a c c o r d i n gt o a p p l i c a t i o nr e q u i r e m e n t s ，s od a t as h o u l db ep a r t i t i o n e di nd i s t r i b u t e dd a t a b a s es y s t e m t h a ti sf r a g m e n t a t i o na n df r a g m e n ta l l o c a t i o ni s s u es h o u l db ec o n c e r n e di nd i s t r i b u t e d d a t a b a s es y s t e m r e d u n d a n td a t ac a ni n c r e a s el o c a ld a t ap r o c e s s i n g ，i m p r o v es y s t e m e f f i c i e n c y , r e l i a b i l i t ya n du s a b i l i t y o n eo fg o a lo fd i s t r i b u t e dd a t a b a s ed e s i g ni sd a t a p r o c e s s i n gl o c a l l y , n a m e l ya l l o c a t i n gf r a g m e n t st ot h ei s s u i n gs i t e ss ot h a tt h er e m o t e c o m m u n i c a t i o nc o s tw i l lb er e d u c e d h o wt oa l l o c a t ef r a g m e n t sr a t i o n a l l ym u s tb ec o n s i d e r e di nd i s t r i b u t e dd a t a b a s e s y s t e m ，f r a g m e n ta l l o c a t i o ni s s u eh a sas i g n i f i c a n ti m p a c to nt h es y s t e mp e r f o r m a n c e , u s a b i l i t y , e f f i c i e n c y a n dr e l i a b i l i t y s y s t e m p e r f o r m a n c ei s w e l l o n l y i f f r a g m e n t a l l o c a t i o ni sw e l l r e s e a r c h e r sb o t hd o m e s t i ca n do v e r s e a sh a v eb e e nd o i n g r e s e a r c ho n f r a g m e n ta l l o c a t i o ni nd i s t r i b u t e dd a t a b a s es y s t e m ，b u tag e n e r a lf r a g m e n ta l l o c a t i o n m e t h o do fc o m b i n i n g o p t i m a l c o s ta n d p e r f o r m a n c e h a sn o tb e e nf o u n df o ri t s c o m p l i c a t i o n a l t h o u g hal a r g ea m o u n to f r e s e a r c h e r sh a v e p r o p o s e dm a n ym o d e l sa n d a l g o r i t h m sd e s i g n e dt oa l l o c a t ef r a g m e n t s ，m o s to f t h e i rm o d e l sa n da l g o r i t h m sa r ev e r y c o m p l i c a t e d a n dn o tw e l lu n d e r s t o o d t h u s ，i ti sd i f f i c u l tt ou s et h e mi nar e a l e n v i r o n m e n t h e r e ，ip r o p o s e ah e u r i s t i cm e t h o dc a l l e dr e m o v ef r a g m e n t c o p i e s a l l o c a t i o nb a s e do nr e s e a r c h i n ga n dm o d i f y i n gt h eb e n e f t t - c o s th e u r i s t i cf r a g m e n t 口| l o c d t i o nm e t h o d 1 6 1 1 1 1 t h i s p a p e r , f i r s t l y , s o m ek e y f a c t o r si n f l u e n c e dh o wt os e l e c ts t a t i s t i c a l i n f o r m a t i o ni s c o n e l u d e d ，t h e n ac o m m u n i c a t i o nc o s tf o r m u l a sf o rt r a n s a c t i o n p r o c e s s i n g i sd e r i v e d , f i n a l l y , ah e u r i s t i cr e m o v e f r a g m e n t c o p i e sa l l o c a t i o na l g o r i t h mi s p r o p o s e d t h ea l g o r i t h m h a st w os t e p s i nt h ef i r s ts t e p ，t h ef r a g m e n ta l l o c a t i o nt a b l eb y o n l yc o n s i d e r i n gt h er e t r i e v a lr e q u e s t si s s u e db yt r a n s a c t i o n si si n i t i a l i z e dw i t h o u ta n y c o m m u n i c a t i o nc o s tb ya l l o c a t i n gi t st a r g e tf r a g m e n t st oi t si s s u i n gs i t e mt h es e c o n d s t e p ，t h ei s s u et h a tt ob ec o n s i d e r e di st or e m o v ef r a g m e n t sc o p i e sf r o mt h ei n i t i a l i z e d i i 里堕奎兰堡主堂垡笙苎 兰墨翌堕翌 a l l o c a t i o ns u c hm a tt h ec o m m u n i c a t i o nc o s t w i l lb er e d u c e df o ra l lr e q u e s t s a tl a s t , t h e m e t h o di sr e a l i z e db ye x p e r i m e n t i th a s b e e np r o v e dt h a ti ti ss i m p l e ，c o m p r e h e n s i v e ， a n dc a nr e d u c et h es c o p eo fs e e k i n gs o l u t i o n , t h e r e s u l tc a nm o r er e f l e c tt h er e a lw o r l d k e y w o r d ：d i s t r i b u t e 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 ，s t a t i s t i c a l i n f o r m a t i o n ，c 0 8 t f o r m u l a s ，h e u r i s t i c a l l o c a t i o na l g o r i t h m i i i 重庆大学硕士学位论文1 绪论 i 绪论 1 1 论文选题及其研究意义 数据库技术和计算机网络技术的结合使数据库技术的发展进入了一个新的阶 段分布式数据库( d i s t r i b u t e dd a t a b a s e ) 阶段。分布式数据库系统是分布或 分散存放在许多台计算机上的数据的集合，它是一个逻辑上单一的、集中管理的 数据库，但物理上却存放在多个场地上，既允许局部的数据访问，同时又实行全 局管理。一个完全的分布式数据库系统能够随时随地提供可靠的信息，用户可以 随时灵活访问信息而不必关心数据存放的地点和方法。分布式数据库能迅速推广 应用极大地依赖于它的效率，和集中式数据库不同的是，在分布式数据库系统中 数据不是集中存放，而是根据实际应用的需要分布于网络的各个节点上。 相对于集中式数据库技术而言，它能够更好地适应当今广泛分布的企业组织 结构，基于这种技术的系统更加可靠，对需求更能够做出及时的响应。更重要的 是，目前许多计算机应用天生就是分布式的，比如，依托于i n t e r n e t 的电子商务， 一些如新闻点播的多媒体应用等。因此，从一个更广阔的视角来看，分布式数据 库技术在处理一些更大型更复杂的问题时，能克服集中式数据库技术的固有缺陷， 提供一个更方便、容易和高效的技术支撑。分布式数据库系统适合数据处理量大、 原有数据库服务器的存储容量或处理能力已不能适应发展的需要、或数据分散在 不同物理位置的单位使用。对于已有各种各样数据库的单位而言，采用分布式方 法，把运行在各混合系统上的现有数据库合并起来，自上而下地集成一个单一的 分布式数据库，可以节省单位在数据库软件和应用软件方面的投资。 在国外，已有不少企事业单位应用分布式数据库技术进行管理或信息交流。 b c f ( b u r l i n g t o nc o a tf a c t o r y ) 制衣厂废弃了大型机集中式数据库系统，改用 u n i x 分级分布式数据库系统，遍布全国的约2 0 0 个零售店由网络连接起来，并在 其数据中心设置一个中央事务处理系统，各零售店与数据中心只需交换数量很少 的文件，减少了广域网的传输量，取得了显著的效益”。 在我国，由于生产发展水平的限制，企事业单位的规模还不能和国外比美， 但人们已经意识到分布式数据库系统的优越性，基于分布式数据库系统的应用也 日渐增多。可以预见，随着社会、经济和技术的发展，在大型企事业机构、大型情 报信息单位、大型服务业等各个行业，分布式数据库系统将取代集中式数据库系统 而成为信息处理的主流。所以，有人称分布式数据库系统为“下一世纪的数据库”。 对于信息工作者们来说，有必要了解分布式数据库系统的原理和发展，并积极研 重庆人学硕士学位论文i 绪论 究分布式数据库系统技术对未来信息处理和信息服务的影响，以迎接信息社会的 到来。 在分布式数据库系统中，分布式数据库设计又是相对重要的个环节。相对 于集中式数据库设计而言，它更加复杂，主要是因为它和所处的环境和涉及到的 应用联系紧密。分布式数据库设计的主要目标之一是数据处理的本地性，即使数 据尽可能存放在使用它们的应用所在的节点，从而减少远程访问。但是实际情况 中，很少有数据和应用都被清晰划分和分配到某一特定节点的，更为一般的情况 是几个应用从不周节点或个应用由几个节点发出，访问同一数据。因此，在分 布式数据库系统中需要冗余的数据，即增加数据副本以提高数据处理的本地性和 效率，同时还可以增加系统的可靠性和可用性，这和集中式数据库系统中尽量避 免数据冗余不同。但是，数据冗余又会带来数据一致性问题，会增加数据同步更 新代价，所以在分布式数据库系统的数据分配设计中考虑的应该是在无冗余和全 复制之间找到一个折中。 分布式数据库设计包含数据逻辑分割( 分片) 和片段物理分配两个方面。分 片是将全局关系分割成一组片段关系；雨分配主要是解决片段关系在分布式系统 各节点上的分布。许多研究者在这方面都作了研究，如m t a m e ro z s u 和p a t t i c k v a l d u r i e z 【l j ，他们在其书( p r i l c i d l e so fd i s t r i b u t e dd a t a b a s es y s t e m s 中系统 阐述了分布式数据库设计问题：另外p e t e rm g a p e r s “，k a m a l a k a rk a r l a p l e m 等国外学者也致力于这方面的研究，经常有相关论文发表；国内象邵佩英“、王 于周”等学者同样在进行这方面的研究。从上可见，分布式数据库设计问题在分 布式数据库系统中是一个重要问题。 无论是数据分片还是片段分配设计都需要考虑实际环境和应用信息，对于片 段的划分，目前已有很多方法，不是本论文的主要论点，本论文主要论述数据分 配问题。分布式数据库分割了概念数据库，使数据存取本地化，这样做有几个潜 在的好处，因每个场地只处理数据库的一部分，可以缓解对c p u 、i o 以及内存等 系统资源的竞争：其次，本地化减少了远程访问延迟，访问延迟在广域网中经常 出现；再者，系统中因为有冗余数据，提高了系统的可靠性和可用性。然而和数 据本地化带来的好处并存的还有其带来的问题，那就是数据同步更新问题，数据 同步更新的系统开销以及对整个系统可靠性和可用性的影响同样是不可忽视的。 因此只有适当划分数据和分配数据才能从中得到减少竞争、减少通信开销以及获 得系统可靠性和可用性的最大好处。 由此可见，数据分配问题对整个应用系统的改进、数据的可用性、提高d d b 的效率和可靠性有很大影响，若数据片段分配得好，整个应用系统的性能、数据 2 重庆人学硕士学位论文 1 绪论 的可用性及d d b 的效率和可靠性都会处于一个良好的状态，否则，就体现不出d d b 的优越性。研究该问题的最终目的是希望得到一个使远程访问通信代价和局部事 务处理代价等总代价最小的最优解决方案，从而明确得出全局关系划分后的逻辑 片段应该放置的最佳场地。基于分布式数据库系统的数据分配研究具有相当的学 术及实用意义，它能为企业的运作和发展节约投入和增强竞争力。 1 2 国内外现状综述 数据分配主要是解决片段关系在分布式系统各节点上的分布。 简言之，数据分配问题就是给定一组数据片段，并针对这些数据片段的操作 及其使用频率，分配这组数据到网络的各个节点，使得总代价最小。讨论分配问 题，实质是要得到一个最优分配方案，即找到一个能最小化总代价同时又能维护 系统最优性能的分配方法，但是这样的方法因其复杂性太大被列为n p 难题。 分布式数据库系统中数据分配方法之所以复杂是由于数据分配和环境及应用 联系紧密，关于环境及应用的一些准确的统计信息( 不同研究者使用不同的统计 信息) 对分配方法及代价公式的建立及优化都有很大影响，归结起来它们是“1 ： ( 1 ) 数据库信息。 ( 2 ) 应用信息。 ( 3 ) 站点信息。 ( 4 ) 网络信息。 分配算法就是如何根据约束条件将数据分配到网络的各个节点上的策略和步 骤。传统的数据分配策略有非冗余分配和冗余分配两种： ( 1 ) 非冗余分配策略。即没有数据副本存在，每一个片段有且仅有一个拷贝。 用得最多的是最佳适宜法，其分配思想为根据代价公式将各片段分配到所需代价 最小的节点上。 ( 2 ) 冗余分配策略。即允许片段存在副本，同一数据片段的不同副本可以分 配到多个不同的节点上，这种方法由于涉及到只读和更新时选择哪一个副本及更 新时维护数据的一致性问题，比非冗余分配复杂。用得较多的有两种：选择所有 收益场地法和添加副本法，实质都是一种启发式方法。即首先使用非冗余分配， 然后计算每增加一个片段副本的得益和代价，若得益大于代价就复制副本，否则 不复制，这样一直下去，直到找到最小代价为止。 一般来说，在分布式数据库系统的数据分配设计中应该考虑冗余分配，否则 和集中式数据库系统一样，体现不出其分布的优越性，冗余分配通过在多个节点 上冗余存放同一个数据片段的多个副本来提高d d b 的可用性和可靠性，减少通信 3 重庆人学硕士学位论文j 绪论 代价和提高查询效率，这是非冗余分配做不到的。 如何度量最优分配，d o w d ya n df o s t e r 在j 9 8 2 年提出用两个标准来度量优 化： ( 1 ) 最小代价。这个代价函数包括在一个站点s j 存储每个片段f i 的代价；在 站点s j 只读f 。的代价；在所有存储f i 的站点更新f 。的代价以及数据通信代价，分 配问题就是企图找到一种分配模型使联合代价函数最小。 ( 2 ) 性能。设计分配策略需维护系统性能，有两个度量标准：最小化响应时 间和最大化每个场地的系统吞吐量。 在优化的度量问题上，国内外学者均偏向于代价优化，提出的优化函数也大 多基于代价函数。 文献 1 中提出的代价函数：m i n ( t o t a lc o s t ) 。其中t o t a lc o s t 函数包含阿 部分：查询处理和存储。 t o c = q p c , + s r c , k v 甄e qv s e s v 目e f 文献 1 4 中提出的代价函数：m i n ( u c o s t + q c o s t ) ，即使更新和查询代价最小。 文献 1 6 中提出的代价函数：m i n ( c c l o a d + c c p r o c ) ，其中，c c l o a d 为数据装 载的通讯代价；c c p r o c 为事务处理的通讯代价。 文献 1 9 中提出的代价函数：m i n ( c q i + c q 2 + c u ) ，c 。l 为单目查询的处理代价和 通讯代价之和；c 。2 为双且查询的处理代价和通讯代价之和；c 。为更新的处理代价 和通讯代价之和。 文献 2 5 1 中提出的代价函数：b ( f ，j ) = c n ( f ，j ) 一c y ( f ，j ) ，其中，b ( f ，j ) 是分配到节点j 的得益，c y ( f ，j ) 是分配片段f 到节点j 的局部代价，c n ( f ，j ) 是不分配片段f 到节点j 的局部代价。 从上面所列公式可见，数据的分配和一些统计信息密切相关，如何量化这些 统计信息，并将之全部考虑进一个分配模型( 目标函数) 中，是一个n p 难题。鉴 于此，一些启发式算法，如背包问题方案脚、分店技术m 、o 1 整数编程、事务 提交概率模型和一个通用算法来最小化处理代价”2 1 等被用来解决数据分配问题。 分布式数据库中的数据分配问题在理论上都是采用启发式算法和优化算法来解决 的。 作者在该论文中采用的方法的特点是简单、可行并易于理解，重在有实用意 义。 4 重庆大学硕士学位论文1 绪论 1 3 研究内容 本论文查询了大量文献，对不同的分配方法进行了分析，特别是“得益一代价 启发式分配方法”的分析，认为合理的选择统计信息和确定代价公式是分配算法成 功和可行的主要条件。 在此基础上归纳了影响选择统计信息的几个主要因素： ( 1 ) 统计信息本身的重要性。 ( 2 ) 统计信息获得的难易程度。 ( 3 ) 统计信息对代价公式复杂性的影响。 现实情况中并非所有的统计信息都容易获得，并非所有的统计信息对一个实 际系统都重要，如果获得一个统计信息的难度代价超过了考虑该统计信息对分配 的好处时，或者该统计信息对分配结果影响甚小时，忽略该统计信息不失为一个 减小复杂性的办法。 同时，通过对各种分配方法的分析，得出影响分配方案的性能的主要考虑因 素是通信代价。在合理选择统计信息的基础上确定了代价公式由初始化数据包时 延，发送数据时延，数据传播时延三部分组成。 最后，提出了“启发式试消副本数据分配方法”，该方法首先通过只满足只读 的本地性，确定一最优初始分配，再通过试消副本方法，减少副本数量，以在只 读事务和更新事务代价之间获得折中。该方法只选择最重要的几个统计信息进行 代价计算，以只读事务和更新事务总代价是否减少作为副本消除的条件，最终目 的是获得一个对只读和更新总代价最小的分配方案。该方法能够在定程度上减 小解空间，使分配方法简单、易行，获得的分配方案也更合乎实际。 通过分析和实验表明，该算法执行时间较小，实验结果也非常接近最优结果。 本文如下组织：第l 章介绍了论文研究的意义、分布式数据分配的研究现状 及研究内容；第2 章介绍了分布式数据库系统的些基础知识；第3 章着力介绍 了数据分配涉及的有关问题，对统计信息的重要性划分和量化做了详细讨论，介 绍了几个分配方法并给以评价；第4 章是论文的核心部分，对提出的启发式试消 副本分配方法涉及的关键技术、步骤进行了详细分析；第5 章针对前一章提出的 分配方法做了模拟实验，并对实验结果进行了对比分析。第6 章为结论。 1 4 本章小结 本章介绍了论文的选题背景，论述了论文选题的学术意义，介绍了分布式数 据库数据分配的研究现状以及论文的研究内容，最后阐述了本论文的主要内容和 各章节的内容安排。 5 重庆大学硕士学位论文2 分布式数据库系统基础 2 分布式数据库系统基础 2 1 分布式数据库系统定义 分布式数据库系统是计算机网络技术与数据库技术互相渗透和有机结合的产 物，在数据库研究领域中已有多年的历史。从概念上讲，分布式数据库是物理上 分散于计算机网络各节点，而逻辑上属于同一个系统的数据集合。具有数据独立 性、集中与自制相结合的控制机制、适当增加数据冗余、事务管理的分布性等特 点。系统强调节点的自治性而不强调系统的集中控制，且系统保持数据的分布透 明性。 2 2 分布式数据库系统环境 分布式数据库系统环境应是一个分布环境，即由多个计算机设备彼此用通汛设 备连接而成的计算机网络，并且把数据库内容渗透到网络环境中。它的主要组成 是节点，场地和通讯设备，以及支持节点场地通讯的网络通讯软件。如图2 1 所示。 闺2 1 分布式数据库环境 f i g 2 1a d i s t r i b u t e dd a t a b a s ee n v i r o n m e n t ( 1 ) 节点场地 节点是指具有主动处理能力的单一计算机( 包括那些有多个终端机或远程终 端机) 的部分；而场地是多台计算机组成的节点。 节点应包括一定的软、硬成分，硬件成分主要是计算机处理设备及网络接口 设备，配置可根据应用的需要设定。根据节点能力的大小，相应的软件配置亦有 不同。 6 重庆大学硕士学位论文2 分布式数据库系统基础 节点在正常情况下应是联网状态，即正常工作、发送命令、完成某种调度。 也可能是非联网状态，处于故障离网或维修中离网。联网或离网对于节点来说一 般是动态的。 ( 2 ) 通讯设备 通讯设备包括连接节点的物理链路和一组通讯协议。通讯设备应该知道每个节 点状态，每个节点状态连接的多种物理路径，以及节点发送报文的协议。通讯设 备的基本功能是在任何一个节点上运行个进程，可以向在此网络中任何其它节 点上运行的另一个进程发送消息或报文。进程发送或接收报文的方式可以是点到 点的，或是广播式的。 ( 3 ) 网络通讯协议 网络中任何两个节点要交换报文，其进程必须遵守某些规则才能得以实现。网 络报文的发送和接收规则称为网络通讯协议，协议规定两个节点的通讯只能在犀 层上进行逻辑对话。 2 3 分布式数据库系统结构 如图2 2 所示是分布式数据库的一种模式结构示意图，实际的系统根据其数据 独立性的不同要求，有不同的抽象层次。 图2 2 分布式数据库系统模式结构 f i g 2 2t h em o d e ls m 】c f u r eo f d i s l r i b u t e dd a m b a s e 重庆大学硕士学位论文2 分布式数据库系统基础 上图从整体来看，映像4 所在的层下面是集中式数据库的模式结构，代表了 各局部场地上的局部数据库系统的结构，映像4 所在的层上面是分布式数据库系 统增加的模式级别，下面仅就分布式数据库系统增加的模式级别做一简要介绍： ( 1 ) 全局外模式：它们是全局应用的用户视图，是全局概念模式的子集。 ( 2 ) 全局概念模式：它定义分布式数据库中数据的整体逻辑结构。全局橛念 模式中所用数据模型应该易于向其它层次的模式映像。通常采用关系模型。 ( 3 ) 分片模式：每一个全局关系可以分为若干不相交的部分，每一个部分称 为一个片段。分片模式定义片段及全局关系到片段的映像。这一映像是一对多的， 因为一个片段来自一个全局关系，而个全局关系对应多个片段。 ( 4 ) 分配模式：片段是全局关系的逻辑部分，一个片段在物理上可以分配到 网络的不同节点上，分配模式定义片段存放位置。分配模式的映像类型确定了分 布式数据库是冗余的还是非冗余的。若映像是一对多的，即一个片段分配到多个 节点存放，则是冗余的：若映像是一对一的，则是非冗余的。根据分配模式提供 的信息，一个全局查询分为若干子查询，每一子查询所要访问的数据属于同一场 地的局部数据库。由分配模式到各局部数据库的映像即是把存储在局部场地的全 局关系或全局关系的片段映像为各局部概念模式。局部概念模式采用局部场地的 d b m s 支持的数据模型。分片模式和分配模式及其对应的映像使分布式数据库系 统具有了分布透明性。 2 4 数据分布的相关概念 数据应当存储到网络的哪些节点上，这是分布式数据库设计中应该考虑的数 据分布问题，下面就数据分布的有关概念作一介绍。 2 4 1 全局关系模式及关系 全局关系模式是一个多元组r ( u ，d ，d o m ，i ，f ，q ，s ) ，其中r 是关系 名；u 是组成r 的有限属性集；d 是u 中属性的值域；d o m 是属性列到域的所有 映射的集合；i 是一组完整性约束条件；f 是属性间的一组数据依赖；q 是关系所 满足的限定条件：s 是关系的分布结构。一个关系r 是相应于全局关系模式r ( u ， d ，d o m ，i ，f ，q ，s ) 按分布结构s 组织起来的从属性集u 到值域d 上所有满 足q 的映射的集合，其中每个元素叫做元组，每个关系有主键k 。可以把全局关 系简记为r ( u ，q ，s ) 。 全局关系模式及关系是两个不相同的概念。关系模式描述关系的结构及语义 约束，如果是全局关系模式，还有按一定谓词条件q 划分成子关系模式和子关系 物理存储模式的约束；关系是关系模式在某时刻的实例。 重庆大学硕士学位论文2 分布式数据库系统基础 2 4 2d d b 中的三种关系 ( 1 ) 全局关系：在分布式数据库中，逻辑上是一个整体，并对用户可见的关 系。全局关系是由若干子关系的逻辑片段和物理片段按分布结构s 组织起来的。 在物理上全局关系是不存在的，它只具有逻辑上的意义。 ( 2 ) 逻辑片段：是指这个关系在d d b 中实际存在的关系，它是基本关系， 不需要由其它关系组成，它是全局关系在某个场地的子关系的逻辑成分。全局关 系与逻辑片段有一定的映射关系，就是分片模式。 ( 3 ) 物理片段：指这个关系在某个场地的逻辑片段，即某个场地的基本关系。 物理片段由分配模式定义。逻辑片段映射为某个场地物理片段，亦可称为某个场 地的副本。它们的映射关系为l ：l 或1 ；n ，即一个片段可以存放在一个场地或几 个场地。 总之在d d b 中，一个全局关系由分片操作分解成几个逻辑关系( 逻辑片段) ； 一个逻辑关系在几个场地上放置( 由分配模式定义) 就产生了几个物理关系( 物 理片段) 。 2 4 3d d b 中的三种数据库 ( 1 ) 全局数据库g d b ：与全局关系模式对应的数据库，它是虚拟的数据库。 ( 2 ) 逻辑数据库l 9 0 8 ：由所有基本关系组成的数据库。 ( 3 ) 物理数据库p d b ：由所有物理片段组成的数据库。 它们之间有如下关系： 分片模式分配模式 g d b + l g d b p d b 2 4 4 分片模式( f s ) 分片模式( f s ) 将g d b 分解成l g d b 中的片段，即f s ( g d b ) = l g d b 。这种 操作还必须具有可逆性，即f s 1 ( l g d b ) = g d b 。 2 4 5 分配模式( a s ) 分配模式( a s ) 将l g d b 中的每个逻辑片段映射到p d b 的一组物理关系上，即 a s ( l g d b ) = p d b 。 2 4 6 分布结构s 关系r 的分布结构是有关r 被划分和分配的信息的集合。r 是物理关系，则 无需划分和分配，因此s = e o ；r 如果是逻辑关系，那么它还需分配场地，因此s 记载的是r 的分配信息：r 如果是全局关系，那么s 记载了r 如何分解成逻辑关系 和物理关系。 9 重庆大学硕士学位论文2 分布式数据库系统基础 2 5 数据库分布设计 分布式数据库设计中数据库分布设计包括数据库分片设计与片段分配设计， 这两者是紧密相关的。本节先讨论分布策略的标准，然后讨论如何进行片段划分 与分配。 2 5 1 数据库分布设计的目标 数据库分布设计应考虑咀下目标： ( 1 ) 可用性与可靠性。可靠的分布式数据库系统是指即使分布式计算环境失 败，仍能继续执行用户要求，同时不破坏数据库的一致性。分布式数据库系统由 多个节点构成，并且在各个节点上存放有数据的多副本，这样可将故障的影响限 制在使用故障节点数据的那些应用，而不会影响整个系统的工作，从而保证系统 的可靠性和可用性。 ( 2 ) 处理局部性。数据分却应以尽量满足局部操作为主，即使大部分操作在 局部场地完成。这就要求划分数据，并将数据片段尽量放置在访问它们最频繁的 场地或最接近的场地上，以减少通信开销。可以按存取方式将应用分成局部存取 和远程存取两类，一旦应用的原场地己知，则存取的局部性与远程性只依赖于数 据的分布。最好的完全局部化应用是请求完全在原场地执行的应用。若处理局部 性高，则系统的可用性与可靠性也高，而且能减少远程通信与系统控制代价，缩 短响应时问，从而提高系统性能。 ( 3 ) 存储代价。多个数据副本的分布受到各个节点存储能力的影响。在网络 中，可能有些节点可以专门用于数据存储，有些节点却不具有海量存储能力。虽 然，存储能力和应用的c p u 、i o 以及网络的传输费用相比不是很重要，但它仍然 是设计时应该考虑的一个因素。 ( 4 ) 负载分布。合理地分配工作负载于网络的各个场地，以便能充分发挥各 地计算机的能力和提高各应用执行的并行度。负载分布与处理局部性可能相冲突， 所以在数据分布设计时必须全面权衡。 设计时同时考虑上面各个因素是很困难的，这将会因为产生的模型很复杂而 不实用。通常，可以根据具体情况重点考虑其中的某些标准；或者采取分步考虑， 在初始设计时集中考虑至关重要的标准，然后再针对其它标准进行优化。 2 5 2 数据分布设计策略及评价 数据分布的方式有许多种，一般说来，可按整个数据库是集中存放在一个场 地还是分割开来散布到多个场地以及是否有数据副本存在等情况，组合成四种数 据分布方式，它们是： ( 1 ) 集中式。即整个数据库存放在一个场地上，且没有数据副本存在。严格 说柬，这不能算作是分布式数据库，因为数据库集中存放在一个场地上，其它场 1 0 重庆大学硕士学位论文2 分布式数据库系统基础 地都从该场地获得数据。存放数据库的那个场地相当于个数据库服务器，其它 场地相当于该数据库服务器的远程终端，它们对数据库的访问是通过远程登录访 问来实现的，因此这种方案属于客户月务器结构的集中式数据库。 集中式最主要的优点是简单，容易实现，所有的存取操作都在单一场地上进 行，这样数据一致性维护和并发控制都比较容易实现。但这种策略有很多缺点， 首先数据库的大小受限于中一山场地的硬盘空间可用性的大小。其次，所有操作都 在中心场地执行，其它场地都要通过网络访问中心场地，因此都有通信代价与时 间延迟，系统的并行处理也受限于中心场地的处理能力与速度，因而中心场地就 会成为“瓶颈”，这就进一步限制了系统的反应速度，另外中心场地也容易崩溃， 系统的有效性与可用性不高。例如，若通信系统失效，则数据库对任何远程场地 都无效；若中心场地出故障，则整个数据库系统失败。 ( 2 ) 重复式。即有多个数据库副本存在，每个场地上都有一个完全的数据库 副本存在。 这种方式的可用性、健壮性及效率相当高。这种可靠性高不仅体现在当个 或多个场地发生故障时数据库仍能有效运转，而且还表现在很容易恢复一个破坏 了的数据库副本，这只需简单地从另一个正常场地完全拷贝一数据库即可。由于 每个场地都有一个完全的数据库副本，用户的请求大都可以在本场地完成这有 助于提高响应速度，减少通信代价，使通信分布比较均匀。在只有读操作时，由 于不需要维护数据一致性，因此不需要场地间的同步通信，系统的可用性是很高 的。但是系统需要花费相当大的开销去维护数据库的一致性和运行并发控制。由 于一致性和并发控制的复杂性，这种策略不适合单请求的并行处理，但在各个场 地，不同请求可以异步地处理。如何保持数据的一致性，依系统的不同差别很大， 而且所承受的开销取决于所提供的数据的一致性的级别。当网络的一部分由于某 种原因而失效时，需要限制修改操作的执行以维护数据的一致性。因为，若允许 两个修改操作在不能实现同步的情况各自在不同的场地进行，则当系统恢复正常 以后，可能出现数据的不一致性。另外， 限于每个场地上硬盘空阉可用性的大小。 靠性高、数据库小、修改频率低的场合。 如同集中式策略一样，数据库的大小受 一般来说，这种策略比较适合于要求可 ( 3 ) 分割式。全局逻辑数据库被分割成许多片段，并且被分配到各个场地上， 但这些片段只有个拷贝。在对数据进行分割时，需要尽量按应用的要求进行分 割，一般来说，应以减少表间的联接为目的。同样进行数据分配时，也应尽量将 某一个场地经常存取的数据存放在相应的场地，这样可以减少网络开销。 分割式策略与集中式策略相比有几个明显的优点。其一是数据库的大小只受 重庆大学硕士学位论文2 分布式数据库系统基础 限于网络上作为整体可用的硬盘空间的大小，而不受限于某一场地的可用硬盘空 间的大小。其二是只读与更新均指向各自所要求数据的所在场地，而非指向一个 中心场地，数据库存取的局部性比例较大，所以通信代价较低。但另一方面，可 能有一个请求需要存取多个场地甚至全部场地的数据，这时由于需要访问相关场 地上的片段，因此网络开销可能比集中式更高，但若设计时分割标准合适且配合 恰当的分布原则，则出现这种情况应该是不多的。若分布式数据库管理系统支持 并行处理，则可进行并行处理，故响应速度比集中式要快。通信负载较均匀地分 布于整个网络，所以任何场地都对通信瓶颈口不敏感。数据库的有效性与可靠性 也比集中式要高，因为若部分或全部通信失效，或者一个或几个场地发生敌障， 不会导致整个系统完全失效，至少数据库部分可用。这种方案的性能、有效性和 可靠性与数据库访问的局部性相关，若一个存取操作几乎在一个场地进行，则说 数据库访问的局部性高，否则就低。而数据库访问的局部性跟设计时数据分布有 关。如果在设计时对数据库进行分片，可能造成每一个请求都要存取多个场地， 则其性能、有效性和可靠性会比集中式更低，因为多个场地出故障的概率较单独 某一个场地出故障的概率要大，这样只要有一个场地出故障，这个请求就不能执 行。一般说来，分割策略比较适合各场地硬盘空间有限、可靠性要求较高、或应 用的数据存取有一定的“分离性”，即能实现高的存取局部化程度的情况。 ( 4 ) 组合式。它是分割与重复的组合，每一场地可以有数据库的任何一部分。 这种策略兼有分割与重复式的一些特点，它的主要的优点是灵活。分割与分布的 策略及各片段重复的数目需要在各因素之间权衡，局部辅存与整个辅存之间、可 靠性与可用性、提高效率的方法及通信代价、同步与控制代价等要素综合折中权 衡。例如，重复可以提高存取的局部性，从而降低通信量，提高可靠性与可用性； 同时可以提高并行处理的可能性，故可缩短响应时间。分割时，可使常用的关键 性数据重复分布于所需的场地，不常用的数据可只存储一次，这样可降低存储量。 这种方式要着力解决的问题是通信与数据一致性维护，同时通信瓶颈仍然可能存 在。这种方式最灵活，同时实现起来也是最复杂的，因为影响系统性能、可靠性、 存取需求等的各种因素是彼此相关的，很难将其分割开来考虑。此外，分布式数 据库管理系统所支持的各种机构，数据库的使用方式等也是施加影响的因素。总 之，采用这种方式必需全面考虑各种因素，并进行权衡。 2 5 3 数据分片 数据分片是指将d d b 的全局关系划分成相应的逻辑片段( 逻辑关系) ，数据分 片有利于按照用户的需求较好地组织数据的分布，也有利于控制数据的冗余。数 据分片的方式基本上有水平分片、垂直分片、混合分片和诱导分片。其中水平分 1 2 重庆大学硕士学位论文2 分布式数据库系统基础 片和垂直分片是两种基本的分片方式。 ( 1 ) 水平分片 是将关系按水平方向以记录组划分为若干片段，实际上是关系的选择操作， 对r 关系的水平分片的片段是满足某- - n 词条件的子关系。该分片方式得到的片 段包含的数据为全局数据库的一些元组，水