余晟隽,宫学庆,祝君,钱卫宁

(华东师范大学数据科学与工程研究院,上海200062)

基于Map/Reduce的分布“数据排序算法分析

余晟隽,宫学庆,祝君,钱卫宁

(华东师范大学数据科学与工程研究院,上海200062)

为了解决大规模数据的存储与计算,近年来分布式系统得到了大量的应用.如何在分布式系统中对大规模数据集进行排序是影响许多应用性能的基础问题,其中不仅涉及每个节点上排序算法的选择,更重要的是设计协调各节点的分布式算法.本文总结了分布式系统中常用的分布式排序算法,对每种算法的执行流程、代价模型和适用场景进行了分析,并通过实验对分析结果进行了验证.本文的工作可以帮助开发人员选择和优化分布式环境下大规模数据排序的算法.

分布式系统;排序算法;代价模型

0 引言

排序是计算机科学中的基础问题,传统的排序算法研究多关注于集中式环境下算法的性能、资源消耗和稳定性[1].近年来,在很多领域中数据的规模快速增长,已经很难在集中式环境中进行存储和处理,Hadoop等分布式系统[2]逐渐成为大规模数据处理的主流平台.在分布式环境中对大规模数据进行排序处理时,不仅需要考虑单节点上排序算法的选择,还需要考虑分布式系统的架构、数据分布策略和分布式计算模型等因素的影响.在分布式系统中如何提高大规模数据排序处理的性能是一个值得研究的问题.

本文关注于分布式系统中大……