憨憨在减肥的博客

流水要争先，争的是滔滔不绝。

0%

SpringBoot-Redis-Bloom

发表于 更新于 分类于
本文字数： 4.3k 阅读时长 ≈ 4 分钟

Redis 中不能直接使用布隆过滤器，Redis 4.0 版本之后提供的 modules（扩展模块）

布隆过滤器的原理

  • 数据结构使用一位的数组，每次存储键值的时候，不是直接把数据存储在数据结构中。而是经过hash运算。将此元素的 hash 值均匀的存储在位数组中。把这些位置设置成 1 就完成了添加操作。
  • 判断元素是否存在时，经过运算判断对应的位置是否为全部1即可。因此布隆过滤器查询此值存在时，此值不一定存在，但查询此值不存在时，此值一定不存在。
  • 但是存在一定的误差，并且当位数组存储值比较稀疏的时候，查询的准确率越高，而当位数组存储的值越来越多时，误差也会增大。

  • 空间占用
    • 布隆过滤器有两个参数，第一个是预计元素的数量n，第二个是误判率p。公式根据这两个输入得到两个输出，第一个输出是位数组的长度m，也就是需要的存储空间大小(bit)，第二个输出是hash函数的最佳数量k。hash函数的数量也会直接影响到误判率，最佳的数量会有最低的误判率。
  • 计算公式
1
2
k≈0.7*(m/n)    
p≈0.6185^(m/n)
  • 位数组m越长，误判率p就越低；
  • 位数组m越长，hash函数最佳数量k就越多，影响计算效率；

演示代码

安装Redis

演示情况直接使用docker来安装，免去下载编译过程。

1
docker run -p 6379:6379 -d redislabs/rebloom:latest
  • 使用redis-cli或者客户端工具进入
1
2
3
4
5
6
➜  docker-run redis-cli 
127.0.0.1:6379> bf.add 1 1
(integer) 0
127.0.0.1:6379> bf.add 1 2
(integer) 1
127.0.0.1:6379>
  • 如果没有提示错误则表示安装成功。

Bloom基础用法

布隆过滤器的命令不是很多，主要包含以下几个

  • bf.add：添加元素
  • bf.exists：判断某个元素是否存在
  • bf.madd：添加多个元素
  • bf.mexists：判断多个元素是否存在
  • bf.reserve：设置布隆过滤器的准确率 只能在未设置数据的时候设置，否则会报错
1
2
3
4
5
6
7
8
127.0.0.1:6379> bf.exists 1 1
(integer) 1
127.0.0.1:6379> bf.exists 1 2
(integer) 1
127.0.0.1:6379> bf.reserve 1 0.01 100 # 已经存在集合在设置会报错
(error) ERR item exists
127.0.0.1:6379> bf.reserve user 0.01 100 # 未设置数据的则可以正常设置。
OK

SprngBoot演示

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
/**
 * @author z201.coding@gmail.com
 **/
@Component
@Slf4j
public class BloomTool {


    @Autowired
    private RedisTemplate redisTemplate;

    /**
     * 初始化
     *
     * @param key
     * @param rate 准确度
     * @param size 大小
     */
    public Boolean init(String key, String rate, String size) {
        try {
            String script = "return redis.call('bf.reserve', KEYS[1], ARGV[1], ARGV[2])";
            DefaultRedisScript<String> defaultRedisScript = new DefaultRedisScript<String>();
            defaultRedisScript.setResultType(String.class);
            defaultRedisScript.setScriptSource(new StaticScriptSource(script));
            String[] argv = new String[]{rate,size};
            String result = (String) redisTemplate.execute(defaultRedisScript, Collections.singletonList(key), argv);
            if (Objects.equals(result, "OK")) {
                return true;
            }
        }catch (RedisSystemException redisSystemException){
            log.error("{}",redisSystemException.getMessage());
        }
        return false;
    }

    /**
     * 添加元素
     *
     * @param key
     * @param value
     */
    public Boolean add(String key, String value) {
        String script = "return redis.call('bf.add', KEYS[1], ARGV[1])";
        return lua(script, key, value);
    }

    /**
     * 是否存在
     *
     * @param key
     * @param value
     * @return
     */
    public Boolean exists(String key, Object value) {
        String script = "return redis.call('bf.exists', KEYS[1], ARGV[1])";
        return lua(script, key, value);
    }

    private Boolean lua(String script, String key, Object value) {
        DefaultRedisScript<Long> defaultRedisScript = new DefaultRedisScript<Long>();
        defaultRedisScript.setResultType(Long.class);
        defaultRedisScript.setScriptSource(new StaticScriptSource(script));
        Long result = (Long) redisTemplate.execute(defaultRedisScript, Collections.singletonList(key), value);
        if (Objects.equals(result, 1L)) {
            return true;
        }
        return false;
    }

}
  • 单元测试
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
package cn.z201.redis;

@Slf4j
@ExtendWith(SpringExtension.class)
@SpringBootTest(classes = AppApplication.class, webEnvironment = SpringBootTest.WebEnvironment.RANDOM_PORT)
@AutoConfigureMockMvc
// 指定单元测试方法顺序
@TestMethodOrder(MethodOrderer.OrderAnnotation.class)
public class AppApplicationTest {

    @Autowired
    BloomTool bloomTool;

    @Autowired
    RedisTemplate redisTemplate;

    @Test
    @Disabled
    public void testBloom() {
        Set<String> keys =  redisTemplate.keys("*");
        log.info("{}",keys);
        redisTemplate.delete(keys);
        String key = "u";
        log.info("init 异常或者错误都会报错 {}", bloomTool.init(key, "0.001", "10000000"));
        List<String> values = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            Integer value = RandomUtil.randomInt(1000, 20000000);
            values.add(value.toString());
            Boolean result =  bloomTool.add(key, value.toString());
            log.info("bf.add {} {} {} ", result, key, value);
        }
        Integer index = RandomUtil.randomInt(0, values.size());
        String value = values.get(index);
        Boolean result = bloomTool.exists(key, value);
        log.info("bf.exists {} {} {} ", result, key, value);
    }

}
  • Console
1
2
3
4
5
6
7
8
9
10
11
12
13
[main]  [u]
[main]  init 异常或者错误都会报错 true
[main]  bf.add true u 11569209 
[main]  bf.add true u 12786658 
[main]  bf.add true u 16272560 
[main]  bf.add true u 1212058 
[main]  bf.add true u 4896410 
[main]  bf.add true u 15218411 
[main]  bf.add true u 13349975 
[main]  bf.add true u 12544373 
[main]  bf.add true u 4507958 
[main]  bf.add true u 12143750 
[main]  bf.exists true u 1212058

END