2 亿条数据去重内存放不下 布隆过滤器 1.5% 误判怎么定

爬虫队列要去重,历史 URL 加起来 2 亿条。机器 24G 内存,但同一台上还有数据库和几个服务,实际能给 8G。最开始用 Python set 存字符串,跑到 6000 万条就被 OOM killer 干掉,RSS 到 19G。每条 URL 平均 78 字节,加上 set 的哈希表和字符串对象头,一条实际要 300 多字节,2 亿条根本装不下。

换成布隆过滤器。误判率 p 和位数组的关系是 m = -n ln p / (ln 2)^2,n 取 2 亿,p 取 1% 时大约 9.6 bit 一条,总共 240MB;p 取 0.1% 要 14.4 bit,360MB。内存不是瓶颈,选哪个看能不能接受漏判。

1% 意味着 2 亿条里约有 200 万条本来没出现过、却被判成已存在。对爬取队列可以接受,漏掉一些页面不影响主流程;对订单号去重就不行,少一单就是事故。这个前提必须先想清楚,再谈参数。

我这边用 RedisBloom 实测,BF.RESERVE 0.01 200000000,插满 2 亿条后拿 1000 万个确定不在集合里的 URL 去试,误判率 1.47%,和理论值接近。插入平均 0.09 ms 一条,2 亿条跑了 5 小时。

from redis import Redis

r = Redis(host='10.0.3.21', port=6379)
r.execute_command('BF.RESERVE', 'url:2026', 0.01, 200000000)
key = 'https://a.example.com/1'
r.execute_command('BF.ADD', 'url:2026', key)
print(r.execute_command('BF.EXISTS', 'url:2026', key))

还有个坑是布隆过滤器不能删元素。我们的 URL 会过期,一年后要允许重新抓,只能按年建 key,查询时查当年和上一年两个过滤器,过期整 key 删掉。用 BF.INFO url:2026 看字节数是 251658240,和按公式估的 240MB 对得上,这个数让我心里有底。

现在的结构是布隆挡第一层,命中的再查磁盘上的 RocksDB。RocksDB 里 2 亿条键值占 11G 磁盘,布隆只负责把 99% 的重复挡在内存里,不做唯一真相。

您可以还会对下面的文章感兴趣: