缓存击穿（Cache Penetration）是分布式系统和缓存使用中的一个常见问题，布隆过滤器在解决缓存击穿问题时非常有用。接下来我会介绍缓存击穿的概念以及布隆过滤器在解决该问题中的应用。
什么是缓存击穿？
缓存击穿是指当大量的客户端请求访问一个不存在的缓存数据时，这些请求会绕过缓存直接击穿到数据库，给数据库带来巨大压力，甚至可能导致服务瘫痪。这通常发生在以下几种情况下：
- 请求的键不存在于缓存中：比如用户在查询一个不存在的商品 ID、文章 ID 等。
- 缓存未命中：由于查询到的结果不存在，直接请求数据库，这种请求行为在高并发场景下，会对数据库产生非常大的压力。
缓存击穿的场景
- 假设你有一个大型电商网站，客户经常搜索商品。某些时候，一些用户会输入随机的 ID 进行商品搜索。如果这些 ID 是无效的，且对应的数据并不在数据库中，查询结果也不会被缓存。这些请求会不断地穿透缓存，直接访问数据库，导致数据库负载过高。
- 在这种情况下，大量查询无效键的请求绕过缓存，直接访问数据库，使得数据库变得不堪重负，甚至宕机。
布隆过滤器在解决缓存击穿中的应用
布隆过滤器可以有效地解决缓存击穿问题，原因是它可以快速判断一个键是否一定不存在，从而避免对数据库的无效查询。
布隆过滤器如何应用于缓存击穿？
-
初始化阶段：
- 在系统启动或初始化时，将所有数据库中的有效键（比如商品 ID）加载到布隆过滤器中。布隆过滤器中记录了所有有效键的信息。
-
请求阶段：
- 当客户端请求某个键时，首先使用布隆过滤器进行检查。
- 布隆过滤器判断：
- 如果布隆过滤器判断该键一定不存在（即返回
false），那么直接返回结果为 “无数据”。 - 如果布隆过滤器判断该键可能存在（即返回
true），则继续查询缓存。 - 如果缓存命中，返回缓存结果；如果缓存未命中，查询数据库。
- 如果布隆过滤器判断该键一定不存在（即返回
-
查询数据库：
- 如果布隆过滤器判断该键可能存在，且缓存也没有结果，最终的查询会走到数据库。
- 如果数据库也没有结果，通常可以将结果设置为一个“空对象”并加入缓存，以防止短时间内再度访问造成缓存击穿。
布隆过滤器解决缓存击穿的好处
-
减少数据库的访问：
- 布隆过滤器在大多数情况下可以直接判断无效的请求，从而不必查询数据库，这样可以减少对数据库的压力。
-
高效的存在性判断：
- 布隆过滤器使用位数组和多个哈希函数，可以在常数时间复杂度 O(k)（k 为哈希函数个数）内完成存在性判断，并且占用的空间非常小。
示例：布隆过滤器用于防止缓存击穿
以下是一个简单的示例，演示如何利用布隆过滤器来防止缓存击穿。
import java.util.BitSet;
public class CacheWithBloomFilter {
private static final int DEFAULT_SIZE = 1000; // 位数组大小
private static final int[] SEEDS = new int[]{7, 11, 13, 31, 37, 61}; // 哈希函数种子
private BitSet bits;
private HashFunction[] hashFunctions;
public CacheWithBloomFilter() {
bits = new BitSet(DEFAULT_SIZE);
hashFunctions = new HashFunction[SEEDS.length];
for (int i = 0; i < SEEDS.length; i++) {
hashFunctions[i] = new HashFunction(DEFAULT_SIZE, SEEDS[i]);
}
// 模拟初始化阶段，将数据库中有效的数据加载到布隆过滤器
String[] existingKeys = {"product_1", "product_2", "product_3"};
for (String key : existingKeys) {
add(key);
}
}
// 添加元素到布隆过滤器
public void add(String value) {
for (HashFunction f : hashFunctions) {
bits.set(f.hash(value), true);
}
}
// 查询元素是否存在
public boolean mightContain(String value) {
for (HashFunction f : hashFunctions) {
if (!bits.get(f.hash(value))) {
return false; // 如果有一个哈希值位置为 0，则说明一定不存在
}
}
return true; // 所有位都为 1，则说明可能存在
}
// 模拟缓存查询
public String getFromCache(String key) {
// 在布隆过滤器中检查是否可能存在
if (!mightContain(key)) {
System.out.println("Key '" + key + "' is not in bloom filter, skipping cache and DB lookup.");
return null; // 一定不存在
}
// 模拟缓存查询（这里假设缓存总是未命中）
System.out.println("Key '" + key + "' might be in bloom filter, continue cache lookup...");
return null; // 模拟缓存未命中
}
// 模拟数据库查询
public String getFromDB(String key) {
// 模拟数据库查询（这里假设部分键不存在）
System.out.println("Querying database for key '" + key + "'...");
if ("product_1".equals(key) || "product_2".equals(key) || "product_3".equals(key)) {
return "Valid Product";
}
return null; // 数据库中不存在该键
}
public static void main(String[] args) {
CacheWithBloomFilter cache = new CacheWithBloomFilter();
// 查询不存在的键，布隆过滤器返回一定不存在
cache.getFromCache("product_100"); // 布隆过滤器直接拒绝
// 查询可能存在的键
cache.getFromCache("product_1");
cache.getFromDB("product_1"); // 继续查询数据库
}
// 内部静态类，定义哈希函数
private static class HashFunction {
private int cap;
private int seed;
public HashFunction(int cap, int seed) {
this.cap = cap;
this.seed = seed;
}
public int hash(String value) {
int result = 0;
for (int i = 0; i < value.length(); i++) {
result = seed * result + value.charAt(i);
}
return (cap - 1) & result; // 返回在 [0, cap) 范围内
}
}
}
解释代码
-
布隆过滤器初始化：
- 将数据库中所有有效的键（例如
"product_1", "product_2", "product_3"）都添加到布隆过滤器中。
- 将数据库中所有有效的键（例如
-
查询流程：
- 当查询一个不存在的键
"product_100"时，布隆过滤器直接判断该键不存在，从而避免了数据库查询。 - 当查询一个可能存在的键
"product_1"时，布隆过滤器判断该键可能存在，于是继续进行缓存查询或者数据库查询。
- 当查询一个不存在的键
总结布隆过滤器在缓存击穿中的作用
- 快速判断无效键：布隆过滤器可以高效地判断某个键是否存在。如果布隆过滤器判定某个键一定不存在，那么请求不会再访问缓存和数据库，从而减少无效请求对系统的压力。
- 减少数据库压力：通过布隆过滤器，可以有效减少对数据库的无效访问，从而防止缓存击穿给数据库带来的高并发压力。
布隆过滤器的这种使用场景，在实际的大规模系统中非常常见，尤其是在需要减少数据库访问次数、保护数据库负载的系统中，如分布式缓存系统、API 限流、去重等场景。
