基于数据局部性的推测式Hadoop任务调度算法研究（可编
辑）
基于数据局部性的推测式Hadoop任务调度算法研究 基于数据局部性的推测式Hadoop任务调度算法 研究
刘 奎1,刘向东1,马宝来2,王翠荣1
1.东北大学秦皇岛分校 计算机与通信学院,河北省省秦皇岛 066004;2. 东 北大学 信息与工程学院,沈阳市 110000
摘 要: 本文针对Hadoop平台现有任务调度算法优化程度不高的问题, 提出了一种基于数据局部性的推测式任务调度算法。该算法通过计算节点上Map
和Reduce任务时长比例,结合不同节点上数据的局部特性,采用了比现有算法更
精确的任务进度探测方式找出快慢节点,在快节点上启动剩余时间最长的落后任
务的备份任务,用移动计算代替移动数据。在Hadoop环境中进行了实验,结果表
明该算法比现有算法缩短了任务平均运行时间,加快了任务的执行效率。 关键词: Hadoop;任务调度;异构环境;数据局部性 中图分类号:TP311文献标志码: A文章编号:
A speculative task scheduling algorithm based on locality of data in Hadoop
LIU Kui1, LIU Xiang-dong1, MA Bao-lai2, WANG Cui-rong1
1. College of Computer and Communication,Northeastern University at QinHuangdao, QinHuangdao Hebei 066004, China;2. College of Information and engineering, Northeastern University , Shenyang 110000, China
Abstract: For the reason that the existing algorithm on Hadoop doesn't have a high level of optimization, this paper presents a novel task scheduling algorithm based on data locality speculation. By calculating the time duration ratio of Map and Reduce task on each node combined with the local characteristics of tasks and data on different nodes, the algorithm introduces a more accurate task detection mechanism, and then launches backup tasks of slow tasks on fast nodes. For using computing migration instead of data migration, the algorithm can obtain higher efficiency. Experimental results in Hadoop show that compared with the existing scheduling algorithm, the algorithm proposed in this paper can shorten the task average operation time and reduce the network congestion caused by data exchange between cluster racks. It also can speed up the task execution efficiency.
Key words: Hadoop; job scheduling; heterogeneous environments; locality of data
0引言 近年来,云计算作为一种新兴的商业计算模型,已经成为了学术界 和各大IT商业巨头的研究热点,发展前景广阔。迄今为止,Google、IBM、 Microsoft、Amazon、Yahoo!等IT公司都推出了自己的云计算服务平台,并把发
展云计算技术作为未来的重要战略道路之一[1-2]。云计算数据中心的资源调度
技术对于计算效率至关重要。当前,大多数开源云计算系统都是基于Hadoop资源
管理平台,尤其在研究领域使用更为广泛。Hadoop是基于谷歌的GFS分布式文件
系统以及MapReduce编程模型的核心技术开发出来的开源项目[3]。这个项目得
到了雅虎公司的大力支持,进而使得Hadoop成为一个更适合并行处理大规模数据的开源分布式计算平台,并且已经在很多大型网站上得到了广泛的应用。Hadoop平台最大的优点就是在并行化技术方面对应用开发者实现了透明处理,开发人员在开发云计算的应用程序时,可以像开发普通程序一样编写代码,而不需要理解那些由Hadoop底层自动实现完成的复杂的并行化技术[4]。但是,Hadoop毕竟还是一个比较年轻的平台,在很多技术细节问题还有待进一步改进,特别是在实际使用过程中暴露出的MapReduce调度器的低效性和对异构系统适应能力差的问题,任务调度技术是Hadoop平台的核心技术之一,其主要功能是对任务执行的顺序以及系统的计算资源进行合理的控制与分配。调度技术的优劣直接影响到Hadoop平台的整体执行性能和系统资源利用效率的高低,这一技术在现阶段仍然处于不完善的状态,现有的任务调度算法都存在着一些不足,限制了云计算技术在应用领域的作为。目前常见的调度算法有Hadoop的默认调度算法FIFO,这种算法不考虑作业的优先级或者大小,选取最老的作业先调度。公平调度[5]是Facebook公司贡献的,它会随着时间的推移公平分配资源。Yahoo公司开发了容量调度器[6],保证作业最小资源的同时共享多余的资源。伯克利大学提出的late[7]算法是推测式算法的一种,它会根据作业中任务的进度重新分配资源,运行效率明显优于其它调度算法,但是在数据局部性方面存在缺陷。本文对Hadoop原有的任务调度算法和late调度算法不足基础上,提出一种基于数据局部性的推测式任务调度算法,并与其它算法进行了比较研究。