A self-adaptive scheduling algorithm for reduce start time
A self-adaptive scheduling algorithm for reduce start time
复制标题
DOI：
10.1016/j.future.2014.08.011
复制
发表时间：
2015-02
期刊：
影响因子：
--
通讯作者：
Zhuo Tang;Lingang Jiang;Junqing Zhou;Kenli Li;Keqin Li-
中科院分区：
文献类型：
--
作者：
Zhuo Tang;Lingang Jiang;Junqing Zhou;Kenli Li;Keqin Li-
MapReduce是迄今为止最成功的大规模数据密集型云计算平台之一。何时启动reduce任务是提升MapReduce性能的关键问题之一。现有的实现可能会导致reduce任务块。当map任务的输出量变大时，MapReduce调度算法的性能将受到严重影响。本文通过对当前MapReduce调度机制的分析，说明了系统槽位资源浪费导致reduce任务等待的原因，并提出了一种最优的reduce调度策略，称为SARS (Self Adaptive reduce scheduling)，用于减少Hadoop平台上的任务启动时间。它可以根据每个作业上下文动态决定每个reduce任务的开始时间点，包括任务完成时间和map输出的大小。通过对作业完成时间、减少完成时间和系统平均响应时间的估计，实验结果表明，与其他算法相比，减少完成时间大幅减少。将SARS算法应用于传统作业调度算法FIFO、FairScheduler和CapacityScheduler时，平均响应时间减少11% ~ 29%。
MapReduce is by far one of the most successful realizations of large-scale data-intensive cloud computing platforms. When to start the reduce tasks is one of the key problems to advance the MapReduce performance. The existing implementations may result in a block of reduce tasks. When the output of map tasks become large, the performance of a MapReduce scheduling algorithm will be influenced seriously. Through analysis for the current MapReduce scheduling mechanism, this paper illustrates the reasons of system slot resources waste, which results in the reduce tasks waiting around, and proposes an optimal reduce scheduling policy called SARS (Self Adaptive Reduce Scheduling) for reduce tasks’ start times in the Hadoop platform. It can decide the start time point of each reduce task dynamically according to each job context, including the task completion time and the size of map output. Through estimating job completion time, reduce completion time, and system average response time, the experimental results illustrate that, when comparing with other algorithms, the reduce completion time is decreased sharply. It is also proved that the average response time is decreased by 11% to 29%, when the SARS algorithm is applied to the traditional job scheduling algorithms FIFO, FairScheduler, and CapacityScheduler.