简介：

本文探讨了缓存击穿问题及其解决方案，特别是使用布隆过滤器的方法。布隆过滤器是一种概率数据结构，用于高效验证元素是否可能存在于集合中，减少对昂贵资源的查询。

如何应对缓存击穿的场景，比如：

    黑客攻击，用户错误的服务？
    服务启动了，但是缓存没有数据？ 

1 使用bloom fliter的场景

Bloom 过滤器是由 Burton Howard 于 1970 年构思的一种概率数据结构，它提供了一种有效的方法来验证条目肯定不在集合中。

这使得它在尝试在访问成本高昂的资源（例如通过网络或磁盘）上搜索项目时特别理想：

如果我有一个大型磁盘数据库，并且我想知道其中是否存在密钥user，

我们可以先查询Bloom过滤器，这将确定地告诉我它是否存在（然后磁盘查找可以继续）或不存在存在，在这种情况下，我可以放弃昂贵的磁盘查找，只需向堆栈发送否定回复。

2 应对缓存穿透

• 原因和现象

  面对现代互联网中大量的恶意攻击，造成大量访问不存在的key。
  例如登陆时使用无效的用户名，在网站查询成绩输入没有的账号，准考证等。

或者大量请求访问数据库中有但是redis中没有的key，例如新业务刚刚上线，此时的redis为空。
如此应用程序可能跳过缓存直接访问数据库去查询，导致数据库连接过多，消耗系统资源。

• 解决办法

针对比较少请求的ip地址，主动限制其访问次数，或者拉黑该ip，使用应用程序检查key的合法性，提前拒绝不合法的请求，比如使用bloom过滤器。

预热redis，运行一个批处理程序，将可能会大量访问的数据预先加载到redis，业务再进行服务，在最前端进行流量控制，逐步释放进来请求。

给出一段时间，让redis逐步加载热数据。如果数据库也没有key，redis就设置key值为null或空。

3 使用的例子

虽然可以使用其他数据结构（例如哈希表）来执行此操作，但布隆过滤器也特别有用，因为它们每个元素占用的空间非常小，通常以位数（而不是字节数！将存在一定比例的误报（这是可控的），但对于集合中是否存在密钥的初始测试，它们提供了出色的速度，最重要的是出色的空间效率。

布隆过滤器用于各种应用，例如广告投放——确保用户不会太频繁地看到广告;同样，在内容推荐系统中 - 确保推荐不会太频繁地出现，在数据库中 - 在磁盘上访问条目之前快速检查表中是否存在该条目，等等。

    # python3
import redis

import redisbloomfilter

name = "bloomfilter"
number_of_insertion=10000000
error_rate = 0.00001
redis_client = redis.StrictRedis()

bloom_filter = redisbloomfilter.RedisBloomFilter(name, number_of_insertion, error_rate, redis_client)
try:
    bloom_filter.initialize()
except redis.RedisError:
    print('occurs redis error')
    raise
except redisbloomfilter.BloomFilterException:
    print('bloom filter exception')
    raise 
bloom_filter.put("abc")
bloom_filter.contains("abc")

4 小结：

布隆过滤器的原理是当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数数组的K个点。

把它们置为1.检索时，这些点是不是都是1就大概知道集合中有没有目标值。

如果这些点有任何一个为0，则被检元素一定不在，如果都是1，则被检锁元素可能存在。

• 优点：

        1 增加和查询元素的时间复杂度为：O(K), K 为哈希函数的个数，一般较小，与数据量大小无关
  
        2 哈希函数相互之间没有关系，方便硬件并行运算
  
        3 布隆过滤器不需要存储元素本身，在某些对保密要求严格的场合有很大优势
  
        4 在能够承受一定的误判时，布隆过滤器比其他数据结构有很大空间优势
  
        5 数据量大时，布隆过滤器可以表示全集，其他数据结构不能
  
        6 使用同一组散列函数的布隆过滤器可以进行交，并，差运算
  

• 缺点：

        1 有误判率
  
        2 不能获取元素本身
  
        3 一般情况下不能从布隆过滤器删除元素
  

  4 如果采用计数方式删除，可能存在计数回绕问题