一、布隆过滤器介绍

1、什么是布隆过滤器

布隆过滤器（英语：Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为O(n),O(logN),O(1)。

这个时候，布隆过滤器（Bloom Filter）就应运而生。

2、布隆过滤器实现原理

如果想判断一个元素是不是在一个集合中，一般想到的方法是暂存数据，然后查找判定是否存在集合中。这种方法在数据量比较小的情况下适用，但是几个中元素较多的时候，检索速度就会越来越慢。

可以利用Bitmap：只要检查对应点是不是1就可以知道集合中有没有这个数。Bloom filter可以看做是对bitmap的扩展，只是使用多个hash映射函数，从而减低hash发生冲突的概率。

算法如下:

BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数组成的。

1. 在初始状态时，对于长度为 m 的位数组，它的所有位都被置为0；
2. 当有变量被加入集合时，通过 K 个映射函数将这个变量映射成位图中的 K 个点，把它们置为 1；
3. 查询某个变量是否存在的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了。

• 如果这些点有任何一个 0，则被查询变量一定不在；
• 如果都是 1，则被查询变量很可能存在。
  为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。

3、误判率

这里的误判率是指，BloomFilter 判断某个 key 存在，但它实际不存在的概率。

布隆过滤器的误判是由于多个输入经过哈希之后在相同的bit位 置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。

散列函数本身就是会出现碰撞，尽管布隆过滤器中会采用多重hash计算降低冲突概率，但还是无法完全避免，这样就导致一个对象经过多重hash计算的bit位可能和其他对象的bit位重合，如果一个新对象的bit位都被存入其他对象时置为1，那么就会出现误判。

这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。

布隆过滤器误判图解：
1、初始状态：布隆过滤器中的bit数组都为0；
2、向布隆过滤器中添加对象X和对象Y，分别经过多重hash计算后，将bit数组中的1,2,4,5,7位置填充为1；
3、当用布隆过滤器判断对象Z是否存在时，先对对象Z进行多重hash计算，对应bit位为4,5,7，而4,5,7刚好已经被对象X和对象Y填充为1，这时就会误判对象Z已经存在。
4、极限情况下当bit数组中的bit位全部被置为1，那么布隆过滤器将会失效。

特性:

• 一个元素如果判断结果为存在的时候元素不一定存在，但是判断结果为不存在的时候则一定不存在。
• 布隆过滤器可以添加元素，但是不能删除元素，因为删掉元素会导致误判率增加。

怎么降低误判率？

1. 增加散列函数个数，减少bit位冲突的可能；
2. 增加Bitmap的大小，避免bit位大量覆盖填充。

4、布隆过滤器使用场景

布隆过滤器的典型应用有：

• 数据库防止穿库, Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter来减少不存在的行或列的磁盘查找。避免代价高昂的磁盘查找会大大提高数据库查询操作的性能。
• 业务场景中判断用户是否阅读过某视频或文章，比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容。
• 缓存宕机、缓存击穿场景，一般判断用户是否在缓存中，如果在则直接返回结果，不在则查询db，如果来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则穿透到db。如果不在布隆器中，则直接返回。
• WEB拦截器，如果相同请求则拦截，防止重复被攻击。用户第一次请求，将请求参数放入布隆过滤器中，当第二次请求时，先判断请求参数是否被布隆过滤器命中。可以提高缓存命中率。
• Squid 网页代理缓存服务器在 cache digests 中就使用了布隆过滤器。Google Chrome浏览器使用了布隆过滤器加速安全浏览服务

总的来说，布隆过滤器是用于大数据场景下的重复判断，并且允许有一定误差存在,最典型的使用是解决缓存穿透问题。

5、哈希表与布隆过滤器比较

哈希表也能用于判断元素是否在集合中，但是Bloom Filter只需要哈希表的1/8或1/4的空间复杂度就能完成同样的问题。
哈希表是将真实的元素存放到集合中，而Bloom Filter只是根据元素的多重hash计算结果填充二进制数组，并不存放真正的对象。

Bloom Filter可以插入元素，但是不可以删除已有元素。集合中的元素越多，误报率越大，但是不会漏报。

二、redis中布隆过滤器实战

“纸上谈来终觉浅，绝知此事要躬行”，接下来让我们实战下如何通过布隆过滤器避免订单信息查询的缓存穿透问题。

1.引入redisson依赖

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

2.创建订单表

CREATE TABLE `tb_order` (
  `id` bigint NOT NULL AUTO_INCREMENT COMMENT '订单Id',
  `order_desc` varchar(50) NOT NULL COMMENT '订单描述',
  `user_id` bigint NOT NULL COMMENT '用户Id',
  `product_id` bigint NOT NULL COMMENT '商品Id',
  `product_num` int NOT NULL COMMENT '商品数量',
  `total_account` decimal(10,2) NOT NULL COMMENT '订单金额',
  `create_time` datetime NOT NULL COMMENT '创建时间',
  PRIMARY KEY (`id`),
  KEY `ik_user_id` (`user_id`)
) ENGINE=InnoDB AUTO_INCREMENT=51 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;

3.配置redis

新增redis连接属性：

spring.redis.host=192.168.206.129
spring.redis.port=6379
spring.redis.password=123456

配置redisTemplate，主要是设置序列化策略Jackson

@Configuration
public class RedisConfig {

    @Bean
    public RedisTemplate<String, Object> redisTemplate(RedissonConnectionFactory redisConnectionFactory) {
        //设置序列化
        Jackson2JsonRedisSerializer jackson2JsonRedisSerializer = new Jackson2JsonRedisSerializer(Object.class);
        ObjectMapper om = new ObjectMapper();
        om.setVisibility(PropertyAccessor.ALL, JsonAutoDetect.Visibility.ANY);
        //反序列化，该设置不能省略，不然从redis获取json转为实体时会报错
        om.activateDefaultTyping(LaissezFaireSubTypeValidator.instance,
                ObjectMapper.DefaultTyping.NON_FINAL,
                JsonTypeInfo.As.WRAPPER_ARRAY);
        jackson2JsonRedisSerializer.setObjectMapper(om);
        //配置redisTemplate
        RedisTemplate<String, Object> redisTemplate = new RedisTemplate<String, Object>();
        redisTemplate.setConnectionFactory(redisConnectionFactory);
        RedisSerializer stringSerializer = new StringRedisSerializer();
        //key序列化
        redisTemplate.setKeySerializer(stringSerializer);
        //value序列化
        redisTemplate.setValueSerializer(jackson2JsonRedisSerializer);
        return redisTemplate;
    }

}

4.配置BloomFilter

/**
 * 配置布隆过滤器
 */
@Configuration
public class BloomFilterConfig {
    @Autowired
    private RedissonClient redissonClient;
    /**
     * 创建订单号布隆过滤器
     * @return
     */
    @Bean
    public RBloomFilter<Long> orderBloomFilter() {
        //过滤器名称
        String filterName = "orderBloomFilter";
        // 预期插入数量
        long expectedInsertions = 10000L;
        // 错误比率
        double falseProbability = 0.01;
        RBloomFilter<Long> bloomFilter = redissonClient.getBloomFilter(filterName);
        bloomFilter.tryInit(expectedInsertions, falseProbability);
        return bloomFilter;
    }
}

5.创建订单

redisson中的BloomFilter有2个核心方法：

• bloomFilter.add(orderId) 向布隆过滤器中添加id
• bloomFilter.contains(orderId) 判断id是否存在

@Slf4j
@Service
public class OrderServiceImpl implements OrderService {

    @Resource
    private RBloomFilter<Long> orderBloomFilter;

    @Resource
    private TbOrderMapper  tbOrderMapper;

    @Resource
    private RedisTemplate<String,Object> redisTemplate;


    @Override
    public void createOrder(TbOrder tbOrder) {
        //1、创建订单
        tbOrderMapper.insert(tbOrder);

        //2、订单id保存到布隆过滤器
        log.info("布隆过滤器中添加订单号：{}",tbOrder.getId());
        orderBloomFilter.add(tbOrder.getId());
    }

    @Override
    public TbOrder get(Long orderId) {
        TbOrder tbOrder = null;
        //1、根据布隆过滤器判断订单号是否存在
        if(orderBloomFilter.contains(orderId)){
            log.info("布隆过滤器判断订单号{}存在",orderId);
            String key = "order:"+orderId;
            //2、先查询缓存
            Object object = redisTemplate.opsForValue().get(key);
            if(object != null){
                log.info("命中缓存");
                tbOrder =  (TbOrder)object;
            }else{
                //3、缓存不存在则查询数据库
                log.info("未命中缓存，查询数据库");
                tbOrder = tbOrderMapper.selectById(orderId);
                redisTemplate.opsForValue().set(key,tbOrder);
            }
        }else{
            log.info("判定订单号{}不存在,不进行查询",orderId);
        }
        return tbOrder;
    }
}

6.单元测试

    @Test
    public void testCreateOrder() {
        for (int i = 0; i < 50; i++) {
            TbOrder tbOrder = new TbOrder();
            tbOrder.setOrderDesc("测试订单"+(i+1));
            tbOrder.setUserId(1958L);
            tbOrder.setProductId(102589L);
            tbOrder.setProductNum(5);
            tbOrder.setTotalAccount(new BigDecimal("300"));
            tbOrder.setCreateTime(new Date());
            orderService.createOrder(tbOrder);
        }
    }

    @Test
    public void testGetOrder() {
        TbOrder  tbOrder = orderService.get(25L);
        log.info("查询结果：{}", tbOrder.toString());
    }

总结

布隆过滤器的原理其实非常简单，就是bitmap + 多重hash，主要优势就是利用非常小的空间就可以实现在大规模数据下快速判断某一对象是否存在，缺点是存在误判的可能，但不会漏判，也就是存在的对象一定会判断为存在，而不存在的对象会有较低的概率为误判为存在，且不支持对象的删除，因为会增加误判的概率。最典型的使用是解决缓存穿透的问题。