布隆过滤器实战【防止缓存击穿】

为什么引入

我们的业务中经常会遇到穿库的问题，通常可以通过缓存解决。 如果数据维度比较多，结果数据集合比较大时，缓存的效果就不明显了。 因此为了解决穿库的问题，我们引入Bloom Filter。

适合的场景

• 数据库防止穿库 Google Bigtable，Apache HBase和Apache Cassandra以及postgresql 使用BloomFilter来减少不存在的行或列的磁盘查找。避免代价高昂的磁盘查找会大大提高数据库查询操作的性能。 如同一开始的业务场景。如果数据量较大，不方便放在缓存中。需要对请求做拦截防止穿库。

• 缓存宕机 缓存宕机的场景，使用布隆过滤器会造成一定程度的误判。原因是除了Bloom Filter 本身有误判率，宕机之前的缓存不一定能覆盖到所有DB中的数据，当宕机后用户请求了一个以前从未请求的数据，这个时候就会产生误判。当然，缓存宕机时使用布隆过滤器作为应急的方式，这种情况应该也是可以忍受的。

• WEB拦截器 相同请求拦截防止被攻击。用户第一次请求，将请求参数放入BloomFilter中，当第二次请求时，先判断请求参数是否被BloomFilter命中。可以提高缓存命中率

• 恶意地址检测 chrome 浏览器检查是否是恶意地址。 首先针对本地BloomFilter检查任何URL，并且仅当BloomFilter返回肯定结果时才对所执行的URL进行全面检查（并且用户警告，如果它也返回肯定结果）。

• 比特币加速 bitcoin 使用BloomFilter来加速钱包同步。

开源项目地址：https://GitHub.com/luw2007/bloomfilter

我们先看看一般业务缓存流程： 

先查询缓存，缓存不命中再查询数据库。 然后将查询结果放在缓存中即使数据不存在，也需要创建一个缓存，用来防止穿库。这里需要区分一下数据是否存在。 如果数据不存在，缓存时间可以设置相对较短，防止因为主从同步等问题，导致问题被放大。

这个流程中存在薄弱的问题是，当用户量太大时，我们会缓存大量数据空数据，并且一旦来一波冷用户，会造成雪崩效应。 对于这种情况，我们产生第二个版本流程:Redis过滤冷用户缓存流程 

我们将数据库里面中命中的用户放在redis的set类型中，设置不过期。 这样相当把redis当作数据库的索引，只要查询redis，就可以知道是否数据存在。 redis中不存在就可以直接返回结果。 如果存在就按照上面提到一般业务缓存流程处理。

聪明的你肯定会想到更多的问题：

1. redis本身可以做缓存，为什么不直接返回数据呢？

2. 如果数据量比较大，单个set，会有性能问题？

3. 业务不重要，将全量数据放在redis中，占用服务器大量内存。投入产出不成比例？

问题1需要区分业务场景，结果数据少，我们是可以直接使用redis作为缓存，直接返回数据。 结果比较大就不太适合用redis存放了。比如uGC内容，一个评论里面可能存在上万字，业务字段多。

redis使用有很多技巧。bigkey 危害比较大，无论是扩容或缩容带来的内存申请释放， 还是查询命令使用不当导致大量数据返回，都会影响redis的稳定。这里就不细谈原因及危害了。 解决bigkey 方法很简单。我们可以使用hash函数来分桶，将数据分散到多个key中。 减少单个key的大小，同时不影响查询效率。

问题3是redis存储占用内存太大。因此我们需要减少内存使用。 重新思考一下引入redis的目的。 redis像一个集合，整个业务就是验证请求的参数是否在集合中。  这个结构就像洗澡的时候用的双向阀门：左边热水，右边冷水。

大部分的编程语言都内置了filter。 拿python举例，filter函数用于过滤序列， 过滤掉不符合条件的元素，返回由符合条件元素组成的列表。

我们看个例子：

$ Python2
Python 2.7.10 (default, Oct  6 2017, 22:29:07)
[GCC 4.2.1 Compatible Apple LLVM 9.0.0 (clang-900.0.31)] on darwin
Type "help", "copyright", "credits" or "license" for more infORMation.
>>> s = {2, 4}
>>> filter(lambda x:x in s, [0, 1, 2])
[2]

集合s中存在 2，4两个数字，我们需要查询 0，1，2 那些在集合s中。 lambda x:x in s构造一个匿名函数，判断入参x是否在集合s中。 过滤器filter依次对列表中的数字执行匿名函数。最终返回列表[2]。

redis中实现set用了两种结构：intset和hash table。 非数字或者大量数字时都会退化成hash table。 那么是否好的算法可以节省hash table的大小呢？

其实早在1970年由Burton Howard Bloom提出的布隆过滤器（英语：Bloom Filter）。 它实际上是一个很长的二进制向量和一系列随机映射函数。 布隆过滤器可以用于检索一个元素是否在一个集合中。 它的优点是空间效率和查询时间都远远超过一般的算法， 缺点是有一定的误识别率和删除困难。

BloomFilter原理

我们常见的将业务字段拼接之后md5，放在一个集合中。 md5生成一个固定长度的128bit的串。 如果我们用bitmap来表示，则需要

2**128 = 340282366920938463463374607431768211456 bit

判断一个值在不在，就变成在这个bitmap中判断所在位是否为1。 但是我们全世界的机器存储空间也无法存储下载。 因此我们只能分配有限的空间来存储。 比如:

 crc32

 (, , ):
    
       :crc32((x).encode())size
    collision, s  , ()
     i  (sample):
        k  ()
         j  (hash_size):
            k.add((ijsizehash_size))
        
          k  s:
            collision  
            
        
        s  k
     collision

当只有一个hash函数时：很容易发生冲突。 

可以看到上面1和2的hash结果都是7，发生冲突。 如果增加hash函数，会发生什么情况？

我们使用更多的hash函数和更大的数据集合来测试。得到下面这张表 

由此可以看到当增加hash方法能够有效的降低碰撞机率。 比较好的数据如下： 

但是增加了hash方法之后，会降低空间的使用效率。当集合占用总体空间达到25%的时候， 增加hash 的效果已经不明显

上面的使用多个hash方法来降低碰撞就是BloomFilter的核心思想。

算法优点：

• 数据空间小，不用存储数据本身。

算法本身缺点：

• 元素可以添加到集合中，但不能被删除。

• 匹配结果只能是“绝对不在集合中”，并不能保证匹配成功的值已经在集合中。

• 当集合快满时，即接近预估最大容量时，误报的概率会变大。

• 数据占用空间放大。一般来说，对于1％的误报概率，每个元素少于10比特，与集合中的元素的大小或数量无关。  查询过程变慢，hash函数增多，导致每次匹配过程，需要查找多个位（hash个数）来确认是否存在。

对于BloomFilter的优点来说，缺点都可以忽略。毕竟只需要kN的存储空间就能存储N个元素。空间效率十分优秀。

如何使用BloomFilter

BloomFilter 需要一个大的bitmap来存储。鉴于目前公司现状，最好的存储容器是redis。 从github topics: bloom-filter中经过简单的调研。

redis集成BloomFilter方案：

• 原生python 调用setbit 构造 BloomFilter

• lua脚本

• Rebloom - Bloom Filter Module for Redis (注：redis Module在redis4.0引入)

• 使用hiredis 调用redis pyreBloom

原生python 方法太慢，lua脚本和module 部署比较麻烦。于是我们推荐使用pyreBloom，底层使用。

pyreBloom:master λ ls
Makefile      bloom.h       bloom.pxd     murmur.c      pyreBloom.pyx
bloom.c       bloom.o       main.c        pyreBloom.c

从文件命名上可以看到bloom 使用c编写。pyreBloom 使用cython编写。

bloom.h 里面实现BloomFilter的核心逻辑，完成与redis server的交互；hash函数；添加，检查和删除方法的实现。

 (pyrebloomctxt * ctxt,  * key,  capacity,  error, * host,  port, * passWord,  db);
 (pyrebloomctxt * ctxt);

 (pyrebloomctxt * ctxt,   * data,  len);
 (pyrebloomctxt * ctxt,  count);

 (pyrebloomctxt * ctxt,   * data,  len);
 (pyrebloomctxt * ctxt);

 delete(pyrebloomctxt * ctxt);

pyreBloom.pyx

 math
 random

cimport bloom


 ():
	
	


cdef  ():
	cdef bloom.pyrebloomctxt context
	cdef                key

	 bits:
		 ():
			 .context.bits

	 hashes:
		 ():
			 .context.hashes

	 (, , , , , ,
		, ):
		.key  key
		 bloom.init_pyrebloom(.context, .key, capacity,
			error, host, port, password, db):
			 pyreBloomException(.context.ctxt.errstr)

	 ():
		bloom.free_pyrebloom(.context)

	 ():
		bloom.delete(.context)

	 (, ):
		 (value, , ):
			r  [bloom.add(.context, v, (v))  v  value]
			r  bloom.add_complete(.context, (value))
		:
			bloom.add(.context, value, (value))
			r  bloom.add_complete(.context, )
		 r  :
			 pyreBloomException(.context.ctxt.errstr)
		 r

	 (, ):
		 .put(value)

	 (, ):
		 .put(values)

	 (, ):
		
		 (value, , ):
			r  [bloom.check(.context, v, (v))  v  value]
			r  [bloom.check_next(.context)  i  ((value))]
			 ((r)  ):
				 pyreBloomException(.context.ctxt.errstr)
			 [v  v, included  (value, r)  included]
		:
			bloom.check(.context, value, (value))
			r  bloom.check_next(.context)
			 (r  ):
				 pyreBloomException(.context.ctxt.errstr)
			 (r)

	 (, ):
		 .contains(value)

	 ():
		
		 [.context.keys[i]  i  (.context.num_keys)]

原生pyreBloom方法:

cdef  (object):

    cdef bloom.pyrebloomctxt context
    cdef bytes

    property bits:

    property hashes:
    

    def (self):
    

    def (self, value):
    

    def add(self, value):
    

    def extend(self, values):
    

    def contains(self, value):
    

    def keys(self):

由于pyreBloom使用hiredis库，本身没有重连等逻辑，于是错了简单的封装。

    
    

















     logging
     six    
     pyreBloom  pyreBloom, pyreBloomException

     BloomFilter.utils  force_utf8


     ():
        












          {, , , , , ,
                , }
          
          
          
          

         (, ):
            



            
            ._bf_conn  

            ._conf  {
                : , : ,
                : , : 
            }

             redis:
                 k, v  redis.items():
                     k  ._conf:
                        ._conf[k]  redis[k]
            ._conf  force_utf8(._conf)

        
         ():
            


              ._bf_conn:
                prefix  force_utf8(.)
                logging.debug(
                    ,
                    ._conf[], ._conf[], ._conf[],
                    prefix, ., .,
                )
                ._bf_conn  pyreBloom(
                    prefix, ., ., ._conf)
             ._bf_conn

         (, ):
            




            
             method   .:
                 ()

            
             (, ):
                
                args  force_utf8(a)
                kwargs  force_utf8(kwargs)
                 _  (.):
                    :
                        func  (.bf_conn, method)
                        res  func(args, kwargs)
                        
                        
                         method    :
                             (res, ):
                                 [i.decode()  i  res]
                         res
                     pyreBloomException  error:
                        logging.warn(
                            , method, (error))
                        .reconnect()
                         _  .:
                            logging.error()
                             error

             catch_error

         (, ):
            




             .contains(item)

         ():
            







             ._bf_conn:
                logging.debug()
                 ._bf_conn
                ._bf_conn  
                _  .bf_conn

进阶：计数过滤器(Counting Filter)

提供了一种在BloomFilter上实现删除操作的方法，而无需重新重新创建过滤器。在计数滤波器中，阵列位置（桶）从单个位扩展为n位计数器。实际上，常规布隆过滤器可以被视为计数过滤器，其桶大小为一位。

插入操作被扩展为递增桶的值，并且查找操作检查每个所需的桶是否为非零。然后，删除操作包括递减每个桶的值。

存储桶的算术溢出是一个问题，并且存储桶应该足够大以使这种情况很少见。如果确实发生，则增量和减量操作必须将存储区设置为最大可能值，以便保留BloomFilter的属性。

计数器的大小通常为3或4位。因此，计算布隆过滤器的空间比静态布隆过滤器多3到4倍。相比之下， Pagh，Pagh和Rao（2005）以及Fan等人的数据结构。（2014）也允许删除但使用比静态BloomFilter更少的空间。

计数过滤器的另一个问题是可扩展性有限。由于无法扩展计数布隆过滤器表，因此必须事先知道要同时存储在过滤器中的最大键数。一旦超过表的设计容量，随着插入更多密钥，误报率将迅速增长。

Bonomi等人。（2006）引入了一种基于d-left散列的数据结构，它在功能上是等效的，但使用的空间大约是计算BloomFilter的一半。此数据结构中不会出现可伸缩性问题。一旦超出设计容量，就可以将密钥重新插入到双倍大小的新哈希表中。

Putze，Sanders和Singler（2007）的节省空间的变体也可用于通过支持插入和删除来实现计数过滤器。

Rottenstreich，Kanizo和Keslassy（2012）引入了一种基于变量增量的新通用方法，该方法显着提高了计算布隆过滤器及其变体的误报概率，同时仍支持删除。与计数布隆过滤器不同，在每个元素插入时，散列计数器以散列变量增量而不是单位增量递增。要查询元素，需要考虑计数器的确切值，而不仅仅是它们的正面性。如果由计数器值表示的总和不能由查询元素的相应变量增量组成，则可以将否定答案返回给查询。

原文作者：卢玮，掌阅资深后端工程师