Question

去重一般的情况是对URL进行去重，也就说我们访问过的页面下次不再访问。但是也有一些情况，例如贴吧和论坛等社交网站，同一个URL，由于用户评论的存在，页面内容是一直变化的，如果想抓取评论内容，那就不能以URL为去重标准，但是本质上都可以看做是针对字符串的去重方式。

对于爬虫来说，由于网络间的链接错综复杂，爬虫在网络间爬行很可能会形成“环”，这对爬虫来说是非常可怕的事情，会一直做无用功。为了避免形成“环”，就需要知道Spider已经访问过哪些URL，基本上有如下几种方案：

1）关系型数据库去重。

2）缓存数据库去重。

3）内存去重。

首先讲解一下前两种方案：

·关系型数据库去重，需要将URL存入到数据库中，每来一个URL就启动一次数据库查询，数据量变得非常庞大后关系型数据库查询的效率会变得很低，不推荐。

·缓存数据库，比如现在比较流行的Redis，去重方式是使用其中的Set数据类型，类似于Python中的Set，也是一种内存去重方式，但是它可以将内存中的数据持久化到硬盘中，应用非常广泛，推荐。

对于第三种“内存去重”方案，还可以细分出三种不同的实现方式：

·将URL直接存储到HashSet中，也就是Python中的Set数据结构中，但是这种方式最明显的缺点是太消耗内存。随着URL的增多，占用的内存会越来越多。大家可以计算一下假如存储了1亿个链接，每个链接平均40个字符，这就占用了4G内存。

·将URL经过MD5或者SHA-1等单向哈希算法生成摘要，再存储到HashSet中。由于字符串经过MD5处理后的信息摘要长度只有128位，SHA-1处理后也只有160位，所以占用的内存将比第一种方式小很多倍。

·采用Bit-Map方法，建立一个BitSet，将每个URL经过一个哈希函数映射到某一位。这种方式消耗内存是最少，但缺点是单一哈希函数发生冲突的概率太高，极易发生误判。

内存去重方案的这三种实现方式各有优缺点，但是对于整个内存去重方案来说，比较致命的是内存大小的制约和掉电易丢失的特性，万一服务器宕机了，所有内存数据将不复存在。

通过对以上去重方式的分析，我们可以确定相对比较好的方式是内存去重方案+缓存数据库，更准确地说是内存去重方案的第二种实现方式+缓存数据库，这种方式基本上可以满足大多数中型爬虫的需要。但是本章要讲的不是针对百万级和千万级数据量的去重方案，而是当数据量上亿甚至几十亿时这种海量数据的去重方案，这就需要用到BloomFilter算法。