Spring Boot集成RBloomFilter快速入门Demo

1.什么是BloomFilter？

布隆过滤器原理：布隆过滤器（Bloom Filter）是一种空间效率很高的概率型数据结构，用于判断一个元素是否在一个集合中。它允许有一定的误判率，换取了存储空间的极大节省。这种数据结构在空间效率和查询速度上具有明显优势，尤其适用于大规模数据去重和快速查找的场景。

布隆过滤器的工作原理如下：

布隆过滤器的核心是一个m位的位数组（Bit Array）和k个哈希函数。

初始化时，布隆过滤器创建一个 m 位的位数组（Bit Array），所有位都设为 0。
选取 k 个不同的哈希函数，每个函数都能将任意元素映射到位数组的 m 位中的一个位置。
添加元素时，将元素通过所有 k 个哈希函数进行哈希，得到 k 个位置，并将这些位置的位设为 1。
检查元素是否存在时，同样通过 k 个哈希函数计算出 k 个位置。如果所有这些位置的位都是 1，则认为元素可能存在；如果任何一个位是 0，则元素一定不存在。

BloomFilter的应用场景

BloomFilter广泛应用于需要快速判断元素是否属于一个集合的场景，例如网页爬虫中的URL去重、缓存击穿的解决方案等。在网页爬虫中，URL去重是一项重要的任务。由于互联网上存在大量重复的URL，为了提高爬取效率，需要判断一个URL是否已经被爬取过。使用BloomFilter可以快速判断一个URL是否在已爬取的URL集合中，从而避免重复爬取。在缓存击穿的解决方案中，BloomFilter可以用于判断一个请求是否需要继续查找数据库或缓存。当一个请求到达时，可以先通过BloomFilter判断请求的参数是否已经被处理过，如果是，则直接返回结果，如果否，则继续查找数据库或缓存。

2.环境搭建

Docker Compose

version: '3'
services:redis:image: redis/redis-stackcontainer_name: redisports:- 6379:6379redis-insight:image: redislabs/redisinsightcontainer_name: redis-insightports:- 8001:8001

Run following command:

docker-compose up -d

登录http://localhost:8001/

redis-insights-connection

3.代码工程

实验目标

利用redis的RBloomFilter实现元素的是否存在的判断

pom.xml

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"xmlns:xsi="http://www.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"><parent><artifactId>springboot-demo</artifactId><groupId>com.et</groupId><version>1.0-SNAPSHOT</version></parent><modelVersion>4.0.0</modelVersion><artifactId>BloomFilter</artifactId><properties><maven.compiler.source>8</maven.compiler.source><maven.compiler.target>8</maven.compiler.target></properties><dependencies><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId></dependency><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-autoconfigure</artifactId></dependency><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-test</artifactId><scope>test</scope></dependency><dependency><groupId>org.redisson</groupId><artifactId>redisson</artifactId><version>3.16.1</version></dependency></dependencies>
</project>

config

package com.et.config;import org.redisson.Redisson;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
import org.redisson.config.SingleServerConfig;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.util.StringUtils;@Configuration
public class RedissonConfig {@Value("${redisson.redis.address}")private String address;@Value("${redisson.redis.password}")private String password;@Beanpublic Config redissionConfig() {Config config = new Config();SingleServerConfig singleServerConfig = config.useSingleServer();singleServerConfig.setAddress(address);if (!StringUtils.isEmpty(password)) {singleServerConfig.setPassword(password);}return config;}@Beanpublic RedissonClient redissonClient() {return Redisson.create(redissionConfig());}
}

启动类

package com.et;import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
import org.springframework.context.ConfigurableApplicationContext;import java.util.*;@SpringBootApplication
public class DemoApplication {public static void main(String[] args) {ConfigurableApplicationContext context = SpringApplication.run(DemoApplication.class, args);RedissonClient redisson = context.getBean(RedissonClient.class);RBloomFilter bf = redisson.getBloomFilter("test-bloom-filter");bf.tryInit(100000L, 0.03);Set<String> set = new HashSet<String>(1000);List<String> list = new ArrayList<String>(1000);//Fill the Bloom filter with data. To test the reality, we recorded 1000 uuids and another 9000 as interference data.for (int i = 0; i < 10000; i++) {String uuid = UUID.randomUUID().toString();if(i<1000){set.add(uuid);list.add(uuid);}bf.add(uuid);}int wrong = 0; // Number of false positives by the Bloom filterint right = 0;// Bloom filter correct timesfor (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 is 1000System.out.println("right:" + right);//Because the error rate is 3%, the wrong value of 10,000 data is about 30.System.out.println("wrong:" + wrong);//Filter remaining space sizeSystem.out.println(bf.count());}
}

application.properties

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

以上只是一些关键代码，所有代码请参见下面代码仓库

代码仓库

GitHub - Harries/springboot-demo: a simple springboot demo with some components for example: redis,solr,rockmq and so on.(RBloomFilter)

4.测试

启动Spring Boot应用，查看控制台输出日志

right:1000
wrong:15
29873

5.引用

Bloom filter | Docs
Spring Boot集成RBloomFilter快速入门Demo | Harries Blog™