algorithm - MapReduce 排序算法如何工作？

Question

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

对我来说，排序只涉及确定一个元素相对于所有其他元素的相对位置。所以排序涉及将“一切”与“一切”进行比较。您的平均排序算法(快速、冒泡、...)只是以一种聪明的方式来执行此操作。

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

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

谢谢你帮助我理解。

Answer 1

以下是关于 Hadoop's implementation for Terasort 的一些详细信息:

TeraSort is a standard map/reduce sort, except for a custom partitioner that uses a sorted list of N − 1 sampled keys that define the key range for each reduce. In particular, all keys such that sample[i − 1] <= key < sample[i] are sent to reduce i. This guarantees that the output of reduce i are all less than the output of reduce i+1."

所以他们的技巧在于他们在映射阶段确定键的方式。从本质上讲，它们确保单个 reducer 中的每个值都保证针对所有其他 reducer 进行“预排序”。

我通过 James Hamilton's Blog Post 找到了论文引用.