为什么要用布隆过滤器？

前端用户查询数据时：
先去缓存或nosql（redis mongodb等）里面查。如果能找到，就直接把数据返回给用户；
如果缓存里面也没有（缓存没命中），才去数据库中查找。
如果有攻击者经常查询一些不会存在的数据，比如查询商品id= -1，那么缓存里面不可能会有商品id=-1的数据，
缓存没命中，最终要到mysql里面查询，加重了mysql的负担。
绕过缓存给mysql增加访问压力，构成了缓存穿透，严重的可能直接压爆数据库。
解决：我们可以在访问mysql之前，先访问一下布隆过滤器。
布隆过滤器能够判断某个值的存在情况， 如果布隆过滤器返回不存在， 那么就肯定不存在，
就没必要访问mysql，这样就成功把这些对mysql的恶意攻击进行过滤。。
问：不使用布隆过滤器如何解决数据过滤问题？
答：数组和哈希表配合常见的排序、二分搜索等算法，可以快速高效处理绝大部分判断元素是否存在集合中。
但数组、哈希等数据结构会存储元素的内容，一旦数据量过大，消耗的内存也会呈现线性增长，最终达到瓶颈。
哈希表不是效率很高吗？查询效率可以达到O(1)。
哈希表存储效率通常小于50%（涉及哈希冲突），哈希表需要消耗的内存依然很高；
哈希函数：将任意大小的数据转换成特定大小的数据的函数，转换后的数据称为哈希值或哈希编码，
原始数据经过哈希函数的映射后成为了一个个的哈希编码，数据得到压缩。

布隆过滤器原理

哈希函数是实现哈希表和布隆过滤器的基础。
在你告诉它总共要插入多少条数据时，BloomFilter就计算并申请好了内存空间，
所以BloomFilter占用内存不会随插入数据的多少而变化。
相反，HashSet在插入数据越来越多时，其占用的内存空间也会越来越多。
布隆过滤器（Bloom Filter）的核心实现是一个超大的位数组和几个哈希函数。
假设位数组的长度为m，哈希函数的个数为k，

以上图为例，具体的操作流程：假设集合里面有3个元素{x, y, z}，哈希函数的个数为3。
首先将位数组进行初始化，将里面每个位都设置位0。
对于集合里面的每一个元素，将元素依次通过3个哈希函数进行映射，每次映射都会产生一个哈希值，
这个值对应位数组上面的一个点，然后将位数组对应的位置标记为1。
查询W元素是否存在集合中的时候，同样将W通过哈希映射到位数组上的3个点。
如果3个点的其中有一个点不为1，则可以判断该元素一定不存在集合中。
反之，如果3个点都为1，则该元素可能存在集合中。
注意：此处不能判断该元素是否一定存在集合中，可能存在一定的误判率。
可以从图中可以看到：假设某个元素通过映射对应下标为4，5，6这3个点。
虽然这3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，
也可能对应的都是1，这是误判率存在的原因。

添加元素

将要添加的元素给k个哈希函数，得到对应于位数组上的k个位置，将这k个位置设为1

查询元素

将要查询的元素给k个哈希函数，得到对应于位数组上的k个位置，
如果k个位置有一个为0，则肯定不在集合中，如果k个位置全部为1，则可能在集合中。

删除元素

一般不能从布隆过滤器中删除元素，但是有些改进的算法支持，如Counting Bloom filter

php+Redis实现的布隆过滤器

由于Redis实现了setbit和getbit操作，天然适合实现布隆过滤器，redis也有布隆过滤器插件。

1. 安装redis插件bloom-filter

cd /usr/local/redis
wget https://github.com/RedisLabsModules/rebloom/archive/v2.2.18.tar.gz
tar -zxvf v2.2.18.tar.gz
cd RedisBloom-2.2.18
make

解压并安装，生成.so文件rebloom.so
在redis配置文件(redis.conf)中加入该模块
loadmodule /usr/local/redis/RedisBloom-2.2.18/redisbloom.so
启动redis即可 redis-server redis.conf

4. bloom-filter主要命令

bf.add 添加元素；bf.exists 查询元素是否存在；bf.madd 一次添加多个元素
在 redis 中有两个值决定布隆过滤器的准确率：
error_rate：允许布隆过滤器的错误率，这个值越低过滤器的位数组的大小越大，占用空间也就越大。
initial_size：布隆过滤器可以储存的元素个数，当实际存储的元素个数超过这个值之后，过滤器的准确率会下降。
redis 中有一个命令可以来设置这两个值：
bf.reserve test 0.1 100000000
第一个值是过滤器名字。第二个为 error_rate 的值。第三个为 initial_size 的值。
注意必须在add之前使用bf.reserve指令显式创建，如果对应的 key 已经存在，bf.reserve会报错。
同时设置的错误率越低，需要的空间越大。如果不使用 bf.reserve，默认error_rate是 0.01，默认的initial_size是 100

5. php调用

php-redis扩展中有个函数可以调用原始的redis指令：

//0.1是误判率，100000000是位向量长度
$redis->rawCommand('bf.reserve', 'test', 0.01,100000000);
//test是布隆过滤器名称，abc12345是需要判断的元素
$redis->rawCommand('bf.add', 'test', 'abc12345');
$res = $redis->rawCommand('bf.exists', 'test', 'abc12345');
var_dump($res);

添加：在向redis set值的之后，调用bf.add添加到过滤器。
检查：在经过redis去到Mysql之前，调用bf.exists检查一下，如果不存在再查询Mysql。

BloomFilter适用场景

比如 网页URL去重、垃圾邮件识别、黑名单、查询加速【比如基于KV结构的数据】、
集合元素重复的判断、缓存穿透（缓存和数据库中都没有查询数据）等场景；