布隆过滤器 redis

一.为什么要用到布隆过滤器？

缓存穿透：查询一条不存在的数据，缓存中没有，则每次请求都打到数据库中，导致数据库瞬时请求压力过大，多见于爬虫恶性攻击

因为布隆过滤器是二进制的数组，如果使用了它，可以把需要的对应的全量业务数据的key值全放到布隆过滤器中，内存占用较小，这样就不会击穿数据库
1
2
3

二.数据访问流程

布隆过滤器–>redis缓存–>数据库

三.原理：

使用二进制数组，对要存入的key进行多次hash，分配到数组的不同位置，数组的值从0改成1，查询的时候也进行多次hash，命中到数组的位置的值都是1则key可能存在，如果有一个不是1则key一定不存在

四.缺点

缺点1：

存在误判的情况，比如：hello和你好经过hash后的值一样，出现hash冲突。比如“你好”是存在，“hello”不存在，但他们的hash值一样，就会通过

解决：

1.根据数据量大小设置误判率。误判率越小，使用的hash函数越多，hash冲突越小，但计算的时间增加，内存占用更多
2.增大布隆过滤器数组

缺点2：

删除困难： 布隆过滤器无法直接删除已添加的元素，因为删除操作会影响其他元素的判断结果。在删除元素时，可能会导致一些位置的位被置为 0，从而影响其他元素的判断结果，增加误判的概率

解决：

只能是重新载入布隆过滤器了。开发定时任务，每隔几个小时，自动创建一个新的布隆过滤器数组替换老的。注意，是几小时，这也就意味着，这一方法在高并发的情况下有巨大缺点

五.代码实践

        <dependency>
            <groupId>org.redisson</groupId>
            <artifactId>redisson-spring-boot-starter</artifactId>
            <version>3.27.2</version>
        </dependency>
1
2
3
4
5

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
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;

/**
 * redisson客户端使用Bloom过滤器拦截无效请求，解决缓存穿透
 * 项目初始化的时候初始化布隆过滤器(例如把商品编号都放进去)，
 * 用户发过来的请求(带商品编号)先经过布隆过滤器过滤，过滤掉的返回null
 *
 */
@Configuration
public class RedissinConfig {


   @Value("${redisson.address}")
   private String addressUrl;


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


    @Bean
    public RedissonClient redissonClient() {
    Config config = new Config();
    config.useSingleServer()
    .setAddress(addressUrl)
    .setRetryInterval(5000)
    .setTimeout(10000)
    .setDatabase(0)
    .setPassword(password)
    .setConnectTimeout(10000);
    return Redisson.create(config);
    }

    /**
     * 可以不注册成bean，直接使用redissonClient来创建Bloom过滤器
     * @param redissonClient
     * @return
     */
   @Bean
   public RBloomFilter<String> bloomFilter(RedissonClient redissonClient) {
      RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter("bloom");
      bloomFilter.tryInit(1000000L, 0.01);
      return bloomFilter;
   }

}
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
43
44
45
46
47
48
49
50
51
52

import lombok.extern.slf4j.Slf4j;
import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.test.context.junit4.SpringRunner;

@RunWith(SpringRunner.class)
@SpringBootTest(classes = DataApplication.class)
@Slf4j
public class BloomTest {

    @Autowired
    private RedissonClient redissonClient;

    RBloomFilter<String> bloomFilter;

    @Before
    public void init()
    {
        bloomFilter = redissonClient.getBloomFilter("bloom");
        bloomFilter.tryInit(10000L, 0.01);
    }

    /**
     * 测试耗时和误判率
     */
    @Test
    public void test()
    {
        long start = System.currentTimeMillis();

        int total=10000;
        for (int i = 0; i < total; i++)
        {
            bloomFilter.add(String.valueOf(i));
        }
        long end= System.currentTimeMillis();
        log.info("插入用时:{}",end-start);
        int count = 0;
        for (int i = total; i < total+1000; i++)
        {
            if(bloomFilter.contains(String.valueOf(i))){
                count++;
                log.info("误判了:{}",i);
            }
        }
        log.info("插入用时:{}",System.currentTimeMillis()-end);
        log.info("count为:{},误判率:{}",count,(count*1.0/1000));
    }

    /**
     * 获取count
     */
    @Test
    public void countBloomTest()
    {

        long count = bloomFilter.count();
        log.info("count为:{}",count);
    }

    /**
     * 删除过滤器
     */
    @Test
    public void delBloomTest()
    {
        bloomFilter.delete();
    }


}
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

1万的数据插入差不多用了4分钟，查询1000个数据用了24秒

在redis可视化中看到的数据如下

六.源码解析

布隆过滤器初始化源码，保存的信息（size，hashIterations，expectedInsertions，falseProbability），跟上图匹配，计算位数组大小和哈希个数是数学计算公式

参考：
https://zhuanlan.zhihu.com/p/622044226