Spark Shuffle的内存调度算法分析及优化

发布时间：2018-01-06 08:35

本文关键词：Spark Shuffle的内存调度算法分析及优化　出处：《浙江大学》2016年硕士论文　论文类型：学位论文

【摘要】：随着分布式计算框架的不断发展和普及,Spark以其先进的设计理念,迅速成为开源社区的热门研究项目。对于大数据计算框架而言,Shuffle过程的设计优劣和性能高低直接影响着整个系统的性能和吞吐量。本文研究的主要内容为Spark Shuffle过程中不同Task司内存分配算法的分析与优化。在分析已有Shuffle优化算法的基础上,发现因各Task对内存需求不均衡而造成Shuffle运行效率低的瓶颈。针对公平分配内存调度算法的不足,提出了一种基于溢出历史的自适应内存调度算法,并通过典型实验证明本文算法能有效提高内存利用率和程序运行效率,提高Spark系统的整体运行性能。本文的主要贡献包括：1) 阐述了分布式计算的主流框架MapReduce,包括MapReduce的编程模型、现状和不足。通过介绍Spark的设计理念分析了Spark对MapReduce模型的改进,比较了两者的优缺点。2)研究了Spark Shuffle的概念、发展及优化过程,通过阅读分析Spark Shuffle的源码研究Shuffle内存调度的思想,指出了公平分配算法存在的不足。3) 提出了基于溢出历史的自适应内存调度算法SBSA,解决Spark Shuffle公平分配内存调度算法影响Shuffle运行效率的问题。本算法详细设计了空闲内存的计算方式、关键Task可从空闲内存借用的内存比例以及Task可用内存的最大阈值。4) 通过典型实验比较了SBSA算法与先来先服务算法、公平分配调度算法的性能差异,实验结果证明本算法可以大大提高数据分布不均匀的应用程序的执行效率。从综合表现来看,本算法能充分利用空闲内存资源,提高资源利用效率,在一定程度上缓解目前内存资源不足的问题。
[Abstract]:With the development of distributed computing framework and the popularity of Spark with its advanced design concept, it has become a hot research project in open source community. The design quality and performance of Shuffle process directly affect the performance and throughput of the whole system. The main content of this paper is Spark. Analysis and optimization of memory allocation algorithms for different Task divisions in Shuffle process. Based on the analysis of existing Shuffle optimization algorithms. It is found that the low efficiency of Shuffle is caused by the imbalance of memory demand in each Task, and the lack of fair allocation memory scheduling algorithm. An adaptive memory scheduling algorithm based on overflow history is proposed, and it is proved by typical experiments that the proposed algorithm can effectively improve memory utilization and program efficiency. The main contributions of this paper include: 1) the main framework of distributed computing, MapReduce, including the programming model of MapReduce. By introducing the design concept of Spark, the improvement of MapReduce model by Spark is analyzed. The concept, development and optimization process of Spark Shuffle are studied. Through reading and analyzing the source code of Spark Shuffle, the idea of Shuffle memory scheduling is studied. The deficiency of fair allocation algorithm. 3) the adaptive memory scheduling algorithm (SBSA) based on overflow history is proposed. To solve the problem that Spark Shuffle fair allocation memory scheduling algorithm affects the efficiency of Shuffle, this algorithm designs the calculation method of free memory in detail. The ratio of key Task memory that can be borrowed from free memory and the maximum threshold value of Task available memory. 4) A comparison between SBSA algorithm and first come first served algorithm is made through typical experiments. The performance of fair allocation scheduling algorithm is different, experimental results show that the algorithm can greatly improve the performance of applications with uneven data distribution. From the comprehensive performance, the algorithm can make full use of free memory resources. Improve the efficiency of resource utilization, to some extent alleviate the problem of insufficient memory resources.
【学位授予单位】：浙江大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP333

【相似文献】