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

[stiekel]

现有数百亿的 id，长度全是 32 位。给定一组 id （比如 10000 个），找出已经存在的 id，已经存在的可能是 0 个，也可能是 10000 个。请问有什么比较好的方案吗？
目前已经否决的：
1、Elasticsearch，速度太慢
2、Redis，使用 hash 组织，太消耗内存

谢谢各位。

主题中描述不准确，应该是每个 id 均是长度为 32 的字符串。内容是 16 进制的的字符。比如 e0a55133df7c1046db081a4640363bb1

[zealic]

Bitmap

[CodeCommunist]

空间与时间总要取舍，要看瓶颈在哪一块。持久化存取储是什么方式也没说，如果是分布式数据库能做到并行计算的话，就要看能有多少机器。另外 32 位怎么能表示百亿，你是说 32 个字符吧。

[pixiaotiao]

分段

[stiekel]

@CodeCommunist 是的 ，每个 id 都是 32 位的字符串。

[stiekel]

@CodeCommunist 是的 ，每个 id 都是长度为 32 的字符串。

[AlisaDestiny]

布隆过滤，有一定的误判几率，不过效率奇高。

[wangluofansi]

感觉布隆过滤器合适。
误判率的意思是:把 ID 放进布隆过滤器中，若 given_id not in bloom_filter，则该 id 一定不存在于你的 ID 集中；但若 given_id in bloom_filter，有一定可能实际上并不存在于你的 ID 集中，这一定可能就是误判率。

[xern]

字典树?

[blacklee]

凭感觉写。
先用楼上说的布隆过滤方法。
然后如果要完全精确，在建立集合的同时造一个子集合用来存所有的值，用来在通过布隆过滤后的精确确认。但这个数据量，对空间要求也是很高的。

[9hills]

其实 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]

当然 source 和 target 都非常大，就只能用 MapReduce 或者别的分布式计算的方式分而治之了

[abcbuzhiming]

要求很精确不，不是很精确就用布隆，要求很精确那就没办法了，空间不可少的。速度的话，首先用个 hash 算法，分个组，分而治之

[herozhang]

如果百亿 id 不是经常变化的，可以先把百亿 id 排序，然后查找就很快了

[WordTian]

百亿级的 32B 长度字符串，按百亿算，也有 320G 原始数据啊
还要快速，那就只能空间换时间了呗

[stiekel]

@AlisaDestiny
@wangluofansi
@blacklee
@abcbuzhiming
好的，我试试布隆过滤。
@xern 请问能否详细点？毕竟数量师有点大。
@9hills MapReduce 也是一个方案，我找时间试试。

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


@WordTian 是的，就是数据量太大了。

[lyjr]

32b 的长度只能表达大小为 2^32 的集合，也就是只有 42 亿多的字符串，哪来的百亿？问题本身就有毛病。。。

[doraemon0711]

@lyjr 可能是说位数吧

[tony601818]

Redis 的 BloomFilter 了解下？

[zealic]

详细说下我在一楼说的算法

(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]

上面的算

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

完成后的也可以通过 Redis 做一二级缓存，完成后可以直接判断 ID 是否存在，以及 ID 总数
落地磁盘做三级缓存，这样以后都不用再次统计数据

[stiekel]

@zealic 多谢你，朋友。这个我找时间试试，C++好久没用了，我用 Go 实现一下。
@tony601818 redis 都直接有布隆过滤了？我来看看。

[hugee]

这是要做特征库？

[tony601818]

@stiekel Redis 有官方支持的 ReBloom 模块： https://redislabs.com/redis-best-practices/bloom-filter-pattern/
当然你也可以自己在应用层写一个……

[sujin190]

trie 树存储呗，内存不够就序列化到磁盘，看你这个 32 位字符串都是 16 进制编码的吧，直接解码成 16 字节，查找磁盘最差也就 16 次，缓存开始几层，应该不慢

[stiekel]

@hugee 哈哈，的确类似特征库。

@tony601818 多谢。

@sujin190 是长度为 32 的字符串。append 中有示例。

[lujinang]

bloomfilter

[sujin190]

@stiekel #25 想了下，如果 500 亿的话，极限情况估计需要 6.2T 磁盘不小啊，前四到五层也许可以直接放到内存里，但是查询是稳定可靠的
排序后遍历 16 次就可以完成 trie 树构建，还是有点麻烦的，如果频繁查询也许还是不错，偶然用一下感觉还是 grep 来的更快更简洁吧
如果想读磁盘更少的话，可以每层保存两字节，8 次就可以，单每次读取量大大上涨了

[sujin190]

@zealic #19 内存使用量算错了吧，算法也不对吧，否则 mysql 索引应该早做成这样了，这么大数据量，想查询快，怎么也得几百 G 内存使用的吧

[stiekel]

@sujin190 如果单纯只存 id 得话，没 6 T 那么大。不过总体还是很吓人。