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

摘要

由于智能硬件智能软件的发展，当今世界数据呈现出爆炸式增长。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。

目录

声明

摘要

1．1 研究背景及意义

1．2 研究内容和主要工作

1．3 论文组织结构

2．1 引言

2．2 相关工作

2．2．1 落后任务产生原因

2．2．2 推测执行策略研究

2．2．3 数据倾斜导致的落后任务的缓解策略研究

2．2．4 Hadoop集群性能优化研究

2．2．5 云环境中动态资源分配研究

2．3 本章小结

3．1 引言

3．2 落后任务识别模型

3．3 算法设计与实现

3．4 实验评估

3．4．1 实验环境

3．4．2 落后任务识别效果

3．5 本章小结

第4章 基于Dijkstra算法的最优备份节点搜索模型

4．1 引言

4．2 备份节点搜索模型

4．2．1 资源速度模型

4．2．2 节点搜索模型

4．3 算法设计与实现

4．3．1 基于线性回归的资源速度算法

4．3．2 基于Dijkstra算法最优备份节点搜索算法

4．4 实验评估

4．4．1 实验环境

4．4．2 备份成功率

4．4．3 作业执行时间

4．4．4 集群资源利用率

4．4．5 参数α值选择

4．5 本章小结

5．1 总结

5．2 展望

参考文献

致谢

攻读学位期间发表的学术论文

攻读学位期间所获的奖励情况