文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

牛哄哄的布隆过滤器,有什么用?

2024-12-14 00:56

关注

图片来自 包图网

本文会介绍布隆过滤器,空间换时间,以较低的内存空间、高效解决这个问题。

性能不够,缓存来凑

现在的年轻人都喜欢网购,没事就逛逛淘宝,剁剁手,买些自己喜欢的东西,释放下工作压力。

地址:

  1. https://detail.tmall.com/item.htm?id=628993216729 

上图是一个天猫 iPhone12 的商品详情页,id 表示商品的编号。

我们都知道淘宝的访问量是非常高的,为了提升系统的吞吐量,做了很多性能优化,其中非常重要一点是将信息异构到缓存中。

有句话说的好:性能不够,缓存来凑。但是,使用缓存时,我们要关注一个重要问题,如果缓存没有命中怎么办?

[[421358]]

缓存没有命中,怎么办?

如上图:

注意:步骤③存在风险漏洞,如果缓存中数据不存在,压力会转嫁给数据库。假如被竞争对手利用,搞无效请求流量攻击,瞬间大量请求打到数据库中,对系统性能产生很大影响,很容易把数据库打挂,这种现象称为缓存穿透。

那么如何处理缓存穿透?

我们的思路是,缓存中能不能判断这个数据库值的存在性,如果真的不存在,直接返回,也避免一次数据库查询。

由于不存在是个无限边界,所以,我们采用反向策略,将存在的值建立一个高效的检索。每次缓存取值时,先走一次判空检索。

简单归纳下,这个框架的要求:

经调研,我们发现布隆过滤器具备以上两个条件。

什么是布隆过滤器?

布隆过滤器(Bloom Filter)是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。

布隆过滤器可以用于检索一个元素是否在一个集合中:

优点:空间效率和查询时间都远远超过一般的算法。

缺点:有一定的误识别率,删除困难。

布隆过滤器如何构建?

布隆过滤器本质上是一个 n 位的二进制数组,用 0 和 1 表示。假如我们以商品为例,有三件商品,商品编码分别为,id1、id2、id3。

①首先,对 id1,进行三次哈希,并确定其在二进制数组中的位置。

三次哈希,对应的二进制数组下标分别是 2、5、8,将原始数据从 0 变为 1。

②对 id2,进行三次哈希,并确定其在二进制数组中的位置。

三次哈希,对应的二进制数组下标分别是 2、7、98,将原始数据从 0 变为 1。

下标 2,之前已经被操作设置成 1,则本次认为是哈希冲突,不需要改动。

Hash 规则:如果在 Hash 后,原始位它是 0 的话,将其从 0 变为 1;如果本身这一位就是 1 的话,则保持不变。

布隆过滤器如何使用?

如下图:

跟初始化的过程有点类似,当查询一件商品的缓存信息时,我们首先要判断这件商品是否存在:

注意:布隆过滤器只能精确判断数据不存在情况,对于存在我们只能说是可能,因为存在 Hash 冲突情况,当然这个概率非常低。

如何减少布隆过滤器的误判?

①增加二进制位数组的长度。这样经过 hash 后数据会更加的离散化,出现冲突的概率会大大降低。

②增加 Hash 的次数,变相的增加数据特征,特征越多,冲突的概率越小。

布隆过滤器会不会很费内存?

带着疑问,我们来做个实验:假设有 1 千万个数据,我们需要记录其是否存在。存在的话标记 1,不存在标记为 0。技术选型,框架采用 Redis 的 BitMap 存储。

数据初始化预热代码:

  1. redisTemplate.executePipelined(new RedisCallback() { 
  2.     @Nullable 
  3.     @Override 
  4.     public Long doInRedis(RedisConnection connection) throws DataAccessException { 
  5.         connection.openPipeline(); 
  6.         for (int offset = 10000000; offset >= 0; offset--) { 
  7.             boolean value = offset % 2 == 0 ? true : false
  8.             connection.setBit("bloom-filter-data-1".getBytes(), offset, value); 
  9.         } 
  10.         connection.closePipeline(); 
  11.         return null
  12.     } 
  13. }); 
  14. System.out.println("数据预热完成"); 

性能有点慢,我们也可以采用分组形式,10000 个数一组,多批次提交。

数据上传完了后,大小 1.19M,跟我们设想的一样。

计算公式:10000000/8/1024/1024=1.19M

Java 应用中,如何使用布隆过滤器?

Java 语言的生态非常繁荣,提供了很多开箱即用的开源框架供我们使用。布隆过滤器也不例外,Java 中提供了一个 Redisson 的组件,它内置了布隆过滤器。

首先引入依赖包:

  1.  
  2.     org.redisson 
  3.     redisson 
  4.     3.11.1 
  5.  

代码示例:

  1.  
  2. @Test 
  3. public void test5() { 
  4.     Config config = new Config(); 
  5.     config.useSingleServer().setAddress("redis://172.16.67.37:6379"); 
  6.     RedissonClient cient = Redisson.create(config); 
  7.     RBloomFilter bloomFilter = cient.getBloomFilter("test5-bloom-filter"); 
  8.     // 初始化布隆过滤器,数组长度100W,误判率 1% 
  9.     bloomFilter.tryInit(1000000L, 0.01); 
  10.     // 添加数据 
  11.     bloomFilter.add("Tom哥"); 
  12.     // 判断是否存在 
  13.     System.out.println(bloomFilter.contains("微观技术")); 
  14.     System.out.println(bloomFilter.contains("Tom哥")); 

运行结果:

  1. false   // 肯定不存在 
  2. true    // 可能存在,有1%的误判率 

注意:误判率设置过小,会产生更多次的 Hash 操作,降低系统的性能。通常我们的建议值是 1%。

布隆过滤器二进制数组,如何处理删除?

初始化后的布隆过滤器,可以直接拿来使用了。但是如果原始数据删除了怎么办?布隆过滤器二进制数组如何维护?

直接删除不行吗?还真不行!因为这里面有 Hash 冲突的可能,会导致误删。

怎么办?

布隆过滤器的应用场景

如下:

本文重点介绍的,解决缓存穿透。

网页爬虫对 URL 的去重,避免爬取相同的 URL 地址。

反垃圾邮件,从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱。

作者:Tom哥

编辑:陶家龙

出处:转载自公众号微观技术(ID:weiguanjishu)

 

来源:微观技术内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯