数据结构和算法分析读书Data Structures and Algorithm

用布隆过滤器实现网页爬虫中的URL去重功能

2022-03-22  本文已影响0人  Sun东辉

网页爬虫是搜索引擎中的非常重要的系统,负责爬取几十亿、上百亿的网页。爬虫的工作原理是,通过解析已经爬取页面中的网页链接,然后再爬取这些链接对应的网页。而同一个网页链接有可能被包含在多个页面中,这就会导致爬虫在爬取的过程中,重复爬取相同的网页。如果你是一名负责爬虫的工程师,你会如何避免这些重复的爬取呢?

最容易想到的方法就是,记录已经爬取的网页链接(也就是 URL),在爬取一个新的网页之前,我们拿它的链接,在已经爬取的网页链接列表中搜索。如果存在,那就说明这个网页已经被爬取过了;如果不存在,那就说明这个网页还没有被爬取过,可以继续去爬取。等爬取到这个网页之后,我们将这个网页的链接添加到已经爬取的网页链接列表了。

那么,如何判断这个网页是否被爬取过呢?

首先,我们需要考虑如何存储已经爬取的网页数据?显然,散列表、红黑树、跳表这些动态数据结构,都能支持快速地插入、查找数据,但是在内存消耗方面,是否可以接受呢?

我们拿散列表来举例。假设我们要爬取 10 亿个网页,为了判重,我们把这 10 亿网页链接存储在散列表中。假设一个 URL 的平均长度是 64 字节,那单纯存储这 10 亿个 URL,需要大约 60GB 的内存空间。因为散列表必须维持较小的装载因子,才能保证不会出现过多的散列冲突,导致操作的性能下降。而且,用链表法解决冲突的散列表,还会存储链表指针。所以,如果将这 10 亿个 URL 构建成散列表,那需要的内存空间会远大于 60GB,有可能会超过 100GB。如果你要采用这样的方案,我建议你同时可以采用分治的思想,用多台机器来存储这十亿网页个网页链接,在数据增长时,只需要加机器和重新调整分治算法,简单实用。

但是,作为一个有追求的工程师,我们应该会考虑,在添加、查询数据的效率以及内存消耗方面,是否还有进一步的优化空间呢?

熟悉散列表的人都知道,在散列表中,添加、查找数据的时间复杂度都是 O(1),但时间复杂度并不能完全代表代码的执行时间。大 O 时间复杂度表示法,会忽略掉常数、系数和低阶,并且统计的对象是语句的频度。不同的语句,执行时间也是不同的。时间复杂度只是表示执行时间随数据规模的变化趋势,并不能度量在特定的数据规模下,代码执行时间的多少。

如果我们用基于链表的方法解决冲突问题呢? 散列表中存储的是 URL,那当查询的时候,通过哈希函数定位到某个链表之后,我们还需要依次比对每个链表中的 URL。这个操作是比较耗时的,主要有两点原因。

对于内存消耗方面的优化,除了刚刚这种基于散列表的解决方案,貌似没有更好的法子了。实际上,如果要想内存方面有明显的节省,那就得换一种解决方案,也就是我们今天要着重讲的这种存储结构,布隆过滤器(Bloom Filter)。

布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。

简单来说,布隆过滤器本身是基于位图的,是对位图的一种改进。我们都知道,通过编程语言中提供的数据类型,比如 int、long、char 等类型,通过位运算,可以将其中的某个位表示为某个数字。同时,位图可以通过数组下标来定位数据,所以,访问效率非常高。而且,每个数字用一个二进制位来表示,在数字范围不大的情况下,所需要的内存空间非常节省。

回到最初的问题,用布隆过滤器来记录已经爬取过的网页链接,需要判重的网页有 10 亿,那我们可以用一个 10 倍大小的位图来存储,也就是 100 亿个二进制位,换算成字节,那就是大约 1.2GB。之前我们用散列表判重,需要至少 100GB 的空间。相比来讲,布隆过滤器在存储空间的消耗上,降低了非常多。

布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数 将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。

什么意思呢?就是说布隆过滤器面对二进制大小的位图,会通过哈希函数,对数字进行处理,让它落在一个范围内。比如我们把哈希函数设计成 f(x)=x%n。其中,x 表示数字,n 表示位图的大小,也就是,对数字跟位图的大小进行取模求余。我们都知道,哈希函数肯定会存在冲突的问题,为了降低这种冲突概率,当然我们可以设计一个复杂点、随机点的哈希函数。除此之外,还有其他方法吗?我们来看布隆过滤器的处理方法。既然一个哈希函数可能会存在冲突,那用多个哈希函数一块儿定位一个数据,是否能降低冲突的概率呢?我来具体解释一下,布隆过滤器是怎么做的。

我们使用 K 个哈希函数,对同一个数字进行求哈希值,那会得到 K 个不同的哈希值,我们分别记作 X_1,X_2,X_3,…,X_K。我们把这 K 个数字作为位图中的下标,将对应的 BitMap[X_1],BitMap[X_2],BitMap[X_3],…,BitMap[X_K]都设置成 true,也就是说,我们用 K 个二进制位,来表示一个数字的存在。当我们要查询某个数字是否存在的时候,我们用同样的 K 个哈希函数,对这个数字求哈希值,分别得到 Y_1,Y_2,Y_3,…,Y_K。我们看这 K 个哈希值,对应位图中的数值是否都为 true,如果都是 true,则说明,这个数字存在,如果有其中任意一个不为 true,那就说明这个数字不存在。

对于两个不同的数字来说,经过一个哈希函数处理之后,可能会产生相同的哈希值。但是经过 K 个哈希函数处理之后,K 个哈希值都相同的概率就非常低了。尽管采用 K 个哈希函数之后,两个数字哈希冲突的概率降低了,但是,这种处理方式又带来了新的问题,那就是容易误判。

布隆过滤器的误判有一个特点,那就是,它只会对存在的情况有误判。如果某个数字经过布隆过滤器判断不存在,那说明这个数字真的不存在,不会发生误判;如果某个数字经过布隆过滤器判断存在,这个时候才会有可能误判,有可能并不存在。不过,只要我们调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例,那就可以将这种误判的概率降到非常低。

尽管布隆过滤器会存在误判,但是,这并不影响它发挥大作用。很多场景对误判有一定的容忍度。比如我们今天要解决的爬虫判重这个问题,即便一个没有被爬取过的网页,被误判为已经被爬取,对于搜索引擎来说,也并不是什么大事情,是可以容忍的,毕竟网页太多了,搜索引擎也不可能 100% 都爬取到。

最后,我们来看一下,布隆过滤器,在执行效率方面,是否比散列表更加高效呢?

布隆过滤器用多个哈希函数对同一个网页链接进行处理,CPU 只需要将网页链接从内存中读取一次,进行多次哈希计算,理论上讲这组操作是 CPU 密集型的。而在散列表的处理方式中,需要读取散列值相同(散列冲突)的多个网页链接,分别跟待判重的网页链接,进行字符串匹配。这个操作涉及很多内存数据的读取,所以是内存密集型的。我们知道 CPU 计算可能是要比内存访问更快速的,所以,理论上讲,布隆过滤器的判重方式,更加快速。

这里还需要考虑到扩容的问题。布隆过滤器的误判率,主要跟哈希函数的个数、位图的大小有关。当我们往布隆过滤器中不停地加入数据之后,位图中不是 true 的位置就越来越少了,误判率就越来越高了。所以,对于无法事先知道要判重的数据个数的情况,我们需要支持自动扩容的功能。

当布隆过滤器中,数据个数与位图大小的比例超过某个阈值的时候,我们需要重新申请一个新的位图。后面来的新数据,会被放置到新的位图中。但是,如果我们要判断某个数据是否在布隆过滤器中已经存在,我们就需要查看多个位图,相应的执行效率就降低了一些。

位图、布隆过滤器应用如此广泛,很多编程语言都已经实现了。比如 Java 中的 BitSet 类就是一个位图,Redis 也提供了 BitMap 位图类,Google 的 Guava 工具包提供了 BloomFilter 布隆过滤器的实现。如果你感兴趣,可以去研究下这些实现的源码,一定会有意想不到的收获。

上一篇下一篇

猜你喜欢

热点阅读