43.【面试宝典】面试宝典-redis缓存穿透之布隆过滤器

本文涉及的产品
云数据库 Tair(兼容Redis),内存型 2GB
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
简介: 【面试宝典】面试宝典-redis缓存穿透之布隆过滤器

前文如上:

39.【面试宝典】面试宝典-redis过期k值回收策略,缓存淘汰策略

40.【面试宝典】面试宝典-redis持久化

41.【面试宝典】面试宝典-redis常用数据类型概述

42.【面试宝典】面试宝典-redis缓存穿透,击穿,雪崩

合集参考:面试宝典


布隆过滤器


1.1 概念


布隆过滤器(Bloom Filter)是1970年由布隆提出的,它实际上是由一个很长的二进制向量和一系列随意映射函数组成。它是一种基于概率的数据结构,主要用来判断某个元素是否在集合内,它具有运行速度快(时间效率),占用内存小的优点(空间效率),但是有一定的误识别率和删除困难的问题。它能够告诉你某个元素一定不在集合内或可能在集合内。


1.2 背景


如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为O(n),O(log n),O(1)。


1.3 原理


布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。 –引自《维基百科,自由的百科全书》


1.3.1 分析


布隆过滤器(Bloom Filter)本质上是由长度为 m 的位向量或位列表(仅包含 0 或 1 位值的列表)组成,最初所有的值均设置为 0


举例,假设数组长度m=19,每个值根据hash散列计算,算出k=2个哈希值 (选用hash算法,必然就会存在碰撞的可能。k=2不同的值计算出来的hash值很有可能会出现一致。k值越大,即为同一个值取不同的多个hash值,取的越多。碰撞率的几率就越小。当然hash的数量也不是越多越好,多的话影响效率。)


1.3.2 插入数据

网络异常,图片无法展示
|

如上图,插入了两个元素,X和Y,X的两次hash取模后的值分别为4,9,因此,4和9位被置成1;Y的两次hash取模后的值分别为14和19,因此,14和19位被置成1。


1.3.3 插入流程

  1. 将要添加的元素给k个哈希函数
  2. 得到对应于位数组上的k个位置
  3. 将这k个位置设为1

1.3.4 查找数据

BloomFilter中查找一个元素,会使用和插入过程中相同的k个hash函数,取模后,取出每个bit对应的值,如果所有bit都为1,则返回元素可能存在,否则,返回元素不存在。

1.3.5 查询流程说明

  1. 将要查询的元素给k个哈希函数
  2. hash计算得到对应于位数组上的k个位置
  3. 如果k个位置有一个为0,则一定不在集合中
  4. 如果k个位置全部为1,则可能在集合中

1.3.6 误差率

为什么bit全部为1时,元素只是可能存在呢? 当然,如果情况如上图中只存在X、Y,而且两个元素hash后的值并不重复。那么这种情况就可以确定元素一定存在。

但是,存在另一种情况。假设我们现在要查询Z元素,假设Z元素并不存在。但是巧了经过hash计算出来的位置为9,14。我们很清楚,这里的9是属于X元素的,14是术语Y元素的。并不存在Z。但是经过hash计算的结果返回值都是1。所以程序认为Z是存在的,但实际上Z并不存在,此现象称为false positive

网络异常,图片无法展示
|


1.3.7 不能删除数据

BloomFilter中不允许有删除操作,因为删除后,可能会造成原来存在的元素返回不存在,这个是不允许的,还是上面例子说明:

网络异常,图片无法展示
|


上图中,刚开始时,有元素X,Y和Z,其hash的bit如图中所示,当删除X后,会把bit 4和9置成0,这同时会造成查询Z时,报不存在的问题,这对于BloomFilter来讲是不能容忍的,因为它要么返回绝对不存在,要么返回可能存在


问题:BloomFilter中不允许删除的机制会导致其中的无效元素可能会越来越多,即实际已经在磁盘删除中的元素,但在bloomfilter中还认为可能存在,这会造成越来越多的误差率


1.4 优缺点


1.4.1 优点


相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数(O(k))。另外, 散列函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。


  • 对于hashmap,其本质上是一个指针数组,一个指针的开销是sizeof(void *),在64bit的系统上是64个bit,如果采用开链法处理冲突的话,又需要额外的指针开销,而对于BloomFilter来讲,返回可能存在的情况中,如果允许有1%的错误率的话,每个元素大约需要10bit的存储空间,整个存储空间的开销大约是hashmap的15%左右(数据来自维基百科)
  • 对于set,如果采用hashmap方式实现,情况同上;如果采用平衡树方式实现,一个节点需要一个指针存储数据的位置,两个指针指向其子节点,因此开销相对于hashmap来讲是更多的
  • 对于bit array,对于某个元素是否存在,先对元素做hash,取模定位到具体的bit,如果该bit为1,则返回元素存在,如果该bit为0,则返回此元素不存在。可以看出,在返回元素存在的时候,也是会有误判的,如果要获得和BloomFilter相同的误判率,则需要比BloomFilter更大的存储空间

布隆过滤器可以表示全集,其它任何数据结构都不能;

  1. 全量存储但是不存储数据本身,适合有保密要求的场景
  2. 空间复杂度为O(m),不会随着元素增加而增加,占用空间少
  3. 插入和查询时间复杂度都是 O(k), 不会随着元素增加而增加,远超一般算法。


1.4.2 缺点


但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。


另外,一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。


  • 相对于hashmap和set,BloomFilter在返回元素可能存在的情况中,有一定的误判率,这时候,调用者在误判的时候,会做一些不必要的工作,而对于hashmap和set,不会存在误判情况
  • 对于bit array,BloomFilter在插入和查找元素是否存在时,需要做多次hash,而bit array只需要做一次hash,实际上,bit array可以看做是BloomFilter的一种特殊情况


1.5 使用场景


布隆过滤器的巨大用处就是,能够迅速判断一个元素是否在一个集合中。因此他有如下几种使用场景:

  1. 网页爬虫对 URL 去重,避免爬取相同的 URL 地址;
  2. 反垃圾邮件,从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱;
  3. Google Chrome 使用布隆过滤器识别恶意 URL;
  4. Medium 使用布隆过滤器避免推荐给用户已经读过的文章;
  5. Google BigTable,Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。
  6. 缓存穿透,将所有可能存在的数据缓存放到布隆过滤器中,当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。


1.6 项目中使用


关于布隆过滤器,我们不需要自己实现,谷歌已经帮我们实现好了。

pom引入guava 的布隆过滤器依赖

<!-- https://mvnrepository.com/artifact/com.google.guava/guava -->
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>27.0.1-jre</version>
</dependency>


1、布隆过滤器的默认容错率是0.03

public static void main(String[] args) {
        int size=10000;
        double fpp=0.0001;
        //没有设置误判率的情况下,10000→312,误判率3.12%
        BloomFilter<CharSequence> bloomFilter =
                BloomFilter.create(Funnels.stringFunnel(
                        Charset.forName("utf-8")),10000);
        for (int m=0;m<size;m++){
            bloomFilter.put(""+m);
        }
        List<Integer> list=new ArrayList<Integer>();
        for(int n=size+10000;n<size+20000;n++){
            if(bloomFilter.mightContain(""+n)){
                list.add(n);
            }
        }
        System.out.println("误判数量:::"+list.size());
    }
//源码::在调用没有设置容错率的创建实例方法时,默认0.03的容错率
 public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
        return create(funnel, expectedInsertions, 0.03D);
    }

2、测试容错率的变化,所需数组位数的变化

容错率0.0001,所需位数191701

public static void main(String[] args) {
    // 1.创建符合条件的布隆过滤器
    // 预期数据量10000,错误率0.0001
    BloomFilter<CharSequence> bloomFilter =
            BloomFilter.create(Funnels.stringFunnel(
                    Charset.forName("utf-8")),10000, 0.0001);
    // 2.将一部分数据添加进去
    for (int i = 0; i < 5000; i++) {
        bloomFilter.put("" + i);
    }
    System.out.println("数据写入完毕");
    // 3.测试结果输出
    for (int i = 0; i < 10000; i++) {
        if (bloomFilter.mightContain("" + i)) {
            System.out.println(i + "存在");
        } else {
            System.out.println(i + "不存在");
        }
    }
}
 //根据插入的数量和误判率来得出位向量应有的长度
long numBits = optimalNumOfBits(expectedInsertions, fpp);
//根据插入的数量和位向量的长度来得出应该用多少个Hash函数
int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
容错率0.01,所需位数95850


容错率0.01,所需位数95850


由此可见,误判率越低,则底层维护的数组越长,占用空间越大。因此,误判率实际取值,根据服务器所能够承受的负载来决定,不是拍脑袋瞎想的。



公众号,感谢关注

网络异常,图片无法展示
|

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
目录
打赏
0
0
0
0
76
分享
相关文章
解决Redis缓存数据类型丢失问题
解决Redis缓存数据类型丢失问题
180 85
云端问道21期方案教学-应对高并发,利用云数据库 Tair(兼容 Redis®*)缓存实现极速响应
云端问道21期方案教学-应对高并发,利用云数据库 Tair(兼容 Redis®*)缓存实现极速响应
云端问道21期实操教学-应对高并发,利用云数据库 Tair(兼容 Redis®)缓存实现极速响应
本文介绍了如何通过云端问道21期实操教学,利用云数据库 Tair(兼容 Redis®)缓存实现高并发场景下的极速响应。主要内容分为四部分:方案概览、部署准备、一键部署和完成及清理。方案概览中,展示了如何使用 Redis 提升业务性能,降低响应时间;部署准备介绍了账号注册与充值步骤;一键部署详细讲解了创建 ECS、RDS 和 Redis 实例的过程;最后,通过对比测试验证了 Redis 缓存的有效性,并指导用户清理资源以避免额外费用。
Redis经典问题:缓存穿透
本文详细探讨了分布式系统和缓存应用中的经典问题——缓存穿透。缓存穿透是指用户请求的数据在缓存和数据库中都不存在,导致大量请求直接落到数据库上,可能引发数据库崩溃或性能下降。文章介绍了几种有效的解决方案,包括接口层增加校验、缓存空值、使用布隆过滤器、优化数据库查询以及加强监控报警机制。通过这些方法,可以有效缓解缓存穿透对系统的影响,提升系统的稳定性和性能。
缓存穿透、缓存击穿和缓存雪崩及其解决方案
在现代应用中,缓存是提升性能的关键技术之一。然而,缓存系统也可能遇到一系列问题,如缓存穿透、缓存击穿和缓存雪崩。这些问题可能导致数据库压力过大,甚至系统崩溃。本文将探讨这些问题及其解决方案。
|
2月前
|
Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出
本文深入探讨了Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出。文章还介绍了Redis在页面缓存、数据缓存和会话缓存等应用场景中的使用,并强调了缓存数据一致性、过期时间设置、容量控制和安全问题的重要性。
60 5
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
本文介绍了多线程环境下的几个关键概念,包括时间片、超线程、上下文切换及其影响因素,以及线程调度的两种方式——抢占式调度和协同式调度。文章还讨论了减少上下文切换次数以提高多线程程序效率的方法,如无锁并发编程、使用CAS算法等,并提出了合理的线程数量配置策略,以平衡CPU利用率和线程切换开销。
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等