面向Flink的负载均衡任务调度算法的研究与实现

计算机工程与科学 ›› 2022, Vol. 44 ›› Issue (07): 1141-1151.

面向Flink的负载均衡任务调度算法的研究与实现

李文佳1，史岚1，季航旭1，罗意彭2

（1.东北大学计算机科学与工程学院，辽宁沈阳 110169；2.辽宁工业大学软件学院，辽宁锦州 121000）

收稿日期:2021-11-10 修回日期:2022-01-17 接受日期:2022-07-25 出版日期:2022-07-25 发布日期:2022-07-25
基金资助:
科技部重点研发项目（2018YFB1004402）

Research and implementation of a Flink-oriented load balancing task scheduling algorithm

LI Wen-jia1,SHI Lan1,JI Hang-xu1,LUO Yi-peng2

（1.College of Computer Science and Engineering,Northeastern University,Shenyang 110169;
2.School of Software,Liaoning University of Technology,Jinzhou 121000,China）

Received:2021-11-10 Revised:2022-01-17 Accepted:2022-07-25 Online:2022-07-25 Published:2022-07-25

摘要/Abstract

摘要： Apache Flink是现在主流的大数据分布式计算引擎之一，其中任务调度问题是分布式计算系统中的关键问题。由于集群的异构性以及不同算子复杂度不同，大数据计算系统Flink中不可避免地会出现负载不均的情况，针对这种问题，提出了基于资源反馈的负载均衡任务调度算法RFTS。通过实时资源监控、区域划分和基于人工萤火虫优化的任务调度算法3个模块，把负载过重的机器中处于等待状态的任务分配给负载较轻的机器，来实现集群的负载均衡，提高系统集群利用率和执行效率。最后通过基于TPC-C和TPC-H数据集的实验结果表明，RFTS算法从执行时间和吞吐量2个方面有效提升了Apache Flink计算系统的性能。

关键词: Apache Flink；基于资源反馈的负载均衡任务调度算法；实时资源监控；区域划分；人工萤火虫优化算法 ,

Abstract: Apache Flink is one of the mainstream big data distributed computing engines, and task scheduling is a key issue in distributed computing systems. Due to the heterogeneity of clusters and the different complexity of operators, uneven load will inevitably appear in the big data computing system Flink. To solve this problem, a load balancing task scheduling algorithm based on resource feedback, named RFTS, is proposed. Through the three modules (real-time resource monitoring, area division, and task scheduling algorithm based on glowworm swarm optimization), the tasks in the waiting queue in the over-loaded machine are allocated to the lighter-loaded machines, so as to reduce the load unevenness of the entire cluster and improve the cluster utilization and execution efficiency of the system. Finally, through the experimental verification based on the TPC-C and TPC-H datasets, the results show that the load balancing task scheduling algorithm based on resource feedback (RFTS) can effectively improve the performance of the Apache Flink computing system in terms of execution time and throughput.

Key words: Apache Flink, load balancing task scheduling algorithm based on resource feedback, real-time resource monitoring, area division, glowworm swarm optimization algorithm

李文佳, 史岚, 季航旭, 罗意彭. 面向Flink的负载均衡任务调度算法的研究与实现[J]. 计算机工程与科学, 2022, 44(07): 1141-1151.

LI Wen-jia, SHI Lan, JI Hang-xu, LUO Yi-peng. Research and implementation of a Flink-oriented load balancing task scheduling algorithm[J]. Computer Engineering & Science, 2022, 44(07): 1141-1151.

参考文献［19］

［1］	Dean J,Ghemawat S.MapReduce:Simple data processing on large clusters［J］.Communications of the ACM,2008,51(1):107-113.
［2］	Bhandarkar M. MapReduce programming with Apache Hadoop［C］∥Proc of 2010 IEEE International Symposium on Parallel & Distributed Processing,2010:1.
［3］	Yao Y,Wang Y F,Liu Z J.An algorithm used to improve task parallelization for directed acyclic graphs［C］∥Proc of the 26th International Conference on Data Engineering,2010:238-240.
［4］	Singh R,Kaur P J.Analyzing performance of Apache Tez and MapReduce with Hadoop multinode cluster on Amazon cloud［J］.Journal of Big Data,2016,3(1):1-10.
［5］	Wang D W,Zhou F F,Li J M.Cloud-based parallel power flow calculation using resilient distributed datasets and directed acyclic graph［J］.Journal of Modern Power Systems and Clean Energy,2019,7(1):65-77.
［6］	Zaharia M,Chowdhury M,Franklin M J,et al.Spark:Cluster computing with working sets［C］∥Proc of the 2nd USENIX Conference on Hot Topics in Cloud Computing,2010:1-7.
［7］	Carbone P, Katsifodimos A,Ewen S,et al.Apache Flink:Stream and batch processing in a single engine［J］.Bulletin of the IEEE Computer Society Technical Committee on Data Engineering,2015,36(4):28-38.
［8］	TPC. TPC-H benchmark standard specification ［EB/OL］.［2021-09-18］.http://www.tpc.org/tpch/.
［9］	Moerkotte G,Scheufele W.Constructing optimal bushy processing trees for join queries is NP-hard:1996 Technical reports［R］.Mannheim:University of Mannheim,1996.
［10］	Devipriya S,Ramesh C.Improved Max-Min heuristic model for task scheduling in cloud［C］∥Proc of 2013 International Conference on Green Computing,Communication and Conservation of Energy,2013:883-888.
［11］	Reda N M.An improved sufferage meta-task scheduling algorithm in grid computing systems［J］.International Journal of Advanced Research,2015,3(10):123-129.
［12］	Teixeira M A,Guardieiro P R.Uplink scheduling algorithm with dynamic polling management in IEEE 802.16 broadband wirelss networks［C］∥Proc of the 2010 ACM Symposium on Applied Computing,2010:601-602.
［13］	Doulamis N D,Doulamis A D,Varvarigos E A,et al.Fair scheduling alogrithms in grids［J］. IEEE Transactions on Parallel and Distributed Systems,2007,18(1):1630-1648.
［14］	Singh H,Bhasin A,Kaveri P R.QRAS:Efficient resource allocation for task scheduling in cloud computing［J］.SN Applied Sciences,2021,3:Article number:474.
［15］	Todd D,Sen P.Distributed task scheduling and allocation using genetic algorithms［J］.Computers & Industrial Engineering,1999,37(1):47-50.
［16］	Chen Q,Hou M.Research on gird task scheduling based on ant colony algorithm［J］.Advanced Materials Research,2010,129-131:1438-1443.
［17］	Sivanandam S N, Visalakshi P.A new approach for task scheduling using elite particle swarm optimization［J］.Artificial Intelligent Systems and Machine Learning,2009,1(2):45-51.
［18］	Shu W N,Zheng S J.A parallel genetic simulated annealing hybrid algorithm for task scheduling［J］.Wuhan University Journal of Natural Sciences,2006,11(5):1378-1382.
［19］	Tsai J T,Fang J C,Chou J H.Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm［J］.Computers & Operations Research,2013,40(12):3045-3055.