URL去重与Bloom filter

在爬虫爬网页的时候,需要避免重复抓同一个网页,来提高爬取效率,避免不必要的开销,这就需要使用一些判重的方法。

数据库

一种比较常见的方法是用数据库。这也是实现分布式爬虫去重的一个比较简单的方案。简单来说就是多个爬虫可以共享同一个数据库,把爬过的url写进去,在爬url前从数据库里查询是否已经写入。

持久化问题数据库已经帮忙处理掉了。同样可以使用类似上面的摘要算法对url的数据量进行优化。

优点很明显,可以比较简单的实现多个爬虫的合作任务。缺点同样很明显,随着数据量的增加,去重的效率将越来越低,严重影响爬取的效率。

Hash Table

另一种比较简单的方式是使用哈希表这种数据结构,比如python中使用set,go中使用map。在每次爬取启动时新建一个哈希表,在爬取过程中将爬过的丢进去,后面每次爬一个url的时候先在哈希表里检查一下是否已经存在这个值,如果已经爬过了就直接把任务丢弃掉。

这个方案也可以稍微优化,url一般会比较长,因此可以在存储和检查哈希表的url之前,先通过一个摘要算法处理,比如md5,sha1之类的,来减少需要存储的数据量。

如果需要持久化的话,就需要把这个哈希表dump成文件,下次使用时再load回来。

这种方法实现起来比较简单,使用比较方便,效率也非常高。适合规模比较小的爬取任务。缺点是一旦爬取的任务量太大,内存会吃不消。

可以借助Redis来实现分布式。

Bloom Filter

就是布隆过滤器。刚听说的时候,以为是这东西叫bloom是因为发明者是个文艺青年,后来发现是这个人叫Bloom =。=

Bloom filter实际上是由一个bitmap和若干个哈希函数构成的。它可以用来高速检查一个元素是否可能在集合中,并且空间占用要比上面的方法少很多,但只能向Bloom filter里添加元素,却没法删除,并且随着里面的数据量增大,会有一定程度的误报。因此这是一个用错误率换时间和空间的方法。

它的原理是将一个元素通过k个哈希函数,将元素映射为k个比特位,在bitmap中把它们置为1。在验证的时候只需要验证这些比特位是否都是1即可,如果其中有一个为0,那么元素一定不在集合里,如果全为1,则很可能在集合里。(因为可能会有其它的元素也映射到相应的比特位上)同时这也导致不能从Bloom filter中删除某个元素,无法确定这个元素一定在集合中。以及带来了误报的问题,当里面的数据越来越多,这个可能在集合中的靠谱程度就越来越低。(由于哈希碰撞,可能导致把不属于集合内的元素认为属于该集合)

可以使用这个计算器来计算容量和错误率。

Bloom filter就很适合用来做URL的去重工作,它由于空间占用及查询效率方面的优势,也经常用在垃圾邮件过滤以及数据库查询等场景中。

大部分常用的语言中都有人已经实现了Bloom filter库,可以直接拿来使用。另外在分布式场景下,也可以将Bloom filter与Redis结合使用。

但是还要重新强调一下,Bloom filter是有一定的误报的几率的,只有在不需要太精确判断的场景下才可以使用。

其他杂项

Scrapy框架里存在一个默认开启的去重过滤器:RFPDupeFilter。他通过scrapy.utils.request.request_fingerprint函数生成请求的指纹,对于请求的method,url,body等进行sha1哈希,并进行判重。可以适合关掉或者用其他过滤器进行过滤,也可以通过继承BaseDupeFilter实现自己的过滤器。

传送门