爬虫课堂（十四）|URL的去重方法

所谓的URL去重，就是爬虫将重复抓取的URL去除，避免多次抓取同一网页。爬虫一般会将待抓取的URL放在一个队列中，从抓取后的网页中提取到新的URL，在他们被放入队列之前，首先要确定这些新的URL没有被抓取过，如果之前已经抓取过了，就不再放入队列。

URL的去重方法有很多种，从次到优依次可以分为以下5种：

1、将URL保存到数据库进行去重（假设单个URL的平均长度是100 byte）。

2、将URL放到HashSet中去重（一亿条占用10G内存）。

3、将URL经过MD5之后保存到HashSet（MD5的结果是128 bit也就是16 byte的长度，一亿条占用1.6G的内存，Scrapy采用的就是类似方法）。

4、使用Bitmap或Bloomfilter方法去重（URL经过hash后映射到bit的每一个位上，一亿URL占用约12M，问题是存在冲突）。

去重方法介绍

一、将URL保存到数据库进行去重

为了尽快把整个爬虫搭建起来，最开始的URL去重采用方案是直接利用数据库的唯一约束进行去重，这是最省时的做法，所有人都能想得到和做到。

二、将URL放到HashSet中去重

在数据库中去重，每次比较都有一次请求数据库的过程，这里对数据库的性能消耗是很大的。于是可以使用将URL放到内存中的HashSet中去重，HashSet中放置的就是URL的字符串，任何一个新的URL首先在HashSet中进行查找，如果HashSet中没有，就将新的URL插入HashSet，并将URL放入待抓取队列。 

这个方案的好处是它的去重效果精确，不会漏过一个重复的URL。它的缺点是，随着数据的增加会出现Out Of Memory。

假设单个URL的平均长度是100 byte，那么一亿条数据占用10G内存，大部分的电脑内存在4G和8G，那么留给JVM的内存就更少啦，那么出现内存泄漏是迟早的事。

3、将URL经过MD5之后保存到HashSet

迟早到底有多早呢？也许是一个月，那么我们可以把这一个月扩展到半年。

这里的处理方式就是HashSet中不存储原始的URL，而是将URL压缩后再放进去。压缩的方式有很大，用MD5对URL做编码是比较省时的一种方式。 

MD5的结果是128 bit也就是16 byte的长度，相比于之间估计的URL平均长度100byte已经缩小了6倍多，一亿条数据占用1.6G的内存，Scrapy采用的就是类似方法。

当然，不管使用那种压缩算法，随着URL越来越多，终有一天还是会Out Of Memory。所以，这个方案不解决本质问题。 

MD5另外一个问题是，有可能两个相同的URL被映射成同一个MD5值，这样的话，它们中有一个就永远不会被抓取了。

4、使用Bitmap方法去重

使用Bitmap方法去重的原理是把URL经过hash后映射到bit的每一个位上，一亿URL占用约12M，主要缺点是去重没那么精准，存在冲突。

总结

关于1、2、3我是有实践过，4的话没有实践，同时为了解决内存的问题，现在也可以使NoSQL的方案去解决，具体的没有操作过就不多讲啦。

不过我们马上就要去实践啦，回头我把实践的结果再同步到这篇文章中来，欢迎关注。