2. 缓存穿透与布隆过滤器

2.1 缓存穿透原理

缓存穿透是指查询一个根本不存在的数据时，缓存层和持久层（数据库）都无法命中。由于缓存层不命中，请求会直接穿透到数据库，当并发量较大时，数据库会承受巨大压力，甚至导致宕机。

缓存穿透的典型场景

• 恶意攻击：攻击者构造大量不存在的 Key（如负数 ID、超长字符串）发起请求。
• 业务误操作：前端或上游服务传入非法参数，导致查询数据库返回空。
• 数据未同步：数据库已删除数据，但缓存未及时清理，后续请求穿透。

缓存穿透的危害

常见解决方案对比

2.2 布隆过滤器实现

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于判断一个元素是否在集合中。它由一个位数组和多个哈希函数组成。

核心数据结构

• 位数组（Bit Array）：长度为 m 的二进制数组，初始所有位为 0。
• 哈希函数集合：k 个相互独立的哈希函数，每个函数将输入元素映射到位数组的一个位置。

基本操作流程

1. 添加元素：对元素使用 k 个哈希函数，得到 k 个位索引，将位数组中这些位置置为 1。
2. 查询元素：对元素使用相同的 k 个哈希函数，检查所有对应位是否都为 1。如果任意一位为 0，则元素一定不存在；如果全部为 1，则元素可能存在。

Java 实现示例（Guava 布隆过滤器）

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.Charset;

public class BloomFilterDemo {
    public static void main(String[] args) {
        // 预期插入数量：100000，期望误判率：1%
        BloomFilter<String> bloomFilter = BloomFilter.create(
            Funnels.stringFunnel(Charset.defaultCharset()),
            100_000,
            0.01
        );

        // 添加元素
        bloomFilter.put("user_1001");
        bloomFilter.put("user_1002");
        bloomFilter.put("order_2024001");

        // 查询元素
        System.out.println(bloomFilter.mightContain("user_1001"));   // true
        System.out.println(bloomFilter.mightContain("user_9999"));   // false（大概率）
        System.out.println(bloomFilter.mightContain("order_9999"));  // false（大概率）
    }
}

2.3 布隆过滤器误判率与容量设计

布隆过滤器的性能由三个核心参数决定：位数组长度 m、哈希函数个数 k、预期元素数量 n。误判率 p 与这些参数之间存在严格的数学关系。

核心公式

• 误判率 p：p ≈ (1 - e^-kn/m)^k
• 最优哈希函数个数 k：k = (m/n) × ln2 ≈ 0.693 × (m/n)
• 位数组长度 m：m = - (n × ln p) / (ln2)²

参数设计对照表

容量设计步骤

1. 确定 n：统计业务中最大可能的 Key 数量（如用户数、订单数）。
2. 确定 p：根据业务容忍度设定误判率（通常 0.1%~1%）。
3. 计算 m：使用公式 m = - (n × ln p) / (ln2)² 计算位数组长度。
4. 计算 k：使用公式 k = (m/n) × ln2 计算最优哈希函数个数。
5. 验证内存：确认 m 位对应的内存大小是否在可接受范围内。

误判率与容量关系图

布隆过滤器在缓存穿透中的部署架构