防缓存穿透利器-布隆滤器(BloomFilter)

这篇具有很好参考价值的文章主要介绍了防缓存穿透利器-布隆滤器(BloomFilter)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

布隆过滤器

  • 1、布隆过滤器原理
    • 1.1 什么是布隆过滤器
    • 1.2 使用场景
    • 1.3 原理
    • 1.4 布隆过滤器的优缺点
  • 2、实现方式
    • 2.1 初始化skuId的布隆过滤器
      • 2.1.1 RedisConst常量类
      • 2.1.2 修改启动类
    • 2.2 给商品详情页添加布隆过滤器

1、布隆过滤器原理

1.1 什么是布隆过滤器

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。

主要用于判断一个元素是否在一个集合中,0代表不存在某个数据,1代表存在某个数据。

总结: 一个元素一定不存在 或者 可能存在! 存在一定的误判率{通过代码调节}

1.2 使用场景

大数据量的时候, 判断一个元素是否在一个集合中。解决缓存穿透问题

1.3 原理

存入过程

布隆过滤器上面说了,就是一个二进制数据的集合。当一个数据加入这个集合时,经历如下:

  • 通过K个哈希函数计算该数据,返回K个计算出的hash值

  • 这些K个hash值映射到对应的K个二进制的数组下标

  • 将K个下标对应的二进制数据改成1。


例如,第一个哈希函数返回x,第二个第三个哈希函数返回y与z,那么: X、Y、Z对应的二进制改成1。

如图所示:

查询过程

布隆过滤器主要作用就是查询一个数据,在不在这个二进制的集合中,查询过程如下:

1、通过K个哈希函数计算该数据,对应计算出的K个hash值

2、通过hash值找到对应的二进制的数组下标

3、判断:如果存在一处位置的二进制数据是0,那么该数据不存在。如果都是1,该数据存在集合中。


1.4 布隆过滤器的优缺点

  • 优点
  1. 由于存储的是二进制数据,所以占用的空间很小
  2. 它的插入和查询速度是非常快的,时间复杂度是O(K),空间复杂度:O (M)。

K: 是哈希函数的个数

M: 是二进制位的个数

  1. 保密性很好,因为本身不存储任何原始数据,只有二进制数据

  • 缺点:

添加数据是通过计算数据的hash值,那么很有可能存在这种情况:两个不同的数据计算得到相同的hash值。

例如图中的“张三”和“张三丰”,假如最终算出hash值相同,那么他们会将同一个下标的二进制数据改为1。

这个时候,你就不知道下标为1的二进制,到底是代表“张三”还是“张三丰”。


由此得出以下缺点:

1、存在误判

假如上面的图没有存 “张三”,只存了 “张三丰”,那么用"张三"来查询的时候,会判断"张三"存在集合中。

因为“张三”和“张三丰”的hash值是相同的,通过相同的hash值,找到的二进制数据也是一样的,都是1。

误判率:

受三个因素影响: 二进制位的个数m, 哈希函数的个数k, 数据规模n (添加到布隆过滤器中的数据)

已知误判率p, 数据规模n, 求二进制的个数m,哈希函数的个数k {m,k 程序会自动计算 ,你只需要告诉我数据规模,误判率就可以了}

ln: 自然对数是以常数e为底数的对数,记作lnN(N>0)。在物理学,生物学等自然科学中有重要的意义,一般表示方法为lnx。数学中也常见以logx表示自然对数。

2、删除困难

还是用上面的举例,因为“张三”和“张三丰”的hash值相同,对应的数组下标也是一样的。

如果你想去删除“张三”,将下标为1里的二进制数据,由1改成了0。

那么你是不是连“张三丰”都一起删了。

2、实现方式

2.1 初始化skuId的布隆过滤器

我在service-product模块中操作

2.1.1 RedisConst常量类

public class RedisConst {

    public static final String SKUKEY_PREFIX = "sku:";
    public static final String SKUKEY_SUFFIX = ":info";
    //单位:秒
    public static final long SKUKEY_TIMEOUT = 24 * 60 * 60;
    // 定义变量,记录空对象的缓存过期时间
    public static final long SKUKEY_TEMPORARY_TIMEOUT = 10 * 60;

    //单位:秒 尝试获取锁的最大等待时间
    public static final long SKULOCK_EXPIRE_PX1 = 100;
    //单位:秒 锁的持有时间
    public static final long SKULOCK_EXPIRE_PX2 = 10;
    public static final String SKULOCK_SUFFIX = ":lock";

    public static final String USER_KEY_PREFIX = "user:";
    public static final String USER_CART_KEY_SUFFIX = ":cart";
    public static final long USER_CART_EXPIRE = 60 * 60 * 24 * 30;

    //用户登录
    public static final String USER_LOGIN_KEY_PREFIX = "user:login:";
    //    public static final String userinfoKey_suffix = ":info";
    public static final int USERKEY_TIMEOUT = 60 * 60 * 24 * 7;

    //秒杀商品前缀
    public static final String SECKILL_GOODS = "seckill:goods";
    public static final String SECKILL_ORDERS = "seckill:orders";
    public static final String SECKILL_ORDERS_USERS = "seckill:orders:users";
    public static final String SECKILL_STOCK_PREFIX = "seckill:stock:";
    public static final String SECKILL_USER = "seckill:user:";
    //用户锁定时间 单位:秒
    public static final int SECKILL__TIMEOUT = 60 * 60 * 1;

    //  布隆过滤器使用!
    public static final String SKU_BLOOM_FILTER="sku:bloom:filter";
}
123456789101112131415161718192021222324252627282930313233343536

2.1.2 修改启动类

@SpringBootApplication
@ComponentScan({"com.atguigu.gmall"})
@EnableDiscoveryClient
public class ServiceProductApplication implements CommandLineRunner {

    @Autowired
    private RedissonClient redissonClient;

    public static void main(String[] args) {
        SpringApplication.run(ServiceProductApplication.class,args);
    }

    //初始化布隆过滤器
    @Override
    public void run(String... args) throws Exception {
        //获取布隆过滤器
        RBloomFilter<Object> bloomFilter = redissonClient.getBloomFilter(RedisConst.SKU_BLOOM_FILTER);
        //初始化布隆过滤器:计算元素的数量 比如预计有多少个sku
        bloomFilter.tryInit(10001,0.001);
    }
}
123456789101112131415161718192021

2.2 给商品详情页添加布隆过滤器

1、查看商品详情页添加布隆过滤器

操作模块:service-item

更改ItemserviceImpl.item方法

2、添加商品sku加入布隆过滤器数据

操作模块:service-product

更改ManageServiceImpl.saveSkuInfo方法

这样就避免了别人用一个不存在的key去疯狂攻击我们的缓存数据库。

我们在分布式锁中将查询结果是null的也进行缓存,但是如果有人用随机数去疯狂请求我们的接口,那我们的Redis可能会扛不住,所以在这里用布隆过滤器,只需要在初始化的时候,指定我们存储数据的数据量和可以承受的误判率即可。

布隆过滤器指导有哪些数据,这样别人使用随机数攻击的时候直接就给他返回,不用再去查Redis了。文章来源地址https://www.toymoban.com/news/detail-576507.html

到了这里,关于防缓存穿透利器-布隆滤器(BloomFilter)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • redis中使用bloomfilter的白名单功能解决缓存穿透问题

    将需要的数据提前缓存到缓存redis中,可以在服务启动时候,或者在使用前一天完成数据的同步等操作。保证后续能够正常使用。 在redis中,查询redis缓存数据没有内容,接着查询mysql数据库,也没有需要的内容,做了两次无用的查询。进而造成mysql数据库的负担,造成一系列

    2024年02月16日
    浏览(69)
  • Redis 原理缓存过期、一致性hash、雪崩、穿透、并发、布隆、缓存更新策略、缓存数据库一致性

    redis的过期策略可以通过配置文件进行配置 redis会把设置了过期时间的key放在单独的字典中,定时遍历来删除到期的key。 1).每100ms从过期字典中 随机挑选20个,把其中过期的key删除; 2).如果过期的key占比超过1/4,重复步骤1 为了保证不会循环过度,导致卡顿,扫描时间上限

    2024年02月08日
    浏览(58)
  • 算法~布隆过滤器

    布隆过滤器(Bloom Filter)是一种高效的概率数据结构,用于判断一个元素是否存在于集合中。它基于位数组和多个哈希函数,并具有以下特点: Bloom Filter 是一个基于概率的数据结构:它只能告诉我们一个 元素绝对不在集合内 或 可能在集合内 快速查询:布隆过滤器具有快速

    2024年02月05日
    浏览(46)
  • 布隆过滤器及其应用

    布隆过滤器是一种数据结构,具有快速插入和查找的特性,能确定某个字符串一定存在或者可能存在。布隆过滤器有着高效的空间利用率,它不存储具体数据,只存储数据的关键标识,所以占用的空间较小。它的查询结果可能会存在一定误差,但是误差总体可控,同时不支持

    2024年02月03日
    浏览(43)
  • 位图以及布隆过滤器

    本文主要讲解哈希思想的实际应用,位图和布隆过滤器。 讲解位图之前我们先来解答这样一道腾讯的面试题 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。【腾讯】 很多人立马就想到了用哈希表或者红黑树,因为足够

    2024年02月08日
    浏览(53)
  • 布隆过滤器详解

    本文全部代码地址 布隆过滤器是一种高效的数据结构,用于判断一个元素是否存在于一个集合中.它的主要优点是速度快,空间占用少,因此在需要快速判断某个元素是否在集合中的场合得到广泛引用. 布隆过滤器就是 一个大型的位数组和几个不一样的无偏hash函数. 所谓无偏就是

    2023年04月22日
    浏览(54)
  • 布隆过滤器的原理

    布隆过滤器是一种用于检索一个元素是否在一个集合中的数据结构,具有高效的查询性能和较小的内存占用。 布隆过滤器的底层实现主要涉及以下几个步骤: 初始化数组: 首先,初始化一个比较大的数组,数组中的元素用二进制表示,初始值都为0。 Hash计算: 当一个新的元

    2024年01月18日
    浏览(39)
  • Redis----布隆过滤器

    目录 背景 解决方案 什么是布隆过滤器 布隆过滤器的原理 一些其他运用 比如我们在观看新闻或者刷微博的时候,会不停地给我们推荐新的内容,我们发现几乎没有重复的,说明后台已经进行了去重处理,基于如何去重,Redis给出了高效的方案---布隆过滤器 1.记录已经浏览过

    2024年02月09日
    浏览(38)
  • 解释一下布隆过滤器原理

    锁屏面试题百日百刷,每个工作日坚持更新面试题。请看到最后就能获取你想要的,接下来的是今日的面试题: 1.解释一下布隆过滤器原理 在日常生活中,包括在设计计算机软件时,我们经常要判断一个元素是否在一个集合中。比如在字处理软件中,需要检查一个英语单词是

    2023年04月10日
    浏览(51)
  • 哈希的应用——布隆过滤器

    上一篇文章,我们学习了位图,位图在某些场景下是非常适用的,非常快捷方便。 但是,在文章的最后,我们也提出了位图的一些缺陷——比如位图只能映射整型数据,其它类型的数据则不行。 因为位图里面的元素去映射的其实就是下标嘛,而下标的话都是整型啊。 那有没

    2024年02月09日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包