请求到达时先经过过滤器还是拦截器_亿级数据过滤算法神器-布隆过滤器
发布日期:2021-09-12 18:30:25 浏览次数:3 分类:技术文章

本文共 3170 字,大约阅读时间需要 10 分钟。

Redis 是软件架构中常用的组件,最常见的用法是将热点数据缓存到 Redis 中,以减少数据库的压力;查询过程中最常见的用法是:查询 Redis,如果能查询到则直接返回,如果 Redis 中不存在则继续查询数据库。

这种方式可以减少数据库的访问次数,但是“当缓存中没有,就查询数据库”,在高并发的环境中依然会有风险,比如 90% 的请求数据都不在缓存中,那么这些请求就都会落到数据库上,这就是缓存穿透。

那么有没有什么办法解决这个问题呢?这就可以使用【布隆过滤器】了,它可以确定“某项数据肯定不存在”。

01.布隆过滤器的概念

布隆过滤器是一个叫“布隆”的人提出的,它本身是一个很长的二进制向量(想象成数组)和一系列随机映射函数(想象成多个 Hash 函数),二进制向量中存放的不是0,就是1(在学习布隆过滤器之前,可以先了解 BitMap 算法,便于理解)。

比如要根据客户手机号做为条件查询客户信息,通常会把手机号码设置成缓存中的 Key,让我们设置一个长度为 16 的布隆过滤器。

布隆过滤器初始化都是 0;

对 13800000000 分别进行 hash1()、hash2()、hash3() 运算,得到三个结果 5、9、12,把对应位置设置成 1;

428cd21d-6b16-eb11-8da9-e4434bdf6706.png

对 18900000000 分别进行 hash1()、hash2()、hash3() 运算,得到三个结果 2、8、12,把对应位置设置成 1,现在 2、5、8、9、12 都是 1,其余元素都是 0;

448cd21d-6b16-eb11-8da9-e4434bdf6706.png

如果我们想要验证某个电话号码是否存在,需要怎么做呢?

对 13700000000 分别进行 hash1()、hash2()、hash3() 运算,得到三个结果 1、9、13,然后去判断第 1、9、13 位上的值是 0 还是 1,如果不全是 1 的话,就说明 13700000000 不在这个布隆过滤器上;这就确定了“某项数据肯定不存在”。

458cd21d-6b16-eb11-8da9-e4434bdf6706.png

当然我们也可以看出来布隆过滤器有个问题,那就是不能保证数据肯定存在,比如对 18000000000 分别进行 hash1()、hash2()、hash3() 运算,得到的结果是 5、8、9,恰好这三位都是 1,但实际上这条数据并不存在,所以布隆过滤器有一定的误判率;

而且因为多个数据经过运算后可能会映射到同一个位置(138 和 189 的运算结果都有 12),所以布隆过滤器很难做到删除,除非要为每一位增加一个计数器,删除的时候需要给计数器减 1,直到计数器为 0 时,才将布隆过滤器对应位置修改成 0。

02.特点总结

可以确定一个元素肯定不存在,但是不能确定一个元素肯定存在;

二进制向量越长,映射函数越多,误判率越低;如果提前可以确定误判率,也可以反推出来布隆过滤器的长度;

可以添加元素,但是不能删除元素(除非增加计数器);

在存储空间和插入查询的时间复杂度都有巨大优势。

回到本文开头的那个业务场景,为了防止缓存穿透,可以使用布隆过滤器过滤掉肯定不存在的数据,误判的请求虽然还是会放到到数据库,但已经极大地减少了穿透的数量。

03.手写一个布隆过滤器

Code 不是目的,Coding 的过程是为了加深理解。

首先我们需要定义一个 bitmap,在 JDK 中,已经有对应实现的数据结构类

java.util.BitSet:

//设置一个布隆过滤器 private int DEFAULT_SIZE = 1 << 30;  private BitSet bitset ;

我们还需要一组映射函数,这里可以使用加法 hash 函数,设置 6 个质数,对应 6 个不同的 hash 函数:

//定义一个质数数组,长度为6,可以生成6个hash函数,用于随机映射 private int[] seeds = {3, 7, 13, 31, 37, 61};  private HashFunction[] functions = new HashFunction[seeds.length];

在构造函数中进行初始化,设置 BitSet 的长度,生成映射函数:

/** * 初始化 */ public BloomFilter() {   bitset = new BitSet(DEFAULT_SIZE);    for (int i = 0; i < seeds.length; i++) {       functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);   } }

增加元素的时候,对入参进行 6 次 hash 运算,并将结果对应的位置修改成 1(BitSet 对应的位置修改成 true):

/** * 添加一个元素,得到hash运算后的结果,将对应的位置修改成1(true) * @param value */ public void add(String value) {   if (value != null) {       for (HashFunction f : functions) {     bitset.set(f.hash(value), true);       }   } }

判断元素是否在布隆管理器中,需要对入参进行 6 次 hash 运算,再查看结果对应的位置上是 0 还是 1(true or false),如果其中一位是 0,表示数据肯定不存在,如果都是 1,表示数据(大概率)可能存在。

/** * 判断元素是否在布隆过滤器中 * @param value * @return */ public boolean contains(String value) {   if (value == null) {       return false;   }    for (HashFunction f : functions) {     if(!bitset.get(f.hash(value))){       //一个位置上不为1(true),就证明不存在,直接返回false       return false;     }   }    return true; }

04.Guava 中的 BloomFilter

已经有很多开源框架帮我们实现了布隆管理器,比如 Google 出品的 Guava 工具库,其中就有开箱即用的布隆过滤器;

public class BloomFilterTest {   public static void main(String[] args){     int size = 1000000;     //布隆过滤器     BloomFilter bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, 0.001);          for (int i = 0; i < size; i++) {             bloomFilter.put(i);         }          List list = new ArrayList(1000);         for (int i = size + 1; i < size + 10000; i++) {             if (bloomFilter.mightContain(i)) {                 list.add(i);             }         }         System.out.println("误判数量:" + list.size());   } }

转载地址:https://blog.csdn.net/weixin_39609822/article/details/110424550 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:boost原理与sklearn源码_Mongodb网络传输处理源码实现及性能调优-体验内核性能极致设计...
下一篇:python解释器文件后戳名_python文件处理、名称空间

发表评论

最新留言

初次前来,多多关照!
[***.217.46.12]2024年03月23日 00时40分36秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

linux服务器上已安装R 用户下载R包,R语言安装R package的2种方法 2019-04-21
linux 7 磁盘空间太小,Linux下磁盘保留空间的调整,解决df看到的空间和实际磁盘大小不一致的问题... 2019-04-21
linux下mysql 备份方法,Linux下mysql数据库备份方法小结 2019-04-21
bootstrap 页面垂直居中_iframe中如何让layer提示框显示在垂直居中的位置 2019-04-21
肺部ct重建_胸片检查容易漏诊肺癌,去年正常今年晚期常发生,体检一定要做CT... 2019-04-21
3dmax如何拆分模型_3D建模大佬如何制作出惊艳四方的游戏建模,看完这篇文章我知道了... 2019-04-21
x86so文件装换成arm64位_64位系统正式发布说明及介绍!! 2019-04-21
for循环中取出最大最小 累加_LeetCode之长度最小的子数组 2019-04-21
如何打开老公人脸识别_【话题】南宁已有小区启用人脸识别门禁,有人点赞有人忧... 2019-04-21
makex机器人程序_机器人教育为相城青少年叩开科学世界大门 2019-04-21
一寸照纯红色底图片_Ella陈嘉桦也是“时髦精”,穿玫红色西装配拼色半身裙,高级洋气... 2019-04-21
米哈游客户端笔试题_Garena校招 游戏客户端开发通关面经 2019-04-21
airpodspro没有弹窗_使用AirPods Pro一天的主观感受 2019-04-21
创建物化视图commit_视图及范式 2019-04-21
函数传参字典_Python新手上车17:函数传递任意多个参数 2019-04-21
去掉数组最后一个元素_【一天一大 lee】在排序数组中查找元素的第一个和最后一个位置 (难度:中等) Day20201201... 2019-04-21
秦九韶算法递推公式_算法讲解之复杂度分析 2019-04-21
添加绝对路径_网站中如何添加绝对路径 2019-04-21
python房价数据分析波士顿代码数据_python数据分析-波士顿房价预测-Go语言中文社区... 2019-04-21
redis线程阻塞原因排插_Redis阻塞原因详解 2019-04-21