论文部分内容阅读
随着大数据时代的到来,如何高效地分析处理海量数据成为了计算机学科的一个新的挑战。MapReduce就是在此背景下出现并飞速发展的一种计算模型。在此之前,并非没有并行计算模型,但MapReduce凭借其简便易学,高效稳定的性能赢得了学术界和工业界的广泛认可,在大数据时代逐渐崭露头角。本文研究的,是异构MapReduce环境下,大批量作业的离线调度问题。众所周知,在MapReduce模型应用最广泛的公司中,其很大一部分需求都是针对周期性执行的日常处理任务。如Google要每天对新爬取的页面进行分析,对用户的日志进行统计等。显然,如何调度这些作业,使其在集群中按照合理的顺序执行,对于减少作业的总运行时间,提早释放系统资源有重大意义。本文的研究内容可以简要概括为:在异构环境下,针对一个给定的独立MapReduce作业集合,设计一个调度算法,使得系统的总执行时间最小。根据我们的调研,该问题是NP完全问题,最优解在现有计算能力下不能取得。故本文创新性地将该问题和两阶段流水作业调度问题类比,提出了混合多阶段调度算法。本文将该调度问题分解为两个子问题,以降低问题复杂度。针对提出的排序子问题,本文提出了基于Johnson的优先权设置算法,从而降低了由map和reduce任务依赖引起的执行时间增长。针对另一个分配子问题,我们又将其一分为二。在map阶段,通过使用Min-Min算法平衡map阶段集群中机器的负载。在reduce阶段,我们提出了Dynamic-Min-Min算法,通过在一个到达作业集合上使用分配算法,使得作业能尽量均匀地分配到集群上。最后,为了验证本文算法的性能,我们设计了一款MapReduce环境下的调度模拟器。模拟实验的结果表明本文提出的每个启发式子算法都极大降低了作业的执行时间。而和FIFO调度算法相比,本文的算法能减少51%到77%的执行时间。