Hadoop&Spark解决二次排序问题(Hadoop篇)

作者：过往记忆

本文由 过往记忆博客 授权发布，版权所有归作者，转载请联系作者！

问题描述

二次排序就是对每一个key对应的value进行排序，也就是对MapReduce的输出(KEY, Value(v1,v2,v3,……,vn))中的Value(v1,v2,v3,……,vn)值进行排序(升序或者降序)，使得Value(s1,s2,s3,……,sn)，si ∈ (v1,v2,v3,……,vn)且s1 < s2 < s3 < …… < sn。假设我们有以下输入文件(逗号分割的分别是年，月，总数)：

我们期望的输出结果是

但是Hadoop默认的输出结果只能对Key进行排序，其中Value中的值次序是不定的;也就是说，Hadoop默认的输出可能如下：

解决方案

针对这个问题我们有两种方法来解决：

(1)、将每个Key对应的Value全部存储到内存(这个只会存储到单台机器)，然后对这些Value进行相应的排序。但是如果Value的数据量非常大，导致单台内存无法存储这些数据，这将会导致程序出现java.lang.OutOfMemoryError，所以这个方法不是很通用。

(2)、这种方法将Value中的值和旧的Key组成一个新的Key，这样我们就可以利用Reduce来排序这个Key，其生成的结果就是我们需要的。过程如下：

1、原始的键值对是(k,v)。这里的k就是就的key，也可以 称为natural key;

2、我们可以将k和v组合成新的key(可以称为composite key)，也就是((k,v), v)

3、自定义分区函数，将k相同的键值对发送到同一个Reduce中;

4、自定义分组函数，将k相同的键值对当作一个分组。

文字比较枯燥，我们来看看下面实例：

1、原始数据是

我们将年、月组成key(natural key)，总数作为value，结果变成：

2、将value和key(natural key)组成新的key(composite key)，如下：

3、自定义分区函数，将k相同的键值对发送到同一个Reduce中，结果如下：

4、自定义组排序函数，结果如下：

5、自定义分组函数，结果如下：

6、最后输出的结果就是我们要的：

代码实例

下面将贴出使用MapReduce解决这个问题的代码：

上面就是将旧的Key(natural key)和Value组合成新的Key(composite key)的代码，接下来看下自定义的分区类：

这个类使得natural key相同的数据分派到同一个Reduce中。然后看下自定义分组类：

只要是natural key相同，我们就认为是同一个分组，这样Reduce内部才可以对Value中的值进行排序。接下来看下Map类

其实就是解析每一行的数据，然后将旧的Key(natural key)和Value组合成新的Key(composite key)。接下来看下Reduce类实现

builder存储的就是排序好的Value序列，最后来看看启动程序的使用：

关键看上面第12-15行的代码。下面是运行这个程序的方法和结果：

原文>>>

End.