python爬虫入门-05-URL去重

less than 1 minute read

本期我们来聊聊URL去重那些事儿。以前我们曾使用Python的字典来保存抓取过的URL,目的是将重复抓取的URL去除,避免多次抓取同一网页。爬虫会将待抓取的URL放在todo队列中,从抓取到的网页中提取到新的URL,在它们被放入队列之前,首先要确定这些新的URL是否被抓取过,如果之前已经抓取过了,就不再放入队列。

有别于单机系统,在分布式系统中,这些URL应该存放在公共缓存中,才能让多个爬虫实例共享,我们继续使用Redis缓存这些数据。URL既可以存储在Redis的Set数据结构中,也可以将URL作为Key存储为Redis的String类型。至于这两种方案各有什么优缺点,就留给读者自己去思考了

直接存储URL

将URL以字符串的形式直接存储到内存中。保守估计一下URL的平均长度是100字节,那么1亿个URL所占的内存是: 100000000 * 0.0001MB = 10000MB,约等于10G。这也不是不能用,占用的空间再大都能通过扩容来解决。

问题是,如果一个服务器存不下这么多URL该怎么办呢?其实也简单,明确每台服务器的分工,也就是说得到一个URL就知道要交给哪台服务器存储,每台服务器只存储一类URL,比较简单的实现方式就是对URL先哈希再取模。虽然能用,但还是有很大优化空间的。

存储消息摘要

MD5是一个消息摘要算法,它的用途很广泛,我们这里用它来压缩URL。

消息摘要算法的特点:

无论输入的消息有多长,计算出来的消息摘要的长度总是固定的。 只要输入的消息不同,对其进行摘要以后产生的摘要消息也必不相同;但相同的输入必会产生相同的输出。 消息摘要是单向、不可逆的。只能进行正向的信息摘要,而无法从摘要中恢复出任何的原始消息。 以上特点说明我们可以通过存储URL的MD5来实现去重功能,因为不同的URL,MD5不同,相同的URL,MD5相同嘛。

以前我们要存的URL是这样的:http://news.baidu.com/ns?ct=1&rn=20&ie=utf-8&bs=%E4%BA%AC%E4%B8%9C%E9%87%91%E8%9E%8D&rsv_bp=1&sr=0&cl=2&f=8&prevct=no&tn=news&word=%E4%BA%AC%E4%B8%9C%E9%87%91%E8%9E%8D&rsv_sug3=1&rsv_sug4=6&rsv_sug1=1&rsv_sug=1

对应的MD5值是这样的:d552b0b40e21d06d73a1a0938635eb1a

怎么样?省了不少空间吧?

有人说,拓海你不要骗我,这个算法的输入是个无穷集合,而输出是一个有限集合,必然会存在碰撞的,也就是存在不同的URL算出相同的MD5。这会导致去重时误判,少抓数据!

好吧,从理论上来说,必然会出现这种情况。可是出现这种情况的概率是多少呢?下面就算算两个不同URL产生相同消息摘要的概率。

以下是三种常见的消息摘要算法,分别是32、64、128字节,每个字节是十六进制数字的字符,它们的可能值数量分别是:

md5: 16^32 = 2^128 = 3.4 * 10^38

sha256: 16^64 = 2^256 = 1.2 × 10^77

sha512: 16^128 = 2^512 = 1.3 × 10^154

可见,不同URL产生相同消息摘要的可能性非常小,简直像大海捞针。。。不是,简直像宇宙中捞原子一样难,所以就放心使用吧。

消息摘要实现了对URL的压缩,但压缩后的大小还是和原来在一个数量级,空间效率并没有质的提升。有没有办法只用几个bit来唯一标识一个URL呢?有!布隆过滤器就是专门解决这类问题的

布隆过滤器

Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。

它的原理很简单,首先需要准bit数组(所有位初始化为0)和k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明存在,否则不存在。很明显这个过程并不保证查找的结果是100%正确的。

如何根据输入元素个数n,确定bit数组m的大小及hash函数个数呢?当hash函数个数k=(ln2)(m/n)时错误率最小。在错误率不大于E的情况下,m至少要等于nlg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应该>=nlg(1/E)*lge ,大概就是nlg(1/E)的1.44倍。假设错误率为0.01,则此时m应是n的13倍。这样k大概是8个。

下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时,Bloom Filter是一个包含m位的位数组,每一位都置为0。

为了表达S={x1, x2,…,xn}这样一个n个元素的集合,Bloom Filter使用k个相互独立的哈希函数(Hash Function),它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x,第i个哈希函数映射的位置hi(x)就会被置为1(1≤i≤k)。注意,如果一个位置多次被置为1,那么只有第一次会起作用,后面几次将没有任何效果。在下图中,k=3,且有两个哈希函数选中同一个位置(从左边数第五位)。   

在判断y是否属于这个集合时,我们对y应用k次哈希函数,如果所有hi(y)的位置都是1(1≤i≤k),那么我们就认为y是集合中的元素,否则就认为y不是集合中的元素。下图中y1就不是集合中的元素。y2或者属于这个集合,或者刚好是一个false positive。

关于bloom算法,更多详情请参考 传送门