MapReduce排序算法是如何工作的?

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

Terasort是一种标准的map/reduce排序,除了一个使用n_ 1采样键的排序列表的自定义分区程序,该列表定义了每个reduce的键范围。特别是,样本[I_ 1]<=key<sample[I]的所有键都被发送到reduce i。这保证reduce i的输出都小于reduce i+1的输出。”

所以他们的诀窍是在地图阶段确定关键点。从本质上讲,它们确保单个减速器中的每个值都与所有其他减速器“预先排序”。

我通过 James Hamilton's Blog Post .

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

出现在 :
OSDI'04:第六届操作系统设计与实现研讨会,
旧金山,CA,2004年12月。

该链接有一个PDF和HTML幻灯片参考。

还有一个 Wikipedia page with description 带有实现引用。

也批评,

DavidDewitt和MichaelStonebraker是并行数据库的先驱专家,他们对MapReduce所能解决的问题的广度提出了一些有争议的看法。他们称其界面太低,并质疑其是否真的代表了其支持者声称的范式转变。他们挑战了MapReduce支持者对新颖性的主张,引用Teradata作为已有20多年的现有技术的一个例子;他们将MapReduce程序员与Codasyl程序员进行了比较,并指出两者都是“用低级语言编写,执行低级记录操作”。MapReduce对输入文件的使用以及缺乏模式支持,阻碍了常见数据库系统功能(如B树和哈希分区)所带来的性能改进,尽管Piglain和Sawzall等项目已经开始解决这些问题。

在阅读谷歌的MapReduce论文时,我也有同样的问题。 @尤瓦尔F 的 answer 几乎解决了我的难题。

在阅读本文时我注意到的一件事是分区中发生了魔力(在映射之后,在reduce之前)。

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

只需将边界条件添加到 @尤瓦尔F 的 回答 要使其完成:假设Min(s)和Max(s)是采样键中的最小键和最大键;将所有键<Min(s)分区为一个reduce任务;反之亦然,将所有键>=Max(s)分区为一个reduce任务。

对采样键没有硬限制,例如最小或最大。只是,这些R键分布在所有键中越均匀,这个分布式系统越“并行”,reduce操作符出现内存溢出问题的可能性就越小。

只是猜测…

如果有一组巨大的数据,您可以将数据划分成若干块进行并行处理(可能按记录编号,即记录1-1000=分区1,依此类推)。

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

每个集群节点将进一步将分区分割(映射)成自己的小分区,可能按键的字母顺序排列。因此,在分区1中,获取以a开头的所有内容,并将其输出到x的迷你分区a中。如果当前已经存在a(x),则创建一个新的a(x)。用序列号替换X(也许这是调度程序的工作)。也就是说,给我下一个唯一的ID。

将映射器(上一步)完成的作业移交(调度)到“reduce”群集节点。然后,reduce node cluster将进一步细化每个a(x)部分的排序,当所有映射器任务完成时,这些A(x)部分只会发生(当仍然有可能生成另一个小分区时,实际上不能开始对所有单词进行排序,从w/a开始)。将结果输出到最终排序的分区(即sorted-a、sorted-b等)

完成后,再次将已排序的分区合并到单个数据集中。此时,它只是n个文件的简单连接(如果只执行a-z操作,n可能是26),等等。

中间可能有中间步骤…我不确定:)。即在初始减少步骤之后进一步映射和减少。