布隆过滤器
布隆过滤器和HLL(HyperLogLog)比较相似，都可以做到元素去重、解决一些精确度要求不高的统计问题，
如果我们想从HLL里获取一个元素是否存在的话，HLL没有直接提供这样的方法，但是redis中的布隆提供了，
虽然用HLL的pfadd可以根据返回值是0或1，确认元素有没有添加成功，没添加成功就代表存在，但是这样会对原本的数据结构造成污染，毕竟我们只是想确认一个元素在不在，并不想把他添加进去。
应用场景
例如我们在使用爱奇艺看视频的时候，它会不停的推送新内容，每次推送内容前将过滤掉我们之前看过的内容，问题来了，爱奇艺是如何实现推荐去重的？
- 服务器记录了用户的观看历史记录，当系统推送的时候可以根据这些记录做筛选，过滤掉已存在的记录，但是在用户量很大、并且历史记录也很大的时候，这种方式性能很明显无法跟上，并且这种记录一般是存在关系型数据库当中，对数据库不停的进行 exists 查询，并发量很大的时候，数据库基本不可能扛住这种压力。
- 既然关系型数据库扛不住，那么是不是可以使用缓存？缓存的速度够快，但是缓存的空间一般很小，这种历史记录的数据还会随着时间的增长不停的增长，所以用缓存也是不合适的。
布隆过滤器就是为了解决这种场景诞生的，在起到去重过滤的同时，在空间上还能节省90%以上，只是会有一定的误判概率。
布隆过滤器是什么
布隆过滤器可以理解为一个不太精确的set结构，当使用contains方法判断某个对象是否存在时，它可能会误判，误判率可以根据参数设置尽量的降低，
当布隆过滤器说某个值存在时，这个值可能不存在，但是当他说某个值不存在时，那就真的不存在，就像它见过很多人的脸，当有另一个人的脸和它见过的人之一比较像时，它会说它认识这个人，但是如果这个人的脸它从没见过，就说明这个人从来没出现过。
套用上面的说法，布隆可以准确的过滤掉用户很多看过的内容，当然也会过滤掉一小部分用户没看过的(误判)，以此保证推送给用户的是无重复的。
redis中的布隆过滤器
redis官方提供的布隆过滤器在4.0版本时才提供，布隆作为一个插件加载到redis server中，为redis提供了强大的去重功能。
使用docker安装带有布隆过滤器的redis
docker pull redislabs/rebloom # 下载
docker run -d -p 6379:6379 --name redisbloom redislabs/rebloom # 运行
docker exec -it redisbloom /bin/bash # 进入容器内
redis-cli # 连接redis基本用法
布隆提供两个基本指令 bf.add/bf.exists ， 前者用于添加元素，后者用于判断元素是否存在，其用法和 set 集合的 sadd/sismember 差不多，
bf.add 一次只能添加一个元素，如果要添加多个，使用 bf.madd，判断多个元素是否存在使用 bf.mexists。
127.0.0.1:6379> bf.add bloom user1
(integer) 1
127.0.0.1:6379> bf.add bloom user2
(integer) 1
127.0.0.1:6379> bf.add bloom user3
(integer) 1
127.0.0.1:6379> bf.add bloom user4
(integer) 1
127.0.0.1:6379> bf.add bloom user4
(integer) 0
127.0.0.1:6379> bf.madd bloom user5 user6 user7
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists bloom user5 user6 user7 user8
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0
上面的结果似乎很准确，一个误判都没有，因为数据量还不大，我们写一个脚本增加大量数据看看，
你会发现，不论循环多少次，下面的代码永远都不会输出，因为布隆过滤器对自己见过的元素肯定不会出现误判，只会误判那些没有见过的，
我们对代码稍微做出一些修改，使用bf.exists去查找没见过的元素，看看是不是会出现已经见过的错误(误判)
可以看到下图中，在306个元素的时候，出现了误判，没有出现过的元素，被当做见过了，
误判率计算
如何验证布隆过滤器的误判率呢？ 首先随机出十万个字符串，然后切成两组，一组放到过滤器中，另一组用于判断字符串是否存在，最后我们用误判的个数和总量一半的百分比作为误判率。
可以看到下图的结果中，五万的数据，有500左右的数据被误判，也就是百分之一的误判率。
降低误判率
上面使用的布隆过滤器使用了默认的参数，它会在第一次add的时候自动创建，redis还提供了自定义参数的布隆过滤器，需要在add之前使用bf.reserve指令显式创建，
如果对应的key已经存在，bf.reserve会报错，bf.reserve有三个参数，分别是key、error_rate(错误率) 和 initial_size。
error_rate越低，需要的空间越大，initial_size表示预计放入的元素数量，当实际数量超出这个数值时，误判率会上升，所以需要提前设置一个较大的数值避免超出导致误判率升高。
如果不使用bf.reserve，默认的error_rate是0.01，默认的initial_size是100。
如下图，在设置了容量和错误率之后，误判率已经由500左右下降大20左右，大幅度的提高了正确率。
源码地址：https://github.com/qiaomengnan16/redis-demo/tree/main/redis-bloom
注意事项
布隆过滤器的inital_size设置的过大，会浪费存储空间，设置的过小，会影响准确率，用户在使用之前一定要尽可能的精确估计元素数量，还需要加上一定的冗余空间以避免实际元素可能会意外高出估计值很多。
error_rate越小，需要的存储空间越大，对于不需要精确过滤的场合，error_rate设置稍大一点也可以，例如新闻的去重，误判率高一点只会让小部分文章不能被合适的人看到，文章的整体阅读量不会因为这点误判带来巨大的改变。
布隆过滤器的其他应用
在爬虫系统中，需要对大量的URL去重，已经爬过的网页不用再爬，如果存储的URL高达百万上亿，用一个集合去存这些数据，很浪费空间，这时候使用布隆过滤器，可以大幅度降低去重存储消耗，不过同样带来少量的页面将会错过爬取。
在NOSQL中，也经常用的布隆过滤器，例如HBase、Cassandra，还有LevelDB、RocksDB内部都有布隆过滤器结构，
布隆过滤器可以显著降低数据库的IO请求数量，当用户来查询某个row时，可以先通过内存中的布隆过滤器过滤掉大量不存在的row请求，然后再去磁盘查询。
邮件系统的垃圾邮件过滤功能也普遍用到了布隆过滤器，所以平时也有某些正常的右键被放进了垃圾邮件目录中，这个就是误判导致的，概率较低。
