写在前面

写在前面
本篇来聊一聊Redis中的布隆过滤器，主要包括布隆过滤器原理、Redis集成布隆过滤器以及一个demo实战。

业务场景

在实际开发过程中遇到过这种情况，用户在使用APP阅读文章时，如何做到每次推荐给该用户的文章不重复，即需要过滤掉他已经阅读过的文章。

此时有人可能会说我们可以记录每个用户的浏览历史，然后每次在推荐的时候查询用户的浏览记录并进行过滤，进而实现文章的去重。如果开发者将用户的浏览历史存储在关系型数据库中，那么就需要频繁的对数据库进行exists判断，在并发量不高的情况下还能正常响应，但是一旦并发量上来，数据库是扛不住的。

那么又有人说，可以将这些浏览历史存在缓存中。请注意，千万不要将它们存在缓存中，这样会浪费很多内存，而且缓存适合更新频率比较低的情况，而用户的浏览历史可能每时每刻都在变化。

针对上述情况，即遇到数据量较大，又需要去重的时候，就可以考虑使用布隆过滤器。一般来说，布隆过滤器适用于如下场景：
（1）解决Redis中缓存穿透问题；
（2）爬虫过滤，对爬虫爬过的网站进行过滤，爬过的不再爬取；
（3）内容推荐，对已经推荐过的内容进行过滤，不再推荐；
（4）邮件过滤，对邮件设置的黑名单进行过滤；
……

布隆过滤器简介

布隆过滤器 (Bloom Filter)由Burton Howard Bloom于1970年提出，它是一种 space efficient 的概率型数据结构，用于判断一个元素是否在集合中。

如果布隆过滤器说某个数据存在，那么这个数据实际上可能不存在；但是如果说某个数据不存在，那么此时这个数据一定不存在，即一种概率性的判断。

你可能会说判断元素是否在集合中，最简单的可以使用哈希表，但是完成同样问题时，布隆过滤器只需哈希表的1/8或1/4的空间复杂度。

请注意，布隆过滤器可以插入元素，但是不可以删除已有元素。而且布隆过滤器中的元素越多，那么false positive rate(误报率)越大，不过不会发生 false negative (漏报)。

布隆过滤器原理

首先看下面一张图，快速了解一下布隆过滤器的原理：

首先分配一块内存空间做bit数组，数组的bit位初始值均为0。

接着往其中添加元素时，采用K个相互独立的 Hash 函数计算，然后将元素Hash 映射的K个位置全部设置为1。

当需要检测元素是否存在，会使用这K个 Hash 函数计算出 K 个位置，如果位置全部为1，则说明元素存在；否则不存在。

由于哈希函数会出现碰撞，因此布隆过滤器也存在误判。一般我们会使用误判率，而误判率是指布隆过滤器判断某个 key 存在，但它实际不存在的概率，因为它存的是 key 的 Hash 值，而非 key 的值。因此有概率存在这样的 key，它们内容不同，但经过多次 Hash 后的 Hash 值相同。

布隆过滤器判断某个元素不存在，那么这个元素必定不存在；判断某个元素存在，那么这个元素可能不存在。可以使用反证法进行验证，如果元素存在，那么它每次Hash计算后的Hash值位置必然为1，而不是0。

前面说了，可以往布隆过滤器中插入元素，但是不可以删除已有元素，为什么是这样呢？我们知道，删除意味着需要将对应的K个bit位置设置为0，而这些有可能是其他元素对应的bit，因此删除会发生false negative (漏报)，这是不允许的。

Redis集成布隆过滤器

Redis在4.0的时候官方提供插件机制，用于提供对布隆过滤器的支持。开发者可以点击 这里 下载：

使用布隆过滤器最低需要4.x版本，不过笔者建议使用6.x版本。

下载

开发者可以自行编译安装，从 github 下载，笔者使用的 release 版本是 v2.2.18，下载地址 点击 这里：

之后将其进行解压，编译：

1
2
3
tar -zxvf RedisBloom-2.2.18.tar
cd RedisBloom-2.2.18
make

之后会生成一个名为redisbloom.so的文件，那么接下来我们就是安装集成它了。

修改redis.conf文件，在里面新增一个loadmodule，值为上面生成的redisbloom.so文件的全路径：

1
2
# 集成BloomFilter
loadmodule /home/envy/RedisBloom-2.2.18/redisbloom.so

之后重启Redis，注意如果是Redis集群，那么每个实例的配置文件都需要加入该配置项。

启动的时候我们需要以指定配置文件启动Redis，进入到Redis的bin目录：

1
./redis-server ../conf/redis.conf

然后使用客户端连接到Redis，开始进行测试。布隆过滤器常用的命令如下：

1
2
3
4
5
6
7
8
# 添加一个元素到布隆过滤器
BF.ADD element bloomfilter
# 判断元素是否在布隆过滤器中
BF.EXISTS element bloomfilter
# 添加多个元素到布隆过滤器
BF.MADD element1 element2 bloomfilter
# 判断多个元素是否在布隆过滤器
BF.MEXISTS element1 element2 bloomfilter

测试结果如下所示：

Redis布隆过滤器实战

前面也说过，在Redis中布隆过滤器常用的作用就是解决缓存穿透问题，所谓的缓存穿透是指请求查询不存在的数据，即缓存和数据库中都没有的数据。

接下来我们模拟一个场景：用户在购买商品创建订单时，我们会往MQ中发送消息，将订单ID添加到布隆过滤器中，之后判断订单是否存在。整个流程如下所示：

BF.RESERVE命令详解

前面的过程我们不编写具体的代码，而是通过一些数据来模拟对应的操作。首先我们来了解BF.RESERVE命令：

1
BF.RESERVE {key} {error_rate} {capacity} [EXPANSION {expansion}] [NONSCALING]

解释一下上述参数的含义：
（1）key是布隆过滤器的名称；
（2）error_rate是期望的错误率，默认值为0.1，值越低需要的空间就越大；
（3）capacity是初始容量，默认值为100，当实际元素的数量超出这个初始容量值时，错误率会上升；
（4）EXPANSION 是可选参数，当添加到布隆过滤器中的元素数量达到初始容量后，不会扩容过滤器，并且会抛出异常（(error) ERR non scaling filter is full）。这说明布隆过滤器的扩容是通过增加布隆过滤器的层数来完成的。每增加一层，查询时就可能会遍历多层布隆过滤器，默认情况下每一层的容量都是上一层的两倍。

请注意，如果不使用BF.RESERVE命令来创建布隆过滤器，而使用Redis自动创建的布隆过滤器，那么默认的error_rate为0.1，初始容量为100。

布隆过滤器的error_rate越小，需要的存储空间就越大，对于不需要过于精确的业务场景来说，error_rate的值可以设置大一些。

布隆过滤器的capacity设置的过大，会浪费存储空间；设置过小会影响准确率，因此在使用布隆过滤器之前，最好尽可能的精确估计元素的数量，同时加上一定的冗余空间，这样可避免实际元素会超出设定值很多的情况。

创建orders布隆过滤器

接下来我们使用BF.RESERVE命令来手动创建一个名为orders的布隆过滤器，注意error_rate为0.1，初始容量为1000万：

1
BF.RESERVE orders 0.1 10000000

添加订单ID到布隆过滤器

接下来我们尝试使用BF.ADD命令往orders这一布隆过滤器中添加10010这一订单号：

1
BF.ADD orders 10010

执行结果如下所示：

1
2
192.168.51.131:0>BF.ADD orders 10010
"1"

当然了也可以一次性添加三个订单号：

1
BF.MADD orders 10011 10012 10013

执行结果如下所示：

1
2
3
4
192.168.51.131:0>BF.MADD orders 10011 10012 10013
 1)  "1"
 2)  "1"
 3)  "1"

判断订单是否存在

开发者可以使用BF.EXISTS命令来判断某一元素是否存在于布隆过滤器中，返回值为1表示存在:

1
BF.EXISTS key element

举个例子，判断订单号为10011的订单是否存在orders这一布隆过滤器中：

1
2
192.168.51.131:0>BF.EXISTS orders 10011
"1"

如果想要批量检查多个元素是否在布隆过滤器中，可以使用BF.MEXISTS命令，该命令返回的是一个数组，其中1表示存在，0表示不存在：

1
BF.EXISTS key element1 element2......

举个例子，判断订单号为10011、10012、10013和10014的订单是否存在orders这一布隆过滤器中：

1
2
3
4
5
192.168.51.131:0>BF.MEXISTS orders 10011 10012 10013 10014
 1)  "1"
 2)  "1"
 3)  "1"
 4)  "0"

也就是说我们可以通过BF.RESERVE、BF.ADD和BF.EXISTS这三个命令来避免缓存穿透问题。

查看创建的布隆过滤器信息

开发者可以使用BF.INFO key命令来查看创建的布隆过滤器信息：

1
2
3
4
5
6
7
8
9
10
11
192.168.51.131:0>BF.INFO orders
 1)  "Capacity"
 2)  "10000000"
 3)  "Size"
 4)  "7794184"
 5)  "Number of filters"
 6)  "1"
 7)  "Number of items inserted"
 8)  "4"
 9)  "Expansion rate"
 10)  "2"

解释一下上述返回值的含义：
（1）Capacity表示预设容量，即初始容量；
（2）Size表示实际占用情况，但如何计算需要进一步确认；
（3）Number of filters表示过滤器层数；
（4）Number of items inserted表示已经实际插入的元素数量；
（5）Expansion rate表示子过滤器扩容系数（默认值为2）。

无法删除布隆过滤器

目前布隆过滤器是无法删除的，但是布谷过滤器(Cuckoo Filter)支持删除。

布隆过滤器在插入项目时通常表现出更好的性能和可伸缩性，因此如果开发者经常向数据集中添加元素，那么此时布隆过滤器还可以接受。不过布谷过滤器在检查操作上更快，也支持删除，可以点击 这里 进行阅读。实际上本篇文章中的实战就来自于Redis官方提供的Redis布隆过滤器实战，可以点击 这里 进行阅读。

Redission布隆过滤器实战

RBloomFilter接口

在Redisson中，与BloomFilter相关的操作都被定义到RBloomFilter接口中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public interface RBloomFilter<T> extends RExpirable {
    //添加元素
    boolean add(T object);
  
    //判断元素是否存在
    boolean contains(T object);

    //根据指定的参数来初始化布隆过滤器
    boolean tryInit(long expectedInsertions, double falseProbability);

    //在布隆过滤器初始化期间计算，返回每个元素的预期插入量
    long getExpectedInsertions();

    //在布隆过滤器初始化期间计算，返回元素存在的错误概率
    double getFalseProbability();

    //返回此实例所需的Redis内存中的bit数
    long getSize();

    //在布隆过滤器初始化期间计算，返回每个元素使用的哈希迭代次数
    int getHashIterations();

    //计算已添加到布隆过滤器的元素的概率数
    long count();
}

第一步，创建一个名为redisson-fly的SpringBoot项目，注意后续关于其他数据结构的代码都在这个项目中进行编写：

第二步，在POM文件中新增如下依赖：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
<dependencies>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter</artifactId>
    </dependency>
    <dependency>
        <groupId>org.redisson</groupId>
        <artifactId>redisson-spring-boot-starter</artifactId>
        <version>3.13.6</version>
    </dependency>
    <dependency>
        <groupId>org.projectlombok</groupId>
        <artifactId>lombok</artifactId>
        <optional>true</optional>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-test</artifactId>
    </dependency>
    <dependency>
        <groupId>junit</groupId>
        <artifactId>junit</artifactId>
        <scope>test</scope>
    </dependency>
</dependencies>

第三步，在application.yml配置文件中新增如下配置项：

1
2
3
4
5
6
7
8
9
server:
  port: 9001
spring:
  redis:
    host: 192.168.51.131
    port: 6379
    ssl: false
    password: envy123
    database: 0

第四步，由于这里我们不对外提供接口，因此我们只创建service类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@Service
public class BoolFilterService {
    @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;
    }
}

第五步，针对这个BoolFilterService类创建对应的测试类及测试方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
@Slf4j
@RunWith(SpringRunner.class)
@SpringBootTest
public class BoolFilterServiceTest {
    @Autowired
    private BoolFilterService boolFilterService;

    @Test
    public void testBloomFilter(){
        //布隆过滤器名称
        String bloomFilterName = "ipBlackList";
        //初始容量
        long expectedInsertions = 10000L;
        //误判率
        double falseProbability = 0.01;
        RBloomFilter<Long> bloomFilter = boolFilterService.create(bloomFilterName, expectedInsertions, falseProbability);

        //往布隆过滤器中添加元素
        for (long i = 0; i < expectedInsertions; i++) {
            bloomFilter.add(i);
        }
        long elementCount = bloomFilter.count();
        log.info("布隆过滤器中的元素个数为：{}",elementCount);

        //统计布隆过滤器中误判次数，即实际上不存在但是布隆过滤器却说存在的次数
        int count = 0;
        for (long i = expectedInsertions; i < expectedInsertions * 2; i++) {
            if(bloomFilter.contains(i)){
                count++;
            }
        }
        log.info("布隆过滤器中的误判次数为：{}",count);
        //删除布隆过滤器
        bloomFilter.delete();
    }
}

我们测试逻辑非常简单，定义一个名为ipBlackList的布隆过滤器，然后设置初始容量为10000，误判率为0.01。然后往里面添加0-10000这些数字，接着我们判断10001到20000是否在这个ipBlackList中，进而得到误判的次数。

当然了，如果上面使用的是Redis集群，那么需要使用如下命令来初始化布隆过滤器：

1
RClusteredBloomFilter<Long > bloomFilter = redisson.getClusteredBloomFilter("redisCluster");

运行该测试方法，可以看到结果如下所示：

1
2
c.k.r.service.BoolFilterServiceTest      : 布隆过滤器中的元素个数为：9895
c.k.r.service.BoolFilterServiceTest      : 布隆过滤器中的误判次数为：259

可以看到是比较符合我们预定的误判率。

总结

布隆过滤器的思想就是判断元素可能存在或者一定不存在，因此在使用时需要结合实际情况进行分析。

参考资料：Redis 布隆（Bloom Filter）过滤器原理与实战、Redis官方文档。