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