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

大数据量下数据判重,有什么好的方法?

  •  
  •   leebs · 2022-03-08 23:37:19 +08:00 · 2119 次点击
    这是一个创建于 750 天前的主题,其中的信息可能已经有所发展或是发生改变。

    几十亿数据,提交一条数据,判断字段内容是否重复。 直接加索引,怕几十亿数据撑不住。

    15 条回复    2022-03-10 15:10:38 +08:00
    ericls
        1
    ericls  
       2022-03-08 23:43:40 +08:00 via iPhone
    benchmark 了吗?
    BrettD
        2
    BrettD  
       2022-03-08 23:46:01 +08:00   ❤️ 2
    bloom filter
    kera0a
        3
    kera0a  
       2022-03-08 23:47:19 +08:00 via iPhone   ❤️ 1
    布隆过滤器,但会有一点点误判率。
    误判率越小占用内存越大,速度非常快 O(1)
    wellsc
        4
    wellsc  
       2022-03-08 23:48:27 +08:00
    文本段?分词+倒排索引
    leebs
        5
    leebs  
    OP
       2022-03-09 00:11:02 +08:00
    @kera0a 布隆的空间占用情况呢,几十亿数据不会内存都放不下了吧。
    levelworm
        6
    levelworm  
       2022-03-09 00:16:55 +08:00 via Android
    不用全部对比吧,如果是分布式的话。更怕的是技术上不重但是业务上重。
    levelworm
        7
    levelworm  
       2022-03-09 00:39:12 +08:00 via Android
    对了,op 用的是什么数据库呐?
    LeeReamond
        8
    LeeReamond  
       2022-03-09 07:07:28 +08:00
    @kera0a 布隆过滤器一个问题是无法应对动态数据,实际业务里比如原先拦截 1 ,2 ,3 ,结果第二天业务上 2 从列表里删除了,布隆过滤器就比较吃瘪了
    murmur
        9
    murmur  
       2022-03-09 08:16:13 +08:00
    几十亿数据有分表或者分库么
    leebs
        10
    leebs  
    OP
       2022-03-09 09:14:11 +08:00
    @levelworm mongodb
    shawndev
        11
    shawndev  
       2022-03-09 10:22:34 +08:00
    Cuckoo Filter?
    ElmerZhang
        12
    ElmerZhang  
       2022-03-09 10:45:30 +08:00
    分表+唯一索引
    ElmerZhang
        13
    ElmerZhang  
       2022-03-09 10:49:06 +08:00
    当前表不好拆的话,就专门为这个索引建个新表,给这个表分表+唯一索引。
    写数据的时候用事务,两个表一起写。
    另外,你只是担心抗不住,到底抗不抗得住还是要看压测,说不定就抗得住了呢。不过这么大的表改索引也得费点劲。
    kera0a
        14
    kera0a  
       2022-03-09 10:50:24 +08:00
    @leebs 空间复杂度根据误判率来计算的
    50 亿数据,误判率 0.001 大概需要 8G 内存
    ghoul5426
        15
    ghoul5426  
       2022-03-10 15:10:38 +08:00
    居然没人说哈希,为每个数据计算一个哈希值,crc32 ( 32 位)、md5 ( 128 位)、sha1 ( 160 位)、sha256 ( 256 位)等都可以,可以把哈希值做主键或者唯一索引,可以用这个值来做分库分表的依据。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3210 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 11:33 · PVG 19:33 · LAX 04:33 · JFK 07:33
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.