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

摘要

随着分布式计算框架的不断发展和普及，Spark以其先进的设计理念，迅速成为开源社区的热门研究项目。对于大数据计算框架而言，Shuffle过程的设计优劣和性能高低直接影响着整个系统的性能和吞吐量。本文研究的主要内容为SparkShuffle过程中不同Task间内存分配算法的分析与优化。在分析已有Shuffle优化算法的基础上，发现因各Task对内存需求不均衡而造成Shuffle运行效率低的瓶颈。针对公平分配内存调度算法的不足，提出了一种基于溢出历史的自适应内存调度算法，并通过典型实验证明本文算法能有效提高内存利用率和程序运行效率，提高Spark系统的整体运行性能。本文的主要贡献包括:
　　1)阐述了分布式计算的主流框架MapReduce，包括MapReduce的编程模型、现状和不足。通过介绍Spark的设计理念分析了Spark对MapReduce模型的改进，比较了两者的优缺点。
　　2)研究了Spark Shuffle的概念、发展及优化过程，通过阅读分析SparkShuffle的源码研究Shuffle内存调度的思想，指出了公平分配算法存在的不足。
　　3)提出了基于溢出历史的自适应内存调度算法SBSA，解决Spark Shuffle公平分配内存调度算法影响Shuffle运行效率的问题。本算法详细设计了空闲内存的计算方式、关键Task可从空闲内存借用的内存比例以及Task可用内存的最大阈值。
　　4)通过典型实验比较了SBSA算法与先来先服务算法、公平分配调度算法的性能差异，实验结果证明本算法可以大大提高数据分布不均匀的应用程序的执行效率。从综合表现来看，本算法能充分利用空闲内存资源，提高资源利用效率，在一定程度上缓解目前内存资源不足的问题。

目录

声明

摘要

图目录

表目录

第1章 绪论

1．1 课题背景

1．1．1 并行计算模型

1．1．2 Spark产生的背景

1．1．3 Spark Shuffle所面临的问题与挑战

1．2 本文的主要贡献及创新点

1．3 论文组织结构

1．4 本章小结

第2章 相关技术及研究现状

2．1 MapReduce模型及研究现状

2．1．1 MapReduce编程模型

2．1．2 MapReduce模型的研究现状

2．2 Hadoop MapReduce与Spark

2．3 Spark的工作原理

2．3．1 Spark系统运行时的部署图

2．3．2 Job的生成与运行

2．3．3 Resilient Distributed Datasets的数据依赖

2．4 本章小结

第3章 Spark Shuffle优化分析及其内存调度算法

3．1 Shuffle基本概念

3．2 MapReduce Shume的优化

3．3 Spark Shuffle的优化

3．3．1 Shuffle Write

3．3．2 Shuffle Fetch

3．4 Spark Shume的内存调度算法

3．5 本章小结

第4章 Spark Shuffle内存调度算法的改进

4．1 Spark Shume内存调度概述

4．2 先来先服务调度算法FCFS

4．2．1 使用FCFS调度Application1的Shume Task

4．2．2 使用FCFS调度Application2的Shume Task

4．2．3 FCFS存在的不足

4．3 公平分配调度算法FA

4．3．1 使用FA调度Application1的Shume Task

4．3．2 使用FA调度Application2的Shume Task

4．3．3 FCFS与FA的比较

4．3．4 FA存在的不足

4．4 基于溢出历史的自适应调度算法SBSA

4．4．1 SBSA产生背景

4．4．2 SBSA的详细设计

4．4．3 SBSA的思路和流程

4．4．4 SBSA的算法实现

4．4．5 使用SBSA调度Application

4．5 本章小结

第5章 Spark Shuffle内存调度算法性能测试及评价

5．1 实验方法和目的

5．2 实验环境

5．3 实验环境安装

5．3．1 安装JDK、SSH和Scala

5．3．2 Hadoop的安装配置

5．3．3 Spark的安装配置

5．4 实验任务

5．4．1 评估方法

5．4．2 GroupByKey操作原理

5．5 实验结果及分析

5．5．1 均匀数据的实验结果分析

5．5．2 不均匀数据的实验结果分析

5．6 实验结论

5．7 本章小结

第6章 总结与展望

6．1 全文总结

6．2 工作展望

参考文献

攻读硕士学位期间主要的研究成果

致谢