Python实现BloomFilter（布隆过滤器）

 

有关布隆过滤器的原理和用途，可以看看这篇文章：

深入Redis之 redis布隆过滤器（十一） http://zbpblog.com/blog-195.html

在本章不再赘述。

 

本章主要介绍如何使用python的布隆过滤器对scrapy框架的去重机制进行优化，从而节省存储已爬取的url（或者说request对象）所占用的内存空间。

 

一、用python实现的布隆过滤器pybloom

在GitHub中有一个开源项目python-bloomfilter，这个项目不仅仅实现了BloomFilter，还实现了一个大小可动态扩展的ScalableBloomFilter。

 

1.安装python-bloomfilter

从https://github.com/qiyeboy/python-bloomfilter

 中下载源码，进入源码目录，使用Python setup.py install即可完成安装。

 

如果发现报错无法安装依赖 bitarray， 可以在

https://www.lfd.uci.edu/~gohlke/pythonlibs/#bitarray

手动下载bitarray模块并安装

 

2. 使用示例：

# coding=utf-8

from pybloom import BloomFilter, ScalableBloomFilter

# 创建一个指定长度的布隆过滤器对象
f = BloomFilter(capacity=1000, error_rate=0.001)

# 构建这个布隆过滤器
for i in range(1000):
    f.add(i*2)

# 验证这个布隆过滤器
print(4 in f)
print(5 in f)

# =================================================

# 创建一个可扩容的布隆过滤器
sbf = ScalableBloomFilter(mode=ScalableBloomFilter.SMALL_SET_GROWTH)
for i in range(1000):
    sbf.add(i*2)

print(4 in sbf)
print(5 in sbf)
print(1001 in sbf)

sbf.add(1001)
print(1001 in sbf)
print(len(sbf))

 

 

二、在scrapy中使用布隆过滤器

scrapy中的去重过滤器源码（位于scrapy/dupefilters.py的RFPDupeFilter类），我们主要关注他的去重逻辑：

class RFPDupeFilter(BaseDupeFilter):
    """Request Fingerprint duplicates filter"""

    def __init__(self, path=None, debug=False):
        self.file = None
        self.fingerprints = set()		# 存放爬取过的request的指纹
        self.logdupes = True
        self.debug = debug
        self.logger = logging.getLogger(__name__)
        if path:
            self.file = open(os.path.join(path, 'requests.seen'), 'a+')
            self.file.seek(0)
            self.fingerprints.update(x.rstrip() for x in self.file)

	def request_seen(self, request):
			fp = self.request_fingerprint(request)
			if fp in self.fingerprints:
				return True
			self.fingerprints.add(fp)
			if self.file:
				self.file.write(fp + '\n')

	def request_fingerprint(self, request):
		return request_fingerprint(request)

# 生成request指纹
def request_fingerprint(request, include_headers=None, keep_fragments=False):
    if include_headers:
        include_headers = tuple(to_bytes(h.lower()) for h in sorted(include_headers))
    cache = _fingerprint_cache.setdefault(request, {})
    cache_key = (include_headers, keep_fragments)
    if cache_key not in cache:
        fp = hashlib.sha1()
        fp.update(to_bytes(request.method))
        fp.update(to_bytes(canonicalize_url(request.url, keep_fragments=keep_fragments)))
        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[cache_key] = fp.hexdigest()
	return cache[cache_key]

 

从这段逻辑我们可以看出，scrapy会先将一个request对象转为指纹，这个指纹是根据request对象的url+method+header头的信息经过sha1加密得到的一个唯一id（长度为40个字符）。

并将这个指纹存放到一个python的set集合( self.fingerprints)中，通过判断每一个request对象的指纹是否已存在于这个set集合中得知这个request对象是否已经请求过。

 

为了能够节省存储爬取过的请求所占用的内存空间，可以使用布隆过滤器替代set集合来进行优化。

 

如何将布隆过滤器使用到scrapy中？

1. 将self.fingerprints这个存放指纹的容器从set()集合改为ScalableBloomFilter布隆过滤器
2. 重写request_seen方法

由于ScalableBloomFilter布隆过滤器的使用方式和set()集合的使用方式完全一致，所以其实request_seen方法也可以不用全写，直接复用即可。

 

如下：

首先在你的scrapy项目的settings.py文件的目录下创建一个requestBloomFilter.py过滤器类，内容如下：

# coding = utf-8

from scrapy.dupefilters import RFPDupeFilter
from pybloom import ScalableBloomFilter

class RequestBloomFilter(RFPDupeFilter):
    def __init__(self, path=None, debug=False):
        self.fingerprints = ScalableBloomFilter(mode=ScalableBloomFilter.SMALL_SET_GROWTH)	# 将保存指纹的容器从set集合换成布隆过滤器。
        super(RequestBloomFilter, self).__init__(path, debug)

# request_seen方法可以不用重写
    # def request_seen(self, request):
    #     fp = self.request_fingerprint(request)
    #     print(fp)
    #     print(fp in self.fingerprints)
    #     if fp in self.fingerprints:
    #         return True
    #     self.fingerprints.add(fp)
    #     if self.file:
    #         self.file.write(fp + '\n')

 

然后，我们要在settings.py将爬虫默认的去重过滤器改为我们写的 RequestBloomFilter 类:

DUPEFILTER_CLASS = "zbpblog.requestBloomFilter.RequestBloomFilter"

 

三、在分布式爬虫scrapy_redis中使用布隆过滤器

我们知道scrapy_redis分布式爬虫的去重是通过redis的set集合类型做到的。现在我们也要将这个set集合替换为布隆过滤器，这次我们就不是使用python的布隆过滤器而是使用redis中的布隆过滤器，而布隆过滤器在redis中本质上是一个bitmap位图结构。

 

分布式爬虫使用的去重过滤器是scrapy_redis模块中的RFPDupeFilter，如下：

DUPEFILTER_CLASS = "scrapy_redis.dupefilter.RFPDupeFilter"

 

第三方的scrapy-redis-bloomfilter为我们重写了scrapy_redis的去重策略，使用了redis中的布隆过滤器替代了set结构，现在我们使用scrapy-redis-bloomfilter 模块中的RFPDupeFilter类来替换scrapy_redis模块中的RFPDupeFilter：

要先安装 scrapy-redis-bloomfilter 模块：

pip install scrapy-redis-bloomfilter

 

然后在setting.py中修改以下配置

# 替换scrapy_redis的去重类
DUPEFILTER_CLASS = "scrapy_redis_bloomfilter.dupefilter.RFPDupeFilter"

# 替换原来的请求调度器的实现类，使用 scrapy-redis 中请求调度器
SCHEDULER = "scrapy_redis_bloomfilter.scheduler.Scheduler"

# 设置布隆过滤器散列函数的个数，默认为6，可以自行修改
BLOOMFILTER_HASH_NUMBER = 6

# Bloom Filter的bit参数，默认30，占用128MB空间，可存储数据量级1亿
BLOOMFILTER_BIT = 30

 

BLOOMFILTER_BIT决定了位图的位数。如果BLOOMFILTER_BIT为30，那么位数组位数为2的30次方，这将占用Redis 128 MB的存储空间，去重量级在1亿左右。

 

散列函数的个数越多错误率越低，但是request指纹写入布隆过滤器的速度越慢，从而影响到爬取的速度。

 

 

需要注意的是，如果设置了一个2^30长度的位图，位图一旦生成就会马上占用一百多兆的内存空间，而随着之后不断往这个布隆过滤器添加数据，这个布隆过滤器的大小不会变，始终保持在一百多兆的大小。而且位图的长度一旦设定，这个布隆过滤器的容量就已经被决定，无法扩容，如果你设定了一个长度位1亿的布隆过滤器，但是随着业务的扩展可能要存10亿个数据，此时只能重新构建一个容量为10亿的布隆过滤器。

 

因此，布隆过滤器适用于要爬取上亿的url的爬虫。而对于爬取数据量小的爬虫使用布隆过滤器反而不合适（因为如果把位数设置大了就浪费空间，把位数设置小了会容纳不下那么多request请求而导致错误率上升），使用set集合反而更合适，因为不会占用太多空间且灵活，其容量是可扩展的。

 

另外除了要将request对象存到布隆过滤器之外，还要将这个request对象的指纹存一份到数据库中。如果真的出现了上面说的要对布隆过滤器扩容重建的情况，我们还可以将数据库中的request指纹重新导入到这个扩容后的布隆过滤器。

 

最后，对scrapy-redis-bloomfilter的去重过滤器感兴趣的同学可以看一下scrapy-redis-bloomfilter中RFPDupeFilter的源码。其实基本思路和之前scrapy以及scrapy_redis的思路一样，只不过操作的容器从set集合换成了redis的布隆过滤器（位图）。