使用BloomFilter优化scrapy-redis去重

2017-12-27 19:14:41来源:CSDN作者:zwq912318834人点击

分享

使用BloomFilter优化scrapy-redis去重

1. 背景

  • 做爬虫的都知道,scrapy是一个非常好用的爬虫框架,但是scrapy吃内存非常的厉害。其中有个很关键的点就在于去重。
  • “去重”需要考虑三个问题:去重的速度和去重的数据量大小,以及持久化存储来保证爬虫能够续爬。
    • 去重的速度:为了保证较高的去重速度,一般是将去重放到内存中来做的。例如python内置的set( ),redis的set数据结构。但是当数据量变得非常大,达到千万级亿级时,因为内存有限,就需要用“位”来去重了, 因此BloomFilter应运而生,将去重工作由字符串直接转到bit位上,大大降低了内存占有率。
    • 去重的数据量大小:当数据量较大时,我们可以使用不同的加密算法,压缩算法(例如md5,hash)等,将长字符串压缩成16/32 长度的短字符串。然后再使用set等方式来去重。
    • 持久化存储:scrapy默认是开启去重的,而且提供了续爬设计,在爬虫终止时,会记录一个状态文件记录爬取过的request和状态。scrapy-redis的去重工作交给了redis,去重队列放到了redis中,而redis可以提供持久化存储。Bloomfilter是将去重对象映射到几个内存“位”,通过几个位的 0/1值来判断一个对象是否已经存在。Bloomfilter运行在一台机器的内存上,并不方便持久化,爬虫一旦终止,数据就丢失了。
  • 如上所述,对于scrapy-redis分布式爬虫来说,使用Bloomfilter来优化,必然会遇到两个问题:
    • 第一,要想办法让Bloomfilter能持久化存储下来。
    • 第二,对于scrapy-redis分布式爬虫来说,爬虫分布在好几台不同的机器上。而Bloomfilter是基于内存的,如何让各个不同的爬虫机器能够共享到同一个Bloomfilter,来达到统一去重?
  • 综上所述,将Bloomfilter挂载到redis上,持久化存储以及让各爬虫共享去重队列,这两个问题就都解决了。

2. 环境

  • 系统:win7
  • scrapy-redis
  • redis 3.0.5
  • python 3.6.1

3. Bloom Filter基本概念以及原理

  • 详情请参考文章:http://blog.csdn.net/jiaomeng/article/details/1495500
  • 简单来说,Bloom Filter是:
    • Bloom Filter 是一种空间效率很高的随机数据结构,利用位数组表示一个集合,并能判断一个元素是否属于这个集合。
    • Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。当然,如果这个元素属于这个集合,是一定不会被误判为不存在这个集合。
    • Bloom Filter不适合那些“0错误”的应用场合。

为了能理解Bloom Filter的原理,必须熟悉以下几个基本元素的概念:

3.1. Bloom Filter位数组

Bloom Filter是用位数组表示集合的。初始状态时,Bloom Filter是一个包含m位的位数组 { 1, …, m },每一位都置为0。表现形式可以是一段空白的内存,长字符串,任意一种占用内存空间的数据结构……
这里写图片描述

3.2. 待去重元素

对爬虫来说,也就是request队列,我们记为 S = { R1, R2, …, Rn } 这样一个n个元素的集合。

3.3. k个相互独立的哈希函数

Bloom Filter使用k个相互独立的哈希函数,我们记为 H = { H1( ), H2( ), …, Hk( ) }。利用这些hash函数,对集合S = { R1, R2, …, Rn } 中的每个元素进行处理,映射到Bloom Filter开辟内存{ 1, …, m }的某一位上。这样,对于R1来说,映射的结果就是{ H1( R1 ), H2( R1 ), …, Hk( R1 ) }

这里写图片描述

需要注意的是,如果一个位置多次被置为1,那么只有第一次会起作用,后面几次将没有任何效果。
从这一点就可以看出为什么会有误判,有可能会把不属于这个集合的元素误认为属于这个集合,就是因为这个元素被映射后的集合上那些位上,可能已经被置成1了。

3.3.

3.1.

4. redis的setbit功能

5. 详细部署

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台