京公网安备11010502063487号爬虫要判断一个 URL 抓过没有,最直接的是放进 set,最省内存的是 Bloom 过滤器。两者差多少、代价是什么?这篇用 100 万个 URL 实测内存、误判率,以及容量估计错了会怎样。
结构 内存 平均每个 URL set 里存完整 URL 字符串 128.0 MiB 134.2 字节 (构建 1.7 秒,集合里 1,000,000 个元素) set 里存 16 字节 MD5 摘要 78.7 MiB 82.6 字节 (构建 3.0 秒,集合里 1,000,000 个元素) set 里存 64 位整数哈希 66.3 MiB 69.5 字节 (构建 3.9 秒,集合里 1,000,000 个元素) set 里存 32 位整数(crc32) 62.5 MiB 65.5 字节 (构建 3.2 秒,集合里 999,873 个元素) Bloom 过滤器(目标误判率 1%,m=9,585,058 位,k=7) 1.1 MiB 1.20 字节 (构建 2.1 秒) Bloom 过滤器(目标误判率 0.1%,m=14,377,587 位,k=10) 1.7 MiB 1.80 字节 (构建 2.6 秒)
100 万个 URL 放进 set 要 128.0 MiB;把 URL 换成 MD5 摘要 78.7 MiB,换成 64 位整数还要 66.3 MiB——Python 的 set 加整数对象每个元素就有约 65 字节的开销。Bloom 过滤器 1% 误判率只要 1.1 MiB,0.1% 要 1.7 MiB。
Bloom(目标 1%):实测误判 1.036%(按公式 (1-e^(-kn/m))^k 的理论值 1.004%),2073 / 200,000 个没见过的 URL 被误认为"已抓过" Bloom(目标 0.1%):实测误判 0.109%(按公式 (1-e^(-kn/m))^k 的理论值 0.100%),218 / 200,000 个没见过的 URL 被误认为"已抓过" set 里存 32 位 crc32:实测误判 0.021%(粗略预期 n / 2^32 = 0.023%) set 里存 64 位哈希:实测误判 0.0000%(粗略预期 n / 2^64 ≈ 0) set 里存完整 URL:实测误判 0.000%(精确集合没有误判)
Bloom 实测误判 1.036%,和理论公式 1.004% 吻合。对爬虫来说,误判不是“多抓一次”,而是“这个 URL 没抓过却被当作抓过,永远不会被抓”——是漏抓。用 32 位哈希放进 set 同样有这个问题:100 万个里就有 127 个撞车;64 位哈希在这个规模下没有观察到。
已加入 理论误判 实测误判 1,000,000 1.004% 1.000% 2,000,000 15.745% 15.737% 3,000,000 43.604% 43.646%
过滤器按 100 万个、1% 设计,装到 200 万个误判率变成 15.7%,300 万个 43.6%,与公式吻合。爬虫事先不知道总量时,要么按上限预留,要么用可扩展的 Bloom(分层增长),本文没有测后者。
生成 URL 字符串本身:3738 千次/秒;set 查询(含生成):2400 千次/秒;Bloom 查询(含生成,k=7,纯 Python):480 千次/秒
我这份纯 Python 的 Bloom 查询 480 千次/秒,比 set 的 2400 千次/秒慢约 5 倍;速度对一个受网络限制的爬虫通常不是瓶颈,内存才是。