布隆过滤器

5.12 布隆过滤器

5.12.1 概述

**布隆过滤器（Bloom Filter）**是一种空间高效的数据结构，用于判断一个元素是否在集合中。它由布隆在1970年提出，因此得名。

布隆过滤器的基本思想是，利用多个不同的哈希函数将一个元素映射到多个不同的位（或桶）上，并将这些位设置为1。当查询一个元素是否在布隆过滤器中时，将这个元素进行哈希操作，得到多个哈希值，并检查这些哈希值对应的位是否都为1。如果有任意一个位为0，则可以确定该元素不在布隆过滤器中；如果所有位都为1，则不能确定该元素一定在布隆过滤器中，因为可能存在哈希冲突，即不同的元素被映射到了相同的位上。

可以简单地将布隆过滤器理解为Set集合（其实他们之间差别还是很大的），可以向里边存放元素，然后判断元素是否存在。

布隆过滤器的优点：

• 时间复杂度低，增加和查询元素的时间复杂为O(N)，（N为哈希函数的个数，通常情况比较小）
• 保密性强，布隆过滤器不存储元素本身
• 存储空间小，如果允许存在一定的误判，布隆过滤器是非常节省空间的（相比其他数据结构如Set集合）（存在一种叠加）

布隆过滤器的缺点：

• 有一定的误判率，但是可以通过调整参数来降低

• 无法获取元素本身，只能判断是否存在

• 很难删除元素

适用场景

• 解决Redis缓存穿透问题
• 网络爬虫的网址去重
• 数据库中的数据查询优化
• 内容推荐，推荐过的不重复推荐

5.12.2 布隆过滤器的原理

如上图，同一个数据经过三个不同的哈希函数获得不同的存储位置，然后将对应索引里的值改为1，只有三个索引对应的值都为1才能说明值已存在，有其中一个不为1都不行。可以试想，当哈市算法为1时，一个数据只对应一个索引，只要那个索引值为1就说明存在，由于哈希冲突的存在，出现误判的可能性是较大的，随着哈希函数数量增多，所需要的储存空间也越多，一个数值需要判断的索引也越多，自然出现误判的几率就小了。（存储01的为二进制数组）

当有多个数值存储时，就是下图的叠加情况

所以这也是为什么很难删除的原因，因为多个数值可能会用到同一索引，一旦删除其中一个就会导致严重误删。

小结：

• 哈希函数越多，所需存储空间越大，计算时间越长，误判率越低

空间计算

布隆过滤器提供两个参数，一个是预计存储元素个数n，一个是误判率。在添加元素之前，布隆过滤器有着初始的存储空间，也就是二进制数组的长度。当添加元素时，布隆过滤器会根据我们填入的这两个参数计算出二进制数组的大小以及hash函数的个数，既要满足我们的要求，又要使空间和计算量的开销都减到最小。

布隆过滤器在线计算的网址：https://krisives.github.io/bloom-calculator/

5.12.3 Redis集成布隆过滤器

这里先介绍使用Docker安装的，所以前置条件是你装了Docker

Redis的安装这里就不再赘述了，没有安装的去安装

1. 下载RedisBloom镜像

   docker pull redislabs/rebloom
   1

2. 启动RedisBloom容器：使用以下命令启动RedisBloom容器：

   docker run -d --name redisbloom --link redis:redis redislabs/rebloom
   1

   这将在后台启动一个名为“redisbloom”的容器，并将它链接到名为“redis”的容器。

3. 连接到RedisBloom容器：使用以下命令连接到RedisBloom容器：

   docker exec -it redisbloom sh
   1

   这将进入RedisBloom容器的命令行界面。

4. 加载RedisBloom模块：在RedisBloom容器中，使用以下命令加载RedisBloom模块：

   redis-cli module load /usr/lib/redis/modules/rebloom.so
   1

   这将加载RedisBloom模块并准备好在Redis中使用。

安装完之后就可以在Redis中使用RedisBloom模块中提供的命令来创建布隆过滤器并执行其他操作。需要注意的是，Redis和RedisBloon的数据都是在内存运行的，所以一旦如果停止了Redis容器或RedisBloom容器，所有数据将被清除。如果需要保存数据就得做持久化操作。（具体怎么操作看Docker一章）

RedisBloom模块常见指令

1. BF.RESERVE: 创建一个新的布隆过滤器。

2. BF.ADD: 将元素添加到布隆过滤器中。

3. BF.MADD: 将多个元素添加到布隆过滤器中。

4. BF.EXISTS: 检查元素是否存在于布隆过滤器中。

5. BF.MEXISTS: 检查多个元素是否都存在于布隆过滤器中。

6. BF.INFO: 获取布隆过滤器的信息，如误判率和元素数量等。

7. BF.COUNT: 获取布隆过滤器中添加的元素数量。

8. BF.SCANDUMP: 以二进制格式返回整个布隆过滤器的数据。

9. BF.LOADCHUNK: 将二进制数据块加载到布隆过滤器中。

10. BF.CLEAR: 清空布隆过滤器中的所有元素。

这些命令可以在Redis客户端中使用，也可以通过Redis命令行界面或编程语言中的Redis客户端库来使用。在使用RedisBloom模块的命令时，需要使用正确的布隆过滤器名称和参数，还需要根据实际情况来选择合适的误判率和布隆过滤器大小。

5.12.4 在SpringBoot中使用

1. 添加依赖

<dependency>
   <groupId>com.google.guava</groupId>
   <artifactId>guava</artifactId>
   <version>30.1-jre</version>
</dependency>
<dependency>
   <groupId>com.github.mgunlogson.cuckoofilter</groupId>
   <artifactId>cuckoofilter</artifactId>
   <version>0.3.2</version>
</dependency>
1
2
3
4
5
6
7
8
9
10

guava是Google开发的一个Java工具库，提供了许多实用的工具类和方法，包括布隆过滤器。cuckoofilter是一个开源的Java布隆过滤器实现。（cuckoofilter是布谷鸟过滤器）

2. 创建布隆过滤器

import com.google.common.hash.Hashing;
import com.google.common.hash.Funnels;
import com.github.mgunlogson.cuckoofilter4j.CuckooFilter;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.stereotype.Component;
import javax.annotation.PostConstruct;

@Component
public class BloomFilter {
    @Value("${bloomfilter.expectedInsertions}")
    private int expectedInsertions; //期望插入数量

    @Value("${bloomfilter.fpp}")
    private double fpp; //误判率，这里都是在配置文件中配置了

    private CuckooFilter<String> filter;//布谷鸟过滤器

    @PostConstruct
    public void init() {
        filter = new CuckooFilter.Builder<>(Funnels.stringFunnel())
                .withFalsePositiveProbability(fpp)
                .withExpectedInsertions(expectedInsertions)
                .build();
    }
//判断是否存在
    public boolean mightContain(String element) {
        return filter.mightContain(element);
    }
//添加元素
    public void add(String element) {
        filter.put(element);
    }
}
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

这里使用CuckooFilter实现了布隆过滤器（准确来说这里应该布叫谷鸟过滤器），使用guava提供的Hashing和Funnels类来计算元素的哈希值和将元素转换为字节数组。在init方法中，我们初始化了布隆过滤器，设置了期望的插入数量和误判率。在mightContain方法中，我们检查元素是否可能存在于布隆过滤器中。在add方法中，我们将元素添加到布隆过滤器中。

在使用布隆过滤器时，需要根据实际情况来选择合适的误判率和期望插入数量。误判率越低，布隆过滤器的大小就越大，且添加元素的时间也越长。期望插入数量越大，布隆过滤器的大小也就越大，但误判率会减小。

5.12.5 简单使用

以下是使用Google Guava库中的BloomFilter类实现布隆过滤器的示例代码：

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterExample {
    public static void main(String[] args) {
        int expectedInsertions = 1000000;//期望插入元素数量
        double fpp = 0.01;//期望误差率

        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(), expectedInsertions, fpp);

        // 添加元素到布隆过滤器中
        bloomFilter.put("apple");
        bloomFilter.put("banana");
        bloomFilter.put("orange");

        // 判断元素是否在布隆过滤器中
        System.out.println(bloomFilter.mightContain("apple"));   // true
        System.out.println(bloomFilter.mightContain("pear"));    // false
        System.out.println(bloomFilter.mightContain("banana"));  // true
        System.out.println(bloomFilter.mightContain("orange"));  // true
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

create方法的第一个参数是元素类型的Funnel对象，第二个参数是期望插入元素的数量，第三个参数是期望误判率。

BloomFilter类提供了put方法来将元素添加到布隆过滤器中，提供了mightContain方法来判断元素是否在布隆过滤器中。

5.12.6 解决Redis缓存穿透逻辑

实现先思考一个问题，误判率会不会有什么影响？

布隆过滤器起到的作用是判断一个元素是否存在，那么就有两种情况，在或不在。胆识误判情况就一种，就是把原本不存在的数据判为存在。（前提是不改变布隆过滤器的期望插入元素和期望误判率这两个参数）

那么，为什么不会产生将原本存在的数据判断为不存在呢？我们在不改变那两个参数的情况下，每次输入同样的数据得到的结果必然一样，那么，既然数据已经存在，说明对应的位已经由0变为1了，而且布隆过滤器的删除是很难的，所以变成1之后的位就可以认定为不会变回0。那么下一次查询的时候查到得也只能是1，所以是不会把存在的判断成不存在的。

黑名单解决方案：

上图会出现一种返回数据有误的情况，就是由于误判导致的。当布隆过滤器将原本不存在的数据判为存在（也就是原本应该去查询Redis，但却没有去查），这就会导致返回的数据有误，这是我不希望看到的。（这部分不知道叙述有没有错）

应用场景：骚扰电话，ip拦截，视频转载

白名单解决方案：

这个方案中的误判会将原本不存在的key判断为存在，从而造成缓存击穿，但是概论很小可以忽略；还有就是需要将所有的合法key都放到白名单里面。

可以考虑将白名单与黑名单结合起来

5.12.7 代码实现

这里简单实现黑名单

1. 创建布隆过滤器（布谷鸟过滤器）

import com.google.common.hash.Hashing;
import com.google.common.hash.Funnels;
import com.github.mgunlogson.cuckoofilter4j.CuckooFilter;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.stereotype.Component;
import javax.annotation.PostConstruct;

@Component
public class BloomFilter {
    @Value("${bloomfilter.expectedInsertions}")
    private int expectedInsertions;

    @Value("${bloomfilter.fpp}")
    private double fpp;

    private CuckooFilter<String> filter;

    @PostConstruct
    public void init() {
        filter = new CuckooFilter.Builder<>(Funnels.stringFunnel())
                .withFalsePositiveProbability(fpp)
                .withExpectedInsertions(expectedInsertions)
                .build();
    }

    public boolean mightContain(String element) {
        return filter.mightContain(element);
    }

    public void add(String element) {
        filter.put(element);
    }
}
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

2. 缓存查询时的逻辑

在缓存查询时，我们首先使用布隆过滤器过滤掉不存在的数据，如果数据可能存在于缓存中，我们再去查询缓存。

@Autowired
private RedisTemplate<String, Object> redisTemplate;

@Autowired
private BloomFilter bloomFilter;

public Object getValue(String key) {
    // 先检查布隆过滤器中是否存在该key
    if (!bloomFilter.mightContain(key)) {
        return null;
    }

    // 查询缓存
    ValueOperations<String, Object> ops = redisTemplate.opsForValue();
    Object value = ops.get(key);

    // 如果缓存中不存在该key，将其添加到布隆过滤器中
    if (value == null) {
        bloomFilter.add(key);
    }

    return value;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

数据库部分省略了

文章内容尚不完善，今后将会不断改进