V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
stiekel
V2EX  ›  问与答

有百亿计的字符串 id ,需要快速批量检查某些给定的 id 是否在其中存在,有什么比较好的解决方案?

  •  
  •   stiekel · 2019-03-24 19:28:47 +08:00 · 3559 次点击
    这是一个创建于 2055 天前的主题,其中的信息可能已经有所发展或是发生改变。
    现有数百亿的 id,长度全是 32 位。给定一组 id (比如 10000 个),找出已经存在的 id,已经存在的可能是 0 个,也可能是 10000 个。请问有什么比较好的方案吗?
    目前已经否决的:
    1、Elasticsearch,速度太慢
    2、Redis,使用 hash 组织,太消耗内存

    谢谢各位。
    第 1 条附言  ·  2019-03-25 07:14:22 +08:00
    主题中描述不准确,应该是每个 id 均是长度为 32 的字符串。内容是 16 进制的的字符。比如 e0a55133df7c1046db081a4640363bb1
    29 条回复    2019-03-25 19:59:33 +08:00
    zealic
        1
    zealic  
       2019-03-24 19:32:46 +08:00   ❤️ 2
    Bitmap
    CodeCommunist
        2
    CodeCommunist  
       2019-03-24 19:37:37 +08:00 via Android   ❤️ 2
    空间与时间总要取舍,要看瓶颈在哪一块。持久化存取储是什么方式也没说,如果是分布式数据库能做到并行计算的话,就要看能有多少机器。另外 32 位怎么能表示百亿,你是说 32 个字符吧。
    pixiaotiao
        3
    pixiaotiao  
       2019-03-24 19:39:11 +08:00 via Android   ❤️ 1
    分段
    stiekel
        4
    stiekel  
    OP
       2019-03-24 19:44:33 +08:00
    @CodeCommunist 是的 ,每个 id 都是 32 位的字符串。
    stiekel
        5
    stiekel  
    OP
       2019-03-24 19:45:47 +08:00
    @CodeCommunist 是的 ,每个 id 都是长度为 32 的字符串。
    AlisaDestiny
        6
    AlisaDestiny  
       2019-03-24 19:57:45 +08:00   ❤️ 2
    布隆过滤,有一定的误判几率,不过效率奇高。
    wangluofansi
        7
    wangluofansi  
       2019-03-24 20:10:11 +08:00 via Android   ❤️ 1
    感觉布隆过滤器合适。
    误判率的意思是:把 ID 放进布隆过滤器中,若 given_id not in bloom_filter,则该 id 一定不存在于你的 ID 集中;但若 given_id in bloom_filter,有一定可能实际上并不存在于你的 ID 集中,这一定可能就是误判率。
    xern
        8
    xern  
       2019-03-24 20:18:22 +08:00 via Android   ❤️ 1
    字典树?
    blacklee
        9
    blacklee  
       2019-03-24 20:28:03 +08:00   ❤️ 1
    凭感觉写。
    先用楼上说的布隆过滤方法。
    然后如果要完全精确,在建立集合的同时造一个子集合用来存所有的值,用来在通过布隆过滤后的精确确认。但这个数据量,对空间要求也是很高的。
    9hills
        10
    9hills  
       2019-03-24 20:39:44 +08:00   ❤️ 2
    其实 shell 一行就搞定了,而且也不占什么内存。如果要是嫌慢,就把文件用 split -l 拆分后,放到多台机器上执行。

    不过不会太慢,因为基本可以达到 IO 满速

    假如原始文件是 source,每个 id 是一行,几百亿行,要比对的 id 文件是 target

    awk 'ARGIND==1{a[$0]} ARGIND>1&&($0 in a){print $0}' target source > jiaoji
    # awk 需要是 gnu-awk,mac 上默认的不行,如果是 mac,可以用 brew install gawk

    jiaoji 就是两个文件的交集


    这个问题是我常备的基础面试题,数百亿 id 存到 Hash 表内存不够,反过来思考下,把 10000 条 id 塞到 hash 表里,然后数百亿的 id 一条条查不就完了。
    9hills
        11
    9hills  
       2019-03-24 20:41:09 +08:00   ❤️ 1
    当然 source 和 target 都非常大,就只能用 MapReduce 或者别的分布式计算的方式分而治之了
    abcbuzhiming
        12
    abcbuzhiming  
       2019-03-24 20:43:54 +08:00   ❤️ 1
    要求很精确不,不是很精确就用布隆,要求很精确那就没办法了,空间不可少的。速度的话,首先用个 hash 算法,分个组,分而治之
    herozhang
        13
    herozhang  
       2019-03-24 21:37:23 +08:00   ❤️ 1
    如果百亿 id 不是经常变化的,可以先把百亿 id 排序,然后查找就很快了
    WordTian
        14
    WordTian  
       2019-03-24 21:42:18 +08:00 via Android   ❤️ 1
    百亿级的 32B 长度字符串,按百亿算,也有 320G 原始数据啊
    还要快速,那就只能空间换时间了呗
    stiekel
        15
    stiekel  
    OP
       2019-03-24 23:12:14 +08:00
    @AlisaDestiny
    @wangluofansi
    @blacklee
    @abcbuzhiming
    好的,我试试布隆过滤。
    @xern 请问能否详细点?毕竟数量师有点大。
    @9hills MapReduce 也是一个方案,我找时间试试。

    @herozhang 会变化,比如发现一个不存在,那就先存到库里,再需要添加进去。


    @WordTian 是的,就是数据量太大了。
    lyjr
        16
    lyjr  
       2019-03-24 23:20:25 +08:00   ❤️ 1
    32b 的长度只能表达大小为 2^32 的集合,也就是只有 42 亿多的字符串,哪来的百亿?问题本身就有毛病。。。
    doraemon0711
        17
    doraemon0711  
       2019-03-24 23:26:01 +08:00   ❤️ 1
    @lyjr 可能是说位数吧
    tony601818
        18
    tony601818  
       2019-03-24 23:48:06 +08:00   ❤️ 1
    Redis 的 BloomFilter 了解下?
    zealic
        19
    zealic  
       2019-03-25 00:55:34 +08:00   ❤️ 1
    详细说下我在一楼说的算法

    (Bitmap + 二叉树) x 链表

    空间最小化,根据已知条件,最坏的情况下内存占用为 645K,计算量也不大

    算法细节为,

    BitmapBinaryTree,六级,1->2-4->8->16->32
    然后循环所有 ID,每个 ID 置位 Bitmap,发现重复的 ID 就创建一个新的 BitmapBinaryTree 并置位
    如此循环最多创建 10000 个 BitmapBinaryTree
    因为大多数 ID 不重复,大部分数据位只会存在于第一个 BitmapBinaryTree

    那么最终数据结构应该叫做 BinaryTreeChain,数据结构如下

    type BinaryTreeChain struct {
    Left *Bitmap128
    Right *Bitmap128
    Next *BinaryTreeChain

    // 二分查找对应的 Bitmap8 并置位,若设置成功返回,否则代表重复
    // 重复需要创建或查找 Next 链并置位
    SetByID(id int256) bool
    //获取值
    GetByID(id int256) bool
    // 计算总数
    CountByID(id int256) bool
    }

    type Bitmap128 struct {
    Left *Bitmap64
    Right *Bitmap64
    }

    type Bitmap64 struct {
    Left *Bitmap32
    Right *Bitmap32
    }

    type Bitmap32 struct {
    Left *Bitmap16
    Right *Bitmap16
    }


    type Bitmap16 struct {
    Left *Bitmap8
    Right *Bitmap8
    }

    type Bitmap8 = byte
    zealic
        20
    zealic  
       2019-03-25 01:06:49 +08:00   ❤️ 1
    上面的算

    首次读取需要读取所有数据,以后增量数据就极其方便,开销几乎可以忽视
    如果对于读取数据有比较高的要求,也可以 MapReduce 并行运行

    完成后的也可以通过 Redis 做一二级缓存,完成后可以直接判断 ID 是否存在,以及 ID 总数
    落地磁盘做三级缓存,这样以后都不用再次统计数据
    stiekel
        21
    stiekel  
    OP
       2019-03-25 07:16:16 +08:00
    @zealic 多谢你,朋友。这个我找时间试试,C++好久没用了,我用 Go 实现一下。
    @tony601818 redis 都直接有布隆过滤了?我来看看。
    hugee
        22
    hugee  
       2019-03-25 09:08:46 +08:00 via Android   ❤️ 1
    这是要做特征库?
    tony601818
        23
    tony601818  
       2019-03-25 09:20:20 +08:00   ❤️ 1
    @stiekel Redis 有官方支持的 ReBloom 模块: https://redislabs.com/redis-best-practices/bloom-filter-pattern/
    当然你也可以自己在应用层写一个……
    sujin190
        24
    sujin190  
       2019-03-25 09:52:17 +08:00   ❤️ 1
    trie 树存储呗,内存不够就序列化到磁盘,看你这个 32 位字符串都是 16 进制编码的吧,直接解码成 16 字节,查找磁盘最差也就 16 次,缓存开始几层,应该不慢
    stiekel
        25
    stiekel  
    OP
       2019-03-25 10:26:02 +08:00
    @hugee 哈哈,的确类似特征库。

    @tony601818 多谢。

    @sujin190 是长度为 32 的字符串。append 中有示例。
    lujinang
        26
    lujinang  
       2019-03-25 10:29:03 +08:00   ❤️ 1
    bloomfilter
    sujin190
        27
    sujin190  
       2019-03-25 10:41:30 +08:00   ❤️ 1
    @stiekel #25 想了下,如果 500 亿的话,极限情况估计需要 6.2T 磁盘不小啊,前四到五层也许可以直接放到内存里,但是查询是稳定可靠的
    排序后遍历 16 次就可以完成 trie 树构建,还是有点麻烦的,如果频繁查询也许还是不错,偶然用一下感觉还是 grep 来的更快更简洁吧
    如果想读磁盘更少的话,可以每层保存两字节,8 次就可以,单每次读取量大大上涨了
    sujin190
        28
    sujin190  
       2019-03-25 10:50:51 +08:00   ❤️ 1
    @zealic #19 内存使用量算错了吧,算法也不对吧,否则 mysql 索引应该早做成这样了,这么大数据量,想查询快,怎么也得几百 G 内存使用的吧
    stiekel
        29
    stiekel  
    OP
       2019-03-25 19:59:33 +08:00
    @sujin190 如果单纯只存 id 得话,没 6 T 那么大。不过总体还是很吓人。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5355 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 08:41 · PVG 16:41 · LAX 00:41 · JFK 03:41
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.