程序员经验分享-hwhale

SpringBoot + Redis实现布隆过滤器

2023-05-16

一、简述

关于布隆过滤器的详细介绍，我在这里就不再赘述一遍了

我们首先知道：BloomFilter使用长度为m bit的字节数组，使用k个hash函数，增加一个元素: 通过k次hash将元素映射到字节数组中k个位置中，并设置对应位置的字节为1。查询元素是否存在: 将元素k次hash得到k个位置，如果对应k个位置的bit是1则认为存在，反之则认为不存在。

Guava 中已经有具体的实现，而在我们实际生产环境中，本地的存储往往无法满足我们实际的 需求。所以在这时候，就需要我们使用 redis 了。

二、Redis 安装 Bloom Filter 

git clone https://github.com/RedisLabsModules/redisbloom.git
cd redisbloom
make # 编译

vi redis.conf
## 增加配置
loadmodule /usr/local/web/redis/RedisBloom-1.1.1/rebloom.so

##redis 重启
#关闭
./redis-cli -h 127.0.0.1 -p 6379 shutdown
#启动
./redis-server ../redis.conf &

三、基本指令 

#创建布隆过滤器，并设置一个期望的错误率和初始大小
bf.reserve userid 0.01 100000
#往过滤器中添加元素
bf.add userid 'sbc@163.com'
#判断指定key的value是否在bloomfilter里存在，存在：返回1，不存在：返回0
bf.exists userid 'sbc@163.com'

四、结合 SpingBoot

搭建一个简单的 springboot 框架

1、方式一：使用Redisson

配置maven

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
        xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>
    <groupId>com.bloom</groupId>
    <artifactId>test-bloomfilter</artifactId>
    <version>1.0-SNAPSHOT</version>
    <parent>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-parent</artifactId>
        <version>1.5.8.RELEASE</version>
        <relativePath/> <!-- lookup parent from repository -->
    </parent>
    <dependencies>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter</artifactId>
        </dependency>
        <dependency>
            <groupId>org.apache.commons</groupId>
            <artifactId>commons-lang3</artifactId>
            <version>3.0.1</version>
        </dependency>
    </dependencies>
</project>

redis本身对布隆过滤器就有一个很好地实现，在 java 端，我们直接导入 redisson 的 jar包即可

<dependency>
  <groupId>org.redisson</groupId>
  <artifactId>redisson</artifactId>
  <version>3.8.2</version>
</dependency>

将 Redisson实例 注入 SpringIOC 容器中

@Configuration
public class RedissonConfig {

    @Value("${redisson.redis.address}")
    private String address;

    @Value("${redisson.redis.password}")
    private String password;

    @Bean
    public Config redissionConfig() {
        Config config = new Config();
        SingleServerConfig singleServerConfig = config.useSingleServer();
        singleServerConfig.setAddress(address);
        if (StringUtils.isNotEmpty(password)) {
            singleServerConfig.setPassword(password);
        }

        return config;
    }

    @Bean
    public RedissonClient redissonClient() {
        return Redisson.create(redissionConfig());
    }
}

配置yml文件

redisson.redis.address=redis://127.0.0.1:6379
redisson.redis.password=

最后测试我们的布隆过滤器

@SpringBootApplication
public class BloomApplication {
    public static void main(String[] args) {
        ConfigurableApplicationContext context = SpringApplication.run(BloomApplication.class, args);
        RedissonClient redisson = context.getBean(RedissonClient.class);
        RBloomFilter bf = redisson.getBloomFilter("test-bloom-filter");
        bf.tryInit(100000L, 0.03);
        Set<String> set = new HashSet<String>(1000);
        List<String> list = new ArrayList<String>(1000);
      //向布隆过滤器中填充数据，为了测试真实，我们记录了 1000 个 uuid，另外 9000个作为干扰数据
        for (int i = 0; i < 10000; i++) {
           String uuid = UUID.randomUUID().toString();
          if(i<1000){
            set.add(uuid);
            list.add(uuid);
          }
          
           bf.add(uuid);
        }

        int wrong = 0; // 布隆过滤器误判的次数
        int right = 0;// 布隆过滤器正确次数
        for (int i = 0; i < 10000; i++) {
            String str = i % 10 == 0 ? list.get(i / 10) : UUID.randomUUID().toString();
            if (bf.contains(str)) {
                if (set.contains(str)) {
                    right++;
                } else {
                    wrong++;
                }
            }
        }

        //right 为1000
        System.out.println("right:" + right);
        //因为误差率为3%，所以一万条数据wrong的值在30左右
        System.out.println("wrong:" + wrong);
          //过滤器剩余空间大小
        System.out.println(bf.count());
    }
}

以上使我们使用 redisson 的使用方式，下面介绍一种比较原始的方式，使用lua脚本的方式

2、方式二：使用lua脚本

bf_add.lua

local bloomName = KEYS[1]
local value = KEYS[2]
local result = redis.call('BF.ADD',bloomName,value)
return result

bf_exist.lua

local bloomName = KEYS[1]
local value = KEYS[2]
 
local result = redis.call('BF.EXISTS',bloomName,value)
return result
@Service
public class RedisBloomFilterService {

    @Autowired
    private RedisTemplate redisTemplate;

    //我们依旧用刚刚的那个过滤器
    public static final String BLOOMFILTER_NAME = "test-bloom-filter";

    /**
     * 向布隆过滤器添加元素
     * @param str
     * @return
     */
    public Boolean bloomAdd(String str) {
        DefaultRedisScript<Boolean> LuaScript = new DefaultRedisScript<Boolean>();
        LuaScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("bf_add.lua")));
        LuaScript.setResultType(Boolean.class);
        //封装传递脚本参数
        List<String> params = new ArrayList<String>();
        params.add(BLOOMFILTER_NAME);
        params.add(str);
        return (Boolean) redisTemplate.execute(LuaScript, params);
    }

    /**
     * 检验元素是否可能存在于布隆过滤器中 * @param id * @return
     */
    public Boolean bloomExist(String str) {
        DefaultRedisScript<Boolean> LuaScript = new DefaultRedisScript<Boolean>();
        LuaScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("bf_exist.lua")));
        LuaScript.setResultType(Boolean.class);
        //封装传递脚本参数
        ArrayList<String> params = new ArrayList<String>();
        params.add(BLOOMFILTER_NAME);
        params.add(String.valueOf(str));
        return (Boolean) redisTemplate.execute(LuaScript, params);
    }
}

最后我们还是用上面的启动器执行测试代码

@SpringBootApplication
public class BloomApplication {
    public static void main(String[] args) {
        ConfigurableApplicationContext context = SpringApplication.run(BloomApplication.class, args);
        RedisBloomFilterService filterService = context.getBean(RedisBloomFilterService.class);
        Set<String> set = new HashSet<String>(1000);
        List<String> list = new ArrayList<String>(1000);
        //向布隆过滤器中填充数据，为了测试真实，我们记录了 1000 个 uuid，另外 9000个作为干扰数据
        for (int i = 0; i < 10000; i++) {
            String uuid = UUID.randomUUID().toString();
            if (i < 1000) {
                set.add(uuid);
                list.add(uuid);
            }

            filterService.bloomAdd(uuid);
        }

        int wrong = 0; // 布隆过滤器误判的次数
        int right = 0;// 布隆过滤器正确次数
        for (int i = 0; i < 10000; i++) {
            String str = i % 10 == 0 ? list.get(i / 10) : UUID.randomUUID().toString();
            if (filterService.bloomExist(str)) {
                if (set.contains(str)) {
                    right++;
                } else {
                    wrong++;
                }
            }
        }

        //right 为1000
        System.out.println("right:" + right);
        //因为误差率为3%，所以一万条数据wrong的值在30左右
        System.out.println("wrong:" + wrong);
    }
}

3、总结

相比而言，个人比较推荐第一种，实现的原理都是差不多，redis 官方已经为我封装好了执行脚本，和相关 api，用官方的会更好一点

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

SpringBoot + Redis实现布隆过滤器 的相关文章

  • J-004 Jetson电路设计之HDMI设计--NANO && XAVIER NX

    HDMI电路设计 1 简介2 框图介绍3 原理图介绍 1 简介 NANO amp XAVIER NX提供一路HDMI接口 xff0c DP接口与HDMI是兼容的 xff0c 可用于扩展一路HDMI 其中引脚说明 PIN名称描述方向类型63H

  • 树莓派入坑第一天——系统烧录以及SSH登录问题

    1 首先下载镜像https www raspberrypi org downloads xff0c Raspbian系统是树莓派官方推荐的系统 xff0c 解压出img镜像文件 注意树莓派3B可能不支持老版本镜像 2 下载一个格式化SD卡的

  • c++学习之路

    3 19 内存分区模型 内存四区意义 不同区域存放的数据 xff0c 赋予不同的生命周期 给我们更大的灵活编程 程序exe 运行前分为 代码区和全局区 xff1b 运行后分为 栈区和堆区 1 代码区 存放CPU执行的机器指令 存放函数体的二

  • 写程序的步骤

    xff08 1 xff09 xff1a 一 要把实际问题提取为数学问题 相当于数学中的建模 抽象问题具体化 二 把其分解为若干个小的函数 并明白每个小函数怎样实现其功能 同时注意功能函数与主函数间的数据交互问题 三 作出 流程图 xff0c

  • Conda_安装库失败：Collecting package metadata (current_repodata.json): failed

    具体原因 xff1a update repo信息时网络有问题 于是就出现了污染 解决方法 xff1a conda clean i 然后重新随便install一个库 会重新下载repo信息 xff0c 问题解决

  • scrapy爬虫实战——抓取NBA吧的内容

    scrapy爬虫 步骤1 进入虚拟环境2 测试爬取页面3 进入开发者模式4 剥离页面中的数据5 在pycharm中码代码scrapy框架的目录 xff08 之前创建虚拟环境自动搭建 xff09 nba py源码详解 6 Debug第一步 点

  • ubuntu系统版本查询命令方法

    目录 一 使用命令 xff1a cat proc version 查看 二 使用命令 xff1a uname a 查看 三 使用命令 xff1a lsb release a 查看 四 使用命令 xff1a hostnamectl 查看 五

  • python解析xml文件（解析、更新、写入）

    Overview 这篇博客内容将包括对XML文件的解析 追加新元素后写入到XML xff0c 以及更新原XML文件中某结点的值 使用的是python的xml dom minidom包 xff0c 详情可见其官方文档 xff1a xml do

  • 一阶微分方程

    传送门https jingyan baidu com article 8065f87fb7f0652331249822 html 1 可分离变量的微分方程解法 一般形式 g y dy 61 f x dx 直接解得 g y dy 61 f x

  • C#多线程--信号量(Semaphore)

    Semaphore 是负责协调各个线程 以保证它们能够正确 合理的使用公共资源 也是操作系统中用于控制进程同步互斥的量 Semaphore常用的方法有两个WaitOne 和Release xff0c Release 的作用是退出信号量并返回

  • 【总结】C++工程师学习路线|推荐视频|推荐书籍

    前言 由于博主秋招拿到的offer有限 xff0c 经过对比 xff0c 决定转到C 43 43 开发技术栈 xff0c 此篇文章用于规划自己今后的成长路线并分享给大家 学习路线 C 43 43 语言本身 xff1a 我们可以将这个部分分为

  • 面试被问到的promise总结

    promise all的使用 promise all可以将多个promise实例包装成一个新的promise实例 xff0c 并且返回的值也不相同 xff0c 成功使 xff0c promise返回的值是一个结果数组 xff0c 而失败的话

  • ROS节点，消息，话题，服务的介绍

    整理结合机器人操作系统 xff08 ros xff09 浅析和网址http wiki ros org cn NODE node几乎是无处不在 xff0c 这个东西相当于可执行文件 xff0c 目前我更愿意把它当做cpp文件 xff0c 通过

  • vue实现表格的更多查询功能

    场景一 xff1a 一行足够显示完所有的查询条件 场景二 xff1a 需要多行才能显示完所有的查询条件 1 首先创建一个按钮组件SearchButton lt template gt lt el form inline class 61 3

  • FreeROTS原理学习笔记

    前言 xff1a 这仅是一篇学习笔记记录 xff0c 无指导意义 想详细了解的人 可看CSDN博主 zhzht19861011 的原创文章 FreeROTS系统 xff1a 使用习惯 xff1a 1 一般来说 xff0c 都是利用下载好的例

  • RuntimeError: dataset.make_initializable_iterator is not supported when eager execution is enabled.

    这是由于代码的接口更改 xff0c 无法正常连接数据集 xff0c 即新版本接口变了 需要按照第4章的数据集部分 xff0c 改一下数据集接口

  • 基于Android 的串口工具类

    欢迎使用串口通讯 xff0c 首先说明下我这里使用的是RS485通讯 xff0c 采用的是半双工通讯 xff0c 所以收和发不能同时操作需要发送等待一段时间来接收完数据在发送其他指令了 xff0c 这里顺便在说下RS232 xff0c 它采

  • ROS安装步骤

    ROS xff08 Robot Operating System xff09 起源于2007年斯坦福大学人工智能实验室与WillowGarage公司的个人机器人项目 xff0c 其后被Willow Garage公司开源和发展 xff0c 目

  • ros对应不同的ubuntu版本

    ros对应不同的ubuntu版本有不同的版本名字 xff1a ubuntu16 04对应ros kinetic xff1b ubuntu18 04对应ros melodic xff1b ubuntu20 04对应ros noetic 在Ub

  • ubuntu20.04安装 gym-gazebo

    官网流程安装 xff1a https github com erlerobot gym gazebo 一 环境与依赖 1 基本环境 xff1a ROS NoeticGazebo11 11 0 2 ROS相关依赖 xff1a sudo apt

随机推荐

热门标签