(目录)

布隆过滤器

1 什么是布隆过滤器

介绍布隆过滤器之前，先介绍一下哈希函数，我们在Java中的HashMap，HashSet也接触过hashcode()这个函数。

哈希函数指将哈希表中元素的关键键值通过一定的函数关系映射为元素存储位置的函数。

哈希函数的特点：

如果根据同一个哈希函数得到的哈希值不同，那么这两个哈希值的原始输入值肯定不同

如果根据同一个哈希函数得到的两个哈希值相等，两个哈希值的原始输入值有可能相等，有可能不相等

那什么是布隆过滤器？

布隆过滤器实际上是一个非常长的二进制向量(bitmap)和一系列随机哈希函数。

优缺点

优点：

布隆过滤器存储空间和插入/查询时间都是常数

Hash函数相互之间没有关系，方便由硬件并行实现

布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势

布隆过滤器可以表示全集，其它任何数据结构都不能

缺点：

有一定的误判率

常见的补救办法是建立一个小的白名单，存储那些可能被误判的元素。但是如果元素数量太少，使用散列表足矣。

一般情况下不能从布隆过滤器中删除元素

我们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加1，这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面，这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

2 布隆过滤器的作用

布隆过滤器可以用于检索一个元素是否在一个集合中，常用于解决如下问题

解决Redis缓存穿透

邮件过滤，使用布隆过滤器来做邮件黑名单过滤

解决视频推荐过的不再推荐

缓存穿透攻击

缓存穿透攻击:

恶意用户在短时内大量查询不存在的数据，导致大量请求被送达数据库进行查询，当请求数量超过数据库负载上限时，使系统缓存穿透攻击是指恶意用户在短时内大量查询不存在的数据，导致大量请求被送达数据库进行查询，当请求数量超过数据库负载上限时，使系统响应出现高延迟甚至瘫痪的攻击行为。响应出现高延迟甚至瘫痪的攻击行为.

3 布隆过滤器的基本原理

首先，建立一个二进制向量，并将所有位设置为0。

然后，选定K个散列函数，用于对元素进行K次散列，计算向量的位下标。

添加元素：当添加一个元素到集合中时，通过K个散列函数分别作用于元素，生成K个值作为下标，并将向量的相应位设置为1。

检查元素：

如果要检查一个元素是否存在集合中，用同样的散列方法，生成K个下标，并检查向量的相应位是否全部是1。

如果全为1，则该元素很可能在集合中

否则（只要有1个或以上的位为0），该元素肯定不在集合中。

布隆过滤器介绍及原理、集成Redisson布隆过滤器解决Redis缓存穿透问题

4. 减少布隆过滤器误判的措施

增加二进制数组位数

增加 Hash 次数

5 布隆过滤器再项目中使用流程

布隆过滤器介绍及原理、集成Redisson布隆过滤器解决Redis缓存穿透问题

核心代码：

布隆过滤器介绍及原理、集成Redisson布隆过滤器解决Redis缓存穿透问题

6 布隆过滤器中内容被删除了怎么办？

布隆过滤器因为某一位二进制可能被多个编号Hash引用,因此布隆过滤器无法直接处理删除数据的情况

常见的解决方案如下：

解决方案1:定时异步重建布隆过滤器

解决方案2: 计数Bloom Fliter

7 在Spring Boot中集成Redisson实现布隆过滤器

7.1 添加redisson依赖

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

7.2 配置yml

spring:
  datasource:
    username: xx
    password: xxxxxx
    driver-class-name: com.mysql.cj.jdbc.Driver
    url: jdbc:mysql://localhost:3306/test?useUnicode=true&characterEncoding=utf-8&serverTimezone=CTT
  cache:
    type: redis
  redis:
    database: 0
    port: 6379               # Redis服务器连接端口
    host: localhost          # Redis服务器地址
    password: xxxxxx         # Redis服务器连接密码（默认为空）
    timeout: 5000            # 超时时间

7.3 配置RedissonConfig

import com.fasterxml.jackson.annotation.JsonAutoDetect;
import com.fasterxml.jackson.annotation.PropertyAccessor;
import com.fasterxml.jackson.databind.ObjectMapper;
import org.redisson.Redisson;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.cache.CacheManager;
import org.springframework.cache.annotation.EnableCaching;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.data.redis.cache.RedisCacheConfiguration;
import org.springframework.data.redis.cache.RedisCacheManager;
import org.springframework.data.redis.connection.RedisConnectionFactory;
import org.springframework.data.redis.serializer.Jackson2JsonRedisSerializer;
import org.springframework.data.redis.serializer.RedisSerializationContext;
import org.springframework.data.redis.serializer.RedisSerializer;
import org.springframework.data.redis.serializer.StringRedisSerializer;

import java.time.Duration;
import java.util.Random;

@EnableCaching
@Configuration
public class RedissonConfig {

    @Value("${spring.redis.host}")
    private String host;

    @Value("${spring.redis.port}")
    private String port;

    @Value("${spring.redis.password}")
    private String password;


    @Bean(destroyMethod = "shutdown")  // bean销毁时关闭Redisson实例，但不关闭Redis服务
    public RedissonClient redisson() {
        //创建配置
        Config config = new Config();
        /**
         *  连接哨兵：config.useSentinelServers().setMasterName("myMaster").addSentinelAddress()
         *  连接集群： config.useClusterServers().addNodeAddress()
         */
        config.useSingleServer()
                .setAddress("redis://" + host + ":" + port)
                .setPassword(password)
                .setTimeout(5000);
        //根据config创建出RedissonClient实例
        return Redisson.create(config);
    }

    @Bean
    public CacheManager RedisCacheManager(RedisConnectionFactory factory) {
        RedisSerializer<String> redisSerializer = new StringRedisSerializer();
        Jackson2JsonRedisSerializer jackson2JsonRedisSerializer = new Jackson2JsonRedisSerializer(Object.class);
        // 解决查询缓存转换异常的问题
        ObjectMapper om = new ObjectMapper();
        om.setVisibility(PropertyAccessor.ALL, JsonAutoDetect.Visibility.ANY);
        /**
         * 新版本中om.enableDefaultTyping(ObjectMapper.DefaultTyping.NON_FINAL)已经被废弃
         * 建议替换为om.activateDefaultTyping(LaissezFaireSubTypeValidator.instance, ObjectMapper.DefaultTyping.NON_FINAL)
         */
        om.enableDefaultTyping(ObjectMapper.DefaultTyping.NON_FINAL);
        jackson2JsonRedisSerializer.setObjectMapper(om);
        // 配置序列化解决乱码的问题
        RedisCacheConfiguration config = RedisCacheConfiguration.defaultCacheConfig()
                // 设置缓存过期时间  为解决缓存雪崩,所以将过期时间加随机值
                .entryTtl(Duration.ofSeconds(60 * 60 + new Random().nextInt(60 * 10)))
                // 设置key的序列化方式
                .serializeKeysWith(RedisSerializationContext.SerializationPair.fromSerializer(redisSerializer))
                // 设置value的序列化方式
                .serializeValuesWith(RedisSerializationContext.SerializationPair.fromSerializer(jackson2JsonRedisSerializer));
        // .disableCachingNullValues(); //为防止缓存击穿，所以允许缓存null值
        RedisCacheManager cacheManager = RedisCacheManager.builder(factory)
                .cacheDefaults(config)
                // 启用RedisCache以将缓存 put/evict 操作与正在进行的 Spring 管理的事务同步
                .transactionAware()
                .build();
        return cacheManager;
    }
}

7.4 工具类BloomFilterUtil

import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.stereotype.Component;

import javax.annotation.Resource;

@Component
public class BloomFilterUtil {

    @Resource
    private RedissonClient redissonClient;

    /**
     * 创建布隆过滤器
     *
     * @param filterName         过滤器名称
     * @param expectedInsertions 预测插入数量
     * @param falsePositiveRate  误判率
     */
    public <T> RBloomFilter<T> create(String filterName, long expectedInsertions, double falsePositiveRate) {
        RBloomFilter<T> bloomFilter = redissonClient.getBloomFilter(filterName);
        bloomFilter.tryInit(expectedInsertions, falsePositiveRate);
        return bloomFilter;
    }
}

7.5 编写service实现层

其它层正常编写即可，与之前并无差别，此处不再展示

import com.baomidou.mybatisplus.extension.service.impl.ServiceImpl;
import com.company.springboot.entity.User;
import com.company.springboot.mapper.UserMapper;
import com.company.springboot.service.UserService;
import com.company.springboot.util.BloomFilterUtil;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.client.codec.StringCodec;
import org.springframework.cache.annotation.CacheEvict;
import org.springframework.cache.annotation.CachePut;
import org.springframework.cache.annotation.Cacheable;
import org.springframework.stereotype.Service;

import javax.annotation.PostConstruct;
import javax.annotation.Resource;
import java.util.List;
import java.util.Random;
import java.util.concurrent.TimeUnit;

@Service
public class UserServiceImpl extends ServiceImpl<UserMapper, User>
        implements UserService {
    // 预期插入数量
    static long expectedInsertions = 200L;
    // 误判率
    static double falseProbability = 0.01;

    // 非法请求所返回的JSON
    static String illegalJson = "[\"com.company.springboot.entity.User\",{\"id\":null,\"userName\":\"null\",\"sex\":null,\"age\":null}]";

    private RBloomFilter<Long> bloomFilter = null;

    @Resource
    private BloomFilterUtil bloomFilterUtil;

    @Resource
    private RedissonClient redissonClient;

    @Resource
    private UserMapper userMapper;

    @PostConstruct // 项目启动的时候执行该方法，也可以理解为在spring容器初始化的时候执行该方法
    public void init() {
        // 启动项目时初始化bloomFilter
        List<User> userList = this.list();
        bloomFilter = bloomFilterUtil.create("idWhiteList", expectedInsertions, falseProbability);
        for (User user : userList) {
            bloomFilter.add(user.getId());
        }
    }


    @Cacheable(cacheNames = "user", key = "#id", unless = "#result==null")
    public User findById(Long id) {
        // bloomFilter中不存在该key,为非法访问
        if (!bloomFilter.contains(id)) {
            System.out.println("所要查询的数据既不在缓存中，也不在数据库中，为非法key");
               /**
             * 设置unless = "#result==null"并在非法访问的时候返回null的目的是不将该次查询返回的null使用
             * RedissonConfig-->RedisCacheManager-->RedisCacheConfiguration-->entryTtl设置的过期时间存入缓存。
             *
             * 因为那段时间太长了，在那段时间内可能该非法key又添加到bloomFilter，比如之前不存在id为1234567的用户，
             * 在那段时间可能刚好id为1234567的用户完成注册，使该key成为合法key。
             *
             * 所以我们需要在缓存中添加一个可容忍的短期过期的null或者是其它自定义的值,使得短时间内直接读取缓存中的该值。
             *
             * 因为Spring Cache本身无法缓存null，因此选择设置为一个其中所有值均为null的JSON，
             */
            redissonClient.getBucket("user::" + id, new StringCodec()).set(illegalJson, new Random().nextInt(200) + 300, TimeUnit.SECONDS);
            return null;
        }
        // 不是非法访问，可以访问数据库
        System.out.println("数据库中得到数据*****");
        return userMapper.selectById(id);
    }

    // 先执行方法体中的代码，成功执行之后删除缓存
    @CacheEvict(cacheNames = "user", key = "#id")
    public boolean delete(Long id) {
        // 删除数据库中具有的数据,就算此key从此之后不再出现，也不能从布隆过滤器删除
        return userMapper.deleteById(id) == 1;
    }

    // 如果缓存中先前存在，则更新缓存;如果不存在，则将方法的返回值存入缓存
    @CachePut(cacheNames = "user", key = "#user.id")
    public User update(User user) {
        userMapper.updateById(user);
        // 新生成key的加入布隆过滤器，此key从此合法,因为该更新方法并不更新id,所以也不会产生新的合法的key
        bloomFilter.add(user.getId());
        return user;
    }

    @CachePut(cacheNames = "user", key = "#user.id")
    public User insert(User user) {
        userMapper.insert(user);
        // 新生成key的加入布隆过滤器，此key从此合法
        bloomFilter.add(user.getId());
        return user;
    }
}

创建表sql

CREATE TABLE `user`  (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `user_name` varchar(255) CHARACTER SET utf8 COLLATE utf8_bin NULL DEFAULT NULL COMMENT '用户名',
  `sex` tinyint(1) NULL DEFAULT NULL COMMENT '0 男 1 女',
  `age` int(11) NULL DEFAULT NULL COMMENT '年龄',
  PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB AUTO_INCREMENT = 104 CHARACTER SET = utf8 COLLATE = utf8_bin ROW_FORMAT = DYNAMIC;

SET FOREIGN_KEY_CHECKS = 1;

秒客网

布隆过滤器介绍及原理、集成Redisson布隆过滤器解决Redis缓存穿透问题

布隆过滤器

1 什么是布隆过滤器

优缺点

2 布隆过滤器的作用

缓存穿透攻击

3 布隆过滤器的基本原理

4. 减少布隆过滤器误判的措施

5 布隆过滤器再项目中使用流程

6 布隆过滤器中内容被删除了怎么办？

7 在Spring Boot中集成Redisson实现布隆过滤器

7.1 添加redisson依赖

7.2 配置yml

7.3 配置RedissonConfig

7.4 工具类BloomFilterUtil

7.5 编写service实现层

创建表sql

相关文章