布隆过滤器原理

布隆过滤器 Bloom Filter 是一种用很小内存判断“一个元素是否可能存在”的数据结构。它最常用在缓存穿透治理里：用户请求一个根本不存在的 ID，如果每次都穿过 Redis 打到数据库，数据库就会被无效请求拖垮；布隆过滤器可以在访问缓存和数据库之前先拦掉“一定不存在”的请求。

一句话理解：

布隆过滤器不保存完整数据，只保存多个哈希位置的位标记。它能判断“一定不存在”或“可能存在”，不能判断“一定存在”。

学习目标

目标	需要掌握什么
知道是什么	位数组、多个哈希函数、添加、查询
知道为什么	为什么能省内存，为什么会误判，为什么不会漏判
知道怎么用	缓存穿透、ID 合法性预判、恶意请求拦截
知道边界	不能直接删除、误判率会升高、初始化和增量同步要可靠
会写 Demo	Guava 本地版、Redis Bitmap 教学版、RedisBloom 命令版
会做项目设计	资产 ID、机构 ID、商品 ID、订单号等商业场景如何落地

解决什么问题

缓存穿透的典型链路是这样的：

mermaid

flowchart TD
    A["请求不存在的 ID"] --> B["Redis 未命中"]
    B --> C["查询 MySQL"]
    C --> D["MySQL 也不存在"]
    D --> E["下次相同或随机 ID 继续打 MySQL"]

如果攻击者不断构造随机 ID，例如 assetId=999999999、assetId=-1、assetId=abc，Redis 本来就没有这些数据，数据库也没有这些数据。空值缓存只能挡住“重复查询同一个无效 ID”，挡不住“每次都换一个无效 ID”。

布隆过滤器的作用是先判断这个 ID 有没有可能存在：

mermaid

flowchart TD
    A["请求 ID"] --> B["参数校验"]
    B --> C["布隆过滤器判断"]
    C --> D{"一定不存在吗"}
    D -- "是" --> E["直接返回空或拒绝"]
    D -- "否" --> F["查询 Redis"]
    F --> G{"缓存命中"}
    G -- "是" --> H["返回缓存"]
    G -- "否" --> I["查询数据库并重建缓存"]

这里要注意：布隆过滤器通常判断的是“数据库里是否可能存在这个业务 ID”，不是判断“Redis 里是否已经有缓存”。Redis 缓存可能因为过期而没有，但数据库可能仍然有数据。

核心结构

布隆过滤器由两部分组成：

一个长度为 m 的位数组，初始每一位都是 0。
k 个哈希函数，每个函数都能把元素映射到位数组上的一个位置。

mermaid

flowchart TD
    A["元素 asset:1001"] --> B["hash1"]
    A --> C["hash2"]
    A --> D["hash3"]
    B --> E["位置 2 置为 1"]
    C --> F["位置 8 置为 1"]
    D --> G["位置 13 置为 1"]

位数组可以想象成一排开关：

text

下标:  0 1 2 3 4 5 6 7 8 9 10 11 12 13
位值:  0 0 1 0 0 0 0 0 1 0  0  0  0  1

添加 asset:1001 时，多个哈希函数算出几个位置，把这些位置都设置为 1。

添加元素流程

添加一个元素时：

用 k 个哈希函数分别计算位置。
把这些位置都设置为 1。
不保存元素本身。

mermaid

flowchart TD
    A["添加 asset:1001"] --> B["计算多个哈希位置"]
    B --> C["位置 2"]
    B --> D["位置 8"]
    B --> E["位置 13"]
    C --> F["bit[2] = 1"]
    D --> G["bit[8] = 1"]
    E --> H["bit[13] = 1"]

伪代码：

text

add(value):
  for each hashFunction:
    index = hashFunction(value) % bitArrayLength
    bitArray[index] = 1

为什么省内存：它只保存若干个 bit，不保存完整字符串、对象、ID 集合。几百万个 ID 可能只需要几 MB 以内的位图空间。

查询元素流程

查询一个元素时：

用同样的 k 个哈希函数计算位置。
如果任意一个位置是 0，说明这个元素一定没有添加过。
如果所有位置都是 1，说明这个元素可能添加过。

mermaid

flowchart TD
    A["查询 asset:9999"] --> B["计算多个哈希位置"]
    B --> C{"是否存在任意 bit 为 0"}
    C -- "是" --> D["一定不存在"]
    C -- "否" --> E["可能存在"]

伪代码：

text

mightContain(value):
  for each hashFunction:
    index = hashFunction(value) % bitArrayLength
    if bitArray[index] == 0:
      return false
  return true

“一定不存在”为什么可靠：如果这个元素曾经被添加过，那么它对应的所有位置一定都被置为 1。现在只要发现其中一个位置还是 0，就说明它不可能被添加过。

“可能存在”为什么不可靠：这些位置可能不是当前元素置为 1 的，而是其他元素碰巧把这些位置都置为了 1。

为什么会误判

误判 False Positive 指：元素实际不存在，但布隆过滤器判断为“可能存在”。

原因是哈希碰撞和位复用。

mermaid

flowchart TD
    A["元素 A"] --> B["设置 bit 2"]
    A --> C["设置 bit 8"]
    D["元素 B"] --> E["设置 bit 13"]
    F["查询不存在的元素 X"] --> G["刚好检查 bit 2 8 13"]
    G --> H["全是 1"]
    H --> I["误判为可能存在"]

误判的后果：

无效请求可能继续查 Redis 或数据库。
但误判率可控，通常可以设置为 1%、0.1% 甚至更低。
误判不会导致真实存在的数据被拒绝。

所以布隆过滤器适合做“前置拦截”，不适合做“强正确判断”。它可以降低数据库压力，但不能替代数据库查询。

为什么不会漏判

漏判 False Negative 指：元素实际存在，但布隆过滤器判断为“一定不存在”。

标准布隆过滤器在两个前提下不会漏判：

添加流程可靠，存在的数据已经写入过滤器。
不执行直接删除，位数组没有被错误清零。

原因很简单：一个元素添加时会把它的所有哈希位置置为 1。查询时只检查这些位置是否为 1。如果它确实添加过，并且这些 bit 没有被清掉，就不会出现某个位置为 0。

mermaid

flowchart TD
    A["添加 asset:1001"] --> B["bit 2 8 13 都置为 1"]
    C["查询 asset:1001"] --> D["再次检查 bit 2 8 13"]
    D --> E["全部为 1"]
    E --> F["判断可能存在"]

注意这里说的是“可能存在”，不是“一定存在”。布隆过滤器永远不能单独证明一个元素一定存在。

为什么不能直接删除

普通布隆过滤器不能直接删除元素，因为多个元素可能共享同一个 bit。如果删除某个元素时把这些 bit 置为 0，可能影响其他元素。

mermaid

flowchart TD
    A["元素 A 使用 bit 2"] --> C["bit 2 = 1"]
    B["元素 B 也使用 bit 2"] --> C
    D["删除元素 A"] --> E["如果把 bit 2 清零"]
    E --> F["元素 B 可能被误判为不存在"]

这就是为什么布隆过滤器适合“只增不删”或“删除不敏感”的数据集合。

如果业务确实需要删除，可以考虑：

方案	思路	代价
定期重建	从数据库全量重新构建过滤器	有重建成本和切换成本
Counting Bloom Filter	每个位置存计数，不是单个 bit	内存更大，复杂度更高
Cuckoo Filter	支持删除，误判率可控	实现和理解成本更高
加白名单或黑名单补偿	对少量删除或特殊数据额外判断	需要额外存储和逻辑

参数怎么估算

布隆过滤器有三个关键参数：

参数	含义
`n`	预计放入多少个元素
`p`	期望误判率
`m`	位数组长度
`k`	哈希函数数量

常用估算公式：

text

m = -n * ln(p) / (ln(2) * ln(2))
k = (m / n) * ln(2)

例子：预计放入 100 万个资产 ID，允许 1% 误判率。

text

n = 1,000,000
p = 0.01
m ≈ 9,585,058 bits ≈ 1.14 MB
k ≈ 7

这说明布隆过滤器非常省内存。用 HashSet 保存 100 万个字符串 ID，内存可能远大于几 MB；布隆过滤器只需要一个位数组和哈希计算。

误判率不是越低越好：

误判率	影响
过高	无效请求放过去太多，数据库保护效果差
过低	位数组更大，哈希次数更多，内存和 CPU 成本上升

商业项目通常根据数据库承受能力、请求量和数据规模来定。比如 1% 或 0.1% 是常见起点，最终要压测。

在缓存穿透中的位置

布隆过滤器应该放在 Redis 缓存查询之前还是之后？常见做法是放在缓存查询之前。

mermaid

flowchart TD
    A["请求 assetId"] --> B["参数格式校验"]
    B --> C["布隆过滤器"]
    C --> D{"可能存在吗"}
    D -- "否" --> E["直接返回空"]
    D -- "是" --> F["查 Redis 缓存"]
    F --> G{"命中"}
    G -- "是" --> H["返回"]
    G -- "否" --> I["查 MySQL"]
    I --> J["写缓存或缓存空值"]

为什么先查布隆过滤器：

随机无效 ID 会被直接拦截，连 Redis 都少查一次。
可以减少 Redis 和 MySQL 的无效压力。
对“海量随机穿透”比空值缓存更有效。

但有些系统也会先查本地缓存或热点缓存，这取决于链路成本。关键原则是：无效请求越早拦截越好。

商业场景

场景	如何使用
商品详情	把有效商品 ID 加入布隆过滤器，随机商品 ID 直接拒绝
资产平台	把有效资产 ID、表 ID、字段 ID 加入过滤器
医疗机构字典	把有效机构 ID、科室 ID 加入过滤器
订单查询	可对订单号格式先校验，再对历史订单号过滤
用户查询	对用户 ID 做存在性预判，避免随机 UID 打库

以医疗数据采集与资产平台为例：

平台启动或定时任务从 MySQL 加载有效 asset_id。
把这些 ID 写入布隆过滤器。
查询资产详情时先判断 asset_id 是否可能存在。
如果一定不存在，直接返回空，不查 Redis 和 MySQL。
如果可能存在，再走 Redis Cache Aside。
新增资产成功后，同步把新 ID 加入布隆过滤器。

Guava 本地 Demo

Guava 提供了本地内存版 BloomFilter，适合单体服务、轻量场景或教学理解。多实例部署时，每个实例都有一份，需要解决初始化和更新同步。

Maven 依赖：

xml

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>32.1.3-jre</version>
</dependency>

初始化：

java

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

import java.nio.charset.Charset;
import java.util.List;

public class AssetBloomFilter {

    private final BloomFilter<CharSequence> bloomFilter;

    public AssetBloomFilter(List<String> assetIds) {
        this.bloomFilter = BloomFilter.create(
                Funnels.stringFunnel(Charset.forName("UTF-8")),
                1000000,
                0.01
        );

        for (String assetId : assetIds) {
            bloomFilter.put(assetId);
        }
    }

    public boolean mightExist(String assetId) {
        return bloomFilter.mightContain(assetId);
    }

    public void addAsset(String assetId) {
        bloomFilter.put(assetId);
    }
}

业务查询：

java

public AssetDTO getAsset(String assetId) {
    if (!assetBloomFilter.mightExist(assetId)) {
        return null;
    }

    AssetDTO cached = redisCache.get("asset:detail:" + assetId);
    if (cached != null) {
        return cached;
    }

    AssetDTO asset = assetRepository.findById(assetId);
    if (asset == null) {
        redisCache.set("asset:detail:" + assetId, AssetDTO.empty(), 120);
        return null;
    }

    redisCache.set("asset:detail:" + assetId, asset, 1800);
    return asset;
}

这个 Demo 里，即使布隆过滤器误判“可能存在”，后面 MySQL 仍然会做最终判断，所以不会返回错误数据。

Redis Bitmap 教学 Demo

如果不用 RedisBloom 模块，也可以用 Redis 的 Bitmap 思路做一个教学版。真实生产建议优先用成熟库或 RedisBloom，因为哈希、参数、扩容、误判率统计都更完整。

下面是简化版思路：

java

import org.springframework.data.redis.core.StringRedisTemplate;

import java.nio.charset.Charset;
import java.util.zip.CRC32;

public class RedisBitmapBloomFilter {

    private static final String KEY = "bf:asset";
    private static final long BIT_SIZE = 10000000L;

    private final StringRedisTemplate redisTemplate;

    public RedisBitmapBloomFilter(StringRedisTemplate redisTemplate) {
        this.redisTemplate = redisTemplate;
    }

    public void add(String value) {
        long[] indexes = indexes(value);
        for (int i = 0; i < indexes.length; i++) {
            redisTemplate.opsForValue().setBit(KEY, indexes[i], true);
        }
    }

    public boolean mightContain(String value) {
        long[] indexes = indexes(value);
        for (int i = 0; i < indexes.length; i++) {
            Boolean bit = redisTemplate.opsForValue().getBit(KEY, indexes[i]);
            if (!Boolean.TRUE.equals(bit)) {
                return false;
            }
        }
        return true;
    }

    private long[] indexes(String value) {
        long h1 = hash(value, "seed1");
        long h2 = hash(value, "seed2");
        long h3 = hash(value, "seed3");
        return new long[] {
                Math.abs(h1 % BIT_SIZE),
                Math.abs(h2 % BIT_SIZE),
                Math.abs(h3 % BIT_SIZE)
        };
    }

    private long hash(String value, String seed) {
        CRC32 crc32 = new CRC32();
        crc32.update((seed + value).getBytes(Charset.forName("UTF-8")));
        return crc32.getValue();
    }
}

这个教学版能帮助理解原理，但有几个问题：

哈希函数不够专业，误判率不可控。
没有自动容量规划。
没有扩容和统计能力。
每次检查多个 bit 可能产生多次 Redis 请求，生产要用 Pipeline 或 Lua 优化。

RedisBloom 命令 Demo

RedisBloom 是 Redis 的布隆过滤器模块，生产中更接近真实使用方式。

创建过滤器：

bash

BF.RESERVE bf:asset 0.01 1000000

含义：

参数	说明
`bf:asset`	过滤器 key
`0.01`	期望误判率 1%
`1000000`	预计元素数量 100 万

添加元素：

bash

BF.ADD bf:asset asset:1001
BF.MADD bf:asset asset:1002 asset:1003 asset:1004

判断是否可能存在：

bash

BF.EXISTS bf:asset asset:1001
BF.MEXISTS bf:asset asset:1001 asset:9999

结果为 0 表示一定不存在，结果为 1 表示可能存在。

注意：RedisBloom 不是 Redis 默认内置命令，需要部署 Redis Stack 或加载 RedisBloom 模块。普通 Redis 直接执行 BF.ADD 会报未知命令。

初始化和同步流程

布隆过滤器最容易被忽略的是数据生命周期。不是写完查询逻辑就完事，必须保证过滤器里的数据和数据库里的有效 ID 集合基本一致。

推荐流程：

mermaid

flowchart TD
    A["系统启动或定时任务"] --> B["从 MySQL 分批加载有效 ID"]
    B --> C["构建新布隆过滤器"]
    C --> D["校验数量和误判率"]
    D --> E["切换线上过滤器"]
    F["新增业务数据"] --> G["写 MySQL 成功"]
    G --> H["增量加入布隆过滤器"]

为什么要先写 MySQL 再加过滤器：数据库是事实来源。只有业务数据创建成功后，才应该把 ID 加入过滤器。否则过滤器可能长期认为一个不存在的数据“可能存在”，降低拦截效果。

对于删除数据：

普通布隆过滤器不直接删除。
如果删除量少，可以接受短时间误判。
如果删除量大，要定期全量重建。
如果强依赖删除，可以换 Counting Bloom Filter 或 Cuckoo Filter。

常见坑

坑	后果	正确做法
把“可能存在”当成“一定存在”	返回错误数据	后面必须继续查缓存或数据库
初始化漏数据	真实数据被判断为不存在	启动全量加载要可靠，有校验
新增数据不更新过滤器	新数据短时间查不到	创建成功后增量加入
删除时直接清 bit	影响其他元素，造成漏判	普通过滤器不直接删除
预估容量太小	bit 被打满，误判率升高	按峰值容量预估，必要时重建
误判率设置过低	内存和 CPU 成本上升	按业务风险和压测结果选择
只用布隆过滤器防穿透	参数攻击仍可能打进来	还要参数校验、限流、空值缓存

排查方法

如果线上怀疑布隆过滤器效果不好，可以按这个流程排查：

mermaid

flowchart TD
    A["数据库仍被无效请求打高"] --> B["看参数校验"]
    B --> C{"是否明显非法 ID"}
    C -- "是" --> D["先在网关或应用拦截"]
    C -- "否" --> E["看布隆过滤器命中统计"]
    E --> F{"不存在请求是否被放过很多"}
    F -- "是" --> G["检查容量和误判率"]
    F -- "否" --> H["检查缓存击穿或雪崩"]
    G --> I["重建过滤器或降低误判率"]

关键指标：

指标	说明
请求总量	看是否有恶意随机 ID
过滤器拦截量	判断过滤器是否真的挡住无效请求
过滤器放行量	进入 Redis 和 MySQL 的请求量
MySQL 空结果量	如果很高，说明误判或漏拦截较多
新增数据同步延迟	判断新数据是否及时加入过滤器
重建耗时	判断全量构建是否影响上线

和其他方案对比

方案	解决什么	优点	缺点
参数校验	非法格式、非法范围	成本低，应该优先做	只能挡明显非法
缓存空值	重复查询同一个不存在 ID	简单有效	随机 ID 会产生大量空值
布隆过滤器	海量随机不存在 ID	内存小，拦截早	有误判，删除困难
限流	恶意流量或突发流量	保护系统	会牺牲部分请求
黑名单	明确攻击来源	精准	覆盖有限，需要维护

成熟方案通常组合使用：

mermaid

flowchart TD
    A["请求"] --> B["参数校验"]
    B --> C["限流"]
    C --> D["布隆过滤器"]
    D --> E["Redis 缓存"]
    E --> F["MySQL"]
    F --> G["空值缓存和监控"]

关联知识点

知识点	继续学习什么
Redis 缓存问题	穿透、击穿、雪崩整体对比
Redis 高并发缓存治理	大 Key、热 Key、慢命令、连接池、限流降级
缓存一致性	缓存和数据库的最终一致策略
Redis 面试知识点	布隆过滤器面试回答和追问

本章小结

布隆过滤器的本质是“位数组 + 多个哈希函数”。添加时把多个位置置为 1，查询时只要有一个位置为 0，就能判断一定不存在；如果所有位置都是 1，只能判断可能存在。它的价值是用很小内存拦截大量无效请求，保护 Redis 和数据库；它的边界是会误判、不能直接删除、需要可靠初始化和增量同步。商业项目里不要单独依赖布隆过滤器，要和参数校验、空值缓存、限流、监控、重建机制一起使用。

JDK 8/11/17/21 LTS演进

线程池

布隆过滤器原理 ​

学习目标 ​

解决什么问题 ​

核心结构 ​

添加元素流程 ​

查询元素流程 ​

为什么会误判 ​

为什么不会漏判 ​

为什么不能直接删除 ​

参数怎么估算 ​

在缓存穿透中的位置 ​

商业场景 ​

Guava 本地 Demo ​

Redis Bitmap 教学 Demo ​

RedisBloom 命令 Demo ​

初始化和同步流程 ​

常见坑 ​

排查方法 ​

和其他方案对比 ​

关联知识点 ​

本章小结 ​

布隆过滤器原理

学习目标

解决什么问题

核心结构

添加元素流程

查询元素流程

为什么会误判

为什么不会漏判

为什么不能直接删除

参数怎么估算

在缓存穿透中的位置

商业场景

Guava 本地 Demo

Redis Bitmap 教学 Demo

RedisBloom 命令 Demo

初始化和同步流程

常见坑

排查方法

和其他方案对比

关联知识点

本章小结