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

一.业务背景

实际业务中使用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>() {
            @Override
            public 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.01
        bloomFilter = 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);
        }
    }
}

六.总结

1.通过使用布隆过滤器，可以显著减少不必要的数据库查询，防止缓存穿透，提升系统性能；

2.布隆过滤器虽然有误判的可能(会错误地判断一个元素存在)，但不会漏判，这保证了数据一致性和系统的稳定性。