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

「部分情节为虚构演绎仅供参考」做爬虫的同行都知道一个经典问题URL去重。你爬一个大站链接之间互相引用爬虫很容易在同一个URL上反复抓取。所以你需要一个「已访问集合」——每抓到一个URL先查一下有没有访问过没访问过就加入队列并标记为已访问。小规模的时候一个set()就搞定了visitedset()defshould_fetch(url):ifurlinvisited:returnFalsevisited.add(url)returnTrue跑几十万URL丝滑。几百万URL还行。然后我接了个活要爬一个电商站的全量商品。估算了一下全站URL大约3亿个。set()里存3亿个URL字符串内存直接干到几十GB。不是我夸张Python的set每个元素要存哈希值、指针、字符串对象本身一个URL平均几十字节3亿个就是十几GB起步。「去重」变成了「去重负」——内存负、时间负、心态负。各种去重方案数据一上量全翻车方案一set存URL字符串visitedset()# 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 visitedset()defmark(url):hhashlib.md5(url.encode()).digest()# 16字节visited.add(h)MD5是16字节比URL字符串短多了。但3亿个16字节的bytes对象加上set开销每个entry约88字节总内存约26GB。还是爆。而且MD5有碰撞风险——两个不同URL可能哈希到同一个值导致漏爬。虽然概率极低但生产环境谁敢赌方案三布隆过滤器布隆过滤器是URL去重的经典方案frompybloom_liveimportBloomFilter visitedBloomFilter(capacity300_000_000,error_rate0.001)3亿个URL错误率0.1%布隆过滤器只需要约540MB。内存从30GB降到540MB香爆了。但布隆过滤器有两个致命问题有误判率它可能把没访问过的URL判为已访问假阳性导致漏爬。0.1%听起来低但3亿URL就是300万个误判不支持删除标准布隆过滤器只能加不能删如果你的爬虫需要重新访问某些URL比如内容更新了做不到。更要命的是布隆过滤器不告诉你哪些URL访问过它只能回答「可能访问过」或「肯定没访问过」。如果你需要遍历已访问URL列表比如做断点续爬布隆过滤器帮不了你。方案四位图bitmap标记换个思路如果URL有自增ID比如商品ID从1到3亿那直接用一个布尔数组标记就行visited[False]*300_000_000# 3亿个布尔值但list[bool]3亿个元素每个8字节指针就是2.4GB。换成bytearrayvisitedbytearray(300_000_000)# 3亿字节约280MB280MB比布隆过滤器还省而且零误判、支持删除、支持遍历。但问题来了如果ID空间是稀疏的呢比如商品ID不是连续的最大ID是100亿但实际只有3亿个商品那bytearray(10_000_000_000)就要9.3GB又爆了。方案五numpy布尔数组importnumpyasnp visitednp.zeros(300_000_000,dtypenp.bool_)3亿个bool_约280MB和bytearray一样。numpy的向量化操作快但定长不支持动态扩展稀疏ID空间照样浪费。小结方案3亿URL内存误判删除遍历稀疏IDset存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稀疏的时候只记录已访问的IDTrue的位置内存和set一样省密度变了就自动「换挡」。连续密集稀疏分散URL IDID密度判断位图模式bytearray稀疏模式array存已访问ID统一数组APIvisited[i]访问/标记关键设计换挡只在创建数组和调用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(detailTrue)看真实内存数字不骗人。」「密集区底层是numpy稀疏区用array存下标都是成熟方案。」「月下载过万不是玩具。」「np.array(arr)直接转numpy接你现有pipeline。」「MIT协议商用随便。」「Python 3.9到3.14全支持。」「find和rindex返回的是真实位置不是下标表位置。」说实话看着像水军但我直接跑代码验frombool_hybrid_arrayimportBoolHybridArr# 模拟3亿URL ID空间实际只有1%被访问稀疏场景visitedBoolHybridArr(Falsefor_inrange(3_000_000_000))# 标记一些已访问的URLforurl_idin[12345,67890,111111,222222,333333]:visited[url_id]Truevisited.optimize()print(visited.memory_usage(detailTrue))跑出来的数字稀疏场景下3亿布尔值只占几MB。我用tracemalloc独立验证对得上。但memory_usage(detailTrue)是库自己算的。我用tracemalloc测出来跟它一致但「一致」不等于「永远一致」。别信我别信它信你自己的测量。同类方案横向对比RoaringBitmap集合运算之王爬虫去重本质上就是「维护一个已访问ID集合」RoaringBitmap是这个领域的工业标准fromroaringbitmapimportRoaringBitmap visitedRoaringBitmap()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布隆numpybool-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%00怎么读稀疏场景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-arrayMIT协议。核心类BoolHybridArrAPI和numpy高度兼容np.array(arr)无缝接入。作者承诺no removal policy现有公开接口不会删。但行为细节可能随版本变化上生产前务必在你自己的数据上跑一遍。别信我信你自己的测量。