专栏首页架构精进之路一文讲透“布隆过滤器”

一文讲透“布隆过滤器”

1、什么是布隆过滤器?

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

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

2、为什么需要布隆过滤器?

2.1 缓存穿透

我们经常会把一部分数据放在Redis中缓存,比如文章详情。

这样有查询请求进来,我们可以根据文章Id直接去缓存中取数据,而不用读取数据库,这是提升性能最简单,最普遍,也是最有效的做法。

一般的查询请求流程是这样的:先查缓存(有缓存的话直接返回)-> 如果缓存中没有,再去数据库查询(把数据库取出来的数据放入缓存)-> 返回数据

好像一切看起来很美好。

问题:如果现在有大量请求进来,而且都在请求一个不存在的文章Id,那将会发生什么?

既然文章Id都不存在,那么肯定没有对应的缓存信息,没有缓存,那么大量的请求都堆积到数据库,数据库的压力一下子就上来了,甚至可能把数据库打满跑死。

2.2 大范围查询

查询近1亿用户手机号系统中是否存在其交易信息,如何做到判断的准确快速?

方案一:通过数据库查询

查询压力好像有点大,做不到高效而且还存在数据库服务被压垮的风险。

方案二:通过Redis缓存(存在交易单的用户手机号放入Set)

可能会产生大Key造成慢查询,同时内存资源会造成浪费。

以上例子有一个共同的特点: 如何判断一个元素是否存在一个集合中。这些问题用其他方式可能都会解决,但“布隆过滤器”就能够有效的解决。

3、布隆过滤器实现原理

3.1 哈希函数

哈希函数的概念:将任意大小的数据转换成特定大小的数据的函数,转换后的数据称为哈希值或哈希编码。示意图如下所示:

可以明显的看到,原始数据经过哈希函数的映射后成为了一个个的哈希编码,数据得到压缩。哈希函数是实现哈希表和布隆过滤器的基础。

3.2 数据结构

布隆过滤器是一个 bit 向量或者说 bit 数组,示意图如下所示:

布隆过滤器(Bloom Filter)的核心实现是一个超大的位数组和几个哈希函数。

假设我们要将x、y、z三元素放入布隆过滤器再去检索w,示意图如下所示:

具体的操作流程如下:

假设集合里面有3个元素{x, y, z},哈希函数的个数为3。将位数组进行初始化,将里面每个位都设置为0。

  • 设置:对于集合{x, y, z}里面的每一个元素,将元素依次通过3个哈希函数进行映射,每次映射都会产生一个哈希值,这个值对应位数组上面的一个点,然后将位数组对应的位置标记为1(这样位置2、4、5、6、12、14、17均为1)。
  • 查询:判断W元素是否存在集合中的时候,同样的方法将W通过哈希映射到位数组上的3个点(位置:5、14、16)。如果3个点的其中有一个点不为1,则可以判断该元素一定不存在集合中。反之,如果3个点都为1,则该元素可能存在集合中。

注意:此处不能判断该元素是否一定存在集合中,可能存在一定的误判率。 假设某个元素通过映射对应下标为4,5,6 这3个点。虽然这3个点都为1,但是很明显这3个点是不同元素经过哈希得到的位置,因此这种情况说明元素虽然不在集合中,也可能对应的都是1,由此推断出误判率存在的可能性。

4、布隆过滤器操作

4.1 添加元素

语法:[bf.add  key  options]

127.0.0.1:6379> bf.add users 15012345678
(integer) 1
  • 将要添加的元素给k个哈希函数
  • 得到对应于位数组上的k个位置
  • 将这k个位置设为1

4.2 查询元素

语法:[bf.exists  key  options]

127.0.0.1:6379> bf.exists users 15012345678
(integer) 1
127.0.0.1:6379> bf.exists users 15012345679
(integer) 0
  • 将要查询的元素给k个哈希函数
  • 得到对应于位数组上的k个位置
  • 如果k个位置有一个为0,则肯定不在集合中
  • 如果k个位置全部为1,则可能在集合中

4.3 删除元素

传统的布隆过滤器并不支持删除操作。

但是名为 Counting Bloom Filter 的变种可以用来测试元素计数个数是否绝对小于某个阈值,它支持元素删除。大家感兴趣可自行检索了解~

5、最佳实践

5.1 应用场景

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

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

5.2 设置哈希函数个数和布隆过滤器长度

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

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


往期热文推荐:


「技术架构精进」专注架构研究,技术分享

Thanks for reading!

本文分享自微信公众号 - 架构精进之路(jiagou_jingjin),作者:架构精进之路

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员不得不知的软技能

    程序员群体不应该是一直低头敲代码,更应该掌握一些软技能,改变一贯的沉闷木讷的形象,让自己在竞争中胜出,从而职业发展更顺利。在此总结整理了几个常用软技能点供大家参...

    架构精进之路
  • 超全面分布式缓存高可用方案:哨兵机制

    开发工作中对于分布式缓存高可用方案(搭建Redis缓存高可用方案),Redis主从架构下是如何保证高可用的呢?

    架构精进之路
  • MySQL explain 中的 rows 究竟是如何计算的?

    疑问1:上述SQL理应按id主键(聚簇索引)范围查找,为啥explain里的rows会多余两者之差呢?

    架构精进之路
  • 持续3分钟 - Java -10

    集合类存放于 Java.util 包中,主要有 3 种:set(集)、list(列表包含 Queue)和 map(映射)。

    子乾建建-Jeff
  • ASP.NET MVC5+EF6+EasyUI 后台管理系统(44)-工作流设计-设计表单

    设计表单是比较复杂的一步,完成一个表单的设计其实很漫长,主要分为四步。 ? 开始之前先说说表的结构。 其实表Flow_Form与Flow_FormContent...

    用户1149182
  • java之学习date类的综合案例-算一下你来到这个世界多少天

    吾爱乐享
  • PON发展趋势:10G PON已开启全面性部署应用

    PON技术是宽带接入网业务承载的重要方式,伴随着4K视频、虚拟现实等大流量、高带宽业务的开展和普及,10G PON在光接入网络中具有非常光明的前景,必将在不远的...

    易天光通信
  • 面经 | 图森未来-感知算法工程师(20校招)

    首先box的数量大小是不固定的,不好直接融合;其次,类别概率图可以一次把整张图的关于小物体的信息都表示出来

    AI算法与图像处理
  • 可折叠手机喂肥了黄牛,但柔性屏的未来从来不止手机

    早在2月12日,三星发布了Galaxy Z Flip后,次日柔性屏概念股延续了10股涨停的狂飙突进态势,维信诺、京东方A、领益智造等10只股票继续涨停,老板笑得...

    用户2908108
  • 高并发后端设计-限流篇

    系统在设计之初就会有一个预估容量,长时间超过系统能承受的TPS/QPS阈值,系统可能会被压垮,最终导致整个服务不够用。为了避免这种情况,我们就需要对接口请求进行...

    Java高级架构

扫码关注云+社区

领取腾讯云代金券