MapReduce在相似度计算中的应用及优化

Contents

1. 一、用户维度的Join
2. 二、特征维度
1. 2.1. 1、转成特征对用户的矩阵：F1->U1…Un
2. 2.2. 2、计算相似度

需求：计算用户的相似度，有用户列表U和特征列表F以及用户和特征的关系。根据 ∩ 的交集数来判断U1和U2的相似度。
解决方法：

一、用户维度的Join

最暴力低效的方法，因为用户量一般很大，所以join效率极低。一般不考虑。

二、特征维度

将用户对特征的矩阵转成特征对用户的矩阵。

1、转成特征对用户的矩阵：F1->U1…Un

1 2	map: context.write(F, U) reduce: context.write(F,List<U>)

2、计算相似度

各种解决方案如下：

(1)直接输出UxUy pair(IO密集型)

map: 将user list拆成各user pair对并输出，具体如下所示范例(代码只是伪码)：

String data[] = value.toSting().split("\t");
String users[] = data[1].split(",");//user间以,分隔
for(int i = 0; i < users.length; i ++){
for(int j = i + 1; j < users.length; j ++){
        //判断users[i]与users[j]的大小 
context.write(users[i]+"_"+users[j], 1);//这里要加上users[i]与users[j]大小的判断，小放前，大放后，便于后面的操作
    }
}

reduce: 对每个user pair的value list进行求和，即是这两个用户的相似度
缺点：map端输出的user pair很多(O(N*N))，使reducer的shuffle成为瓶颈

(2)按各user进行聚合(计算密集型)

< u1,u3,u5,u2 >，按(1)的输出是< u1_u3–>1 >, < u1_u5–>1 >, < u1_u2–>1>, < u3_u5–>1 >, < u3_u2–>1 >,< u5_u2–>1 >。 (1是次数)
按user聚合的结果是：< u1–>u2,u3,u5 > ,< u2–>u3,u5 >,< u3–>u5 >，输出数为N(U)-1。
该方案需要对user list进行排序，便于后面reduce进行按userid聚合，如一个user list输出的是< u1–>u2,u3,u5 >，另一个是< u1–>u3,u5 >,这样reduce时就是u1->u2,u3,u5,u3,u5。
而如果不排序的话就需要再弄一个job进行操作：如< u1–>u2,u3,u5 >, < u2–>u1,u3,u5 > 。这样会得到< u1_u2 >与< u2_u1 >，还需要job进行一次合并求和处理。
mapper:

    StringBuilder uuidListStr = new StringBuilder();
    String data[] = value.toString().split("\t");
    String uuidArr[] = data[1].split(",");
    Arrays.sort(uuidArr);
    for(int i = 0; i < uuidArr.length; i ++){
        for(int j = i + 1; j < uuidArr.length; j ++){
            uuidListStr.append(uuidArr[j]).append(",");
        }
    	if(uuidListStr.length() > 0){
    	    uuidListStr.deleteCharAt(uuidListStr.length() - 1);
    	    context.write(new Text(uuidArr[i]), new Text(uuidListStr.toString()));
    	    uuidListStr = new StringBuilder();
    	}
    } 
```       
reduce: 会得到u1->u2,u3,u5,u3,u5,  计算values中各用户出现的个数< ux,count >, 然后输出count即可
```java
    //利用hashMap来管理各user的次数
    Map<String, Integer> countMap = new HashMap<String, Integer>();
    for (Text v : values) { //每个v都是u1,u2,u3这样的形式
        uuids = v.toString().split(",");
        for (int i = 0; i < uuids.length; i++) {
            uuid = uuids[i];
            tmp = countMap.get(uuid);
            if (null == tmp) {
                countMap.put(uuid, new Integer(1));
            } else {
                countMap.put(uuid, tmp + 1);
            }
        }
    }
    for (Map.Entry<String, Integer> entry : countMap.entrySet()) {
        context.write(new Text(key.toString() + "_" + entry.getKey()), new IntWritable(entry.getValue()));
    }

该方案有个瓶颈是map中自己实现的排序，可能某个F下用户数特别大，会造成数据倾斜，有的user list特别大，排序花费时间长，导致整个任务变慢(计算密集型)。一种思路是将splitSize变小，如从默认的64M变成8M，这样InputSplit数将变多，即Mapper变多，各个Mapper处理的数据量变小，充分发挥并行的优势。
具体设置splitSize的代码：

1
2
3

//splitSize = max(minSize, min(maxSize, blockSize))
conf.set("mapred.min.split.size", 8 * 1024 * 1024 + "");
conf.set("mapred.max.split.size", 8 * 1024 * 1024 + "");

(3)排序放到Reducer端

在转置特征对用户的矩阵的job中reduce已经得到了各F的user list，则可以直接对user list进行排序并输出按user聚合的结果。

a、reduce方法中对user list进行排序

会遇到和(2)方案中一样的数据倾斜问题，且无法像(2)那样减少splitSize来减少各Mapper的处理数据量，增大Mapper数。该方案一般会作死，数据量大时不用考虑。

b、利用Reducer的Sort功能

需要覆盖的类：
MapOutputKey：其中的compareTo用于map/reduce各阶段进行排序的依据
Partitioner: 用于partition分到哪个区
GroupingComparator：用于reduce的sort–>reduce中 key迭代时的分组。
Reducer的各阶段为：Shuffle/Merge, Sort, Reduce, Output。其中Sort与Reduce是并行的。Sort迭代遍历得到的记录会进行grouping,从而得到reduce方法中的values。
Sort会将各文件按Key(MapOutputKey)的大小建最小堆，每取一个最小Key的记录, 都会到GroupingComparator进行判断(具体源码没研究，不过这里面的实现应该是会保存上一个记录的Key, 如果当前记录与上一Key 通过GroupingComparator方法得到的结果是一样的话，则把当前记录加到group的记录列表中，该列表元素顺序是按插入顺序的；如果不一样的话，就将Key以前列表的数据传到reduce方法，并清空group的记录列表)
我们可以创建自己的MapOutputKey

public class GeoMapOutputKey implements Writable,WritableComparable<GeoMapOutputKey> {
    private Text geohash = new Text();//相当于Feature
    private Text uuid = new Text();  //相当于user
    public GeoMapOutputKey(){}
    public GeoMapOutputKey(String geohash, String uuid){
        this.geohash.set(geohash);
        this.uuid.set(uuid);
    }
    public Text getGeohash() {
        return geohash;
    }
    public void setGeohash(Text geohash) {
        this.geohash = geohash;
    }
    public Text getUuid() {
        return uuid;
    }
    public void setUuid(Text uuid) {
        this.uuid = uuid;
    }
    @Override
    public void write(DataOutput dataOutput) throws IOException {
        geohash.write(dataOutput);
        uuid.write(dataOutput);
    }
    @Override
    public void readFields(DataInput dataInput) throws IOException {
        geohash.readFields(dataInput);
        uuid.readFields(dataInput);
    }
    @Override
    //重点是这个compareTo方法，会先根据geohash进行排序，再根据uuid进行排序
    public int compareTo(GeoMapOutputKey o) {
        int compareValue = this.geohash.compareTo(o.geohash);
        if(compareValue == 0){
            compareValue = this.uuid.compareTo(o.uuid);
        }
        return compareValue;
    }
    @Override
    public int hashCode() {
        return geohash.hashCode() * 163 + uuid.hashCode() * 163;
    }
    @Override
    public boolean equals(Object o) {
        if (o instanceof GeoMapOutputKey) {
            GeoMapOutputKey ok = (GeoMapOutputKey) o;
            return geohash.equals(ok.getGeohash()) && uuid.equals(ok.getUuid());
        }
        return false;
    }
    @Override
    public String toString() {
        return geohash + "\t" + uuid;
    }
}

通过这个GeoMapOutputKey，就可以保存先按Feature进行排序，再按user进行排序。(map输出有N行记录，Reducer默认情况下也要对这N行记录进行compare，所以性能没有什么影响)。
Mapper的map阶段的输出会调用Partitioner方法进行决定分区，默认情况下会按feature+user进行分区，我们需要按Feature进行分区，所以要覆盖：

public class GeoPartitioner extends Partitioner<GeoMapOutputKey, Text> {
    @Override
    public int getPartition(GeoMapOutputKey geoMapOutputKey, Text text, int numPartitions) {
   //这里的geohash就是feature
        return Math.abs(geoMapOutputKey.getGeohash().hashCode()) % numPartitions;
    }
}

默认情况下Reducer的GroupingComparator会按Key进行grouping聚合操作，这样reduce方法中的key就是feature_u1这样的，没多大帮助，所以我们要自定义GroupingComparator，让相同feature的聚合在一起，即reduce方法中的key是feature。

public class GeoGroupingComparator extends WritableComparator {
    protected GeoGroupingComparator() {
        super(GeoMapOutputKey.class, true);
    }
    @Override
    public int compare(WritableComparable a, WritableComparable b) {
        GeoMapOutputKey ok1 = (GeoMapOutputKey) a;
        GeoMapOutputKey ok2 = (GeoMapOutputKey) b;
        //这里只对feature进行比较，即会按feature进行grouping聚合
        return ok1.getGeohash().compareTo(ok2.getGeohash());
    }
}

设置这两个类的代码：

1 2	job.setMapOutputKeyClass(GeoMapOutputKey.class); job.setGroupingComparatorClass(GeoGroupingComparator.class);

通过这样的设置，就可以实现Sort最小堆是按先feature再user进行排序，而聚合时又是按feature进行聚合。
reduce中的key是,,中的某一个(第一个?)，value是< u1,u2,u5 >
这个job的输出是U1–>u2,u3,u5这样的形式。
下一个job的mapper只要context(“u1”,”u2,u3,u5”)，而reducer和(2)中的reducer操作一样。

第(3)种方案是最优的，处理速度比前面的高效很多。

DataKnocker

learn bigdata step by step