← 返回学习路线

SYSTEM

布隆过滤器

面试八股
src/content/notes/growth/redis.md

布隆过滤器

解决什么业务问题(后端高频场景,Redis 配套考点)

主要有:缓存三防、Redisson 锁、看门狗、哨兵、主从、RDB/AOF、过期删除、内存淘汰

1. 解决缓存穿透(最核心面试场景)

缓存穿透: 查询数据库不存在的数据(如非法 id=-1、不存在商品 id),请求绕过 Redis 直接打满 MySQL,压垮数据库。 布隆过滤器方案:

  • 启动时把数据库所有有效商品 id 存入布隆过滤器
  • 接口查询流程:先过布隆过滤器
    • mightContains=false → 直接返回空,不查 Redis、不查 DB
    • mightContains=true → 再查询 Redis,缓存无数据再查数据库 效果:拦截大量不存在的非法查询,保护数据库。

2. 海量数据去重

比如爬虫 URL 去重、邮件黑名单、百万级黑名单过滤:

  • 亿级 URL 全部存入 HashMap 会占用几十 GB 内存;
  • 布隆过滤器仅需几百 MB,快速判断 URL 是否已经爬取过。

3. 分布式系统黑名单过滤

敏感词、违规账号、垃圾设备 ID 拦截,海量数据下低内存快速校验。

4. 数据库批量查询前置过滤

海量 ID 批量查询前,先用布隆过滤器过滤不存在的 ID,减少无效 SQL 查询。

配套衍生问题(面试追问)

  1. 如何降低误判率? 增大 bit 数组长度、增加哈希函数个数;但哈希函数越多,插入和查询性能越差,需要平衡。
  2. 为什么不能删除普通布隆过滤器? bit 位共享,置 0 会误伤其他元素;如果需要删除,使用计数布隆过滤器(每一组 bit 改为计数器,记录占用次数,计数归 0 再置 0)。
  3. 和 HashMap 对比?
    • HashMap:存储完整 key,精准无误差,内存占用极高;
    • 布隆过滤器:不存原始数据,内存极小,存在假阳性。
  4. Redis 布隆过滤器底层?
    • Redis 基于位数组实现,模块名 redisbloom,支持单实例、分布式布隆过滤器。

一句话总结

底层:bit 二进制数组 + 多个独立哈希函数;

原理:元素映射多个 bit 标记置 1,查询时校验全部标记位;

实现:bit 数组存储标记,多哈希计算下标;

核心解决:缓存穿透、海量数据去重、黑名单过滤,用极小内存换取快速存在性判断。