Redis中的布隆过滤器

一、前戏

Redis提供了HyperLogLog来解精确度不是很高的统计需求，相比set空间减少了很多，也更方便，但是HyperLogLog只是提供了pfadd添加元素,pfcount统计元素，基于HyperLogLog数据结构的实现，无法判断某个数是否存在与这个key中，故没有pfcontain这种指令一说。
举个栗子，当我们刷短视频时，会不停的给我们推荐视频，它每次推荐都需要进行去重，去掉那些我们已经看到过的视频，那么像人均一天刷100个视频/小时，这种数据该怎么去重了，
假如服务端记录每个人的浏览记录，需要查询时再从这个集合中过滤掉已经存在的记录，如果存在关系型数据库当中，每次进行大量的exists查询，存在缓存当中，假如每个人每天存一个key，用户量很大，数据量很大时，推荐的去重性能能跟的上么，存储空间会随着时间线性增长。
基于这种大数据量的去重问题，布隆过滤器（Bloom Filter）闪亮登场，它就是专门解决这种去重问题的，在去重的同时，存储空间可以减少90%以上，但是布隆过滤器也不是那么的准确，存在一定的误判率。

二、布隆过滤器介绍

布隆过滤器可以看成一个不怎么精确的set结构，当使用contains方法判断某个值是否存在时，它可能会误判，默认布隆过滤器实际上是一个很长的二进制向量或者位图和一系列的随机映射函数组成，初始状态，给定长度的位数组所有位置都位1。

向布隆过滤器中添加元素时，会使用多个hash函数对元素算得一个整数索引值，然后对位数组进行取模运算得到一个位置，每个hash函数都会算得一个不同的位置，，再把位数组的这个位置设置为1，就完成了添加操作。

1. 将要添加的元素给k个哈希函数
   2.得到位于位数组的k个位置
   3.将位数组这k个位置设置为1
   向布隆过滤器中查询是否存在某个元素时也一样，根据这些hash函数把这几个位置算出来，算完查看对应值是否为1，只要有一个位为0，那么说明这个元素一定不在布隆过滤器当中，如果所有位的值都为1，这并不能说明这个值一定存在，因为某个位置的1可能是其他元素hash运算出来的，所以会发生误判。因为不确定这个位的1是哪个元素产生并置为1的，（所以布隆过滤器没有删除操作，删除某个位的1可能导致其他元素不准确，增大了误判率）如果这个位数组比较稀疏，这个概率就会很大， 相反，如果这个位数组比较密集，这个概率就会很低
   1.将要查询的元素给k个哈希函数
   2.得到位于位数组的k个位置
   3.判断k个位置是否全部位1，如果全部为1，可能存在，如果有一位为0，则一定不存在
   布隆过滤器的优缺点：
   一个事物不可能好的不得了，凡事都有优缺点，只是孰轻孰重由自己判读，布隆过滤器的优点在于相比其他数据结构，空间和时间都存在巨大优势，由于Redis的最开始是由位数字实现的，占用的空间可以很小，存储和查询的时间都位O(1)，散列函数相互没有关系，方便由硬件并行实现，布隆过滤器并不需要存储元素本身，所以在需要相对保密的场合也有一定优势。
   缺点：随着元素的增加，误算率会随之增加，在需要绝对精确的场合，以及小量数据情况下，不推荐使用布隆过滤器。
   三、redis使用
   Redis官方提供的布隆过滤器到了Redis4.0之后提供了插件功能之后正式登场，布隆过滤器作为一个插件加载到Redis server当中，给redis提供了强大的去重功能。
   Docker安装：
   https://hub.docker.com/r/redislabs/rebloom

docker pull redislabs/rebloom
docker run -p6379:6379 redislabs/rebloom
redis-cli

命令：
添加元素

bf.add key ...options...

返回值为1表示添加成功,bf.add一次只能插入一个元素，如果想插入多个，可以使用下面这个命令

bf.madd key ...options...

查询某个元素是否已经存在

bf.exists key ...options...

如果想一次性查询多个元素，使用下面的命令

bf.mexists key ...options...

bf.info key [CAPACITY | SIZE | FILTERS | ITEMS | EXPANSION]
查看过滤器的信息