面向云计算的期限约束的MapReduce作业调度方法

doi:10.3969/j.issn.1006-2475.2018.11.010

计算机与现代化

面向云计算的期限约束的MapReduce作业调度方法

(1.江苏润和软件股份有限公司,江苏南京210012；2.中国科学院软件研究所,北京100190)

收稿日期:2018-04-27 出版日期:2018-11-22 发布日期:2018-11-23
作者简介:周博（1983-），男，吉林长春人，江苏润和软件股份有限公司工程师，学士，研究方向：分布式系统；李亚琼（1980-），男，工程师，学士，研究方向：分布式系统；刘永波（1982-），男，工程师，学士，研究方向：分布式系统；李守超（1986-），男，工程师，学士，研究方向：分布式系统；宋云奎（1979-），男，中国科学院软件研究所工程师，学士，研究方向：分布式系统。
基金资助:
国家自然科学基金资助项目（61602454）；南京市高端人才团队引进计划项目（10072090）

Deadline Constrained MapReduce Jobs Scheduling for Cloud Computing

(1. Jiangsu Hoperun Software Company, Nanjing 210012, China； 2. Institute of Software, Chinese Academy of Sciences, Beijing 100190, China)

Received:2018-04-27 Online:2018-11-22 Published:2018-11-23

摘要/Abstract

摘要： 提出一种面向异构云计算环境的截止时间约束的MapReduce作业调度方法。使用加权偶图建模MapReduce作业调度问题，将Map任务及Reduce任务与资源槽分为2个节点集合，连接2个节点集合的边的权重为任务在资源槽上的执行时间。进而，使用整数线性规划求解最小加权偶图匹配，从而得到任务到资源槽的调度方案。本文考虑了云计算环境下异构节点任务处理时间的差异性，在线动态评估和调整任务的截止时间，从而提升了MapReduce作业处理的性能。实验结果表明，所提出的方法缩短了作业数据访问的时间，最小化了截止时间冲突的作业数量。

关键词: 作业调度, 最后期限约束, 云计算, 性能管理

Abstract: This paper proposes a deadline constrained MapReduce jobs scheduling approach for cloud computing. A weighted bipartite graph is used to model the problem of scheduling MapReduce jobs. Map jobs and reduce jobs are organized as two isolated sets, and the weights of edges connecting two sets represent the executing time to execute jobs. Furthermore, an integral linear programming method is used to solve the problem of matching the bipartite graph with the least weight. The proposed scheduling approach considers heterogeneous servers in cloud computing, where different servers have different task execution time. This paper online predicts and adjusts the deadlines of different tasks, so improves the performance of processing MapReduce jobs significantly. The experimental results demonstrate that the proposed approach reduces the time of accessing data and the jobs which violates the deadline.

Key words: job scheduling, deadline constraint, cloud computing, performance management

中图分类号:

TP393

周博1，李亚琼1，刘永波1，李守超1，宋云奎2. 面向云计算的期限约束的MapReduce作业调度方法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2018.11.010.

ZHOU Bo1， LI Ya-qiong1， LIU Yong-bo1， LI Shou-chao1， SONG Yun-kui2. Deadline Constrained MapReduce Jobs Scheduling for Cloud Computing[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2018.11.010.

参考文献

［1］ MELL P. "The NIST definition of cloud computing," Version 15［J］. Communications of the ACM, 2009,53(6):50.
［2］ DEAN J, GHEMAWAT S. MapReduce: Simplified data processing on large clusters［J］. Communications of the ACM, 2008,51(1):107-113.
［3］ ZAHARIA M, BORTHAKUR D, SARMA J S, et al. Job Scheduling for Multi-user MapReduce Clusters: UCB/EECS-2009-55 ［R］. Electrical Engineering and Computer Sciences University of California at Berkeley, 2009.
［4］ LIU Z, SQUILLANTE M S, WOLF J L. On maximizing service-level-agreement profits［J］. ACM Sigmetrics Performance Evaluation Review, 2001,29(3):43-44.
［5］ POLO J, BECERRA Y, CARRERA D, et al. Deadline-based MapReduce workload management［J］. IEEE Transactions on Network & Service Management， 2013,10(2):231-244.
［6］ DONG X, WANG Y, LIAO H. Scheduling mixed real-time and non-real-time applications in MapReduce environment［C］// Proceedings of IEEE the 17th International Conference on Parallel Distributed Systems. 2011:9-16.
［7］ CHO B， RAHMAN M， CHAJED T， et al. Natjam: Design and evaluation of eviction policies for supporting priorities and deadlines in MapReduce clusters［C］// Proceedings of the 4th Annual Symposium on Cloud Computing. ACM,2013:1-17.
［8］ MATTESS M， CALHEIROS R N， BUYYA R. Scaling MapReduce applications across hybrid clouds to meet soft deadlines［C］// Proceedings of IEEE 27th International Conference on Advanced Information Networking and Applications. 2013:629-636.
［9］ XIE J, MENG F J, WANG H L, et al. Research on scheduling scheme for Hadoop clusters［J］. Procedia Computer Science, 2013,18,2468-2471.
［10］SUN M M, ZHUANG H, ZHOU X H, et al. HPSO: Prefetching based scheduling to improve data locality for MapReduce Clusters［C］// International Conference on Algorithms and Architectures for Parallel Processing. Springer, 2014:82-95.
［11］ZHANG X H, ZHONG Z Y, FENG S Z, et al. Improving data locality of MapReduce by scheduling in homogeneous computing environments［C］// IEEE the 9th International Symposium on Parallel and Distributed Processing with Applications. 2011:120-126.
［12］SEO S, JANG I, WOO K, et al. HPMR: Prefetching and pre-shuffling in shared MapReduce computation environment［C］// IEEE International Conference on Cluster Computing and Workshops. 2009:1-8.
［13］SURESH S, GOPALAN N. Delay scheduling based replication scheme for Hadoop distributed file system［J］. Information Technology and Computer Science, 2015(4):73-78.
［14］WANG W, ZHU K, YING L, et al. Map task scheduling in Mapreduce with data locality: Throughput and heavy-traffic optimality［C］// INFOCOM’13. IEEE, 2013:1609-1617.
［15］MADNI S H H, LATIFF M S A, COULIBALY Y, et al. Resource scheduling for infrastructure as a service (IaaS) in cloud computing: Challenges and opportunities［J］. Journal of Network & Computer Applications, 2016,68(C):173-200.
［16］NAYAK S C, TRIPATHY C. Deadline sensitive lease scheduling in cloud computing environment using AHP［J］. Journal of King Saud University(Computer and Information Sciences), 2018,30(2):152-163.
［17］WERF J M, DONGEN B F, HURKENS C A, et al. Process discovery using integer linear programming［C］// Proceedings of the 29th International Conference on Applications and Theory of Petri Nets. 2008:368-387.

[1]	何玉鹏, 陶勇, 王必恒, 赵英男. 智能配电网边缘计算研究现状与展望[J]. 计算机与现代化, 2023, 0(08): 87-92.
[2]	杨波, 徐胜超. 基于SRv6服务链的云网专线场景安全防护方法[J]. 计算机与现代化, 2023, 0(08): 107-111.
[3]	毛明扬, 徐胜超. 可信赖云计算的通信终端攻击行为识别算法[J]. 计算机与现代化, 2022, 0(11): 37-42.
[4]	曹禹, 李晓辉, 刘忠麟, 贾贺, 费志伟. 云环境大数据工作流编排管理系统研究综述[J]. 计算机与现代化, 2022, 0(01): 41-53.
[5]	张晓敏. 基于布隆过滤器属性基的多关键词可搜索方案[J]. 计算机与现代化, 2021, 0(08): 104-111.
[6]	邓斌涛, 徐胜超. 基于动态双子种群的差分进化K中心点聚类算法[J]. 计算机与现代化, 2021, 0(07): 54-59.
[7]	吴君才, 刘雪芳. 基于云计算和深度信念网络的数字资源配置[J]. 计算机与现代化, 2021, 0(05): 78-82.
[8]	陆歌皓, 杨丹妮. 区块链即服务的发展现状与展望[J]. 计算机与现代化, 2020, 0(10): 31-35.
[9]	梁慈1,陈世平2. 基于包簇映射架构的包漂移策略研究[J]. 计算机与现代化, 2019, 0(11): 112-.
[10]	丁顺1,陈世平2. 基于包簇映射机制的实验平台建设及应用[J]. 计算机与现代化, 2019, 0(11): 120-.
[11]	文婷婷,李洪赭. 面向云服务平台的弹性负载均衡算法[J]. 计算机与现代化, 2019, 0(10): 28-.
[12]	袁敏夫，李引，陈胜俭，郑翔蔚. 基于云平台的区块链组网方案及数据共享存储机制[J]. 计算机与现代化, 2019, 0(09): 46-.
[13]	王少强,王宇. 基于边缘计算的新型数据处理系统[J]. 计算机与现代化, 2019, 0(07): 15-.
[14]	王旭1,2，倪宏2，韩锐2. 基于拍卖的数据中心资源匹配算法[J]. 计算机与现代化, 2018, 0(10): 114-.
[15]	张兴兰,李建楠. 支持高效撤销的属性加密方案[J]. 计算机与现代化, 2018, 0(07): 114-.

面向云计算的期限约束的MapReduce作业调度方法

Deadline Constrained MapReduce Jobs Scheduling for Cloud Computing

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价