SpringBoot+Redis实现布隆过滤器的示例代码

SpringBoot+Redis实现布隆过滤器的示例代码

目录简述Redis安装BloomFilter基本指令结合SpingBoot方式一方式二

简述

关于布隆过滤器的详细介绍，我在这里就不再赘述一遍了

我们首先知道：BloomFilter使用长度为m bit的字节数组，使用k个hash函数，增加一个元素: 通过k次hash将元素映射到字节数组中k个位置中，并设置对应位置的字节为1。查询元素是否存在: 将元素k次hash得到k个位置，如果对应k个位置的bit是1则认为存在，反之则认为不存在。

Guava 中已经有具体的实现，而在我们实际生产环境中，本地的存储往往无法满足我们实际的 需求。所以在这时候，就需要我们使用 redis 了。

Redis 安装 Bloom Filter

git clone https://github.com/RedisLabsModules/redisbloom.git

cd redisbloom

make # 编译

vi redis.conf

## 增加配置

loadmodule /usr/local/web/redis/RedisBloom-1.1.1/rebloom.so

##redis 重启

#关闭

./redis-cli -h 127.0.0.1 -p 6379 shutdown

#启动

./redis-server ../redis.conf &

基本指令

#创建布隆过滤器，并设置一个期望的错误率和初始大小

bf.reserve userid 0.01 100000

#往过滤器中添加元素

bf.add userid 'sbc@163.com'

#判断指定key的value是否在bloomfilter里存在，存在：返回1，不存在：返回0

bf.exists userid 'sbc@163.com'

结合 SpingBoot

搭建一个简单的 springboot 框架

方式一

配置

xmlns:xsi="http://w3.org/2001/XMLSchema-instance"

xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">

4.0.0

com.bloom

test-bloomfilter

1.0-SNAPSHOT

org.springframework.boot

spring-boot-starter-parent

1.5.8.RELEASE

org.springframework.boot

spring-boot-starter

org.apache.commons

commons-lang3

3.0.1

xmlns:xsi="http://w3.org/2001/XMLSchema-instance"

xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">

4.0.0

com.bloom

test-bloomfilter

1.0-SNAPSHOT

org.springframework.boot

spring-boot-starter-parent

1.5.8.RELEASE

org.springframework.boot

spring-boot-starter

org.apache.commons

commons-lang3

3.0.1

redis本身对布隆过滤器就有一个很好地实现，在 java 端，我们直接导入 redisson 的 jar包即可

org.redisson

redisson

3.8.2

将 Redisson实例 注入 SpringIOC 容器中

@Configuration

public class RedissonConfig {

@Value("${redisson.redis.address}")

private String address;

@Value("${redisson.redis.password}")

private String password;

@Bean

public Config redissionConfig() {

Config config = new Config();

SingleServerConfig singleServerConfig = config.useSingleServer();

singleServerConfig.setAddress(address);

if (StringUtils.isNotEmpty(password)) {

singleServerConfig.setPassword(password);

}

return config;

}

@Bean

public RedissonClient redissonClient() {

return Redisson.create(redissionConfig());

}

}

配置文件

redisson.redis.address=redis://127.0.0.1:6379

redisson.redis.password=

最后测试我们的布隆过滤器

@SpringBootApplication

public class BloomApplication {

public static void main(String[] args) {

ConfigurableApplicationContext context = SpringApplication.run(BloomApplication.class, args);

RedissonClient redisson = context.getBean(RedissonClient.class);

RBloomFilter bf = redisson.getBloomFilter("test-bloom-filter");

bf.tryInit(100000L, 0.03);

Set set = new HashSet(1000);

List list = new ArrayList(1000);

//向布隆过滤器中填充数据，为了测试真实，我们记录了 1000 个 uuid，另外 9000个作为干扰数据

for (int i = 0; i < 10000; i++) {

String uuid = UUID.randomUUID().toString();

eQtPCDoL if(i<1000){

set.add(uuid);

list.add(uuid);

}

bf.add(uuid);

}

int wrong = 0; // 布隆过滤器误判的次数

int right = 0;// 布隆过滤器正确次数

for (int i = 0; i < 10000; i++) {

String str = i % 10 == 0 ? list.get(i / 10) : UUID.randomUUID().toString();

if (bf.contains(str)) {

if (set.contains(str)) {

right++;

} else {

wrong++;

}

}

}

//right 为1000

System.out.println("right:" + right);

//因为误差率为3%，所以一万条数据wrong的值在30左右

System.out.println("wrong:" + wrong);

//过滤器剩余空间大小

System.out.println(bf.count());

}

}

以上使我们使用 redisson 的使用方式，下面介绍一种比较原始的方式，使用lua脚本的方式

方式二

bf_add.lua

local bloomName = KEYS[1]

local value = KEYS[2]

local result = redis.call('BF.ADD',bloomName,value)

return result

bf_exist.lua

local bloomName = KEYS[1]

local value = KEYS[2]

local result = redis.call('BF.EXISTS',bloomName,value)

return result

@Service

public class RedisBloomFilterService {

@Autowired

private RedisTemplate redisTemplate;

//我们依旧用刚刚的那个过滤器

public static final String BLOOMFILTER_NAME = "test-bloom-filter";

/**

* 向布隆过滤器添加元素

* @param str

* @return

*/

public Boolean bloomAdd(String str) {

DefaultRedisScript LuaScript = new DefaultRedisScript();

LuaScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("bf_add.lua")));

LuaScript.setResultType(Boolean.class);

//封装传递脚本参数

List params = new ArrayList();

params.add(BLOOMFILTER_NAME);

params.add(str);

return (Boolean) redisTemplate.execute(LuaScript, params);

}

/**

* 检验元素是否可能存在于布隆过滤器中 * @param id * @return

*/

public Boolean bloomExist(String str) {

DefaultRedisScript LuaScript = new DefaultRedisScript();

LuaScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("bf_exist.lua")));

LuaScript.setResultType(Boolean.class);

//封装传递脚本参数

ArrayList params = new ArrayList();

params.add(BLOOMFILTER_NAME);

params.add(String.valueOf(str));

return (Boolean) redisTemplate.execute(LuaScript, params);

}

}

最后我们还是用上面的启动器执行测试代码

@SpringBootApplication

public class BloomApplication {

public static void main(String[] args) {

ConfigurableApplicationContext context = SpringApplication.run(BloomApplication.class, args);

RedisBloomFilterService filterService = context.getBean(RedisBloomFilterService.class);

Set set = new HashSet(1000);

List list = new ArrayList(1000);

//向布隆过滤器中填充数据，为了测试真实，我们记录了 1000 个 uuid，另外 9000个作为干扰数据

for (int i = 0; i < 10000; i++) {

String uuid = UUID.randomUUID().toString();

if (i < 1000) {

set.add(uuid);

list.add(uuid);

}

filterService.bloomAdd(uuid);

}

int wrong = 0; // 布隆过滤器误判的次数

int right = 0;// 布隆过滤器正确次数

for (int i = 0; i < 10000; i++) {

String str = i % 10 == 0 ? list.get(i / 10) : UUID.randomUUID().toString();

if (filterService.bloomExist(str)) {

if (set.contains(str)) {

right++;

} else {

wrong++;

}

}

}

//right 为1000

System.out.println("right:" + right);

//因为误差率为3%，所以一万条数据wrong的值在30左右

System.out.println("wrong:" + wrong);

}

}

相比而言，个人比较推荐第一种，实现的原理都是差不eQtPCDoL多，redis 官方已经为我封装好了执行脚本，和相关 api，用官方的会更好一点

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。