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

实际工程中的十亿条数据完全匹配查询

  •  
  •   beryl · 353 天前 · 2839 次点击
    这是一个创建于 353 天前的主题,其中的信息可能已经有所发展或是发生改变。

    也算是一道常见的算法题:有十亿条 URL,来了一个新的 URL 判断是否在里面,提供在线服务

    但是想着优先使用 mysql 查询,其次 ES, 想布隆过滤器等不适合在工程应用,要保证准确

    现有思路,将 url 进行 md5 存储,作为主键 key 分表放在数据库。

    但是不清楚具体这种情况下效率会是怎么样

    22 条回复    2021-02-03 17:59:50 +08:00
    liprais
        1
    liprais  
       353 天前
    为啥 bloom 过滤器不行?
    Jooooooooo
        2
    Jooooooooo  
       353 天前
    "布隆过滤器等不适合在工程应用" "要保证准确"

    没有理解布隆的精髓啊
    rahuahua
        3
    rahuahua  
       353 天前
    @Jooooooooo 楼主这种情况确实不适合 bloom 呀
    lanmoyingsheng
        4
    lanmoyingsheng  
       353 天前   ❤️ 4
    布隆过滤可以保证不存在。
    感觉先布隆过滤,如果不存在直接返回;如果存在 再查 ES 或 mysql ;
    liuxu
        5
    liuxu  
       353 天前
    用 crc64 可以小一点,md5 得 32 位 char 做索引,然后 hash 拆库
    dongtingyue
        6
    dongtingyue  
       353 天前
    es 为啥不能保证准确?
    sampeng
        7
    sampeng  
       353 天前 via iPhone
    请问…用数据库,es 实现了。还考个什么算法?
    herozzm
        8
    herozzm  
       353 天前 via Android
    @dongtingyue #6 es 更新不能及时体现,只能说接近即时
    liuzhaowei55
        9
    liuzhaowei55  
       353 天前 via iPhone
    热数据放缓存,key hash 后分表,数据库如果用 mongo 单表 2 亿数据,加个索引就行了基本不需要特殊优化。
    swulling
        10
    swulling  
       353 天前
    不需要数据库,使用 Hash 表就可以了,先做 Hash,然后进行取模 Mod N,分布到 N 个 Hash 表里。

    估计需要 3 台 128G 内存的物理机就足够了。
    tisswb
        11
    tisswb  
       353 天前
    url 的话 那就先格式化,然后 md5,然后 redis
    fengpan567
        12
    fengpan567  
       353 天前
    ES 为啥不能保证准确性?更新延迟?
    love
        13
    love  
       353 天前
    md5 太大了,64 位 hash 算法如 xxhash 足够,hash 加个索引 where hash = ? and url = ?就行了
    THESDZ
        14
    THESDZ  
       353 天前
    拆分 模拟树结构就好了
    aeli
        15
    aeli  
       353 天前
    10 亿 url,做成短链?
    lambdaq
        16
    lambdaq  
       353 天前
    先申请 10 万台服务器,每个服务器存 1 万条数据。这样是不是就简单了。2333
    chenqh
        17
    chenqh  
       353 天前
    感觉可以 md5 hash,要是觉得长, 可以只存前 16 位呀
    wangdashuai
        18
    wangdashuai  
       353 天前
    可以构造前缀树,这样可以压缩数据大小.
    abersheeran
        19
    abersheeran  
       353 天前   ❤️ 1
    @wangdashuai 压缩前缀树面对十亿这个量级还是不够用的。我之前试过。

    楼主这个需求,如果只是判断是否在里面,布隆过滤器就够了。十亿数据,根据最优概率公式算出来,错误率控制在万分之一左右,我记得也就一个多 GB 。

    一份之前用过的 Python 代码贴出来以供参考:

    abersheeran
        20
    abersheeran  
       353 天前
    @abersheeran 如果要精准判断,这里就需要上一个 kv 索引了。这个参考一下 HBase 之类的数据库做法就行,也没啥别的好办法。
    Lemeng
        21
    Lemeng  
       353 天前
    10 亿条,竟然 url
    luozic
        22
    luozic  
       353 天前 via iPhone
    Cuckoo Filter 了解一下
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1599 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 17:38 · PVG 01:38 · LAX 09:38 · JFK 12:38
    ♥ Do have faith in what you're doing.