Redis使用布隆过滤器_redis bloom 过滤器下载

---

前言

---

一、使用场景

（1）redis防止缓存击穿的解决方案
（2）数据去重
（3）过滤垃圾信息(邮件，短信)

二、实现原理

  布隆过滤器（Bloom Filter）是一个高空间利用率的概率性数据结构，由二进制向量（即位数组）和一系列随机映射函数（即哈希函数）两部分组成。

  布隆过滤器使用exists()来判断某个元素是否存在于自身结构中。当布隆过滤器判定某个值存在时，其实这个值只是有可能存在；当它说某个值不存在时，那这个值肯定不存在，这个误判概率大约在 1% 左右。

1、工作流程-添加元素

布隆过滤器主要由位数组和一系列 hash 函数构成，其中位数组的初始状态都为 0。

如下图所示：

  当使用布隆过滤器添加 key 时，会使用不同的 hash 函数对 key 存储的元素值进行哈希计算，从而会得到多个哈希值。根据哈希值计算出一个整数索引值，将该索引值与位数组长度做取余运算，最终得到一个位数组位置，并将该位置的值变为 1。每个 hash 函数都会计算出一个不同的位置，然后把数组中与之对应的位置变为 1。通过上述过程就完成了元素添加(add)操作。

2、工作流程-判定元素是否存在

  当我们需要判断一个元素是否存时，其流程如下：首先对给定元素再次执行哈希计算，得到与添加元素时相同的位数组位置，判断所得位置是否都为1，如果其中有一个为0，那么说明元素不存在，若都为1，则说明元素有可能存在。

布隆过滤器判断存在不一定真的存在，但是，判断不存在则一定不存在。

3、为什么是可能“存在”

  您可能会问，为什么是有可能存在？其实原因很简单，那些被置为 1 的位置也可能是由于其他元素的操作而改变的。比如，元素1 和 元素2，这两个元素同时将一个位置变为了 1（如上图所示）。在这种情况下，我们就不能判定“元素 1”一定存在，这是布隆过滤器存在误判的根本原因。

  Bloom Filter 中，误判的概率和位数组的大小有很大关系，位数组越大，误判概率越小，当然占用的存储空间越大；位数组越小，误判概率越大，当然占用的存储空间就小

三、如何使用

1、下载布隆过滤器

布隆过滤器是GitHub上的开源项目（布隆过滤器开源地址）我们先访问这个地址去找到适合自己版本的布隆过滤器。
这种方法就不做演示了，有需要的可以去源码查看下载。

---

2、使用谷歌Guava依赖实现

依赖

        <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>30.0-jre</version>
        </dependency>
1
2
3
4
5

Demo示例：

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

import java.math.BigDecimal;

/**
 * @ClassName: Test2
 * @Author : le
 * @Date :2023/4/23 0023  11:28
 * @Description: TODO
 * @Version :1.0
 */
public class Test2 {
    public static void main(String[] args) {
        // 开始时间
        long startTime = System.currentTimeMillis();
        // 初始化误判个数
        BigDecimal count = new BigDecimal("0");
        // 相当于一个常量
        BigDecimal number = new BigDecimal("1");
        // 测试的10W个数据 也是常量 用于计算误判率
        BigDecimal testCount = new BigDecimal("1000000");
        // 百分比换算，还是常量
        BigDecimal percentage = new BigDecimal("100");
        // 第一个参数为数据类型，第二个数组长度，第三个误判率
        BloomFilter<Integer>bloomFilter=BloomFilter.create(Funnels.integerFunnel(),10000000L,0.01);
        for (int i = 0; i < 10000000; i++) {
            bloomFilter.put(i);
        }
        for (int i = 20000000; i < 21000000; i++) {
            boolean b = bloomFilter.mightContain(i);
            if(b){
                count=count.add(number);
            }
        }
        //测试100个不存在的数据；
        System.out.println("总耗时" + (System.currentTimeMillis() - startTime) + "MS");
        System.out.println("误判个数:" + count);
        System.out.println("误判率:" + (count.divide(testCount)).multiply(percentage) + "%");

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

结果：

总结：

  误判了10076个，在100W里面占比1%，符合我们设置的误判率。误判率不是越小越好，越小耗时也越长，因为误判率越小哈希次数越多，我们需要取一个合适的误判率，数据越大，误判率越大最好，个人观点。

使用在缓存穿透示列:

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.CommandLineRunner;
import org.springframework.context.annotation.Configuration;

import java.util.List;

/**
 * @ClassName: BlooInitConfig
 * @Author : le
 * @Date :2023/4/23 0023  11:43
 * @Description: TODO
 * @Version :1.0
 */
@Configuration
public class BloomInitConfig implements CommandLineRunner {
    //调用需要初始化数据的接口
    @Autowired
    private UserMapper userMapper;

    @Override
    public void run(String... args) throws Exception {
        this.bloomInit();
    }

    public BloomInitConfig bloomInit() {
        // 第一个参数为数据类型，第二个数组长度，第三个误判率
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), 10000000L, 0.01);
        //获取需要装入的数据
        List<User> list = userMapper.getBloolmList();
        //循环装入
        for (User user : list) {
            bloomFilter.put(user.getId());
        }
        //初始化完成
        return bloomInit();
    }
    //在用户接口的时候调用一个获取，传入user.id 调用boolean b = bloomFilter.mightContain(user.getId);来判断是否存在
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

3、使用redisson依赖实现

依赖：

        <dependency>
            <groupId>org.redisson</groupId>
            <artifactId>redisson</artifactId>
            <version>3.17.4</version>
        </dependency>
1
2
3
4
5

redis配置依赖加载配置

import org.redisson.Redisson;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

@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
    public RedissonClient getRedisson() {
        Config config = new Config();
        config.useSingleServer().setAddress("redis://" + host + ":" + port).setPassword(password);
        return Redisson.create(config);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

布隆过滤器初始化配置

import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

/**
 * @ClassName: BloomFilterConfig
 * @Author : le
 * @Date :2023/4/18 0018  15:33
 * @Description: TODO
 * @Version :1.0
 */
@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;
    }

}
//在调用类新增用redissonClient获取并且设置值进去，然后跟上面使用guava类型，都是判断用contains来判断是否存在。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

总结

  布隆过滤器也是有缺点的，比如存在误判，删除数据困难，只能一段时间重新删除再初始化，可以选择使用布谷鸟过滤器，各方面相对于布隆过滤器都有一些优化。