当前位置： 首页 > article >正文

在SpringBoot项目中利用Redission实现布隆过滤器（布隆过滤器的应用场景、布隆过滤器误判的情况、与位图相关的操作）

article 2024/11/14 10:21:44

文章目录

  • 1. 布隆过滤器的应用场景
  • 2. 在SpringBoot项目利用Redission实现布隆过滤器
  • 3. 布隆过滤器误判的情况
  • 4. 与位图相关的操作
  • 5. 可能遇到的问题（Redission是如何记录布隆过滤器的配置参数的）
    • 5.1 问题产生的原因
    • 5.2 解决方案
      • 5.2.1 方案一：删除Redis中与布隆过滤器相关的key
      • 5.2.2 方案二：创建一个新的布隆过滤器

对 Redission 不了解的同学，可以参考我的另一篇博文： 在SpringBoot项目中使用Redission实现分布式锁（什么是Redission、为什么要使用分布式锁、分布式锁的应用场景、Redission的读锁和写锁、可重入锁的原理

至于什么是布隆过滤器，可以参考我的另一篇博文：Redis缓存面试三兄弟：缓存穿透、缓存雪崩、缓存击穿 的 1.3.3 方案三：使用布隆过滤器 部分

1. 布隆过滤器的应用场景

布隆过滤器（Bloom Filter）是一种空间效率极高的概率数据结构，用于测试一个元素是否属于集合

布隆过滤器可能会产生误报（一个元素不属于集合，但布隆过滤器判断元素属于该集合），但绝不会漏报（一个元素属于集合，但布隆过滤器判断元素不属于该集合）

布隆过滤器适用于以下一些应用场景：

  1. 网络爬虫：避免爬取已经访问过的URL，减少重复工作
  2. 防止缓存穿透：在缓存系统中，使用布隆过滤器检查请求的数据是否可能存在，以避免对不存在的数据进行数据库查询
  3. 数据库索引：用于快速判断一个记录是否存在于数据库中，减少不必要的磁盘I/O操作
  4. 邮件系统：过滤垃圾邮件，通过布隆过滤器快速判断一个邮件地址是否在垃圾邮件发送者列表中
  5. 网络安全：用于检测和防御DDoS攻击，通过布隆过滤器识别和过滤恶意流量
  6. 分布式系统：在分布式环境中，布隆过滤器可以用来检查数据是否已经被处理，以避免重复处理
  7. 文件系统：在文件检索系统中，快速判断一个文件是否存在于文件系统中，减少文件系统的访问次数
  8. 大数据集去重：在处理大规模数据集时，使用布隆过滤器进行高效去重
  9. 网络服务：检查客户端请求的内容是否已经被服务器处理过，从而避免重复处理

布隆过滤器的优点在于它的空间效率和查询速度，布隆过滤器在处理大量数据时非常有用

2. 在SpringBoot项目利用Redission实现布隆过滤器

如果不知道如何在 SpringBoot 项目项目中接入 Redission，可以参考我的另一篇博文：在SpringBoot项目中使用Redission实现分布式锁（什么是Redission、为什么要使用分布式锁、分布式锁的应用场景、Redission的读锁和写锁、可重入锁的原理）

编写一个测试类，测试布隆过滤器的过滤效果

import org.junit.jupiter.api.Test;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;

@SpringBootTest
public class BloomFilterTests {

    @Autowired
    private RedissonClient redissionClient;

    @Test
    public void testBooleanFilter() {
        try {
            String filterName = "myBloomFilter";
            long expectedInsertions = 100000L; // 预期元素数量
            double falseProbability = 0.01; // 容错率，也就是误报率

            // 创建布隆过滤器，参数分别为：过滤器名称，预期元素数量，误差率
            RBloomFilter<Object> bloomFilter = redissionClient.getBloomFilter(filterName);
            bloomFilter.tryInit(expectedInsertions, falseProbability);

            // 添加元素
            for (int i = 1; i <= 50; i++) {
                bloomFilter.add(String.format("element%02d", i));
            }

            // 检查元素是否存在
            System.out.println("bloomFilter.contains(\"element01\") = " + bloomFilter.contains("element01"));
            System.out.println("bloomFilter.contains(\"element51\") = " + bloomFilter.contains("element51"));
        } finally {
            // 关闭 Redission 客户端
            redissionClient.shutdown();
        }
    }

}

输出结果如下

在这里插入图片描述

3. 布隆过滤器误判的情况

我们将预期元素数量改为 5 个，再次对布隆过滤器进行测试

import org.junit.jupiter.api.Test;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;

@SpringBootTest
public class BloomFilterTests {

    @Autowired
    private RedissonClient redissionClient;

    @Test
    public void testBooleanFilter() {
        try {
            String filterName = "myBloomFilter";
            long expectedInsertions = 5L; // 预期元素数量
            double falseProbability = 0.01; // 容错率，也就是误报率

            // 创建布隆过滤器，参数分别为：过滤器名称，预期元素数量，误差率
            RBloomFilter<Object> bloomFilter = redissionClient.getBloomFilter(filterName);
            bloomFilter.tryInit(expectedInsertions, falseProbability);

            // 添加元素
            for (int i = 1; i <= 50; i++) {
                bloomFilter.add(String.format("element%02d", i));
            }

            // 检查元素是否存在
            System.out.println("bloomFilter.contains(\"element01\") = " + bloomFilter.contains("element01"));
            System.out.println("bloomFilter.contains(\"element51\") = " + bloomFilter.contains("element51"));
        } finally {
            // 关闭 Redission 客户端
            redissionClient.shutdown();
        }
    }

}

运行结果如下

在这里插入图片描述

可以看到，布隆过滤器出现了误判的情况（element51 不在集合中，但布隆过滤器判断 element51 在集合中）

我们查看布隆过滤器的配置（布隆过滤器中各个参数的含义可参考本文的 布隆过滤器中各个参数的含义 章节）

在这里插入图片描述

可以发现，布隆过滤器底层的位图的大小为 47，布隆过滤器在处理每个元素时要应用的哈希函数的数量为 7，也就是说，每个元素会映射到位图的 7 个位置上

我们往布隆过滤器中插入了 50 个元素，每个元素映射到位图的 7 个位置上，非常容易发生哈希冲突的情况，从而导致布隆过滤器误判

我们删除布隆过滤器后，重写运行测试代码，查看位图中 1 的数量

在这里插入图片描述

redissionClient.getBitSet(filterName).cardinality()

在这里插入图片描述

可以发现，位图的大小为 47，位图中 1 的数量也是 47，也就是说，位图中所有位置都是 1，也就意味着此时布隆过滤器已经完全失去了过滤作用

所以说，在初始化布隆过滤器时，我们需要十分注意 预期元素数量 和 误判率 参数，否则布隆过滤器的过滤效果将会大打折扣，甚至失效

4. 与位图相关的操作

Redission 提供的 RBloomFilter 类用于布隆过滤，而 RBitSet类 用于常规的位图操作

使用 RBitSet 类可以对各种位图进行各种操作，如设置位、清除位、检查位的状态等

在这里插入图片描述

@Test
public void testBitmap() {
    try {
        String filterName = "myBloomFilter";

        RBitSet bitSet = redissionClient.getBitSet(filterName);

        bitSet.set(0, true); // 设置第0位为1
        bitSet.set(1, false); // 设置第1位为0

        bitSet.clear(0); // 清除第0位

        boolean isSet = bitSet.get(0); // 检查第0位是否为1
        System.out.println("isSet = " + isSet);

        long count = bitSet.cardinality(); // 返回位图中1的数量
        System.out.println("count = " + count);
    } finally {
        // 关闭 Redission 客户端
        redissionClient.shutdown();
    }
}

5. 可能遇到的问题（Redission是如何记录布隆过滤器的配置参数的）

在这里插入图片描述

org.redisson.client.RedisException: ERR Error running script (call to f_a7ac8cff901d5cafb8de37987dfbe1fc11f00eb4): @user_script:1: user_script:1: Bloom filter config has been changed . channel: [id: 0xe1fd1f6a, L:/127.0.0.1:3098 - R:127.0.0.1/127.0.0.1:6379] command: (EVAL), promise: java.util.concurrent.CompletableFuture@52a215fa[Not completed, 1 dependents], params: [local size = redis.call(‘hget’, KEYS[1], ‘size’);local hashIterations = redis.call(‘hget’, KEYS[1], ‘hashIterations’);assert(size == ARGV[1] and hashIterations == ARGV[2], ‘Bloom filter config has been changed’)local k = 0;local c = 0;for i = 4, #ARGV, 1 do local r = redis.call(‘setbit’, KEYS[2], ARGV[i], 1); if r == 0 then k = k + 1;end; if ((i - 4) + 1) % ARGV[3] == 0 then if k > 0 then c = c + 1;end; k = 0; end; end; return c;, 2, {myBloomFilter}:config, myBloomFilter, 47, 7, 7, 6, 14, 20, …]

5.1 问题产生的原因

之所以会报错，是因为布隆过滤器的配置参数被篡改了

那布隆过滤器的配置参数存放在哪里呢，当然是存在 Redis 里面，Redis 中会有一个与布隆过滤器配置参数相关的 key，这个 key 使用的是 Hash 结构

在这里插入图片描述

在这里插入图片描述

各个参数的含义：

  1. size：布隆过滤器位图的大小
  2. hashIterations：布隆过滤器在处理每个元素时要应用的哈希函数的数量
  3. falseProbability：布隆过滤器的误报率，即错误地判断一个元素存在于集合中的概率
  4. expectedInsertions：预期将要插入布隆过滤器的元素数量

5.2 解决方案

5.2.1 方案一：删除Redis中与布隆过滤器相关的key

直接删除 Redis 中与布隆过滤器相关的 key，下次再操作布隆过滤器时会重新创建布隆过滤器

在这里插入图片描述

5.2.2 方案二：创建一个新的布隆过滤器

直接更改布隆过滤器的名字，创建一个新的布隆过滤器

在这里插入图片描述


http://www.kler.cn/a/319621.html

相关文章：

  • 什么是数字图像？
  • openSUSE 环境下通过 zypper 安装软件
  • DOM 规范 — MutationObserver 接口
  • Python多进程间通讯（包含共享内存方式）
  • 机器情绪及抑郁症算法
  • springboot项目中，使用ProGuard 对代码进行混淆
  • MICS：PythonJail沙箱逃逸（持续更新中）
  • Python数据分析与可视化：从基础到高级应用
  • vue3 实现图片预览组件
  • [ABC330E] Mex and Update
  • java-重启异常断掉的线程和监控线程状态
  • Android——Application
  • 网红挣钱太容易了
  • 路由器全局配置DHCP实验简述
  • MySQL篇（视图）（持续更新迭代）
  • CANopen通讯协议笔记
  • 制作一个能对话能跳舞的otto机器人
  • SentencePiece进行文本分类
  • 大数据-147 Apache Kudu 常用 Java API 增删改查
  • 二进制位运算题
  • python库 | lxml库
  • Python_yield
  • 【项目实战】如何在项目中自定义错误码
  • VisualStudio编译时出现无法启动mt.exe
  • C++之spring
  • Codeforces Round 973 (Div. 2) C. Password Cracking