Online task scheduling algorithm for big data analytics based on cumulative running work

doi:10.11772/j.issn.1001-9081.2019010073

Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (8): 2431-2437.DOI: 10.11772/j.issn.1001-9081.2019010073

• Frontier & interdisciplinary applications • Previous Articles Next Articles

Online task scheduling algorithm for big data analytics based on cumulative running work

LI Yefei¹, XU Chao², XU Daoqiang³, ZOU Yunfeng², ZHANG Xiaoda¹, QIAN Zhuzhong¹

1. Department of Computer Science and Technology, Nanjing University, Nanjing Jiangsu 210023, China;
2. Electric Power Research Institute, State Grid Jiangsu Electric Power Company Limited, Nanjing Jiangsu 210000, China;
3. State Grid Jiangsu Electric Power Company Limited, Nanjing Jiangsu 210000, China

Received:2019-01-11 Revised:2019-04-12 Online:2019-04-17 Published:2019-08-10
Supported by:
This work is partially supported by the Natural Science Foundation of China (61472181), the Natural Science Foundation of Jiangsu Province (BK20151392).

基于累计工作量的在线大数据分析作业调度算法

李叶飞¹, 徐超², 许道强³, 邹云峰², 张晓达¹, 钱柱中¹

1. 南京大学计算机科学与技术系, 南京 210023;
2. 国网江苏省电力有限公司电力科学研究院, 南京 210000;
3. 国网江苏省电力有限公司, 南京 210000

通讯作者: 钱柱中
作者简介:李叶飞(1979-),男,安徽池州人,工程师,硕士,主要研究方向:大数据处理;徐超(1989-),男,山东莱芜人,工程师,硕士,主要研究方向:大数据处理、信息安全;许道强(1978-),男,辽宁丹东人,高级工程师,主要研究方向:网络虚拟化、电力信息化;邹云峰(1977-),男,江西丰城人,高级工程师,硕士,主要研究方向:电力信息技术、大数据;张晓达(1991-),男,河北邢台人,博士研究生,主要研究方向:分布式大数据处理;钱柱中(1980-),男,江苏常熟人,副教授,博士,主要研究方向:分布式系统、数据中心网络。
基金资助:
国家自然科学基金项目（61472181）；江苏省自然科学基金项目（BK20151392）。

Abstract

Abstract: A Cumulative Running Work (CRW) based task scheduler CRWScheduler was proposed to effectively process tasks without any prior knowledge for big data analytics platform like Hadoop and Spark. The running job was moved from a low-weight queue to a high-weight one based on CRW. When resources were allocated to a job, both the queue of the job and the instantaneous resource utilization of the job were considered, significantly improving the overall system performance without prior knowledge. The prototype of CRWScheduler was implemented based on Apache Hadoop YARN. Experimental results on 28-node benchmark testing cluster show that CRWScheduler reduces average Job Flow Time (JFT) by 21% and decreases JFT of 95th percentile by up to 35% compared with YARN fair scheduler. Further improvements can be obtained when CRWScheduler cooperates with task-level schedulers.

Key words: data analytics system, Job Flow Time (JFT), fairness, starvation-free

摘要： 针对Hadoop和Spark等大数据分析系统中无先验知识任务的高效执行问题，设计了基于累计工作量（CRW）的任务调度器CRWScheduler。该调度器根据CRW将任务在低权重队列与高权重队列间切换；在为作业分配资源时，同时考虑到作业所在的队列和其瞬时占用资源量，无需作业先验知识即显著提升系统性能。基于Apache Hadoop YARN实现了CRWScheduler原型，在28个节点的基准测试集群上的实验表明，与YARN的公平调度机制相比，作业流时间（JFT）平均降低21%，其中95百分位的作业流时间（JFT）最多降低了35%，并且在与任务级调度程序协作时可获得进一步的性能提升。

关键词: 数据分析系统, 作业流时间, 公平性, 饥饿避免

CLC Number:

TP316.4

LI Yefei, XU Chao, XU Daoqiang, ZOU Yunfeng, ZHANG Xiaoda, QIAN Zhuzhong. Online task scheduling algorithm for big data analytics based on cumulative running work[J]. Journal of Computer Applications, 2019, 39(8): 2431-2437.

李叶飞, 徐超, 许道强, 邹云峰, 张晓达, 钱柱中. 基于累计工作量的在线大数据分析作业调度算法[J]. 计算机应用, 2019, 39(8): 2431-2437.

References

[1] Apache Software Foundation. Apache Tez[EB/OL].[2017-12-21]. http://tez.apache.org/.
[2] DEAN J, GHEMAWAT S. MapReduce:simplified data processing on large clusters[C]//Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation. Berkeley, CA:USENIX Association, 2004, 6:10-10.
[3] ISARD M, BUDIU M, YU Y, et al. Dryad:distributed data-parallel programs from sequential building blocks[C]//Proceedings of the 2nd ACM Special Interest Groups in Operating Systems (SIGOPS)/European Conference on Computer Systems. New York:ACM, 2007:59-72.
[4] ZAHARIA M, CHOWDHURY M, DAS T, et al. Resilient distributed datasets:a fault-tolerant abstraction for in-memory cluster computing[C]//Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation. Berkeley, CA:USENIX Association, 2012:15-28.
[5] GHODSI A, ZAHARIA M, HINDMAN B, et al. Dominant resource fairness:Fair allocation of multiple resource types[C]//Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation. Berkeley, CA:USENIX Association, 2011:323-336.
[6] GHODSI A, ZAHARIA M, SHENKER S, et al. Choosy:max-min fair sharing for datacenter jobs with constraints[C]//Proceedings of the 8th ACM European Conference on Computer Systems. New York:ACM, 2013:365-378.
[7] HINDMAN B, KONWINSKI A, ZAHARIA M, et al. Mesos:A platform for fine-grained resource sharing in the data center[C]//Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation. Berkeley, CA:USENIX Association, 2011:295-308.
[8] VAVILAPALLI V K, MURTHY A C, DOUGLAS C, et al. Apache hadoop YARN:yet another resource negotiator[C]//Proceedings of the 4th Annual Symposium on Cloud Computing. New York:ACM, 2013:1-16.
[9] WANG W, LIANG B, LI B. Multi-resource fair allocation in heterogeneous cloud computing systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(10):2822-2835.
[10] ZAHARIA M, BORTHAKUR D, SARMA J S, et al. Delay scheduling:a simple technique for achieving locality and fairness in cluster scheduling[C]//Proceedings of the 5th ACM European Conference on Computer Systems. New York:ACM, 2013:265-278.
[11] Apache Software Foundation. Hadoop MapReduce Next Generation-Fair Scheduler[EB/OL].[2018-10-21]. http://tinyurl.com/j9vzsl9.
[12] GRANDL R, CHOWDHURY M, AKELLA A, et al. Altruistic scheduling in multi-resource clusters[C]//Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation. Berkeley, CA:USENIX Association, 2016:65-80.
[13] GRANDL R, KANDULA S, RAO S, et al. Graphene:packing and dependency-aware scheduling for data-parallel clusters[C]//Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation. Berkeley, CA:USENIX Association, 2016:81-97.
[14] AGRAWAL K, LI J, LU K, et al. Scheduling parallel DAG jobs online to minimize average flow time[C]//Proceedings of the 27th annual ACM-SIAM Symposium on Discrete algorithms. Philadelphia, PA:Society for Industrial and Applied Mathematics, 2016:176-189.
[15] FERGUSON A D, BODIK P, KANDULA S, et al. Jockey:guaranteed job latency in data parallel clusters[C]//Proceedings of the 7th ACM European Conference on Computer Systems. New York:ACM, 2012:99-112.
[16] GRANDL R, ANANTHANARAYANAN G, KANDULA S, et al. Multi-resource packing for cluster schedulers[C]//Proceedings of the 2014 ACM Conference on SIGCOMM. New York:ACM, 2014:455-466.
[17] JALAPARTI V, BODIK P, MENACHE I, et al. Network-aware scheduling for data-parallel jobs:Plan when you can[C]//Proceedings of the 2015 ACM Conference on SIGCOMM. New York:ACM, 2015:407-420.
[18] RAI I A, URVOY-KELLER G, BIERSACK E W. Analysis of LAS scheduling for job size distributions with high variance[C]//Proceedings of the 2003 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. New York:ACM, 2003:218-228.
[19] BAI W, CHEN L, CHEN K, et al. Information-agnostic flow scheduling for commodity data centers[C]//Proceedings of the 12th USENIX Symposium on Networked Systems Design and Implementation. Berkeley, CA:USENIX Association, 2015:455-468.
[20] CHOWDHURY M, STOICA I. Efficient coflow scheduling without prior knowledge[C]//Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication. New York:ACM, 2015:393-406.
[21] Apache Software Foundation. Apache Hadoop NextGen MapReduce (YARN)[EB/OL].[2017-12-21]. http://tinyurl.com/zyy8kbc.
[22] 吴信东,嵇圣硙.MapReduce与Spark用于大数据分析值比较[J].软件学报,2018,29(6):1770-1791. (WU X D, JI S W. Comparive study on MapReduce and Spark for bid data analytics[J]. Journal of Software, 2018, 29(6):1770-1791.)
[23] ISARD M, PRABHAKARAN V, CURREY J, et al. Quincy:fair scheduling for distributed computing clusters[C]//Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles. New York:ACM, 2009:261-276.
[24] AHMAD F, CHAKRADHAR S, RAGHUNATHAN A, et al. Shufflewatcher:Shuffle-aware scheduling in multi-tenant mapreduce clusters[C]//USENIX Proceedings of 2014 USENIX Annual Technical Conference. Berkeley, CA:USENIX Association, 2014:1-12.
[25] BLUMOFE R D, LEISERSON C E. Scheduling multithreaded computations by work stealing[J]. Journal of the ACM. 1999, 46(5):720-748.
[26] EDMONDS J, PRUHS K. Scalably scheduling processes with arbitrary speedup curves[J]. ACM Transactions on Algorithms, 2012, 8(3):256-265.
[27] 王习特,申德荣,于戈,等.MapReduce集群中最大收益问题的研究[J].计算机学报,2015,38(1):109-121. (WANG X T, SHEN D R, YU G, et al. Research on maximum benefit problem in a MapReduce cluster[J]. Chinese Journal of Computers, 2015, 38(1):109-121.)
[28] VAZIRANI V V. Approximation Algorithms[M]. Berlin:Springer, 2003:74-78.
[29] NAIR J, WIERMAN A, ZWART B. The fundamentals of heavy-tails:properties, emergence, and identification[C]//Proceedings of the ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems. New York:ACM, 2013:387-388.
[30] WIKIPEDIA. Max-min fairness[EB/OL].[2017-12-21]. http://tinyurl.com/krkdmho.
[31] Apache Software Foundation. Hadoop MapReduce Next Generation-Capacity Scheduler[EB/OL].[2018-12-01]. http://tinyurl.com/j739ojm.
[32] Apache Software Foundation. Apache Spark[EB/OL].[2018-11-07]. http://spark.apache.org/.

Online task scheduling algorithm for big data analytics based on cumulative running work

基于累计工作量的在线大数据分析作业调度算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	DU Xueling, MENG Xuelei, YANG Bei, TANG Lin. Emergency resource assignment for requirements of multiple disaster sites in view of fairness [J]. Journal of Computer Applications, 2018, 38(7): 2089-2094.
[2]	HU Jing, ZHENG Wu. Proportional fairness and maximum weighted sum-rate in D2D communications underlaying cellular networks [J]. Journal of Computer Applications, 2017, 37(5): 1321-1325.
[3]	NI Junhong, SHEN Zhentao, YANG Huifeng. D2D power allocation based on max-min fairness underlying cellular systems [J]. Journal of Computer Applications, 2017, 37(4): 945-947.
[4]	ZUO Yuxing, GUO Aihuang, HUANG Bo, WANG Lu. Power control algorithm based on network utility maximization in Internet of vehicles [J]. Journal of Computer Applications, 2017, 37(12): 3345-3350.
[5]	LIU Xi, ZHANG Xiaolu, ZHANG Xuejie. Fair allocation of multi-dimensional resources based on intelligent optimization algorithm in heterogeneous cloud environment [J]. Journal of Computer Applications, 2016, 36(8): 2128-2133.
[6]	KE Zunwang, YU Jiong, LIAO Bin. Adaptive multi-resource scheduling dominant resource fairness algorithm for Mesos in heterogeneous clusters [J]. Journal of Computer Applications, 2016, 36(5): 1216-1221.
[7]	ZHU Qingchao, CHEN Jing, GONG Shuiqing. Throughput analysis and optimization of MAC protocol with multiple rates in mobile Ad Hoc network [J]. Journal of Computer Applications, 2016, 36(10): 2664-2669.
[8]	XUE Shengjun, HU Minda, XU Xiaolong. Fairness-optimized resource allocation method in cloud environment [J]. Journal of Computer Applications, 2016, 36(10): 2686-2691.
[9]	XUE Shengjun, QIU Shuang, XU Xiaolong. Energy-aware fairness enhanced resource scheduling method in cloud environment [J]. Journal of Computer Applications, 2016, 36(10): 2692-2697.
[10]	DU Xiongjie, WANG Min, TANG Xuehai, ZHANG Zhang. Scheduling mechanism based on service level objective in multi-tenant cluster [J]. Journal of Computer Applications, 2015, 35(4): 944-949.
[11]	ZHU Jie, LI Wenrui, ZHAO Hong, LI Ying. Resource matching maximum set job scheduling algorithm under Hadoop [J]. Journal of Computer Applications, 2015, 35(12): 3383-3386.
[12]	WANG Yuxin, CAO Shijie, GUO He, CHEN Zheng, CHEN Xin. Communication aware multiple directed acyclic graph scheduling considering cost and fairness [J]. Journal of Computer Applications, 2015, 35(11): 3017-3020.
[13]	ZHU Qingchao, CHEN Jing, GONG Shuiqing, SHI Ting. Design of medium access control protocol tradeoff between throughput and fairness in MANET [J]. Journal of Computer Applications, 2015, 35(11): 3275-3279.
[14]	LIU Kui LIANG Xiangqian LI Xiaolin. Concurrent signature scheme constructed by identity-based ring signcryption [J]. Journal of Computer Applications, 2013, 33(05): 1386-1390.
[15]	MO Li-ping YUE Xiaobo ZHOU Kai-qing ZHANG Zhao-hai. Property preserving operation for simplifying Petri nets with inhibitor arcs [J]. Journal of Computer Applications, 2012, 32(11): 3071-3074.