当前位置：首页 > news >正文

彻底理解布隆过滤器怎么解决缓存穿透问题

news 2024/12/13 21:41:48

一.业务背景

实际业务中使用Redis，都是先通过用户插入数据到Mysql中，然后更新缓存到Redis，下一次用户再查询该数据的时候就可以通过Redis来进行查询。

先看下图，是假设的一个用户查询的场景：

首先用户查询的时候会去缓存里面查询，查看是否有该数据，如果不存在，就会去Mysql中查询，然后将数据返回给用户和缓存到Redis；

然后一些非法请求过来，查询的一些Key在Redis里面不存在，并且Mysql也不存在，这些数据就不会被缓存到Redis中；

此时，这中频繁的发起伪造的请求，就相当于导致Redis的缓存不存在了，所有请求都会穿透Redis的缓存去直接访问Mysql，就会把Mysql搞宕机。

这就是我们所说的缓存穿透问题，解决这个问题可以通过布隆过滤器。

二.什么是BitMaps

在谈布隆过滤器之前，需要先了解Bitmaps，它是Redis的一种高级数据结构。

定义：Bitmaps(位图)是一种数据结构，用于表示一个由二进制位(bit)组成的集合，每个二进制位的值可以是 0 或 1，通常用于表示某些状态或者集合中元素的存在与否，位图在内存中高效地存储和操作大量的布尔值(即 0 或 1)，因此在许多场景中，特别是在高效存储和查找时，具有非常重要的应用。

比如现在要去存一个1 3 5 7，在BitMap里面怎么表示？

从上图来看，每个整数映射到它的值(例如，1 映射到第 1 位，3 映射到第 3 位，等等)，1存入的时候，存在bit[1]，3存在bit[3]，5存在bit[5]，7存在bit[7]，那么就只需要一个bit类型的8位数组，它就只有一个bit的大小。

在BitMap里面又诞生了一个叫做布隆过滤器，在大致了解了布隆过滤器后底层实现后，再来谈谈布隆过滤器。

三.布隆过滤器

1970 年布隆提出了一种布隆过滤器的算法(概率判断算法)，用来判断一个元素是否在一个集合中，这种算法由一个二进制数组和一个 Hash 算法组成。

比如上面的查询逻辑，当不正常的用户查查询数据的时候，先判断该数据存不存在，不存在直接返回就行了，这样就不会去查询Mysql了。

接下里看一下布隆过滤器的实现：

数据库中存在的数据有A B C，通过Hash算法存储在二进制数组中，并且把对应位置写成1，然后此时过来一个D F数据，接下来要去判断F在不在集合，就需要通过Hash算法计算F出来的位置，此时位置如果是0，代表F不存在，因为不存在的时候默认值就是0；

但是这样可能会出现一个问题，就是Hash算法不能保证存储的数据一定分散在不同的数组位置，所以是会出现Hash冲突的问题，所以说D数据经过计算它所在的位置依然是1，这就是布隆过滤器的误判问题。

1.为什么误判问题不是很重要？

通过Hash计算在数组上不一定是数据库中存在的数据，但是通过Hash计算不在数组的一定不在集合，这种误判的概率是很小的，所以及时出现误判，也是可以运行的。

2.优化方案：

(1)可以通话增大数组来减少Hash冲突的概率；

(2)采用两个Hash算法，只要一Hash算法匹配不存在就不存在：

在 Guava 中，你可以通过实现 Funnel 接口和自定义 Hasher 来使用多个哈希算法，也就是说，可以在 Hasher 中使用两个不同的哈希函数来计算同一个元素的多个哈希值，测试代码如下：

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnel;
import com.google.common.hash.Hasher;
import com.google.common.hash.Hashing;
import com.google.common.base.Charsets;import java.nio.charset.StandardCharsets;public class CustomBloomFilter {public static void main(String[] args) {// 创建一个自定义的Funnel，使用两个哈希算法Funnel<String> funnel = new Funnel<String>() {@Overridepublic void funnel(String from, Hasher into) {// 使用第一个哈希算法（MurmurHash）into.putString(from, StandardCharsets.UTF_8);int murmurHash = Hashing.murmur3_128().hashString(from, StandardCharsets.UTF_8).asInt();into.putInt(murmurHash);// 使用第二个哈希算法（SHA-256）byte[] sha256Hash = Hashing.sha256().hashString(from, StandardCharsets.UTF_8).asBytes();for (byte b : sha256Hash) {into.putByte(b);}}};// 创建布隆过滤器BloomFilter<String> bloomFilter = BloomFilter.create(funnel, 100000, 0.01);// 测试布隆过滤器String value = "hello";bloomFilter.put(value);System.out.println("Contains 'hello'? " + bloomFilter.mightContain(value));}
}

四.缓存击穿的解决

流程如下：

1.创建一个布隆过滤器，用来存储需要缓存的数据的键；

2.如果用户查询的数据不存在布隆过滤器中，直接返回；

3.如果用户查询的数据存在布隆过滤器，通过Redis去获取数据；

4.如果Redis没有获取到数据，再查询Mysql，并将该数据的加入布隆过滤器中。

通过上诉几步，就可以解决缓存击穿问题。

五.代码实现

下面写一段简单代码，举例一下实现步骤：

1.引入布隆过滤器库

<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>32.0.1-jre</version>
</dependency>

2. 布隆过滤器初始化和配置

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;import java.nio.charset.StandardCharsets;public class BloomFilterExample {// 创建一个布隆过滤器private static BloomFilter<String> bloomFilter;public static void initBloomFilter() {// 初始化布隆过滤器，预计存储100000个元素，错误率设为0.01bloomFilter = BloomFilter.create(Funnels.stringFunnel(StandardCharsets.UTF_8), 100000, 0.01);// 添加初始的元素到布隆过滤器addToBloomFilter("user123");addToBloomFilter("user456");}// 向布隆过滤器添加元素public static void addToBloomFilter(String data) {bloomFilter.put(data);}// 检查元素是否存在布隆过滤器中public static boolean mightContain(String data) {return bloomFilter.mightContain(data);}
}

3.模拟缓存穿透防护

import java.util.HashMap;
import java.util.Map;public class CacheService {// 模拟数据库（简单的 HashMap）private static final Map<String, String> database = new HashMap<>();static {// 模拟数据库中存在的数据database.put("user123", "User 123 Data");database.put("user456", "User 456 Data");}// 模拟缓存private static final Map<String, String> cache = new HashMap<>();public static String getFromCache(String key) {return cache.get(key);}public static void setCache(String key, String value) {cache.put(key, value);}// 模拟从数据库查询数据public static String getFromDatabase(String key) {return database.get(key);}// 使用布隆过滤器防止缓存穿透public static String getData(String key) {// 先检查布隆过滤器，防止缓存穿透if (!BloomFilterExample.mightContain(key)) {return "Data does not exist";  // 直接返回数据不存在}// 查缓存String cachedData = getFromCache(key);if (cachedData != null) {return cachedData;  // 缓存命中}// 如果缓存没有，查数据库String dbData = getFromDatabase(key);if (dbData != null) {// 如果数据库中有，设置到缓存setCache(key, dbData);// 更新布隆过滤器BloomFilterExample.addToBloomFilter(key);return dbData;} else {       return "Data does not exist";  // 数据不存在}}
}

4.测试代码

public class Main {public static void main(String[] args) {// 初始化布隆过滤器BloomFilterExample.initBloomFilter();// 模拟请求的数据String[] keys = {"user123", "user456", "user789"};for (String key : keys) {System.out.println("Fetching data for: " + key);String result = CacheService.getData(key);System.out.println(result);}}
}