论文研究-基于负载均衡的MapReduce后备任务上限自适应算法.pdf

所需积分/C币:6 2019-07-22 19:06:38 959KB .PDF
6
收藏 收藏
举报

已有算法采用固定后备任务上限,不能动态适应负载水平变化。针对该问题,提出了基于负载均衡的MapReduce后备任务上限自适应算法。通过计算空闲节点强度和网络带宽分析系统负载水平,不断调整后备任务上限,精确控制后备任务数量,避免因过多空闲节点空载导致资源浪费或过度执行后备任务导致网络拥塞。实验表明,该算法能有效感知系统负载水平,对后备任务数量作出合理调整,并且比原算法在负载均衡和作业响应时间上有明显的提升。
第1期 李燕歌,等:基于负载均偾的 Map reduce后备任务上限自适应算法 69 由传输数据量除以传输时间得到。传输数据量用作业执行屮CPU,4GB內冇,80GB硬盘)组成集群,其屮 master一台(充 每次传输的文件块大小表小,传输时间近似看做数据非木地化当 JobTracker角色), slave八台(充当 TaskTracker角色)。输人 任务和数据本地化任务执行的时间差(数据本地化任务执行文件由 Hadoop分布式文件系统管理,文件块存储在各个计算 时间近似认为不需要传输时间,而数据非本地化任务的传输时节点的本地磁盘,每个文件块均有三个副本。系统基于Ha 间随着网络带宽的变化而变化)。求出作业i中每个任务处理op0.20.1112开发,bmnh10.10操作系统, MyEclipse7.5 的文件块j时网络带笕V和作业i执行过程中的平均传输带编程坏境。 宽V,具体计算方法如下 为了比铰该算法对不同规模作业的影响,实验诜取三组不 同规模的作业,每组作业数据量随着任务数不同而变化,结合 T2-7 实际环境中的作业负载确定每组作业的数目。各组作业参数 设置如表1所小。 Tasktracker 其中:d表小作业i中每个任务处理的文件块j的大小;Tmn、 请求任务 T分别表示作业i最近完成数据非本地化作业i中包括的文 件块数目。 bRacker判断 值得注意的是会出现T-TE≤0的现象,如当作业中 是否为块节点 没有已完成任务,以至于没有办法统计T和TL值,所以这 两个值为空,那么V就等于网终带宽最大值;当然也会出现 Tm和T其中一个值为空的现象,则v等于其余作业网终传 后备任务数量 是否达到上限 输带宽的均值。 2.3后备任务上限自适应调整 将当前Job的一个 汪务分配给该节点 后备任务数量用 Backup Iask Num表示,其取值由系统的 UltRacker将后备 工作负载Ioad得出。设个调度轮转周期为t,默认30 任务分配给该节点 集群屮工作节点数目为N 计算下一轮转周期内 推测执行的后备任务上限 Backup TaskNum < -I)×N (5) 图1算法流程图 当后备任务数量 Backup TaskNuIm满足式(5)就分配后各 仁务进行推测执行,不满足就不分配。 表1作业参数设置 组号任务数/个数据量/MB作业数/个 2.4算法描述 后备任务上限自适应具体算法伪码描述如下: 0 3200 3 输入:任务。 输出:是否调度执行。 实验从三个性能进行分析:空闲计算节点强度、不同网终 ie t do 环境下后备任务上限自适应过程以及不同调度算法对作业响 f( BackupTask\um<后备任务上限)then 应时间上的影响 Q=true;//后备务调度执行 1)空闲计算节点强度分析 Q=alse;//等待 空闲计算节点强度体现在IA算法快速感知系统工作负载 end if 变化,实时更新强度值。同时提交三组作业,空闲节点强度的 感知曲线如图2所示。其中T1为作业提交时刻,72为感知到 负载发生变化调整时刻。 end if return Q 从图2中可以得出,在0时刻因为这时作业提交得较少 后备任务进行推测执行的限制为:a)当前网络带宽大丁系统工作负载较轻平均每秒有4.2个计算节点空闲;在T时 作业执行平均带宽;h)后备仁务数量在工作负载允许的范围刻提交大量作业,占用了几乎系统所有的计算节点,所以集群 内,当前后备任务未达到后备任务数量上限。这样严格地根据负载增加,IA算法通过统计感知到了系统工作负载发生变化 工作负载和网络负载水平对后备任务数量上限进行实时控制并在30s内作出响应;在72时刻,把空闲节点强度降为2.3 的方式更适应环境的变化,比使用固定的后备任务上限的方式最终稳定在14左右 更贴近实际。基于负载均衡的后备任务上限自适应调度算法 2)不同调度算法下节点负载水平分析3 流程如图1所示。 从七个计算节点中任意选取两个计算节点分别记为1作 节点1、2,得出它们在不同算法下完成相同作业的负载量,记 3实验与结果分析 为a、b,然后计算a2-b2的值。从图3屮的三条出线可以比较 三种算法下系统的负载情况,自這应算法的由线比较接近0刻 自主搭建实验平台,由九台普通IC(每台机器都是双核度,这表明该算法具有良好的负载均衡效果。从图的后半部分 ·70 计算机应用研究 笃32卷 可以看出,自逅应算法的负载调节效率最高,因为它根据系统境。通过实验对 Mapreduce模型的自适应调度算法的性能进 负载水平实时地调整后备任务数量上限,进行合理的调度。 行测试,后备任务上限可以感知系统的工作负载和网络负载情 度算法 况,计算出合理的上限值,并在作业响应时间上优于原有算法 3000 P 自适应算法 后备任务上限自這应凋度算法相对于原来的调度算法有 很大的优势,但是该调度算法在后备任务分配中没有考虑作业 优先级问题,在以后的研究中可以加入这方而的考虑,进一步 提高 Mapreduce的性能 40C 时司/ 参考文献: 图2空闲计算节点强度感知 图3不同调度算法下节点 负载水平方差 [Ⅰ]潘巍,李战怀,伍赛.基于消息侍递机制的Map贔cduc图算沄硏究 L400 [J].计算机学报,2011,34(10):1768-1784 1006日运应算法 [2]郑启龙,房明,江胜,芨于 Mapreduce模型的并行科学计算[J 口PWS實算法 000口参数没定调疗算法 微电子学与计算机,2009,26(8):13-17. 二800 [3 DEAN J, CHEMAWAT S MapReduce simplified data processing large clusterd[ c//Proc of ther 6th Symposium on Operating System Design and Implemenlation. Berkeley: USENTX Association, 2004 [4 NIGHTINGALE E B, CHEN P M, FLINN J Speculative execution in a distributed file system C]// Proc of the 20th ACM Symposium on (p 图4作业响应时间 erating Syslems Principles. 2005: 191-205 3)不同调度算法下作业响应时间分析 [5]陈艳金. Mapreduce模型在 Hadoop平台下实现作业洞度算法的 作业响应时间是指从提交作业到作业完成所需要的时间, 研究和改进[D.广州:华南坦工大学,2011. 从用户的角度反映作业的执行开销。分别运行三组不同规模[6」赵春燕.云环境下作业调度算法研究与实现LM」.北京:北京交通 作业获得仵业的响应时问 大学出版社,2009;2058 如图4所示,对亍小规模的作业来说,后备任务上限自适[7]陈全,邓侑妮异环境下自适应的 Mapreduce调度[J.计算机 应调度算法性能与PWSW算法性能相近,其作业响应时间大 工程与科学,2009,31(A1):169-170. 约是参数设定方式的调度算法半;而对于大规模的作业,由[8]全嘉,罗军舟,宋爱波基于数据中心负载分析的自适应延迟调 于PWSW算法的后备任务上限不符合当前的负载水平导致资 度算法[冂.通讯学报,2011,32(7):4951 源竞争,所以其作业响应时间延长,而后备任务上限自适应调9张密密. Mapreduce型在 Hadoop实现中的性能分析及改进优 度算法的仵业响应时间较短。以第三组作业为例,后备任务上 化D_.成都:电子科技大学,2010 限自适应调度算法比PWSW算法少约43s,比参数设定方式 [10]姜淼, Hadoop云平台下调度算法的研宄[D].长春:言林大学 的调度算法少约511s。 [ilIHadoopondemandeb/ol.2011.http://hadoop.apacheorg 4结束语 common/does/10.18.3/hod. html [12]yahoo.Yahoo!Hadooptutorialleb/ol].2002.http://public.ya- 木文提出的基于负载均衡的 MapReduce模型后备任务上 hoo. com/gogate/hadoop-tutorial/start- tutorial. html 限自适应调度算法针对有调度算法进行改进,后备仼务上限[13]李文中,郭胜,许平.服务组合口一种自适应的负载均衙算法 随着系统负载水平自逅应调整,这样更贴近现实复杂运行坏 [J].软件学报,2006,17(5):1068-1077 (上接第44页) [2 DUAN Qing yun, SOROOSHIAN S, CUPTA V. Effective and effi- [7] WHITE K L, CHALBEY L. Sensitivity analysis, calibration, and cient global optimization for conceptual rainfall-runoff models[ J] validations for a multisite and multivariable swat modell[J. Journal Water Resources Research, 1992, 28(4): 1015-1031 of the American Water Resources Association, 2005, 41(5) [3 YALEW SG. Van GRIENSVEN A, KOKOSZKIEWICZ L. Parallel 1077-1089 computing of a large scale spatially distributed model using the soil [8] LENHART T, ECKHARDT K, FOHRER N. Comparison of two dif- nd water assessment lool[ C// Proc of the 5th Intermat ferent approaches of sensitivity analysis[J]. Physics and Chemistry gress on Environmental Modelling and Software, Modelling for Envi of the earth,2002,27(9):645454 ronment's Sake 2010 [9 Van GRIENSVEN A, MEIXNER T, GRUNWALD S. a global sensi- 4 ILYA M D, MACLEA N, JONATHAN J. A high-resolution model of tivity analysis tool for the parameters of multi-variable catchment mod soil and surface water conditions[ J]. Ecological Modelling, 2012, 23 els[ J] Journal of Hydrology, 2006, 324(1 ): 10-23 (7):109119 [10 LUO Yu-zhou, ZHANG Ming-hua. Management-oriented sensitivity a [5. MCKAY M D, BECKMAN R J. A comparison of three methods for nalysis for pesticide transport in watershed-scale water quality model selecting values of input variables in the analysis of output from a com- ing using SWat Environmental Pollution, 2009, 157(12) puter codeL J. Technometrics, 1979, 21(2): 239-245 3370-3378 [ 6. IIOLVOET K, Van GRIENSVEn A, SEUNTJENS P, et al. Sensitivity L11 GROPP W, LUSK E, SKJELLUM A. Using MPI; potable parallel analysis for hydrology and peslic ide supply towards the river in SWAT programming with the message-passing interface M]. Cambridge: MIT [J. Physics and Chemistry of the Earth, 2005, 30(8-10): 518 Press. 1994

...展开详情
试读 4P 论文研究-基于负载均衡的MapReduce后备任务上限自适应算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_39840588 欢迎大家使用并留下宝贵意见
2019-07-22
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
上传资源赚积分or赚钱
最新推荐
论文研究-基于负载均衡的MapReduce后备任务上限自适应算法.pdf 6积分/C币 立即下载
1/4
论文研究-基于负载均衡的MapReduce后备任务上限自适应算法.pdf第1页

试读结束, 可继续读1页

6积分/C币 立即下载 >