这篇文章更多的是应用和代码实践。理论请参考文末介绍。确认它在那里。详细介绍：BloomFilter，中文名叫做Bloomfilter，由Bloom于1970年提出，可以用来检测一个元素是否在一个集合中。它的空间利用效率非常高。使用它可以大大节省存储空间。.BloomFilter用一个位数组来表示一个待检测的集合，通过概率算法可以快速判断这个集合中是否存在某个元素，所以我们可以利用这个算法来实现去重。其优点是空间效率和查询时间远超一般算法，缺点是存在一定的误识别率和删除难度。场景1.大量爬虫数据去重2.保护数据安全：广告精准投放：广告主通过设备id计算hash算法，在数据包（数据提供者）中搜索。如果存在，则证明设备id属于目标群体，用于投放广告，同时保证设备id不泄露。数据提供商和广告商都没有透露他们自己的设备ID。间接用户画像，不违反数据安全法。详见：https://zhuanlan.zhihu.com/p/...3、比特币网络转账确认SPV节点：SPV是“SimplifiedPaymentVerification”的缩写。中本聪的论文简单提到了这个概念，指出无需运行全节点即可验证支付，用户只需保存所有区块头即可。虽然用户无法自己验证交易，但如果他能在区块链某处找到匹配的交易，他就可以知道网络已经批准了这笔交易，以及它从网络收到了多少确认。首先访问布隆过滤器判断交易记录是否存在于某个区块（block）中。从海量数据（数十亿区块，每个区块1-2M交易记录）中快速得出结果。详见：https://www.youtube.com/watch...4.分布式系统（Map-Reduce）将大任务分块，分配并验证子任务是否在子系统上。必要节省空间，提高效率我们先回顾一下ScrapyRedis的去重机制，在Redis集合中存储了Request的指纹，每个指纹的长度为40个16进制数。我们算一下这样消耗的存储空间，每个16进制数占用4b，1个指纹用40个16进制数表示，占用空间20B，所以10000个指纹占用200KB。1亿个指纹占用2G，所以当我们爬取的数量达到数亿的时候，Redis占用的内存会变得非常高，而这只是指纹的存储。此外，Redis还存储了爬行队列。内存占用会进一步增加，更不用说多个Scrapy项目同时爬取的情况了。所以当爬取达到亿级规模时，ScrapyRedis提供的set去重已经不能满足我们的要求了，所以这里需要使用一种更节省内存的去重算法，叫做BloomFilter。(内存版)Python实现的布隆过滤器pybloom的内存版https://github.com/jaybaird/p...安装：pipinstallpybloom该模块包含两个实现布隆过滤器功能的类。BloomFilter是恒定体积的。ScalableBloomFilter可用于自动扩容：>>>frompybloomimportBloomFilter>>>f=BloomFilter(capacity=1000,error_rate=0.001)#capacity为容量，error_rate为可容忍误报率>>>f.add('Traim304')#当元素不存在时返回FalseFalse>>>f.add('Traim304')#如果存在则返回TrueTrue>>>'Traim304'inf#值得注意的是如果返回True.该元素可能存在也可能不存在。过滤器可以容忍某些错误True>>>f#中的'Jacob'但是False。那么一定不能有False>>>len(f)#当前存在的元素1>>>f=BloomFilter(capacity=1000,error_rate=0.001)>>>frompybloomimportScalableBloomFilter>>>sbf=ScalableBloomFilter(mode=ScalableBloomFilter.SMALL_SET_GROWTH)>>>#sbf.add()和BloomFilter在误报率超过时会抛出异常>>>f=BloomFilter(capacity=1000,error_rate=0.0000001)>>>forainrange(1000):..._=f.add(a)...>>>len(a)Traceback（最近调用最后一次）：文件“”，第1行，在TypeError中：类型为“int”的对象hasnolen()>>>len(f)1000>>>f.add(1000)False>>>f.add(1001)#当误报率超过error_rate时，会报错Traceback（最近的calllast)：文件“”，第1行，在文件“/usr/local/lib/python2.7/site-packages/pybloom/pybloom.py”，第182行，添加raiseIndexError("BloomFilterisatcapacity")IndexError:BloomFilterisatcapacity(persistence)手动实现的redis版布隆过滤器数据量大，经常使用redis持久版布隆过滤器#布隆过滤器redis版本实现importhashlibimportredisimportsix#1.多个哈希函数的实现与求值#2.哈希表实现及对应的映射判断类MultipleHash(object):'''根据提供的原始数据，并预定义多个盐，生成多个哈希函数值'''def__init__(self,salts,hash_func_name="md5"):self.hash_func=getattr(hashlib,hash_func_name)iflen(salts)<3:raiseException("请提供至少3个盐")self.salts=saltsdefget_hash_values(self,data):'''根据提供的原始数据，返回多个哈希函数值'''hash_values=[]foriinself.salts:hash_obj=self.hash_func()hash_obj.update(self._safe_data(data))hash_obj.update(self._safe_data(i))ret=hash_obj.hexdigest()hash_values.append(int(ret,16))returnhash_valuesdef_safe_data(self,data):'''python2str===python3bytespython2uniocde===python3str:paramdata:给定的原始数据:return:st二进制类型'''的环形数据ifsix.PY3:ifisinstance(data,bytes):returndataelifisinstance(data,str):returndata.encode()else:raiseException("Pleaseprovideastring")#建议用英文描述else:ifisinstance(data,str):returndataelifisinstance(data,unicode):returndata.encode()else:raiseException("Pleaseprovideastring")#建议使用英文描述classBloomFilter(object):''''''def__init__(self,salts,redis_host="localhost",redis_port=6379,redis_db=0,redis_key="bloomfilter"):self.redis_host=redis_hostself.redis_port=redis_portself.redis_db=redis_dbself.redis_key=redis_keyself.client=self._get_redis_client()self.multiple_hash=MultipleHash(salts)def_get_redis_client(self):'''返回一个redis连接对象'''pool=redis.ConnectionPool(host=self.redis_host,port=self.redis_port,db=self.redis_db)client=redis.StrictRedis(connection_pool=pool)returnclientdefsave(self,data):''''''hash_values=self.multiple_hash.get_hash_values(data)forhash_valueinhash_values:offset=self._get_offset(hash_value)self.client.setbit(self.redis_key,offset,1)返回真defis_exists(self,data):hash_values=self.multiple_hash.get_hash_values(data)forhash_valueinhash_values:offset=self._get_offset(hash_value)v=self.client.getbit(self.redis_key,offset)ifv==0:returnFalsereturnTruedef_get_offset(self,hash_value):#512M长度哈希表#2**8=256#2**20=1024*1024#(2**8*2**20*2*3)代表hash表的长度如果同一项目中不能更改returnhash_value%(2**8*2**20*2*3)if__name__=='__main__':data=["asdfasdf","123","123","456","asf","asf"]bm=BloomFilter(salts=["1","2","3","4"],redis_host="172.17.0.2")fordindata:ifnotbm.is_exists(d):bm.save(d)print("映射数据成功：",d)else:print("发现重复数据：",d)scrapy-redis中应用的代码已经打包成Python包发布到PyPi，链接为：https://pypi.python.org/pypi/...，这样以后如果我们想直接使用ScrapyRedisBloomFilter，就不需要自己实现了。我们可以直接使用pip安装。命令如下：pip3installscrapy-redis-bloomfilterused方法和ScrapyRedis基本类似，这里有几个关键配置：#去重类，要使用BloomFilter，请替换DUPEFILTER_CLASSDUPEFILTER_CLASS="scrapy_redis_bloomfilter.dupefilter.RFPDupeFilter"#hash函数个数，默认6个，可以修改BLOOMFILTER_HASH_NUMBER=6#BloomFilter的bit参数，默认30，占用128MB空间，去重1亿BLOOMFILTER_BIT=30DUPEFILTER_CLASS是去重类，如果要使用BloomFilter，你需要修改DUPEFILTER_CLASS为该包的去重类。BLOOMFILTER_HASH_NUMBER是BloomFilter使用的hash函数个数，默认6个，可以根据去权重修改。BLOOMFILTER_BIT是上面介绍的BloomFilter类的bit参数，决定了bit数组的位数。如果BLOOMFILTER_BIT为30，则位数组的位数为2的30次方，将占用Redis128MB的存储空间。1亿左右，也就是对应的爬取级别是1亿左右。如果爬取级别是10亿、20亿甚至100亿，一定要相应增加这个参数。测试蜘蛛文件：fromscrapyimportRequest,SpiderclassTestSpider(Spider):name='test'base_url='https://www.baidu.com/s?wd='defstart_requests(self):foriinrange(10):url=self.base_url+str(i)yieldRequest(url,callback=self.parse)#Herecontains10duplicatedRequestsforiinrange(100):url=self.base_url+str(i)yieldRequest(url,callback=self.parse)defparse(self,response):self.logger.debug('Responseof'+response.url)首先在start_requests()方法中循环10次，构造一个URL，参数为0-9，然后循环100次构造一个参数为0-99的URL，那么这里会有10个重复的Requests，我们运行项目测试一下：scrapycrawltest可以看到最终输出如下：{'bloomfilter/filtered':10,'downloader/request_bytes':34021,'downloader/request_count':100,'downloader/request_method_count/GET':100,'downloader/response_bytes':72943,'downloader/response_count':100,'downloader/response_status_count/200':100,'finish_reason':'完成shed','finish_time':datetime.datetime(2017,8,11,9,34,30,419597),'log_count/DEBUG':202,'log_count/INFO':7,'memusage/max':54153216,'memusage/startup':54153216,'response_received_count':100,'scheduler/dequeued/redis':100,'scheduler/enqueued/redis':100,'start_time':datetime.datetime(2017,8,11,9,34,26,495018)}可以看到最后统计第一行的结果：'bloomfilter/filtered':10，这是经过BloomFilter过滤后的统计结果，可以看到过滤器的个数为10，也就是成功识别出了重复的10个Reqeusts，通过测试的原理在本文中得到了应用，难以描述的原理，最后说一下。一个长二进制向量和一个映射函数。参考资料1,https://zhuanlan.zhihu.com/p/...2,https://www.youtube.com/watch...3,《python3网络爬虫开发实战》崔庆才4,https://www.jianshu.com/p/f57…
