代码之家 › 专栏 › 技术社区 › Niels Basjes

在将值发送到reducer之前对其进行排序

mapreduce hadoop sorting

2

Niels Basjes · 技术社区 · 16 年前

我正在考虑在Hadoop中构建一个小型的测试应用程序,以掌握系统的窍门。

我想到的应用程序将在做统计方面。我想从reducer函数中得到“每个键的10个最差值”(在这里,我必须假设某些键的值可能很大)。

我计划的是,进入减速器的值基本上是“实际值”和“实际值的质量/相关性”的组合。基于相关性,我“简单”地想取10个最差/最佳值,并从减速器中输出它们。

我该怎么做呢(假设一个特定的键有大量的值)? 有没有一种方法可以在将所有值发送到reducer之前对其进行排序(当我读取前10个值时,只需停止读取输入),或者必须以不同的方式进行排序?

这里有人能给我指一段我可以看的示例代码吗?

更新:我发现了两个有趣的JIRA问题 HADOOP-485 和 HADOOP-686 .

有人有关于如何在Hadoop0.20API中使用这个的代码片段吗?

3 回复 | 直到 14 年前

1

SquareCog 16 年前

听起来您想使用组合器,它定义了在将创建的值发送到reducer之前,但在按键分组之后,如何处理这些值。合并器通常被设置为只是reducer类(因此在map端进行reduce,然后在reduce端再次进行reduce)。

看看wordcount示例如何使用合并器预计算部分计数:

http://wiki.apache.org/hadoop/WordCount

更新以下是我对你的问题的看法;不过,我可能误解了你的想法。

每个映射器发出 <key, {score, data}> 对。

合并器获取这些对的部分集: <key, [set of {score, data}> 并执行本地排序(仍在映射器节点上)和输出 <key, [sorted set of top 10 local {score, data}]> 对。

减速器会 <key, [set of top-10-sets]> --它所要做的就是对值集的每个成员执行排序合并(不需要排序)的合并步骤,并在提取前10个值时停止合并。

更新2

所以,既然我们知道了等级是连续的,因此,您不能使用合并器过早地过滤数据,唯一的事情就是做您建议的——进行二级排序。您已经找到了正确的记录单;在src/examples/org/apache/hadoop/examples/secondarysort.java中的hadoop 20中有一个如何做到这一点的示例(或者,如果您不想下载整个源代码树,可以查看 https://issues.apache.org/jira/browse/HADOOP-4545 )

2

4

Peter Wippermann 16 年前

听起来确实像是第二个排序问题。如果你愿意的话,可以看看“Hadoop:权威指南”。是O'Reilly寄来的。您也可以在线访问它。在这里,他们描述了一个非常好的实现。

我自己也实现了。基本上是这样工作的: 分区程序将关注所有具有相同键的键值对,这些键值对将流向一个reducer。这里没什么特别的。但是也有GroupingComparator,它将形成分组。一个组实际上作为迭代器传递给一个reduce()-调用。因此分区可以包含多个分组。但是分区的数量应该等于减速器的数量。但是分组还允许在实现CompareTo方法时进行一些排序。

使用此方法,可以控制10个最佳/最差/最高/最低键将首先到达减速器。因此,在您阅读了这10个键之后,您可以离开reduce方法而不进行任何进一步的迭代。

希望能帮上忙——)

3

0

bajafresh4life 16 年前

如果我正确理解这个问题,你需要使用 TotalOrderPartitioner .