MapReduce排序算法如何工作？

Question

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

对我来说，排序只需要确定一个元素与所有其他元素的相对位置。所以排序包括比较“一切”和“一切”。您的平均排序算法（快速，气泡，...）只是以一种明智的方式做到这一点。

在我看来，将数据集分成多个部分意味着您可以对单个部分进行排序，然后您仍然必须将这些部分整合到'完整'完全排序的数据集中。鉴于分布在数千个系统上的terabyte数据集，我预计这将是一项艰巨的任务。

那么这是如何做到的？这个MapReduce排序算法是如何工作的？

谢谢你帮助我理解。

Answer 1

这里有一些细节上Hadoop's implementation for Terasort：

TeraSort是一个标准的地图/排序减少，除了使用N的排序列表的自定义分区 - 定义键的范围为每减少1个采样键。特别是，样本[i - 1] < =样本[i]的密钥<被发送以减少i。这保证了减少i的输出都小于减少i + 1的输出。“

所以他们的诀窍是他们在映射阶段确定键的方式，基本上他们确保每个值一个减速是保证“预排序”对所有其他减速。

我发现通过James Hamilton's Blog Post本文参考。

Answer 2

谷歌参考：MapReduce: Simplified Data Processing on Large Clusters

出演：
OSDI'04：第六届学术研讨会操作系统的设计与实现，
旧金山，CA，十二月，2004

该链接具有PDF和HTML-Slide参考。

还有一个Wikipedia page with description与实施参考。

而且批评，

大卫德威特和迈克尔·斯通布雷克，并行数据库和无共享架构创业专家，作出了关于那MapReduce的可用于问题的广度一些有争议的断言。他们称其界面太低级，并质疑它是否真正代表其支持者所声称的范例转变。他们质疑MapReduce支持者的新颖性主张，并将Teradata列为已有二十多年的现有技术的一个例子;他们将MapReduce程序员与Codasyl程序员进行了比较，指出他们都是“用低级别语言编写低级别的记录操作”。 MapReduce使用输入文件和缺少模式支持可以防止通用数据库系统功能（如B树和散列分区）启用性能改进，但PigLatin和Sawzall等项目正在开始解决这些问题。

Answer 3

只是猜测......

鉴于庞大的数据集，则可以将数据分割成一些块并行，即记录1进行处理（也许通过记录号 - 1000 =分区1，和等等）。

将每个分区分配/调度到集群中的特定节点。

每个群集节点都会将分区进一步分割（映射）到它自己的迷你分区中，可能是按键字母顺序。因此，在分区1中，将所有以A开头的内容输出到x的迷你分区A中。如果当前有A（x），则创建一个新的A（x）。将x替换为顺序号（也许这是调度程序的工作）。即给我下一个A（X）唯一的ID。

将映射器（前一步骤）完成的作业移交（调度）到“减少”群集节点。然后减少节点集群将进一步改进每个A（x）部分的排序，当映射器任务完成时，这些部分将很快发生（当仍然存在仍然存在的可能性时，实际上无法开始排序所有以w/A开始的单词将成为另一个迷你分区）。将结果输出到最终的排序分区（即Sorted-A，Sorted-B等）

完成后，再次将已排序的分区组合到单个数据集中。在这一点上，它只是n个文件（其中n可能是26，如果你只是在做A - Z）等简单串联等。

可能有中间步骤之间......我不确定： ）。即在最初的缩小步骤之后进一步映射并减少。

Answer 4

我有同样的问题，而读谷歌的MapReduce纸。@Yuval˚F的answer几乎解决了我的难题。

我在阅读报纸时注意到的一件事是，魔术发生在分区中（在地图之后，减少之前）。

本文使用hash(key) mod R作为分区示例，但这不是将中间数据分区到不同reduce任务的唯一方法。

只需添加边界条件来@Yuval˚F的answer使它完成：假设分钟（S）和max（S）是被采样的键中的最小密钥和最大密钥;所有密钥<分钟（S）被分区为一个reduce任务;反之亦然，所有密钥> = max（S）被分区为一个reduce任务。

对采样键没有硬性限制，如最小或最大。只是，更均匀地将这些R密钥分布在所有密钥中，这个分布式系统更“平行”，减少操作员存在内存溢出问题的可能性更小。