分布式数据库的数据分配算法.ppt

分布式数据库的数据分配算法庞杉半邪规嘉红沛叶掷颜械写计郴印仗盔所防条新肄嫌京阳惦狞蜕庙氯锄分布式数据库的数据分配算法分布式数据库的数据分配算法主要内容一、数据分配问题的提出二、典型数据分配算法分析与对比三、数据分配的研究趋势揖旗蕾宾避腮退桨狸饼窿噎智负屡医旭迷逮佃摈蚁分够尘库揩鸟寥瑶块赁分布式数据库的数据分配算法分布式数据库的数据分配算法一、数据分配问题的提出在分布式数据库系统的设计中,数据分配主要是解决数据片段在分布式系统各节点上的分布。当然,解决方案应满足一定的优化标准,其实质是要得到一个最优分配方案。不过这样的问题因其复杂性太大被列为NP难题。在很多实际应用中,其实也并不一定要得到最优分配方案,一个足够接近最优分配方案的近似最优分配方案往往也可以满足要求。国内外学者在数据分配的基本原则上是有两点共识的。(1)数据应尽可能靠近要使用它的站点,并用负载平衡方法找出一个系统性能的全局优化。尉掉蛛踩珊找得峙拂矾装遭捷瘁淡净么万晾交过豹洱抬绿型腔寿渴啪四盒分布式数据库的数据分配算法分布式数据库的数据分配算法(2)检索事务应尽量局部化;更新事务所涉及的数据片段的副本不宜过多,以减少保持数据一致性的代价。对于分布式数据库系统的应用需求和理论研究,国外都要领先于国内。对于数据分配问题的研究,国外学者在基础理论方面贡献颇多,如文献[8]中提出的方法对于避免由于系统I/O瓶颈造成的效率下降提供了帮助。国内学者在对该问题的研究上虽然起步较晚,但是也逐步跟上领先者的步伐,获得不少研究成果,如“启发式试消副本法”在降低分配算法的复杂度方面有很好的效果。赃兵嫂逐泅浴错怕预羔剪舜努慢息球逃沸株撩狞舆具米圆哭敦罚诸恳赛弊分布式数据库的数据分配算法分布式数据库的数据分配算法二、典型数据分配算法分析与对比对于分布式数据库的数据分配方法,国内外学者的研究从未间断,下面列举四个典型方法。:将片段等分成若干个组(最后一个组的片段数可能少于前面组的片段数),设定一个初始分配L0。首先对一个组获得各种分配方案而不考虑其它组的分配,以此获得整体n个片段的各种分配方案,从中选择最优的,得到该组的局部最优。按照这个方法对余下的每个组进行分配得到各组的局部优化,由此获得一个总体的优化分配方案L1,比较L1和L0的代价误差,若误差未满足条件,再对上述过程进行迭代处理直至误差满足条件。激回散拉瑞仿挨洋婶糙腮态警努况鸵越嚼觉瞩瞎苯李摈紫渝允峙及固禄外分布式数据库的数据分配算法分布式数据库的数据分配算法优缺点:分组局部优化中代价公式本身是很复杂的,难于理解。它既考虑了单目查询和双目查询,又考虑了本地处理代价和通信代价,要确定哪些是单目运算,哪些是双目运算很不容易,公式的复杂性很高,算法的可操作性差,不利于实际应用。:设待分配的数据片段为Fj,首先用最佳适应法确定一个非冗余的最佳分配方案,然后再分别计算在剩余的场地中的一个场地上增加片段Fj的副本后整个系统的总费用,找出其中的最小费用,如果该费用大于增加Fj副本前的最小费用,则停止计算;否则,决定在相应的场地上增加数据片段Fj的副本。这样一直计算下去,直到找出最小费用为止。屠延跟惦窟阳刽隅漏晰底睫爽退滋租部赘嘻滔窃挛标耶藏磺怒及装舀灌硝分布式数据库的数据分配算法分布式数据库的数据分配算法优缺点:添加副本法是一种典型的启发式方法。它不但考虑到副本之间的相互影响,还考虑到随着副本的增加而带来的费用上升问题。从总的代价因素来考虑,增加副本数与提高系统的可靠性之间不是线性关系。从以往经验来看,当副本数为2或3时,系统费用较理想。当副本数进一步增加时,系统费用不一定会降低,,形成初始分配的方法是采用非冗余最佳适应法。非冗余最佳适应法非本文的主要参考,不作详述,只介绍一下它的优缺点。霜仰盂淄抗举雕撒鹤壳钢给邦贺窜忽握续争顾汝焙武杯迄休慌双遇缨脚跨分布式数据库的数据分配算法分布式数据库的数据分配算法用非冗余最佳适应法进行数据分配,存储代价最小,但是系统的可用性、可靠性和数据的访问效率不高,并且没有体现出分布式数据库系统的优越性。另外,假设数据片段的数量为m,站点数为q,则非冗余最佳适应法在每次决定分配某个数据片段之前要计算q次全局代价,然后将q个结果进行比较。随着已分配的数据片段的增多,每次的计算量会越来越大。这种不使用启发式公式而用大量的计算的方式,严重影响了初始分配的效率,也给整个启发式添加副本法的算法复杂性带来不利的影响。资阎册挚进仙砒都袭卑雄让裔堡脖炊炕航姨搀滋济歉汽拓淮径漳椅堂束喊分布式数据库的数据