架构视界
主页
企业架构
  • 方案总览
  • 业财一体
  • 企业中台
  • 组织与绩效
  • 流程治理
数据收集与分析
  • 转型总览
  • 信息化阶段
  • 数字化解决方案
  • 智数化解决方案
  • 智能化解决方案
  • 产品设计
  • 项目管理
全栈软件工程
AI 原生软件工程
方法论
博客
  • 资源导航
  • 效率工具
  • 展示专区
主页
企业架构
  • 方案总览
  • 业财一体
  • 企业中台
  • 组织与绩效
  • 流程治理
数据收集与分析
  • 转型总览
  • 信息化阶段
  • 数字化解决方案
  • 智数化解决方案
  • 智能化解决方案
  • 产品设计
  • 项目管理
全栈软件工程
AI 原生软件工程
方法论
博客
  • 资源导航
  • 效率工具
  • 展示专区
  • 标签索引
  • 2024年

    • 勇闯大A:美债与美元周期
    • 勇闯大A:交易纪律与自我管理
    • 勇闯大A:交易系统分层
    • 勇闯大A:买卖点与止损规则
    • 勇闯大A:债券与资金流向
    • 勇闯大A:微观、宏观与周期
    • Mac 开发环境:新机配置清单
    • 勇闯大A:内外盘与换手率
    • 会计管理:财报阅读与管理报表
    • 会计基础:记账原理与分录
    • 财务入门:财务体系全景
  • 2023年

    • 境外投资:泰国 BOI 申请实务
  • 2022年

    • 企业架构:故障管理与分级响应
    • 企业架构:技术债务的识别、度量与偿还
  • 2021年

    • Python 数据分析:员工分布可视化
    • Python 数据分析:IP 访问折线图
    • Python 数据分析:IP 词云图
    • Redis:RediSearch 全文检索
    • Rust 基础:第一个 CLI 程序
    • Rust 基础:所有权机制
    • Rust 基础:函数与控制流
    • Rust 基础:变量与数据类型
    • Rust 基础:入门与开发环境
    • 企业架构:分布式系统设计
    • 企业架构:编程式权限设计
    • JVM 调优:启动参数与 GC 日志
    • MyBatis 批量插入:三种写法对比
    • 测试:Spring Boot 分层 Mock
    • Redis:布隆过滤器判断元素存在
    • Jenkins:安装配置与应用部署
    • WebClient:非阻塞 HTTP 客户端
    • Drone:Docker 部署轻量 CI
    • Spring AOP:操作审计日志落库
    • Redisson:分布式锁与 RedLock
    • MyBatis 拦截器:雪花算法主键
    • Netty:线程模型与网络编程
    • Redis:SCAN 游标遍历大键空间
    • Jenkins:单机部署与升级脚本
    • Mac:Neo4j 与 Jupyter 安装
    • JavaFX:OpenJDK 11 环境配置
    • Mac:用 jenv 管理 JDK 版本
    • Redis:有序集合实现延时队列
    • Spring Boot 日志:MDC 串联链路
    • 定时任务:Spring 调度与 Cron
    • GoAccess:Nginx 日志分析
    • MyBatis 拦截器:慢 SQL 分析
    • Lucene:倒排索引与中文分词
    • 分布式锁:三种实现方案对比
    • 学习技巧:减少学习排斥心理
    • 动态数据源:多租户数据路由
    • Compose:Spring Boot 三件套
    • Java 阻塞队列:源码与用法
    • Redis:Docker Compose 哨兵
    • Redis:Docker Compose 主从
    • 网络通信:TCP/IP 与 HTTP 基础
  • 2020年

    • 延时队列:DelayQueue 与 Redis 实现
    • MySQL 基础:员工库导入实践
    • 雪花算法:分布式 ID 生成
    • Redis:地理位置查询
    • 抓包:Wireshark 与 Tcpdump
    • SPI:JDK 与 Spring 扩展机制
    • ZooKeeper:概念与集群搭建
    • Spring Boot:集成 JMH 基准测试
    • Wireshark:抓包工具入门
    • Compose:Redis 与 MySQL
    • CentOS 7:Docker 安装部署
    • Netty:源码阅读环境搭建
    • MySQL 基础:SQL 常见用法
    • CentOS 7:Selenium 运行环境
    • Nginx:HTTPS 证书配置
    • JMH:基准测试与 Spring Boot 集成
    • Spring Boot:指定 Tomcat 版本
    • Eureka:实例上下线告警
    • 钉钉告警:应用异常与实例上下线
    • JVM:内存布局、类加载与调优
    • Git:rebase 合并多次提交
    • CentOS 7:OpenResty 部署
  • 2019年

    • Redis CLI:macOS 安装与使用
    • Nginx:访问日志格式
    • 工程规范:可维护代码的写法
    • IntelliJ IDEA:常用插件
    • SkyWalking:源码阅读环境搭建
    • Spring Boot:Redis 超时配置
    • gRPC:ProtoBuf 定义与代码生成
    • Arthas:Java 线上问题诊断
    • Redis:缓存穿透与击穿防护
    • Docker 部署:Elasticsearch
    • Docker 部署:MySQL 5.7 单机
    • Spring Redis:字符串命令封装
    • Docker 部署:ZooKeeper 运行
    • Docker 部署:Redis 单机运行
    • Dubbo:Spring Boot 微服务集成
    • CentOS 7:CMake 源码编译安装
    • 性能度量:吞吐量与 QPS 指标
    • Java 递归:从笔试题到经典问题
    • CentOS 7:ELK 日志平台部署
    • CentOS 7:SonarQube 部署
    • Selenium:Chrome 浏览器自动化
    • JJWT:令牌生成与解析测试
    • Spring 源码:阅读环境搭建
    • JUnit 4:注解、断言与参数化
    • JWT:令牌结构与签名机制
    • FastDFS:架构与文件存取机制
    • XPath:XML 文档节点定位
    • Redis 基础:锁、队列与事务
    • Redis 基础:数据类型与命令
    • MyBatis:Slf4j 日志接入
    • MyBatis:H2 单元测试与 SQL 日志
    • 源码阅读:开源项目环境搭建
    • Git 配置:命令清单与作用域
    • Java 核心:面向对象与基础类型
    • Java 核心:关键字、异常与反射
    • Java 核心:多线程基础
    • Java 核心:同步关键字与线程池
    • Java 核心:锁与并发工具
    • Java 核心:语言基础与并发
    • Dubbo:远程调用与服务治理
    • Java 集合:框架总览与实现对比
    • Maven:生命周期与常用命令
    • MyBatis:执行流程与插件机制
    • Spring:IoC 容器与依赖注入
    • Spring:AOP 与自动装配
    • Spring:事务与启动流程
    • Spring:IoC、AOP 与事务
    • Spring MVC:请求分发与注解
    • MySQL:架构与索引
    • MySQL:事务、锁与 MVCC
    • MySQL:日志与 SQL 优化
    • MySQL:架构、事务与优化
    • Redis 基础:持久化与线程模型
  • 2018年

    • Java HashMap:扩容机制与哈希冲突
    • Java 集合:HashSet 去重原理
    • Java 基础:交换两个变量的值
    • Spring MVC:零 web.xml 改造
    • Mac 开发环境:新机配置清单
    • Log4j:日志分级与按业务拆分
    • Modbus:工业通信协议与 RTU 帧
    • MySQL 基础:子查询与连接查询
    • MySQL 基础:库与表操作
    • MySQL 基础:表操作与查询
    • MySQL 基础:约束、引擎与数据类型
    • MySQL 基础:库表、约束与类型
    • Java 集合:Vector 与 Stack
    • Java 集合:Vector 与 Stack
    • RabbitMQ:CentOS 7 单机部署
    • Redis:CentOS 7 单机部署
    • MongoDB:CentOS 7 单机部署
    • Linux:常用系统与运维命令
    • 注册中心:Eureka 与 ZooKeeper
    • MySQL:CentOS 7 单机部署
    • Git 分支:主分支与临时分支
    • CentOS 7:Java 开发环境部署
    • Java 集合:LinkedList 双向链表
    • Java 集合:ArrayList 动态数组
    • Spring AOP:注解方式实现切面
← 返回博客

Redis:布隆过滤器判断元素存在

2021年6月11日 #数据与存储 #Redis #Spring

Redis 中不能直接使用布隆过滤器,Redis 4.0 版本之后提供的 modules(扩展模块)

布隆过滤器的原理

  • 数据结构使用一位的数组,每次存储键值的时候,不是直接把数据存储在数据结构中。而是经过hash运算。将此元素的 hash 值均匀的存储在位数组中。把这些位置设置成 1 就完成了添加操作。
  • 判断元素是否存在时,经过运算判断对应的位置是否为全部1即可。因此布隆过滤器查询此值存在时,此值不一定存在,但查询此值不存在时,此值一定不存在。
  • 但是存在一定的误差,并且当位数组存储值比较稀疏的时候,查询的准确率越高,而当位数组存储的值越来越多时,误差也会增大。

  • 空间占用
    • 布隆过滤器有两个参数,第一个是预计元素的数量n,第二个是误判率p。公式根据这两个输入得到两个输出,第一个输出是位数组的长度m,也就是需要的存储空间大小(bit),第二个输出是hash函数的最佳数量k。hash函数的数量也会直接影响到误判率,最佳的数量会有最低的误判率。
  • 计算公式
k≈0.7*(m/n)    
p≈0.6185^(m/n) 
  • 位数组m越长,误判率p就越低;
  • 位数组m越长,hash函数最佳数量k就越多,影响计算效率;

演示代码

安装Redis

演示情况直接使用docker来安装,免去下载编译过程。

docker run -p 6379:6379 -d redislabs/rebloom:latest
  • 使用redis-cli或者客户端工具进入
➜  docker-run redis-cli 
127.0.0.1:6379> bf.add 1 1
(integer) 0
127.0.0.1:6379> bf.add 1 2
(integer) 1
127.0.0.1:6379> 
  • 如果没有提示错误则表示安装成功。

Bloom基础用法

布隆过滤器的命令不是很多,主要包含以下几个

  • bf.add:添加元素
  • bf.exists:判断某个元素是否存在
  • bf.madd:添加多个元素
  • bf.mexists:判断多个元素是否存在
  • bf.reserve:设置布隆过滤器的准确率 只能在未设置数据的时候设置,否则会报错
127.0.0.1:6379> bf.exists 1 1
(integer) 1
127.0.0.1:6379> bf.exists 1 2
(integer) 1
127.0.0.1:6379> bf.reserve 1 0.01 100 # 已经存在集合在设置会报错
(error) ERR item exists
127.0.0.1:6379> bf.reserve user 0.01 100 # 未设置数据的则可以正常设置。
OK

Spring Boot 演示

/**
 * @author z201.coding@gmail.com
 **/
@Component
@Slf4j
public class BloomTool {


    @Autowired
    private RedisTemplate redisTemplate;

    /**
     * 初始化
     *
     * @param key
     * @param rate 准确度
     * @param size 大小
     */
    public Boolean init(String key, String rate, String size) {
        try {
            String script = "return redis.call('bf.reserve', KEYS[1], ARGV[1], ARGV[2])";
            DefaultRedisScript<String> defaultRedisScript = new DefaultRedisScript<String>();
            defaultRedisScript.setResultType(String.class);
            defaultRedisScript.setScriptSource(new StaticScriptSource(script));
            String[] argv = new String[]{rate,size};
            String result = (String) redisTemplate.execute(defaultRedisScript, Collections.singletonList(key), argv);
            if (Objects.equals(result, "OK")) {
                return true;
            }
        }catch (RedisSystemException redisSystemException){
            log.error("{}",redisSystemException.getMessage());
        }
        return false;
    }

    /**
     * 添加元素
     *
     * @param key
     * @param value
     */
    public Boolean add(String key, String value) {
        String script = "return redis.call('bf.add', KEYS[1], ARGV[1])";
        return lua(script, key, value);
    }

    /**
     * 是否存在
     *
     * @param key
     * @param value
     * @return
     */
    public Boolean exists(String key, Object value) {
        String script = "return redis.call('bf.exists', KEYS[1], ARGV[1])";
        return lua(script, key, value);
    }

    private Boolean lua(String script, String key, Object value) {
        DefaultRedisScript<Long> defaultRedisScript = new DefaultRedisScript<Long>();
        defaultRedisScript.setResultType(Long.class);
        defaultRedisScript.setScriptSource(new StaticScriptSource(script));
        Long result = (Long) redisTemplate.execute(defaultRedisScript, Collections.singletonList(key), value);
        if (Objects.equals(result, 1L)) {
            return true;
        }
        return false;
    }

}

  • 单元测试
package cn.z201.redis;

@Slf4j
@ExtendWith(SpringExtension.class)
@SpringBootTest(classes = AppApplication.class, webEnvironment = SpringBootTest.WebEnvironment.RANDOM_PORT)
@AutoConfigureMockMvc
// 指定单元测试方法顺序
@TestMethodOrder(MethodOrderer.OrderAnnotation.class)
public class AppApplicationTest {

    @Autowired
    BloomTool bloomTool;

    @Autowired
    RedisTemplate redisTemplate;

    @Test
    @Disabled
    public void testBloom() {
        Set<String> keys =  redisTemplate.keys("*");
        log.info("{}",keys);
        redisTemplate.delete(keys);
        String key = "u";
        log.info("init 异常或者错误都会报错 {}", bloomTool.init(key, "0.001", "10000000"));
        List<String> values = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            Integer value = RandomUtil.randomInt(1000, 20000000);
            values.add(value.toString());
            Boolean result =  bloomTool.add(key, value.toString());
            log.info("bf.add {} {} {} ", result, key, value);
        }
        Integer index = RandomUtil.randomInt(0, values.size());
        String value = values.get(index);
        Boolean result = bloomTool.exists(key, value);
        log.info("bf.exists {} {} {} ", result, key, value);
    }

}
  • Console
[main]  [u]
[main]  init 异常或者错误都会报错 true
[main]  bf.add true u 11569209 
[main]  bf.add true u 12786658 
[main]  bf.add true u 16272560 
[main]  bf.add true u 1212058 
[main]  bf.add true u 4896410 
[main]  bf.add true u 15218411 
[main]  bf.add true u 13349975 
[main]  bf.add true u 12544373 
[main]  bf.add true u 4507958 
[main]  bf.add true u 12143750 
[main]  bf.exists true u 1212058 

小结

位数组加多哈希使布隆过滤器不存在时必为假、存在时可能误判,bf.reserve 只能在集合为空时设误判率与容量,已有数据会返回 item exists。

最近更新: 2026/11/20 22:16
Contributors: 庆峰
Prev
测试:Spring Boot 分层 Mock
Next
Jenkins:安装配置与应用部署