布隆过滤器
概述
布隆过滤器Bloom Filter是一种概率型数据结构，它高效且占用空间小，常用于判断某个元素是否在一个集合中。不过，这个结果并不是完全准确的，只是一个具有概率性的结果，只要正确使用，在足够大体量的数据中这个概率的不完全准确几乎就可以忽略不计了。
布隆过滤器用于解决缓存穿透的问题，比如故意搜索一些缓存和数据库中没有的数据、恶意穿透缓存形成对数据库的攻击。
环境安装
$ wget https://github.com/RedisBloom/RedisBloom/archive/refs/tags/v2.2.12.tar.gz
$ tar xzvf RedisBloom-2.2.12.tar.gz
$ cd RedisBloom-2.2.12
$ make原理
每一个布隆过滤器对应到Redis中就是一个位数组和几个不同的哈希函数，当我们向布隆过滤器中添加元素时会调用这几个哈希函数将算出来的几个整型索引值对应到位数组中的内容，将那几个位置的值标为1，初始时默认该位数组中所有值都是0。在判断元素是否在该集合中时，也是调用这几个哈希函数将算出来的几个整型索引值对应到位数组中的内容，判断这几个位置的数组内容是否全部为1，如果有不为1的值，那么说明该元素一定不在这个集合内，如果全部为1，则该元素很可能存在于该集合内。
误判的失败率与哈希算法计算的次数以及位数组的长度有关，数组越长，哈希算法计算次数越多、插入元素越少，误判率就越低。
计算公式如下：
$$
h ≈ 0.7 * (m / n)
$$$$
p ≈ 0.6185 ^{m / n}
$$
其中，n表示元素的数量，m代表位数组的长度，位数组越长，占用空间越大；h表示最佳的哈希函数的数量；p代表误判率。
通过上面的公式可知：位数组m越长，误判率p越低，哈希函数最佳的数量h越多，哈希函数越多，则计算花费的时间越长。
实际上，通过上面的公式可以得出：
也就是说，误判率p=0.0001%时，每个元素只占用28.8bit，就算存储100万个元素，也不过消耗27.5MB的存储空间。布隆过滤器的空间效率非常高、占用率非常低，无论是查询速度还是存储方式都相当不错。
# 创建一个误判率0.1%、可存储10000个元素的布隆过滤器
127.0.0.1:6379> bf.reserve myfilter 0.001 10000
OK
# 查看布隆过滤器
127.0.0.1:6379> bf.info myfilter
1) Capacity
2) (integer) 10000
3) Size
4) (integer) 19928
5) Number of filters
6) (integer) 1
7) Number of items inserted
8) (integer) 0
9) Expansion rate
10) (integer) 2
# 添加新元素
127.0.0.1:6379> bf.add myfilter key1
(integer) 1
# 判断元素是否在集合内
127.0.0.1:6489> bf.exists myfilter key1
(integer) 1