转载自董的博客
1. 目的
本文描述了hadoop中的公平调度的实现算法,公平调度器是由facebook贡献的,适合于多用户共享集群的环境的调度器,其吞吐率高于FIFO,论文参见参考资料[1]。本文分析的Hadoop版本是0.20.2,在新版本(0.21.0)中,公平调度算法已经有了改进与增强。本文组织结构如下:1)目的 2)公平调度介绍 3)公平调度算法分析 4)新版hadoop中公平调度器的新特性 5)参考资料。
2. 公平调度介绍
公平调度器按资源池(pool)来组织作业,并把资源公平的分到这些资源池里。默认情况下,每一个用户拥有一个独立的资源池,以使每个用户都能获得一份等同的集群资源而不管他们提交了多少作业。按用户的 Unix 群组或作业配置(jobconf)属性来设置作业的资源池也是可以的。在每一个资源池内,会使用公平共享(fair sharing)的方法在运行作业之间共享容量(capacity)。用户也可以给予资源池相应的权重,以不按比例的方式共享集群。
除了提供公平共享方法外,公平调度器允许赋给资源池保证(guaranteed)最小共享资源,这个用在确保特定用户、群组或生产应用程序总能获取到足够的资源时是很有用的。当一个资源池包含作业时,它至少能获取到它的最小共享资源,但是当资源池不完全需要它所拥有的保证共享资源时,额外的部分会在其它资源池间进行切分。
主要特点如下:
Ø 支持多用户多队列
Ø 资源公平共享(公平共享量由优先级决定)
Ø 保证最小共享量
Ø 支持时间片抢占
Ø 限制作业并发量,以防止中间数据塞满磁盘
3. 公平调度算法分析
3.1 变量定义
Ø 描述job信息的变量(JobInfo)
jobWeight:作业的权重。实际计算时,map阶段和reduce阶段分开,分别记为mapWeight,reduceWeight
jobDeficit:作业的缺额,即作业在理想调度器上所应得的计算时间与实际所获得的计算时间的缺额,这个是测量作业的“不公平”待遇的度量标准。实际运算时将map阶段和reduce阶段分开,分别记为mapDeficit和reduceDeficit。
runningTasks:作业正在运行的task数。实际计算时,map task和reduce task需分开,分别记为:runningMaps和runningReduces
minSlots:作业在相应的pool中的最小slot保证量,实际计算时,map阶段和reduce阶段分开,分别记为:minMaps和minReduces
jobFairShare:上次更新给该job分配的公平共享量,实际计算时,map阶段和reduce阶段分开,分别记为mapFairShare和reduceFairShare
Ø计算过程的中间变量
poolWeight:pool的权重,这个可由用户自己设定,默认为1。
tasksNum:某个作业正在运行任务与尚未运行的任务(包括Speculative 任务)数量和,有两种task类型:map task和reduce task,计算时需要分开
priorityFactor:与作业优先级相关的因子,用于计算作业的权重,具体如下:
priority |
priorityFactor |
VERY_HIGH |
4.0 |
HIGH |
2.0 |
NORMAL |
1.0 |
LOW |
0.5 |
Default |
0.25 |
poolRunningJobsWeightSum:pool中已经开始运行的所有作业的权重之和
poolLowJobsWeightSum:在某个pool中,已经开始运行的,但尚需slot(tasksNum数量大于其最小共享量)的那些作业权重之和
systemJobsWeightSum:系统(可能有很多pool)中可以运行的所有作业的权重之和
timeDelta:两次信息更新的时间间隔
3.2 相关算法
当出现一个空闲slot时,公平调度器会将此slot分配给缺额最大的作业。系统每隔500毫秒(UPDATE_INTERVAL)更新一次信息(有一个专门的更新线程对job信息进行更新),包括:作业缺额(作业的其他属性,如权重、最小共享量、公平共享量等,均是为计算缺额服务的)、权重、最小共享量、公平共享量等。
1) 作业权重计算方法
(1)默认情况下,权重是基于作业优先权的,但也可以基于作业的大小和年龄。权重的计算方法如下:
(2)根据优先权计算权重:
(3)根据用户自定义的weightAdjuster类调整权重
2) 更新权重
每个已经运行的作业权重更新公式:
3) 初始缺额计算
每个作业的初始缺额mapDeficit,reduceDeficit设置为0。
4) 更新作业的最小共享量
在每个pool中,将其拥有的slot按作业的权重分配给各个作业(由步骤(1)完成),分完之后将剩余的slot按作业的权重和缺额分配给仍需slot的作业(由步骤(2)和(3)完成),如果还有slot剩余,则将这些slot共享给其他pool。
初始化:
当前所有作业的最小共享量置零;
pool的minMaps数或者minReduces数(由用户在配置文件中设定)
重复以下几步,直到slotsLeft=0:
(1)计算每个job的最小共享量:jobinfo.minMaps或jobinfo.minReduces
首先计算该作业可获得的共享值:
根据当前pool的剩余slot数,调整该共享值:
其中runnableNum表示作业尚需的slot数与正在运行的slot数之和,curMin表示作业的当前最小共享量(jobinfo.minMaps或jobinfo.minReduces),初始值为0。
将slotsToGive作为最小共享量赋予相应的job。
修改值为值减去slotsToGive。
如果此轮循环中,slotsLeft值未变,即没有slot分给任何作业,则将剩余的slot共享给pool中所有job,即,执行(2)(3)并结束算法:
(2)将pool中的job按weight和deficit排序
(3)按顺序依次计算每个job的最小共享量。
首先计算该作业可获得的共享值:
根据当前pool的剩余slot数,调整该共享值:
将slotsToGive作为最小共享量赋予相应的job。
修改slotsLeft值为slotsLeft值减去slotsToGive。
需要注意的是,当执行完(2)(3)后,slotsLeft可能仍大于0,这时候会将剩余的slotsLeft个slot共享给其他pool。
5) 更新公平共享量
主要思想:基于作业权重和最小共享量计算公平共享量。首先,根据权重分配可用slot数,如果作业的最小共享量大于公平共享量,先要满足最小共享量,更新可用slot数,重复以上步骤,直到所有作业的最小共享量小于或等于公平共享量,这样,每个作业的最小共享量都得到了满足,最后,所有作业平分剩下的slot数。
算法实现:
初始化:当前所有作业的公平共享量置零;slotsLeft={系统中map slot 或者reduce slot 总数};jobsLeft={系统中正在运行的作业}
(1)遍历集合jobsLeft中的所有作业,计算每个作业的jobFairShare:
如果作业的最小共享量(minSlots)大于公平共享量(jobFairShare),则:将最小共享量作为公平共享量赋值给作业。
同时将此作业从集合jobsLeft中删除。
(2)将剩下的slot按权重比例给集合jobsLeft中剩余的作业:
将jobFairShare作为公平共享量赋值给作业。
6) 更新缺额
实际计算时,会分开:
7) 资源分配
当系统中产生一个空闲slot时,将此slot分配给缺额最大的作业。
4、新版hadoop中公平调度器的新特性
(1)增加抢占功能:若某个作业在一定时间间隔内获取的资源(sl0t)总小于minShare/2或者fairShare/2,则从多拿资源的作业那抢占(kill task)。
(2)系统中有多个pool时,每个pool可以配置自己的调度方式:FIFO或者fair schduler(以前强制所有pool的调度方式都一样,是要么是FIFO,要么是Fair scheduler)。
(3)支持delay scheduling(见参考文献[5])。当空闲slot没有locality的task可匹配时,调度器会选择延迟一段时间直到选中一个locality的task或者超时,如果超时(该时间内仍没有locality的task),则分配给非locality的task。
5、参考资料
(1)Fair scheduler论文:M. Zaharia, D. Borthakur, J. S. Sarma, K. Elmeleegy, S. Shenker, and I. Stoica, “Job scheduling for multi-user mapreduce clusters,” EECS Department, University of California, Berkeley, Tech. Rep., Apr 2009.【下载】
(2)Hadoop主页:http://hadoop.apache.org/
(3)Hadoop公平调度指南:http://hadoop.apache.org/common/docs/r0.20.2/fair_scheduler.html
(4)0.21.0版本中fair scheduler设计文档:【下载】
(5)Delay Scheduling: A Simple Technique for Achieving.Locality and Fairness in Cluster Scheduling. Matei Zaharia. University of California, Berkeley,【下载】
分享到:
相关推荐
HADOOP公平调度器算法解析.doc
hadoop公平调度算法解析
Hadoop公平调度器延迟调度算法延迟间隔的选择,张博钰,方维,目前,Hadoop分布式计算框架在各大互联网企业中被广泛的应用。多用户共享集群是Hadoop应用的典型场景,其中如何在保证用户作业服务质
Hadoop的利器,公平调度器算法的详细概述与实现!
公平调度器按资源池(pool)来组织作业,并把资源公平的分到这些资源池里。默认情况 下,每一个用户拥有一个独立的资源池,以使每个用户都能获得一份等同的集群资源而不管 他们提交了多少作业。按用户的 Unix 群组或...
Hadoop任务调度器 基础知识 • Hadoop调度流程 • Hadoop自带调度器介绍 • 编写自己的Hadoop调度器 • 总结
Hadoop集群作业的调度算法Hadoop集群作业的调度算法Hadoop集群作业的调度算法
Hadoop集群公平调度算法的改进,张晓莉,谷利泽,对于基于特定系统和应用建立的Hadoop集群,任务的作业优先级别有显著差异。此时原有的公平调度算法并不能很好地利用资源并完成相应
在此基础上对Yarn的FairScheduler算法进行了改进,形成了考虑节点性能的调度算法。重新对Hadoop源码进行了编译,在所搭建的Hadoop平台上进行了对比实验,证明了加入节点性能指标有效解决了Hadoop负载均衡问题,对...
Hadoop常用调度算法介绍,包括FIFO、公平调度算法、计算能力调度算法、基于朴素贝叶斯先验的调度算法、基于自适应学习的调度算法。
mapred.capacity-scheduler.queue.<queue-name>.capacity:设置调度器中各个queue的容量,这里指的是占用的集群的slots的百分比,需要注意的是,所有queue的该配置项加起来必须等于100,否则会导致JobTracker启动...
Hadoop平台下的作业调度算法研究与改进
在分析Hadoop缺省及改进的作业调度算法基础上,引入群智能算法,设计了基于改进人工鱼群算法的Hadoop作业调度算法。采用随机键方式对待分配任务进行编码,以任务总执行时间作为启发函数,并引入吞食行为和跳跃行为...
负载均衡的Hadoop平台调度算法研究.pdf
Hadoop中作业调度算法的研究与改进.pdfHadoop中作业调度算法的研究与改进.pdfHadoop中作业调度算法的研究与改进.pdfHadoop中作业调度算法的研究与改进.pdfHadoop中作业调度算法的研究与改进.pdfHadoop中作业调度算法...
基于节点性能的Hadoop作业调度算法改进.pdf
Hadoop调优之调度算法详解一,大数据开发的基本语法在这里。
通过研究蚁群算法,针对现有Hadoop调度器的不足,提出一个基于蚁群算法的Hadoop资源感知调度器及其具体实现方案。从而使Hadoop作业调度器可以更有效地对任务进行分配,提高整体架构的作业性能。通过实验证明,利用蚁...
介绍了在FACEBOOK 的中使用HADOOP 进行TASK 调度的情况