布隆过滤器实战|温言的小破站

场景

首先，明确我们的场景，就是在用户注册的时候查询一下用户名和账户是否已经存在了，这个是一个很基础的问题，这里我们主要列举三种方案，并且列举一下这三种方案的优缺点

第一种是直接查询数据库请求用户名是否存在
在查询数据库之前加一层缓存
使用布隆过滤器

一、检查用户名是否存在

第一种方式，也就是最直接的，那就是查询数据库请求用户名是否存在。

流程图如下：

这种方式很直接，也是我们作为初学者最容易想到的，这种方式如果数据量不大，确实可以这样做，但是，你有没有考虑过一个点，当你的网站用户数量变多之后，就所有用户的请求，无论存在还是不存在，所有的用户名查询请求都会请求到数据库，这样下去数据库的压力不就很大了吗？所以，针对以上问题，我这里提出一个问题，问题如下：

海量用户如果查询的用户名存在或者不存在的场景，全部请求都打到数据库，这样会对数据库产生巨大的压力。

二、根据用户名加载缓存

第二种方式：根据用户名加载缓存，然后对缓存实现访问，如果缓存内存在数据的话，那就访问缓存内的内容，缓存中如果没有对应的数据，再访问数据库。

针对以上场景，在学习了 Redis 之后的小伙伴可能会有一个想法，那就是我可不可以将数据库里面所有已经有的用户名全都放到缓存里呢，想到这里的小伙伴说明很不错，你可以想到用 Redis 来作缓存，说明了你已经了解 Redis 的基本使用了，那么，接下来，针对这个点，我们来看一下以下的流程图：

现在我们来分析一下该方案存在的问题：

是否要设置数据的有效期？
不设置有效期，用户名这个不属于热点数据，如果将大批量的数据放到内存中，这是一种对于 Redis 内存数据的浪费；
设置有效期，设置有效期，如果用户名不存在了，就刷新 DB，要是用户故意发起这种不存在的数据，就每次都要加载 DB,这样对于数据库的压力就会比较大；

综上所示，我们这里只能设置为没有无效期，即永久数据；如果你设置为永久不过期数据，占用 Redis 内存太高了

三、布隆过滤器

针对以上两种情况，可能很多人就陷入了无解的境地了，那么有什么更好的方法呢，那就是我们今天的压轴——布隆过滤器。

首先，很多人可能听说过布隆过滤器，但是可能并不是那么得熟悉，我们在这里先介绍一下布隆过滤器

3.1 什么是布隆过滤器？

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

这里提一个点，为什么不用数组和字符串来存呢？

这个是因为位数据其所占空间是非常小的，1字节（Byte）=8位（Bit）

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

3.2 优缺点

优点：

由于其使用哈希函数直接定位数组的下标，所以可以高效地判断一个元素是否属于一个大规模集合
由于其使用位数组的方式，所以其很节省内存，一亿的元素，其只需要 500 MB 的内存便可以存储 40 亿的数据，这种内存的消耗是可以接受的

缺点：

其可能存在一定的误判情况，由于是哈希存储，其可能产生哈希冲突的情况，举例来说，就是我现在数字 1 放到了 6 的位置，然后我现在 6 来访问的话，可能访问到 6 的位置，这个时候数组中是没有 6 的，就可能存在误判的情况，但是如果想使用布隆过滤器的话，就要考虑可不可以忍受这种容错性。

3.3 布隆过滤器误判理解

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

3.4 本题的场景是否可以接受误判？

这种场景下的误判是可以容忍的，因为用户名本身不是非常重要的数据，也就是说我如果设置用户名为 AAA，系统返回我这个用户名不可以使用的话，我只需要在AAA的基础上加一个字符，即 AAAA就可以了，所以这种场景式可以接受误判的。

3.5 布隆过滤器流程图

初始化流程图：

执行流程图：

四、布隆过滤器实战

4.1 引入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>

4.2 配置redis参数

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

4.3 创建布隆过滤器实例

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

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

tryInit 有两个核心参数：

expectedInsertions：预估布隆过滤器存储的元素长度。
falseProbability：运行的误判率。

错误率越低，位数组越长，布隆过滤器的内存占用越大。

错误率越低，散列 Hash 函数越多，计算耗时较长。

一个布隆过滤器占用大小的在线网站：Bloom Filter Calculator

使用布隆过滤器的两种场景：

初始使用：注册用户时就向容器中新增数据，就不需要任务向容器存储数据了。
使用过程中引入：读取数据源将目标数据刷到布隆过滤器。

4.4 代码中使用

private final RBloomFilter<String> userRegisterCachePenetrationBloomFilter;

//注册时加入布隆过滤器
userRegisterCachePenetrationBloomFilter.add(requestParam.getUsername());

public Boolean hasUsername(String username) {
    return !userRegisterCachePenetrationBloomFilter.contains(username);
}