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

1、分布式数据库的数据分配算法第1页，共18页，2022年，5月20日，10点10分，星期一主要内容一、数据分配问题的提出二、典型数据分配算法分析与对比三、数据分配的研究趋势第2页，共18页，2022年，5月20日，10点10分，星期一一、数据分配问题的提出在分布式数据库系统的设计中，数据分配主要是解决数据片段在分布式系统各节点上的分布。当然，解决方案应满足一定的优化标准，其实质是要得到一个最优分配方案。不过这样的问题因其复杂性太大被列为NP难题。在很多实际应用中，其实也并不一定要得到最优分配方案，一个足够接近最优分配方案的近似最优分配方案往往也可以满足要求。国内外学者在数据分配的基本原则上是有两

2、点共识的。 (1)数据应尽可能靠近要使用它的站点，并用负载平衡方法找出一个系统性能的全局优化。第3页，共18页，2022年，5月20日，10点10分，星期一 (2)检索事务应尽量局部化；更新事务所涉及的数据片段的副本不宜过多，以减少保持数据一致性的代价。对于分布式数据库系统的应用需求和理论研究，国外都要领先于国内。对于数据分配问题的研究，国外学者在基础理论方面贡献颇多，如文献8 中提出的方法对于避免由于系统IO瓶颈造成的效率下降提供了帮助。国内学者在对该问题的研究上虽然起步较晚，但是也逐步跟上领先者的步伐，获得不少研究成果，如“启发式试消副本法”在降低分配算法的复杂度方面有很好的效果。第4页，

3、共18页，2022年，5月20日，10点10分，星期一二、典型数据分配算法分析与对比 对于分布式数据库的数据分配方法，国内外学者的研究从未间断，下面列举四个典型方法。21 分组局部优化法分组局部优化的数据分配方法的算法思想为：将片段等分成若干个组(最后一个组的片段数可能少于前面组的片段数)，设定一个初始分配L0。首先对一个组获得各种分配方案而不考虑其它组的分配，以此获得整体n个片段的各种分配方案，从中选择最优的，得到该组的局部最优。按照这个方法对余下的每个组进行分配得到各组的局部优化，由此获得一个总体的优化分配方案L1，比较L1和L0的代价误差，若误差未满足条件，再对上述过程进行迭代处理直至误

4、差满足条件。第5页，共18页，2022年，5月20日，10点10分，星期一优缺点：分组局部优化中代价公式本身是很复杂的，难于理解。它既考虑了单目查询和双目查询，又考虑了本地处理代价和通信代价，要确定哪些是单目运算，哪些是双目运算很不容易，公式的复杂性很高，算法的可操作性差，不利于实际应用。第6页，共18页，2022年，5月20日，10点10分，星期一22 启发式添加副本法该方法的主要思想是：设待分配的数据片段为Fj，首先用最佳适应法确定一个非冗余的最佳分配方案，然后再分别计算在剩余的场地中的一个场地上增加片段Fj的副本后整个系统的总费用，找出其中的最小费用，如果该费用大于增加Fj副本前的最小费

5、用，则停止计算；否则，决定在相应的场地上增加数据片段Fj的副本。这样一直计算下去，直到找出最小费用为止。第7页，共18页，2022年，5月20日，10点10分，星期一优缺点：添加副本法是一种典型的启发式方法。它不但考虑到副本之间的相互影响，还考虑到随着副本的增加而带来的费用上升问题。从总的代价因素来考虑，增加副本数与提高系统的可靠性之间不是线性关系。从以往经验来看， 当副本数为2或3时，系统费用较理想。当副本数进一步增加时，系统费用不一定会降低，甚至有可能上升在此方法中，形成初始分配的方法是采用非冗余最佳适应法。非冗余最佳适应法非本文的主要参考，不作详述，只介绍一下它的优缺点。第8页，共18页

6、，2022年，5月20日，10点10分，星期一用非冗余最佳适应法进行数据分配，存储代价最小，但是系统的可用性、可靠性和数据的访问效率不高，并且没有体现出分布式数据库系统的优越性。另外，假设数据片段的数量为m，站点数为q，则非冗余最佳适应法在每次决定分配某个数据片段之前要计算q次全局代价，然后将q个结果进行比较。随着已分配的数据片段的增多，每次的计算量会越来越大。这种不使用启发式公式而用大量的计算的方式，严重影响了初始分配的效率，也给整个启发式添加副本法的算法复杂性带来不利的影响。第9页，共18页，2022年，5月20日，10点10分，星期一2. 3 启发式试消副本法启发式试消副本法的基本思路是

7、：对检索应用，可以按照应用发出的原始站点将目标片段放在应用所在站点而使得检索最优。这样一来，每个数据片段可能有多个副本分布在网络的多个站点上。对更新应用，则会因为要维护多个站点上片段多副本的数据一致性而增加开销。因此，第一步仅考虑检索需求片段的完全本地化，即先保证检索应用最优，得到初始分配，显然这种初始分配对更新应用是最坏的。然后再考虑更新应用的影响，逐步消除片段副本数以减小更新的通信代价。第10页，共18页，2022年，5月20日，10点10分，星期一其间，用目标函数作为衡量其副本是否该被消除的判断依据，当去掉一个片段副本时，计算产生的总代价是否小于原方案(未去掉该片段副本时的中间方案)，若

8、是就消除该片段副本，否则不消除，目的是尽可能使最终的分配方案的总代价最小。该算法是一种启发式算法，第一步，基于条件设定，可以根据检索访问矩阵和检索事务执行频率矩阵很容易地得到初始片段分配表；第二步以第一步得到的分配表为基础，逐步消除片段副本。在消除片段副本的过程中，目标函数的计算量受分配表的影响，随着副本数的减少，计算量也相应减小。第11页，共18页，2022年，5月20日，10点10分，星期一优缺点：这种启发式试消副本法比起分组局部优化法有着明显的实用性，但是这种方法只是对检索应用较多、事务的检索更新比普遍较大的分布式数据库系统有着良好的实用性。而对于更新应用较多或不比检索应用少、事务的检索

9、更新比并非普遍较大甚至是更新检索比普遍较大的系统时，由于开始只考虑检索应用(而分布式数据库系统可能是更新应用占有相对较大比例)，数据片段的副本过多，导致消除副本这一步的复杂度随更新应用所占的比重的增加而增加。第12页，共18页，2022年，5月20日，10点10分，星期一2. 4 基于代价得益和内部数据交换的启发式数据分配方法基于代价得益和内部数据交换的启发式片段分配方法的算法思想为：先按照最小代价原则分配片段，然后考虑片段之间的相关性，对相关性大的片段进行合并成组，最后以片段组为分配单位按照最小代价原则进行分配。分配步骤分为三步：片段分配、片段组的构造、片段组分配到系统节点上。第13页，共1

10、8页，2022年，5月20日，10点10分，星期一优缺点：该分配算法为了考虑片段间的相关性，将整个分配分为三个步骤，这显得十分繁琐，并且用IDC概念来构造片段组的计算开销非常大。其中分配过程要进行两次，一是片段的分配，二是片段组的分配，这极大地增加了算法本身的复杂性和执行算法的开销。该算法对统计信息考虑得比较合理，但是片段组分配用到的某些统计信息必须受第一步分配结果即片段分配的限制，也增加了复杂性。另外，在代价公式中将通信代价和存储代价一并处理，没有考虑代价单位的换算问题。总之，该分配方法的复杂性还是较大，实际应用中的可行性不高。第14页，共18页，2022年，5月20日，10点10分，星期一

11、三、数据分配的研究趋势目前，国内外学者已经研究出多种数据分配方法，但基本上都存在代价公式复杂，算法执行效率较低或所求结果与最优分配方案相差较大的不足之处。一种基于遗传算法的数据分配策略，更好地解决了数据分配问题。这种分配策略利用了遗传算法高并行性，鲁棒性，简单易行，实现方式规范，能够在深度优先搜索和广度优先搜索之间维持很好的平衡，以及不受优化函数连续可导等性质约束的优良性能。第15页，共18页，2022年，5月20日，10点10分，星期一同时在应用过程中对遗传算法进行了一定改进：根据数据片段的更新检索比来初始群体，采用适应度比例和精英保留策略相结合的选择机制，采用自适应的交叉算子和变异算子。改

12、进后的算法具有更强的搜索全局最优解的能力，以及更快的搜索速度。该分配策略采用以事务处理为主的代价公式，在选择统计信息时，以统计信息本身的重要性，获取统计信息的代价，统计信息对代价公式的复杂性的影响为原则，忽略了对代价公式准确性影响不大或很难获取的统计信息，降低了代价公式的复杂度，从而减小了算法的执行开销。第16页，共18页，2022年，5月20日，10点10分，星期一四、参考文献1邵佩英分布式数据库系统及其应用M北京：科学出版社，2000：72肖凌，刘继红，姚建初分布式数据库系统的研究与应用J计算机工程，2001，27(01)：33353王于同一种分布式数据分布的启发式算法J计算机时代，199

13、5，4：18-204Shuoi W，Hsing-Lung CNearoptimal data allocation over multiple broadcast channelsJComputer Communications，2006，29：134113495杨洲分布式数据库中数据分配策略的研究D哈尔滨：哈尔滨工程大学，20076郑宇，周广声分布式数据库中的数据分配策略及其实例研究J计算机工程与应用1997,12：17页7杨艺分布式数据库中数据分配方法的研究D重庆：重庆大学，20048Ching-Ter ChangOptimization approach for data allocat

14、ion in multidisk databaseEuropean Joumal of Operational Research2002，43：210217P9Ran C,-iladi，Ephraim Korach,Rony OhayonPlacement of network resources in communication networksComputer Networks2003，43：195209P10韩启龙，郝忠孝分布环境下实时数据的分配算法J计算机工程，2006，l(3)：525411李想.分布式数据库中数据分配策略研究.大连：大连理工大学，2009.12师广利，余东梅，袁占亭分布式数据库设计中的数据分配问题研究甘肃工业大学学报，199912：616513陈江萍分布式数据库系统及其应用前景现代图书情报技术，1996，3：293114Kang S，Moon SA Integrated Access Control in Heterogeneous Distributed Database Systems.1992 IEEE Region 10 Conference on Co