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

我正在阅读有关MapReduce的内容,以下内容令我感到困惑.

假设我们有一个包含100万个条目(整数)的文件,我们想要使用MapReduce对它们进行排序.我理解的方式如下:

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

我怀疑的是,如果我们有一个reducer,那么它如何利用分布式框架,如果最终我们必须将结果合并到一个地方？问题是在一个地方合并100万个条目.是这样还是我错过了什么？

谢谢,Chander

检查合并排序.

事实证明,排序部分排序列表在操作和内存消耗方面比排序完整列表更有效.

如果reducer获得4个排序列表,它只需要查找4个列表中的最小元素并选择该列表.如果列表的数量是常数,则该减少是O(N)操作.

通常,减速器也像树一样"分布",因此工作也可以并行化.

正如其他人所提到的,合并比分类简单得多,因此在那里取得了很大的成功.

但是,对巨型数据集执行O(N)串行操作也是令人望而却步的.正如您正确指出的那样,最好还是找到一种并行进行合并的方法.

实现此目的的一种方法是将分区函数从随机分区器(这是通常使用的)替换为更智能的东西.例如,Pig为此做的是对数据集进行采样,以得出值的分布的粗略近似值,然后将值的范围分配给不同的reducer.Reducer 0获取所有元素<1000,reducer 1获取所有元素> = 1000且<5000,依此类推.然后,您可以并行执行合并,并根据您知道每个reducer任务的数量对最终结果进行排序.

因此,使用map-reduce进行排序的最简单方法(尽管不是最有效的方法)是执行以下操作

在Map阶段(Input_Key,Input_Value)发出(Input_Value,Input Key)

Reducer是一个身份减少器

因此,例如,如果我们的数据是学生,年龄数据库,那么您的映射器输入将是('A',1)('B',2)('C',10)......并且输出将是(1, A)(2,B)(10,C)

没有尝试过这种逻辑,但这是我正在研究的家庭作业问题的一步.将放置更新源代码/逻辑链接.