步隆过滤器

penjc2024-05-282025-03-10

检查用户名是否存在

直接查询数据库请求用户名是否存在。

存在什么问题？

海量用户如果查询的用户名存在或不存在，全部请求数据库，会将数据库直接打满。

检查用户名是否存在引起的问题

用户名加载缓存

第一版解决方案，将数据库已有的用户名全部放到缓存里。

该方案问题：

是否要设置数据的有效期？只能设置为无效期，也就是永久数据。
如果是永久不过期数据，占用 Redis 内存太高。

布隆过滤器

第二版解决方案，使用布隆过滤器。

什么是布隆过滤器

布隆过滤器是一种数据结构，用于快速判断一个元素是否存在于一个集合中。具体来说，布隆过滤器包含一个位数组和一组哈希函数。位数组的初始值全部置为 0。在插入一个元素时，将该元素经过多个哈希函数映射到位数组上的多个位置，并将这些位置的值置为 1。

1字节（Byte）=8位（Bit）

在查询一个元素是否存在时，会将该元素经过多个哈希函数映射到位数组上的多个位置，如果所有位置的值都为 1，则认为元素存在；如果存在任一位置的值为 0，则认为元素不存在。

优缺点

优点：

高效地判断一个元素是否属于一个大规模集合。
节省内存。

缺点：

可能存在一定的误判。

布隆过滤器误判理解

布隆过滤器要设置初始容量。容量设置越大，冲突几率越低。
布隆过滤器会设置预期的误判值。

误判能否接受

布隆过滤器的误判是否能够接受？

答：可以容忍。为什么？因为用户名不是特别重要的数据，如果说我设置用户名为 aaa，系统返回我不可用，那我大可以在 aaa 的基础上再加一个a，也就是 aaaa。

代码中使用布隆过滤器

引入 Redisson 依赖

<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson-spring-boot-starter</artifactId>
</dependency>

配置 Redis 参数

spring:
  data:
    redis:
      host: 127.0.0.1
      port: 6379
      password: 123456

创建布隆过滤器实例

import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.boot.context.properties.EnableConfigurationProperties;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

/**
 * 布隆过滤器配置
 */
@Configuration
public class RBloomFilterConfiguration {

    /**
     * 防止用户注册查询数据库的布隆过滤器
     */
    @Bean
    public RBloomFilter<String> userRegisterCachePenetrationBloomFilter(RedissonClient redissonClient) {
        RBloomFilter<String> cachePenetrationBloomFilter = redissonClient.getBloomFilter("xxx");
        cachePenetrationBloomFilter.tryInit(0, 0);
        return cachePenetrationBloomFilter;
    }
}