redis缓存穿透中的布隆过滤器详解

布隆过滤器详解

基本概念

布隆过滤器（Bloom Filter）是一种概率型数据结构，用于快速判断元素是否存在于集合中。具有以下特点：

• 空间效率极高
• 查询时间复杂度O(k)（k为哈希函数数量）
• 允许误判（False Positive）
• 绝不漏判（False Negative）

数据结构组成

• 位数组（Bit Array）：长度为m的二进制向量

• 哈希函数组：k个相互独立且均匀分布的哈希函数

工作原理

图片来自小林coding

添加元素

使用k个哈希函数计算元素值

将对应的位数组位置置1

查询元素

使用相同的k个哈希函数计算

检查所有对应位置是否都为1

特性分析

误判率计算

误判概率公式：
P ≈ (1 - e^(-kn/m))k

m：位数组长度

k：哈希函数个数

n：已插入元素数量

最佳实践公式（最小误判率时）：
k = (m / n) * ln(2)

应用场景

• 缓存系统：防止缓存穿透
• 分布式系统：快速判断数据是否存在
• 爬虫系统：URL去重
• 数据库：减少磁盘查询
• 安全领域：恶意网址检测
• 推荐系统：已读内容过滤

优化方向

• 动态扩容：自动扩展位数组大小
• 参数调优：
  • 根据预期元素量选择m
  • 根据m/n比值选择k值
• 哈希函数优化：使用更均匀分布的哈希算法
• 变种方案：
  • 计数布隆过滤器（支持删除）
  • 分块布隆过滤器
  • 动态布隆过滤器

参数选择参考表

关键结论

• 位数组越大，误判率越低
• 哈希函数数量需要权衡：
  • 过少：容易冲突
  • 过多：位数组快速饱和
• 实际使用需要根据业务场景：
  • 选择可接受的误判率
  • 平衡内存使用和准确性

redis缓存穿透中布隆过滤器的应用

缓存穿透问题概述

缓存穿透是指在高并发场景下，大量请求查询数据库中不存在的数据，导致请求直接穿透缓存层打到数据库，给数据库带来巨大压力。例如，攻击者恶意构造大量不存在的商品 ID 来请求商品信息，由于缓存中没有这些数据，每次请求都要访问数据库，可能导致数据库性能下降甚至崩溃。

布隆过滤器的应用

• 初始化布隆过滤器：在 Redis 中，可以使用第三方库（如 RedisBloom）来实现布隆过滤器。首先，根据预期的元素数量和可接受的误判率，设置布隆过滤器的参数，如位数组大小（m）和哈希函数数量（k）。例如，预期要存储 10000 个元素，希望误判率控制在 1%，可以根据相关公式计算出合适的 m 和 k 值。
• 数据写入：当有新数据写入数据库时，同时将该数据的相关标识（如商品 ID）添加到布隆过滤器中。以添加商品信息为例，假设商品 ID 为 12345，通过 RedisBloom 的命令将其添加到布隆过滤器中。具体命令可能如下（不同库的命令可能略有差异）：

BF.ADD myBloomFilter product:12345

这里 myBloomFilter 是布隆过滤器的名称，product:12345 是要添加的元素。

• 请求处理：当有请求到来时，首先根据请求的参数（如请求的商品 ID），在布隆过滤器中进行查询。例如，请求商品 ID 为 67890 的商品信息，使用以下命令查询布隆过滤器：

BF.EXISTS myBloomFilter product:67890

如果查询结果为该元素不存在（返回 0），则直接返回结果，无需查询数据库，避免了缓存穿透。如果查询结果为该元素可能存在，则继续查询 Redis 缓存。

• 缓存查询与处理：如果布隆过滤器判断元素可能存在，接着查询 Redis 缓存中是否存在对应的数据。如果缓存中有数据，直接返回给客户端；如果缓存中没有数据，则查询数据库，将查询到的数据存入 Redis 缓存（同时设置合适的过期时间），然后返回给客户端。在将数据存入缓存的同时，也可以再次将相关标识添加到布隆过滤器中，以确保布隆过滤器的准确性。