Redis笔记-布隆过滤器组件 什么是布隆过滤器 使用场景 Redis中的布隆过滤器 安装插件 基本使用 注意事项 原理 空间占用估计 布隆过滤器的其它应用
布隆过滤器（Bloom Filter）是一种比较巧妙的概率型数据结构，它可以告诉你某种东西一定不存在或者可能存在。当布隆过滤器说，某种东西存在时，这种东西可能不存在；当布隆过滤器说，某种东西不存在时，那么这种东西一定不存在。
布隆过滤器相对于Set、Map 等数据结构来说，它可以更高效地插入和查询，并且占用空间更少，它也有缺点，就是判断某种东西是否存在时，可能会被误判。但是只要参数设置的合理，它的精确度也可以控制的相对精确，只会有小小的误判概率。
使用场景
解决缓存穿透，首先对所有可能查询的参数以hash形式存储，当用户想要查询的时候，使用布隆过滤器发现不在集合中，就直接丢弃，不再对持久层查询。
Redis中的布隆过滤器
之前的布隆过滤器可以使用Redis中的位图操作实现，直到Redis4.0版本提供了插件功能，Redis官方提供的布隆过滤器才正式登场。布隆过滤器作为一个插件加载到Redis Server中，就会给Redis提供了强大的布隆去重功能。
安装插件
下载：
git clone https://github.com/RedisBloom/RedisBloom.git
安装：
cd RedisBloom
make # 编译后生成redisbloom.so
修改配置文件
vim /usr/local/bin/redis.conf
loadmodule /application/RedisBloom/redisbloom.so #添加
重启：
./redis-server redis.conf
基本使用
bf.add添加元素，如果不存在就自动创建
bf.add blackuser 1
bf.madd一次添加多个元素
bf.add blackuser 1 2 3 4 5
bf.reserve
布隆过滤器在第一次add的时候自动创建基于默认参数的过滤器，Redis还提供了自定义参数的布隆过滤器。
在add之前使用bf.reserve指令显式创建，其有3个参数，key，error_rate， initial_size，错误率越低，需要的空间越大，error_rate表示预计错误率，initial_size参数表示预计放入的元素数量，当实际数量超过这个值时，误判率会上升，所以需要提前设置一个较大的数值来避免超出。默认的error_rate是0.01，initial_size是100。
bf.reserve blackuser 0.01 10000
bf.exists查询元素是否存在
bf.exists blackuser 2
bf.mexists一次查询多个元素。
bf.mexists blackuser 1 2 3 4
注意事项
initial_size估计的过大会浪费存储空间，因此在使用前要尽可能精确估计好元素数量+冗余空间。
error_rate越小，需要的存储空间越大。
原理
每个布隆过滤器对应到Redis的数据结构中就是一个大型的位数组和几个不同的无偏hash函数，无偏表示分布均匀。
添加key时，使用多个hash函数对key进行hash运算得到一个整数索引值，对位数组长度进行取模运算得到一个位置，每个hash函数都会得到一个不同的位置，将这几个位置都置1就完成了add操作。
查询同理，只要有一位是0就表示这个key不存在，但如果都是1，则不一定存在对应的key。
空间占用估计
布隆过滤器的空间占用有一个简单的计算公式，但推导比较繁琐。布隆过滤器有两个参数，预计元素数量n，错误率f，公式得到两个输出，位数组长度L（即存储空间大小bit），hash函数的最佳数量k。
布隆过滤器的其它应用
解决缓存穿透：
般情况下，先查询缓存是否有该条数据，缓存中没有时，再查询数据库。当数据库也不存在该条数据时，每次查询都要访问数据库，这就是缓存穿透。缓存穿透带来的问题是，当有大量请求查询数据库不存在的数据时，就会给数据库带来压力，甚至会拖垮数据库。
可以使用布隆过滤器解决缓存穿透的问题，把已存在数据的key存在布隆过滤器中。当有新的请求时，先到布隆过滤器中查询是否存在，如果不存在该条数据直接返回；如果存在该条数据再查询缓存查询数据库。
黑名单
发现存在黑名单中的，就执行特定操作。比如：识别垃圾邮件，只要是邮箱在黑名单中的邮件，就识别为垃圾邮件。假设黑名单的数量是数以亿计的，存放起来就是非常耗费存储空间的，布隆过滤器则是一个较好的解决方案。把所有黑名单都放在布隆过滤器中，再收到邮件时，判断邮件地址是否在布隆过滤器中即可。