MapReducesortingalgorithm如何工作？
Terasort基准testing中用来展示MapReducefunction的主要示例之一。 我无法理解在MapReduce环境中使用的sortingalgorithm的基础知识。
对我来说，sorting只涉及确定一个元素与所有其他元素的相对位置。 所以sorting包括比较“一切”和“一切”。 你的平均sortingalgorithm（快速，泡沫，…）只是在一个聪明的方式做到这一点。
在我看来，将数据集分成许多部分意味着您可以对单个部分进行sorting，然后您仍然必须将这些部分整合到“完整”完全sorting的数据集中。 鉴于分布在数千个系统上的TB级数据集，我预计这将是一项艰巨的任务。
那么这是如何做到的？ 这个MapReducesortingalgorithm是如何工作的？
感谢帮助我理解。
以下是有关Hadoop实现Terasort的一些细节：
TeraSort是一种标准的映射/减lesssorting，除了定制分区程序使用N – 1采样键sorting的列表，定义每个减less的键范围。 特别是，发送样本[i-1] <= key <sample [i]的所有密钥以减lessi。 这保证了减lessi的输出都小于减lessi + 1的输出。
所以他们的诀窍是他们在地图阶段确定键的方式。 从本质上讲，他们确保单个减速器中的每个值都能保证对所有其他减速器进行“预先sorting”。
我通过詹姆斯·汉密尔顿博客文章发现了这篇论文
Google Reference： MapReduce：简化大型集群数据处理
出现在 ：
OSDI'04：第六届操作系统devise与实现研讨会，
加利福尼亚州旧金山，2004年12月。
该链接有PDF和HTML-Slide参考。
还有一个维基百科页面，带有实现参考的描述 。
还有批评，
David DeWitt和Michael Stonebraker是并行数据库领域的先驱专家，没有共享架构，对于MapReduce可以使用的广泛问题提出了一些有争议的断言。 他们把它的接口称为低层次，并质疑它是否真正代表了它的支持者声称它的范式转变。 他们质疑MapReduce支持者的新颖性，声称Teradata是已有二十多年的现有技术的例子; 他们将MapReduce程序员与Codasyl程序员进行了比较，指出他们都是“用低级语言编写低级别的logging操作”。 MapReduce使用input文件和缺less模式支持，可以防止通用数据库系统function（如B树和散列分区）所带来的性能改进，但是像PigLatin和Sawzall这样的项目正在开始解决这些问题。
只是猜测…
给定一个巨大的数据集，你可以将数据分割成一些块并行处理（可能是logging号，即logging1 – 1000 =分区1，等等）。
将每个分区分配/调度到集群中的特定节点。
每个群集节点将进一步将分区分割（映射）到其自己的迷你分区中，可能是按照字母顺序排列。 因此，在分区1中，将所有以A开头的内容输出到x的迷你分区A中。 如果当前有A（x），则创build一个新的A（x）。 将xreplace为序列号（也许这是调度程序的工作）。 即给我下一个A（X）唯一的ID。
将由映射器（上一步）完成的作业移交（调度）到“减less”群集节点。 减less节点簇将进一步细化每个A（x）部分的sorting，当映射器任务完成时，这些部分将很快发生（当仍然存在仍然存在的可能性时，实际上不能开始sorting所有以W / A开始的词将成为另一个迷你分区）。 将结果输出到最终分类的部分（即Sorted-A，Sorted-B等）
完成后，再次将已sorting的分区组合到单个数据集中。 在这一点上，它只是一个简单的n个文件的连接（如果你只是在做A – Z，n可能是26）等等。
可能有中间步骤之间……我不知道:)。 即在最初的缩小步骤之后进一步映射并减less。
在阅读Google的MapReduce论文时，我也遇到过同样的问题。 @Yuval F的回答几乎解决了我的难题。
我在阅读这篇论文的时候注意到的一件事情是，魔术发生在分区之后（在缩小之前）。
本文使用hash(key) mod R作为分区的例子，但这不是将中间数据分区到不同reduce任务的唯一方法。
只要给@Yuval F的答案添加边界条件就可以了：假设min（S）和max（S）是采样密钥中的最小密钥和最大密钥; 所有密钥<min（S）被分区为一个reduce任务; 反之亦然，所有密钥> = max（S）被分区为一个reduce任务。
采样键没有硬性限制，如最小或最大。 只是，更均匀地将这些R密钥分布在所有密钥之中，这个分布式系统更“平行”，减less操作员存在内存溢出问题的可能性更小。
