高级数据库系统数据库报告

1、关于分布式数据库中数据分配算法的组员学号分工21521213相关算法，算法评价，总结21521222相关算法，POEA 算法21521228相关算法，背景与意义，算法比较摘要随着大数据和云计算时代的到来，传统的关系型数据库已经不能够满足海大数据的需求，因此，分布式技术在这种环境下应运而生。分布式数据库由于其高可扩展性、高可用性和可并发性的特点，在近年来得到了快速的发展，而合适的数据分配是分布式数据库高效工作的关键，本文在了现有一些数据分配算法的基础上，着重介绍了一个性能较好的 POEA 算法。POEA 是 Performance Optimality Enhancement Algorithm

2、 的简写，POEA 算法在借鉴前人的算法基础之上进行优化。通过采用 Dijkstra 算法，计算在网络拓扑结构中数据迁移的最短路径，并且采用阈值来判断数据是否需要迁移。POEA 的优势在于在动态环境下进行无副本的数据分配任务，旨在降低数据传输的开销，避免不必要的数据迁移，减少节点间数据迁移的频率和时间，最终优化分布式数据库的整体性能。1.背景与意义分布式数据库指的是利用高速的计算机网络将物理位置上分散的多个数据节点，逻辑上连接起来组成一个数据库。分布式数据库的基本是：在逻辑上作为一个整体的基础上，将原本由集中式数据库中的数据分散地到多个通过网络连接的数据节点中，这样就能够得到更大的的容量，同时

3、支持更高的并发量。近年来，随着数据量的快速增长，分布式数据库技术也相应得到了快速的发展，传统的关系型数据库开始从集中式模型向分布式架构发展，关系型的分布式数据库有着传统数据库的数据模型，在保留其基本特征的基础上，从原来的集中式变为分布式，从集中式计算分布式计算。数据分配是分布式数据库的一个重要方向，合适恰当的数据分配能够大大降低数据传送的代价，提高系统整体性能。这也是分布式数据库相对于传统集中式数据库架构的一个优势所在，这是因为大多数针对数据库的操作具有很强的局部性。因此一个高效的数据分配算法在降低数据传输代价，继而提高分布式数据库性能方面有重要意义。从数据库设计上讲，分布式数据库系统中的分布

4、式数据库设计和普通数据库设计相比较具有自己的特色。在分布式数据库设计中，要解决的绝大部分问题是由数据的分布性而引起的，这些问题对整个应用系统的可用性、可靠性及数据的存取效率都产生很大的影响，同时又与分布式数据库系统设计的诸多其它方面问题密切相关，尤其是分布式查询处理与更新处理问题，它们往往彼此交织在一起，需要统筹考虑。分布式数据库设计的主要目标之一便是达到是数据处理的本地性，即通过设计，让数据尽可能都存放在使用它们的应用所处的节点,减少，性能。由此产生了“数据冗余”这一技术，但它却是一把 “双刃剑”, 虽然能为检索提供便利，却给数据的一致性带来新的问题。所以，在分布式数据库系统的优化设计中,设

5、计数据如何分布的问题就显得特别重要。数据分配问题包括两个方面的内容：数据逻辑分割（数据分片）和片段物理分配（数据分配）。数据分配问题对整个分布式数据库应用系统的改进、数据的可用性、数据库效率和可靠性有很大影响。若数据片段分配得好,整个应用系统的性能、数据的可用性以及分布式数据库的效率和可靠性都会处于一个良好的状态，否则，就体现不出分布式数据库的优越性。各国的学者该问题的目标是一致的，即通信代价，Lc 表示局部C=Rc+Lc 最小，其中 C 表示代价，Rc 表示事务处理代价，以此为目标探索逻辑片段应该放置的最佳位置。对于分布式数据库系统的数据分配问题的具有相当大的学术及实用意义，它不仅是一个重要

6、的学术问题，而且对于分布式数据库系统深度融入企业的竞争力等方面的实用意义也十分巨大。、节约成本和增强2.相关算法Amer 和 Abdalla (2012)提出了用于分布式系统的动态数据分配算法，它描述了在动态环境下，即节点数据的概率随着时间而改变，如何进行动态数据分配。作者提出了一种通过更改节点上的数据模式，进行数据重新分配的模型。假设数据分片最初是根据查询频繁度的合适的集分布在不同的网络节点上。该模型提出了一个基于节点之间的通信代价的数据分片再分配以及每个数据分片的更新代价的方法。重新分配过程将根据选择的最大更新代价对每个片段进行相应的重分配。经验结果表明，所技术将有效地在一个分布式关系数据

7、库系统的上下文中解决动态片段重新分配问题做出贡献。而Chang (2002)也了DDBS 的数据分配问题，并涵盖了冗余和非冗余情形，但是数据分配执行在一个节点数据概率不变的静态环境中，这种静态分配在概率改变的情况下会降低数据库的性能。Brunstrom 等人 (1995)展示了一个非数据库系统的最优化算法。Ulus,Uysal (2007)和Singh, Kahlon (2009)分别提出了两个非分布式数据库算法，前者使用了阈值算法，根据数据模式的改变持续地重分配数据分片，而后者在此基础上增加了时间约束来重分配数据。Nilarun Mukherjee (2011)提出了一个更加综合性的算法，它

8、包含了对时间约束，阈值以及运行时数据分片动态重分配到节点所传输的数据量的考量。Daudpota (1998)通过初次分配提出数据分配模型，以此模型来陈述和解决DDBS 问题并提出数据分配问题。Grebla,Mldovan, Darabant, Campan (2004)提出了 DDBS 中数据分配和优化的解决方案，它利用移动的方式执行。在此之后，又有一个基于观察节点模式的非集中式方法用于 DDBS 的动态表分片和分配(Hauglid, Ryeng (2010)，它根据最近的历史执行数据的分片，和重分配的操作。KarimiAdl, Rouhani Roohi (2009)提出了一个基于蚁群算法的

9、启发式算法来减少数据传输和分配的开销。本文在了现有一些数据分配算法的基础上，着重介绍了一个性能较好的POEA 算法。POEA 是Performance Optimality Enhancement Algorithm 的简写，POEA 算法在借鉴前人的算法基础之上进行优化。下一节主要描述一下 POEA 算法。3.POEA 算法3.1 问题描述增强 DDBS 性能的一个基本建议是把每一个数据分片存在它最频繁被的节点。问题就在于为每一个数据分片选择这样一个节点是很复杂的。实际上，最好的解决方案之一是为每一个节点对于某一数据分片的和更新进行计数。在此基础上，对该数据分片的相应计数值最高的那个节点成为

10、可能该数据分片的候选节点，条件是被选节点不招致任何约束被破坏。3.2 环境描述假设有一个由 M 个节点组成的完全互联的网络，每一个节点有 N 个数据分片，这些分片最初以静态方式分布在节点上，如图 1 所示。节点Sj上的每一个分片Fi有两个变量， LACi（代表本地Fi的计数值）和RACi（代表远端访问Sj上Fi的计数值）。每一个节点Sj有两个约束：容量Cj（任何节点都不能接受超过改值的数据量）和分片限制FLj（代表每一个节点能处理的最大分片数量），当下述(1),(2)和(6)三个条件满足时才会把分片Fi从Sh移动到Sj。 ，( = 1,2, , )（1） , (, = 1,2, , )（2）=

11、1=1 = （3）=1FTC = , （4）=1 1Thresholdvalue = ( )（5）=1 =1（6）Thresholdvalue FTCC , 1 （7）=1（8） , =1 = , 1 =1(1)式表示对于分片Fi（9）计数器值应当大于本地计数器值。(2)式表分片Fi时，节点Sh和节点Sj之间平均请求开销应该高于节点Sh和所有其他节点之间的平均开销(除节点Sj之外)。(3)式用来计算Sh节点和Sj节点之间的请求开销（相同的等式也可以用来计算节点Sh同其他所有节点的总的请求开销），节点Sh和Sj之间的请求开销可以通过它们之间的传输单元开销(TCh)乘上计算出j的数据(DRh)，该

12、数据量即 Karimi Adl 和Rouhani Roohi (2009)中使用的传输j数据量，（这一数据是通过执行节点Sj请求分配在Sh上的分片Fi中的某一数据得到的）。(4)式用来给出把分片Fi从节点Sh传输到Sj的分片传输开销。(5)式计算分片Fi的阈值。(6)式表明分片传输开销应当大于阈值。下面三条约束应当在整个分配过程中都予以考虑：(7)式表示容量约束，即每个节点都不能接受超过其容量的数据。(8)式表示一个数据分片只会被分配在一个节点上。(9)式表示每个节点都不能处理超过分片限制(FL)的分片数量。表 1.变量RAC计数LAC本地计数S数据节点C节点容量FL分片数量约束FI分片标识符

13、ASA当前节点位置图 1. 数据节点网络3.3 算法描述POEA 算法按以下三个步骤执行： A.决定最短路径和它们的值；B.初始化病确定变量值；C.执行算法并周期性检查节点约束。CSA候选节点位置AC计数TFA分片时刻TCS候选节点位置的时段选择从到的分片中数据大小AT每个节点的时刻 到的平均查询耗时 到所有其他节点的平均查询耗时当 需要时,为 1,否则为 0从 出发的检索操作的频率从 出发的更新操作的频率从 出发的第i 次频率V分片的总量SC开销当分配到 时,为 1,否则为 0从 到的开销A.最短路径。偶然情况下，在网络拓扑改变后，算法首先在每个节点执行 Dijkstra 算法来得到从本节点

14、到所有其他节点的最短路径。这个算法将会一直重复直到所有节点间的最短路径都已得到。在带权有向图 G=(V,E)中，有一个权重函数 W:E-R 将边 为的权重值（见图 1）。最短路径表如表 2 所示。表 2. 最短路径矩阵B.计算阈值。开销矩阵 ACM 来表SAR（表 7），每个数据分片都至少被一个节点。所有用示。ACMij给出节点Sj分片Fi的次数。在这里，基于节点开销矩阵 ACM 如表 3 所示。传输开销矩阵TCM（表 4）表示节点Sj分片Fi的传输开销。将 ACM 矩阵乘以TCM 矩阵得到的分片使用矩阵FUM。在此基础上，计算出阈值。表 3. 分片开销矩阵ACM表 4. 传输开销矩阵TCM表

15、 5. DDBS 数据分片从分片使用矩阵 FUM 中选择对于分片的平均下面将举例说明。C.初始化变量。开销最大的那个节点，分片F1F2F3F4F5F6标识符123456大小810B620B900B660B521B701BSitesS1S2S3S4S105918S250164S3916011S4184110S/FF1,S1F2,S2F3,S4F4,S3F5,S3F6,S4S1110100S2131022S3200111S4012002源地址目的地路径路径开销S1S2S1-S25S1S3S1-S39S1S4S1-S2-S39S2S3S2-S1-S314S2S4S2-S44S3S4S3-S411a.

16、可能N 个数据分片分布在 M 个节点上，每个节点包含一个或多个分片。请求分配在不同节点的多个分片。每一个节点有 2 个约束：分片限制(FL)和节点容量(C)，如表 5 所示。b.每个节点储每个节点的分片一个叫做节点(SAR)的独立的数据结构。SAR 存，用表示，表明节点的第 k 次以下信息：，其中 k=1,2,3.,信息j=1,2,3,.,m. SAR 对每次1.2.3.被的分片标识，见表 5。来访节点地址 ASA执行请求 Q 的数据DR（字节为），请求 Q 是指节点位于本节点的数据分片。4.5.本节点分片的时间。节点被计数器（AC）,次数c.对于节点内的每一个数据分片一个叫做计数以下信息：（

17、ACR）的数据结构，该数据结构在每次分片后1.候选节点地址（CSA）：它是在时间间隔（t1 到 t2）内请求开销高于其他任何节点的节点地址。最初 CSA 被设为分片当前所在节点的地址。2.3.4.本地远端计数（LAC）计数（RAC）候选节点地址选取的时间（TCS） 对每一个本地的分片，本地和远端计数初始为 0（LAC=0,RAC=0）4.算法比较基于以下 3 个因子，比较了POEA 算法和已经存在的 4 种算法（最优化算法 Optimal，Threshold 算法，TTCA 算法和Synthesis 算法）：数据分片迁移决策成本（SC）；传输成本（TC）和计算成本（CO）还有网络流量成本（NT

18、）。A. 数据分片迁移决策：Brunstrom 的 Optimal 算法是当节点的 counter值比持有数据的节点的 counter 值大，分片Fi进行迁移。阈值算法是当持有数据的节点大于一个阈值t 时，分片Fi进行迁移。TTCA 算法是当节点的 counter值比阈值t 大，并且所有剩余的t+1 个都会在特定时间T 内发生，那么分片Fi进行迁移。而Mukherjee 的综合算法是当持有数据节点的数据传输成本比任何其他节点的都要高，并在最近的一些时间间隔内都高于一个阈值，那么就将数据迁移到一个计划的节点上。然而，POEA 算法是当节点的 counter 值大于本地持有数据节点的 counte

19、r 值，并且新老节点的查询成本 QC 比老节点到其他节点的 QC 都要高，则分片Fi进行迁移，新老节点的最短路径也会被更新。90%80%70%60%OA50%TTCASYNPOEA40%30%20%10%0%TCSCCONT90%80%70%60%OA50%TTCASYN POEA40%30%20%10%0%TCSCCONT图 2. DDBS 性能B.成本因子：从图 2 中容易看出，Brunstrom 的 Optimal 算法开销比较大，因为它为每一个数据分片了多个counter 值；阈值算法相对于Optimal 算法不需要多少空间，因为它为每一个数据分片只了一个counter 值；TTCA

20、算法相对于前两个算法需要的空间。Mukherjee 的综合算法需要很高的成本，因为他了好几个数据结构体。而 POEA 算法的成本和Mukherjee 的综合算法差不多，原因也是C. 传输成本和计算开销：图 2 的 DDBS 性能了好几个数据结构体。的中清楚地显示了 Optimal算法的传输成本最高。这是因为基本的经验法则：更高的频率会带来更高的传输成本和网络流量开销。阈值算法使网络流量开销最小化并且使用阈值因子来控制传输成本，阈值算法的计算开销也比 Optimal 算法更低。然而相对于前两个算法，TTCA 算法通过时间限制和阈值来进一步的降低网络流量开销和传输成本。Mukherjee 的综合算

21、法造成的计算开销，因为它还要在时间间隔 t 内计算这个数据分片传输到所有数据节点的成本。而 POEA 算法相对于其他算法，最引人注目的是，通过增加以下几个特点来使分片迁移的传输成本最小：节点的counter（必须大于本地已迁移的分片 Fi 的 counter），阈值（阈值的计算算法和其他几个算法的不同），查询成本（QC）的计算，相对于综合算法使用的数据传输总量，POEA 使用节点 和节点 的查询成本,节点 和所有其他节点的查询成本，最后还采用了最短路径算法。在POEA 算法里，只要节点存在约，那么分片会一直呆在持有节点。束5.评价与Brunstrom 等人Optimal 算法保留了一个计数矩阵

22、，矩阵的每一行表示特定的数据分片能够的数据节点。数据分片中的数据节点最大访问计数将会成为数据分片的候选节点。这个算法中的最关键的问题在于当数据模式快速变化时，该算法将花费很长的时间去转化数据节点上的数据,因为对每个数据分片的时间会比本地高。这个过程将会产生巨大的网络超负载转化。然而，阀值算法证明了一个数据分片将会在它原始位置停留更长的时间，只要这个数据分片的计数值小于阀门值,并且本地分片的可能计数器性比要高。这个阀值算法只为每个数据分片保留了一个（一般为最后的数据节点去的数据节点）。到目前为止，数据分片并没有方法选择一个新数据分片除了最后一个数据节点，也就是说，无论何时在一个数据分片计数大于阀

23、值之后，最后一个数据节点将会被选中用于保存数据分片。阀值的选择将会影响数据分片在 DDBS 的数据节点之间移动.增加阀值意味着减少数据分片在数据节点之间的移动，反之亦然。这又会出现一个问题，如果有很多的数据节点对于一个数据分片有一样的可能性，这将会导致数据分片去访问所有的数据节点，结果增加了转化的代价以及网络通信。Singh 和 Kahlon 在 2009 年TTCA 算法尽管和 Optimal 算法一样保留了一个计数矩阵，但是它在不同的矩阵中了的时间而不是在同样的矩阵中。无论何时，一个特定分片的数据节点的计数器比阀值大，那么这个数据节点将会成为问矩阵终数据分片的候选节点。TTCA 的主要问题

24、就是它并不在访时间，也没有在一个不可预料的情况发生时给出一个可说服的措施.举个例子，在 t+1 次达到了要求的数量之前的时间消逝.在这个算法中，当时间增加,转化代价也就增加，反之亦然。然而，Mukjherjee 的synthesis算法开发了一个技术，增加新的数据分片迁移的限制来减少转化代价。它采用了特定的数据结构来保留最后一个节点的信息。这花费了的空间，增加了代价。同时，它产生了的计算负荷，由于需要计算连续时间间隔的数据节点之后的整个数据容量交换。在这个算法中，阀值或者高，数据迁移就会越少，反之亦然。表 6. 标准符号的容量越表 7.不同算法的开发标准使用情况算ARATHVTTCHICQCS

25、COSPA评价Optimal算法是是否否否否否否否高传输成本，大数据迁移引起高网络通信量，高本成本，低计算成阈 值法算否是是否否仅最近访问节点否否否高计算成本，低数据迁移和TTCA 算法否是是是否最近否否否高计算成本和成本，低数据迁移，低网络通信量和低传输成本节点Synthesis 算法否是是是是是否否否高计算成本和成本，低数据迁移和比TTCA 低的传输成本标准标准符号本地Local AcsLARemoteAcsRA阈值Threshold ValueTHV数据的时间约束Time constras for data acsingT节点之间的传输成本Transmiscost betn sitesT

26、C查询成本Query CostQC保留历史信息Maain history information for acsHIC节点约束Site constraSCO最短路径算法Shortest PalgorithmSPA表 8. 不同性能因子的比较POEA 算法试图解决以上算法中的所有问题来减少交流代价和提高DDBS 的性能。POEA 算法增加了一些新的特性，更好地避免不必要的数据迁移。考虑到网络的全接连，增加的特性包括了：A.B.C.D.Synthesis 算法使用数据传输容量的合并查询代价，开发新的数据节点约束，本地和的变量，使用传输代价矩阵来计算阀值，阀值的运行采用和之前算法都不一样的方法。这个

27、 POEA 算法和 Synthesis 算法一样拥有空间花费和计算超负荷的产生.然而,和之前的方法比较，它实现了数据节点的约束和最短路径算法，这大大减少了数据迁移和传输代价。表 7 显示了运行时期不同算法的通过和发展特点。表 6 显示了表 7 中使用的标准名词的符号。被采用的比较元素包括：传输代价(transmiscost，TC)，代价(storagecost，SC)，计算成本(compuion overhead，CO)和网络通信量(network traffic，NT)。这些元素在表 8，图 2 中显示。至于数据分片迁移决策(fragment migration deci，FMD)，并不能明

28、确地在比较中表示成一个性能因子。因为它可以含蓄地通过其他比较因子推导出来，比如TC 和 NT，因为它们之间存在正相关关系。算法TC(%)SC(%)CO(%)NT(%)Optimal 算法7080575阈值算法45302550TTCA 算法40504050Synthesis 算法30807015POEA 算法10807010POEA 算法是是是是是是是是是高计算成本和成本，与前面的算法比，由于采用SPA，有低数据迁移和传输成本图 3.的所有算法的分片迁移百分比图 4. 分片迁移百分比事实上，这里有五个基本的影响 DDBS 性能和减少不必要的分片迁移的因子，分别是时间约束(time constra

29、， T)分片(remote fragment acs，RFA)，阈值(threshold value，THV)，节点约束违背(site constras violation， SCV)以及节点之间的查询代价(query costs，QC)。当 T，RAC 增加，THV，SCV，QC 减少时，分片迁移将减少，反之亦然。举个例子，当固定了 V，SCV，QC，增加T 或者 RAC，那么分片迁移就会增加，反之亦然。图 3(A)和 3(B)描述了这个事实并显示了所有因子和数据迁移频率之间的关系。图 4 显示了不同算法的数据分片迁移百分比比较。包括了 Optimal 算法(OA)，Threshold 算法

30、()，TTCA算法，Synthesis 算法(SYN)以及 POEA 算法。这证明的数据迁移频率。POEA 算法具有最低6.总结本文了几种分布式数据库中的数据分配算法，并详细介绍了性能较好的POEA 算法。POEA 算法结合了很多因子，比如时间，数据节点约束，数据模式，阈值以及包含了数据传输容量，运行时数据节点之间的数据分片动态再分配的查询成本，POEA 算法加强了整个DDBS 的性能，通过维持严格的分片再分配使得DDBS 中的从数据节点到另一个节点的分片迁移频率显著地减少。POEA算法在动态数据分配上是前面提到的算法中最有效的，一旦需要数据移动，它采用了最短路径算法来提高 DDBS 的性能，

31、通过与之前算法比较更好地减少网络通信量和减少数据传输。POEA 唯一的不足就是，与之前的算法比较，它需要更多的空间。然而，DDBS 性能提高补偿了这个缺点，同时在急剧下降的情况下，这被视为一个并不重要的缺点。硬件价格的参考文献1Abdalla, H. I. (2011). An efficient approach for data placement in distributedsystems. In: 2011 Fifth FTRAubiquitous engineering.ernational conference on multimedia and2Hauglid, J. O., & Ryeng, N. H. (2010). DYFRAM: Dynamic fragmenion and replica management in distributed database systems. Distributed and Parallel Databases,28, 157185.Ahmad, I., Karlapalem, K., Kwok, Y. K., & So, S. K. (2002). Evolutionaryalgorithm