BloomFilter(布隆过滤器)学习笔记

看到一个集合查找的面试题,想起这个算法。

前言

一个面试题

现在有一个非常庞大的数据,假设全是 int 类型。现在我给你一个数,你需要告诉我它是否存在其中(尽量高效)。

如果int是32位或以下,这个题目只需要使用BitMap即可。

分析

  1. 我们可以将数据存放到BitMap中,共需要空间(2^64)=0.5G,目前的计算机可以存放。
  2. 计算效率是O(1)可满足性能。

以上办法可以解决32位int的场景。但别高兴得太早,此时,面试官会加大难度,如果int是64位,或元素是不是int,是字符串,怎么办呢?
此时,面试官想要得到的答案,就是BloomFilter

算法

BloomFilter使用BitMap保存Hash计算出的校验和。为了降低冲突概率,使用不同Hash算法进行多次Hash。
在实际生产中,通常还是会用同一个Hash算法,但会对数据进行不同的处理,比如末尾添加些字符等。

特点

优点

算法简单

整个算法只需要使用多次Hash算法,单机即可完成。

使用空间小

由于使用BitMap,相比树状存储或HashMap等需要存储数据本身的算法而言。空间效率远优于一般算法。

由于BloomFilter计算简单,所需存储空间小,单机就能完成计算,可以很方便的扩展,是个非常精干的算法。但由于并未保存数据本身,因此也存在一些缺陷。

缺点

存在误判

BloomFilter存在假阳性,但不存在假阴性。不过误判概率极小。
如果BloomFilter判断元素不存在,则元素一定不存在,如果判断元素存在,则大概率存在。

不能删除元素

BloomFilter不允许删除元素,只允许添加。
由于BloomFilter不保存数据本身,所以
此外,由于存在假阳性的可能,因此即便在数组中使用计数的方式,也是存在问题。

使用场景

防止缓存被击穿

现在的系统,可以说在每个环节都会存在缓存。无论是加速静态数据的CDN,应用缓存tair,memcache,还是数据库内部,都存在缓存的设计。
如果是正常的查询,缓存通常有很高的命中率,即便存在一些未命中的情况,缓存也会更新,使得下次请求命中。但如果请求的数据本身就是不存在的呢

可以预料到:
  1. 缓存会被全部击穿。
  2. 最终数据库中也查询不到。
  3. 缓存并不会更新。
    这种情况下。可以使用BloomFilter来过滤掉不存在的元素。因为BloomFilter中不存在的元素,数据库里一定不存在

另一个面试题

系统遇到大量的请求,这些请求一定会击穿缓存,应该怎么办?
答案就是BloomFilter。

用于黑名单

同样,由于所需存储空间小,也很适用于黑名单。用于过滤危险网址垃圾邮件等。
因为存在误判,所以还需要一个白名单。

问题

为什么LevelDB中使用BloomFilter但MySQL没有?

  1. MySQL的Innodb的数据本地更新的,BloomFilter并不支持删除。
  2. 通常MySQL的数据量不会非常巨大。
  3. LevelDB中,已经生成的SSTable数据是不会删除的,BloomFilter正好满足。
  4. LevelDB的数据结构就和缓存金字塔一样,如果数据不存在,或在较底层,就需要一层层往下查找,要没有用BloomFilter跳不存在数据的层,就要每一层进去找,查询的成本会被放大的很厉害。
  5. 在B+tree中查找不存在的数据,查询成本不会像LevelDB那样放大

总结

  1. BloomFilter存在极低概率的假阳性,但不存在假阴性。
  2. 用于保护缓存击穿,或存放过滤网址,黑名单等,BloomFilter通常是一个不错的选择,也可能是目前唯一的选择。
© 版权声明
THE END
广告
喜欢就支持一下吧
点赞0 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情

    暂无评论内容