当前位置 >> 论文 >> 写论文 >>

关于节点方面学年毕业论文范文,与云计算文参考文献教师,云计算文参考文献培训相关论文答辩开场白

本文是一篇节点论文范文,关于节点方面在职研究生毕业论文,关于云计算文参考文献教师,云计算文参考文献培训相关学年毕业论文范文。适合节点及计算机应用及算法方面的的大学硕士和本科毕业论文以及节点相关开题报告范文和职称论文写作参考文献资料下载。

基于数据局部性的推测式Hadoop任务调度算法研究

刘奎1,,,

(1.东北大学秦皇岛分校计算机与通信学院,河北省省,2.市)

摘 要:

关 键 词:Hadoop

中图分类号:TP31文献标志码:A文章编号:

AspeculativetaskschedulingalgorithmbasedonlocalityofdatainHadoop

LIUKui1,LIUXiang-dong1,MABao-lai2,WANGCui-rong1

(1.CollegeofComputerandCommunication,NortheasternUniversityatQinHuangdao,QinHuangdaoHebei066004,China,2.CollegeUniversity,Shenyang110000,China)

Abstract:ForthereasonthattheexistingalgorithmonHadoopdoesn'thaveahighlevelofoptimization,thispaperpresentsanoveltaskschedulingalgorithmbasedondatalocalityspeculation.BycalculatingthetimedurationratioofMapandReducetaskoneachnodebinedwiththelocalcharacteristicsoftasksanddataondifferentnodes,thealgorithmintroducesamoreaccuratetaskdetectionmechanism,andthenlaunchesbackuptasksofslowtasksonfastnodes.Forusingputingmigrationinsteadofdatamigration,thealgorithmcanobtainhigherefficiency.ExperimentalresultsinHadoopshowthatparedwiththeexistingschedulingalgorithm,thealgorithmproposedinthispapercanshortenthetaskaverageoperationtimeandreducetheworkcongestioncausedbydataexchangebetweenclusterracks.Italsocanspeedupthetaskexecutionefficiency.

Keywords:Hadoop,jobscheduling,heterogeneousenvironments,localityofdata


怎样写节点本科论文
播放:23346次 评论:3789人

0引言

Amazon,Yahoo!等IT公司都推出了自己的云计算服务平台,并把云计算作为未来的重要战略之一[2].云[3].这个项目得到了雅虎公司的大力支持,进而使得Hadoop成为一个更适合并行处理大规模数据的开源分布式计算平台,并且已经在很多大型网站上得到了广泛的应用.Hadoop平台最大的优点就是在并行化技术方面对应用开发者实现了透明处理,开发人员在开发云计算的应用程序时,可以像开发普通程序一样编写代码,而不需要理解那些由Hadoop底层自动实现完成的复杂的并行化技术[4].但是,Hadoop毕竟还是一个比较年轻的平台,在很多技术细节问题还有待进一步改进,特别是在实际使用过程中暴露出的MapReduce调度器的低效性和对异构系统适应能力差的问题,任务调度技术是Hadoop平台的核心技术之一,其主要功能是对任务执行的顺序以及系统的计算资源进行合理的控制与分配.调度技术的优劣直接影响到Hadoop平台的整体执行性能和系统资源利用效率的高低,这一技术在现阶段仍然处于不完善的状态,现有的任务调度算法都存在着一些不足,限制了云计算技术在应用领域的作为.目前常见的调度算法有Hadoop的默认调度算法FIFO,这种算法不考虑作业的优先级或者大小,选取最老的作业先调度.公平调度[5]是Facebook公司贡献的,它会随着时间的推移公平分配资源.Yahoo公司开发了容量调度器[6],保证作业最小资源的同时共享多余的资源.伯克利大学提出的late[7]算法是推测式算法的一种,它会根据作业中任务的进度重新分配资源,运行效率明显优于其它调度算法,但是在数据局部性方面存在缺陷.本文对Hadoop原有的任务调度算法和late调度算法不足基础上,提出一种基于数据局部性的推测式任务调度算法,并与其它算法进行了比较研究.

1相关工作

,任务阶段性地完成,所以进度值比较小的任务被判定为慢任务.上述理想情况下的假设在异构的集群环境中都是不成立的.这使得原有的Hadoop调度算法在探测落后任务并为落后任务启动推测式备份任务的算法中显得不够精确.

Hadoop目前原有的调度算法都是假定了大部分的Map任务都是在本地数据节点中执行,没有考虑Reduce任务是否在本地读取数据执行任务的问题.根据FaceBook使用Hadoop平台的情况统计分析,拥有1至25个Map任务的小工作只有5%的任务能够在存储数据的本地节点上执行(数据局部性),如图1所示.有59%的任务在存储数据的本地机架上执行,如图2所示.因此,需要对传统的Hadoop调度算法在数据局部性上进行优化,来进一步提高算法的性能,提高整个集群资源的利用率.

图1Map任务数与本地节点Map任务数的关系

图2Map任务数与本机架上Map任务数的关系

本文对Hadoop原有的推测式任务调度做出了进一步的改进,结合Yahoo公司提出的保证作业最小资源的同时共享多余的资源的原则,考虑数据局部性和推测式算法的优势,实现了一种基于数据局部性的推测式任务调度算法LOL,通过统计执行任务节点上已经记录的数据,使得调度器能够随时收集到节点中的任务处理的有效信息,从而自主地调整任务调度队列,来提高Hadoop平台的运行效率,尤其适合在异构环境下的集群环境.

2落后任务判定算法

在快节点上为落后任务启动备份任务是减小整个工作响应时间的核心,准确判定真正的落后任务,对于减少任务响应时间至关重要.在异构环境的云计算系统中,任务的完成时间不同,落后任务完成的时间决定整个作业的运行时间,只有减小落后任务的完成时间,才能缩短整个作业完成的总时间.判定落后任务的算法是Hadoop平台的任务调度器能否高效运行的关键所在.

2.1慢任务判定算法的改进

本文将原有Hadoop调度算法中的慢任务进一步细分为Map慢任务和Reduce慢任务,正确地判断出Map慢任务和Reduce慢任务是找到落后任务的前提.

本文将Map任务又细分为两个阶段,两阶段所占Map任务总时间的比例设为MapHisFirst(MHF),MapHisSecond(MHS).对于Reduce任务继续沿用现有的Hadoop调度算法中的设定,分为三个阶段,所占时间比例设为ReduceHisFirst,ReduceHisSecond,ReduceHisThird,分别简记为RHF,RHS,RHT,并满足:

MHF+MHS等于1(1)

RHF+RHS+RHT等于1(2)

在异构环境的Hadoop集群中,由于不同的节点所具备的资源不同,磁盘读写速度,网络传输速率,CPU速度都不尽相同,所以不能保证每个节点执行任务的时间相同.但是在一个节点上的这些资源是基本保持长期不变的,在某一个节点上执行相同类型的任务所需的时间相差无几[8].在本设计中,TaskTracker上的每个任务执行完成后,将该任务执行过程中,各个阶段所耗用的时间比例记录在节点的本地磁盘上.其他任务在执行时从所属的TaskTracker所在的节点的磁盘上读取已经存储的相关的时间比例数据,记录并调整时间比例.

图3获得Map和Reduce任务时间比例算法流程图

在节点的本地磁盘上,利用已经运行过的Map任务和Reduce任务各阶段所占时间比例分别计算出各阶段耗费时间比例的平均值:**gMapFirst(AMF),**gMapSecond(AMS),**gReduceFirst(ARF),**gReduceSecond(ARS),**gReduceThird(ART).当TaskTracker启动一个新任务时,如果该任务为Map任务,则将AMF和AMS作为Map任务两阶段耗用时间比例的数据,如果该任务为Reduce型任务,则将ARF,ARS,ART作为Reduce任务三个阶段耗用时间比例的数据.获得Map任务和Reduce任务各阶段时间比例的流程如图3所示.

在计算任务的当前进度时,设任务总数为J,任务当前所处阶段为第I阶段,任务当前阶段所需处理的数据条数为M,已经处理完成的数据条数为N.任务的进度为Progress,当前阶段已经完成的进度为SProgress,J个任务的平均进度为**gProgress.则阶段内进度如公式(3)所示:

(3)

Map任务的两阶段计算进度方法如公式(4),(5)所示.


本篇论文转载于:http://www.thtc.cn/xie/07011872.html

当I等于0时,则

Progress等于AMF*SProgress(4)

当I等于1时,则

Progress等于AMF+AMS*SProgress(5)

Reduce任务的三阶段计算进度方法如公式(6),(7),(8)所示.

当I等于0时,则

Progress等于ARF*SProgress(6)

当I等于1时,则

Progress等于ARF+ARS*SProgress(7)

当I等于2时,则

Progress等于ARF+ARS+ART*SProgress(8)

J个任务的平均进度为:

(9)

这里仍然Hadoop原有的LATE算法计算任务执行速率的方式,且Map任务和Reduce任务的执行速率相同,即:

PRM等于PRR等于progress/T(10)

在式(11)中,ProgressRateMap(PRM)为单位时间内Map任务的进度增长,ProgressRateReduce(PRR)为单位时间内Reduce任务的进度增长,T为从任务开始执行到当前时间所耗用的时间.**gProgressRate(APR)是同类任务执行的平均速率,将APR分为Map任务的**gProgressRateMap(APRM)和Reduce任务的**gProgressRateReduce(APRR),Map和Reduce任务的数量分别记作CountMap(CM)和CountReduce(CR).这样,可以得到Map任务的平均速率如式(11

关于云计算文参考文献教师,云计算文参考文献培训的学年毕业论文范文
关于节点方面论文范文参考文献
)所示:

(11)

Reduce任务的平均速率如式(12)所示:

(12)

定义一个常数SlowTaskThreshold(STT)作为判定一个任务是否为慢任务的阈值,在本文中,若Map任务的速率满足:

PRM<,(1-STT)*APRM(13)

则判定该Map任务为Map慢的任务,若Reduce任务的速率满足:

PRR<,(1-STT)*APRR(14)

则判定该Reduce任务为Reduce慢的任务.

2.2任务的剩余时间估计算法

判定一个任务是否为落后任务并且为之启动备份任务需要满足以下几个条件:(1)系统中正在运行的备份任务数量小于阈值SpeculativeCap,(2)该任务已经执行超过60s,(3)该任务被判定为Map慢任务或者Reduce慢任务,(4)该任务在所属的Map慢任务或者Reduce慢任务中,是剩余时间最长的.由于Map慢的任务和Reduce慢的任务是不同类型的,所以落后任务也需被区分为Map落后任务和Reduce落后任务.寻找

1 2 3 4

怎样才能写好议论文

如何写一篇议论文

写议论文的方法

小学语文写作论文

怎么写博士论文

论文后记怎么写

如何写好历史论文

论文****

写论文公司

写一篇议论文500字

如何写好中考议论文

sci论文书写

怎样写ei论文

博士论文****

写论文的注意事项

与云计算文参考文献教师,云计算文参考文献培训相关的论文基于Zigbee和51单片机的温湿度数据采集系统的设计与实现摘要:本设计采用Zigbee通信协议,使用基于CC2430的Zigbee模块作为主通信模块,使用DHT11数字温湿度传感器进行温湿度数据的采集和发送.整个系统分为一个主节点负责和PC机通信和若干子节。引入权重的AdHoc网络分布式证书撤销算法摘要:提出一种引入等级服务权重的AdHoc网络证书撤销算法,是一种分布式算法.该算法利用撤销关系记录矩阵R(T)、节点证书特征值记录矩阵V(T)描述节点间的撤销关系和节点的可信度,利用等级服务。ZigBee无线传感器网络节点能耗检测装置的设计摘要无线传感器网络节点通常是没有稳定能源作为供给的,只能靠自身携带的电池作为能源.若无线传感器网络节点出现能源耗尽,则管理端不能正常显示其传感器节点检测。基于P2P的流媒体在网络中的应用摘要:基于P2P技术的流媒体系统,通过播放节点的相互协作,使整个系统的服务能力随节点数量的增加而增加,具有可扩展性.笔者通过对基于P2P的。一种节点加权的相似重复XML数据检测算法摘要:XML类型的数据成为当前主流的数据形式,本文提出一种检测XML数据相似性的方法,即将XML文档转换成树结构的基础上,对树结构的节点加权,并结合树编辑。高层框架节点施工的技术与管理【摘要】在高层建筑中,框架结构的节点是联系整个结构体系的枢纽,节点承受由梁端和柱端传递来的各种荷载的共同作用,在承担地震力作用时容易出现应力集中,因此,节点要保证具有足够。基于C#的网页正文信息提取摘要:快速有效的获取有用的信息是一个具有相当挑战性的课题,在传统的信息提取过程中,使用正则表达式提取网页正文信息,可以快速的获得网页的主要。无线Mesh网络的安全问题摘要:无线Mesh网络在近年来获得了飞速发展,因其速率高、自组织等特点受到普遍推崇,被认为是下一代的无线网络首选模式,有着非常广阔的应用前景.但由于其无线多跳等。节点运动的脉冲耦合无线传感器网络同步探析摘要:近年来,随着科技发展水平的显著提升,在全球传感器技术领域中,无线传感网络占据着甚为关键的应用地位,其重要性不容忽视,其中,无线传感器网络节点定位算法可作为重要的支撑技术.在此,本文将针。基于WSN的低功耗无线粮情监控系统的实现摘要:在物联网高速发展的同时,现代化技术引入到农业领域.无线传感器网络(WSN)广泛应用于对粮库环境的检测.无线通信的粮情监控系统既能有效的解决有线通信方式带来的不便,又能方。
返回论文网首页 阅读更多优秀论文
★关于本文相关开题报告