基于排队网络的多优先级MapReduce作业调度算法

摘要/Abstract

摘要：

MapReduce是一个能够对大规模数据进行分布式处理的框架，目前被各个领域广泛应用。在提供MapReduce服务的集群中，如何保证不同优先级用户的截止时间限定是MapReduce作业调度问题的一个挑战。针对这一问题，提出了一个基于排队网络的多优先级作业调度算法（MPSA）。首先分析和归纳了基于MapReduce模型的算法，提出了三种常见模式，采用Jackson排队网络对基于MapReduce模型的算法建立了数学模型，应用该网络模型可以求出不同优先级队列对资源的需求；随后使用AR(1)模型进行预测，使算法可以动态地适应不同的用户访问量；利用二分查找算法，分步计算出不同优先级在map阶段和reduce阶段分配的槽位数；最后实现了在MapReduce模型中应用的实时调度算法。实验结果表明，与传统的FIFO和公平调度算法相比，本文提出的算法在用户到达率和任务规模变化的情况下，可以更加有效地满足不同优先级用户的截止时间限定。

关键词: 云计算, 排队网络, MapReduce, 调度算法

Abstract:

MapReduce is a distributed computing framework for big data processing, which has been widely used in various fields. It’s a challenge to ensure the deadline of different priority users in the cluster providing MapReduce services. To solve this problem, a queuing network based multipriority scheduling algorithm (MPSA) is proposed. Firstly, the MapReduce based algorithms are summarized and analyzed, three common patterns are proposed, and the Jackson queuing network is used to build a mathematic model of the MapReduce based algorithms. The mathematic model can be used to find the resource demands of different priority queues. Secondly, the AR(1) model is used to predict the numbers of accessing users, and the binary search algorithm is used to calculate the assigned slot numbers of different priority users in map phase and reduce phase. Finally, a real time scheduling algorithm running in the MapReduce framework is implemented. Experimental results show that, compared with the traditional FIFO and fair scheduling algorithm, the proposed scheduling algorithm can ensure the defined deadlines of different priority users more effectively when the user arrival rates and the task scales change.

Key words: cloud computing;queuing network;MapReduce;scheduling algorithm

万聪，王翠荣，王聪，吕艳霞，贾朔. 基于排队网络的多优先级MapReduce作业调度算法[J]. J4, 2014, 36(12): 2286-2295.

WAN Cong，WANG Cuirong，WANG Cong，L Yanxia,JIA Shuo. A MapReduce scheduling algorithm supporting
multiple priorities based on queuing network [J]. J4, 2014, 36(12): 2286-2295.

参考文献［19］

［1］	Dean J,Ghemawat S.MapReduce:Simplified data processing on large clusters ［J］.Communications of the ACM,2008,51(1):107113.
［2］	Ranger C,Raghuraman R,Penmetsa A,et al.Evaluating MapReduce for multicore and multiprocessor systems ［C］∥Proc of High Performance Computer Architecture,2007:1324.
［3］	Hadoop ［EB/OL］. ［20140801］. http:// hadoop.apache.org/.
［4］	Lin C,Snyder L. Principles of parallel programming［M］. Lu Xinda, Lin Xinhua, translation. Beijing:China Machine Press, 2009.(in Chinese)
［5］	Job scheduling for multiuser MapReduce clusters［R］. Techical Report UCB/EECS200955, Berkeley:University of California, 2009.
［6］	Capacity scheduler guide ［EB/OL］. ［20100101］.http://hadoop.apache.org/docs/r1.2.1/capacity_scheduler.html.
［7］	Zaharia M, Konwinski A, Joseph A D, et al. Improving MapReduce performance in heterogeneous environments［C］∥Proc of the 8th USENIX Conference on Operating Systems Design and Implementation,2008:810.
［8］	Sandholm T,Lai K. Dynamic proportional share scheduling in Hadoop ［C］∥Proc of the 15th Inernational Workshop on Job Scheduling Strategies for Parallel Processing, 2010:110131.
［9］	Dong X,Wang Y,Liao H. Scheduling mixed realtime and nonrealtime applications in MapReduce environment［C］∥Proc of Parallel and Distributed Systems(ICPADS),2011:916.
［10］	Wan Cong,Wang Cuirong, Yuan Ying,et al. Gamebased scheduling algorithm to achieve optimize profit in MapReduce environment［C］∥Proc of the 9th International Conference on Intelligent Computing Theories, 2013:234240.
［11］	Wan Cong,Wang Cuirong, Wang Haiming, et al. Utilitydriven share scheduling algorithm in Hadoop ［C］∥Proc of the 10th International Symposium on Neural Networks,2013:560568.
［12］	Zhao Weizhong, Ma Huifang, Fu Yanxiang, et al. Research on parallel kmeans algorithm design based on Hadoop platform［J］. Computer Science,2011,38(10):166176.(in Chinese)
［13］	Wan Cong, Wang Cuirong, Song Xin. A MapReduce based ISODATA algorithm ［C］∥Proc of Intelligent Control and Information Processing(ICICIP),2012:765768.
［14］	Zhang Yanfeng, Gao Qixin, Gao Lixin. iMapReduce:A distributed computing framework for iterative computation［J］. Journal of Grid Computing,2012,10(1):4768.
［15］	Jiang Hongling, Shao Xiuli, Li Yaofang. Online botnet detection algorithm using MapReduce［J］.Journal of Electronics & Information Technology,2013,35(7):17321738.(in Chinese)
［16］	Alham N K, Li M, Liu Y, et al. A MapReducebased distributed SVM ensemble for scalable image classification and annotation ［J］.Computers & Mathematics with Applications,2013,66(10):19201934.
［17］	Zhang Ying, Zhao Liru, Gu Xinliang. Resource analysis method for multiservice network based on queuing network ［J］. Journal of Computer Applications, 2009,29(9):24242431.(in Chinese)
［18］	Lin Chuang. Performance evaluation of computer network and computer system［M］. Beijing:Tsinghua University Press, 2001.(in Chinese)
［19］	Zhang Yongzhong,Zhao Yinliang,Li Zengzhi.Delaybounded dispatching mechanism for supporting multiple priorities［J］. Journal of System Simulation,2007,19(5):978982.(in Chinese)
［20］	Chandra A, Gong W, Shenoy P. Dynamic resource allocation for shared data centers using online measurements ［C］∥Proc of Quality of Service—IWQoS 2003, 2003:381400.
	附中文参考文献：
［4］	Calvin Lin,Lawrence Snyder. 并行程序设计原理［M］. 陆鑫达, 林新华, 译. 北京：机械工业出版社, 2009.
［12］	赵卫中, 马慧芳, 傅燕翔, 等. 基于云计算平台Hadoop的并行kmeans聚类算法设计研究［J］.计算机科学,2011,38(10):166176.
［15］	蒋鸿玲, 邵秀丽, 李耀芳. 基于MapReduce 的僵尸网络在线检测算法［J］.电子与信息学报,2013,35(7):17321738.
［17］	张英, 赵莉茹, 谷新亮. 基于排队网络的多业务网络资源分析方法［J］.计算机应用,2009,29(9):24242431.
［18］	林闯. 计算机网络和计算机系统的性能评价［M］. 北京：清华大学出版社, 2001.
［19］	张永忠, 赵银亮, 李增智. 一个支持多优先级延迟限定的调度机制［J］.系统仿真学报,2007,19(5):978982.

[1]	李卫平1,2，武海燕2，杨杰1. 基于效益博弈的云计算资源动态可协调分配策略研究[J]. J4, 20160101, 38(01): 57-61.
[2]	李文佳, 史岚, 季航旭, 罗意彭. 面向Flink的负载均衡任务调度算法的研究与实现[J]. 计算机工程与科学, 2022, 44(07): 1141-1151.
[3]	杨柏蔼, 赵山, 刘芳. 无服务器计算技术研究综述[J]. 计算机工程与科学, 2022, 44(04): 611-619.
[4]	李波, 侯鹏, 牛力, 武浩, 丁洪伟. 基于软件定义网络的云边协同架构研究综述[J]. 计算机工程与科学, 2021, 43(02): 242-257.
[5]	嵇友浪, 朱君, 邹云峰１, 周子馨, 陈兴. 面向在线客服系统的调度算法研究[J]. 计算机工程与科学, 2020, 42(12): 2242-2251.
[6]	廖建锦, 孙庆骁, 杨海龙, 栾钟治, 钱德沛. 满足工作流执行时限的可抢占虚拟机实例配置和调度方法研究[J]. 计算机工程与科学, 2020, 42(11): 1956-1964.
[7]	关川江, 李建鹏, 史国振, 毛明. 基于关联数据本地化的多密码作业流调度算法[J]. 计算机工程与科学, 2020, 42(11): 1988-1995.
[8]	林涛, 冯竞凯, 郝章肖, 黄少群. 基于组合预测模型的云计算资源负载预测研究[J]. 计算机工程与科学, 2020, 42(07): 1168-1173.
[9]	彭晋韬1，杨章1,2,刘青凯1,2,张倩1. 结合通信重排和消息合并的通信调度方法研究[J]. 计算机工程与科学, 2020, 42(02): 191-196.
[10]	史文杰，詹雨奇，李奎. 一种面向多平台航电资源建模及其调度算法[J]. 计算机工程与科学, 2019, 41(11): 1976-1984.
[11]	刘梓璇，周建涛. 负载均衡的主导资源公平分配算法[J]. 计算机工程与科学, 2019, 41(09): 1574-1580.
[12]	王宇新，王飞，王冠，郭禾. 一种基于两级DAG模型的MapReduce工作流异构调度算法[J]. 计算机工程与科学, 2019, 41(08): 1353-1359.
[13]	李于锋1,2，莫则尧2，肖永浩1，熊敏1. 并行任务图的优化调度算法[J]. 计算机工程与科学, 2019, 41(06): 955-962.
[14]	曹云梦1,2,周胜军3,刘晨1,2,韩燕波1,2. 面向服务的云-端动态协作方法[J]. 计算机工程与科学, 2019, 41(04): 598-605.
[15]	李进生，蒙江，童名文. 基于分布式遗传算法的水质传感器布置优化研究[J]. 计算机工程与科学, 2019, 41(03): 545-550.