当你，如下场景：
-
解决Redis 缓存穿透(面试重点)；
-
使用布隆过滤器过滤邮件黑名单；
-
爬虫爬网站过滤，爬网站不再爬；
-
不再推荐推荐的新闻；
布隆过滤器是什么？
布隆过滤器 (Bloom Filter)是由 Burton Howard Bloom 于 1970 年提出，。
当布隆过滤器说，
哈希表也可以用来判断元素是否集中，但布隆过滤器只需要哈希表 1/8 或 1/4 同样的问题可以通过空间复杂性来完成。
元素越多，false positive rate(误报率)越大，但是 false negative (漏报)是不可能的。
布隆过滤器原理
BloomFilter 算法是首先分配一个内存空间 bit 数组，数组 bit 所有的初始值都设为 0。
添加元素时，使用 k 彼此独立 Hash 函数计算，然后将元素 Hash 映射的 K 所有位置都设置为 1。
检测 key 是否存在，还是用这个 k 个 Hash 函数计算出 k 如果所有位置都是个位置， 1，则表明 key 存在，否则不存在。
如下图所示：
布隆过滤器原理
这里的误判率是指，BloomFilter 判断某个 key 它存在，但它实际上不存在，因为它存在 key 的 Hash 值，而非 key 的值。
因此，有可能存在这种情况 key，它们有不同的内容，但很多次 Hash 后的 Hash 值都相同。
为什么码哥不允许删除元素？
删除意味着需要删除相应的 k 个 bits 位置设置为 0，可能是其他元素对应的位置。
因此 remove 会引入 false negative，这是绝对不允许的。
Redis 集成布隆过滤器
Redis 4.0 当官方提供插件机制时，布隆过滤器正式出现。以下网站可以下载官方编译的可扩展模块。
https://redis.com/redis-enterprise-software/download-center/modules/
RedisModules
弟弟推荐使用 Redis 版本 6.x，最低 4.x 集成布隆过滤器。查看下面的指令。码哥安装的版本是 6.2.6。
redis-server-v Redisserverv=6.2.6sha=00000000:0malloc=libcbits=64build=b5524b65e12bbef5 下载
我们需要自己编译和安装 github 下载，目前 release 版本是 v2.2.14、下载地址：https://github.com/RedisBloom/RedisBloom/releases/tag/v2.2.14
Redis 布隆
解压编译
解压
tar-zxvfRedisBloom-2.2.14.tar 编译插件
cdRedisBloom-2.2.14 make 成功的编译，就会看到redisbloom.so文件。
安装集成
需要修改 redis.conf 文件，新增loadmodule并重启配置 Redis。
loadmodule/opt/app/RedisBloom-2.2.14/redisbloom.so module 配置
指定配置文件并启动 Redis：
redis-server /opt/app/redis-6.2.6/redis.conf
加载成功的页面如下：
成功加载布隆过滤器
客户端连接 Redis 测试。
BF.ADD--在布隆素到布隆过滤器 BF.EXISTS--判断元素是否在布隆过滤器中 BF.MADD--在布隆过滤器中添加多个元素 BF.MEXISTS--判断布隆过滤器中是否有多个元素 测试
Redis 实战布隆过滤器
用布隆过滤器解决缓存穿透问题，缓存穿透：有特殊要求查询不存在的数据，
当用户购买商品并创建订单时，我们经常 mq 发送消息，把订单 ID 加入布隆过滤器。
订单同步到布隆过滤器
在添加布隆过滤器之前，我们通过它BF.RESERVE命令手动创建名称orderserror_rate = 0.1 ，初始容量为 10000000 布隆过滤器：
#BF.RESERVE{key}{error_rate}{capacity}[EXPANSION{expansion}][NONSCALING] BF.RESERVEorders0.110000000 -
key：filter 的名字；
-
error_rate：预期错误率，默认 0.1.值越低，空间越大；
-
capacity：初始容量，默认 当实际元素数量超过这个初始化容量时，误判率就会上升。
-
EXPANSION：可选参数，当添加到布隆过滤器中的数据达到初始容量时，布隆过滤器会自动创建子过滤器，乘以最后一个过滤器的大小 expansion；expansion 的默认值是 2.也就是说，布隆过滤器的扩容是默认的 2 倍扩容；
-
NONSCALING：设置此项后，当添加到布隆过滤器中的数据达到初始容量时，可选参数不会扩大过滤器，并会抛出异常（(error) ERR non scaling filter is full） 说明：BloomFilter 扩容是通过增加 BloomFilter 层数完成。每增加一层，查询时可能会遍历多层 BloomFilter 每层的容量是上层的两倍(默认)。
如果不使用BF.RESERVE创建命令，而是使用 Redis 布隆过滤器自动创建，
布隆过滤器 error_rate 存储空间越小，不需要太准确的场景，error_rate 设置稍大一点也可以。
布隆过滤器 capacity 如果设置太大，会浪费存储空间。如果设置太小，会影响准确性。因此，在使用前，必须尽可能准确地估计元素的数量，并增加一定的冗余空间，以避免实际元素意外高于设置值。
添加订单 ID 到过滤器
#BF.ADD{key}{item} BF.ADDorders10086 (integer)1 使用BF.ADD向名称为orders添加布隆过滤器 10086 这个元素。
若同时添加多个元素，则使用BF.MADD key {item ...}，如下：
BF.MADDrders 10087 10089
1) (integer) 1
2) (integer) 1
判断订单是否存在
# BF.EXISTS {key} {item}
BF.EXISTS orders 10086
(integer) 1
BF.EXISTS 判断一个元素是否存在于BloomFilter，返回值 = 1 表示存在。
如果需要批量检查多个元素是否存在于布隆过滤器则使用 BF.MEXISTS，返回值是一个数组：
-
1：存在；
-
0：不存在。
# BF.MEXISTS {key} {item}
BF.MEXISTS orders 100 10089
1) (integer) 0
2) (integer) 1
总体说，我们通过BF.RESERVE、BF.ADD、BF.EXISTS三个指令就能实现避免缓存穿透问题。
码哥，如何查看创建的布隆过滤器信息呢？
用 BF.INFO key查看，如下：
BF.INFO orders
1) Capacity
2) (integer) 10000000
3) Size
4) (integer) 7794184
5) Number of filters
6) (integer) 1
7) Number of items inserted
8) (integer) 3
9) Expansion rate
10) (integer) 2
返回值：
-
Capacity：预设容量；
-
Size：实际占用情况，但如何计算待进一步确认；
-
Number of filters：过滤器层数；
-
Number of items inserted：已经实际插入的元素数量；
-
Expansion rate：子过滤器扩容系数（默认 2）；
码哥，如何删除布隆过滤器呢？
目前布隆过滤器不支持删除，布谷过滤器Cuckoo Filter是支持删除的。
Bloom 过滤器在插入项目时通常表现出更好的性能和可伸缩性（因此，如果您经常向数据集添加项目，那么 Bloom 过滤器可能是理想的）。布谷鸟过滤器在检查操作上更快，也允许删除。
大家有兴趣可可以看下：https://oss.redis.com/redisbloom/Cuckoo_Commands/)
码哥，我想知道你是如何掌握这么多技术呢？
其实我也是翻阅官方文档并做一些简单加工而已，这篇的文章内容实战就是基于 Redis 官方文档上面的例子：https://oss.redis.com/redisbloom/。
大家遇到问题一定要耐心的从官方文档寻找答案，培养自己的阅读和定位问题的能力。
Redission 布隆过滤器实战
码哥的样例代码基于 Spring Boot 2.1.4，代码地址：https://github.com/MageByte-Zero/springboot-parent-pom。
添加 Redission 依赖：
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson-spring-boot-starter</artifactId>
<version>3.16.7</version>
</dependency>
使用 Spring boot 默认的 Redis 配置方式配置 Redission：
spring:
application:
name: redission
redis:
host: 127.0.0.1
port: 6379
ssl: false
创建布隆过滤器
@Service
public class BloomFilterService {
@Autowired
private RedissonClient redissonClient;
/**
* 创建布隆过滤器
* @param filterName 过滤器名称
* @param expectedInsertions 预测插入数量
* @param falseProbability 误判率
* @param <T>
* @return
*/
public <T> RBloomFilter<T> create(String filterName, long expectedInsertions, double falseProbability) {
RBloomFilter<T> bloomFilter = redissonClient.getBloomFilter(filterName);
bloomFilter.tryInit(expectedInsertions, falseProbability);
return bloomFilter;
}
}
单元测试
@Slf4j
@RunWith(SpringRunner.class)
@SpringBootTest(classes = RedissionApplication.class)
public class BloomFilterTest {
@Autowired
private BloomFilterService bloomFilterService;
@Test
public void testBloomFilter() {
// 预期插入数量
long expectedInsertions = 10000L;
// 错误比率
double falseProbability = 0.01;
RBloomFilter<Long> bloomFilter = bloomFilterService.create("ipBlackList", expectedInsertions, falseProbability);
// 布隆过滤器增加元素
for (long i = 0; i < expectedInsertions; i++) {
bloomFilter.add(i);
}
long elementCount = bloomFilter.count();
log.info("elementCount = {}.", elementCount);
// 统计误判次数
int count = 0;
for (long i = expectedInsertions; i < expectedInsertions * 2; i++) {
if (bloomFilter.contains(i)) {
count++;
}
}
log.info("误判次数 = {}.", count);
bloomFilter.delete();
}
}
注意事项：如果是 Redis Cluster 集群，则需要 RClusteredBloomFilter<SomeObject> bloomFilter = redisson.getClusteredBloomFilter("sample");