hadoop or spark 大数据去重(10 亿)

[engineer9]

现有一些社交数据如下，

id from to
1   A   B
2   A   C
3   B   A
4   C   A

去重复后如下，

id from to
1   A   B
2   A   C

尝试的解决方案:
1、采用 bloomfilter 去重，由于 bloomfilter 本身算法问题，会丢失一些数据；
2、使用数据库查询然后写入到新表，速度有点慢。
3、使用 BerkeleyDB ？
4、使用 hadoop 或者 spark 解决,网上找到的方式几乎都是使用 group by 或者 distinct 但这并不适合我这个场景，如何解决呢？
头大。。。新手上路。。。

[zjxzhqq]

很简单吧你把后两个字段排下序，然后根据这两个字段去重就可以了

[bsidb]

这个就是转无向图的过程吧？

使用 Spark SQL API （ Spark RDD API 的 distinct 有严重的 GC 问题，不推荐）。

1. 将数据导入 Spark SQL 的表
2. 将 from 和 to 规则化（确保 from 的顶点 ID 小于 to 的）
3. 使用 Spark SQL API 进行 distinct 去重

[liprais]

from 和 to 拼起来再 group by 就行了

[omygod]

好巧 https://www.v2ex.com/t/474997

[xwander]

先用 bloomfilter 判断是否有这段数据，如果有，再进一步使用 md5 判断。
有时间深入，可以了解下，Online Deduplication。
https://ieeexplore.ieee.org/document/7996543/

[zhuanggu]

select id, `from`, `to` from( select id, `from`, `to`,row_number() over(partition by `from`,`to` order by id) rk) t where rk=1

[luckychenhaha]

from 和 to 做字母排序，然后 hadoop 的 kv 自动匹配就可以了

[BIGUFO]

@bsidb 请问为什么 sparkSQL 的 distinct api 要比 rdd 的 distinct 好？

[engineer9]

@bsidb 在 spark 中具体怎么规则化？ map 这里

[pwrliang]

尝试实现下 cuckoo hash ？ https://en.m.wikipedia.org/wiki/Cuckoo_hashing

[laxenade]

map 阶段：让 from < to
reduce 阶段：做 distinct
这样不行吗

[owenliang]

难道不是构造一个 from_to 的 key，直接走 spark 或者 mr 去重就可以了吗。。

[bsidb]

@BIGUFO RDD 的 distinct 中每一条记录会创建一个对象，10 亿条记录会创建 10 亿个对象，即使集群多机计算，中间生成这么多对象 GC 压力也很大。SQL API 有钨丝计划优化，gc 问题会小很多。

[bsidb]

@engineer9 如果 from > to 则 map 一个（ id, to, from ）否则 map(id, from, to)

[bsidb]

@engineer9 在导入数据的时候先处理好，再创建 SQL 表比较方便

[dangluren]

为什么 spark,hadoop 不适合你们的场景。
是考虑到 A B B A 无法判断相同？ 这种情况可以将每一条看成一个对象，重写 equals 方法啊。
又或者是考虑到资源不足？

[dangluren]

bloomfilter 其实也是可以的， 首先第一步：
不在里面： 肯定不在里面。
在里面： 可能不在里面。 这时候，我们并不是把这条数据去掉，而是将这条数据给记录下来，敢肯定的是，由于布隆过滤器的概率，这种数据肯定很少很少。
下一步：
将这 10 亿条数据再遍历一次，看看上面保存的数据到底有没有重复。

这种需求简单的很呐

[dangluren]

布隆过滤器的原理和使用参考我之前写的：
https://blog.csdn.net/t1dmzks/article/details/79212179

[diginWu]

百八十 M 的东西内存里面算不就行了么？

[diginWu]

不好意思少算了一个数量级。