异构Spark集群数据倾斜修正调度策略

计算机工程与科学 ›› 2022, Vol. 44 ›› Issue (04): 620-630.

异构Spark集群数据倾斜修正调度策略

卞琛1，修位蓉2，于炯3

（1广东金融学院互联网金融与信息工程学院，广东广州 510521;
2.广州商学院信息技术与工程学院，广东广州 511363;3新疆大学信息科学与工程学院，新疆乌鲁木齐 830046）

收稿日期:2021-11-09 修回日期:2021-12-15 接受日期:2022-04-25 出版日期:2022-04-25 发布日期:2022-04-20
基金资助:
国家自然科学基金（61862060，61902081）；广州市哲学社会科学规划项目（2021GZGJ145）

A data skew correction scheduling strategy of heterogeneous Spark cluster

BIAN Chen1，XIU Wei-rong2，YU Jiong3

(1.College of Internet Finance and Information Engineering,Guangdong University of Finance,Guangzhou 510521;
2.School of Information Technology and Engineering,Guangzhou College of Commerce,Guangzhou 511363;
3.College of Information Science and Engineering,Xinjiang University,Urumqi 830046,China)Abstract:Due to the barrel effect of heterogeneous Spark clusters, unreasonable parallelism leads to poor adaptation of task allocation to the power of workers, which affects cluster computational efficiency and resource utilization. Aiming at this issue, the node resource models are firstly established, the coupling relationships among data distribution, parallelism parameters and task allocation are analyzed, and the optimization objective of the algorithm is proposed. The data skew correction scheduling strategy DSCS for heterogeneous Spark cluster is designed, which includes the parallelism prediction algorithm, data skew correction algorithm and heterogeneous task allocation algorithm. The prediction algorithm sets the parallelism degree in advance, the data skew correction algorithm performs data re-partitioning and parallelism correction according to the statistical information of the first stage, and the heterogeneous task allocation algorithm reasonably allocates the tasks to the workers according to their computing capabilities in the heterogeneous cluster, so as to improve the adaptability of data volume and workers power and optimize the overall performance of Spark cluster. The experimental results show that the algorithm achieves performance improvement under different job types and dataset conditions, and can effectively reduce the probability of spill to the external storage of workers.

Received:2021-11-09 Revised:2021-12-15 Accepted:2022-04-25 Online:2022-04-25 Published:2022-04-20

摘要/Abstract

摘要： 异构Spark集群存在木桶效应，不合理的并行度导致任务分配与工作节点计算能力的适配性较差，进而影响集群计算效率和资源利用率。针对这一问题，首先建立模型，分析数据分布、并行度参数和节点任务分配的耦合关系，提出算法的优化目标，设计异构Spark集群的数据倾斜修正调度策略DSCS，包括并行度预估算法、数据倾斜修正算法和异构节点任务分配算法。预估算法对并行度进行先期设定，数据倾斜修正算法根据首个计算阶段的统计信息进行数据重新划分和并行度修正，由异构节点任务分配算法对集群不同计算能力的工作节点进行合理的任务分配，从而提高数据计算量与节点计算能力的适配性，优化Spark集群的整体性能。实验结果表明：在不同作业类型、不同数据集条件下，算法均取得了一定的性能提升，并能有效减少工作节点外存溢写的概率。

关键词: Spark, parallel scheduling, data partitioning, heterogeneous cluster, data skew

Abstract: Spark；并行调度；数据分配；异构集群；数据倾斜

卞琛, 修位蓉, 于炯. 异构Spark集群数据倾斜修正调度策略[J]. 计算机工程与科学, 2022, 44(04): 620-630.

BIAN Chen, XIU Wei-rong, YU Jiong. A data skew correction scheduling strategy of heterogeneous Spark cluster[J]. Computer Engineering & Science, 2022, 44(04): 620-630.

参考文献［2］

［1］	Zaharia M.An architecture for fast and general data proces- sing on large clusters［M］.Williston:Morgan & Claypool,2016.
［2］	Luo Le,Liu Yi,Qian De-pei.Survey on in-memory computing technology［J］.Journal of Software,2016,27(8):2147-2167.(in Chinese)
［3］	Zaharia M,Chowdhury M,Das T,et al.Resilient distributed datasets:A fault-tolerant abstraction for in-memory cluster computing［C］∥Proc of the 9th USENIX Conference on Networked Systems Design and Implementation,2012:2.1-2.14.
［4］	Meituan Comment Techical Group.Spark performance tuning guide ［EB/OL］.［2017-04-28］.http://tech.meituan.com/Spark-tuning-basic.html.
［5］	Apache Spark［EB/OL］.［2017-03-15］.http://Spark.apache.org.
［6］	Dean J,Ghemawat S.MapReduce:Simplified data processing on large clusters［J］.Communications of the ACM,2008,51(1):107-113.
［7］	Apache Impala.Impala overview ［EB/OL］. ［2015-09-21］.http://www.cloudera.com/content/www/en-us/products/apache-hadoop/impala.html.
［8］	Ananthanarayanan G, Ghodsi A,Wang A,et al.PACMan:Coordinated memory caching for parallel jobs［C］∥Proc of the 9th USENIX Conference on Networked Systems Design and Implementation,2012:20.1-20.14.
［9］	Babu S.Towards automatic optimization of MapReduce programs ［C］∥Proc of the 1st ACM Symposium on Cloud Computing,2010:137-142.
［10］	Sarma A D,Afrati F N,Salihoglu S,et al.Upper and lower bounds on the cost of a map-reduce computation ［C］∥Proc of the 39th International Conference on Very Large Data Bases,2013:277-288.
［11］	Li J G, Lin X L, Cui X L, et al. Improving the shuffle of Hadoop MapReduce［C］∥Proc of the 13th IEEE International Conference on Cloud Computing Technology and Science,2013:266-273.
［12］	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:29-42.
［13］	Wang K,Khan M.Performance prediction for Apache Spark platform［C］∥Proc of the 2015 IEEE 17th International Conference on High Performance Computing and Communications,2015 IEEE 7th International Symposium on Cyberspace Satety and Security, and 2015 IEEE 12th International Conference on Embedded Software and Systems,2015:166-173.
［14］	Petridis P,Gounaris A,Torres J.Spark parameter tuning via trial-and-error［C］∥Proc of INNS Conference on Big Data,2016:226-237.
［15］	Kwon Y,Balazinska M,Howe B,et al.Skew-resistant parallel processing of feature-extracting scientific user-defined functions［C］∥Proc of the 1st ACM Symposium on Cloud Computing,2010:75-86.
［16］	Kwon Y,Balazinska M,Howe B,et al.SkewTune:Mitigat- ing skew in MapReduce applications ［C］∥Proc of the 2012 ACM SIGMOD International Conference on Management of Data,2012:25-36.
［17］	Ramakrishnan S R,Swart G,Urmanov A, et al.Balancing Reducer skew in MapReduce workloads using progressive sampling ［C］∥Proc of the 3rd ACM Symposium on Cloud Computing,2012:1-14.
［18］	Gufler B,Augsten N,Reiser A,et al.Handing data skew in MapReduce ［C］∥Proc of the 1st International Conference on Cloud Computing and Services Science,2011:574-583.
［19］	Gufler B, Augsten N, Reiser A, et al.Load balancing in MapReduce based on scalable cardinality estimates ［C］∥Proc of the 28th IEEE International Conference on Data Engineering,2012:522-533.
［20］	Kolb L,Thor A,Rahm E.Load balancing for MapReduce-based entity resolution ［C］∥Proc of the 28th IEEE International Conference on Big Data Engineering,2012:618-629.
［21］	Kolb L,Thor A,Rahm E,et al.Block-based load balancing for entity resolution with MapReduce ［C］∥Proc of the 20th ACM International Conference on Information and Knowledge Management,2011:2397-2400.
［22］	Racha S C.Load balancing Map-Reduce communications for efficient executions of applications in a cloud ［D］.Bangalore,India:Indian Institute of Science,2012:12-16.
［23］	Ibrahim S,Jin H,Lu L,et al.Handling partitioning skew in MapReduce using LEEN ［J］.Peer-to-Peer Networking and Applications,2013,6(4):409-424.
［24］	Xu L N, Butt A R,Lim S-H,et al.A heterogeneity-aware task scheduler for Spark ［C］∥Proc of the 2018 IEEE International Conference on Cluster Computing,2018:1-12.
［25］	Pan F F, Xiong J,Shen Y J,et al.H-Scheduler:Storage-aware task scheduling for heterogeneous-storage Spark clusters ［C］∥Proc of the 2018 IEEE 24th International Confe- rence on Parallel and Distributed Systems,2018:9-17.
［26］	Klimovic A,Litz H,Kozyrakis C.Selecta:Heterogeneous cloud storage configuration for data analytics ［C］∥Proc of the 2018 USENIX Conference on Annual Technical Confe- rence,2018:759-773.
［27］	Wang L, Zhan J,Luo C,et al.Bigdatabench:A big data benchmark suite from internet services［C］∥Proc of 2014 IEEE 20th International Symposium on High Performance Computer Architecture,2014:488-499.
	附中文参考文献：
［2］	罗乐,刘轶,钱德沛.内存计算技术研究综述［J］.软件学报,2016,27(8):2147-2167.