动态容错依赖调度算法在分布式数据仓库中提高查询效率及资源利用率

Egyptian Informatics Journal（2014）15，51开罗大学埃及信息学杂志www.elsevier.com/locate/eijwww.sciencedirect.com原创文章分布式数据仓库S. Krishnaveni，M. Hemalatha*印度哥印拜陀卡尔帕加姆大学计算机科学系接收日期：2013年4月10日;修订日期：2013年8月27日;接受日期：2013年2013年11月28日在线发布摘要分布式数据仓库主要基于数据是如何被处理的，并区分动态和物理分布式系统。从一个庞大的数据库中查找相关信息是一个非常费力的过程，需要花费更多的时间。这一冲突已解决在分布式数据仓库中使用查询调度过程对于在几秒钟内完成这些任务是非常紧凑的。本文提出了一种动态容错依赖调度算法（DFTDS），该算法根据查询的依赖关系对查询进行调度，并通过检查虚拟机的确认状态来自动分配资源。也就是说，在分布式数据仓库系统中回复客户端/用户查询。与现有算法相比，DFTDS算法在查询处理时间和内存利用率©2013制作和主办由Elsevier B.V.代表计算机与信息学院开罗大学。1. 介绍分布式系统是通过局域网或广域网连接的异构计算机的互连集合。随着数据量和站点数量的增长，通常分布式系统对于调度查询变得至关重要。因此，采用基于网格的任务和资源调度算法来解决分布式环境中的*通讯作者。联系电话：+91 9659079670。电 子 邮 件 地 址 ： sss.gmail.com （ S.Krishnaveni ） ，csresearchhema@gmail.com（M. Hemalatha）。开罗大学计算机和信息系负责同行审查。数据仓库计算大量的数据是一个重要的任务，现在的一天。现有的调度算法不可能从单个存储库中检索精确的信息。为了从分布的数据仓库中获取准确的信息，并共享来自不同存储库的大量数据，提出了一种基于网格调度的数据仓库调度算法。在局域网中，计算机与各个物理机或物理机上的主机完全连接，虚拟机成为分布式资源。大多数虚拟机都是用不同的属性开发和配置的，如RAM，存储，CPU等。一些资源仍然未使用，因为大多数系统资源仅对系统所有者可用。分布式系统的未使用或未开发的计算能力可以用于执行由用户分配的各种任务，而不使用任何附加的计算能力。1110-8665© 2013由Elsevier B. V.代表开罗大学计算机与信息学院制作和主办。http://dx.doi.org/10.1016/j.eij.2013.10.002制作和主办：Elsevier关键词数据仓库; DTDS算法; VMFTRS算法;WINE算法; DTDS算法52 S. Krishnaveni，M. 赫马拉塔基础设施设备。在局域网中，一个虚拟框架进入分布式资源。例如，用户可以提供某些技术来访问资源，而不损害系统安全性并且不干扰系统的实际所有者的操作。大多数广泛分布和自治的资源也可以在所选查询的执行中使用。PM或VM故障可能不太可能，但也很昂贵。容忍错误而不是放弃已经完成的工作是更高的，除非完成所需的回滚恢复机制[1]，是分布式查询处理中容错机制的一种。对于只读查询，人们认为对容错的支持太昂贵了，不值得。在物理纯数学期间的用户请求的高级别表达为标准化容错提供了机会，因此按比例降低了价格，并且在非常便宜的问题处理级别上提供了比使用通用容错机制更高的性能。本文针对分布式数据仓库系统中存在的问题，提出了一种新的动态容错相关调度算法（DFTDS）。所提出的系统集成了我们先前提出的动态任务依赖性调度（DTDS）和虚拟机容错调度（VMFTRS）算法[2-本文提出的DFTDS算法是一种在线的、非抢占式的DFTDS算法。这意味着，用户给定查询然后，通过六个参数对加固进行评估。与WINE、DTDS和VMFTRS算法进行了比较。WINE算法能够很好地满足客户比较结果表明，通过在虚拟机发生故障后恢复并继续运行，可以显著提高性能。2. 初步诊断为了提高分布式数据仓库系统中任务调度的性能，采用了三种现有的基于网格的任务调度算法，即最优资源约束（ORC）、基于分组的细粒度任务调度算法和基于网格的任务调度算法。图1所提出的DFTDS算法的架构。（GFJS）和启发式算法（HA）。ORC算法[6]应用循环调度（RR）和最佳匹配算法为可用处理器分配任务。GFJS算法[7，8]基于资源特征，还集成了Greedy和FCFS算法，以改进细粒度作业。然后使用一组细粒度作业来开发粗粒度任务。 [9]提出的分组策略提供了一个真实的网格计算环境，减少了分组任务的等待时间。 Grace等人，在他们提出的框架中使用HA来计算和最小化处理时间[10]。HA对于大规模问题显示出更好的输出。所有这些现有的算法已经在分布式环境中实现，并且它们的处理时间、存储器利用率和一些缺点已经通过在70个资源（系统或机器）中的150个查询的给定集合来识别，如表1所示。这些缺点已在我们提出的三个新算法，即DTDS，VMFTRS和DFTDS。DTDS算法的提出是为了解决基于查询依赖的问题。DTDS算法首先根据查询的依赖性和资源的状态对查询进行调度并映射到资源上。通过资源的最早空闲时间ri和查询的最早开始时间qi将资源映射到查询。如果资源处于运行状态，则跳过并搜索其他资源。如果资源是免费的表1现有算法的缺点。算法缺点处理时间内存利用率（MB）作业调度ORC通信开销36212.583高预处理时间和内存大小的限制微不足道37612.339HA阻碍评估重新设计质量的方法35312.139资源调度RNDRM 资源配置期高33311.997NRMNS资源成本最小化时资源提供者代理的32511.908VCGRP在查询中发生任何故障时不显示任何错误信息30811.894分布式数据仓库DFTDS算法的评价检查是否所有依赖查询都被执行，然后根据排序顺序插入独立查询，直到所有独立查询都被执行。为了提高资源管理的效率，结合并使用了三种现有的基于 网 格 的 算 法 的 原 理 ， 即 新 的 动 态 资 源 管 理 研 究（RNDRM）、新的资源协商机制（NRMNS）和使用资源池的虚拟计算网格（VCGRP）。RNDRM算法是一个范例，将代理技术与基于网格计算的应用集成在一起[11]。NRMNS算法是一种基于代理的资源管理系统模型[12]。它在资源发现故障时提供了替代解决方案。VCGRP算法[13]用于以较少的工作量利用理想的计算能力。当使用这些算法时，表1中列出的缺点很少。为了克服这些矛盾，以前提出的VMFTRS算法使用。VMFTRS算法的主要目的是回收虚拟机。优先分配资源查询并检查虚拟机的状态。如果任何虚拟机出现故障，则根据MIPS（每秒百万指令）可用性对所有其他虚拟机进行排序。如果查询大小小于虚拟机在阵列中的可用性，则将否则使用查询大小评估任何其他虚拟机的可用性。如果状态未满足，则检查虚拟机的所有可能组合3. 建议的DFTDS算法3.1. 设计细节所提出的DFTDS算法的设计方式是，第一个查询根据其依赖性进行分组。然后，基于VMFTRS算法将分组的查询分配给资源，随后是VCGRP技术，如图1所示。所提出的DFTDS算法的工作流程已使用图2中的伪代码进行了说明。最初，用户查询存储在查询表中。物理机（PM）和虚拟机（VM）及其带宽详细信息保存在资源表中。在分配表中，存储了已分配机器的详细信息，资源守护程序读取此表以更新资源表。每当查询提交到PM或VM时，都会在提交表中创建一个条目，查询守护程序从此表中读取条目以更新查询表。 这四个表都在资源分布监控器中维护。3.2. 算法步骤步骤1：收集所有查询，并根据大小，到达时间和依赖性进行排序。步骤2：初始化可重构的VM数量、物理机数量和查询大小。图2所提出的DFTDS算法的伪代码。54 S. Krishnaveni，M. 赫马拉塔第3步：首先，根据查询依赖性和资源容量（MIPS）调度查询并将其映射到资源。第4步：检查是否（查询状态=挂起，资源状态=终止）。然后创建新的VM以匹配其查询大小。步骤5：如果VM failure= true，则从RVM创建新的VM，并使用查询大小检查其容量。步骤6：如果新VM容量>查询大小，则分配查询。其他使用单个或组合PR技术创建新VM以满足查询大小。第7步：检查是否分配了所有依赖查询如果是，则转到步骤8如果否，则重复步骤4并继续该过程，直到所有查询都已分配。步骤8：使用与依赖查询相同的过程，根据其优先级处理独立查询。第9步：检查是否执行●如果是的话，那就停止这个过程。如果没有，则转到步骤4并重复相同的过程。4. 数据集描述食品市场数据集已被用来评估我们提出的DFTDS算法的性能。它包含24个相关表格。记录总数为3，20，835。表名称 为 Account 、 Category 、 Currency 、 Cus- tomer 、 Days-check 、 Department 、 Employee 、 Account_fact 、Inventory_fact_2010 、 Inventory_fact_2011 、 Position 、Product、Product_class、Promotion、Region、Reserve_employee、Salary、Sales_fact_2010、Sales_fact_2010、Sales_dec_2011、Store、Time_by_day、Warehouse和Warehouse_class。在这项工作中，这些表随机分布到不同的网站。5. 性能度量为了评估所提出的算法的性能，已经使用了各种参数，如处理时间，数据库利用率，复制度量，无错误执行，查询成本和可扩展性。基于[14-6. 实验结果和讨论在分布式数据仓库中，当需要获取的数据量增加时，需要向网络中增加更多的资源，并进行大量的合并和拆分操作。为了解决这一问题，提出了现有的基于网格的这有助于更快、更容易地生成报告。提出的任务调度算法基于查询依赖性将查询分配到合适的资源上.所提出的资源调度算法侧重于检查表2评价指标。描述给定查询的到达时间（tqi）和执行时间（etqi系统总数之间的差异在用户给出其查询之前的空闲内存（Tm）和系统在执行所有输入查询在不同站点或资源中重复的相同查询的数量性能度量处理时间（PT）缩写q=用户给出的查询数量i=第i个查询MUqi=第qth查询的内存利用率式PTqi =（etqi- tqi）（MUqi）=（Tm-Fm）P内存利用率（MU）P PLn m1马币复制指标（RM）Qi2Rj[] ω100ð ½ ðk=同一组查询执行的周期数Tq=用户给出的查询总数=执行的查询IEq=迭代错误查询K¼1iK联系我们ω100Tq -lEq Þ在不同资源无错误执行TQEFE¼Eq=（TqPIEq=N]Mk¼1PnPTqi1查询成本（QC）扩展性质量控制执行用户给出的查询所用的总处理时间dj=给定查询中出现的数据Qi= i查询数量Rj= j资源数量KKPTQi Rj]1djPTQiRj]对不同查询集的平均处理时间（PT）进行评估可扩展性¼●由同一组资源●分布式数据仓库DFTDS算法的评价图3推荐DFTDS算法屏幕的主界面。(3)在VMFTRS中，根据VCGRP算法将查询分配到资源中。检查VM状态，如果任何VM失败，检查其他VM的可用性。如果并发VM<图4数据仓库示例查询。通过使用虚拟机和物理机，我们可以更好地管理资源，并容忍资源故障。实验装置包括70台机器，配置为运行Windows XP的Intel（R）Core（TM）2 DUO CPU 2.80 GHz系统和80 GBSATA硬盘，2 GB RAM。我们实现了建议DFTDS以及所有其他现有的调度算法，使用Java 1.7的各种给定的用户查询。WINE、DTDS、VMFTRS和DFTDS都是在线的、非抢占式的调度算法，它们的倾向不同。(1) WINE是两级调度算法。(a)平衡查询和更新队列。(b)查询和更新都分别基于服务质量和数据质量进行优先级排序。(2) 在DTDS中，查询是按照它们的依赖性和资源的带宽容量来执行的在分布式数据仓库环境中，由用户随机生成。图3示出了我们提出的DFTDS算法的主界面屏幕，其中客户端输入针对其请求的查询。提交的查询存储在文本文件中，然后使用我们提出的DFTDS调度算法分配到不同的资源或站点。查询处理完成后，服务器从资源中收集结果最简单的示例查询及其结果如图1和2所示。分别为4和5。上述性能指标已被用来评估所提出的DFTDS方法与其他现有方法的性能。本文通过执行间隔为25（25，50，75，100，125，150）的不同查询集和间隔为10（10，20，30，40，50，60，70）的不同资源组来评估处理时间和内存利用率测量了25个周期的处理时间、内存利用率、可扩展性、副本度量、无错误执行和查询成本度量每个周期评估同一组查询和资源。汇总结果见下图。所有四种调度算法的处理时间如表3所示，并将它们分为三组资源和六组查询。通过增加查询和资源，处理时间会自动增加。对于25个查询，DFTDS算法需要45 s。在10个资源中，91个。在40个资源和139个s中。70资源在70个资源中，DFTDS算法需要228 s。对于100个查询，239个s。125个查询和255个s。150个查询56 S. Krishnaveni，M. 赫马拉塔图5示例查询获得的结果。表3查询数量与处理时间的不同算法比较表。WINE DTDS VMFTRS拟议的DFTDSR-10转轴-40R-70R-10转轴-40R-70R-10转轴-40R-70R-10转轴-40R-70256012616661125161431021574591139506813019065132195481121704810816675174192242177203248120169236119149194100181222278195219272132194249131185228125193246285202255298145221285139198239150224278335213298337154231297147228255表4不同算法的查询次数与内存使用率（MB）的比较表。数量的查询酒的dtdVMFTRS提出DFTDSR-10转轴-40R-70R-10转轴-40R-70R-10转轴-40R-70R-10转轴-40R-702510.29210.44110.83310.44210.63610.7489.93410.34310.7039.0629.2969.6835010.33810.75010.88210.55110.86410.93910.00210.52810.9169.4439.44910.0897510.86110.97611.35910.81911.17911.45210.50810.83710.9299.93410.13710.6210011.09311.66711.58211.08111.52411.63610.87411.16911.46410.44210.77610.90912511.26411.70111.76411.65711.8511.76311.06311.47411.72210.95411.03411.17415011.86311.98511.92711.87512.13612.01411.59311.80611.88911.09511.26511.297所提出的DFTDS算法与其他现有算法在内存利用率方面的性能比较对于25个查询，DFTDS算法在10个资源中使用9.062 MB（兆字节），在40个资源中使用9.296 MB，在70个资源中使用9.683 MB。在70个资源中，DFTDS算法使用10.909 MB用于100个查询，11.174 MB用于125个查询，11.297 MB用于150个查询。图6描绘了WINE、DTDS、VMFTRS和所提出的DFTDS算法的四个性能度量值。在处理时间、内存利用率、可扩展性、无错执行、复制度量和查询代价方面，DFTDS算法的平均性能分别比传统的DFTDS算法高20.58%、1.25%、13%、3%、3%和28葡萄酒，50.29%，1.87%，11%，2%，3%和27%优于分布式数据仓库DFTDS算法的评价图6具有不同度量的各种算法的评估图DTDS分别比VMFTRS高12.07%、1.1%、7%、2%、2%和13% 。结果表明，与各种调度算法相比，我们提出的DFTDS算法性能更好。但是现有的调度算法在每次发送100个查询时，有时不能产生完整的查询结果，也不能发送任何错误消息。因此，我们提出的DFTDS算法已执行不同的查询大小范围在25和150之间。DFTDS算法通过在任何故障情况下自动创建新VM来获得较低的处理时间。根据检索信息的大小，在5到10秒内执行错误纠正。7. 结论和今后的工作本文针对分布式数据仓库环境，提出了一种在线的、非抢占式的DFTDS算法。DFTDS算法通过考虑查询的依赖性和资源状态来调度查询，然后调度虚拟机以避免故障。在不同的参数下，使用不同的查询集和资源组大小，将DTDS和VMFTRS是我们以前提出的作业和资源调度算法。WINE是现有的数据仓库算法，基于查询和更新。从处理时间、数据库利用率、可扩展性、无错执行、复制度量和查询代价等方面给出了系统的平均性能评价。实验结果表明，本文提出的DFTDS算法比WINE算法的性能分别提高了20.58%、1.25%、13%、3%、3%和28%。在未来，我们将模型在线和抢占式调度算法的任务预测，资源分类。确认我们感谢卡尔帕加姆大学的动机和鼓励，使这项工作取得成功。引用[1] Jim Smith和Paul Watson，[2] Krishnaveni S，Hemalatha M.分布式数据仓库中基于动态任务依赖调度算法的查询处理。Int J Comput Appl2012;55（8）：17-22.58 S. Krishnaveni，M. 赫马拉塔[3] Krishnaveni S，Hemalatha M.基于DTDS和VMFTRS算法的分布式数据仓库查询调度。Eur J SciRes 2012;89（4）：612-25.[4] Krishnaveni S，Hemalatha M.利用虚拟机容错资源调度算法实现数据仓库查询管理。Int J Theor Appl Inform Technol2013;47（3）：1331-7.[5] Thiele Maik，Fischer Ulrike，Lehner Wolfgang.活数据仓库环境中基于分区 的工作负载调度。 Inform Syst （ Elsevier ）2009;34：382-99.[6] Somasundaram K，Radhakrishnan S.网格计算中使用最优资源约束调度的节点分配。Int J Comput Sci Netw Secur 2008;8（6）：309-13.[7] 刘全，廖叶青。网格计算中基于分组的细粒度作业调度。第一届IEEE国际研讨会教育技术计算科学2009：556-9。[8] 廖叶青，柳泉。网格计算中的细粒度作业调度研究。Int JInform Eng Electron Business2009;1（1）：9-16.[9] Soni Vishnu Kant，Sharma Raksha，Mishra Manoj Kumar. 网格计算中基于分组的作业调度模型。WorldAcad Sci Eng Technol2010;65：781-4.[10] Grace Mary Kanaga E，Valarmathi ML，Murali Juliet A.使用启发 式 算 法 的 基 于 代 理 的 患 者 调 度 。 Int J ComputSci Eng2010;2：69-75.[11] 李福芳，齐德宇，张利民，张贤光，张志立，709[12] 王俊彦，徐跃斌，刘冠峰，潘振宽，郝永胜，“基于Agent的网格环境下的资源发现与协商机制”，IEEE-第三届国际网格与普适计算研讨会，pp. 2008年23[13] 拉詹·阿尔帕纳，拉瓦特·阿尼尔，维尔玛·拉杰什·库马尔.使用资源池的虚拟计算网格。IEEE-Int Conf InformTechnol 2008：59-64.[14] ''计算 吞吐量 和 响应 时间“， 提供，2005年。[15] 嘉廉Weinstock和JohnB.Goodenough，http://www.sei.cmu.edu/reports/06tn012.pdf[16] GregBarish ， ，2002年。