细谈布隆过滤器及Redis实现

2021/8/19 19:07:56

本文主要是介绍细谈布隆过滤器及Redis实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

 何为布隆过滤器?

本质上是一种数据结构,是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



这篇关于细谈布隆过滤器及Redis实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程