最小化多MapReduce任务总完工时间的分析模型及其应用

J4 ›› 2014, Vol. 36 ›› Issue (04): 571-578.

• 论文 • 下一篇

最小化多MapReduce任务总完工时间的分析模型及其应用

田文洪1,2,陈瑜2,王心阳2,薛瑞尼2,赵勇2

（1.电子科技大学信息与软件工程学院,四川成都 610054;
2.电子科技大学计算机科学与工程学院,四川成都 611731)

收稿日期:2013-07-10 修回日期:2013-09-08 出版日期:2014-04-25 发布日期:2014-04-25
基金资助:
国家自然科学基金资助项目（61150110486，61272528）;中央高校基金资助项目（IDZYGX2013J073）;2013年CCF腾讯科研基金资助项目

An analytical model and its applications for
minimizing total makespan of multiple MapReduce jobs

TIAN Wenhong1,2,CHEN Yu2,WANG Xinyang2,XUE Ruini2,ZHAO Yong2

(1.School of Information and Software Engineering,University of Electronic Science and Technology of China,Chengdu 610054;
2.School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China)

Received:2013-07-10 Revised:2013-09-08 Online:2014-04-25 Published:2014-04-25

摘要/Abstract

摘要：

随着大规模的MapReduce集群广泛地用于大数据处理，特别是当有多个任务需要使用同一个Hadoop集群时，一个关键问题是如何最大限度地减少集群的工作时间，提高MapReduce作业的服务效率。可将多个MapReduce作业当做一个调度任务建模，观察发现多个任务的总完工时间和任务的执行顺序有密切关系。研究目标是设计作业调度系统分析模型，最小化一批MapReduce作业的总完工时间。提出一个更好的调度策略和实现方法, 使整个调度系统符合经典Johnson算法的条件, 从而可使用经典Johnson算法在线性时间内获取总完工时间的最优解。同时，针对需要使用两个或多个资源池进行平衡的问题, 提出了一种线性时间解决方案, 优于已知的近似模拟方案。该理论模型可应用于提高系统响应速度、节能和负载均衡等方面, 对应的应用实例提供了证实。

关键词: Hadoop, MapReduce, 批量作业, 调度优化, 最小化总完工时间

Abstract:

As large-scale MapReduce clusters become widely adapted to process huge amount of data, one of critical challenges is to improve the service quality of MapReduce clusters by minimizing their makespan. A scheduling model can be considered for multiple MapReduce jobs. It is observed that the order in which these jobs are executed can have a significant impact on their overall makespan. The goal of the paper is to design a framework of automatic job scheduler and propose an analytical model for minimizing the makespan of such a set of MapReduce jobs. By considering a better strategy and implementation, we can meet the conditions of the classical Johnson algorithm and use it to find the optimal solution. Under our proposed new strategy, solving the balanced pools problem becomes exact in linear time, better than existing simulating approaches. Our proposed analytical results can be applied to improve system response time, energyefficiency and load-balance in Hadoop cluster pools, while corresponding numerical examples validate our observations.

Key words: Hadoop;MapReduce;batch workloads;optimized schedule;minimized makespan

田文洪1,2,陈瑜2,王心阳2,薛瑞尼2,赵勇2. 最小化多MapReduce任务总完工时间的分析模型及其应用[J]. J4, 2014, 36(04): 571-578.

TIAN Wenhong1,2,CHEN Yu2,WANG Xinyang2,XUE Ruini2,ZHAO Yong2. An analytical model and its applications for
minimizing total makespan of multiple MapReduce jobs [J]. J4, 2014, 36(04): 571-578.

参考文献

［1］http: // hadoop.apache.org/common/docs/ro.20.1/capacityscheduler.htm.
［2］Zaharia M, Borthakur D, Sarma J S, et al. Delay scheduling:A simple technique for achieving locality and fairness in cluster scheduling ［C］∥Proc of EuroSys, 2010:265278.
［3］Wolf J, Rajan D, Hildrum K, et al. FLEX:A slot allocation scheduling optimizer for MapReduce workloads［C］∥Proc of ACM/IFIP/USENIX International Middleware Conference, 2010:120.
［4］Verma A, Cherkasova L, Campbell R H. ARIA:Automatic resource inference and allocation for MapReduce environments［C］∥Proc of ICAC’11, 2011:235244.
［5］Verma A, Cherkasova L, Campbell R H. Play it again, SimMR!［C］∥Proc of Intl. IEEE Cluster’11, 2011:253261.
［6］Verma A, Cherkasova L, Campbell R H. Orchestrating an ensemble of MapReduce jobs for minimizing their makespan［J］. IEEE Transactions on Dependable and Secure Computing, 2013,10(5):314327.
［7］Tian Wenhong, Yeo C S, Xue Ruini,et al. Poweraware scheduling of realtime virtual machines in cloud data centers considering fixed processing intervals［C］∥Proc of IEEE CCIS’12,2012:337341.
［8］Tian Wenhong, Xue Ruini, Xiong Qing, et al. An energyefficient online parallel scheduling algorithm for cloud data centers［C］∥Proc of IEEE Services 2013,2013:1.
［9］Tian Wenhong, Zhao Yong, Zhong Yuanliang, et al. Dynamic and integrated loadbalancing scheduling algorithms for cloud data centers［J］. Journal of China Communications, 2011, 8(6):117126.
［10］Herodotou H, Babu S. Profiling, whatif analysis, and cost based optimization of MapReduce programs［J］. Proc of the VLDB Endowment, 2011,4(11):11111122.
［11］Moseley B, Dasgupta A, Kumar R, et al. On scheduling in MapReduce and flowshops［C］∥Proc of SPAA’11, 2011:289298.
［12］Verma A, Cherkasova L, Campbell R H. Two sides of a coin:Optimizing the schedule of MapReduce jobs to minimize their makespan and improve cluster performance［C］∥Proc of MASCOTS’12,2012:1118.
［13］Johnson S. Optimal two and threestage production schedules with setup times included［J］. Naval Research Logistics Quarterly, 1954, 1(1):6168.
［14］Beloglazov A, Abawajy J, Buyya R. Energyaware resource allocation heuristics for efficient management of data centers for cloud computing［J］. Future Generation Computer Systems, 2012,28(5):755768.
［15］Chen Y, Keys L, Katz R H. Towards energy efficient MapReduce［R］∥Technical Report No. UCB/EECS2009109, Berkeley:University of California,2009.
［16］Garey M, Johnson D. Computers and intractability:A guide to the theory of NPcompleteness［M］. USA:WH Freeman & Co, 1979.

[1]	苏丽，孙彦猛，张博为，杨先博，朱颖. 一种基于Hadoop+CUDA实现相关器的方法[J]. J4, 20160101, 38(01): 46-51.
[2]	赵俊生, 王鑫宇, 尹玉洁, 张林. 基于蒙古语新闻领域本体的分布式检索方法[J]. 计算机工程与科学, 2021, 43(03): 560-570.
[3]	杨青1,2,3，张亚文1,2，张琴1，袁佩玲1. 基于Hadoop的多维关联规则挖掘算法研究及应用[J]. 计算机工程与科学, 2019, 41(12): 2127-2133.
[4]	王宇新，王飞，王冠，郭禾. 一种基于两级DAG模型的MapReduce工作流异构调度算法[J]. 计算机工程与科学, 2019, 41(08): 1353-1359.
[5]	陶晓玲1,2,亢蕊楠3，刘丽燕3. 基于选择性集成的并行多分类器融合方法[J]. 计算机工程与科学, 2018, 40(05): 787-792.
[6]	王永坤1,罗萱1,金耀辉1,2. 基于私有云和物理机的混合型大数据平台设计及实现[J]. 计算机工程与科学, 2018, 40(02): 191-199.
[7]	刘鹏1,2，叶帅3，孟磊1,2，王灿4. 基于Spark的并行遗传算法求解多峰函数极值[J]. 计算机工程与科学, 2018, 40(02): 210-217.
[8]	王菁1,2，王若飞1,2. 基于日志挖掘的电商查询建议方法[J]. 计算机工程与科学, 2018, 40(02): 231-237.
[9]	肖文，胡娟，周晓峰. PFPonCanTree：一种基于MapReduce的并行频繁模式增量挖掘算法[J]. 计算机工程与科学, 2018, 40(01): 15-23.
[10]	蔡武越1,王珂2，郝玉洁2，段晓冉2. 一种Hadoop集群下的行为异常检测方法[J]. 计算机工程与科学, 2017, 39(12): 2185-2191.
[11]	赵宝文，徐华. 基于MapReduce的并行MRACO-PAM聚类算法[J]. 计算机工程与科学, 2017, 39(10): 1801-1806.
[12]	吴云蔚，宁芊. 基于Hadoop平台的分布式SVM参数寻优[J]. 计算机工程与科学, 2017, 39(06): 1042-1047.
[13]	赵一宁,肖海力. 对于大规模系统日志的日志模式提炼算法的优化[J]. 计算机工程与科学, 2017, 39(05): 821-828.
[14]	张元鸣，陈苗，陆佳炜，徐俊，肖刚. 基于MapReduce的Bagging决策树优化算法[J]. 计算机工程与科学, 2017, 39(05): 841-848.
[15]	李锦1，王联国2. 基于细菌觅食优化算法的城市轨道交通调度优化[J]. 计算机工程与科学, 2017, 39(03): 586-592.

最小化多MapReduce任务总完工时间的分析模型及其应用

An analytical model and its applications for
minimizing total makespan of multiple MapReduce jobs

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

最小化多MapReduce任务总完工时间的分析模型及其应用

An analytical model and its applications for minimizing total makespan of multiple MapReduce jobs

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

An analytical model and its applications for
minimizing total makespan of multiple MapReduce jobs