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

分布式数据库的数据分配算法
1
主要内容
一、数据分配问题的提出
二、典型数据分配算法分析与对比
三、数据分配的研究趋势
2
一、数据分配问题的提出
在分布式数据库系统的设计中,数据分配主要是解决数据片段在分布式系统各节点上的分布。当然,解决方案应满足一定的优化标准,其实质是要得到一个最优分配方案。不过这样的问题因其复杂性太大被列为NP难题。在很多实际应用中,其实也并不一定要得到最优分配方案,一个足够接近最优分配方案的近似最优分配方案往往也可以满足要求。
国内外学者在数据分配的基本原则上是有两点共识的。
(1)数据应尽可能靠近要使用它的站点,并用负载平衡方法找出一个系统性能的全局优化。
3
(2)检索事务应尽量局部化;更新事务所涉及的数据片段的副本不宜过多,以减少保持数据一致性的代价。对于分布式数据库系统的应用需求和理论研究,国外都要领先于国内。对于数据分配问题的研究,国外学者在基础理论方面贡献颇多,如文献[8] 中提出的方法对于避免由于系统I/O瓶颈造成的效率下降提供了帮助。
国内学者在对该问题的研究上虽然起步较晚,但是也逐步跟上领先者的步伐,获得不少研究成果,如“启发式试消副本法”在降低分配算法的复杂度方面有很好的效果。
4
二、典型数据分配算法分析与对比
对于分布式数据库的数据分配方法,国内外学者的研究从未间断,下面列举四个典型方法。
分组局部优化法
分组局部优化的数据分配方法的算法思想为:将片段等分成若干个组(最后一个组的片段数可能少于前面组的片段数),设定一个初始分配L0。首先对一个组获得各种分配方案而不考虑其它组的分配,以此获得整体n个片段的各种分配方案,从中选择最优的,得到该组的局部最优。按照这个方法对余下的每个组进行分配得到各组的局部优化,由此获得一个总体的优化分配方案L1,比较L1和L0的代价误差,若误差未满足条件,再对上述过程进行迭代处理直至误差满足条件。
5
优缺点:分组局部优化中代价公式本身是很复杂的,难于理解。它既考虑了单目查询和双目查询,又考虑了本地处理代价和通信代价,要确定哪些是单目运算,哪些是双目运算很不容易,公式的复杂性很高,算法的可操作性差,不利于实际应用。
6
启发式添加副本法
该方法的主要思想是:设待分配的数据片段为Fj,首先用最佳适应法确定一个非冗余的最佳分配方案,然后再分别计算在剩余的场地中的一个场地上增加片段Fj的副本后整个系统的总费用,找出其中的最小费用,如果该费用大于增加Fj副本前的最小费用,则停止计算;否则,决定在相应的场地上增加数据片段Fj的副本。这样一直计算下去,直到找出最小费用为止。
7
优缺点:添加副本法是一种典型的启发式方法。它不但考虑到副本之间的相互影响,还考虑到随着副本的增加而带来的费用上升问题。从总的代价因素来考虑,增加副本数与提高系统的可靠性之间不是线性关系。从以往经验来看, 当副本数为2或3时,系统费用较理想。当副本数进一步增加时,系统费用不一定会降低,甚至有可能上升.
在此方法中,形成初始分配的方法是采用非冗余最佳适应法。非冗余最佳适应法非本文的主要参考,不作详述,只介绍一下它的优缺点。
8
用非冗余最佳适应法进行数据分配,存储代价最小,但是系统的可用性、可靠性和数据的访问效率不高,并且没有体现出分布式数据库系统的优越性。另外,假设数据片段的数量为m,站点数为q,则非冗余最佳适应法在每次决定分配某个数据片段之前要计算q次全局代价,然后将q个结果进行比较。随着已分配的数据片段的增多,每次的计算量会越来越大。这种不使用启发式公式而用大量的计算的方式,严重影响了初始分配的效率,也给整个启发式添加副本法的算法复杂性带来不利的影响。
9
2. 3 启发式试消副本法
启发式试消副本法的基本思路是:对检索应用,可以按照应用发出的原始站点将目标片段放在应用所在站点而使得检索最优。这样一来,每个数据片段可能有多个副本分布在网络的多个站点上。对更新应用,则会因为要维护多个站点上片段多副本的数据一致性而增加开销。因此,第一步仅考虑检索需求片段的完全本地化,即先保证检索应用最优,得到初始分配,显然这种初始分配对更新应用是最坏的。然后再考虑更新应用的影响,逐步消除片段副本数以减小更新的通信代价。
10