MapReduce排序算法如何工作？

用于演示MapReduce功能的主要示例之一是Terasort基准测试.我无法理解MapReduce环境中使用的排序算法的基础知识.

对我来说,排序只涉及确定元素与所有其他元素的相对位置.因此排序涉及将"一切"与"一切"进行比较.你的平均排序算法(快速,泡沫......)只是以聪明的方式做到这一点.

在我看来,将数据集分成多个部分意味着您可以对单个部分进行排序,然后您仍然必须将这些部分集成到"完整"的完全排序数据集中.鉴于分布在数千个系统上的TB级数据集,我认为这是一项艰巨的任务.

那怎么回事呢？这个MapReduce排序算法如何工作？

谢谢你帮我理解.

以下是Hadoop为Terasort实施的一些细节:

TeraSort是标准的map/reduce排序,但自定义分区器除外,该分区器使用N-1个采样键的排序列表,这些键定义了每个reduce的键范围.特别是,所有键,例如sample [i-1] <= key

所以他们的诀窍在于他们在地图阶段确定键的方式.基本上,他们确保单个减速器中的每个值都保证与所有其他减速器"预先排序".

我通过James Hamilton的博客文章找到了论文.