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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2062 天前的主题，其中的信息可能已经有所发展或是发生改变。

现有数百亿的 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

给定

Redis

Hash

存在

29 条回复 • 2019-03-25 19:59:33 +08:00

zealic

2019-03-24 19:32:46 +08:00

Bitmap

CodeCommunist

2019-03-24 19:37:37 +08:00 via Android

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

pixiaotiao

2019-03-24 19:39:11 +08:00 via Android

分段

stiekel

2019-03-24 19:44:33 +08:00

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

stiekel

2019-03-24 19:45:47 +08:00

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

AlisaDestiny

2019-03-24 19:57:45 +08:00

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

wangluofansi

2019-03-24 20:10:11 +08:00 via Android

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

xern

2019-03-24 20:18:22 +08:00 via Android

字典树?

blacklee

2019-03-24 20:28:03 +08:00

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

9hills

2019-03-24 20:39:44 +08:00

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

2019-03-24 20:41:09 +08:00

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

abcbuzhiming

2019-03-24 20:43:54 +08:00

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

herozhang

2019-03-24 21:37:23 +08:00

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

WordTian

2019-03-24 21:42:18 +08:00 via Android

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

stiekel

2019-03-24 23:12:14 +08:00

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

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

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

lyjr

2019-03-24 23:20:25 +08:00

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

doraemon0711

2019-03-24 23:26:01 +08:00

@lyjr 可能是说位数吧

tony601818

2019-03-24 23:48:06 +08:00

Redis 的 BloomFilter 了解下？

zealic

2019-03-25 00:55:34 +08:00

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

(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

2019-03-25 01:06:49 +08:00

上面的算

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

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

stiekel

2019-03-25 07:16:16 +08:00

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

hugee

2019-03-25 09:08:46 +08:00 via Android

这是要做特征库？

tony601818

2019-03-25 09:20:20 +08:00

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

sujin190

2019-03-25 09:52:17 +08:00

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

stiekel

2019-03-25 10:26:02 +08:00

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

@tony601818 多谢。

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

lujinang

2019-03-25 10:29:03 +08:00

bloomfilter

sujin190

2019-03-25 10:41:30 +08:00

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

sujin190

2019-03-25 10:50:51 +08:00

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

stiekel

2019-03-25 19:59:33 +08:00

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