© 2013由Elsevier B.V.发布。由美国应用科学研究所负责选择和/或同行评审可在www.sciencedirect.com在线获取ScienceDirectAASRI Procedia 5（2013）147 - 1552013年AASRI并行和分布式计算系统基于可用性管理数据复制和放置Bakhta Meroufela *，Ghalem Belalembabakhtasba@gmail.com，bghalem1dz@univ-oran.dz精密科学与应用阿尔及利亚奥兰大学摘要在数据网格的多个站点之间进行数据复制是一种有效的解决方案，可以在负载平衡、响应时间和提高数据可用性方面获得良好的性能。为了使数据复制获得最大的收益，它们在系统中的放置策略是至关重要的。本文提出了一种基于可用性的复制策略。它还提出了一个放置和替换策略的副本，确保所需的可用性与最少的副本，尽管存在的节点故障，而不会使系统过载。我们的实验结果证实，所提出的方法达到其目标。© 2013作者。由Elsevier B. V.在CC BY-NC-ND许可下开放获取。由美国应用科学研究所负责选择和/或同行评审关键词：复制;可用性;数据网格;相似性;放置;集群。1. 介绍数据网格是一种很有前途的分布式系统技术。它提供了大量数据的可用性[16]，这种类型的网格环境中的问题是确保数据的持续可用性并尽快响应用户请求，考虑到节点的地理分布和* Bakhta Meroufel电子邮件地址：bakhtasba@gmail.com。2212-6716 © 2013作者由Elsevier B. V.在CC BY-NC-ND许可下开放获取。美国应用科学研究所负责的选择和/或同行评审doi：10.1016/j.aasri.2013.10.071148Bakhta Meroufel和Ghalem Belalem / AASRI Procedia 5（2013）147数据的普及。解决这个问题最常用的方法是复制[15]。数据复制是一种创建数据（文件、数据库等）的相同副本的技术。在地理上分布的地点。每个副本都被称为副本[7]。我们的工作的目的是确保所需的可用性与最少的副本，而不会降低系统的性能。这一目标是可能的布局策略，考虑到：所需的可用性，系统中的节点的稳定性和故障。第二节介绍了分布式系统和数据网格中副本复制和放置的相关研究。在第3节中，我们定义所使用的拓扑。第4节介绍了我们的贡献，即建议一个有效的动态复制的方法，考虑到在系统中的副本和故障的位置。第5节介绍了我们不同模拟的实验结果。最后一节总结了本文，并对未来的工作进行了简要的概述。2. 相关作品针对网格中具有层次拓扑结构的副本，已经提出了各种放置策略。[3]中提出的模型最小化了通信（数据传输）和存储（放置副本的成本）的成本。本文[5]使用了两种副本放置模型。在第一种情况下，作者使用读/写成本作为布局参数。在第二种情况下，它们还考虑到每个节点所需的存储负担。在[11]中，作者通过同时确保节点之间的负载平衡和副本数量来解决放置问题。在[5，11]中，网格的节点数是固定的，这在节点通常不可预测地连接和断开的网格中不是一个容易满足的条件。在[8]中，在接收大量请求的节点上创建副本。然后，它们将在用户请求时或数据不再使用时，或存储空间已满且必须创建最高优先级的副本时被删除。副本放置决策基于成本模型。[6]的作者在分布式网络中实现了一种复制方法。该网络被建模为双向图中结构化的着色节点。创建副本时，包含相同副本的节点具有相同的颜色。协议[6]的原理是每个节点选择一个颜色图，以最小化不同颜色的节点之间的距离，最大化相同颜色的节点之间的距离。这种方法的问题是，它只考虑每个节点有一个数据的情况，也就是说节点只能有一种颜色。3. 系统模型我们使用的系统模型是一个集群联邦，其中一个单一的根，从而集群之间的链接。一些系统具有这种拓扑结构，例如Internet [10]和DIET [1]。图1显示了系统及其组件的示例。Bakhta Meroufel和Ghalem Belalem / AASRI Procedia 5（2013）147149群集间链路集群内链路根簇头通常节点第1群组2Fig. 1.使用拓扑学。拓扑中的根用于将各个集群相互绑定。代表集群成员的簇头（CH）具有管理集群内节点的路由表。它还包含有关群集中现有副本的元数据和信息。其他节点是存储元素;它们包含各种数据的一个或多个副本。在系统中，节点具有预测行为[4]，故障检测基于生命的消息[9]。换句话说，如果检测到故障，自动稳定[2]将被触发以保持拓扑连接。4. 该方法本文采用了一种新的数据复制和放置模型。该模型的主要目标是在保证一定可用度的前提下，在不降低系统性能的前提下，最小化系统的副本数量。与文献[10] [13] [14] [17]中的大多数工作相比，我们的策略考虑了不同和独立的稳定节点。每个Cluster_Head包含一个复制控制器，用于管理集群中副本的复制和放置。4.1. 所需副本为了计算系统中数据j的可用性，我们可以使用[12]中提出的公式（一）哪里j：数据;数据的可用性j。0 j 1;数据j的副本的数量N;pi：存储数据j的副本的节点i的稳定性。0 π 1。在本文的其余部分，我们将区分节点的稳定性和其数据的稳定性，我们注意到第一个STAB和第二个p。因此，如果数据j存储在节点i中，则：.如果系统中的节点具有相同的独立稳定性，则公式（1）将为[9]：（二）150Bakhta Meroufel和Ghalem Belalem / AASRI Procedia 5（2013）147公式（2）允许我们估计满足数据j的可用性Avail的值文献[10]、[14]、[17]中的许多工作都假设节点具有相同的稳定度，以便使用公式2。在工作[13]中，作者使用了不同程度的稳定性节点，但他建议在同一稳定性类别的节点中复制数据。这个建议允许他使用公式2来计算满足期望可用性所需的副本数量。在我们的系统中，节点具有不同的和独立的稳定性;这是现有系统的情况。要计算确保所需可用性程度Avail所需的副本数量，我们有三种可能性：乐观：是数据i的所有副本都存储在稳定性良好的节点中的情况。因此，可用性将以最小数量的副本来保证。Op是在乐观情况下确保所需可用性所需的副本数量。它由公式2计算，其中p是系统中的最佳稳定性。Pessibility：数据i的所有副本都存储在稳定性差的节点中。因此，可用性将通过最大数量的副本来保证。Pes是在悲观情况下确保期望可用性所需的副本数量，它由公式2计算，其中p是系统中的最小稳定性。混合是副本存储在不同稳定程度的节点中的情况。因此，通过在系统中创建Hyp副本来保证可用性。所以Hyp将在[ Op，Pes]范围内。在指定复制品的放置位置后，无法计算Hyp数，因为您必须在公式1中选择参与pi。为了在包含不同稳定性的不同节点的系统中确保数据j的可用性程度，可以提出几种解决方案：创建Pes副本，这样我们就可以确保可用性得到尊重。但是在副本的创建和管理成本高昂的环境中，这种解决方案将不会有效。创建Opt副本，因此副本的数量是最小的，但此解决方案要求具有最佳稳定性的节点的数量大于或等于Opt。此解决方案使最稳定的节点过载，这增加了故障时丢失文件的数量，也增加了恢复时间。我们的方法包括创建尽可能少的副本（最小然后Pes），而不会过载的节点的良好的稳定性和不降低系统性能。我们建议的原则如下：每个调度器头（CH）指定某个程度的可用性调度器D以确保其集群中的可用性。使用数据本身的历史及其在以前时期的重要性（受欢迎程度）来估计BHD。在计算出可用性ID之后，CH将集群中的数据可用性R的实际可用性（真实可用性）与期望可用性ID进行比较。如果不符合条件，则表示满足可用性。所以CH什么也不做，它等待一段时间重新检查约束。在这种情况下，CH开始创建副本，并存储在一个良好的位置，只要可用性所需的BROID将得到满足。我们将存储副本的节点称为：最佳目标（见§ 4.2节）。4.2复制品的放置副本在系统中的位置起着重要的作用。在[17]中，作者表明，在同一节点中放置相同数据的多个副本不会提高可用性或容错性。因此，在节点中存储相同数据的单个副本将非常有用。但是什么是存储数据的好候选者呢？在我们的系统中，节点可以预测故障。在怀疑故障的情况下，Bakhta Meroufel和Ghalem Belalem / AASRI Procedia 5（2013）147151节点将其所有数据放置在其它节点中以确保期望的可用性。我们使用了一个新的参数，称为DR，表示在怀疑节点故障的情况下必须在其他地方替换的字节量。（三）哪里Nj：节点;k：节点N j中的数据数量; D ij：节点j中存储的数据i。高度的责任性表示该节点在疑似故障的情况下有大量的字节要放置（移动）。在这种情况下，该节点的恢复时间将很长，并且故障将加速。恢复时间表示将数据从可疑节点移动到其他节点所需的时间。我们假设一开始所有节点的DR都是1。也称为最佳目标的候选节点的特征在于：还没有数据。足够的可用存储空间来存储数据。良好的可用性系数（AF）。AF计算如下：（四）也就是说，具有良好AF的节点是具有良好稳定性STAB和低责任度DR的节点。基于可用性因子AF的副本放置策略保证了副本在集群节点上的良好分布可能存在这样的情况，即相同数据的许多副本存储在邻居中，这增加了其他节点的响应时间。为了避免这个问题，我们添加了最后一个条件：为了增加相同副本（相同数据的副本）之间的距离[6]，我们建议使用具有以下定义的非相似性参数：（五）n：节点;Di：数据;LLDn：L是数据在节点n中的局部;LDNn：节点n的所有N个邻居的数据的列表。因此，节点n的数据列表与其邻居的数据列表之间的不同数据列表的大小也是如此。例如，如果=0，则节点n中的所有数据也存在于1-邻域中。我们的目标是在网络中分配负载。在我们不知道数据访问频率的系统中，因为：制度是新的，或者说是处于新的时期。数据的流行程度往往是可变的。最大化每个节点而不使其过载更有用。因此，我们提出了以下算法，该算法结合了可用性因子AF和非相似性参数：在算法1的第一步（见图2）中，CH创建可以存储该数据副本的候选节点列表，该列表被标记为Liste_cand。这些候选节点没有数据，但有152Bakhta Meroufel和Ghalem Belalem / AASRI Procedia 5（2013）14701：创建候选节点列表Liste_cand02：将列表Liste_cand按照AF * 的降序排序（1/））。03：Rep假04：While（Liste_cand09：否则转到Liste_cand中的下一个节点。第10章：结束第11章：结束12：如果Rep = false，则十三：将副本存储在Liste_cand中的第一个节点n中十四：足够的存储空间。列表Liste_cand将按照AF *（1/）的降序排列（参见算法1：行01和02），也就是说，我们支持良好AF和更低AF的节点（参见算法1：行01和02）。为了避免不确定的情况，如果=0，我们根据以下参数对列表中的节点进行分类：只要CH没有复制数据，它就验证列表Liste_cand中的每个节点，并且如果添加副本增加了节点的非相似性，则它将该数据存储在节点中，否则它测试列表Liste_cand中的下一个节点（参见算法1：第04至11行）。在CH遍历整个列表Liste_cand而不复制数据的情况下，它会选择AF方面的最佳节点（参见算法1第12和15行）。/打开/关闭在节点n存储数据05：如果> then / /该副本不存在于1-neighbor06：在节点n07：08：RepTrue图二.布局算法图3显示了一个由五个节点组成的集群示例。假设CH想要存储数据M的新副本并且所有节点具有相同的AF。如果Liste_Cand= {1，4}，则在节点1中创建数据M的副本不会增加其非相似性（1））=（（1），因为该数据已经存在于其1-邻域中。但是在节点4中添加该数据增加了其非相似性（=2 >=1）。因此，CH在节点4中复制此数据。在CH在集群中添加新数据S的情况下，并且它具有作为候选的Liste_Cand={1，4}，因此它选择节点4来存储数据的副本，因为该节点具有最低（一））的。Bakhta Meroufel和Ghalem Belalem / AASRI Procedia 5（2013）147153副本数{A，B，C，M}2 3 4 A、B、C、M、E、F1 A、B、O15 A、B、O1{O，C，M，F，E} 54{A}14 O、B图3.非相似性示例系统中的每个节点存储请求访问其数据的节点的列表。如果存在故障怀疑，则节点将其数据移动到其他节点以保持集群中的可用性。对于每个数据，节点从请求该数据的节点列表中选择具有良好AF的最近节点。通过这种方式，节点可以最大限度地减少恢复时间，并保持不同数据复制之间的距离。5. 评价为了估计我们称为PD（动态放置）的方法的行为，我们使用了我们开发的模拟器FTSim[13]。第一个实验使用系统中不同数量的节点来评估响应时间。结果如图4所示。我们注意到，在所提出的模型中的响应时间变得更小相比，随机的方法（副本被随机放置），如果在系统中的节点的数量增加。在我们的方法PD中，我们确保了集群上副本的良好分布，从而最大限度地减少了节点和目标数据之间的距离。第二个实验（见图5）计算了两种放置方法（PD/随机）的系统中副本的数量。我们注意到，我们的方法的副本数量少于随机方法;尽管可用性期望AvailD在两种情况下是相同的，因为我们的方法选择最稳定的节点作为副本的放置，这些节点最小化确保AvailD所需的副本数量（见§ 4.1节）。0.25 250.2 200.150.10.05050 60 70 80 9099.99失败次数15PD10随机50可用D（%）PD随机Pes选项见图4。节点数与响应时间。图五.可用D与副本数。1{A，B，O}{C，B，F}245{A}3{A，E}恢复时间（s）154Bakhta Meroufel和Ghalem Belalem / AASRI Procedia 5（2013）147M恢复时间是容错系统中一个非常重要的参数。系统的恢复时间是每个疑似崩溃节点的恢复时间之和。所获得的结果（参见图6）表明，该恢复时间随着系统中故障数量的增加而增加，但是我们的方法PD最小化了该时间，因为数据的替换是由节点本身完成的，而没有CH节点的干预，并且还选择最近的节点来存储数据。故障可能会导致数据丢失或最小化其空房的 图7所示的实验结果证明，我们的方法PD确保了可用性可用性D尽可能（可用性R>=可用性D）。但是随机方法增加了恢复时间，因为可疑崩溃的节点没有策略来选择其数据的新位置。见图6。故障数与恢复时间6. 结论观点在本文中，我们提出了一种基于可用性的复制策略，我们还提出了一种有效的方式，提高系统的性能，而不过载的系统节点的副本在系统中的位置。这种方法的不便之处在于它是半集中式的，也就是说，复制和放置副本的决定是由每个簇中的每个簇头完成的。但由于集群中节点的数量有限，可扩展性的约束可以得到满足。在接下来的研究中，我们将使用Globus来研究我们的布局模型在真实网格中的表现。我们还将通过考虑任务复制和放置来扩展这项工作，以确保系统作业的快速和容错执行。引用[1] E.卡隆和弗雷德里克·德普雷。DIET一个可扩展的服务器，在网格上构建支持网络的服务器。International Journal of High Performance Computing Applications，20（3）：335[2] E.W. Dijstra分布式控制下的自稳定系统。Communications of the ACM，17（11）：643[3] M. Garmehi和Y. Mandarin.数据网格环境中的最佳放置复制。第10届信息技术国际会议（ICIT 2007），第190-195页[4] G-F休斯，J-F。默里和K德尔哥达改进的磁盘驱动器故障警告。IEEE Transaction on reliability，51（3）：350见图7。Nu 失效率与可用率Bakhta Meroufel和Ghalem Belalem / AASRI Procedia 5（2013）147155[5] K.卡尔帕基斯湾题名其余部分：O.J.在具有读、写和存储成本的树中最优放置副本。IEEETrans.并行分布式系统，12（6）：628-637，2001年。[6] B-J.Ko和D.鲁宾斯坦新兴网络中复制资源的分布式自稳定放置。IEEE/ACM Trans. Netw，13（3）：476[7] H.拉梅哈梅迪数据网格的分散式数据管理框架。2005年11月，纽约伦斯勒理工学院博士论文[8] H.拉梅哈梅迪湾Szymanski，Z. Shentu和E.迪尔曼网格环境中的数据复制策略。第五届并行处理算法和架构国际会议论文集（ICA 3 PP[9] M. Larrea，S. Arevalo和A.费尔南德斯部分同步系统中实现不可靠故障检测器的有效算法。分布式计算，6（9）：34[10] M. Lei，S. Vrbsky，一种提高数据网格可用性的在线复制策略。Future GenerationComputer Systems，24（2）：85-98，2008。[11] P. Liu和J-J. Wu。层次数据网格系统中副本最优放置策略。集群、云和网格计算国际研讨会（CCGRID 2006），第417-420页[12] E.Marcus，H. 高可用性设计，第二版，北京：计算机科学出版社，2003年。[13] B. Meroufel，G. Belalem：数据网格中的可用性管理，电气工程讲义，1，第107卷，IT融合与服务，第1部分，第43- 53页，2011年。[14] K. Ranganathan，A.在大型P2P社区中通过动态模型驱动的复制提高数据可用性。第二届IEEE/ACM集群计算和网格国际研讨会论文集，IEEE计算机协会，华盛顿特区，美国，2002年。[15] H. Stockinger，A. Samar和B.奥尔科克数据网格中的文件和对象复制。IEEE Symposium on HighPerformance and Distributed Computing（HPDC-10），5（3）：305[16] S.韦努戈帕尔河Buyya和R.小桐用于分布式数据共享、管理和处理的数据网格分类。在ACM计算调查，38（1）：1[17] M. Zhong，K. Shen，J. Seiferas，高可用性的复制度定制，第三届ACM SIGOPS/EuroSys欧洲计算机系统会议简报，美国。2008年5月
我的内容管理
收起
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助 
