海量数据并行排序算法研究：基于 Spark 集群的实现与评测

本文以海量数据并行排序问题为研究内容，在 Spark 集群上设计并实现了多种并行排序算法，并进行了评测。本文首先详细分析并设计了在 Spark 集群上进行海量数据排序的算法架构；之后在此架构的基础上设计并实现了 6 种并行排序算法，并进行了实验对比分析。本文的主要贡献如下：(1) 针对并行排序问题，本文分析并设计了在 Spark 集群上进行排序任务的架构；换言之，只要在 Spark 集群上设计与实现任意一种基于分区的并行排序算法，都可以应用此架构进行二次设计。本文所实现的桶并行排序、计数并行排序、鸽巢并行排序、基数并行排序和样本并行排序都是在此架构上进行二次设计的。(2) 经过多种并行排序算法的设计与评测工作，在 Spark 集群或者其它的分布式计算框架中，待排序数据集中存在大量的重复关键字是影响一个并行排序时间开销的主要因素；并行排序算法主要解决的一点就是如何处理这些大量重复关键字的数据的问题，使得算法不会引发 OOM 异常，造成排序任务失败；解决办法的核心是分离器的设计，分离器的优劣直接影响着并行排序任务的时间开销，本文总结了一个高效的分离器所必须满足的 6 条标准，这些标准是在设计并行排序算法时都应该要考虑的方面。(3) 在实现的 6 种并行排序算法中，使用了百分位分离器划分策略的样本排序达到了最少的排序时间开销，但忽略了同一分区中热 key 与非热 key 同在的情况；使用了次优分离器划分策略的样本排序算法满足了分离器设计的全部 6 条标准，在处理含有大量重复关键字的待排序数据集时达到了一个较好的平衡，既具备相对较少的排序时间开销，又具备较均衡的负载分布，同时也保证了热 key 与非热 key 被划分到不同桶中。(模仿上文写基于MPI的排序并行化算法的结论)\内容：综上所述，本文在Spark集群上设计并实现了多种并行排序算法，并进行了评测。通过分析并设计了在Spark集群上进行海量数据排序的算法架构，实现了桶并行排序、计数并行排序、鸽巢并行排序、基数并行排序和样本并行排序等算法。在评测过程中发现，待排序数据集中存在大量重复关键字是影响并行排序时间开销的主要因素。为了解决这个问题，分离器的设计起到了关键作用，本文总结了高效的分离器应满足的6条标准。在实现的6种并行排序算法中，使用百分位分离器划分策略的样本排序达到了最少的排序时间开销，而使用次优分离器划分策略的样本排序算法在处理含有大量重复关键字的数据集时达到了较好的平衡，既具备较少的排序时间开销，又具备较均衡的负载分布。同时，该算法能够保证热 key 和非热 key 被划分到不同的桶中。