布隆过滤器

TrumanWong

4/7/2022

概述

布隆过滤器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模块中。

# 将redisbloom.so文件移动到创建的模块目录中
$ mv redisbloom.so /path/to/
# 修改配置文件redis.conf，加上下面这行代码
# loadmodule /path/to/redisbloom.so
# 重启redis
$ systemctl restart redis

原理

每一个布隆过滤器对应到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

应用场景

避免爬虫爬到重复内容可以将爬虫爬过的URL放入布隆过滤器中，爬虫每次爬取之前先判断目标URL是否在布隆过滤器中，如果在就不需要重复爬取，否则就执行爬取操作
垃圾邮件过滤黑名单可以把黑名单用户信息存储在布隆过滤器中。当收到邮件之后，判断发件人是否在布隆过滤器中，如果在，就将此邮件过滤掉。白名单亦是如此。
避免消息推送给相同的人将发送过消息的用户名单存放在布隆过滤器中，下次发送此消息时若用户名在布隆过滤器中则不需要重新发送。
解决缓存穿透等缓存问题具体解决方案可以查看缓存穿透、缓存击穿和缓存雪崩详解一文。

#Redis