SpringBoot+Redis實現(xiàn)布隆過濾器的示例代碼

更新時間：2022年03月17日 11:08:26 作者：小小陳丶

本文主要介紹了SpringBoot+Redis實現(xiàn)布隆過濾器的示例代碼，文中根據(jù)實例編碼詳細(xì)介紹的十分詳盡，具有一定的參考價值，感興趣的小伙伴們可以參考一下

簡述

關(guān)于布隆過濾器的詳細(xì)介紹，我在這里就不再贅述一遍了

我們首先知道：BloomFilter使用長度為m bit的字節(jié)數(shù)組，使用k個hash函數(shù)，增加一個元素: 通過k次hash將元素映射到字節(jié)數(shù)組中k個位置中，并設(shè)置對應(yīng)位置的字節(jié)為1。查詢元素是否存在: 將元素k次hash得到k個位置，如果對應(yīng)k個位置的bit是1則認(rèn)為存在，反之則認(rèn)為不存在。

Guava 中已經(jīng)有具體的實現(xiàn)，而在我們實際生產(chǎn)環(huán)境中，本地的存儲往往無法滿足我們實際的需求。所以在這時候，就需要我們使用 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 重啟
#關(guān)閉
./redis-cli -h 127.0.0.1 -p 6379 shutdown
#啟動
./redis-server ../redis.conf &

基本指令

#創(chuàng)建布隆過濾器，并設(shè)置一個期望的錯誤率和初始大小
bf.reserve userid 0.01 100000
#往過濾器中添加元素
bf.add userid 'sbc@163.com'
#判斷指定key的value是否在bloomfilter里存在，存在：返回1，不存在：返回0
bf.exists userid 'sbc@163.com'

結(jié)合 SpingBoot

搭建一個簡單的 springboot 框架

方式一

配置

<?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">
? ? <modelVersion>4.0.0</modelVersion>
? ? <groupId>com.bloom</groupId>
? ? <artifactId>test-bloomfilter</artifactId>
? ? <version>1.0-SNAPSHOT</version>
? ? <parent>
? ? ? ? <groupId>org.springframework.boot</groupId>
? ? ? ? <artifactId>spring-boot-starter-parent</artifactId>
? ? ? ? <version>1.5.8.RELEASE</version>
? ? ? ? <relativePath/> <!-- lookup parent from repository -->
? ? </parent>
? ? <dependencies>
? ? ? ? <dependency>
? ? ? ? ? ? <groupId>org.springframework.boot</groupId>
? ? ? ? ? ? <artifactId>spring-boot-starter</artifactId>
? ? ? ? </dependency>
? ? ? ? <dependency>
? ? ? ? ? ? <groupId>org.apache.commons</groupId>
? ? ? ? ? ? <artifactId>commons-lang3</artifactId>
? ? ? ? ? ? <version>3.0.1</version>
? ? ? ? </dependency>
? ? </dependencies>
</project>

redis本身對布隆過濾器就有一個很好地實現(xiàn)，在 java 端，我們直接導(dǎo)入 redisson 的 jar包即可

<dependency>
? <groupId>org.redisson</groupId>
? <artifactId>redisson</artifactId>
? <version>3.8.2</version>
</dependency>

將 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<String> set = new HashSet<String>(1000);
? ? ? ? List<String> list = new ArrayList<String>(1000);
? ? ? //向布隆過濾器中填充數(shù)據(jù)，為了測試真實，我們記錄了 1000 個 uuid，另外 9000個作為干擾數(shù)據(jù)
? ? ? ? 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; // 布隆過濾器誤判的次數(shù)
? ? ? ? int right = 0;// 布隆過濾器正確次數(shù)
? ? ? ? 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%，所以一萬條數(shù)據(jù)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<Boolean> LuaScript = new DefaultRedisScript<Boolean>();
? ? ? ? LuaScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("bf_add.lua")));
? ? ? ? LuaScript.setResultType(Boolean.class);
? ? ? ? //封裝傳遞腳本參數(shù)
? ? ? ? List<String> params = new ArrayList<String>();
? ? ? ? params.add(BLOOMFILTER_NAME);
? ? ? ? params.add(str);
? ? ? ? return (Boolean) redisTemplate.execute(LuaScript, params);
? ? }

? ? /**
? ? ?* 檢驗元素是否可能存在于布隆過濾器中 * @param id * @return
? ? ?*/
? ? public Boolean bloomExist(String str) {
? ? ? ? DefaultRedisScript<Boolean> LuaScript = new DefaultRedisScript<Boolean>();
? ? ? ? LuaScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("bf_exist.lua")));
? ? ? ? LuaScript.setResultType(Boolean.class);
? ? ? ? //封裝傳遞腳本參數(shù)
? ? ? ? ArrayList<String> params = new ArrayList<String>();
? ? ? ? params.add(BLOOMFILTER_NAME);
? ? ? ? params.add(String.valueOf(str));
? ? ? ? return (Boolean) redisTemplate.execute(LuaScript, params);
? ? }
}

最后我們還是用上面的啟動器執(zhí)行測試代碼

@SpringBootApplication
public class BloomApplication {
? ? public static void main(String[] args) {
? ? ? ? ConfigurableApplicationContext context = SpringApplication.run(BloomApplication.class, args);
? ? ? ? RedisBloomFilterService filterService = context.getBean(RedisBloomFilterService.class);
? ? ? ? Set<String> set = new HashSet<String>(1000);
? ? ? ? List<String> list = new ArrayList<String>(1000);
? ? ? ? //向布隆過濾器中填充數(shù)據(jù)，為了測試真實，我們記錄了 1000 個 uuid，另外 9000個作為干擾數(shù)據(jù)
? ? ? ? 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; // 布隆過濾器誤判的次數(shù)
? ? ? ? int right = 0;// 布隆過濾器正確次數(shù)
? ? ? ? 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%，所以一萬條數(shù)據(jù)wrong的值在30左右
? ? ? ? System.out.println("wrong:" + wrong);
? ? }
}

相比而言，個人比較推薦第一種，實現(xiàn)的原理都是差不多，redis 官方已經(jīng)為我封裝好了執(zhí)行腳本，和相關(guān) api，用官方的會更好一點(diǎn)

到此這篇關(guān)于SpringBoot+Redis實現(xiàn)布隆過濾器的示例代碼的文章就介紹到這了,更多相關(guān)SpringBoot Redis布隆過濾器內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: