A Novel Spark Job Scheduling Algorithm Oriented Deadline-Cost Balance

doi:10.19678/j.issn.1000-3428.0069968

Abstract

Abstract:

The significance of big data computation frameworks such as Apache Spark for large-scale data analysis is becoming increasingly prominent. However, handling data-intensive jobs by relying solely on local computing resources is difficult. Therefore, a feasible solution is to rent cloud resources from public cloud service providers and fully deploy Spark clusters in the cloud. However, this operation incurs high deployment costs. To reduce costs, an increasing number of users are choosing to use local and cloud resources together to build hybrid cloud computing clusters. However, in Spark clusters deployed in hybrid clouds, scheduling jobs while simultaneously meeting multiple service-level agreement requirements (such as minimizing costs and ensuring job deadlines at the same time) is challenging. Existing research mainly focuses on ways to reduce cluster usage costs or improve job deadline satisfaction rates, without considering the balance between these two goals. This paper proposes a Deadline-Cost Aware Ant Colony Optimization (DC-ACO) algorithm to solve the job scheduling problem in hybrid clouds. DC-ACO can optimize the pricing of different Virtual Machine (VM) instances in a hybrid cloud deployment cluster while maximizing the percentage of job deadlines met. In extensive simulation experiments, DC-ACO is compared with baseline methods. The results demonstrate that the proposed algorithm exhibits robust scalability, achieving an approximately 20% increase in the job deadline fulfillment percentage, coupled with a notable 10% reduction in VM usage costs for hybrid clusters.

Key words: Spark cluster, job scheduling, hybrid cloud, Ant Colony Optimization (ACO) algorithm, job deadline, Virtual Machine (VM)

摘要：

大数据计算框架如Apache Spark在大数据分析任务中的重要性日益凸显, 但是仅依靠本地计算资源往往难以支撑数据密集型作业任务的处理。因此, 一种可行的方案是租用公共云服务商的云资源, 并将Spark集群完全部署在云端。然而, 这样会导致计算成本过高。为了降低成本, 越来越多的用户选择使用本地资源和云资源协同的方式构建混合云计算集群。但是在混合云部署的Spark集群中, 在满足多个服务水平协议需求(例如最小化成本和保证作业截止期限)的同时完成作业调度是一项具有挑战性的任务。现有的研究主要关注如何降低集群使用成本或者提高作业截止日期的满足率, 而没有考虑这两个目标之间的平衡。针对这一问题, 提出了一种新的期限-成本感知蚁群优化(DC-ACO)作业调度算法, 该算法能够在利用混合云部署集群中不同虚拟机(VM)实例定价下优化集群VM使用成本的同时, 最大限度地保证作业截止日期的满足百分比, 并通过仿真实验对比提出的DC-ACO作业调度算法与基线算法的性能。实验结果表明, DC-ACO算法具有良好的可扩展性, 并且能够将作业截止日期的满足百分比提升约20%, 同时将混合集群的VM使用成本降低约10%。

关键词: Spark集群, 作业调度, 混合云, 蚁群优化算法, 作业截止期限, 虚拟机

HE Yulin, MO Peiheng, HUANG Zhexue, Philippe Fournier-Viger. A Novel Spark Job Scheduling Algorithm Oriented Deadline-Cost Balance[J]. Computer Engineering, 2026, 52(3): 318-331.

何玉林, 莫沛恒, 黄哲学, Philippe Fournier-Viger. 一种新的截止期限与成本平衡为导向的Spark作业调度算法[J]. 计算机工程, 2026, 52(3): 318-331.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0069968

https://www.ecice06.com/EN/Y2026/V52/I3/318

Figures/Tables 18

Fig.1 Hybrid cloud system model

Fig.2 Deadline fulfillment percentage for high load-small job set

Fig.3 Deadline fulfillment percentage for high load-large job set

Fig.4 Deadline fulfillment percentage for low load-small job set

Fig.5 Deadline fulfillment percentage for low load-large job set

Fig.6 Usage cost for high load-small job set

Fig.7 Usage cost for high load-large job set

Fig.8 Usage cost for low load small-job set

Fig.9 Usage cost for low load-large job set

Fig.10 Average job duration for high load-small job set

Fig.11 Average duration for high load-large job set

Fig.12 Average duration for low load-small job set

Fig.13 Average duration for low load-large job set

References 34

1	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, USA: ACM Press, 2013: 1-16.
2	ZAHARIA M , XIN R S , WENDELL P , et al. Apache spark. Communications of the ACM, 2016, 59 (11): 56- 65. doi: 10.1145/2934664
3	SHVACHKO K, KUANG H R, RADIA S, et al. The hadoop distributed file system[C]//Proceedings of the 26th IEEE Symposium on Mass Storage Systems and Technologies. Incline Village, USA: IEEE Press, 2010: 1-10.
4	GEORGE L . HBase: the definitive guide: random access to your planet size data. Newton, USA: O'Reilly Media, 2011.
5	LAKSHMAN A , MALIK P . Cassandra: a decentralized structured storage system. ACM SIGOPS Operating Systems Review, 2010, 44 (2): 35- 40. doi: 10.1145/1773912.1773922
6	ZAHARIA M, CHOWDHURYET M, TATHAGATA D, et al. Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing[C]//Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. Washington D. C., USA: IEEE Press, 2012: 15-28.
7	Apache Spark. Job scheduling[EB/OL]. [2024-05-05]. https://spark.apache.org/docs/latest/job-scheduling.html.
8	HUSSAIN M , LUO M X , HUSSAIN A , et al. Deadline-constrained cost-aware workflow scheduling in hybrid cloud. Simulation Modelling Practice and Theory, 2023, 129, 102819. doi: 10.1016/j.simpat.2023.102819
9	RAMESH D , RIZVI N , SRINIVASA RAO P C , et al. Improved chemical reaction optimization with fitness-based quasi-reflection method for scheduling in hybrid cloud-fog environment. IEEE Transactions on Network and Service Management, 2024, 21 (1): 653- 669. doi: 10.1109/TNSM.2023.3299358
10	DORIGO M , MANIEZZO V , COLORNI A . Ant system: optimization by a colony of cooperating agents. IEEE Transactions on System, Man, and Cybernetics, Part B: Cybernetics, 1996, 26 (1): 29- 41. doi: 10.1109/3477.484436
11	SHETTI M M, LI B Z, DU D H C. E-VM: an elastic virtual machine scheduling algorithm to minimize the total cost of ownership in a hybrid cloud[C]//Proceedings of the IEEE International Conference on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking. Washington D. C., USA: IEEE Press, 2021: 202-211.
12	严磊, 张功萱, 王添, 等. 混合云下具有交付期约束的众包任务调度算法. 计算机科学, 2022, 49 (5): 244- 249. doi: 10.11896/jsjkx.210300120
	YAN L , ZHANG G X , WANG T , et al. Crowdsourcing task scheduling algorithm with delivery time constraints in hybrid cloud. Computer Science, 2022, 49 (5): 244- 249. doi: 10.11896/jsjkx.210300120
13	WANG B , WANG C H , HUANG W W , et al. Security-aware task scheduling with deadline constraints on heterogeneous hybrid clouds. Journal of Parallel and Distributed Computing, 2021, 153, 15- 28. doi: 10.1016/j.jpdc.2021.03.003
14	YEH T , CHEN Y L . Improving the hybrid cloud performance through disk activity-aware data access. Simulation Modelling Practice and Theory, 2021, 109, 102296. doi: 10.1016/j.simpat.2021.102296
15	SUN Z X , HUANG H J , LI Z K , et al. Efficient, economical and energy-saving multi-workflow scheduling in hybrid cloud. Expert Systems with Applications, 2023, 228, 120401. doi: 10.1016/j.eswa.2023.120401
16	PAL S , JHANJHI N Z , ABDULBAQI A S , et al. An intelligent task scheduling model for hybrid Internet of things and cloud environment for big data applications. Sustainability, 2023, 15 (6): 5104. doi: 10.3390/su15065104
17	STAVRINIDES G L , KARATZA H D . Dynamic scheduling of bags-of-tasks with sensitive input data and end-to-end deadlines in a hybrid cloud. Multimedia Tools and Applications, 2021, 80 (11): 16781- 16803. doi: 10.1007/s11042-020-08974-8
18	FU Z M , TANG Z , YANG L , et al. An optimal locality-aware task scheduling algorithm based on bipartite graph modelling for spark applications. IEEE Transactions on Parallel and Distributed Systems, 2020, 31 (10): 2406- 2420. doi: 10.1109/TPDS.2020.2992073
19	RAJPUT K Y, LI X P, LAKHAN A, et al. Task scheduling in multi-cloud environments for spark workflow under performance uncertainty[C]//Proceedings of the 27th International Conference on Computer Supported Cooperative Work in Design. Washington D. C., USA: IEEE Press, 2024: 2752-2757.
20	LI C L , CAI Q Q , LUO Y L . Dynamic data replacement and adaptive scheduling policies in Spark. Cluster Computing, 2022, 25 (2): 1421- 1439. doi: 10.1007/s10586-022-03541-2
21	ISLAM M T , WU H M , KARUNASEKERA S , et al. SLA-based scheduling of spark jobs in hybrid cloud computing environments. IEEE Transactions on Computers, 2021, 71 (5): 1117- 1132.
22	MOHAMMAD HASANI ZADE B , MANSOURI N . Improved red fox optimizer with fuzzy theory and game theory for task scheduling in cloud environment. Journal of Computational Science, 2022, 63, 101805. doi: 10.1016/j.jocs.2022.101805
23	DUBEY K , SHARMA S C . A novel multi-objective CR-PSO task scheduling algorithm with deadline constraint in cloud computing. Sustainable Computing: Informatics and Systems, 2021, 32, 100605. doi: 10.1016/j.suscom.2021.100605
24	ABUALIGAH L , ALKHRABSHEH M . Amended hybrid multi-verse optimizer with genetic algorithm for solving task scheduling problem in cloud computing. The Journal of Supercomputing, 2022, 78 (1): 740- 765. doi: 10.1007/s11227-021-03915-0
25	QIN S , PI D C , SHAO Z S , et al. A cluster-based cooperative co-evolutionary algorithm for multiobjective workflow scheduling in a cloud environment. IEEE Transactions on Automation Science and Engineering, 2023, 20 (3): 1648- 1662. doi: 10.1109/TASE.2022.3183681
26	TAO S Y , XIA Y Q , YE L J , et al. DB-ACO: a deadline-budget constrained ant colony optimization for workflow scheduling in clouds. IEEE Transactions on Automation Science and Engineering, 2023, 21 (2): 1564- 1579. doi: 10.1109/TASE.2023.3247973
27	WANG Z J , ZHAN Z H , YU W J , et al. Dynamic group learning distributed particle swarm optimization for large-scale optimization and its application in cloud workflow scheduling. IEEE Transactions on Cybernetics, 2020, 50 (6): 2715- 2729. doi: 10.1109/TCYB.2019.2933499
28	MAIA A M, GHAMRI D Y, VIEIRA D et al. Optimized placement of scalable IoT services in edge computing[C]//Proceedings of the 2019 IFIP/IEEE Symposium on Integrated Network and Service Management. Washington D. C., USA: IEEE Press, 2019: 189-197.
29	BURER S , LETCHFORD A N . Non-convex mixed-integer nonlinear programming: a survey. Surveys in Operations Research and Management Science, 2012, 17 (2): 97- 106. doi: 10.1016/j.sorms.2012.08.001
30	WANG X M , WANG J , WANG X , et al. Energy and delay tradeoff for application offloading in mobile cloud computing. IEEE Systems Journal, 2017, 11 (2): 858- 867. doi: 10.1109/JSYST.2015.2466617
31	LIU Y, MA J W, ZANG S F, et al. Dynamic path planning of mobile robot based on improved ant colony optimization algorithm[C]//Proceedings of the 8th International Conference on Networks, Communication and Computing. New York, USA: ACM Press, 2019: 248-252.
32	LU L C , YUE T W . Mission-oriented ant-team ACO for Min-max MTSP. Applied Soft Computing, 2019, 76, 436- 444. doi: 10.1016/j.asoc.2018.11.048
33	GAO W L, ZHAN J F, WANG L, et al. BigDataBench: a scalable and unified big data and AI benchmark suite[EB/OL]. [2024-05-05]. https://arxiv.org/abs/1802.08254.
34	Alibaba. Clusterdata/cluster-trace-gpu-v2023[EB/OL]. [2024-05-05]. https://github.com/alibaba/clusterdata/tree/master/cluster-trace-gpu-v2023.

[1]	ZHANG Wenshuai, LI Huimin, LI Jing, PAN Bicai. A Parallel Parameter Optimization Method Integrated with Job Scheduling System for Supercomputing Applications [J]. Computer Engineering, 2025, 51(7): 59-67.
[2]	JIANG Zetao, SHI Chen. Cross-Domain Identity Authentication Scheme Based on Heterogeneous Systems in Hybrid Cloud Environment [J]. Computer Engineering, 2019, 45(10): 13-18.
[3]	XUE Tao,YAN Minglei. Research on Hadoop Job Scheduling Based on CHC Genetic Algorithm [J]. Computer Engineering, 2016, 42(3): 61-68.
[4]	TI Ming, CHEN Dun-Jie, JIANG Pan. Map Reduce Scheduling Algorithm Based on Simulated Annealing [J]. Computer Engineering, 2012, 38(19): 45-48.
[5]	MU Xiao-fang; ZHAO Yue-ai; ZHANG Zhao-xia. Genetic Algorithm for Job Scheduling in Grid Based on Auction Mechanism [J]. Computer Engineering, 2009, 35(9): 187-189.
[6]	SHU Wan-neng. Job Scheduling in Campus Grid Based on Quantum Genetic Algorithm [J]. Computer Engineering, 2008, 34(7): 191-193.
[7]	LI Pei-feng; ZHU Qiao-ming; ZHI Li-yan. Design of Grid Resource Management System Oriented to Information Service [J]. Computer Engineering, 2008, 34(3): 49-51,5.
[8]	KANG Jian; LI Wei; LI Yun-chun. Job Scheduling Based on Resource Availability in Clusters [J]. Computer Engineering, 2008, 34(18): 53-55.
[9]	JIANG Wei; CHEN Kai; ZHONG Xiao-qiang; WANG Cheng-en; ZHU Chang-an. Resource Constrained Stochastic Job Scheduling Based on Dynamic Programming [J]. Computer Engineering, 2008, 34(16): 19-21.
[10]	LUO Hong-bing; ZHANG Yu; ZHANG Xiao-xia. Design and Application of Scalable Parallel Job Scheduling Simulator ParaSim [J]. Computer Engineering, 2007, 33(18): 45-47.
[11]	ZHANG Xiaojie, MENG Qingchun, QU Weifen. A Job Scheduling for Service Grid Using Ant Colony Algorithm [J]. Computer Engineering, 2006, 32(8): 216-218.
[12]	ZHANG Wenju, CHEN Shudong, LIU Liao, MA Fanyuan, SHEN Jianhua. Design and Implementation of Drug Discovery Grid [J]. Computer Engineering, 2006, 32(11): 259-261.

Please choose a citation manager

Content to export