0%

SpringBoot-Redis-Bloom

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