为什么我们在业务中引入时经常会遇到数据库穿透的问题，通常可以通过缓存来解决。如果数据维度很多，得到的数据集比较大，缓存的效果就不会很明显。因此，为了解决通过库的问题，我们引入了BloomFilter。我们先看一下一般的业务缓存流程：先查询缓存，找不到缓存再查询数据库。然后将查询结果放在缓存中即使数据不存在，也需要创建缓存防止数据库被透传。这里需要区分数据是否存在。如果数据不存在，可以将缓存时间设置的比较短，防止因为主从同步等问题将问题放大。这个过程中的弱点是，当用户量过大时，我们会缓存大量的空数据，一旦有一波冷用户到来，就会造成雪崩效应。针对这种情况，我们生成第二个版本流程：redis过滤冷用户缓存流程。我们把选中的用户放到redis的set类型的数据库中，设置不过期。这样就把redis当成了数据库的索引。只要查询redis，就可以知道数据是否存在。如果redis中不存在，可以直接返回结果。如果存在，按照上面提到的通用业务缓存流程。聪明的你肯定会想到更多的问题：Redis本身可以作为缓存，为什么不直接返回数据呢？如果数据量比较大，单套会有性能问题吗？业务不重要，全量数据放在redis中，占用服务器内存大。投入产出不成比例？问题1需要区分业务场景，得到的数据量小。我们可以直接使用redis作为缓存，直接返回数据。如果结果比较大，不适合用redis存储。比如ugc内容，一条评论可能有几万字，业务领域也很多。使用redis有很多技巧。Bigkey相对有害。无论是扩缩容引起的内存申请释放，还是查询命令使用不当导致大量数据返回，都会影响redis的稳定性。其成因及危害不在此详述。bigkey的解决方案很简单。我们可以使用哈希函数来划分桶，将数据分散到多个键中。在不影响查询效率的情况下减小单个键的大小。问题3是redis存储占用内存太大。所以我们需要减少内存使用。重新思考引入redis的目的。Redis就像一个集合，整个业务就是验证请求的参数是否在集合中。这种结构就像淋浴时使用的双向阀：左边是热水，右边是冷水。大多数编程语言都内置了过滤器。以python为例，filter函数用于过滤序列，过滤掉不满足条件的元素，返回满足条件的元素组成的列表。我们来看一个例子：$python2Python2.7.10(default,Oct62017,22:29:07)[GCC4.2.1CompatibleAppleLLVM9.0.0(clang-900.0.31)]ondarwinType"help","copyright","credits"or"license"fororeinformation.>>>s={2,4}>>>filter(lambdax:xins,[0,1,2])[2]集合s中有两个数2和4，我们需要查询0和1,2集合s中的那些。lambdax:xins构造一个匿名函数来判断输入参数x是否在集合s中。filter过滤器依次对列表中的数字执行匿名函数。最后返回列表[2]。redis中set的实现使用了两种结构：intset和hashtable。非数字或大量数字将退化为哈希表。那么一个好的算法能不能节省哈希表的大小呢？其实布隆过滤器（英文：BloomFilter）早在1970年就由BurtonHowardBloom提出。它实际上是一个长二值向量和一系列随机映射函数。布隆过滤器可用于检索元素是否在集合中。其优点是空间效率和查询时间远超一般算法，缺点是存在一定的误识别率和删除难度。BloomFilter的原理我们一般把业务字段拼接后md5放在一个集合中。md5生成一个固定长度的128位字符串。如果用bitmap来表示，需要2**128=340282366920938463463374607431768211456bit来判断一个值是否存在，也就变成判断这个位图中的bit是否为1。但是我们遍布全球的机器存储空间也存不下下载。所以我们只能分配有限的空间用于存储。例如：importcrc32defBloomFilter(sample,size,hash_size=1):#构造一个散列函数，将输入数据散列到大小为hash=lambdax:crc32(str(x).encode())%sizecollision,s=0的位置,set()foriinrange(sample):k=set()forjinrange(hash_size):k.add(hash(i+j*size/hash_size))#只有当所有hash结果k都在s中时，才认为i是repeatedifnotk-s:collision+=1continue#更新哈希结果k到集合ss|=kreturncollision当哈希函数只有一个时：容易发生冲突。可以看出上面1和2的hash结果都是7，发生了冲突。如果增加散列函数会发生什么？我们使用更多的哈希函数和更大的数据集来测试。得到下表，由此可见，加入hash方法后，可以有效降低碰撞概率。比较好的数据如下：但是加入hash方法后，空间使用效率会降低。当collection占总空间的25%时，增加hash的效果就不再明显了。上面提到的使用多种hash方法来减少碰撞是BloomFilter的核心思想。适用场景防止磨损的数据库GoogleBigtable、ApacheHBase和ApacheCassandra，以及Postgresql使用BloomFilter来减少对不存在的行或列的磁盘查找。避免代价高昂的磁盘查找可以极大地提高数据库查询操作的性能。就像一开始的商业场景。如果数据量很大，不方便放到缓存中。有必要拦截请求以防止它通过库。缓存宕机当缓存宕机时，使用布隆过滤器会造成一定程度的误判。原因除了BloomFilter本身的误判率外，宕机前的缓存可能没有覆盖到DB中的所有数据。当用户在宕机后请求一个之前从未请求过的数据时，此时就会发生误判。当然，当缓存宕机时，使用Bloomfilter作为应急手段，应该是可以容忍的。WEB拦截器拦截相同的请求，防止入侵。当用户第一次请求时，将请求参数放入BloomFilter，当用户第二次请求时，先判断请求参数是否被BloomFilter命中。可以提高缓存命中率。恶意地址检测chrome浏览器检查恶意地址。首先根据本地BloomFilter检查任何URL，只有当BloomFilter返回肯定结果时，才会对URL执行完整检查（如果它也返回肯定结果，则会警告用户）。BitcoinAcceleration比特币使用BloomFilter来加速钱包同步。算法优点：数据空间小，不需要自己存储数据。算法本身的缺点：元素可以添加到集合中，但不能删除。匹配结果只能是“绝对不在集合中”，不保证匹配值已经在集合中。当集合接近满时，即接近估计的大容量时，误报的概率会增加。数据足迹扩大了。通常，对于1%的误报概率，每个元素少于10位，无论集合中元素的大小或数量如何。-查询过程变慢，哈希函数数量增加，导致需要搜索多个位（哈希数）来确认每个匹配过程的存在。对于BloomFilter的优点，缺点可以忽略不计。毕竟存储N个元素只需要kN的存储空间。空间效率极佳。如何使用BloomFilterBloomFilter需要一个大的位图来存储。鉴于公司目前的情况，比较合适的存储容器是redis。Redis集成BloomFilter方案：Redis集成BloomFilter方案：Nativepython调用setbit构造BloomFilterlua脚本Rebloom-BloomFilterModuleforRedis(注：redisModule是在redis4.0引入的)使用hiredis调用redispyreBloomnativepython方法太慢，lua脚本和Module部署比较麻烦。所以我们推荐使用底层使用的pyreBloom。pyreBloom:masterλlsMakefilebloom.hbloom.pxdmurmur.cpyreBloom.pyxbloom.cbloom.omain.cpyreBloom.c从文件命名可以看出bloom是用c写的。pyreBloom是用cython编写的。Bloom.h实现了BloomFilter的核心逻辑，完成与redis服务器的交互；哈希函数；添加、检查和删除方法的实现。intinit_pyrebloom(pyrebloomctxt*ctxt,char*key,uint32_tcapacity,doubleerror,char*host,uint32_tport,char*password,uint32_tdb);intfree_pyrebloom(pyrebloomctxt*ctxt);intadd(pyrebloomctxt*ctxt,constchar*data,uint32_tlen);intadd_complete(pyrebloomctxt)*ctxt，uint32_tcount）；intcheck（pyrebloomctxt*ctxt，constchar*data，uint32_tlen）；intcheck_next（pyrebloomctxt*ctxt）；intdelete（pyrebloomctxt*ctxt）；pyreBloom.pyximportmathimportrandomcimportbloomclasspyreBloomException（异常）：'''Somesortofexceptionhashappenedinternally'''passcdefobject（classpyreBloomobject）):cdefbloom.pyrebloomctxtcontextcdefbyteskeypropertybits:def__get__(self):returnsself.context.bitspropertyhashes:def__get__(self):returnsself.context.hashesdef__cinit__(self,key,capacity,error,host='127.0.0.1',port=6379,password='',db=0):self.key=keyifbloom.init_pyrebloom(&self.context,self.key,capacity,error,host,port,password,db):raisepyreBloomException(self.context.ctxt.errstr)def__dealloc__(self):bloom.free_pyrebloom(&self.context)defdelete(self):bloom.delete(&self.context)defput(self,value):ifgetattr(value,'__iter__',False):r=[bloom.add(&self.context,v,len(v))forvinvalue]r=bloom.add_complete(&self.context,len(value))else:bloom.add(&self.context,value,len(value))r=bloom.add_complete(&self.context,1)ifr<0:raisepyreBloomException(self.context.ctxt.errstr)returnrdefadd(self,value):returnsself.put(value)defextend(self,values):returnsself.put(values)defcontains(self,value):#Iftheobjectis'iterable'...ifgetattr(value,'__iter__',False):r=[bloom.check(&self.context,v,len(v))forvinvalue]r=[bloom.check_next(&self.context)foriinrange(len(value))]if(min(r)<0):raisepyreBloomException(self.context.ctxt.errstr)return[vforv,includedinzip(value,r)ifincluded]else:bloom.check(&self.context,value,len(value))r=bloom.check_next(&self.context)if(r<0):raisepyreBloomException(self.context.ctxt.errstr)returnbool(r)def__contains__(self,value):returnself.contains(value)defkeys(self):'''Returnalistofthekeysusedinthisbloomfilter'''return[self.context.keys[i]foriinrange(self.context.num_keys)]本机pyreBloom方法：cdefclasspyreBloom(object):cdefbloom.pyrebloomctxtcontextcdefbytespropertybits:propertyhashes://hash方法使用的次数defdelete(self)://delete，会在redis中删除defput(self,value)://添加底层方法，不建议调用defadd(self,value)://添加单个元素，调用put方法defextend(self,values)://添加一组元素，调用put方法defcontains(self,value)://检查是否存在，当`value`可以迭代时，返回`[value]`，否则返回`bool`defkeys(self)://redis存储的key列表由于pyreBloom使用的是hiredis库，没有重连等逻辑，所以简单的封装是错误的#coding=utf-8'''Bloomfilter基础模块可用方法：extend,keys,contains,add,put,hashes,bits,deleteUsage:>>>classTestModel(BaseModel):...PREFIX="bf:test">>>t=TestModel()>>>t.add('hello')1>>>t.extend(['hi','world'])2>>>t.contains('hi')True>>>t.delete()'''importloggingfromsiximportPY3asIS_PY3frompyreBloomimportpyreBloom,pyreBloomExceptionfromBloomFilter.utilsimportforce_utf8classBaseModelES(object):'''bloomfilter基本模块参数：SLOT：可用的方法类型PREFIX：redis前缀BF_SIZE：BF_ERRORT：错误率RE：允许试验主机数:redisserverIPport:redisserverportdb:redisserverDB_bf_conn:Internalstorage`pyreBloom`instance'''SLOT={'add','contains','extend','keys','put','delete','bits','hashes'}PREFIX=""BF_SIZE=100000BF_ERROR=0.01RETRIES=2def__init__(self,redis=None):'''初始化redis配置:paramredis:redis配置'''#这里初始化预防类静态变量被多个继承类重用，导致datapollutionself._bf_conn=Noneself._conf={'host':'127.0.0.1','password':'','port':6379,'db':0}ifredis:fork,vinredis.items():ifkinself._conf:self._conf[k]=redis[k]self._conf=force_utf8(self._conf)@propertydefbf_conn(self):'''初始化pyreBloom'''ifnotself._bf_conn:prefix=force_utf8(self.PREFIX)logging.debug('pyreBloomconnect:redis://%s:%s/%s,(%s%s%s)',self._conf['host'],self._conf['port'],self._conf['db'],prefix,self.BF_SIZE,self.BF_ERROR,)self._bf_conn=pyreBloom(prefix,self.BF_SIZE,self.BF_ERROR,**self._conf)returnself._bf_conndef__getattr__(self,method):'''在没有枚举方法的情况下调用pyrebloom方法会从`pyreBloom`获取：parammethod::return:pyreBloom.{method}'''#只提供内部方法ifmethodnotinself.SLOT:raiseNotImplementedError()#捕获`pyreBloom`的异常，打印必要的logdefcatch_error(*a,**kwargs):'''多次重试服务'''args=force_utf8(a)kwargs=force_utf8(kwargs)for_inrange(self.RETRIES):try:func=getattr(self.bf_conn,method)res=func(*args,**kwargs)#python3返回值和python2返回值不一样，#手动处理返回类型ifmethod=='contains'andIS_PY3:ifisinstance(res,list):return[i.decode('utf8')foriinres]返回res除了pyreBloomException:logging.warn('pyreBloomError:%s%s',method,str(error))self.reconnect()if_==self.RETRIES:logging.error('pyreBloomError')raiseerrorreturncatch_errordef__contains__(self,item):'''跳转__contains__method:paramitem:查询元素列表/单个元素:typeitem:list/basestring:return:[bool...]/bool'''returnsself.contains(item)defreconnect(self):'''reconnectbloom`pyreBloom`使用cdriver连接，不提供timeout参数，使用内置的timeout来保证对于服务可靠性，增加了多种重试机制关闭redis连接'''ifself._bf_conn:logging.debug('pyreBloomreconnect')delself._bf_connself._bf_conn=None_=self.bf_conn进阶：计数过滤器（CountingFilter）提供了一种无需重新创建BloomFilter方法即可实现删除操作的方法筛选。在计数过滤器中，数组位置（桶）从单个位扩展为n位计数器。事实上，一个普通的布隆过滤器可以看作是一个桶大小为一位的计数过滤器。插入操作被扩展以增加桶的值，查找操作检查每个所需的桶中的非零值。然后删除操作包括递减每个桶的值。桶的算术溢出是一个问题，桶应该足够大，这种情况很少见。如果确实发生，递增和递减操作必须将存储设置为最大可能值，以保留BloomFilter的属性。计数器的大小通常为3或4位。因此，计算型布隆过滤器需要的空间是静态布隆过滤器的3到4倍。相比之下，Pagh、Pagh和Rao(2005)以及Fan等人的数据结构。(2014)也允许删除但使用比静态BloomFilter更少的空间。计数过滤器的另一个问题是可扩展性有限。由于无法扩展计数布隆过滤器表，因此必须事先知道过滤器中同时存储的最大键数。一旦超过表的设计容量，随着插入的键越来越多，误报率会快速增长。博诺米等人。(2006)引入了一种基于d-left散列的数据结构，它在功能上是等效的，但使用的计算空间大约是BloomFilter的一半。此数据结构中不会出现可伸缩性问题。一旦超过设计容量，就可以将密钥重新插入到新的两倍大小的哈希表中。Putze、Sanders和Singler(2007)的节省空间的变体也可用于通过支持插入和删除来实现计数过滤器。Rottenstreich、Kanizo和Keslassy（2012年）引入了一种基于变量增量的新通用方法，该方法显着提高了计算Bloom过滤器及其变体的误报概率，同时仍支持删除。与计数布隆过滤器不同，哈希计数器在每次元素插入时以哈希变量增量而不是单位增量递增。要查询元素，需要考虑计数器的确切值，而不仅仅是它们的积极性。如果计数器值表示的和不能由查询元素的相应变量增量形成，则查询可能会返回否定答案。
