布隆过滤器

---

1. 什么是布隆过滤器

布隆过滤器（Bloom Filter）是一种基于位图的概率型数据结构，用极小的内存空间实现元素存在性的快速判断。

核心结论：

判断结果为"不存在" ──▶ 该元素一定不存在（100% 准确）
判断结果为"存在"   ──▶ 该元素可能存在（存在误判概率）

特性	说明
空间效率	存储 1 亿个元素仅需约 120 MB（存 Set 需要数 GB）
时间复杂度	添加和查询均为 O(k)，k 为哈希函数数量，极快
误判率	可配置，通常设为 0.01（1%）或更低
不可删除	标准布隆过滤器不支持删除元素
不可枚举	无法遍历已添加的元素

2. 工作原理

2.1. 初始化

布隆过滤器由一个位数组（bit array）和若干哈希函数组成，初始所有位均为 0：

位数组（初始全 0）：
[0][0][0][0][0][0][0][0][0][0][0][0][0][0][0][0]
 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15

2.2. 添加元素

对元素执行 k 次哈希，将结果对应的位置 1：

添加 "Alice"（3 个哈希函数）：
hash1("Alice") % 16 = 2  ──▶ 位 2 置 1
hash2("Alice") % 16 = 7  ──▶ 位 7 置 1
hash3("Alice") % 16 = 13 ──▶ 位 13 置 1

[0][0][1][0][0][0][0][1][0][0][0][0][0][1][0][0]

2.3. 查询元素

对查询元素执行相同的 k 次哈希，检查所有对应位是否都为 1：

查询 "Alice"：
hash1 → 位 2 = 1 ✓
hash2 → 位 7 = 1 ✓
hash3 → 位 13 = 1 ✓
──▶ 全部为 1，判断"可能存在"

查询 "Bob"：
hash1 → 位 3 = 0 ✗
──▶ 有 0，判断"一定不存在"

2.4. 误判原因

不同元素的哈希结果可能碰撞到已置 1 的位，导致从未添加的元素被误判为存在：

"Charlie" 的三个哈希恰好都落在已被置 1 的位上
──▶ 误判为"存在"（实际从未添加过）

误判率与参数的关系

误判率（FPR）由位数组大小和哈希函数数量共同决定：位数组越大、哈希函数数量越合适，误判率越低，但内存占用越大。Redisson 会根据期望误判率自动计算最优参数。

---

3. Redisson 集成布隆过滤器

Redisson 提供了开箱即用的布隆过滤器实现，基于 Redis 位图存储，支持分布式访问。

3.1. 添加依赖

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson-spring-boot-starter</artifactId>
    <version>3.27.0</version>
</dependency>

3.2. 初始化布隆过滤器

@Configuration
public class BloomFilterConfig {

    @Bean
    public RBloomFilter<Long> productBloomFilter(RedissonClient redissonClient) {
        RBloomFilter<Long> bloomFilter = redissonClient.getBloomFilter("bf:product:ids");
        // 参数：期望存储元素数量，期望误判率
        bloomFilter.tryInit(1_000_000L, 0.01);
        return bloomFilter;
    }
}

3.3. 数据预热（启动时加载）

@Component
@RequiredArgsConstructor
public class BloomFilterInitializer implements ApplicationRunner {

    private final RBloomFilter<Long> productBloomFilter;
    private final ProductMapper productMapper;

    @Override
    public void run(ApplicationArguments args) {
        // 应用启动时，将所有合法商品 ID 加入布隆过滤器
        List<Long> allIds = productMapper.selectAllIds();
        allIds.forEach(productBloomFilter::add);
        log.info("布隆过滤器初始化完成，共加载 {} 个商品 ID", allIds.size());
    }
}

---

4. 实战：防缓存穿透

@Service
@RequiredArgsConstructor
public class ProductService {

    private final RBloomFilter<Long> productBloomFilter;
    private final StringRedisTemplate redisTemplate;
    private final ProductMapper productMapper;
    private final ObjectMapper objectMapper;

    public Product getById(Long id) throws JsonProcessingException {
        // ① 布隆过滤器拦截：一定不存在，直接返回
        if (!productBloomFilter.contains(id)) {
            return null;  // 拦截非法请求，DB 完全不受影响
        }

        // ② 查 Redis 缓存
        String key  = "product:" + id;
        String json = redisTemplate.opsForValue().get(key);
        if (json != null) {
            return "NULL".equals(json) ? null
                                       : objectMapper.readValue(json, Product.class);
        }

        // ③ 查 DB（布隆误判时走到这里，概率 ≤ 1%）
        Product product = productMapper.selectById(id);
        String  value   = product == null ? "NULL"
                                          : objectMapper.writeValueAsString(product);
        redisTemplate.opsForValue().set(key, value, 30, TimeUnit.MINUTES);
        return product;
    }

    // 新增商品时同步更新布隆过滤器
    public void create(Product product) {
        productMapper.insert(product);
        productBloomFilter.add(product.getId());
    }
}

完整请求流程：

请求 id=99999（不存在）
      │
      ▼
布隆过滤器.contains(99999) → false
      │
      ▼
直接返回 null ✅（DB 和 Redis 完全未被访问）

请求 id=1001（存在）
      │
      ▼
布隆过滤器.contains(1001) → true（可能存在）
      │
      ▼
查 Redis 缓存 → 命中 → 返回 ✅

请求 id=9999（误判，不存在但布隆认为存在，概率 1%）
      │
      ▼
布隆过滤器.contains(9999) → true（误判）
      │
      ▼
查 Redis → miss → 查 DB → null → 缓存空值
（少量误判请求落到 DB，可接受）

---

5. 布隆过滤器 vs 空值缓存

对比项	空值缓存	布隆过滤器
内存占用	高（每个不存在的 key 都缓存）	极低（位图，固定空间）
实现复杂度	简单	中等（需预热）
防随机 key 攻击	❌ 无效	✅ 有效
误判率	无（精确）	有（可控，通常 ≤ 1%）
新增数据处理	无需额外处理	需同步 add 到过滤器
删除数据处理	删除对应空值缓存	❌ 标准布隆过滤器不支持删除
推荐场景	key 范围固定，量少	key 范围大，防恶意攻击

组合使用

实际生产中两者通常配合使用：布隆过滤器拦截绝大多数非法请求，空值缓存兜底处理布隆误判漏过的少量请求，双重防护效果最佳。

---

6. 常见问题

Q：布隆过滤器不支持删除，商品下架怎么办？

标准布隆过滤器确实不支持删除。生产中的处理策略：

方案一：定时重建
└── 每天凌晨从 DB 全量重新初始化布隆过滤器，接受短暂的不一致

方案二：计数布隆过滤器（Counting Bloom Filter）
└── 每个位改为计数器，支持删除，但内存占用更大

方案三：缓存空值兜底
└── 布隆误放（已删除但过滤器认为存在）的请求，
    查 DB 返回 null 后缓存空值，后续命中空值缓存返回 null

Q：分布式部署时，多实例如何共享布隆过滤器？

Redisson 的布隆过滤器数据存储在 Redis 中，天然支持多实例共享，无需额外处理。

Q：布隆过滤器初始化时 tryInit 的参数如何设置？

// 预估未来 1~2 年的数据量（留出余量，避免频繁重建）
// 误判率 0.01（1%）是通用选择，对性能影响极小
bloomFilter.tryInit(10_000_000L, 0.01);

// 注意：tryInit 只在过滤器不存在时初始化
// 已存在的过滤器不会被覆盖，需要先 delete 再 tryInit