【数据结构与算法】布隆(Bloom Filter)过滤器

Redisson系列文章：

• 【Redisson】Redisson–基础入门
• 【Redisson】Redisson–布隆(Bloom Filter)过滤器
• 【Redisson】Redisson–分布式锁的使用（推荐使用）
• 【分布式锁】Redisson分布式锁底层原理
• 【Redisson】Redisson–限流器

1、什么是布隆过滤器

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
​

上面这句介绍比较全面的描述了什么是布隆过滤器，如果还是不太好理解的话，就可以把布隆过滤器理解为一个set集合，我们可以通过add往里面添加元素，通过contains来判断是否包含某个元素。由于本文讲述布隆过滤器时会结合Redis来讲解，因此类比为Redis中的Set数据结构会比较好理解，而且Redis中的布隆过滤器使用的指令与Set集合非常类似（后续会讲到）。
​

学习布隆过滤器之前有必要先聊下它的优缺点，因为好的东西我们才想要嘛！

• 布隆过滤器的优点：

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

• 布隆过滤器的缺点：

  • 有点一定的误判率，但是可以通过调整参数来降低
  • 无法获取元素本身
  • 很难删除元素

2、布隆过滤器的使用场景

布隆过滤器可以告诉我们 “某样东西一定不存在或者可能存在”，也就是说布隆过滤器说这个数不存在则一定不存，布隆过滤器说这个数存在可能不存在（误判，后续会讲），利用这个判断是否存在的特点可以做很多有趣的事情。

• 解决Redis缓存穿透问题（面试重点）
• 邮件过滤，使用布隆过滤器来做邮件黑名单过滤
• 对爬虫网址进行过滤，爬过的不再爬
• 解决新闻推荐过的不再推荐(类似抖音刷过的往下滑动不再刷到)
• HBase\RocksDB\LevelDB等数据库内置布隆过滤器，用于判断数据是否存在，可以减少数据库的IO请求

3、布隆过滤器的原理

3.1 数据结构

布隆过滤器它实际上是一个很长的二进制向量和一系列随机映射函数。以Redis中的布隆过滤器实现为例，Redis中的布隆过滤器底层是一个大型位数组（二进制数组）+多个无偏hash函数。
一个大型位数组（二进制数组）：

多个无偏hash函数：
无偏hash函数就是能把元素的hash值计算的比较均匀的hash函数，能使得计算后的元素下标比较均匀的映射到位数组中。

如下就是一个简单的布隆过滤器示意图，其中k1、k2代表增加的元素，a、b、c即为无偏hash函数，最下层则为二进制数组。

3.2 空间计算

在布隆过滤器增加元素之前，首先需要初始化布隆过滤器的空间，也就是上面说的二进制数组，除此之外还需要计算无偏hash函数的个数。布隆过滤器提供了两个参数，分别是预计加入元素的大小n，运行的错误率f。布隆过滤器中有算法根据这两个参数会计算出二进制数组的大小l，以及无偏hash函数的个数k。
它们之间的关系比较简单：

• 错误率越低，位数组越长，控件占用较大
• 错误率越低，无偏hash函数越多，计算耗时较长

如下地址是一个免费的在线布隆过滤器在线计算的网址：

https://krisives.github.io/bloom-calculator/

3.3 增加元素

往布隆过滤器增加元素，添加的key需要根据k个无偏hash函数计算得到多个hash值，然后对数组长度进行取模得到数组下标的位置，然后将对应数组下标的位置的值置为1

• 通过k个无偏hash函数计算得到k个hash值
• 依次取模数组长度，得到数组索引
• 将计算得到的数组索引下标位置数据修改为1

例如，key = Liziba，无偏hash函数的个数k=3，分别为hash1、hash2、hash3。三个hash函数计算后得到三个数组下标值，并将其值修改为1.
如图所示：

3.4 查询元素

布隆过滤器最大的用处就在于判断某样东西一定不存在或者可能存在，而这个就是查询元素的结果。其查询元素的过程如下：

• 通过k个无偏hash函数计算得到k个hash值
• 依次取模数组长度，得到数组索引
• 判断索引处的值是否全部为1，如果全部为1则存在（这种存在可能是误判），如果存在一个0则必定不存在

关于误判，其实非常好理解，hash函数在怎么好，也无法完全避免hash冲突，也就是说可能会存在多个元素计算的hash值是相同的，那么它们取模数组长度后的到的数组索引也是相同的，这就是误判的原因。例如李子捌和李子柒的hash值取模后得到的数组索引都是1，但其实这里只有李子捌，如果此时判断李子柒在不在这里，误判就出现啦！因此布隆过滤器最大的缺点误判只要知道其判断元素是否存在的原理就很容易明白了！

3.5 修改元素

无
​

3.6 删除元素

布隆过滤器对元素的删除不太支持，目前有一些变形的特定布隆过滤器支持元素的删除！关于为什么对删除不太支持，其实也非常好理解，hash冲突必然存在，删除肯定是很苦难的！
​

4、Redis集成布隆过滤器

4.1 版本要求

• 推荐版本6.x，最低4.x版本，可以通过如下命令查看版本：

redis-server -v

• 插件安装，网上大部分推荐v1.1.1，文章写的时候v2.2.6已经是release版本了，用户自己选择，地址全在下面(2.2.6官网介绍说是1.0版本的维护版本，如果不想使用新的功能，无需升级！)

v1.1.1

https://github.com/RedisLabsModules/rebloom/archive/v1.1.1.tar.gz

v2.2.6

https://github.com/RedisLabsModules/rebloom/archive/v2.2.6.tar.gz

4.2 安装&编译

以下安装全部在指定目录下完成，可以选择一个合适的统一目录进行软件安装和管理。

4.2.1 下载插件压缩包

wget https://github.com/RedisLabsModules/rebloom/archive/v2.2.6.tar.gz

4.2.2 解压

tar -zxvf v2.2.6.tar.gz

4.2.3 编译插件

cd RedisBloom-2.2.6/
make

编译成功后看到redisbloom.so文件即可
​

4.3 Redis集成

4.3.1 Redis配置文件修改

• 在redis.conf配置文件中加入如RedisBloom的redisbloom.so文件的地址
• 如果是集群则每个配置文件中都需要加入redisbloom.so文件的地址
• 添加完成后需要重启redis

loadmodule /usr/local/soft/RedisBloom-2.2.6/redisbloom.so

redis.conf配置文件中预置了loadmodule的配置项，我们可以直接在这里修改，后续修改会更加方便。

• 保存退出后一定要记得重启Redis！

4.3.2 测试是否成功

Redis集成布隆过滤器的主要指令如下：

• bf.add 添加一个元素
• bf.exists 判断一个元素是否存在
• bf.madd 添加多个元素
• bf.mexists 判断多个元素是否存在

连接客户端进行测试，如果指令有效则证明集成成功

如果出现如下情况(error) ERR unknown command ，可以通过如下方法检查：

• SHUTDOWN Redis实例，再重启实例，再次测试
• 检查配置文件是否配置redisbloom.so文件地址正确
• 检查Redis的版本是否过低

5、Redis中布隆过滤器指令使用

5.1 bf.add

bf.add表示添加单个元素，添加成功返回1

127.0.0.1:6379> bf.add name liziba
(integer) 1

5.2 bf.madd

bf.madd表示添加多个元素

127.0.0.1:6379> bf.madd name liziqi lizijiu lizishi
1) (integer) 1
2) (integer) 1
3) (integer) 1

5.3 bf.exists

bf.exists表示判断元素是否存在，存在则返回1，不存在返回0

127.0.0.1:6379> bf.mexists name liziba
1) (integer) 1

5.4 bf.mexists

bf.mexists表示判断多个元素是否存在，存在的返回1，不存在的返回0

127.0.0.1:6379> bf.mexists name liziqi lizijiu liziliu
1) (integer) 1
2) (integer) 1
3) (integer) 0

6、Java本地内存使用布隆过滤器

使用布隆过滤器的方式有很多，还有很多大佬自己手写的，我这里使用的是谷歌guava包中实现的布隆过滤器，这种方式的布隆过滤器是在本地内存中实现。

6.1 引入pom依赖

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>29.0-jre</version>
</dependency>

6.2 编写测试代码

package com.lizba.bf;
 
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
 
/**
 * <p>
 *        布隆过滤器测试代码
 * </p>
 *
 */
public class BloomFilterTest {
 
    /** 预计插入的数据 */
    private static Integer expectedInsertions = 10000000;
    /** 误判率 */
    private static Double fpp = 0.01;
    /** 布隆过滤器 */
    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), expectedInsertions, fpp);
 
    public static void main(String[] args) {
        // 插入 1千万数据
        for (int i = 0; i < expectedInsertions; i++) {
            bloomFilter.put(i);
        }
 
        // 用1千万数据测试误判率
        int count = 0;
        for (int i = expectedInsertions; i < expectedInsertions *2; i++) {
            if (bloomFilter.mightContain(i)) {
                count++;
            }
        }
        System.out.println("一共误判了：" + count);
 
    }
 
}

6.3 测试结果

误判了100075次，大概是expectedInsertions（1千万）的0.01，这与我们设置的 fpp = 0.01非常接近。

6.4 参数说明

在guava包中的BloomFilter源码中，构造一个BloomFilter对象有四个参数：

• Funnel funnel：数据类型，由Funnels类指定即可
• long expectedInsertions：预期插入的值的数量
• fpp：错误率
• BloomFilter.Strategy：hash算法

6.5 fpp&expectedInsertions

• 当expectedInsertions=10000000&&fpp=0.01时，位数组的大小numBits=95850583，hash函数的个数numHashFunctions=7

• 当expectedInsertions=10000000&&fpp=0.03时，位数组的大小numBits=72984408，hash函数的个数numHashFunctions=5
  

• 当expectedInsertions=100000&&fpp=0.03时，位数组的大小numBits=729844，hash函数的个数numHashFunctions=5
  

综上三次测试可以得出如下结论：

• 当预计插入的值的数量不变时，偏差值fpp越小，位数组越大，hash函数的个数越多
• 当偏差值不变时，预计插入的中的数量越大，位数组越大，hash函数并没有变化（注意这个结论只是在guava实现的布隆过滤器中的算法符合，并不是说所有的算法都是这个结论，我做了多次测试，确实numHashFunctions在fpp相同时，是不变的！）

7、Java集成Redis使用布隆过滤器

Redis经常会被问道缓存击穿问题，比较优秀的解决办法是使用布隆过滤器，也有使用空对象解决的，但是最好的办法肯定是布隆过滤器，我们可以通过布隆过滤器来判断元素是否存在，避免缓存和数据库都不存在的数据进行查询访问！在如下的代码中只要通过bloomFilter.contains(xxx)即可，我这里演示的还是误判率！

7.1 引入pom依赖

<dependency>
  <groupId>org.redisson</groupId>
  <artifactId>redisson-spring-boot-starter</artifactId>
  <version>3.16.0</version>
</dependency>

7.2 编写测试代码

package com.lizba.bf;
 
import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
 
/**
 * <p>
 *      Java集成Redis使用布隆过滤器防止缓存穿透方案
 * </p>
 *
 */
public class RedisBloomFilterTest {
 
    /** 预计插入的数据 */
    private static Integer expectedInsertions = 10000;
    /** 误判率 */
    private static Double fpp = 0.01;
 
    public static void main(String[] args) {
        // Redis连接配置，无密码
        Config config = new Config();
        config.useSingleServer().setAddress("redis://192.168.211.108:6379");
        // config.useSingleServer().setPassword("123456");
 
        // 初始化布隆过滤器
        RedissonClient client = Redisson.create(config);
        RBloomFilter<Object> bloomFilter = client.getBloomFilter("user");
        bloomFilter.tryInit(expectedInsertions, fpp);
 
        // 布隆过滤器增加元素
        for (Integer i = 0; i < expectedInsertions; i++) {
            bloomFilter.add(i);
        }
 
        // 统计元素
        int count = 0;
        for (int i = expectedInsertions; i < expectedInsertions*2; i++) {
            if (bloomFilter.contains(i)) {
                count++;
            }
        }
        System.out.println("误判次数" + count);
 
    }
 
}

7.3 测试结果

文章来源地址https://www.toymoban.com/news/detail-446251.html

到了这里，关于【数据结构与算法】布隆(Bloom Filter)过滤器的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！