背景

之前业务里面遇到一个问题,就是有两批url,都是亿级的,里面有一些相同的url,我们需要找出这些相同的url来,这个问题如果数据量比较少的话,肯定就比较简单了,我们直接最笨的方法进行O(n^2)次比较就行了,但是数据量这么大,单机程序肯定没法跑,我们使用集群的话,是把文件进行分开处理的,这样的话,一般的方法就不行了,最后用了一个比较巧妙的方法,感觉比较有意思,记录一下。

线索:map/reduce排序

我们知道,hadoop分为map和reduce两次作业,map输出的,是按照map的key进行排过序的数据,然后按照key分组,相同的key默认情况下一定进入同一个reduce作业,这样的话,我们就能在每一个reduce作业里面得到一批排过序的数据。
我们想一下,如果我们把两个数据集给合并到一块的话,那么经过排序,如果相同的url,位置肯定是前后的关系,这样的话,我们就能知道那些url有重复了,有重复,就代表有可能是交集的一部分。

问题:如何避免单个文件相同的url被算入交集

但是,按照我们上面那个方法,会造成一个问题,就是,如果发现有两个相同的url位置是前后的关系,那么我们不知道这两个url到底是来自同一个文件还是不同文件,如果这两个集合中都没有重复的数据就好办了,但是如果有的话,这个问题就不行了。
那么,我们需要想一个办法,去判断url到底属于哪一个集合。
这个小问题才是整个大问题的关键,其实很简单,我们给每个数据集再多加一列特征,这个特征就代表这行记录属于这个数据集。这样,当我们把两个数据集混合排序,相同的url位置前后的时候,我们就知道这两个url是不是来自不同的数据集了。
猛地一想,除了上面那个问题,貌似有可能一个数据集中会出现多个重复的项,这样会不会导致重复的url提取多遍呢,其实不会,因为我们排序的时候,我们多加的那一列特征也会进行排序,相同的url一定会排在一块,会形成下面这样:
1 1
2 1
4 1
4 1
4 2
4 2
5 2

这样的话,无论单个数据集里面有多少重复的,我们还是只会提取出和另一个数据集里面有交集的一个来。

examble

我们上面说了一堆,简单的示范一下:
比如,我们这里有两个数据集文件,
文件一:
2
1
4
6
8
5
3

文件二:1
5
2
6
8
3
2

我们把每个文件多加一列,来代表这个文件
文件一:
2 1
1 1
4 1
6 1
8 1
5 1
3 1

文件二:
5 2
2 2
6 2
8 2
3 2
2 2

然后,我们把两个文件合并到一块
2 1
1 1
4 1
6 1
8 1
5 1
3 1
5 2
2 2
6 2
8 2
3 2
2 2

我们把上面这个合并数据作为输入,这个数据有两列,第一列是原始求交的数据,第二列是判断数据集的

我们的map策略什么都不用做,只是输出就行,reduce策略如下:

#! /bin/bash

awk '
BEGIN{
    pre_value=""
    pre_id=""
}{
    cur_value=$1
    cur_id=$2

    if(pre_value==cur_value && pre_id!=cur_id){
        print cur_value
    }

    pre_value=cur_value
    pre_id=cur_id
}
'

这样,我们就能成功得到两个数据集的交集。

总结

这个数据集求交的问题其实挺简单的,但是感觉比较有意思,记录一下。


原创文章,转载请注明地址: 文章地址