MapReduce中落后任务的识别与处理研究

发布时间：2020-06-08 07:25

【摘要】：由于智能硬件智能软件的发展,当今世界数据呈现出爆炸式增长。MapReduce,一种分布式计算框架应运而生。在MapReduce框架下,一个作业被分为多个任务分发到多个节点上并行执行,加快作业的完成。但在执行过程中,有的任务与其它任务相比,执行的异常缓慢,拖慢了整个作业的完成,这就是落后任务。推测执行策略是解决落后任务问题通用的方法,通过简单备份落后任务到备选机器上,期望可以加快作业完成。因此,推测执行策略包括识别作业中的落后任务以及选择合适的备份节点两步。不同的推测执行策略提出了很多落后任务识别的方法,其中FlexSlot利用k-means聚类算法识别落后任务时,无论作业中是否存在落后任务,总会识别出一类落后任务来,导致落后任务的识别准确率不高。本文分析了 FlexSlot策略落后任务识别准确率不高的原因,并对其进行改进,提出一个基于聚类优化的落后任务识别模型。首先,为了找出比较符合任务运行真实情况的任务划分,人为为k-means中的k指定一个阈值范围,在该范围内基于任务的进度率、处理带宽这两个聚类特征对任务并行聚类,得到多种聚类结果;其次,利用DBI得到最符合任务运行情况的最优任务划分;再次,为了避免将大部分正常任务识别为落后任务这种情况,利用空闲资源数以及作业任务数对落后任务类中任务的个数加以限制;最后,限制最慢任务类中的任务要慢于次慢任务类任务的α倍,保证落后任务确实很慢。为落后任务选择合适的备份节点。现有的一些推测执行策略在选择备份节点时,或是避免选择节点性能较差的节点,或是通过预测备份任务的备份时间来决定备份节点。然而,通过预测备份时间来决定备份节点的方法,往往是基于节点上已完成的历史任务信息,而不考虑备份任务实际的资源需求特性,不能很好地预测备份时间。因此本文提出一个基于Dijkstra算法的最优备份节点搜索模型。首先,基于同一作业所有任务分配的资源情况和处理带宽信息,利用线性回归建立资源速度模型,预测备份任务在可能备份节点上的处理带宽,从而得到备份任务的处理时间花销;其次,将集群节点简化为图论中的顶点,将备份任务的处理时间花销和数据迁移时间花销简化为顶点间的权重;最后,根据两种搜索策略,得到最短的备份时间以及最优备份节点。实验表明在不同工作负载下,本文提出的基于聚类优化的落后任务识别模型落后任务的识别准确率高于FlexSlot、MCP。基于Dijkstra算法的最优备份节点搜索模型能够较好的处理落后任务,比FlexSlot减少了约10%的作业执行时间,比MCP减少了约20%的作业执行时间。在备份成功率上,本文的推测执行策略的备份成功率相比FlexSlot和MCP分别提高了约12.4%、48.8%。本文提出的推测执行策略的CPU利用率和内存利用率高于FlexSlot、MCP。
【图文】：

效果图,效果图,查全率,策略

逦山东大学硕士学位论文逦逡逑由于ＦｌｅｘＳｌｏｔ的过度识别落后任务，因此它要比ＭＣＰ、本文提出ＣＯＳＲＤＮＳ查全逡逑率要高。但是查准率低对作业的影响要比查全率对作业的影响更大，因为查准率逡逑低意味着要大量备份正常任务，造成集群资源浪费，甚至会加剧落后任务问题，逡逑影响作业的完成；查全率低则意味着作业所有的落后任务，在识别时仅仅识别出逡逑一部分落后任务，那么只会备份这部分落后任务，其它落后任务不备份，不会浪逡逑费集群资源。因此本文提出的基于聚类优化的落后任务识别模型比ＭＣＰ的落后任逡逑务识别策略识别落后任务的效果好。本文提出的基于聚类优化的落后任务识别模逡逑型与ＦｌｅｘＳｌｏｔ的落后任务识别策略相比，识别准确率提高了很多，查全率稍微低一逡逑点，因此本文提出的ＣＯＳＲＤＮＳ比：ＦｌｅｘＳｌｏｔ的落后任务识别策略识别落后任务的逡逑效果好。同时，也可以看出本文提出的ＣＯＳＲＤＮＳ要比ＭＣＰ的落后任务识别策略逡逑识别落后任务的效果要好。逡逑￣１００％逦逡逑

搜索图,备份,最小值

逦山东大学硕士学位论文逦逡逑间也可表示为ｗ［ｌ］［２］。ｗ［ｌ］［２］和ｗ［ｌ］［３］表示的是落后任务经过一般节点到达数据逡逑副本所在节点的距离。根据以上两种情况，，落后任务的最短的备份时间可表示为逡逑＂？舰逦＝邋ｍｉｎ｛ｍｉｎ｛Ｄ［．／］［R%丨户邋ｅ邋厂－？／｝，邋ｍｉｎ邋｛￡＞［／］邋［ｇ］邋｜邋ｇ邋ｅ邋＃邋－邋ｙ｝｝。￡＞［／］［川表示第一逡逑种情况，可以通过遍历得到。／）［＿／］［《］表示第二种情况可以通过Ｄｉｊｋｓｔｒａ［４（）］算法得逡逑到落后任务所在节点到数据副本所在节点的最短时间。第一种情况下的最小值和逡逑第二种情况下的最小值，它们两者中的最小值就为落后任务最短的备份时间，同逡逑时得到最优备份节点。逡逑＾■＞、逦，邋、逡逑
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP311.13

【参考文献】