Terasort基准测试是演示MapReduce功能的主要示例之一。我在理解MapReduce环境中使用的排序算法的基础时遇到了麻烦。
对我而言，排序仅涉及确定元素相对于所有其他元素的相对位置。因此，排序涉及将“所有”与“所有”进行比较。您的平均排序算法（快速，冒泡，…）简单地以一种聪明的方式做到了。
在我看来，将数据集分为多个部分意味着您可以对单个部分进行排序，然后仍然必须将这些部分集成到“完整的”完全排序的数据集中。鉴于TB数据集分布在数千个系统中，我希望这是一项艰巨的任务。
那么这到底是怎么做的呢？该MapReduce排序算法如何工作？
感谢您帮助我理解。
以下是有关Hadoop为Terasort实施的一些详细信息：
TeraSort是标准的map / reduce排序，但自定义分区程序除外，该分区程序使用N-1个采样键的排序列表来定义每个reduce的键范围。特别是，发送所有采样，使sample [i-1] <= key <sample [i]减少i。这保证了reduce i的输出都小于reduce i + 1的输出。”
因此，他们的诀窍在于在地图阶段确定键的方式。从本质上讲，它们确保单个减速器中的每个值都保证与所有其他减速器“预排序”。
我通过James Hamilton的Blog Post找到了该论文的参考资料。
