Hadoop集群作业调度算法

2024-05-17

Hadoop集群作业调度算法（精选8篇）

篇1：Hadoop集群作业调度算法

Hadoop集群中有三种作业调度算法，分别为FIFO，公平调度算法和计算能力调度算法

先来先服务(FIFO)

FIFO比较简单，hadoop中只有一个作业队列，被提交的作业按照先后顺序在作业队列中排队，新来的作业插入到队尾，一个作业运行完后，总是从队首取下一个作业运行。这种调度策略的优点是简单、易于实现，同时也减轻了jobtracker的负担。但是它的缺点也是显然的，它对所有的作业都一视同仁，没有考虑到作业的紧迫程度，另外对小作业的运行不利。

公平调度策略

这种策略在系统中配置了任务槽，一个任务槽可以运行一个task任务，这些任务就是一个大的作业被切分后的小作业。当一个用户提交多个作业时，每个作业可以分配到一定的任务槽以执行task任务(这里的任务槽可以理解为可以运行一个map任务或reduce任务)。如果把整个hadoop集群作业调度跟操作系统的作业调度相比，第一种FIFO就相当于操作系统中早期的单道批处理系统，系统中每个时刻只有一道作业在运行，而公平调度相当于多道批处理系统，它实现了同一个时刻多道作业同时运行。由于linux是多用户的，若有多个用户同时提交多个作业会怎样?在这种策略中给每个用户分配一个作业池，然后给每个作业池设置一个最小共享槽个数，什么是最小共享槽个数呢?先要理解一个最小什么意思，最小是指只要这个作业池需要，调度器应该确保能够满足这个作业池的最小任务槽数的需求，但是如何才能确保在它需要的时候就有空的任务槽，一种方法是固定分配一定数量的槽给作业池不动，这个数量至少是最小任务槽值，这样只要在作业池需要的时候就分配给它就行了，但是这样在这个作业池没有用到这么多任务槽的时候会造成浪费，这种策略实际上是这样做的，当作业池的需求没有达到最小任务槽数时，名义上是自己的剩余的任务槽会被分给其他有需要的作业池，当一个作业池需要申请任务槽的时候若系统中没有了，这时候不会去抢占别人的(也不知道抢谁的啊)，只要当前一个空的任务槽释放会被立即分配给这个作业池，

在一个用户的作业池内，多个作业如何分配槽这个可以自行选择了如FIFO。所以这种调度策略分为两级：

第一级，在池间分配槽，在多用户的情况下，每个用户分配一个作业池。

第二级，在作业池内，每个用户可以使用不同的调度策略。

计算能力调度

计算能力调度和公平调度有点类似，公平调度策略是以作业池为单位分配任务槽，而计算能力调度是以队列为单位分配tasktracker(集群中一个节点)，这种调度策略配置了多个队列，每个队列配置了最小额度的tasktracker数量，同公平调度策略类似，当一个队列有空闲的tasktracker时，调度器会将空闲的分配给其他的队列，当有空闲的tasktracker时，由于这时候可能有多个队列没有得到最小额度的tasktracker而又在申请新的，空闲的tasktracker会被优先分配到最饥饿的队列中去，如何衡量饥饿程度呢?可以通过计算队列中正在运行的任务数与其分得的计算资源之间的比值是否最低来判断的，越低说明饥饿程度越高。

计算能力调度策略是以队列的方式组织作业的，所以一个用户的作业可能在多个队列中，如果不对用户做一定的限制，很可能出现在多个用户之间出现严重不公平的现象。所以在选中新作业运行时候，还需要考虑作业所属的用户是否超过了资源的限制，如果超过，作业不会被选中。

对于在同一个队列中，这种策略使用的是基于优先级的FIFO策略，但是不会抢占。

转自：blog.csdn.net/chen_jp/article/details/7983076

篇2：Hadoop集群作业调度算法

其次，要确保本地机器上的用户对hadoop执行文件和配置文件具备相应的权限(在实验环境中，hadoop用户需要对hadoop安装文件具有执行权限;需要对hadoop配置文件具备读权限;需要对作业的jar文件具备执行权限等)。

再次，本地机器的hadoop配置文件需要与集群的配置文件一致。在一般情况下直接将集群上的配置文件拷贝下来即可。

所有这些完成后使用下面命令进行作业的提交

hadoop--config配置文件目录jar作业.jar其他参数

注意：在本次作业提交实验过程中还发现一些问题，hadoop在通过配置文件进行启动的过程中已经知道HDFS是使用的何种文件系统，

因此，在使用的过程中不需要在添加hdfs://namenode:port/。注意，如果添加了hdfs://namenode:port/一定要注意端口与配置文件的端口是不是一致。我们知道，在命令行中输入的参数具有较高的优先级。以下面的命令为例：

hadoop--config~/conffs-lsdirecotry

其中directory是不需要以hdfs://namenode:port/开头的，因为hadoop会根据配置文件～/conf进行默认判断。如果directory以hdfs://namenode:port/作为开头，那么一定要注意port。如果你没有显示表明port，默认的port是8020。在本次实验中，HDFScore-site设置的是hdfs://namenode:9001/，而我们在执行命令的时候输入的是hadoop--config~/conffs-lshdfs://namenode/这样就导致了两者的端口不一致，从而造成了麻烦。

篇3：Hadoop集群中作业调度研究

随着云计算的兴起和大数据[1]时代的到来 ,传统的数据处理方法在系统扩展性、复杂应用适用性、海量数据处理速度与存储等方面均遇到了很大的瓶颈问题 , 已经越来越难以适应新应用的要求 ,而这些瓶颈问题正是分布式系统所擅长的。Apache Hadoop[2]是一个开源、高效的分布式平台 ,它运用一切可以利用的资源 , 以“云”的形式解决大型复杂计算问题 ,同时还可以满足每个用户的需求。Hadoop是基于Java语言的分布式密集数据处理和数据分析软件框架 ,是一种低成本处理的大数据平台。

1Hadoop平台

Hadoop有两大核心框架:分布式文件系统HDFS和分布式计算框架Map/Reduce。HDFS是一个高可靠、透明、支持并发与容错的文件系统,基于主从结构设计,由NameNode和DataNode共同完成,其中数据以数据块 (block)的形式存储,NameNode主要负责数据块元数据的存储及数据块的动态信息,DataNode负责数据块的存储。 HDFS是Map/Reduce的存储基础。Map/Reduce[3]是并行处理大数据的计算框架,简单说就是任务的合成与分解。Hadoop的Map/Reduce也是一种主从结构设计,由JobTracker和TaskTracker两部分组成。JobTracker是主服务节点,其任务之一是负责作业的切分与任务的调度分配;TaskTracker是从节点,主要负责任务的执行。

2Hadoop作业调度

JobTracker服务于整个Map/Reduce计算框架,负责整个集群的作业控制和资源管理。作业控制主要是监控作业的状态,在任务调度时提供调度依据。作业调度是影响Hadoop集群性能的重要方面,直接决定了作业执行效率和集群资源利用率。作业调度由JobTracker节点上任务调度模块完成,调度流程见图1。

Hadoop作业调度采用三级策略模式[4]。Hadoop将作业执行过程分为Map阶段和Reduce阶段,分别对应Map任务和Reduce任务。这些任务被分配在集群节点的任务槽(slot)上执行,任务槽是节点资源的一种简化表示形式, 每个节点根据计算资源配置有一系列的Map槽和Reduce槽,典型的配置是节点的每个CPU配置一个槽,调度器的功能就是为任何空闲的slot分配任务。所有调度器采用三级策略,即为空闲的slot依次选取队列、作业、任务。

3Hadoop调度方法

Hadoop有3种调度器:批处理调度器FIFO及两个多用户调度器Fair Scheduler和Capacity Scheduler,本文重点研究这3种调度器。

3.1FIFO调度

FIFO是默认的调度方式,该调度将所有作业都提交到JobQueue队列,JobTracker先按照作业优先级高低, 再按照提交时间的先后顺序执行作业。Hadoop中只有一个作业队列,被提交的作业按照先后顺序在作业队列中排队,新来的作业排在队尾。一个作业运行完后,总是从队首进行下一个作业。这种调度策略的优点是简单、易于实现,减轻了Jobtracker的负担。缺点是对所有作业都一视同仁,没有考虑到作业的紧迫程度,因而对小作业的运行不利。

3.2Fair调度

Fair调度适用于多用户情形。算法设计思想是当集群中多个用户提交作业时,为了保证公平性,调度器为每个用户或组分配一个资源池,资源池里的每个作业都会按照其作业权重分配最小的资源共享量,以保证每个作业都能得到执行。当集群中的某个节点出现空闲的slot时,则选择已获得的资源量和理论上应获得的资源量的差值最大的作业来执行,以保证公平。与FIFO相比,它支持多用户多队列、资源公平共享、保证最小共享量、支持时间片抢占、限制作业并发量、防止中间数据塞满硬盘、动态调整各个资源池的资源量等,以保证调度的公平。

3.3Capacity调度

Capacity调度同样支持多用户。其设计思想是支持多个队列,每个队列可配置一定的资源量,采用FIFO调度策略。为了防止同一用户的作业独占队列资源,该调度器会对同一用户提交的作业所占资源量进行限定。调度时,首先计算每个队列中正在运行的任务数与其应该分得的计算资源比值,选择该比值最小的队列;然后按照作业优先级和提交时间顺序选择,同时考虑用户资源量限制和内存限制。该调度器的特点是保证计算能力、资源分配灵活、支持优先级、支持多重租赁、支持资源密集型作业,允许作业使用的资源量高于默认值。

4Hadoop调度器设计

随着各种应用需求的提升,已有的调度器已很难适应需求的变化,因此调度器设计也要升级。Hadoop中任务调度器被设计成一个可插拔的模块,设计从三方面考虑: 1编写JobInProgressListener;2编写调度器类,继承抽象类TaskScheduler;3配置并启用Hadoop调度器。

编写JobInProgressListener抽象类:

配置并启用Hadoop调度器:

5结语

篇4：基于遗传算法的柔性车间作业调度

【关键词】柔性车间作业调度；活性调度；遗传算法

1.引言

在基本的车间作业调度问题(Job Shop Problem，简称JSP)中，所有工件的工序都只能由指定的某一台机器进行加工。随着加工技术、自动化技术的发展，特别是柔性制造系统的出现，此传统限制已被突破，工件具有多个可选择的加工路线，即路径柔性已经成为生产的实际需求。生产技术的进步推动着调度理论研究的进深，具有柔性路径的柔性车间作业调度(Flexible Job Shop Problem，简称FJSP)研究也开始进入人们的视野并引起重视[1-3]。

目前，遗传算法以其优良的计算性能和显著的应用效果，在求解JSP问题和FJSP问题中获得了很大的成功[4-11]。本文使用遗传算法来求解FJSP问题，提出了多维矩阵的编码方式，以及相应的选择、交叉、变异操作设计，保证遗传操作每一步产生的染色体都是合法的，避免了传统柔性车间作业调度中繁琐的染色体合法化修复工作。最后用一个调度实例验证了算法的正确性和有效性。

2.调度问题描述

n种工件J={Ji|i=1，…，n}在一个由m台不同的加工机器组成的制造系统中进行加工。加工工件Ji需要p(i)道工序，每道工序都有一个可选的机器集合，其加工时间随机器的选择不同而变化。调度目标是确定每台机器上各工件的加工顺序及开工时间，使得系统的最大完成时间Cmax最小，同时给出满足要求的活动调度。假设：

(1)各工件经过准备时间后即可开始加工；

(2)每个工件在某一个时刻只能在一台机器上加工，中途不能打断；

(3)每台机器每次只能加工一个工件；

(4)不考虑工件之间的加工优先权。

3.遗传算子设计

3.1 适应度函数f(i)

染色体i的适应度值由以下公式给出，其中C是一个大的正整数。

f(i)=C-Cmax

3.2 编码

op=å(i=1，…，n)p(i)：所有工件工序数量总和。

定义染色体为矩阵ch[3][op]，该染色体蕴涵工序和机器选择的双重信息。

第一行是基于工序的编码：数字i代表工件Ji。从左到右扫描，数字i的第j次出现代表工件Ji的第j道工序，记为Oij。

第二行是基于机器的编码：[k11，k12，…，k1p(1)，…，kn1，kn2，…，knp(n)]，其中kij表示工序Oij所选择的机器号码。

第三行提供了加工时间的信息：[t11，t12，…，t1p(1)，…，tn1，tn2，…，tnp(n)]，其中tij代表工序Oij在机器kij上进行加工所需要的加工时间。

3.3 交叉与变异

为了避免交叉操作之后产生非法个体(某道工序选择了不可用的机器)，规定仅仅对染色体的第二行、第三行数据，以概率pc进行两点交叉操作。

设计两种变异算子。

对染色体第一行数据，以概率pmop进行互逆变异操作，其目的在于生成新的调度。

对染色体第二行数据，以概率pmch改变某基因的值，注意要保证选择的机器合法。之后改变染色体第三行相应位置上的值，赋予其新机器上的加工时间。

以上的编码方式结合交叉、变异操作可使得生成的染色体在工序和机器选择方面都是合法染色体。

3.4 活动调度的调整

对染色体解码时，从左到右依次扫描第一行基于工序的编码串，确定工序信息Oij，之后在第二行的编码串中找到该工序选择的机器号码，扫描完毕即得到了该染色体对应的调度形式。按照这种解码方式一般只能得到半活动调度，而不是活动调度[12]。因此，将一种插入式算法嵌入到适应度计算过程中，在有必要时调整染色体的基因序列，使其解码后生成活动调度。

这种插入算法针对所有工件的非首道工序进行处理，将其插入到对应机器上最佳可行的加工时刻安排加工，以这种方式保证所有工序都安排在最佳可行的地方，使得机器利用率最大化。

stij：当前工序Oij的开工时间；

opij：当前工序Oij的加工时间，j>1；

fti(j-1)：同一工件前道工序Oi(j-1)的完工时间，j>1；

ftm：工序Oij所选用机器目前的可用时间；

stm：同一机器上前道工序的开工时间；

在基于工序的编码方式下，各个工件的加工已经按照其工艺顺序进行。给定染色体，设系统中所有机器的可用时间为0，所有待加工工件的初始可用时间为0。从左到右扫描染色体第一行数据，确定工序Oij的加工开始时间：

for(k=1 to op)

{对每一道工序ch[0][k-1]，判断其工序信息Oij；

if(j=1)stij=ftm；

else{

if(fti(j-1)³ftm)stij=fti(j-1)；

else{

if((fti(j-1)+opij)£stm){stij=fti(j-1)；调用染色体调整过程；}

else stij=ftm；}}

}

调整过程：代表当前工序Oi的数字为a，代表同一台机器上前道工序的数字为b。在染色体第一行编码串中，将a提到b之前。

图1的甘特图中，字符串“i–j”表示工序Oij。图1(a)显示：工序O11的完工时间ft11=2；工序O21在st2=5时刻开始加工，加工完毕后有ft2=8；工序O12的加工时间op12=2。因满足条件(ft11+op12)

3.5 选择

采用适应度比例方法，并执行保优策略。即当进行交叉、变异等操作时，生成的子代种群和父代种群合并成一个新的种群，对新种群应用适应度比例方法，即轮盘赌方法进行选择，且保存当代最优个体，即适应度最大且所有机器的总完工时间最小的染色体。

4.实例仿真

以表1所示的调度问题为例，表格中的数字代表各工序在相应机器上的加工时间。

遗传算法的参数设置为：交叉概率Pc=0.85，变异概率Pmop=0.012，Pmch=0.2，种群规模popsize=40，运行次数maxrun=10，每次运行最大进化代数maxgen=100。最终得到的调度结果makespan=17。

观察表1，令每道工序都选择最小加工时间的机器，可得到工件J1、J2、J3和J4的完工时间分别为5、9、17和12，所以对于该问题，若不限制工件访问同一台机器的次数，且系统缓冲区无限，makespan=17已经是最优的调度结果。

在makespan=17的调度中，得到的最小的总完工时间为63。图2中，字符串“ij”表示工序Oij的开始加工时间是a，完工时间是b。调度的甘特图见图3，字符串“i-j”表示工序Oij。因任何工序都不可能提前操作而同时保证其他工序不延迟，因此该调度是活动调度。

5.结论

本文使用遗传算法来求解柔性车间作业活动调度问题。首先将基于工序的编码和基于机器的编码方式结合，同时对交叉操作和变异操作的对象作了规定，这些改进方法可以保证遗传操作每一步产生的染色体都是合法的，避免了传统柔性车间作业调度中繁琐的染色体合法化修复工作。为了得到活动调度的形式，在适应度计算的过程中对染色体的基因序列进行调整。用4工件6机器的柔性车间作业调度问题为例进行仿真，得到的调度结果为最优；在所有最小makespan值的调度中，进一步给出了机器总完工时间最小的调度。仿真结果表明，本文设计的遗传算法在求解柔性车间作业调度问题时是有效的。

参考文献

[1]Zribi N,Kamel AE,Borne P.Scheduling in a flexible job shop under machine availability constraints[J].APII-JESA Journal Europeen des Systemes Automatises,2007,41(6):651-671.

[2]Guohui Zhang,Liang Gao,Yang Shi.An effective genetic algorithm for the flexible job-shop scheduling problem[J].Expert Systems with Applications,2011,4(38):3563-3573.

[3]白俊杰,龚毅光,王宁生,唐敦兵.批量生产柔性作业车间作业优化调度研究[J].机械科学与技术,2010,3(29):293-298.

[4]Kacem I.Genetic algorithm for the flexible job-shop scheduling problem[C],IEEE International Conference on Systems,Man and Cybernetics,OCT 05-08,WASHINGTON D.C.2003,1-5:3464-3469.

[5]Kun Y,Zhu JY.Improved genetic algorithm for the flexible job-shop scheduling with multi-object[J].China Mechanical Engineering,2007,18(2):156-160.

[6]光熠,刘心报,程浩.求解车间作业调度问题的一种改进遗传算法[J].计算机技术与发展,2007,11(17):171-174,178.

[7]陈亮,王世进,周炳海.柔性作业车间调度问题的集成启发式算法[J].计算机工程,2008,34(1):256-258.

[8]席卫东,乔兵,朱剑英.基于改进遗传算法的柔性作业车间调度[J].哈尔滨工业大学学报,2007,39(7):1151-1153.

[9]杨红红,吴智铭.混合遗传算法在柔性系统动态调度中的应用研究[J].信息与控制,2001,30(5):392-397.

[10]方红雨,崔逊学.基于遗传算法的调度问题研究[J].电脑与信息技术,2001(2):1-5.

[11]Ferrolho A,Crisostomo M.A hybrid and flexible genetic algorithm for the job-shop scheduling problem[C].IEEE International Symposium on Computational Intelligence in Robotics and Automation.IEEE Piscataway.NJ.USA Jacksonville.FI.USA,2007:421-426.

[12]王凌.车间调度及其遗传算法[M].北京:清华大学出版社,2003.



作者简介：白康（1982—），女，河北保定人，硕士研究生，华北电力大学自动化系讲师，研究方向：智能调度与优化。

篇5：Hadoop集群作业调度算法

在大数据持续发展的今天Hadoop集群环境下调度算法的研究越来越受到重视。对于作业调度算法的改进一般都是为了减少作业的完成时间, 在同样资源的基础上减少系统消耗。例如大多数的算法都要研究数据本地性, 通过减少机架间的网络传输减少传输时间, 提高系统性能。

本文在对已有的调度策略改进时不仅注意提高作业的完成时间, 还注意了系统对作业需要的优先程度, 即一般作业使用FIFO默认调度策略思路。导致一些优先级高的作业没有在需要的时间完成, 造成系统性能降低。在其他操作系统中遇到类似情况, 一般使用优先级抢占策略, 使优先级高的作业可以抢占正在执行的优先级低的作业的资源, 达到可以降低紧急作业的响应时间。本文沿用了这一思路, 提出基于静态优先级的抢占策略。以解决作业优先级不同时如何降低紧急作业的响应时间等问题。

2 Hadoop平台 (Hadoop platform)

Hadoop平台是Apache基金组织引入[1], 受到Google开发的GPS (Google File System) 的启发, 主要由Hadoop分布式文件系统HDFS (Hadoop Distributed Files System) [2]和分布式计算框架Map Reduce[3]计算架构组成。

Hadoop平台在大数据的背景下发展飞速, 在这种背景下大量数据出现了中心聚集的问题, 每日的数据处理、作业处理在逐步上升。作业调度性能是衡量大型Hadoop平台性能的首要问题, 一个好的调度策略可以减少作业的平均完成时间, 减少系统的负荷, 提高作业的完成效率和准确性, 同时也可以有效使用平台资源[4]。在Hadoop平台中, 作业调度策略是通过作业调度器 (Hadoop Task Schedule) 对作业进行调度, 如图1所示。那么设计、使用好的Task Schedule, 对Hadoop集群平台的性能提高特别主要[5]。Hadoop中Map Reduce原有三种调度器[6]:默认的调度器FIFO Scheduler (先入先出调度) 、计算能力调度器 (Capacity Scheduler) 、公平调度器 (Fair Scheduler) 。

默认调度器FIFO是Hadoop Map/Reduce计算架构中最早的, Job Tracker在进行作业调度时使用的是FIFO (First In First Out) 算法。所有用户的作业都被提交到一个队列中, 然后由Job Tracker先按照作业的优先级高低, 再按照作业提交时间的先后顺序选择将被执行的作业。优点是调度算法简单明了, Job Tracker工作负担轻。同样缺点是忽略了不同作业的需求差异。例如如果类似对海量数据进行统计分析的作业长期占据计算资源, 那么在其后提交的交互型作业有可能迟迟得不到处理, 从而影响到用户的体验。计算能力调度器使用时, 用户需要了解大量系统信息, 才能设置和选择队列;公平调度器不考虑节点的实际负载状态, 导致节点负载不均匀。所以越来越多的研究者从多个方面对调度算法进行了深入研究。

为了研究资源调度策略, 研究者通过调查大量数据和不同的方向[9]从其他研究者的工作中, 将调度分成五类:

(1) 本地性感知调度 (Data Locality Aware Schedulers)

(2) 可靠性感知调度 (Speculative Execution Based Schedulers)

(3) 资源竞争感知调度 (Resource Contention Aware Schedulers)

(4) 性能管理感知调度 (Performance Management Based Schedulers)

(5) 能源与完成时间感知调度 (Energy and Makespan Aware Schedulers)

Map Reduce作业调度算法对集群的性能有着至关重要的影响。通过以下五个标准来比较Hadoop平台性能[10]:平均完成时间 (是一个作业从开始到结束的时间, 同时也是衡量系统性能的最重要的标准) 、公平性 (调度策略给不同的作业分配的资源是否一致) 、数据本地性 (研究调度策略的另一重要指标, 是否在存储数据节点上处理任务) 、调度时间 (调度策略的开销) 、调度策略是否达到客户对系统资源的配额。然而, 这些性能标准之间又存在互相冲突, 即当提高一些标准时, 会同时降低其他一些标准。在通常情况下, 作业的平均完成时间和数据本地性是每个调度策略都必须优先处理的性能标准

3 本地性调度算法 (Local scheduling algorithm)

数据本地性是Hadoop集群平台下衡量作业调度器的重要的标准。大量的数据在机架之间传输会产生较大的网络I/O, 特别是在多个不同的机架之间传输时延迟更大。这会使作业的平均完成时间降低, 同时还会产生大量的网络传输开销。Palanisamy等人提出Purlieus[11]算法, 该算法通过将任务调度和数据放置结合起来的方式, 使Reduce任务的本地性有较大幅度的提高。他指出, 如果不考虑数据的放置策略, 将会很难获得良好的本地性, 因为随机的数据放置策略可能会导致一些节点变得更加拥塞。一个有效的数据放置策略需要将这些特点考虑进去, 尽量将长作业的数据放到负载最小的节点上。但是这种算法仍然没有考虑到Reduce任务的本地性要求。

Hammoud等人提出本地化感知的Reduce任务调度算法LARTS[12] (Locality-Aware Reduce Tasl Scheduling for Map Reduce) 以解决Reduce任务数据本地性的问题。LARTS在Map任务完成到一定的阈值α后启动Early Shuffle机制。这种调度策略利用Early Shuffle的优点并且兼顾了Reduce任务的数据本地性。但是阀值α的设定需要根据不同类型的作业设定, 而且存在一定的误差。

4 集成静态优先级抢占的本地性调度算法 (Local scheduling algorithm with integrated static priority preemption)

对于本地性调度算法来说, 优先强调的是数据的本地性。但是, 无论是单机调度还是集群式调度都会涉及到任务的优先性问题。尤其是在集群环境下的作业调度, 当前作业的Map任务个数多, 需要系统利用大量时间进行处理计算。而后面进入的重要任务一直没办法分配到资源, 使得任务无响应, 严重时会引发系统崩溃。这样正常的本地性调度并不能处理这些问题, 本文提出静态优先级抢占式本地性调度算法。

集成静态优先级抢占的本地性调度策略, 为每一个提交的作业都设置一个静态优先级, 而被设置的静态优先级意味着作业的紧急程度。按照优先级抢占策略, 紧急程度高的作业有着较高的优先级, 它可以抢占紧急程度低的且优先级低的作业的处理资源。使得调度策略更加的有针对性, 提高调度策略对高优先级任务的关注, 使计算资源优先分配。确保紧急任务紧急处理, 减少高优先级任务的响应时间。

一般的本地性调度算法都是使用FIFO算法的调度方式, 也就是先到的作业先进行处理, 这样的调度算法缺少对任务紧要程度的关注。所以集成静态优先级抢占的本地性调度策略首先要对优先级进行定义。每个作业在提交时设置独立的参数staticpriority, 用来表示作业的紧要程度。作业越紧要越优先staticpriority值越高。

但是如果仅仅考虑到作业的优先性问题, 有可能导致作业优先级低且数据量很小的作业一直被优先级高数据量很大的作业抢占, 导致优先级低的作业一直无法执行。所以本文在定义优先级的时候加入新的参数作业的等待时间waittime。

在公式 (1) 中nowtime和submittime分别表示系统的现在时间和作业的提交时间, 通过两者做差的方式得出作业在作业池中的等待时间。

为了防止上文中提到的优先级低的作业无法执行的问题为作业的优先级加入等待时间这个影响因素。但是即使加上了作业的等待时间也会出现等待时长过长的问题。比如优先级较高的作业数据非常大, Map任务数量也较多。系统在通过原本地性调度策略后, 作业的处理时间也非常大。在处理的过程中可能会有优先级相同且数据小, Map任务个数少的作业等待时间变长。在Hadoop集群环境下不能像其他系统一样直接抢占运算资源, 因为其中涉到了Map任务完成后的中间值问题, 和Reduce任务的中间拷贝等问题。无法直接抢占原有作业的运算资源。所以作业池中的优先级定义就特别重要。在加入等待时间的基础上再加入作业的估计执行时间estimatetime如公式 (2) 。

priority是调度算法的最终优先级。α、β、γ表示其中各项参数所占比例, 对于不同种的数据类型和作业将取不同的数值, 以达到对作业优先性能的标准。其中estimatetime的确定要根据不同的本地性调度算法出发, 针对算法的本地性调度得出估计时间。

5 实验结果及性能分析 (Experimental results and performance analysis)

本文通过虚拟机的方式搭建异构测试环境。定义两个机架, 每个机架5台虚拟机, 每个虚拟机分配512MB内存。测试作业为Word Count。通过给不同大小的作业设置不同的静态优先级实验比较算法间作业的响应时间。

提交五个大小为5G的Word Count作业, 静态优先级分别设置为1、2、3、4、5, 作业编号为1、2、3、4、5。提交五个大小为10GB的Word Count作业, 静态优先级分别设置为1、2、3、4、5, 作业编号为6、7、8、9、10。

通过图2可以观察出编号为5、10的响应最快, 其次是编号4、9, 响应时间最长的是编号1、6。这样的结果可以证明前面的想法, 作业的响应时间和作业的静态优先级设置有关, 通过实验可以发现编号5、10的作业优先级最高, 调度策略将优先处理这些作业, 使得调度算法在实际上将资源倾斜。而两种作业之间比较5GB的作业处理估计时间短, 所以响应时间要比10GB的作业短。这也证明了之前的想法, 相同情况下执行时间小的作业优先处理。

6 结论 (Conclusion)

本文分析了Hadoop集群下对数据本地性调度的改进, 在保证原算法的数据本地性的前提下, 指出可以通过集成静态优先级抢占的方式提高优先级高的作业响应时间。通过获得静态优先级, 计算等待时间等参数, 得到作业的优先级。通过优先级分配资源给各个作业, 使得作业按照优先级响应。避免高优先级的作业无法执行。通过实验可以发现这种调度策略, 基本上达到了要求, 即优先级高的作业的响应时间要小于优先级低的, 等待时间长的作业对应的等待时间权值也会增加, 而执行时间小的作业在相同优先级情况下优先执行。这个算法的设计使紧急程度较高的作业能优先执行, 且尽量小的去影响其他作业。

篇6：Hadoop集群作业调度算法

摘要：文章详细介绍了Hadoop Yarn框架及Hadoop调度，并分析了Yarn框架下的标签调度（Label based scheduling）策略，以实例方式详细介绍了标签调度的应用场合和使用方法。该文的方法对基于Hadoop Yarn框架下的大数据处理平台配置，特别是异构环境中的平台优化有一定的参考意义。

关键词：大数据；框架；标签调度

中图分类号：TP311.13 文献标识码：A 文章编号：1006-8937（2015）15-0072-01

1 概述

在Hadoop0.20版本推出之后，Hadoop开源社区开始设计全新构架的新一代Hadoop系统，该版本后演化为Hadoop2.0版本，即新一代的Hadoop系统YARN。

YARN构架将主控节点的资源管理和作业管理功能分离设置，引入了全局资源管理器（Resource Manager）和针对每个作业的应用主控管理器（Application Master）。在最新的Hadoop 2.6.0版本中，YARN引入了一种新的调度策略：基于标签的调度机制。该机制的主要引入动机是更好地让YARN运行在异构集群中，进而更好地管理和调度混合类型的应用程序，本文即尝试如何使用标签调度展开讨论。

2 Hadoop Yarn框架介绍

新的Hadoop MapReduce框架命名为MapReduceV2或者叫 Yarn。重构根本的思想是将JobTracker两个主要的功能分离成单独的组件，这两个功能是资源管理和任务调度/监控。新的资源管理器全局管理所有应用程序计算资源的分配，每一个应用的ApplicationMaster负责相应的调度和协调。一个应用程序无非是一个单独的传统的MapReduce任务或者是一个DAG（有向无环图）任务。ResourceManager和每一台机器的节点管理服务器能够管理用户在那台机器上的进程并能对计算进行组织。每一个应用的ApplicationMaster的职责有：向调度器索要适当的资源容器运行任务，跟踪应用程序的状态和监控它们的进程，处理任务的失败原因。

3 Hadoop常用调度器

为了更好地理解标签调度技术，有必要回顾一下Hadoop常用的调度器。

3.1 默认的调度器FIFO

最早的Hadoop Map/Reduce 计算架构中，JobTracker 在进行作业调度时使用的FIFO（First In First Out）算法，其优点是调度算法简单明了，JobTracker工作负担轻。

3.2 公平份额调度算法（Fair Scheduler）

Fair Scheduler是由Facebook公司提出的，设计思想是，尽可能保证所有的作业都能够获得等量的资源份额，Fair Scheduler考虑了作业用户的“公平性”。

3.3 计算能力调度器（Capacity Scheduler）

Capacity Scheduler能有效的对hadoop集群的内存资源进行管理，以支持内存密集型应用。作业对内存资源需求高时，调度算法将把该作业的相关任务分配到内存资源充足的节点上。在hadoop自带的调度器中，Capacity Scheduler支持标签调度，FIFO Scheduler和Fair Scheduler尚不支持。

4 Label based scheduling应用

Label based scheduling是一种调度策略，就像priority-based scheduling一样，是调度器调度众多调度策略中的一种，可以跟其他调度策略混合使用，下面以实例说明。

不失一般性，假设有30个以上的节点，各节点硬件配置和网络部署如表一所示，其中：HighCPU组10个节点，各节点CPU运算能力较强，适合计算密集型任务；HighMEM组10个节点，计算能力普通，但各节点内存较高，适合内存密集型任务；HighIO组10个节点，计算能力和内存配置普通，但使用了IB高性能网络，网络交换能力较强，适合IO密集型任务。

假设公司运行的任务类型有三类，一类是普通的Hadoop应用，一类是运行高内存需求应用，一类是高IO的应用。

首先，用Normal、HighgCPU、Highmem、HighIO表示分配标签名，需要为三类节点创建相应的标签，方法如下：

修改capacity scheduler相关配置，设置每个队列对应的label，以及每中label的资源上下限。根据规划，应创建四个队列，假设为queue1、queue2、queue3、queue4，其中queue1队列可使用的标签是Normal和HighgCPU、Highmem、HighIO，queue2队列可使用的标签是HighCPU，queue3队列可使用的标签是HighMEM，queue4队列可使用的标签是HighIO，并配置四个队列的capacity和maxcapacity。

之后按照以下步骤操作：

步骤1：添加系统级别的label（相当于所有label的全集），注意各个节点上的label必须都在系统级别的label中。

yarn rmadmin-addToClusterNodeLabels Normal，HighCPU，HighMeM，HighIO

步骤2：为各个节点分别添加label（可动态修改）。

yarn rmadmin -replaceLabelsOnNode“nodeId，Normal，High-

CPU，HighMeM，HighIO”

注意，nodeId是nodemanager的唯一标示，注意一个节点上可以有多个nodemanager，每个nodemanager的nodeid可以在ResourceManager界面上看到，通常有host和PRC port拼接而成，默认情况下，各个nodemanager的RPC port是随机选取的，你可以将所有的nodemanager配置成一样的，便于管理：

yarn.nodemanager.address

0.0.0.0：45454

步骤3：配置label重启恢复功能。这样，label信息会保存到hdfs上（默认是保存在内存中的），之后Yarn重新启动，可以自动恢复所有label信息：

yarn.node-labels.manager-class

org.apache.hadoop.yarn.server.resourcemanager.

nodelabels.RMNodeLabelsManager

5 结语

本文详细介绍本文详细介绍了Hadoop Yarn框架下的标签调度（Label based scheduling）策略，并介绍了使用方法，但对异构环境中的资源类别划分、任务类别划分等没有作深入的讨论，用户在使用标签调度时，应根据平台的实际资源状况作出比较详细的分类，然后根据各任务的资源需求建立相对合理的配置规划，只有这样，才能充分发挥标签调度的作用。

参考文献：

[1] 邓传华，范通让，高峰.Hadoop下基于统计最优的资源调度算法[J].计算机应用研究，2013，（2）.

[2] 土峰.Hadoop集群作业的调度算法[J].程序员，2009，（12）.

篇7：Hadoop集群作业调度算法

关键词：Hadoop,负载均衡,MapReduce,调度算法

0 引言

Hadoop[1]执行MapReduce的过程主要分为Map和Reduce两个阶段[2],前者对数据进行划分和键值对处理,后者对划分后的数据片进行规约计算。然而Reducer所处理的数据是根据数据片的Key值分配的,由于数据本身特点的不确定性,K e y值的分布通常不均衡,从而导致Reducer分配到的数据量与资源也容易出现不均衡状况,在数据量较大的情况下会严重影响MapReduce的任务处理效率[3]。

针对该问题,本文通过研究Hadoop的任务调度原理,结合相关负载均衡调度算法,提出了一种新的动态优先级负载均衡算法(DPLB),实现集群作业的动态负载,提高了Hadoop集群的资源利用率和系统响应速度。

1 MapReduce在Hadoop上的任务调度

Hadoop MapReduce的任务调度主要由JobTracker和TaskTracker两个进程来完成。JobTracker的作用是作业控制、状态监控以及资源管理,TaskTracker的作用是执行JobTracker下达的命令,并且周期性地将节点资源使用情况以及任务运行状态等信息通过心跳机制[4]汇报给JobTracker。Hadoop MapReduce的任务执行过程如图1所示。

在作业调度过程中,当一个Maptask完成之后并不会主动将输出的数据发送给Reducer,而是由Reducetask通过向JobTracker询问自身的节点状态是否能接受工作任务,得到JobTracker允许后会通过http协议从完成的Maptask获取属于自己的数据块,并根据Key值进行排序,最后调用用户定义的Reduce函数进行处理并输出结果。合理的调度算法能够更充分地利用集群中的TaskTracker,提高集群的并行处理效率。

2 常用Hadoop作业调度算法

2.1 FIFO调度算法

FIFO调度算法[5]通过单队列结构来存放提交的作业,新到达的作业排在队列尾,队列头部的作业拥有最高的执行优先级。该算法的缺点是不利于多作业的并行执行,另外时间先后优先级的方式没有考虑作业之间的差异性,容易导致小作业的长时间等待,无法充分利用系统资源。

2.2 Capacity Scheduler调度算法

基于容量的调度[6]算法采用多队列结构,每个队列配置一定比例的资源,当JobTracker接到一个作业时,会对各队列当前可用资源比重进行比较,将作业分配给可用资源最多的队列。Capacity Scheduler算法灵活性较好,但在队列的资源配置上依赖经验设置,管理难度较大。

2.3 Fair Scheduler调度算法

公平调度算法[7]也采用多队列结构,不同的是该算法为每个用户配置了一个资源池,不管提交的作业有多少都能够保证每个用户分得均等的资源,并且允许每个资源池选择自己的调度方式。但该算法在分配资源池之前需要针对不同用户的数据特性做出不同的参数配置策略,因而在异构集群情况下的管理会变得十分复杂。

3 动态优先级负载均衡调度算法(DPLB)

3.1 算法思想

针对传统Hadoop集群调度算法的不足,提出DPLB(Dynamic Priority Load Balance,动态优先级负载均衡)算法。该算法利用TaskTracker周期性反馈的心跳信息计算节点负载情况与队列的任务承担能力,结合作业在队列中的等待时间与作业规模设计一种动态优先级,使小作业的等待时间减少,提高调度效率。

3.2 算法相关定义

3.2.1 节点负载能力NL与队列承载能力QL

节点负载能力计算主要依赖于TaskTracker发送的心跳信息,该信息包含的相关状态参数主要有:最大并行Map数、最大并行Reduce数、任务失败次数、CPU使用率、CPU频率、可用内存容量、可用磁盘空间以及磁盘I/O速率等。为了反映节点的负载能力,需要综合考虑这些信息,因此定义节点i的负载能力,如式(1):

根据各参数数量级的不同以及各项性能在计算中的重要性差异设计一组参数ki,这样在异构环境下能够通过心跳信息了解不同节点的负载能力。

任务队列的承载能力是JobTracker给队列分配任务的主要依据,可通过该队列所拥有的资源节点负载能力进行计算,即式(2):

3.2.2 动态优先级Pri

为了避免小作业在队列中长时间等待,对优先级计算方式进行改进,得到式(3):

其中,Twait表示作业在队列中的等待时间,Tres表示作业需要的资源量,由式(3)可以看出,作业的优先级会随着在队列中等待时间的增加而提高,同时考虑到了小作业优先执行的情况,作业需求的资源比越小,则优先级越高。

3.3 算法描述

基于心跳反馈的Hadoop动态负载均衡调度算法描述如下:

Step1:计算队列承载能力QL与当前并行的作业数TaskNum,若TaskNum达到最大并行作业数maxTask则转到Step10,否则转到Step2;

Step2:JobTracker将作业放入QL值最大的队列中;

Step3:遍历队列,根据Pri优先级进行作业排序;

Step4:计算各健康节点的负载能力NL,选出NL最高的健康节点;

Step5:判断该节点是否满足队列中一个作业的执行资源需求,满足则转Step6,否则转到Step9;

Step6:检查该节点的TaskTracker启动记录与任务失败记录,判断该节点是否健康,状态为true则转Step7,为false则转Step8;

Step7:将该节点的资源分配给该作业,转到Step1;

Step8:将该节点的健康状态标记为false,转到Step4;

Step9:将该作业转移至其它队列,转到Step3;

Step10:JobTask停止作业调度,算法结束。

过多的并行作业数量会对JobTracker造成很大负担,因此当并行的作业数量达到maxNum时会终止调度算法。另外,节点的健康与否主要由该节点执行上一个作业的失败次数来判断,若JobTracker检测到该节点在执行同一个任务时失败多次,则会将其标记为非健康节点,暂时脱离集群工作,直到管理员对该节点进行修复后将其重新分配给队列。

4 仿真实验结果与分析

4.1 实验环境与数据

根据实验室条件与设备情况,采用虚拟机搭建了4个节点的Hadoop集群,其中一个节点作为Master,其余3个节点作为Slave。为了体现异构环境,其中两台Slave虚拟主机配置为AMD单核CPU,主频2.9Gz,内存512M,硬盘大小为64G,另一台Slave与Master配置均为AMD双核CPU,主频2.9Gz,内存1G,系统采用Linux Redhat9.0,Hadoop版本为Hadoop1.2,代码编译采用Java jdk1.6.0_24。实验数据使用路透社的14 578条新闻集数据,在集群上运行K-均值聚类算法,聚类中心数设为200[8]。

4.2 实验结果与分析

实验使用DPLB算法与常用的3种Hadoop调度算法分别进行不同数据规模下的聚类分析,通过记录不同调度方式下的运行时间与节点负载情况来分析算法对Hadoop集群负载均衡的效果,结果如图2、图3所示。

从图2可以看出,DPLB算法在Hadoop作业执行的效率上与公平调度算法相当,但要优于FIFO算法与基于容量的调度算法。而在集群节点的负载均衡方面,DPLB算法取得了很好的效果。图3结果显示,DPLB算法在作业执行过程中对资源的占有量较高,究其原因在于实验中采用的数据集是条目较多的小文件,在DPLB的小作业相对优先的调度模式中使得并行的作业数增多,增加了节点压力,但在作业执行的整体效率上有明显提升。

5 结语

本文针对传统Hadoop作业调度模式可能出现的节点负载不均衡,以及资源利用率不高等问题,提出了一种动态优先级的负载均衡调度算法DPLB,通过实验证明了该算法在Hadoop集群作业的执行效率上要高于传统调度算法,并且能够有效实现集群节点的负载均衡。该算法在节点负载优化方面还有很大提升空间,后续将在此基础上重点研究如何降低TaskTracker的通信开销。

参考文献

[1]WHITE T.Hadoop:the definitive guide[M].O'Reilly,2012.

[2]DEAN B J.Mapreduce:simplified data processing on large clusters[J].Osdi’,2010,51(1):107-113.

[3]万聪,王翠荣,王聪,等.MapReduce模型中reduce阶段负载均衡分区算法研究[J].小型微型计算机系统,2015(2):240-243.

[4]关国栋,滕飞,杨燕.基于心跳超时机制的Hadoop实时容错技术[J].计算机应用,2015,35(10):2784-2788.

[5]王峰.Hadoop集群作业的调度算法[J].程序员,2009(12):119-121.

[6]CHEN H,CUI D.SLa-based hadoop capacity scheduler algorithm[C].2015International Conference on Electronic Science and Automation Control,2015.

[7]潘旭明.Map Reduce Fair Scheduler的高性能优化及超大规模集群模拟器设计及实现[D].杭州:浙江大学,2012.

篇8：Hadoop集群作业调度算法

1 Hadoop作业调度

1.1 Hadoop执行框架

Hadoop由分布式文件系统(HDFS)、分布式数据库(Hbase)实现数据的存储功能并分配到各个计算节点上,Map Reduce实现对海量数据的分布式并行处理。HDFS采用master/slave主从式架构,一个HDFS集群由一个Namenode和一定数目的Datenode组成。Namenode作为中心服务器,主要负责管理文件系统的namespace和客户端对文件的访问。Datanode在集群中主要负责管理节点上的附带的存储。

1.2 Map Reduce框架的组件及执行流程

Map Reduce是一种分布式计算框架,主要负责对大规模集群上的数据任务进行合成与分解。Map Reduce框架主要有两个组件:Job Tracker和Task-Tracker。Job Tracker负责作业的切分与任务的调度分配,运行和监控Map Reduce的Job。Task Tracker作为Hadoop计算进程,主要运行在集群的datanode节点上,负责运行Job Tracker分配给它的实际计算任务。

每个Task Tracker节点将从HDFS分布式文件中读取所有处理的数据。

2 基于ACO的Hadoop作业调度算法

2.1 蚁群算法

蚁群算法(Ant Colony Optimization,简称ACO)是一种模拟蚂蚁群体觅食行为的智能进化算法。蚂蚁之间是通过信息素进行通信的,当遇到一条新的路径时,蚂蚁会释放出一定浓度的信息素,路径越长,信息素的浓度越低,信息素浓度高的路径会有更大的概率被后来的蚂蚁再次选择,因此,便形成了正反馈机制。信息素浓度高的路径成为最优的路径。作为蚁群觅食行为的抽象,蚁群算法具有群体行为的分布式特征。具有独立意义的单只蚂蚁无法获得最优解时,不会影响到整个问题的最优解的获得。因此,蚁群算法作为一个分布式多智能体系统具有较强的全局搜索能力。

2.2 Hadoop作业调度描述

将n个相互独立的子任务分配到m个TaskTracker节点上执行,每个子任务只能分配在一个节点上执行,相关定义描述:

(1)集合T={t1,t2,…,tn}表示待分配的n个任务。

(2)集合R={r1,r2,…,rm}表示Hadoop中的m个资源。

(3)矩阵表示任务的执行时间。其中元素etij表示任务ti在rj上的执行时间。………

(4)M(i),1≤i≤n,表示任务ti被分配的资源。

(5)sj={sj(i)1≤i≤n,1≤j≤m},用户记录每个资源上的任务调度顺序,sj(i)为一个调度函数,表示ti在rj上的执行顺序。

2.3 蚁群算法应用在Hadoop中的过程

为了能够动态获得最优调度问题,在大数据处理框架Hadoop中引入蚁群算法。蚂蚁作为调度者,蚂蚁的觅食过程作为任务的调度过程。本算法中的信息素更新是由资源的效益值决定的,即效益值高并且完成时间小的任务为蚂蚁选择下一个任务的目标。

假设给定个任务个资源的任务调度问题,蚂蚁的数量为x,则蚁群算法的Hadoop任务调度过程如下:

(1)算法中每个节点上的初始信息素浓度的设置。

(2)将x只蚂蚁随机分配到m个资源节点上。

(3)计算每只蚂蚁的任务转移概率,选择下一个资源节点。

(4)完成所有任务调度,更新信息素。

(5)完成最大迭代次数,产生最佳调度结果,否则,重复执行(2)至(5).

3 实验结果

3.1 基于Hadoop集群环境设置见表1。

3.2 实验结果

在实验中所有的集群节点具有相同的配置,确保每个节点的资源(CPU、内存)相同。在Hadoop中与现有FIFO算法及计算能力调度算法进行对比验证:提交N=100个任务;M=5,10,20,30个资源节点;蚂蚁的数量x=5;最大迭代次数为100;运算时间T=END(t)-START(t),其中,END(t)为运算的结束时间,START(t)为运算的开始时间。结果为5次运算的平均值,相同环境下的结果见表2。在不同环境下,实验结果见表3。

相同实验环境,即采用完全相同的集群节点。确保每个节点具有相同的CPU和内存,选用局域网为网络环境,最大限度的保证初始节点的网络吞吐量、内存占用率一致。

从表2、表3中可以看出,无论在相同环境还是不同环境下,如果具有相同的任务量,则随着节点个数的增加,运行时间会不断减少。因为更多的节点并行执行更多的任务从而缩短了整体运行时间。

表2中,FIFO算法和计算能力算法,当节点个数增加时,每个节点分配的任务时间较短,因此具有较高的运算效率。而蚁群算法由于具有较高的复杂度,在汇总各节点信息的效率较低。当任务量增大时,随着节点个数增多,获取各个节点资源信息时间增加。因此,在相同环境下蚁群算法的效率是低于其他两种算法的。

表3中,在不同实验环境下,蚁群算法的效率要优于其他两种算法。随着节点个数的增加,运算时间也随之增加。但是,由于本实验中蚁群算法将不同的任务合理分配给了最合适的资源,使得本算法的整体时间大大优于其他两种算法。

综上所述,无论是哪种环境下,本算法都能较好的完成调度任务,使得整体运算效率较高,但由于本算法复杂度较高,且迭代次数较多,因此算法本身花费的时间相对较多。由于蚁群算法的复杂度较大,因此,并不适合于所有任务下的调度问题,只适用于不同环境下各资源节点差异较大的情况。

4 结束语

将蚁群算法应用在Hadoop平台上进行任务调度优化,根据集群各节点的情况进行任务分配,实现最优任务调度。但根据实验结果表明,在相同环境下的调度效率并未有明显优势,在未来研究中可结合其他智能算法深入研究。

参考文献

[1]王珊,王会举,覃雄派.架构大数据:挑战、现状与展望[J].计算机学报,2011,34(10):1741-1752.

[2]怀特.Hadoop权威指南[M].曾大聃,周傲英译.北京:清华大学出版社,2010.

[3]任萱萱.基于Hadoop平台的作业调度研究[D].天津:天津师范大学,2010.

[4]陈玉云,柳先辉,赵晓东.基于Hadoop平台资源调度策略的研究[J].电脑知识与技术,2012.8(19):4687-4690.