大规模数据并行处理应用中的弹性任务调度问题研究

摘要

Hadoop分布式计算框架有效解决了大规模数据并行处理中数据的存储与计算问题，集群资源分配及调度方式对于提高系统的整体性能具有重大的现实意义。目前，相关学者在提高数据本地化，作业完成时间，系统吞吐量等方面提出了各种启发式算法来改善系统的整体性能。然而大部分启发式算法在调度过程中采用贪心策略去调度任务，对于任务缺乏整体性规划，而且由于数据分布式存放在集群中，Shuffle阶段仍会产生网络拥塞造成作业完成时间的延迟。随着数据量的急剧增长，合理的分配及利用资源、释放项层带宽并加快作业的完成速度是目前面临的新挑战。另外，现实生活中部分用户对于作业有截止时间的要求，现有算法没有考虑到作业不同完成时间产生的不同收益问题，即作业对于截止时间的敏感程度不同。 本文针对以上两方面问题，分别设计了调度算法去解决。研究的重点:1资源分配策略;2.作业调度方法。以上两方面的好坏直接影响平台的整体性能和系统资源的利用率。 在现实生活中存在许多重复性的工作具有可预测的属性特征，通过建立相应的模型可以对作业的执行时间进行预测。另外，在研究过程中发现作业调度与矩形条装箱问题有许多相似之处，不同点是任务矩形条的形状会随着分配资源的不同而改变，我们称之为弹性作业。本文首次将集群资源调度问题转化为可变的任务矩形条装箱问题，设计了弹性作业装箱算法(Flexible Job Bin Packingalgorithm，简称FJBP)。同时本文结合遗传算法，进一步优化解集。针对作业的截止时间不同敏感性问题，本文首先将作业根据敏感程度进行了分类，设计了既考虑作业紧急程度又考虑作业预执行收益的一种作业弹性与截止时间感知的调度算法（elasticity and Deadline Aware job scheduling algorithm，简称DA）。 在Matlab仿真的环境下验证了本文算法的优势。FJBP算法缩短了作业的整体完成时间，提高了系统资源利用率，释放了项层带宽且一定程度上减少了网络拥塞。DA算法在作业执行前会去衡量作业执行的综合收益，优先选择收益大的去执行。实验表明整体收益平均提高了2.37倍。

目录

声明

摘要

第一章绪论

1．1课题研究背景

1．2国内外研究现状

1．3存在的问题及解决思路

1．4论文主要研究内容

1．5论文组织结构

1．6本章小结

第二章大数据和Hadoop核心技术简介

2．1大数据简介

2．2 Hadoop背景及结构简介

2．2．1 Hadoop背景及发展历史概述

2．2．2 Hadoop总体结构

2．2．3 Hadoop物理集群组织方式

2．3 Hadoop核心技术

2．3．1分布式文件系统

2．3．2分布式计算框架

2．3．3资源管理系统

2．4 Hadoop任务调度算法的研究

2．4．1调度器的基本结构

2．4．2 Hadoop调度算法分析

2．5本章小结

第三章一种作业弹性的装箱算法

3．1 MapReduce性能模型

3．2分析举例说明

3．3 FJBP算法实现

3．3．1算法设计思想

3．3．2具体算法设计

3．3．3实例分析说明

3．4 FJBP+GA算法实现

3．4．1算法的总体流程

3．4．2编码及适应度函数

3．4．3选择

3．4．4交叉

3．4．5变异

3．5实验仿真及分析

3．5．1实验环境

3．5．2实验结果分析

3．6本章小结

第四章截止时间感知的弹性作业调度算法

4．1需要解决的问题

4．2作业分类及目标函数抽象

4．3解决方法

4．3．1确定资源

4．3．2规划调度

4．4仿真实验及分析

4．4．1实验环境

4．4．2结果分析

4．5本章小结

第五章总结及展望

5．1论文总结

5．2未来展望

参考文献

发表论文及科研情况

致谢