论文部分内容阅读
随着云计算环境中数据量的激增,人们急需研究在云环境下如何对大量数据进行快速有效的分析与处理。在云环境下对大量数据进行高效地排序是其中一个重要问题。一些被广泛使用的排序算法是否能在云计算系统中高性能运行,运行时所需要消耗的云计算资源量都是令人非常关注的问题。本文主要进行Hadoop平台上快速,高效,集群负载均衡度高,资源消耗少的排序算法的研究,主要工作为:1)分析研究串行系统中效率较高的排序算法。在熟练掌握MapReduce编程框架和Hadoop体系结构的基础上,对Radixsort,Quicksort以及Sample sort在Hadoop平台上进行实现。分别对Radix sort,Quicksort和Sample sort的算法思想及在串行和并行系统中的复杂度问题进行比较分析。2)对基于 Hadoop 平台的 Radix sort,Quicksort 和 Sample sort 的执行效率、CPU资源的消耗,内存的消耗,以及处理机间的通信量进行研究和比较分析。通过大量运行在Hadoop上的实验,发现Hadoop平台上的Sample sort相较于Radix sort和Quicksort具有排序速度快,负载均衡度高,CPU消耗低等优势。这一结果为云计算环境下设计更高效、节能的算法提供了有效的依据和基础。3)针对不均匀数据集的高效排序问题,研究并提出了一种排序效率高,负载均衡度高的随机化分区Sample sort算法。Sample sort是一种在云计算环境中大量使用的排序算法。在数据可以均匀分割的情况下,sample sort算法把数据分割成为多个数据块,高速并行地对数据块进行排序。Sample sort在处理一些密度均匀的数据集时具有较高效率,而现实生活中的数据集往往分布极不均匀。为了解决密度分布不均匀数据集的排序问题,提出了一种随机化分区的样本排序算法,Randomized Partition Sample Sort(RPSS)。它引入了一个随机化分区函数,能够使得密度不均匀数据相对均匀的分布。通过大量运行在Hadoop集群上的实验,发现RPSS对分布不均的数据集排序效率比传统的样本排序有显著的提高,并且提高了 Hadoop集群的负载均衡度,降低集群故障率。