详解布隆过滤器的原理、使用场景和注意事项

简介: 详解布隆过滤器的原理、使用场景和注意事项

去重去重去重(如果懂原理,直接看下边吧)


今天碰到个业务,他的 Redis 集群有个大 Value 用途是作为布隆过滤器,但沟通的时候被小怼了一下,意思大概是 “布隆过滤器原理都不懂,还要我优化?”。技术菜被人怼认了、怪不得别人,自己之前确实只是听说过这个,但是没深入了解过,趁这个机会补充一下知识。


在进入正文之前,之前看到的有句话我觉得说得很好:


Data structures are nothing different. They are like the bookshelves of your application where you can organize your data. Different data structures will give you different facility and benefits. To properly use the power and accessibility of the data structures you need to know the trade-offs of using one.


大意是不同的数据结构有不同的适用场景和优缺点,你需要仔细权衡自己的需求之后妥善适用它们,布隆过滤器就是践行这句话的代表。


什么是布隆过滤器

本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。


相比于传统的 List、Set、Map 等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的。


实现原理

HashMap 的问题

讲述布隆过滤器的原理之前,我们先思考一下,通常你判断某个元素是否存在用的是什么?应该蛮多人回答 HashMap 吧,确实可以将值映射到 HashMap 的 Key,然后可以在 O(1) 的时间复杂度内返回结果,效率奇高。但是 HashMap 的实现也有缺点,例如存储容量占比高,考虑到负载因子的存在,通常空间是不能被用满的,而一旦你的值很多例如上亿的时候,那 HashMap 占据的内存大小就变得很可观了。


还比如说你的数据集存储在远程服务器上,本地服务接受输入,而数据集非常大不可能一次性读进内存构建 HashMap 的时候,也会存在问题。


布隆过滤器数据结构

布隆过滤器是一个 bit 向量或者说 bit 数组,长这样:





image


如果我们要映射一个值到布隆过滤器中,我们需要使用多个不同的哈希函数生成多个哈希值,并对每个生成的哈希值指向的 bit 位置 1,例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7,则上图转变为:





image


Ok,我们现在再存一个值 “tencent”,如果哈希函数返回 3、4、8 的话,图继续变为:





image


值得注意的是,4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位,因此它被覆盖了。现在我们如果想查询 “dianping” 这个值是否存在,哈希函数返回了 1、5、8三个值,结果我们发现 5 这个 bit 位上的值为 0,说明没有任何一个值映射到这个 bit 位上,因此我们可以很确定地说 “dianping” 这个值不存在。而当我们需要查询 “baidu” 这个值是否存在的话,那么哈希函数必然会返回 1、4、7,然后我们检查发现这三个 bit 位上的值均为 1,那么我们可以说 “baidu” 存在了么?答案是不可以,只能是 “baidu” 这个值可能存在。


这是为什么呢?答案跟简单,因为随着增加的值越来越多,被置为 1 的 bit 位也会越来越多,这样某个值 “taobao” 即使没有被存储过,但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ,那么程序还是会判断 “taobao” 这个值存在。


支持删除么

目前我们知道布隆过滤器可以支持 add 和 isExist 操作,那么 delete 操作可以么,答案是不可以,例如上图中的 bit 位 4 被两个值共同覆盖的话,一旦你删除其中一个值例如 “tencent” 而将其置位 0,那么下次判断另一个值例如 “baidu” 是否存在的话,会直接返回 false,而实际上你并没有删除它。


如何解决这个问题,答案是计数删除。但是计数删除需要存储一个数值,而不是原先的 bit 位,会增大占用的内存大小。这样的话,增加一个值就是将对应索引槽上存储的值加一,删除则是减一,判断是否存在则是看值是否大于0。


如何选择哈希函数个数和布隆过滤器长度

很显然,过小的布隆过滤器很快所有的 bit 位均为 1,那么查询任何值都会返回“可能存在”,起不到过滤的目的了。布隆过滤器的长度会直接影响误报率,布隆过滤器越长其误报率越小。


另外,哈希函数的个数也需要权衡,个数越多则布隆过滤器 bit 位置位 1 的速度越快,且布隆过滤器的效率越低;但是如果太少的话,那我们的误报率会变高。





image


k 为哈希函数个数,m 为布隆过滤器长度,n 为插入的元素个数,p 为误报率。

至于如何推导这个公式,我在知乎发布的文章有涉及,感兴趣可以看看,不感兴趣的话记住上面这个公式就行了。


最佳实践

常见的适用常见有,利用布隆过滤器减少磁盘 IO 或者网络请求,因为一旦一个值必定不存在的话,我们可以不用进行后续昂贵的查询请求。


另外,既然你使用布隆过滤器来加速查找和判断是否存在,那么性能很低的哈希函数不是个好选择,推荐 MurmurHash、Fnv 这些。


大Value拆分

Redis 因其支持 setbit 和 getbit 操作,且纯内存性能高等特点,因此天然就可以作为布隆过滤器来使用。但是布隆过滤器的不当使用极易产生大 Value,增加 Redis 阻塞风险,因此生成环境中建议对体积庞大的布隆过滤器进行拆分。


拆分的形式方法多种多样,但是本质是不要将 Hash(Key) 之后的请求分散在多个节点的多个小 bitmap 上,而是应该拆分成多个小 bitmap 之后,对一个 Key 的所有哈希函数都落在这一个小 bitmap 上。


参考资料

probabilistic data structures:bloom filter

bloom filters

本文遵守创作共享 CC BY-NC-SA 3.0协议

目录
相关文章
|
JSON JavaScript 前端开发
解决js中Long类型数据在请求与响应过程精度丢失问题(springboot项目中)
解决js中Long类型数据在请求与响应过程精度丢失问题(springboot项目中)
1334 0
|
Java 开发者 Spring
探索Spring Boot中的原则:约定大于配置
在软件开发领域,简化和提高开发效率一直是追求的目标。而"约定大于配置"(Convention Over Configuration)正是一种理念,旨在通过默认约定和规则来减少开发人员需要做的配置工作。在Spring Boot框架中,这一原则得到了充分应用,帮助开发者更快地构建高效的应用程序。本文将深入探讨"约定大于配置"的概念、优势以及在Spring Boot中的实践。
1981 0
|
Rust 算法 Go
【密码学】一文读懂MurMurHash3
本文应该是MurMurHash算法介绍的最后一篇,来一起看一下最新的MurMurHash算法的具体过程,对于最新的算法来说,整个流程和之前的其实也比较相似,这里从维基百科当中找到了伪代码,也就不贴出来Google官方给出的推荐代码了,先来看一下维基百科给出的伪代码,这里只有32位的伪代码。
2732 0
【密码学】一文读懂MurMurHash3
|
5月前
|
消息中间件 大数据 关系型数据库
RocketMQ实战—3.基于RocketMQ升级订单系统架构
本文主要介绍了基于MQ实现订单系统核心流程的异步化改造、基于MQ实现订单系统和第三方系统的解耦、基于MQ实现将订单数据同步给大数据团队、秒杀系统的技术难点以及秒杀商详页的架构设计和基于MQ实现秒杀系统的异步化架构。
403 64
RocketMQ实战—3.基于RocketMQ升级订单系统架构
|
存储 SQL 安全
MySQL 安全加固配置(等保二级)
数据库安全是等保测评和网络安全中的重要的一项内容,本文介绍一些常见的加固配置。
4760 0
|
5月前
|
监控 Java Unix
6个Java 工具,轻松分析定位 JVM 问题 !
本文介绍了如何使用 JDK 自带工具查看和分析 JVM 的运行情况。通过编写一段测试代码(启动 10 个死循环线程,分配大量内存),结合常用工具如 `jps`、`jinfo`、`jstat`、`jstack`、`jvisualvm` 和 `jcmd` 等,详细展示了 JVM 参数配置、内存使用、线程状态及 GC 情况的监控方法。同时指出了一些常见问题,例如参数设置错误导致的内存异常,并通过实例说明了如何排查和解决。最后附上了官方文档链接,方便进一步学习。
468 4
|
4月前
|
安全 编译器 开发工具
鸿蒙系统”套壳论”的认知迷思与技术真相-优雅草卓伊凡
鸿蒙系统”套壳论”的认知迷思与技术真相-优雅草卓伊凡
113 0
鸿蒙系统”套壳论”的认知迷思与技术真相-优雅草卓伊凡
|
6月前
|
算法
面试场景题:如何设计一个抢红包随机算法
本文详细解析了抢红包随机算法的设计与实现,涵盖三种解法:随机分配法、二倍均值法和线段切割法。随机分配法通过逐次随机分配金额确保总额不变,但易导致两极分化;二倍均值法优化了金额分布,使每次抢到的金额更均衡;线段切割法则将总金额视为线段,通过随机切割点生成子金额,手气最佳金额可能更高。代码示例清晰,结果对比直观,为面试中类似算法题提供了全面思路。
1082 16
|
缓存 NoSQL Java
Spring Boot 3 整合 Spring Cache 与 Redis 缓存实战
Spring Boot 3 整合 Spring Cache 与 Redis 缓存实战
|
9月前
|
SQL 缓存 关系型数据库
MySQL Limit实现原理
本文深入解析了MySQL中`LIMIT`子句的实现原理及其在分页、性能优化等场景下的应用技巧。文章详细介绍了`LIMIT`的基本语法、MySQL内部处理流程,以及如何通过索引优化、覆盖索引等策略提升分页查询的性能,并提供了实践建议。
691 3