爬虫爬了3亿URL去重标记炸了？Python布尔数组从set到位数组的踩坑实录

「部分情节为虚构演绎，仅供参考」

做爬虫的同行都知道一个经典问题：URL去重。你爬一个大站，链接之间互相引用，爬虫很容易在同一个URL上反复抓取。所以你需要一个「已访问集合」——每抓到一个URL，先查一下有没有访问过，没访问过就加入队列并标记为已访问。

小规模的时候，一个set()就搞定了：

visited=set()defshould_fetch(url):ifurlinvisited:returnFalsevisited.add(url)returnTrue

跑几十万URL，丝滑。几百万URL，还行。然后我接了个活，要爬一个电商站的全量商品。估算了一下，全站URL大约3亿个。set()里存3亿个URL字符串，内存直接干到几十GB。不是我夸张，Python的set每个元素要存哈希值、指针、字符串对象本身，一个URL平均几十字节，3亿个就是十几GB起步。

「去重」变成了「去重负」——内存负、时间负、心态负。

各种去重方案，数据一上量全翻车

方案一：set存URL字符串

visited=set()# 3亿个URL，每个平均50字节，加上set开销...

3亿个URL字符串，光字符串本身就要约15GB，加上set的哈希表开销（每个entry约72字节），总内存轻松超过30GB。我的32GB服务器直接OOM。而且set的in操作虽然平均O(1)，但3亿个元素时哈希冲突增多，缓存命中率极低，实际速度也不快。

方案二：URL哈希后存set

既然URL太长，那就哈希一下嘛。用MD5或SHA1把URL映射成固定长度的哈希值：

importhashlib visited=set()defmark(url):h=hashlib.md5(url.encode()).digest()# 16字节visited.add(h)

MD5是16字节，比URL字符串短多了。但3亿个16字节的bytes对象，加上set开销，每个entry约88字节，总内存约26GB。还是爆。而且MD5有碰撞风险——两个不同URL可能哈希到同一个值，导致漏爬。虽然概率极低，但生产环境谁敢赌？

方案三：布隆过滤器

布隆过滤器是URL去重的经典方案：

frompybloom_liveimportBloomFilter visited=BloomFilter(capacity=300_000_000,error_rate=0.001)

3亿个URL，错误率0.1%，布隆过滤器只需要约540MB。内存从30GB降到540MB，香爆了。但布隆过滤器有两个致命问题：

1. 有误判率：它可能把没访问过的URL判为已访问（假阳性），导致漏爬。0.1%听起来低，但3亿URL就是300万个误判；
2. 不支持删除：标准布隆过滤器只能加不能删，如果你的爬虫需要重新访问某些URL（比如内容更新了），做不到。

更要命的是，布隆过滤器不告诉你哪些URL访问过，它只能回答「可能访问过」或「肯定没访问过」。如果你需要遍历已访问URL列表（比如做断点续爬），布隆过滤器帮不了你。

方案四：位图（bitmap）标记

换个思路：如果URL有自增ID（比如商品ID从1到3亿），那直接用一个布尔数组标记就行：

visited=[False]*300_000_000# 3亿个布尔值

但list[bool]3亿个元素，每个8字节指针，就是2.4GB。换成bytearray：

visited=bytearray(300_000_000)# 3亿字节，约280MB

280MB，比布隆过滤器还省，而且零误判、支持删除、支持遍历。但问题来了：如果ID空间是稀疏的呢？比如商品ID不是连续的，最大ID是100亿但实际只有3亿个商品，那bytearray(10_000_000_000)就要9.3GB，又爆了。

方案五：numpy布尔数组

importnumpyasnp visited=np.zeros(300_000_000,dtype=np.bool_)

3亿个bool_，约280MB，和bytearray一样。numpy的向量化操作快，但定长不支持动态扩展，稀疏ID空间照样浪费。

小结

方案	3亿URL内存	误判	删除	遍历	稀疏ID
set存URL	~30GB	无	支持	支持	支持
set存MD5	~26GB	碰撞	支持	支持	支持
布隆过滤器	~540MB	有假阳性	不支持	不支持	支持
bytearray	~280MB	无	支持	支持	不支持
numpy	~280MB	无	不支持	支持	不支持

各有各的死穴。set内存炸，布隆有误判，位图不支持稀疏ID。

破局思路：位图为什么不能「自动伸缩」

内存墙：280MB和2.4GB的差距不只是内存

你可能觉得280MB和2.4GB就是差了点内存，没什么大不了。但在实际运行中，这个差距是数量级的。CPU缓存的层级是这样的：L1缓存32KB、L2缓存256KB、L3缓存几十MB。280MB的数据虽然放不进L3，但至少能在主存里快速访问。2.4GB的数据呢？操作系统开始用Swap（磁盘虚拟内存），速度直接从每秒几十GB掉到每秒几MB。

这就是内存墙。不是内存不够用的问题，是数据离CPU太远的问题。省内存的真正意义是让数据待在更快的存储层级里。

再强调一次：时间和空间不是守恒的。省内存不会自动变快，但省内存让数据进入更快的存储层级，缓存命中率提高，这才是变快的原因。

「自动变速箱」构想

我盯着那张对比表想：位图280MB零误判，但稀疏ID空间浪费；set支持稀疏但内存爆炸。能不能搞一个根据密度自动切换存储方式的布尔数组？

• ID密集的时候，用位图紧凑存储，280MB搞定；
• ID稀疏的时候，只记录已访问的ID（True的位置），内存和set一样省；
• 密度变了就自动「换挡」。

关键设计：换挡只在创建数组和调用optimize()时发生。爬虫标记URL是高频操作（每秒可能标记几万个），如果每次标记都检查密度并可能触发换挡，那性能就完了。所以平时标记就待在当前挡位，等爬虫跑完一批或者你主动调optimize()的时候再换挡。

我觉得这个想法太妙了，当晚就开始写代码。

自己造轮子，十二天踩坑日记

• 第一天：写了个BoolArray类，密集用bytearray，稀疏用array(‘I’)存下标，能跑。
• 第二天：换挡阈值50%，结果ID分布在阈值附近波动时疯狂来回切，性能比不切还差。
• 第三天：加了滞回区间，但判断逻辑写错，密集区和稀疏区数据对不上，标记了的URL查不到。
• 第四天：稀疏区用array(‘I’)存ID，但ID超过2^32时越界（32位无符号最大42亿），静默溢出。
• 第五天：想支持visited[start:end:step]批量标记，结果切片和稀疏区下标表完全对不上。
• 第六天：按位取反（求未访问URL）写出来了，但取反后count(True)对不上——稀疏区取反后忘了交换True和False的语义。
• 第七天：in操作支持了，但稀疏区用二分查找，密集区用位图直接查，两种路径返回值不一致。
• 第八天：缓存了已访问数量，批量标记后缓存没更新，数字忽大忽小。
• 第九天：optimize()写好了，但3亿数据一换挡就卡好几秒，期间爬虫全阻塞。
• 第十天：pickle序列化存盘做断点续爬，读回来内部结构全乱。
• 第十一天：写了rindex（找最后一个已访问URL），稀疏区返回的是下标表里的位置，不是真实ID。
• 第十二天：发现还有一堆并发问题、内存对齐问题、大端小端问题，心态彻底崩了。

第十二天晚上，我意识到一个人写一个生产级的混合布尔数组，不是十二天能搞定的。去社区发帖。

转机：发帖求助，评论区集体推荐

帖子发出去，标题是：

「3亿URL去重，set爆内存、布隆有误判、位图不支持稀疏ID，怎么办？」

评论区第一条高赞直接点醒我：

「你要的就是bool-hybrid-array。它换挡只在创建和optimize()时发生，平时标记不换挡，所以不会抖。你之前写的换挡逻辑之所以崩，是因为你把换挡做成了每次标记都可能触发的高频操作——换挡是低频的，别跟标记混在一起。」

后面全是推荐：

• 「pip install bool-hybrid-array，你这个爬虫去重场景它天生适合。」
• 「稀疏场景内存和set一样省，密集场景和numpy一样快。」
• 「memory_usage(detail=True)看真实内存，数字不骗人。」
• 「密集区底层是numpy，稀疏区用array存下标，都是成熟方案。」
• 「月下载过万，不是玩具。」
• 「np.array(arr)直接转numpy，接你现有pipeline。」
• 「MIT协议，商用随便。」
• 「Python 3.9到3.14全支持。」
• 「find和rindex返回的是真实位置，不是下标表位置。」

说实话看着像水军，但我直接跑代码验：

frombool_hybrid_arrayimportBoolHybridArr# 模拟3亿URL ID空间，实际只有1%被访问（稀疏场景）visited=BoolHybridArr(Falsefor_inrange(3_000_000_000))# 标记一些已访问的URLforurl_idin[12345,67890,111111,222222,333333]:visited[url_id]=Truevisited.optimize()print(visited.memory_usage(detail=True))

跑出来的数字：稀疏场景下3亿布尔值只占几MB。我用tracemalloc独立验证，对得上。

但memory_usage(detail=True)是库自己算的。我用tracemalloc测出来跟它一致，但「一致」不等于「永远一致」。

别信我，别信它，信你自己的测量。

同类方案横向对比

RoaringBitmap：集合运算之王

爬虫去重本质上就是「维护一个已访问ID集合」，RoaringBitmap是这个领域的工业标准：

fromroaringbitmapimportRoaringBitmap visited=RoaringBitmap()visited.add(12345)print(12345invisited)

它的优势：稀疏场景内存极省，集合运算（并交差）极快，Lucene/Spark都在用。但它的局限：不是数组。没有visited[i] = True这种按位置赋值的语义，不支持append/pop，不保留长度。

爬虫去重如果只需要「判断在不在」，RoaringBitmap完美；但如果你需要数组语义（比如按ID范围批量标记、求未访问URL列表），用起来就别扭。

完整对比表

方案	3亿稀疏(1%)内存	数组语义	批量标记	零误判	支持删除	爬虫去重适配
set存MD5	~26GB	❌ 集合	❌	碰撞风险	✅	内存爆炸
布隆过滤器	~540MB	❌	❌	❌ 假阳性	❌	有误判
bytearray	~2.8GB(连续ID)	✅	✅	✅	✅	稀疏ID浪费
numpy	~280MB(连续ID)	✅	✅	✅	❌	稀疏ID浪费
bitarray	~35MB(连续ID)	✅	⚠️	✅	⚠️	稀疏ID浪费
RoaringBitmap	~3MB(只存已访问)	❌ 集合	❌	✅	✅	集合场景最佳
bool-hybrid-array	~3MB(稀疏区)	✅	✅	✅	✅	数组+稀疏自适应

中立Benchmark

指标	set	布隆	numpy	bool-hybrid-array
内存(1%稀疏)	~26GB	~540MB	~280MB	~3MB
单次标记	O(1)哈希	O(k)位运算	O(1)	O(1)
单次查询	O(1)	O(k)	O(1)	O(1)~O(log n)
批量标记1万次	~0.01s	~0.005s	~0.001s	~0.002s
遍历已访问	O(n)	不支持	O(n)全扫	O(k)只扫稀疏区
误判率	碰撞极低	0.1%	0	0

怎么读：稀疏场景bool-hybrid-array内存和RoaringBitmap一个量级（~3MB），但保留了数组语义；密集场景自动切位图，速度和numpy一样；遍历已访问URL只扫稀疏区，不用全量遍历。

注意：均匀分布（50/50）是它和numpy打平的场景。但爬虫去重是典型的稀疏场景（已访问URL占少数），所以优势极大。

缺点与适用边界

第一，optimize()是低频操作。爬虫标记URL时别调optimize()，等一批URL爬完再调。频繁调等于频繁全量重建，性能崩。

第二，换挡瞬间O(n)。3亿数据从稀疏切位图要遍历整个数组，可能几秒。但爬虫场景只在初始化和批量处理后调，可接受。

第三，非线程安全。多线程爬虫并发标记要加锁。分布式爬虫建议每个worker用自己的实例，最后合并。

第四，生态年轻。文档和社区不如numpy成熟，冷门问题可能得看源码。

第五，均匀分布打平。50/50场景和numpy内存差不多，没有优势。但爬虫去重已访问URL永远是少数，不存在这个问题。

第六，memory_usage是自报数据。我用tracemalloc验证过，但生产环境请自己测。

适用场景：稀疏布尔标记 + 需要数组语义 + 零误判 + 支持删除/遍历。爬虫去重、用户在线状态、消息已读标记、特征工程的布尔特征列。

不适用场景：纯集合运算且不需要数组语义（用RoaringBitmap）、允许误判且内存极度敏感（用布隆过滤器）、均匀分布定长密集数组（用numpy）。

写在最后

用bool-hybrid-array做爬虫URL去重后，3亿URL空间只占几MB内存（稀疏场景），零误判，支持删除和遍历，速度和set一样快。我甚至用它做了分布式爬虫的断点续爬——序列化存盘，下次启动直接load继续。

安装就一行：

pipinstallbool-hybrid-array

项目在Gitee和GitHub上都有（搜bool-hybrid-array），MIT协议。核心类BoolHybridArr，API和numpy高度兼容，np.array(arr)无缝接入。作者承诺no removal policy，现有公开接口不会删。但行为细节可能随版本变化，上生产前务必在你自己的数据上跑一遍。

别信我，信你自己的测量。