使用MapReduce / Hadoop对大数据进行排序

Question

我正在阅读有关MapReduce的内容，以下内容使我感到困惑。

假设我们有一个包含一百万个条目（整数）的文件，并且我们想使用MapReduce对它们进行排序。我了解的处理方式如下：

编写一个对整数排序的映射器函数。因此，框架会将输入文件分为多个块，并将它们分配给不同的映射器。每个映射器将彼此独立地对数据块进行排序。完成所有映射器后，我们会将其每个结果传递给Reducer，它将合并结果并提供给我最终输出。

我的疑问是，如果我们只有一个化简器，那么它最终将如何利用分布式框架，如果最终我们必须将结果汇总到一个地方呢？问题可追溯到在一个地方合并100万个条目。是这样还是我缺少什么？

谢谢，钱德

Answer 1

查看合并排序。

事实证明，就操作和内存消耗而言，对部分排序的列表进行排序比对整个列表进行排序要有效得多。

如果化简器得到4个排序的列表，则只需查找4个列表中的最小元素，然后选择该列表。如果列表的数量是恒定的，则此减少为O（N）操作。

通常，减速器也可以“分布”在树上，因此工作也可以并行化。