牛哄哄的布隆过滤器，有什么用？

图片来自 包图网

万载ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景，ssl证书未来市场广阔！成为创新互联的ssl证书销售渠道，可以享受市场价格4-6折优惠！如果有意向欢迎电话联系或者加微信：13518219792（备注：SSL证书合作）期待与您的合作！

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

性能不够，缓存来凑

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

地址：

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

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

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

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

缓存没有命中，怎么办?

如上图：

  • 我们先查询缓存，判断缓存中是否有数据
  • 如果有数据，直接返回
  • 如果缓存为空，我们需要再查一次数据库，并将数据格式异构化，然后预热到缓冲中，然后将结果返回

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

那么如何处理缓存穿透?

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

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

简单归纳下，这个框架的要求：

  • 快速检索
  • 内存空间要非常小

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

什么是布隆过滤器?

布隆过滤器(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 的话，则保持不变。

布隆过滤器如何使用?

如下图：

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

  • 通过三个哈希函数对商品 id 计算哈希值
  • 然后，在布隆数组中查找访问对应的位值，0 或 1
  • 判断，三个值中，只要有一个不是 1，那么我们认为数据是不存在的。

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

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

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

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

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

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

数据初始化预热代码：

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

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

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

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

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

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

首先引入依赖包：

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

代码示例：

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

运行结果：

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

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

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

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

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

怎么办?

  • 方案 1：开发定时任务，每隔几个小时，自动创建一个新的布隆过滤器数组，替换老的，有点 CopyOnWriteArrayList 的味道。
  • 方案 2：布隆过滤器增加一个等长的数组，存储计数器，主要解决冲突问题，每次删除时对应的计数器减一，如果结果为 0，更新主数组的二进制值为 0。

布隆过滤器的应用场景

如下：

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

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

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

作者：Tom哥

编辑：陶家龙

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

当前文章：牛哄哄的布隆过滤器，有什么用？
文章位置：http://www.shufengxianlan.com/qtweb/news17/480767.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

虚拟主机知识

分类信息网站

成都标志设计　　 　成都圣月窗帘　　 　成都外贸网站优化　　 　响应式网站建设　　 　郫县封阳台　　 　网站建设开发　　 　益鑫餐饮　　 　高端网站设计　　 　成都包装设计公司　　 　网页设计　　 　定制网站制作　　 　乐山中领科信　　 　广汉锦华橡塑　　 　网站制作报价　　 　芦山网站建设　　 　四川乐山服务器托管　　 　微信公众号二次开发　　 　成都托管服务器　　 　成都响应式网站建设公司　　 　成都模版网站建设