30｜布隆过滤器：如何解决Redis缓存穿透问题？
黄清昊
该思维导图由 AI 生成，仅供参考
你好，我是微扰君。
上一讲我们学习了如何基于 bitmap，使用少量内存，对大量密集数据高效地去重和排序，本质就是通过一个长长的二进制 01 序列，来维护每个元素是否出现过这样的二值状态，这个数据结构非常重要，日常工作中有很多应用，比如我们今天要学习的布隆过滤器，就建立在相似的数据结构之上。
那什么是布隆过滤器，用来解决什么样的问题呢？我们先从缓存说起。
缓存穿透
还记得之前介绍 LRU 的时候，我们提过的缓存思想吗，用一些访问成本更低的存储，来存一些更加高频的访问数据，提高系统整体的访问速度。比如在业务开发中，我们经常会用 Redis 来缓存数据。
这就是因为 Redis 主要把数据存储在内存中，访问速度比数据库快得多，引入缓存层之后，能大大减少数据访问的延时，也能降低数据库系统本身的压力。
我们的用法通常是这样：每次请求某个数据的时候，假设都是基于某个 key 去访问数据库，比如用户 ID 之类的字段，我们会先试图访问 Redis，查看是否有 key 相关的缓存记录，有的话就可以直接返回了；如果没有，再去数据库里查询，查到结果后会把数据缓存在 Redis 中；如果数据库中也没有，返回没有相关记录，这样 Redis 中自然也不会有缓存数据。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
布隆过滤器是一种用于解决缓存穿透问题的数据结构，通过维护一个位图来快速判断某个key是否存在于某个集合中。它基于多重Hash算法实现，能够以较小的空间付出小概率的“误差”成本，从而解决缓存穿透问题。虽然存在一定的误判风险和记录删除困难的问题，但在选取合适的Bitmap数组大小和Hash计算次数之后，可以将误判率控制在低于5%的水平，为系统性能提升带来显著效果。布隆过滤器在实现上相对简单，Guava库提供了高质量的实现代码，适合Java爱好者进行源码学习。此外，文章还提出了一个思考题，探讨如何更好地清理过期数据，为读者提供了进一步思考的空间。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《业务开发算法 50 讲》，新⼈⾸单¥59
《业务开发算法 50 讲》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(6)
- 最新
- 精选
webmin“我们提到了布隆过滤器清除状态比较困难，但有些缓存数据是有生命周期的，比如一周或者一个月之后就大概率过期了，你有没有什么好办法可以帮助我们更好地清理过期数据呢？” 每过一定的周期就建立一个新的布隆过滤器B，和原有的布隆过滤器A保持双写，再过一段时间后，A与B的指代交换，然后删除A。作者回复: 哈哈哈 标准答案～
2022-03-0539
那时刻为了应对缓存数据过期，可以采用定期重建bloom filter的方法，比如数据一周过期，bloom filter可以在一周多之后重建，去掉过期数据信息。作者回复: 没错，就是这样做的～
2022-03-032
peter请教老师两个问题： Q1：布隆过滤器需要提前“预热”吗？ 布隆过滤器使用之前，需要先把各个位都设置值吗？ 还是在使用过程中进行设置？ Q2：处理流程上是先经过布隆过滤器吗？ 请求到来之后，原来是先到redis；现在是需要 先到布隆过滤器吗？作者回复: Q1 我理解直接在使用过程中采用布隆过滤器即可 Q2 我们是可以采用布隆过滤器解决redis缓存穿透问题的；事实上某些云厂商提供的redis公有云版本就带有增强的布隆过滤器的能力。
2022-03-032- Paul Shan要删除已经存储在布隆过滤器的内容依据过滤器本身的信息是不够的，一个可能的方案是存储额外累加次数到数据库，类似于{index,number}, index 是对应位的下标，number是额外的累加次数。当布隆过滤器的一位已经是1的时候再次被设置为1的时候，做{index,++number}操作。当删除一个id的时候，首先做{index,--number}操作，如果对应的number已经是0的情况下，就把布隆过滤器相应的位设置成0.
作者回复: 是的 也是一种解决的方案 不过个人认为代价比较高 可以采用定期重建替换布隆过滤器的方式
2022-03-031 
雨落～紫竹这种恶意访问的小可爱 直接从源头 把它ip 用户身份 通过(单位时间内请求次数 返回相同失败) 识别出来 拉黑 限流 过一段时间或者联系客服再把他放出来 现在你这种方案其实可以归位保底2022-07-181
加油加油100w 的数据量，如果希望通过 5 次 Hash 得到 5% 以内的误判率，我们大概需要 700 万位 Bitmap，内存只需要不到 1M 即可完成 -- 这个结论中说需要700万位，那是不是对应的哈希函数结果位数也要能达到这个级别？2022-07-19
收起评论
