基于 LLF 的 HADOOP 任务调度器
豆丁网标准与论文:
基于 LLF 的 Hadoop 任务调度器 荆超，吕玉琴，侯宾
(北京邮电大学电子工程学院，北京 100876)
5 摘要:Hadoop 是一个优秀的开源分布式计算平台。通过 Hadoop 可以将各种不同配置的计
算机组建成低成本、高性能的分布式集群，并且具有高容错性和可扩展性。Hadoop 集群中
可以同时运行成百上千的作业，这些作业共享系统资源，所以任务调度就成为一个问题。本
文提出了一种在 Hadoop 环境下的基于最低松弛度优先的任务调度算法。目的是实现调度器
的公平性并提供特殊抢占功能。文章详细描述了该调度算法的内容，包括松弛度的表示方法、
10 优先级的计算方法以及应对超时现象的方法。另外还描述了调度器的设计结构和实现方式，
并通过实验验证调度策略的有效性。
关键词:计算机应用技术;Hadoop;任务调度;最低松弛度优先 LLF Scheduler in Hadoop 15 Jing Chao, Lv Yuqin, Hou Bin
(School of Electronic Engineering, Beijing University of Posts and Telecommunications, Beijing
100876)
Abstract: Hadoop is an excellent open-source distributed computing platform. The Hadoop can take use of different configurations of computers to build low-cost, high-performance distributed
20 clusters, with fault tolerance and scalability. Hadoop cluster can run hundreds of jobs that sharin system resources, so scheduling becomes a problem. This paper proposes a scheduling algorithm based on Least Laxity First(LLF) in Hadoop in order to achieve fairness and scheduling special preemption. This article discusses the details of the scheduling algorithm, including the representation of laxity, priority calculation method and the method of response timeouts. It also
25 describes the design and implementation of the scheduler, and shows experiments to verify the effectiveness of scheduling strategies.
Key words: computer application technology; Hadoop; task scheduling; Least Laxity First
0 引言
[1]30 Hadoop 是开源的分布式计算平台，实现了 MapReduce模型。MapReduce 是 Google 提
出的一个用于大规模计算的分布式编程模型。MapReduce 隐藏了分布式编程的底层细节，
让没有并行编程经验的开发人员也能够开发分布式程序 。在该模型中，分布式运算抽象为
Map 和 Reduce 两个步骤。开发者只需要实现 Map 和 Reduce 函数的逻辑，然后提交给
MapReduce 运行环境，计算任务便会在计算机集群上自动、并行地调度执行。 35 MapReduce 架构中包含一个 JobTracker 和若干个 TaskTraker。JobTracker 负责将作业拆
分成 Map 任务和 Reduce 任务，分发给不同的 TaskTraker 去执行，并监视 Task 的的执行情
况。默认情况下，一个 TaskTracker 可以同时运行两个 Map 任务或 Reduce 任务，这样一个
能够运行一个任务的资源称为 Slot。
由于 Hadoop 集群内的所有作业共享资源，所以需要由调度器决定作业获得资源的顺序。
40 Hadoop 默认的调度方法是先进先出(FIFO)策略，作业按照到达的顺序被提交。 公平调度
[2]算法(Fair Scheduler)目的是让所有的作业都获得相同资源。调度器将所有
资源分为若干个池(Pool)，并为每个作业池分配相同的资源。默认情况下，每个用户分属
作者简介:荆超(1987-)，男，硕士研究生，主要研究方向:云计算、数据仓库. E-mail: jingchao1024@163.com
- 1 -
豆丁网标准与论文:
在不同的作业池中，从而使得每个用户获得等量的资源。[3]Malgorzata 和 Ian 为了增加系统执行效率，设计了一种限定作业执行时间的调度器。 45 根据作业已完成部分的运行速度及预先设定的完成时间，来估计作业的资源需求量，按照这
个需求量决定作业执行的优先级。
r[4]基于 Deadline 还有另外一种调度算法 Constraint Schedule。在该算法中，作业的
Deadline 由用户指定。系统首先根据集群中最慢的节点计算出在规定 Deadline 内完成该作业
至少需要的 Slot 个数，并把这个数目的 Slot 分配给该作业。如果还有空闲 Slot，则尽量安 50 排更多的作业运行。
Laxity First， LLF)是广为人知的动态任务调度算法，已经被 最低松弛度优先(Least
[5][6]用于多核 CPU 环境和并行计算环境，但是在 MapReduce 环境还没有相关研究。
本文将提出一种 Hadoop 环境下的 LLF 任务调度算法，实现调度器的公平性并提供特殊
抢占功能。文章结构安排如下:第一部分将论述 LLF 调度器的原理。第二部分描述调度器 55 的实现方法。第三部分对 LLF 调度器进行实验验证。总结部分将概况本文内容并提出对未
来工作的展望。 1 LLF 调度算法 1.1 松弛度的表示
LLF 算法根据任务紧急的程度来计算作业的优先级。作业的紧急程度越高，其优先级就 60 越高。例如，要求一个作业在 300ms 的时候执行完，其本身运行需要 100ms，那么这个作
业的松弛程度就是 200ms，如图 1 所示。 作业开始 时间 作业运行时间 松弛度
当前时间 作业预计完成 时间
图 1 松弛度的表示 65
我们的 LLF 算法设计为可抢占式的，在每次调度的时候，即便有已经开始的作业，高
优先级的作业也可以在它们完成之前先获取资源。所以作业的运行时间并不是集中的，有可
能被打断，图 1 所述的松弛度需要进行转换。
如果用户不指定预完成时间，那么系统在一个合理的时间内完成该作业即可。这个合理70 的时间应当是根据系统的处理速度和提交作业的作业规模预计出来的。我们以这个合理完成
时间作为预计完成时间，用这个值减去当前时间作为松弛度计算的依据，如图 2 所示。
图 2 松弛度的变换表示 - 2 -
豆丁网标准与论文:
修改后的松弛度计算方法如式 4-2。 start estimated curr L= T+ T? T(2)mmm m75 startcurrestimated TTT是当前时间。我们将是作业开始的时间，是作业估计运行时间， m mm start estimatedT+ T作为作业预计完成时间，如式 4-3 所示: m m deadline start estimated(3)=+ TTT mm m
基于 LLF 的 HADOOP 任务调度器
