布隆过滤器

介绍

概念：是一种高效查询的数据结构

作用：判断某个元素是否在一个集合中。（但是会出现误判的情况）

实现原理

1. 加入元素：

• 当一个元素需要加入到布隆过滤器中时，会使用一组哈希函数对该元素进行计算，得到多个哈希值。

• 每个哈希值对应到位数组的一个特定位置，将这些位置的值设置为1。

1. 查询元素：

• 对给定的元素再次进行相同的哈希计算，得到一组哈希值。

• 检查位数组中对应的每个位置是否都为1。如果所有位置都是1，那么认为这个元素可能在布隆过滤器中；如果有任何一个位置不为1，那么可以确定该元素不在布隆过滤器中。

误判和不可删除

下面是一个插入元素的图：

模拟插入：

1. 先插入“你好”

   1. 计算“你好”的hash值

   2. 插入到2的位置

2. 插入“hello”

   1. 计算“hello”的hash值

   2. 插入到2的位置

• 误判：如果计算出“hello”和“你好”的hash值是一样的，这个时候就会出现误判的情况。

• 不能删除：当发现“你好”和“hello”的值都在2位置，如果要删除“你好”的hash值在布隆过滤器中，那么“hello”也会同时被删除。

使用场景

使用在缓存穿透场景。

可以利用布隆过滤器先看看数据是否存在，再进行下一步的判断，可能可以减少很多次的数据库访问请求。

if(!bloomFilter.contains(data)){
    //.....
}

一般采用上述这种方式进行布隆过滤器的判断。

原因：布隆过滤器可能存在误判

• 当布隆过滤器中不存在一个数据的时候，那么这个数据肯定不存在。

• 当布隆过滤器存在一个数据的时候，可能这个数据还是存在的。

补充缓存穿透：

前端请求要查询一个数据，但是Redis中没有这个数据，所以要将请求打到数据库中。如果是大量请求情况，这个大的流量，可能导致数据库直接挂了。（一般可以采用布隆过滤器+分布式锁防止缓存穿透）

布隆过滤器使用

• Guava的布隆过滤器

• Redis实现的布隆过滤器

这里以Redis的布隆过滤器作示例：

1、引入依赖

<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>

2、配置Redis参数

spring:
  data:
    redis:
      host: 127.0.0.1
      port: 6379
#      password: 123456     #密码

3、布隆过滤器的配置类：

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;
    }
}

tryInit 有两个核心参数：

• expectedInsertions：预估布隆过滤器存储的元素长度。

• falseProbability：运行的误判率

这里是一个计算误判率和大小的网站：Bloom Filter Calculator

4、代码中的使用

private final RBloomFilter<String> userRegisterCachePenetrationBloomFilter;

• add方法添加

• contains方法判断是否存在