Redis布隆过滤器
简介
布隆过滤器(Bloom Filter)是 1970 年由布隆提出的,是一种非常节省空间的概率数据结构,运行速度快,占用内存小,但是有一定的误判率且无法删除元素。它实际上是一个很长的二进制向量和一系列随机映射函数组成,主要用于判断一个元素是否在一个集合中。
Guava 中的布隆过滤器仅使用于单机环境,不使用于分布式环境,分布式环境
模块加载
1、点击https://redis.io/modules 找到RedisBloom。 实际地址:https://github.com/RedisBloom/RedisBloom
2、点击进去下载RedisBloom-master.zip文件,上传到linux
3、解压缩刚才的RedisBloom文件
unzip RedisBloom-master.zip
cd RedisBloom-master
#编译安装
make
#make完生成redisbloom.so,拷贝到redis的安装目录。
cp redisbloom.so /home/www/server/redis
4、在redis.conf
配置文件中加入RedisBloom
的redisbloom.so
文件的地址
loadmodule /home/www/server/redis/redisbloom.so
如果是集群则每个配置文件中都需要加入
redisbloom.so
文件的地址
5、或者在启动时指定 module。
redis-server redis.conf --loadmodule /home/www/server/redis/redisbloom.so
重启
Redis
,在本地和测试环境还可以,但是正式环境能不重启就不需要重启,那这么做可以不重启Redis,使用module load
命令执行。
MODULE LOAD /home/www/server/redis/redisbloom.so
module list
命令介绍
参考:https://redis.io/docs/data-types/probabilistic/bloom-filter/
创建BloomFilter
使用给定的期望错误率和初始容量创建空的布隆过滤器
BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion] [NONSCALING]
参数说明
- key:布隆过滤器的key
- error_rate:期望的错误率(False Positive Rate),该值必须介于0和1之间。该值越小,BloomFilter的内存占用量越大,CPU使用率越高
- capacity:布隆过滤器的初始容量,即期望添加到布隆过滤器中的元素的个数。当实际添加的元素个数超过该值时,布隆过滤器将进行自动的扩容,该过程会导致性能有所下降,下降的程度是随着元素个数的指数级增长而线性下降
- EXPANSION:元素超过capacity,扩展。即新容器的capacity是旧容器的capacity的多少倍。默认值是2.
- NONSCALING:元素超过capacity,不扩展。
返回值
- 成功:OK
- 其它情况返回相应的异常信息
增加元素
BF.ADD {key} {element}
BF.MADD {key} {element} {element} {element}
-
BF.ADD
返回值:- 元素不存在插入成功:返回1
- 元素可能已经存在:返回0
- 其它情况返回相应的异常信息
-
BF.MADD
返回值:- 成功:返回一个数组,数组的每一个元素可能为1或0,当item一定不存在时数组元素值为1,当item可能已经存在时数组元素值为0
- 其它情况返回相应的异常信息
判断是否存在
BF.EXISTS {key} {element}
BF.MEXISTS {key} {element} {element} {element}
BF.EXISTS
返回值:- 元素一定不存在:0
- 元素可能存在:1
- 其它情况返回相应的异常信息
BF.MEXISTS
返回值:返回一个数组。- 元素一定不存在:0
- 元素可能存在:1
- 其它情况返回相应的异常信息
插入元素
向key指定的Bloom中添加多个元素,添加时可以指定大小和错误率,且可以控制在Bloom不存在的时候是否自动创建
bf.insert{key} [CAPACITY {cap}] [ERROR {ERROR}] [NOCREATE] ITEMS {item…}
增量持久化
用于对布隆过滤器的增量保存,这适用于不能正常保存和恢复的大型布隆过滤器,第一次调用此命令时,iter的值应为 0。此命令返回连续(iter, data)
对,直到(0, NULL)
指示完成。
bf.scandump {key} {item}
- 参数说明:
- key:布隆过滤器的名字
- item:首次调用传值0,或者上次调用此命令返回的结果值
加载数据
加载增量保存的布隆过滤器数据。
BF.LOADCHUNK {key} {iter} {data}
其中iter
和data
是每次执行BF.SCANDUMP
返回的结果值
参考:https://redis.io/commands/bf.scandump/
查看信息
返回布隆过滤器的相关信息
bf.info {key}
- 返回值:
- Capacity:预设容量
- Size:实际占用情况,但如何计算待进一步确认
- Number of filters:过滤器层数
- Number of items inserted:已经实际插入的元素数量
- Expansion rate:子过滤器扩容系数(默认2)
debug
查看布隆过滤器的内部详细信息
bf.debug {key}
返回值:
- size:布隆过滤器中已插入的元素数量
- 每层BloomFilter的详细信息
- bytes:占用字节数量
bits:占用bit位数量,bits = bytes * 8 - shashes:该层hash函数数量
- hashwidth:hash函数宽度
- capacity:该层容量(第一层为BloomFilter初始化时设置的容量,第2层容量 = 第一层容量 * expansion,以此类推)
- size:该层中已插入的元素数量(各层size之和等于BloomFilter中已插入的元素数量size)
- ratio:该层错误率(第一层的错误率 = BloomFilter初始化时设置的错误率 * 0.5,第二层为第一层的0.5倍,以此类推,ratio与expansion无关)
- bytes:占用字节数量
Java集成Redis使用布隆过滤器
1、redisson实现
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson-spring-boot-starter</artifactId>
<version>3.13.2</version>
</dependency>
代码示例1:
Config config = new Config();
SingleServerConfig singleServerConfig = config.useSingleServer();
singleServerConfig.setAddress("redis://127.0.0.1:6379");
singleServerConfig.setPassword("123456");
RedissonClient redissonClient = Redisson.create(config);
RBloomFilter<String> bloom = redissonClient.getBloomFilter("name");
// 初始化布隆过滤器; 大小:100000,误判率:0.01
bloom.tryInit(100000L, 0.01);
for(int i=0;i<100000;i++) {
bloom.add("name" + i);
}
boolean notExist = bloom.contains("name1");
if (notExist) {
notExistList.add(str);
}
代码示例2:
@RunWith(SpringRunner.class)
@SpringBootTest
public class BloomFilterTest {
@Autowired
private RedissonClient redissonClient;
@Test
public void testAll() {
String key ="BF:AAB";
RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter(key);
bloomFilter.tryInit(500,0.01);
bloomFilter.add("happy");
bloomFilter.add("cool");
boolean aNew = bloomFilter.contains("new");
System.out.println(aNew);
aNew = bloomFilter.contains("cool");
System.out.println(aNew);
}
}
注意:
#如果不执行 bloom.tryInit(100000L, 0.01); 进行初始化,则会抛出以下异常:
Bloom filter is not initialized!
# Redisson 创建的bloomFilter 内部类型为String。不能操作使用bf.RESERVE 生成的key
WRONGTYPE Operation against a key holding the wrong kind of value. channel: [id: 0x155aa9f1, L:/192.168.8.55:50887 - R:/192.168.1.54:6378] command: (SETBIT), params: [BF:AAA, 14, 1]
127.0.0.1:6379> type BF:AAA
MBbloom--
127.0.0.1:6379> type BF:AAB
string
2、com.redislabs
实现
<!-- https://mvnrepository.com/artifact/com.redislabs/jrebloom -->
<dependency>
<groupId>com.redislabs</groupId>
<artifactId>jrebloom</artifactId>
<version>2.2.2</version>
</dependency>
@Configuration
public class RedisBloomFilterConfiguration {
@Autowired
private RedisTemplate redisTemplate;
@Bean
public JedisPool jedisPool() {
RedisConnectionFactory connectionFactory = redisTemplate.getConnectionFactory();
if (connectionFactory instanceof LettuceConnectionFactory) {
LettuceConnectionFactory lettuceConnectionFactory = (LettuceConnectionFactory) connectionFactory;
return new JedisPool(new GenericObjectPoolConfig()
, lettuceConnectionFactory.getHostName()
, lettuceConnectionFactory.getPort()
, Long.valueOf(lettuceConnectionFactory.getTimeout()).intValue()
, lettuceConnectionFactory.getPassword()
, lettuceConnectionFactory.getDatabase());
} else {
if (connectionFactory instanceof JedisConnectionFactory) {
JedisConnectionFactory jedisConnectionFactory = (JedisConnectionFactory) connectionFactory;
return new JedisPool((jedisConnectionFactory).getPoolConfig());
}
}
throw new IllegalArgumentException("RedisConnectionFactory unsupport.");
}
}
import io.rebloom.client.Client;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.test.context.junit4.SpringRunner;
import redis.clients.jedis.JedisPool;
@RunWith(SpringRunner.class)
@SpringBootTest
public class BloomFilter2Test {
@Autowired
private RedisTemplate redisTemplate;
@Autowired
private JedisPool jedisPool;
@Test
public void testAll() {
String key = "BF:AAE";
Client client = new Client(jedisPool);
Boolean exists = redisTemplate.hasKey(key);
if (!exists) {
client.createFilter(key, 1000, 0.01);
}
client.add(key, "happy");
client.add(key, "cool");
boolean aNew = client.exists(key, "new");
System.out.println(aNew);
aNew = client.exists(key, "cool");
System.out.println(aNew);
}
}
127.0.0.1:6379> type BF:AAE
MBbloom--
3、redistemplate + lua
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.data.redis.core.script.DefaultRedisScript;
import org.springframework.data.redis.core.script.RedisScript;
import java.util.Arrays;
import java.util.List;
/**
* RedisBloomFilterUtil
* RedisTemplate实现方式
*
* @author lihz
* @date 2023/12/5
*/
public class RedisBloomFilterUtil {
private static RedisScript<Boolean> SCRIPT_RESERVE = new DefaultRedisScript<>("return redis.call('bf.reserve', KEYS[1], ARGV[1], ARGV[2])", Boolean.class);
private static RedisScript<Boolean> SCRIPT_ADD = new DefaultRedisScript<>("return redis.call('bf.add', KEYS[1], ARGV[1])", Boolean.class);
private static RedisScript<Boolean> SCRIPT_EXISTS = new DefaultRedisScript<>("return redis.call('bf.exists', KEYS[1], ARGV[1])", Boolean.class);
private static String SCRIPT_MADD = "return redis.call('bf.madd', KEYS[1], %s)";
private static String SCRIPT_MEXISTS = "return redis.call('bf.mexists', KEYS[1], %s)";
private RedisTemplate redisTemplate;
public RedisBloomFilterUtil(RedisTemplate redisTemplate) {
this.redisTemplate = redisTemplate;
}
/**
* 设置错误率和大小(需要在添加元素前调用,若已存在元素,则会报错)
* 错误率越低,需要的空间越大
*
* @param key
* @param errorRate 错误率,默认0.01
* @param initialSize 默认100,预计放入的元素数量,当实际数量超出这个数值时,误判率会上升,尽量估计一个准确数值再加上一定的冗余空间
* @return
*/
public Boolean reserve(String key, double errorRate, int initialSize) {
return (Boolean) redisTemplate.<Boolean>execute(SCRIPT_RESERVE, Arrays.asList(key), String.valueOf(errorRate),
String.valueOf(initialSize));
}
/**
* 添加元素
*
* @param key
* @param value
* @return true表示添加成功,false表示添加失败(存在时会返回false)
*/
public Boolean add(String key, String value) {
return (Boolean) redisTemplate.<Boolean>execute(SCRIPT_ADD, Arrays.asList(key), value);
}
/**
* 查看元素是否存在(判断为存在时有可能是误判,不存在是一定不存在)
*
* @param key
* @param value
* @return true表示存在,false表示不存在
*/
public Boolean exists(String key, String value) {
return (Boolean) redisTemplate.<Boolean>execute(SCRIPT_EXISTS, Arrays.asList(key), value);
}
/**
* 批量添加元素
*
* @param key
* @param values
* @return 按序 1表示添加成功,0表示添加失败
*/
public List<Integer> madd(String key, List<String> values) {
String[] vs = new String[values.size()];
values.toArray(vs);
return (List<Integer>) redisTemplate.execute(this.generateScript(SCRIPT_MADD, vs), Arrays.asList(key),
vs);
}
/**
* 批量检查元素是否存在(判断为存在时有可能是误判,不存在是一定不存在)
*
* @param key
* @param values
* @return 按序 1表示存在,0表示不存在
*/
public List<Integer> mexists(String key, List<String> values) {
String[] vs = new String[values.size()];
values.toArray(vs);
return (List<Integer>) redisTemplate.execute(this.generateScript(SCRIPT_MEXISTS, vs), Arrays.asList(key), vs);
}
private RedisScript<List> generateScript(String script, String[] values) {
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= values.length; i++) {
if (i != 1) {
sb.append(",");
}
sb.append("ARGV[").append(i).append("]");
}
return new DefaultRedisScript<>(String.format(script, sb.toString()), List.class);
}
}
public class BloomFilter2Test {
@Autowired
private RedisTemplate redisTemplate;
@Autowired
private JedisPool jedisPool;
public void testAll() {
String key = "BF:AAH";
StringRedisSerializer serializer = new StringRedisSerializer();
redisTemplate.setKeySerializer(serializer);
redisTemplate.setValueSerializer(serializer);
RedisBloomFilterUtil util = new RedisBloomFilterUtil(redisTemplate);
Boolean exists = redisTemplate.hasKey(key);
if (!exists) {
util.reserve(key, 0.01, 1000);
}
util.add(key, "happy");
util.add(key, "cool");
boolean aNew = util.exists(key, "new");
System.out.println(aNew);
aNew = util.exists(key, "cool");
System.out.println(aNew);
util.madd(key, Arrays.asList("rich", "niubi", "hot", "cry"));
List<Integer> mexists = util.mexists(key, Arrays.asList("cool", "swarm"));
System.out.println(mexists);
mexists = util.mexists(key, Arrays.asList("cry", "xxx", "hot"));
System.out.println(mexists);
}
}
区别
RedisBloom
和Redisson
实现的过滤器区别:
- 数据结构:
RedisBloom
相当于为了实现过滤器而新增了一个数据结构,而Redisson
是基于redis
原有的bitmap
位图数据结构来通过硬编码实现的过滤器。 - 存储: 存储两者其实并没有差距,都没有存储原数据。
- 容错: 同样是10000条数据0.01容错,RedisBloom误判元素是58,Redisson实现的是227。
- 耦合度: 使用
RedisBloom
就需要安装RedisBloom
,如果不安装RedisBloom
程序直接就不能使用了,而使用Redisson
他只依赖于redis
。 - 分片:
RedisBloom
只是redis
一种数据结构,本身redis
集群就是支持分片的,所以RedisBloom
肯定也没问题,Redisson
的布隆过滤器也支持分片,但是需要付费。 - 性能: 使用
redis
的位图来实现的布隆过滤器性能上要差不少。比如一次 exists 查询会涉及到多次getbit
操作,网络开销相比而言会高出不少。
附录
参考
https://redis.com/blog/bloom-filter/
https://github.com/redis/jedis
spring-data-redis与Jedis版本: https://mvnrepository.com/artifact/org.springframework.data/spring-data-redis
jedis与redis对应版本
Jedis version | Supported Redis versions | JDK Compatibility |
---|---|---|
3.9+ | 5.0 and 6.2 Family of releases | 8, 11 |
>= 4.0 | Version 5.0 to current | 8, 11, 17 |
>= 5.0 | Version 6.0 to current | 8, 11, 17 |
免费的在线布隆过滤器在线计算
https://hur.st/bloomfilter/?n=1000000&p=0.03&m=&k=
示例
127.0.0.1:6379> BF.RESERVE BF:AAA 0.01 50
OK
127.0.0.1:6379> BF.ADD BF:AAA abort
(integer) 1
127.0.0.1:6379> BF.ADD BF:AAA about
(integer) 1
127.0.0.1:6379> BF.MADD BF:AAA happy cool
1) (integer) 1
2) (integer) 1
127.0.0.1:6379> BF.EXISTS BF:AAA abort
(integer) 1
127.0.0.1:6379> BF.EXISTS BF:AAA pool
(integer) 0
127.0.0.1:6379> BF.MEXISTS BF:AAA abort pool rich happy
1) (integer) 1
2) (integer) 0
3) (integer) 0
4) (integer) 1
127.0.0.1:6379> BF.INFO BF:AA
(error) ERR not found
127.0.0.1:6379> BF.INFO BF:AAA
1) Capacity
2) (integer) 50
3) Size
4) (integer) 168
5) Number of filters
6) (integer) 1
7) Number of items inserted
8) (integer) 4
9) Expansion rate
10) (integer) 2
127.0.0.1:6379>
127.0.0.1:6379> bf.debug BF:AAA
1) "size:4"
2) "bytes:72 bits:576 hashes:8 hashwidth:64 capacity:50 size:4 ratio:0.005"
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!