1.去重的应用场景：
如果你只是做一些简单的爬虫，可能不会遇到这种问题，可是如果你正在做一个大型的全站爬虫，或是一个持久化的爬虫，那你一定会遇到这样的问题：刚开始爬虫速度还可以，随着待爬取的队列达到数亿级甚至更多的时候，爬虫会变得非常慢，为什么会出现这样的问题呢？ 我们以scrapy为例来说明并解决这个问题。
2.scrapy去重原理
Scrapy 有自动去重功能，它的去重使用了 Python 中的集合。这个集合记录了 Scrapy 中每个 Request 的指纹，这个指纹实际上就是 Request 的散列值。
在scrapy中发出一个请求时，会有一个参数dont_filter，而scrapy会根据这个参数来判断是否去重。
scrapy 对 request 不做去重很简单，只需要在 request 对象中设置dont_filter为 True。默认是False, 默认是去重，改为True就不去重了。比如说：
yield scrapy.Request(url, callback=self.get_response, dont_filter=True)
那么，scrapy是怎么去重的呢，让我们从源码角度来分析一下scrapy是怎么去重的。我们可以看看 Scrapy 的源代码，如下所示：
核心源代码如下：
import hashlibdef request_fingerprint(request, include_headers=None):if include_headers:include_headers = tuple(to_bytes(h.lower())for h in sorted(include_headers))cache = _fingerprint_cache.setdefault(request, {})if include_headers not in cache:fp = hashlib.sha1()fp.update(to_bytes(request.method))fp.update(to_bytes(canonicalize_url(request.url)))fp.update(request.body or b'')if include_headers:for hdr in include_headers:if hdr in request.headers:fp.update(hdr)for v in request.headers.getlist(hdr):fp.update(v)cache[include_headers] = fp.hexdigest()return cache[include_headers]
request_fingerprint 就是计算 Request 指纹的方法，其方法内部使用的是hashlib的 sha1 方法。然后再使用to_bytes方法，计算的字段包括 Request 的 Method、URL、Body、Headers 这几部分内容，这里只要有一点不同，那么计算的结果就不同。计算得到的结果是加密后的字符串，也就是指纹。
to_bytes方法核心代码如下：
def to_bytes(text, encoding=None, errors='strict'):"""Return the binary representation of `text`. If `text`is already a bytes object, return it as-is."""if isinstance(text, bytes):return textif not isinstance(text, six.string_types):raise TypeError('to_bytes must receive a unicode, str or bytes ''object, got %s' % type(text).__name__)if encoding is None:encoding = 'utf-8'return text.encode(encoding, errors)
每个 Request 都有独有的指纹，指纹就是一个字符串，判定字符串是否重复比判定 Request 对象是否重复容易得多，所以指纹可以作为判定 Request 是否重复的依据。
那么我们如何判定是否重复呢？Scrapy 是这样实现的，如下所示：
class RFPDupeFilter(BaseDupeFilter):"""Request Fingerprint duplicates filter"""def __init__(self):self.fingerprints = set()def request_seen(self, request):fp = self.request_fingerprint(request)if fp in self.fingerprints:return Trueself.fingerprints.add(fp)if self.file:self.file.write(fp + os.linesep)def request_fingerprint(self, request):return request_fingerprint(request)
在去重的类RFPDupeFilter中，有一个request_seen方法，这个方法有一个参数 request，它的作用就是检测该 Request 对象是否重复。这个方法调用 request_fingerprint 获取该 Request 的指纹，检测这个指纹是否存在于 fingerprints 变量中，而 fingerprints 是一个集合，集合的元素都是不重复的。
如果指纹存在，那么就返回 True，说明该 Request 是重复的，否则将这个指纹加入集合中。如果下次还有相同的 Request 传递过来，指纹也是相同的，那么这时指纹就已经存在于集合中，Request 对象就会直接判定为重复。这样去重的目的就实现了。
简单的总结一句话就是，Scrapy 的去重过程就是，利用集合元素的不重复特性来实现 Request 的去重。
参考博客：第47讲：大幅提速，分布式爬虫理念
3.scrapy_redis去重原理
Scrapy 的去重是利用集合来实现的，而scrapy-redis的去重就需要利用共享的集合，只不过是将指纹池储存到了redis中。
核心代码如下：
def request_seen(self, request):fp = self.request_fingerprint(request)# This returns the number of values added, zero if already exists.added = self.server.sadd(self.key, fp)return added == 0def request_fingerprint(self, request):return request_fingerprint(request)
这里同样实现了一个 request_seen 方法，和 Scrapy 中的 request_seen 方法实现极其类似。不过这里集合使用的是 server 对象的 sadd 操作，也就是集合不再是一个简单数据结构了，而是直接换成了数据库的存储方式。
鉴别重复的方式还是使用指纹，指纹同样是依靠 request_fingerprint 方法来获取的。获取指纹之后就直接向集合添加指纹，如果添加成功，说明这个指纹原本不存在于集合中，返回值 1。代码中最后的返回结果是判定添加结果是否为 0，如果刚才的返回值为 1，那这个判定结果就是 False，也就是不重复，否则判定为重复。
这样我们就成功利用 Redis 的集合完成了指纹的记录和重复的验证。
scrapy-redis 重写了 scrapy 的调度器和去重队列，所以需要在 settings 中修改如下两列
# Enables scheduling storing requests queue in redis.SCHEDULER = "scrapy_redis.scheduler.Scheduler"# Ensure all spiders share same duplicates filter through redis.DUPEFILTER_CLASS = "scrapy_redis.dupefilter.RFPDupeFilter"
有关scrapy_redis去重原理详细的介绍，可以看下面这篇博客。
第48讲：分布式利器 Scrapy-Redis 原理
3.Bloom Filter布隆过滤器原理
3.1.了解 BloomFilter
Bloom Filter，中文名称叫作布隆过滤器，是 1970 年由 Bloom 提出的，它可以被用来检测一个元素是否在一个集合中。Bloom Filter 的空间利用效率很高，使用它可以大大节省存储空间。Bloom Filter 使用位数组表示一个待检测集合，并可以快速地通过概率算法判断一个元素是否存在于这个集合中。利用这个算法我们可以实现去重效果。
3.2. BloomFilter 的算法
在 Bloom Filter 中使用位数组来辅助实现检测判断。在初始状态下，我们声明一个包含 m 位的位数组，它的所有位都是 0，如图 所示。
现在我们有了一个待检测集合，我们表示为 S={x1, x2, …, xn}，我们接下来需要做的就是检测一个 x 是否已经存在于集合 S 中。在 BloomFilter 算法中首先使用 k 个相互独立的、随机的哈希函数来将这个集合 S 中的每个元素 x1、x2、…、xn 映射到这个长度为 m 的位数组上，哈希函数得到的结果记作位置索引，然后将位数组该位置索引的位置 1。例如这里我们取 k 为 3，即有三个哈希函数，x1 经过三个哈希函数映射得到的结果分别为 1、4、8，x2 经过三个哈希函数映射得到的结果分别为 4、6、10，那么就会将位数组的 1、4、6、8、10 这五位置 1，如图 所示：
这时如果再有一个新的元素 x，我们要判断 x 是否属于 S 这个集合，我们便会将仍然用 k 个哈希函数对 x 求映射结果，如果所有结果对应的位数组位置均为 1，那么我们就认为 x 属于 S 这个集合，否则如果有一个不为 1，则 x 不属于 S 集合。
例如一个新元素 x 经过三个哈希函数映射的结果为 4、6、8，对应的位置均为 1，则判断 x 属于 S 这个集合。如果结果为 4、6、7，7 对应的位置为 0，则判定 x 不属于 S 这个集合。
注意这里 m、n、k 满足的关系是 m>nk，也就是说位数组的长度 m 要比集合元素 n 和哈希函数 k 的乘积还要大。
这样的判定方法很高效，但是也是有代价的，它可能把不属于这个集合的元素误认为属于这个集合，我们来估计一下它的错误率。当集合 S={x1, x2,…, xn} 的所有元素都被 k 个哈希函数映射到 m 位的位数组中时，这个位数组中某一位还是 0 的概率是：
因为哈希函数是随机的，所以任意一个哈希函数选中这一位的概率为 1/m，那么 1-1/m 就代表哈希函数一次没有选中这一位的概率，要把 S 完全映射到 m 位数组中，需要做 kn 次哈希运算，所以最后的概率就是 1-1/m 的 kn 次方。
一个不属于 S 的元素 x 如果要被误判定为在 S 中，那么这个概率就是 k 次哈希运算得到的结果对应的位数组位置都为 1，所以误判概率为：
根据：
可以将误判概率转化为：
在给定 m、n 时，可以求出使得 f 最小化的 k 值为：
在这里将误判概率归纳如下：
表 中第一列为 m/n 的值，第二列为最优 k 值，其后列为不同 k 值的误判概率，可以看到当 k 值确定时，随着 m/n 的增大，误判概率逐渐变小。当 m/n 的值确定时，当 k 越靠近最优 K 值，误判概率越小。另外误判概率总体来看都是极小的，在容忍此误判概率的情况下，大幅减小存储空间和判定速度是完全值得的。
3.3 布隆过滤器对接scrapy的使用：
安装scrapy-redis-bloomfilter 模块
pip install scrapy-redis-bloomfilter
修改setting 文件：
# Ensure use this SchedulerSCHEDULER = "scrapy_redis_bloomfilter.scheduler.Scheduler"# 把去重模块更改为scrapy-redis-bloomfilter写好的模块DUPEFILTER_CLASS = "scrapy_redis_bloomfilter.dupefilter.RFPDupeFilter"# Redis URLREDIS_URL = 'redis://localhost:6379/0'# 散列函数的个数，个人偏向设置为10，不设置则默认为6，BLOOMFILTER_HASH_NUMBER = 6# Bloom Filter的bit参数，默认30（一亿级指纹池）BLOOMFILTER_BIT = 30# PersistSCHEDULER_PERSIST = True
DUPEFILTER_CLASS 是去重类，如果要使用 BloomFilter 需要将 DUPEFILTER_CLASS 修改为该包的去重类。
BLOOMFILTER_HASH_NUMBER 是 BloomFilter 使用的哈希函数的个数，默认为 6，可以根据去重量级自行修改。
BLOOMFILTER_BIT 即前文所介绍的 BloomFilter 类的 bit 参数，它决定了位数组的位数，如果 BLOOMFILTER_BIT 为 30，那么位数组位数为 2 的 30 次方，将占用 Redis 128MB 的存储空间，去重量级在 1 亿左右，即对应爬取量级 1 亿左右。如果爬取量级在 10 亿、20 亿甚至 100 亿，请务必将此参数对应调高。
参考博客：崔庆才的 14.4–Bloom Filter 的对接
