细谈布隆过滤器及Redis实现

2023-08-05 15:03:58

何为布隆过滤器？

本质上是一种数据结构，是1970年由布隆提出的。它实际上是一个很长的二进制向量(位图)和一系列随机映射函数（哈希函数）。可以用于检索一个元素是否在一个集合中。

数据结构：

布隆过滤器是一个 bit 向量或者说 bit 数组，就是一个二进制的数据，数据存放0或1。如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，

并对每个生成的哈希值指向的 bit 位置为 1。

布隆过滤器的日常使用

在日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）；新闻客户端的推送去重功能，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录；在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。

判断一个元素是否在集合中有很多方法，但是为啥会选择布隆过滤器呢？

将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。比如说，一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。如果用哈希表，每存储一亿个 email 地址，就需要 1.6GB 的内存（用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB，即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机，一般服务器是无法存储的[1]。

其实这也就是需要说的布隆过滤器相对其他方式的优点：

高效地插入和查询，相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少。

当然缺点也很明显，就是有一定的误算概率。

布隆过滤器还有个特点，不支持删除，也不是完全不能，可以通过特殊手段实现，但是较为复杂，这边也不做细说。复杂的数学公式我们就不说了，我想也没有几个想了解的。

说点实用的，布隆过滤器如何在Redis中解决缓存击穿的。

处理redis的缓存穿透有两种方式：

一、缓存层缓存空值

将数据库中的空值也缓存到缓存层中，这样查询该空值就不会再访问DB，而是直接在缓存层访问就行。

但是这样有个弊端就是缓存太多空值占用了更多的空间，可以通过给缓存层空值设立一个较短的过期时间来解决。

二、布隆过滤器

将所有查询条件放入布隆过滤器中，数据请求时，现在布隆过滤器中查询，如果有，则继续查询操作，如果没有，则直接舍弃。

那么就来说说布隆过滤器是如何实现redis缓存穿透优化的，这边举两种常用方式：

1、使用google的guava工具实现：

pom添加依赖

<dependency>
     <groupId>com.google.guava</groupId>
     <artifactId>guava</artifactId>
     <version>23.0</version>
</dependency>

demo代码

        //初始化布隆过滤器
        Long initLong = 1000000L;
        BloomFilter<Long> bl = BloomFilter.create(Funnels.longFunnel(), 10000000, 0.01);
        for(long l=0; l<initLong; l++){
            bl.put(l);
        }
        try {
            if(!bl.mightContain(userAccount)){
                System.out.println("数据不存在");
                return "error_code";//不存在的key为"stock"的直接返回
            }
             //下面是正常的redis操作，跟布隆过滤器没啥关系，可以忽略不看，测试key有所不同
            Integer stock = Integer.valueOf(stringRedisTemplate.opsForValue().get("stock"));
            if (stock > 0) {
                int realStock = stock - 1;
                stringRedisTemplate.opsForValue().set("stock", realStock + "");
                System.out.println("库存剩余：" + realStock);
            } else {
                System.out.println("库存不足！");
            }
        }finally {
            if(clientId.equals(stringRedisTemplate.opsForValue().get(lockKey))){
                stringRedisTemplate.delete(lockKey);
            }
        }

主要使用到create和put已经mightContain三个方法，实现起来是不是很容易呢。

2、使用redisson为我们封装好的方法

同样的引入依赖包

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>3.15.2</version>
</dependency>

代码demo简单实现：

redis的简单配置

@Configuration
public class RedissonConfig {

    @Value("${spring.redis.host}")
    private  String host;
    @Value("${spring.redis.port}")
    private  String port;
    @Bean
    public Redisson redisson(){
        Config config = new Config();
        config.useSingleServer().setAddress("redis://"+host+":"+port).setDatabase(0);
        return (Redisson) Redisson.create(config);
    }
}

布隆过滤器实现

@RequestMapping("/redisson/{userAccount}")
    public String redisson(Long userAccount){
        //模拟初始化布隆过滤器,可以不再局部内做
        Long initLong = 1000000L;
        BloomFilter<Long> bl = BloomFilter.create(Funnels.longFunnel(), 10000000, 0.01);
        for(long l=0; l<initLong; l++){
            bl.put(l);
        }
        if(!bl.mightContain(userAccount)){
            System.out.println("数据不存在");
            return "error_code";//不存在的key为"stock"的直接返回
        }
        String lockKey = "product_101";//分布式锁
        RLock lock = redisson.getLock(lockKey);
        try {
            lock.lock();
            //下面是正常的redis操作，跟布隆过滤器没啥关系，可以忽略不看，测试key有所不同
            Integer stock = Integer.valueOf(stringRedisTemplate.opsForValue().get("stock"));
            if (stock > 0) {
                int realStock = stock - 1;
                stringRedisTemplate.opsForValue().set("stock", realStock + "");
                System.out.println("库存剩余：" + realStock);
            } else {
                System.out.println("库存不足！");
            }
        }finally {
            lock.unlock();
        }
        return "end";
    }

总结：对于redis缓存穿透还有其他实现方式，常用的就是布隆过滤器，其原理其实就是这么简单，相信你们也都理解了，分享就这样吧。

参考文章：[1] https://www.cnblogs.com/liyulong1982/p/6013002.html

码农公寓

何为布隆过滤器？

相关文章