SpringBoot redis系列 -布隆过滤器（4）
背景
给用户推荐文章阅读，需要知道用户有没有看过该文章，看过了不需要再次推荐，如何去去重呢，TyperLogLog是可以做到去重，但是它无法知道某个用户是否看过了，如果把看过的用户和文章写到一个Set集合，那随着业务增长，带来的内存开销是巨大的，这个时候布隆过滤器的作用就出来了。它就是用来处理这种去重问题的，它去重的同时还能节约90%的空间，只是它不是那么精准，存在一点误差，像推荐的业务，我们平时刷抖音，今日头条也会碰到推荐了重复的，所以我猜测他们的推荐可能也是基于布隆过滤器。
ps：不同的数据结构有不同的适用场景和优缺点，你需要仔细权衡自己的需求之后妥善适用它们，布隆过滤器就是践行这句话的代表。如果知道业务的走向，无法到达膨大的用户量，其实也没必要使用复杂的结构
使用场景
正文
布隆过滤器简介
布隆过滤器可以理解为一个不怎么精准的Set集合，使用contains 方法判断某个对象是否存在，可能会存在误判的情况，但是只要参数设置合理，精确度可以控制到相对足够精确，只会有小小的误判。
布隆过滤器只会误判没有见过的元素，不会误判见过的元素，因为可能跟它见过的元素比较像。
Redis中布隆过滤器在Redis4.0提供了插件功能之后才正式出现，要安装布隆过滤器插件才可以用，直接用docker装了一个，并且给他设置密码，我开始没有设置密码，结果第二天就中了挖矿程序，建议大家服务器上的Redis对公网开放端口的设置一个密码
1
| docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
|
布隆过滤器基本指令：
bf.add 添加元素
bf.exists元素是否存在
bf.madd 添加多个元素
bf.mexists 多个元素是否存在
返回1代表存在 0代表不存在
使用bf.add 命令会创建一个默认的布隆过滤器，它的精确度可能不是那么好，我们通过调参使它的精确度提高。使用bf.reserve在add之前创建，它有三个参数，分别是key, error_rate和initial_size，错误率error_rate越低，需要的空间越大，initial_size表示预计放入的元素数量，当超出这个数量时，误判率会上升。默认值error_rate：0.01 initial_size：100
注意：initial_size过大会浪费内存，过大会正确率变低，在使用之前一定要估计用户量，加上一定的冗余空间避免低估。
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
|
**原理简介：**
布隆过滤器组成就是一个大型的位数组和几个不一样的无偏Hash函数，无偏就是能把hash算的比较均匀。
hash算法是可能不同key重复的，所以采用多个hash函数。添加key时，会用多个Hash函数对key进行Hash计算一个整数索引，多个hash函数就会有多个索引，把这个这些索引上的值都设置成1，判断是否存在时，判断这些索引上的值是否都是1，如果都是1，就认为存在，这样避免了Hash重复。
### SpringBoot 中使用布隆过滤器
找了下文档，似乎SpringBoot Data Redis 并未对布隆过滤器支持，参考Redis官网的介绍，我们给其增加对布隆过滤器的支持。
redis 官方布隆过滤器介绍：
https://oss.redislabs.com/redisbloom/
redis bloom java sdk：
https://github.com/RedisBloom/JRedisBloom
我们先观察下Redis **RedisTemplate.opsForValue()** 的操作String实现，模仿它写一个布隆过滤器操作，进入方法内部。
```java
public ValueOperations<K, V> opsForValue() {
return this.valueOps;
}
|
ValueOperations 是一个接口，定义了操作string的一些常用命令，如 set get等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public interface ValueOperations<K, V> {
void set(K var1, V var2);
void set(K var1, V var2, long var3, TimeUnit var5);
default void set(K key, V value, Duration timeout) {
Assert.notNull(timeout, "Timeout must not be null!");
if (TimeoutUtils.hasMillis(timeout)) {
this.set(key, value, timeout.toMillis(), TimeUnit.MILLISECONDS);
} else {
this.set(key, value, timeout.getSeconds(), TimeUnit.SECONDS);
}
}
}
|
我们顺腾摸瓜，看看它的实现，有个默认的实现DefaultValueOperations，可以看到它集成于AbstractOperations抽象类，提供了一系列方法，如获取RedisTemplate配置，序列化key，value等。
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
| package org.springframework.data.redis.core;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;
import org.springframework.data.geo.GeoResults;
import org.springframework.data.redis.connection.DefaultTuple;
import org.springframework.data.redis.connection.RedisConnection;
import org.springframework.data.redis.connection.RedisGeoCommands.GeoLocation;
import org.springframework.data.redis.connection.RedisZSetCommands.Tuple;
import org.springframework.data.redis.connection.convert.Converters;
import org.springframework.data.redis.core.ZSetOperations.TypedTuple;
import org.springframework.data.redis.serializer.RedisSerializer;
import org.springframework.data.redis.serializer.SerializationUtils;
import org.springframework.lang.Nullable;
import org.springframework.util.Assert;
import org.springframework.util.CollectionUtils;
abstract class AbstractOperations<K, V> {
abstract class ValueDeserializingRedisCallback implements RedisCallback<V> {
private Object key;
public ValueDeserializingRedisCallback(Object key) {
this.key = key;
}
public final V doInRedis(RedisConnection connection) {
byte[] result = this.inRedis(AbstractOperations.this.rawKey(this.key), connection);
return AbstractOperations.this.deserializeValue(result);
}
@Nullable
protected abstract byte[] inRedis(byte[] var1, RedisConnection var2);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| class DefaultValueOperations<K, V> extends AbstractOperations<K, V> implements ValueOperations<K, V> {
DefaultValueOperations(RedisTemplate<K, V> template) {
super(template);
}
public V get(Object key) {
return this.execute(new AbstractOperations<K, V>.ValueDeserializingRedisCallback(key) {
protected byte[] inRedis(byte[] rawKey, RedisConnection connection) {
return connection.get(rawKey);
}
}, true);
}
|
追了一下get方法，execute继承于AbstractOperations，调用了RedisTemplate的方法，并传入了回调类，这个方法主要就是根据配置获取一个RedisConnection 实例执行命令。
1
2
3
4
| @Nullable
<T> T execute(RedisCallback<T> callback, boolean exposeConnection) {
return this.template.execute(callback, exposeConnection);
}
|
拿到回调之后就开始执行命令了， connection.set 方法就是在执行指令，我们追源码发现RedisConnection继承于RedisCommands,它提供了执行命令的操作。就是它了，用它来执行就命令就ok了。具体Redistemplate原理可以参考：https://blog.csdn.net/junchenbb0430/article/details/51104335
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| protected byte[] inRedis(byte[] rawKey, RedisConnection connection) {
connection.set(rawKey, rawValue);
return null;
}
public interface RedisConnection extends RedisCommands {
default RedisGeoCommands geoCommands() {
return this;
}
public interface RedisCommands extends RedisKeyCommands,...{
@Nullable
Object execute(String var1, byte[]... var2);
}
|
我们根据套路，先创建BloomOperations定义操作方法，DefaultBloomOperations实现，封装一个常量存放关键字命令。注意：AbstractOperations使用默认修饰符，也就是说同包下面才能访问，所以我们的包名必须跟它一致，org.springframework.data.redis.core
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| package org.springframework.data.redis.core;
import lombok.AllArgsConstructor;
import lombok.Getter;
@Getter
@AllArgsConstructor
public enum BloomCommand {
RESERVE("BF.RESERVE"),
ADD("BF.ADD"),
MADD("BF.MADD"),
EXISTS("BF.EXISTS"),
MEXISTS("BF.MEXISTS");
private String command;
}
|
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
| package org.springframework.data.redis.core;
public interface BloomOperations<K, V> {
void createFilter(K key, double errorRate, long initCapacity);
Boolean add(K key, V value);
Boolean[] addMulti(K key, V... values);
Boolean exists(K key, V value);
Boolean[] existsMulti(K key, V... values);
Boolean delete(K key);
}
|
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
77
78
79
| package org.springframework.data.redis.core;
import java.util.List;
import java.util.Objects;
class DefaultBloomOperations<K, V> extends AbstractOperations<K, V> implements BloomOperations<K, V> {
public DefaultBloomOperations(RedisTemplate<K, V> template) {
super(template);
}
@Override
public void createFilter(K key, double errorRate, long initCapacity) {
byte[] rawKey = rawKey(key);
byte[] rawErrorRate = rawString(String.valueOf(errorRate));
byte[] rawInitCapacity = rawString(String.valueOf(initCapacity));
this.execute(connection -> {
connection.execute(BloomCommand.RESERVE.getCommand(), rawKey, rawErrorRate, rawInitCapacity);
return null;
}, true);
}
@Override
public Boolean add(K key, V value) {
byte[] rawKey = rawKey(key);
byte[] rawValue = rawValue(value);
return this.execute(connection -> {
Long l = (Long) connection.execute(BloomCommand.ADD.getCommand(), rawKey, rawValue);
return Objects.equals(l, 1L);
}, true);
}
@Override
public Boolean[] addMulti(K key, V... values) {
byte[][] rawArgs = rawArgs(key, values);
return this.execute(connection -> {
List<Long> ls = (List<Long>) connection.execute(BloomCommand.MADD.getCommand(), rawArgs);
return ls.stream().map(l -> Objects.equals(l, 1L)).toArray(Boolean[]::new);
}, true);
}
@Override
public Boolean exists(K key, V value) {
byte[] rawKey = rawKey(key);
byte[] rawValue = rawValue(value);
return this.execute(connection -> {
Long l = (Long) connection.execute(BloomCommand.EXISTS.getCommand(), rawKey, rawValue);
return Objects.equals(l, 1L);
}, true);
}
@Override
public Boolean[] existsMulti(K key, V... values) {
byte[][] rawArgs = rawArgs(key, values);
return this.execute(connection -> {
List<Long> ls = (List<Long>) connection.execute(BloomCommand.MEXISTS.getCommand(), rawArgs);
return ls.stream().map(l -> Objects.equals(l, 1L)).toArray(Boolean[]::new);
}, true);
}
@Override
public Boolean delete(K key) {
return template.delete(key);
}
private byte[][] rawArgs(Object key, Object... values) {
byte[][] rawArgs = new byte[1 + values.length][];
int i = 0;
rawArgs[i++] = rawKey(key);
for (Object value : values) {
rawArgs[i++] = rawValue(value);
}
return rawArgs;
}
}
|
最后发现SpringBoot2使用的是lettuce，它没有对布隆过滤器的支持，所以改用Jedis
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| <dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-data-redis</artifactId>
<exclusions>
<exclusion>
<groupId>io.lettuce</groupId>
<artifactId>lettuce-core</artifactId>
</exclusion>
</exclusions>
</dependency>
<dependency>
<groupId>org.springframework.data</groupId>
<artifactId>spring-data-redis-bloom-filter</artifactId>
<version>1.0.0-SNAPSHOT</version>
</dependency>
<dependency>
<groupId>redis.clients</groupId>
<artifactId>jedis</artifactId>
<version>3.2.0</version>
</dependency>
|
最后开始测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| @Slf4j
@SpringBootTest
public class BloomFilterTests {
@Autowired
BloomOperations bloomOperations;
@Test
public void test() {
bloomOperations.createFilter("bloom_filter", 0.1, 2000);
for (int i = 1; i < 200; i++) {
bloomOperations.add("bloom_filter", String.valueOf(i));
}
bloomOperations.addMulti("bloom_filter", "2000", "2001", "2003");
log.info("{}是否存在：{}", 2000, bloomOperations.exists("bloom_filter", "2000"));
log.info("{}是否存在：{}", 20005, bloomOperations.exists("bloom_filter", "20005"));
log.info("{}是否存在：{}", 20005 + "" + 2001, bloomOperations.existsMulti("bloom_filter", "20005", "2001"));
}
}
|
总结
布隆过滤器使用起来有点麻烦，不过效果还是很香的，它是一个逻辑存在的结构，在很多NoSQl数据库中都有应用。
以上内容个人学习总结，部分内容来源于网上，欢迎各位大佬指点。
代码连接地址：https://github.com/smalljop/my-blog-java-project
