V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
engineer9
V2EX  ›  Hadoop

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

  •  
  •   engineer9 · 2018-07-30 10:03:38 +08:00 · 6596 次点击
    这是一个创建于 2068 天前的主题,其中的信息可能已经有所发展或是发生改变。

    现有一些社交数据如下,

    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 但这并不适合我这个场景,如何解决呢?
    头大。。。新手上路。。。

    21 条回复    2018-07-31 11:54:51 +08:00
    zjxzhqq
        1
    zjxzhqq  
       2018-07-30 10:29:25 +08:00 via Android
    很简单吧你把后两个字段排下序,然后根据这两个字段去重就可以了
    bsidb
        2
    bsidb  
       2018-07-30 10:37:34 +08:00   ❤️ 1
    这个就是转无向图的过程吧?

    使用 Spark SQL API ( Spark RDD API 的 distinct 有严重的 GC 问题,不推荐)。

    1. 将数据导入 Spark SQL 的表
    2. 将 from 和 to 规则化(确保 from 的顶点 ID 小于 to 的)
    3. 使用 Spark SQL API 进行 distinct 去重
    liprais
        3
    liprais  
       2018-07-30 10:50:21 +08:00 via iPhone
    from 和 to 拼起来再 group by 就行了
    omygod
        4
    omygod  
       2018-07-30 11:00:39 +08:00
    xwander
        5
    xwander  
       2018-07-30 11:08:49 +08:00
    先用 bloomfilter 判断是否有这段数据,如果有,再进一步使用 md5 判断。
    有时间深入,可以了解下,Online Deduplication。
    https://ieeexplore.ieee.org/document/7996543/
    zhuanggu
        6
    zhuanggu  
       2018-07-30 11:10:47 +08:00
    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
        7
    luckychenhaha  
       2018-07-30 11:12:19 +08:00
    from 和 to 做字母排序,然后 hadoop 的 kv 自动匹配就可以了
    BIGUFO
        8
    BIGUFO  
       2018-07-30 11:18:38 +08:00
    @bsidb 请问为什么 sparkSQL 的 distinct api 要比 rdd 的 distinct 好?
    engineer9
        9
    engineer9  
    OP
       2018-07-30 11:26:18 +08:00
    @bsidb 在 spark 中具体怎么规则化? map 这里
    pwrliang
        10
    pwrliang  
       2018-07-30 11:48:34 +08:00 via Android
    尝试实现下 cuckoo hash ? https://en.m.wikipedia.org/wiki/Cuckoo_hashing
    laxenade
        11
    laxenade  
       2018-07-30 11:53:42 +08:00
    map 阶段:让 from < to
    reduce 阶段:做 distinct
    这样不行吗
    owenliang
        12
    owenliang  
       2018-07-30 12:18:40 +08:00
    难道不是构造一个 from_to 的 key,直接走 spark 或者 mr 去重就可以了吗。。
    bsidb
        13
    bsidb  
       2018-07-30 12:24:48 +08:00 via Android
    @BIGUFO RDD 的 distinct 中每一条记录会创建一个对象,10 亿条记录会创建 10 亿个对象,即使集群多机计算,中间生成这么多对象 GC 压力也很大。SQL API 有钨丝计划优化,gc 问题会小很多。
    bsidb
        14
    bsidb  
       2018-07-30 12:26:33 +08:00 via Android
    @engineer9 如果 from > to 则 map 一个( id, to, from )否则 map(id, from, to)
    bsidb
        15
    bsidb  
       2018-07-30 12:28:22 +08:00 via Android
    @engineer9 在导入数据的时候先处理好,再创建 SQL 表比较方便
    dangluren
        16
    dangluren  
       2018-07-30 17:21:39 +08:00
    为什么 spark,hadoop 不适合你们的场景。
    是考虑到 A B B A 无法判断相同? 这种情况可以将每一条看成一个对象,重写 equals 方法啊。
    又或者是考虑到资源不足?
    dangluren
        17
    dangluren  
       2018-07-30 17:28:54 +08:00
    bloomfilter 其实也是可以的, 首先第一步:
    不在里面: 肯定不在里面。
    在里面: 可能不在里面。 这时候,我们并不是把这条数据去掉,而是将这条数据给记录下来,敢肯定的是,由于布隆过滤器的概率,这种数据肯定很少很少。
    下一步:
    将这 10 亿条数据再遍历一次,看看上面保存的数据到底有没有重复。

    这种需求简单的很呐
    dangluren
        18
    dangluren  
       2018-07-30 17:30:41 +08:00
    布隆过滤器的原理和使用参考我之前写的:
    https://blog.csdn.net/t1dmzks/article/details/79212179
    diginWu
        19
    diginWu  
       2018-07-30 17:41:53 +08:00
    百八十 M 的东西内存里面算不就行了么?
    diginWu
        20
    diginWu  
       2018-07-30 17:45:43 +08:00
    不好意思少算了一个数量级。
    kavana
        21
    kavana  
       2018-07-31 11:54:51 +08:00
    hadoop or spark 大数据去重,收藏待用
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   954 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 20:49 · PVG 04:49 · LAX 13:49 · JFK 16:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.