用于展示 MapReduce 功能的主要示例之一是Terasort 基准。我无法理解 MapReduce 环境中使用的排序算法的基础知识。
对我来说，排序只是确定一个元素相对于所有其他元素的相对位置。因此，排序涉及将“一切”与“一切”进行比较。您的平均排序算法（快速、冒泡、...）只是以一种聪明的方式完成此操作。
在我看来，将数据集分成许多部分意味着您可以对单个部分进行排序，然后您仍然必须将这些部分整合到“完整”的完全排序的数据集中。鉴于分布在数千个系统上的 TB 数据集，我预计这将是一项艰巨的任务。
那么这到底是怎么做到的呢？这个 MapReduce 排序算法是如何工作的？
谢谢你帮助我理解。
TeraSort 是一个标准的 map/reduce 排序，除了一个自定义分区器，它使用 N - 1 个采样键的排序列表来定义每个 reduce 的键范围。特别是，所有满足 sample[i - 1] <= key < sample[i] 的键都被发送到 reduce i。这保证了reduce i的输出都小于reduce i+1的输出。”
所以他们的诀窍在于他们在映射阶段确定键的方式。本质上，它们确保单个 reducer 中的每个值都保证针对所有其他 reducer 进行“预排序”。
我通过James Hamilton 的博客文章找到了论文参考。
Google 参考：MapReduce：大型集群上的简化数据处理
出现在：
OSDI'04：第六届操作系统设计和实施研讨会，
加利福尼亚州旧金山，2004 年 12 月。
该链接有一个 PDF 和 HTML-Slide 参考。
还有一个Wikipedia 页面，其中包含带有实现参考的描述。
还有批评，
David DeWitt 和 Michael Stonebraker 是并行数据库和无共享架构的先驱专家，他们对 MapReduce 可用于解决的问题的广度提出了一些有争议的断言。他们称其界面太低级，并质疑它是否真的代表了其支持者所声称的范式转变。他们挑战 MapReduce 支持者的新颖性主张，引用 Teradata 作为已经存在了 20 多年的现有技术的一个例子；他们将 MapReduce 程序员与 Codasyl 程序员进行了比较，指出两者都是“用低级语言编写执行低级记录操作”。MapReduce 使用输入文件和缺乏模式支持阻碍了常见数据库系统功能（如 B 树和哈希分区）所带来的性能改进，
我在阅读 Google 的 MapReduce 论文时遇到了同样的问题。@Yuval F的回答几乎解决了我的难题。
我在阅读这篇论文时注意到的一件事是分区发生了魔法（在 map 之后，reduce 之前）。
本文使用hash(key) mod R作为分区示例，但这并不是将中间数据分区到不同 reduce 任务的唯一方法。
只需在@Yuval F的答案中添加边界条件即可完成：假设 min(S) 和 max(S) 是采样键中的最小键和最大键；所有 < min(S) 的键都被划分为一个 reduce 任务；反之亦然，所有 >= max(S) 的键都被划分为一个 reduce 任务。
采样键没有硬性限制，例如 min 或 max。只是，这些 R 键更均匀地分布在所有键中，这个分布式系统更“并行”，reduce 运算符不太可能出现内存溢出问题。
只是猜测...
给定大量数据，您可以将数据划分为一些块以并行处理（可能按记录编号，即记录 1 - 1000 = 分区 1，依此类推）。
将每个分区分配/调度到集群中的特定节点。
每个集群节点将进一步将分区分解（映射）到自己的迷你分区中，可能按字母顺序排列。所以，在分区 1 中，把所有以 A 开头的东西都给我，然后输出到 x 的迷你分区 A 中。如果当前已经存在 A(x)，则创建一个新的 A(x)。将 x 替换为序号（也许这是调度程序的工作）。即给我下一个 A(x) 唯一 ID。
将映射器（上一步）完成的作业移交（调度）到“reduce”集群节点。然后，Reduce 节点集群将进一步细化每个 A(x) 部分的排序，这将在所有映射器任务完成时发生（当仍有可能仍然存在时，实际上无法开始对所有以 w/A 开头的单词进行排序将成为另一个正在制作的迷你分区）。在最终排序的部分（即 Sorted-A、Sorted-B 等）中输出结果
完成后，再次将排序的分区组合成一个数据集。在这一点上，它只是 n 个文件的简单串联（如果你只做 A - Z，n 可能是 26）等等。
中间可能有中间步骤......我不确定:)。即在初始归约步骤之后进一步映射和归约。