Spark计算环境中的种间数据均衡放置算法研究

摘要

随着网络信息技术的不断发展，全球使用互联网的人数在持续的增加，互联网已经在很多行业进行实践和应用，带来了互联网数据的批量式增加，分析处理这些海量的互联网数据是一个至关重要的现实问题，同时也给分布式计算提供了新的发展机遇。Google提出的MapReduce，它的特点是可靠性高、编程简单、能自动并行处理作业，是一种用于处理大数据的分布式并行编程模型。Spark是基于内存计算的分布式并行计算框架，Spark通过引入RDD数据模型及基于内存的运算模式，使其能很好地适应大数据的数据挖掘这中场景，并且在迭代计算方面优于Hadoop，迅速成为了广大企业、学者的研究重点。此外，很多科研单位和企业开始在海量数据的处理和研究中开始应用Spark。
　　自MapReduce变成一个高效的和流行的并行数据处理编程框架，中间数据key值的偏斜成为影响系统性能的一个重要瓶颈。当MapReduce处理的数据分布不均匀时，会造成有些任务比其他任务运行较慢的情况，而整个作业的执行时间是由最慢的那个任务决定的，当处理数据存在倾斜会导致处理数据分布不平衡从而产生“短腿”作业，最终影响整体的运行效果。因此增加了整个作业的完成时间，使系统性能下降。MapReduce中数据倾斜问题可以通过统计key值频率提前制定分配方案的方法来解决。
　　为解决在Spark计算框架下shuffle过程中的buckets容器负载不平衡问题。本文提出了对中间数据块分割和组合算法SCID(segmentation and combinationalgorithm for skew intermediate data)。由于keys值的数量不可统计，除非输入数据被map任务处理，因此本文基于蓄水池的采样算法以得到中间key值的分布数据。对比原始buckets中数据加载机制，SCID根据每个map任务的键/值元组的数据大小进行排序，并有序的填充到相关buckets中。如果一个cluster超过当前的buckets容量将被分割。在填充满这个buckets后，其余clusters将进入下一次迭代，通过这种方式，数据的总大小在每个bucket大约是相等的。对于每一个map任务，每个reduce任务会从一个特定的buckets获取到中间结果，这样每个bucket中map的任务数量在reduce任务端达到负载均衡。我们在Spark1.1.0上运行SCID算法并通过广泛使用的标准Benchmark评估其性能，比如:Sort，TextSearch，Word Count。实验结果表明，我们的算法不仅可以实现更高的总体平均负载平衡性能，而且对不同程度的数据倾斜降低了作业的执行时间。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 研究背景

1．2 研究现状

1．2．1 抽样研究现状

1．2．2 负载均衡研究现状

1．3 研究内容与主要工作

1．4 论文的组织结构

第2章 相关技术介绍

2．1 Spark平台概述

2．1．1 Spark产生背景

2．1．2 Spark生态系统

2．2 Spark系统架构

2．2．1 Spark架构

2．2．2 Spark计算流程

2．2．3 RDD

2．3 MapReduce编程模型介绍

2．3．1 MapReduce架构

2．3．2 Spark—MapReduce

2．4 本章小结

第3章 基于Spark平台的中间数据负载平衡设计

3．1 系统框架概述

3．1．1 系统流程

3．1．2 数据倾斜模型

3．2 抽样算法设计

3．2．1 蓄水池抽样算法

3．2．2 cluster大小预测

3．3 分割组合算法设计

3．3．1 过程描述

3．3．2 算法分析

3．4 本章小结

第4章 实验分析与性能评估

4．1 实验环境

4．2 实验方案

4．3 实验结果与分析

4．3．1 抽样实验分析

4．3．2 Sort Benchmark测试分析

4．3．3 Text Search Benchmark测试分析

4．3．4 Word Count Benchmark测试分析

4．3．5 整体执行时间性能分析

4．4 本章小结

结论

参考文献

致谢

攻读硕士学位期间所发表的学术论文目录