Redis中的布隆过滤器

一、前言
从布隆过滤器和计数过滤器和布谷鸟过滤器，都是过滤器，都是判断集合中是否存放元素的算法，像对于传统的hash算法有改进，都是为redis服务的，知道本质就好。

面试中，一般问到缓存穿透，或者海量数据去重这个时候引出布隆过滤器，作为面试加分项

二、避免缓存击穿的利器之BloomFilter
2.1 Bloom Filter 概念
名称由来：布隆过滤器是一个音译词语，英文为 Bloom Filter，音译为布隆过滤器；
作用：用于检索一个元素是否在一个集合中；
本质：本质上是一个很长的二进制向量和一系列随机映射函数；
优点：空间效率和查询时间都远远超过一般的哈希算法；
缺点：有一定的误识别率和删除困难。

2.2 布隆过滤器适合的五个场景
用于检索一个元素是否在一个集合中
两个应用方向：缓存穿透、海量数据去重

1、布隆过滤器作为判断方法用来 防止数据库穿库，处理缓存穿透

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

简单来说就是你数据库的id都是1开始然后自增的，那我知道你接口是通过id查询的，我就拿负数去查询，这个时候，会发现缓存里面没这个数据，我又去数据库查也没有，一个请求这样，100个，1000个，10000个呢？你的DB基本上就扛不住了，如果在缓存里面加上布隆过滤器，是不是就知道这个负数不存在了，你判断没这个数据就不去查了，直接return一个数据为空不就好了嘛。

缓存击穿和缓存穿透
缓存穿透与缓存击穿异同：
相同点：都是数据库承受不了巨大压力，导致崩溃。
不同点：
缓存穿透是指redis没作用，形同虚设，每一次访问都要查询数据库，导致崩溃，这是技术上可以解决的，redis中记录一个（x,null）键值对；我们的业务中经常会遇到穿库的问题，通常可以通过缓存解决。 如果数据维度比较多，结果数据集合比较大时，缓存的效果就不明显了，表现为缓存穿透。 因此为了解决穿库的问题，我们引入Bloom Filter。
缓存击穿是指redis作用了，但是数据量实在是太大了，实在是承受不了这么大的数据量，数据库连带redis缓存一起崩溃，这时在固定的硬件成本下，缓存、数据库软件方面已经达到理论上的最优了，技术上解决不了。

2、布隆过滤器作为判断方法用来作为 缓存宕机时的应急方式

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

3、布隆过滤器作为判断方式用来作为 WEB拦截器 拦截相同请求防止DOS攻击

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

4、布隆过滤器作为判断方式用来作为 chrome恶意地址检测

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

5、布隆过滤器作为判断方式用来实现 比特币加速

bitcoin 使用BloomFilter来加速钱包同步。

6、海量数据去重方向：cerberus在收集监控数据的时候, 有的系统的监控项量会很大, 需要检查一个监控项的名字是否已经被记录到db过了, 如果没有的话就需要写入db，如果记录过db就不用记录。

7、海量数据去重方向：爬虫过滤已抓到的url就不再抓，可用bloom filter过滤

8、空间效率高方向：垃圾邮件过滤。如果用哈希表，每存储一亿个 email地址，就需要 1.6GB的内存（用哈希表实现的具体办法是将每一个 email地址对应成一个八字节的信息指纹，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个 email地址需要占用十六个字节。一亿个地址大约要 1.6GB，即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百 GB的内存。而Bloom Filter只需要哈希表 1/8到 1/4 的大小就能解决同样的问题。