一、什么是布隆过滤器
布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于判断一个元素是否在一个集合中。
核心特性：
- 判断为"不存在"，则一定不存在（100% 准确）
- 判断为"存在"，则可能存在（有一定误判率）
- 插入的元素越多，误判率越高
- 不存储元素本身，只占用固定大小的位数组
典型场景：
| 场景 |
说明 |
| 缓存穿透防护 |
查询不存在的数据时直接拦截，不穿透到 DB |
| 爬虫 URL 去重 |
数十亿 URL 去重，内存只需几 GB |
| 黑名单/白名单 |
无需存储完整数据，快速判断是否命中 |
| 邮件/用户名判重 |
注册时判断用户名是否已被使用 |
| 推荐系统去重 |
已推荐过的不再重复推荐 |
二、布隆过滤器原理
2.1 数据结构
|
1
2
3
4
|
位数组（bit array）： ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 1 │ 0 │ 0 │ 1 │ ...
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
bit 索引: 0 1 2 3 4 5 6 7 8 9
|
2.2 添加元素
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
添加 "hello" 时：
hash1("hello") = 2 ──? 索引 2 置 1
hash2("hello") = 5 ──? 索引 5 置 1
hash3("hello") = 9 ──? 索引 9 置 1
添加 "world" 时：
hash1("world") = 1 ──? 索引 1 置 1
hash2("world") = 4 ──? 索引 4 置 1
hash3("world") = 8 ──? 索引 8 置 1
结果位数组：
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 1 │ 0 │ 1 │ 1 │ 0 │ 0 │ 1 │ 1 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
index: 0 1 2 3 4 5 6 7 8 9
|
2.3 查询元素
- 查询 “hello” → hash 得 [2,5,9] → 全是 1 → 可能存在
- 查询 “hello1” → hash 得 [2,3,7] → 位 3 是 0 → 一定不存在
- 查询 “hello2” → hash 得 [1,4,9] → 全是 1 → 可能存在（但从未添加过，这就是误判）
2.4 误判率计算
|
1
2
3
4
5
6
|
误判率 p ≈ (1 - e^(-k*n/m))^k
m = 位数组长度（bit 数）
n = 插入元素数量
k = 哈希函数个数
最优哈希函数个数：k ≈ (m/n) * ln(2) ≈ 0.7 * (m/n)
|
示例：m=10亿(128MB), n=100万，k≈7，误判率 p ≈ 千万分之一
三、方式一：Redis Stack / RedisBloom 模块（推荐）
Redis 7.x 已集成 RedisBloom，无需额外安装。旧版本安装 Redis Stack 即可。
3.1 创建布隆过滤器
|
1
2
|
# BF.RESERVE <key> <error_rate> <capacity> [EXPANSION expansion] [NONSCALING]
BF.RESERVE user_filter 0.01 1000000
|
| 参数 |
说明 |
| key |
过滤器名称 |
| error_rate |
期望误判率，越小越占内存（0~1） |
| capacity |
预计存储的元素数量 |
| EXPANSION |
容量超限后自动扩容倍数（默认 2） |
| NONSCALING |
禁止自动扩容 |
3.2 添加元素
|
1
2
|
BF.ADD user_filter "user_123" # 单个添加，返回 1 新增 / 0 可能重复
BF.MADD user_filter "a" "b" "c" # 批量添加 → [1, 1, 1]
|
3.3 查询元素
|
1
2
|
BF.EXISTS user_filter "user_123" # 单个查询，返回 1 可能存在 / 0 一定不存在
BF.MEXISTS user_filter "a" "x" "c" # 批量查询 → [1, 0, 1]
|
3.4 查看信息
|
1
2
|
BF.INFO user_filter # 返回容量、已插入数量、子过滤器数量等
BF.CARD user_filter # 返回独立 item 数（去重估计值）
|
3.5 多语言代码示例
Java（Jedis）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
import redis.clients.jedis.UnifiedJedis;
public class BloomFilterDemo {
private static final String FILTER_KEY = "cache:bloom";
public static void main(String[] args) {
try (UnifiedJedis jedis = new UnifiedJedis("redis://localhost:6379")) {
jedis.bfReserve(FILTER_KEY, 0.01, 1_000_000);
jedis.bfAdd(FILTER_KEY, "article_001");
jedis.bfAdd(FILTER_KEY, "article_002");
String id = "article_999";
if (!jedis.bfExists(FILTER_KEY, id)) {
System.out.println(id + " 一定不存在，直接返回 null");
return;
}
// 可能存在，查缓存或 DB
String cache = jedis.get("article:" + id);
if (cache != null) return;
// 查 DB ...
}
}
}
|
Go（go-redis）
|
1
2
3
4
5
6
|
import "github.com/redis/go-redis/v9"
rdb := redis.NewClient(&redis.Options{Addr: "localhost:6379"})
rdb.BFReserve(ctx, "myfilter", 0.01, 1000000)
rdb.BFAdd(ctx, "myfilter", "item1")
exists, _ := rdb.BFExists(ctx, "myfilter", "item1").Result()
|
Python（redis-py）
|
1
2
3
4
5
|
import redis
r = redis.Redis(host='localhost', port=6379)
r.bf().reserve('myfilter', 0.01, 1000000)
r.bf().add('myfilter', 'item1')
r.bf().exists('myfilter', 'item1') # True/False
|
四、方式二：Bitmap + Lua 脚本（纯 Redis，无插件）
当无法使用 Redis Stack 时，用 Redis 原生的 Bitmap（SETBIT/GETBIT）配合 Lua 手动实现。
4.1 Lua 添加元素脚本
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
-- bloom_add.lua，KEYS[1]=过滤器 key，ARGV=要添加的元素
local key = KEYS[1]
local bits = 1 << 31
for i = 1, #ARGV do
local val = ARGV[i]
local h1 = math.abs(redis.call('HASH', val) % bits)
local h2 = math.abs(redis.call('CRC16', val) % bits)
local h3 = math.abs((h1 + h2) % bits)
redis.call('SETBIT', key, h1, 1)
redis.call('SETBIT', key, h2, 1)
redis.call('SETBIT', key, h3, 1)
end
return 1
|
4.2 Lua 查询元素脚本
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
-- bloom_exists.lua，KEYS[1]=过滤器 key，ARGV=要查询的元素，返回数组 [1,0,1,...]
local key = KEYS[1]
local bits = 1 << 31
local results = {}
for i = 1, #ARGV do
local val = ARGV[i]
local h1 = math.abs(redis.call('HASH', val) % bits)
local h2 = math.abs(redis.call('CRC16', val) % bits)
local h3 = math.abs((h1 + h2) % bits)
if redis.call('GETBIT', key, h1) == 0
or redis.call('GETBIT', key, h2) == 0
or redis.call('GETBIT', key, h3) == 0 then
results[i] = 0
else
results[i] = 1
end
end
return results
|
4.3 Java 调用示例
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
public class RedisBitmapBloomFilter {
private static final String ADD_SCRIPT = loadScript("bloom_add.lua");
private static final String EXISTS_SCRIPT = loadScript("bloom_exists.lua");
private final JedisPool pool;
private final String addSha;
private final String existsSha;
public RedisBitmapBloomFilter(JedisPool pool) {
this.pool = pool;
try (Jedis jedis = pool.getResource()) {
this.addSha = jedis.scriptLoad(ADD_SCRIPT);
this.existsSha = jedis.scriptLoad(EXISTS_SCRIPT);
}
}
public void add(String key, String... values) {
try (Jedis jedis = pool.getResource()) {
jedis.evalsha(addSha, 1, key, values);
}
}
public boolean exists(String key, String value) {
try (Jedis jedis = pool.getResource()) {
List<Long> result = (List<Long>) jedis.evalsha(
existsSha, 1, key, value);
return result != null && result.get(0) == 1;
}
}
}
|
4.4 位数组大小与内存对照
| 位数组大小 (bit) |
内存占用 |
适用数据量 (1%误判) |
| 2^28 (2.68 亿) |
32 MB |
~100 万 |
| 2^30 (10.7 亿) |
128 MB |
~400 万 |
| 2^32 (42.9 亿) |
512 MB |
~1600 万 |
五、实战：缓存穿透防护
5.1 问题
恶意攻击者用大量不存在的 ID 查询 → 每次缓存未命中 → 全部落到数据库 → DB 崩溃
5.2 方案架构
|
1
2
3
|
请求 → 布隆过滤器 → 不存在 → 直接返回 null（拦截 ?）
→ 可能存在 → 查缓存 → 命中 → 返回
→ 未命中 → 查 DB → 回写缓存
|
5.3 Spring Boot 集成
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
@Configuration
public class BloomFilterConfig {
@Bean
public UnifiedJedis unifiedJedis() {
return new UnifiedJedis("redis://localhost:6379");
}
@PostConstruct
public void initBloomFilter(UnifiedJedis jedis, ProductMapper mapper) {
jedis.bfReserve("product:bloom", 0.01, 1_000_000);
// 预热：将已有数据 ID 全部加入过滤器
mapper.getAllIds().forEach(id -> jedis.bfAdd("product:bloom", id));
}
}
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
@Service
public class ProductService {
private final UnifiedJedis jedis;
private final ProductMapper mapper;
public Product getById(String id) {
// 1. 布隆过滤器拦截
if (!jedis.bfExists("product:bloom", id)) {
return null;
}
// 2. 缓存查询
String cacheKey = "product:" + id;
String cached = jedis.get(cacheKey);
if (cached != null) return JSON.parseObject(cached, Product.class);
// 3. 数据库查询
Product p = mapper.selectById(id);
if (p != null) jedis.setex(cacheKey, 3600, JSON.toJSONString(p));
return p;
}
public void add(Product p) {
mapper.insert(p);
jedis.bfAdd("product:bloom", String.valueOf(p.getId()));
}
}
|
六、常见问题
Q1：布隆过滤器可以删除元素吗？
标准布隆过滤器不支持删除。需删除时可使用 RedisBloom 的计数布隆过滤器（Cuckoo Filter）：
|
1
2
3
4
|
CF.RESERVE cfilter 0.01 1000000
CF.ADD cfilter "item1" # 添加
CF.DEL cfilter "item1" # 删除（支持！）
CF.EXISTS cfilter "item1" # 判断
|
Q2：如何选择误判率？
| 场景 |
建议误判率 |
| 缓存穿透防护 |
1% |
| URL / 爬虫去重 |
0.1% ~ 1% |
| 黑名单 |
0.01% |
Q3：布隆过滤器满了怎么办？
| 策略 |
说明 |
| 自动扩容（默认） |
容量超限自动创建子过滤器，查询时遍历全部 |
| 分层过滤 |
按时间分片：bloom:2026-01、bloom:2026-02 |
| 手动重建 |
监控误判率，达阈值后重建更大的过滤器 |
七、方案对比总结
| 方案 |
优点 |
缺点 |
适用场景 |
| RedisBloom 模块 |
API 简洁、高性能、自动扩容 |
需 Redis Stack / 7.x |
生产环境首选 |
| Bitmap + Lua |
纯 Redis，零依赖 |
实现复杂、不可扩容 |
无法装模块的过渡方案 |
| 本地 Guava |
单机零网络延迟 |
多实例间不一致 |
单机应用 |
| Redisson |
封装好的分布式实现 |
底层仍是 Bitmap |
不想手写 Lua 的场景 |
结论：
- 优先用 RedisBloom；
- 装不了再用 Bitmap + Lua 兜底。
|
