Redis中Redisson布隆過濾器的學(xué)習(xí)
更新時間：2022年05月16日 09:20:42 作者：我家有貓已長成
布隆過濾器是一個非常長的二進(jìn)制向量和一系列隨機(jī)哈希函數(shù)的組合，可用于檢索一個元素是否存在，本文就詳細(xì)的介紹一下Redisson布隆過濾器，具有一定的參考價值，感興趣的可以了解一下
簡介
本文基于Spring Boot 2.6.6、redisson 3.16.0簡單分析Redisson布隆過濾器的使用。
布隆過濾器是一個非常長的二進(jìn)制向量和一系列隨機(jī)哈希函數(shù)的組合，可用于檢索一個元素是否存在；
使用場景如下：
- 解決Redis緩存穿透問題；
- 郵件過濾；
使用
- 建立一個二進(jìn)制向量，所有位設(shè)置0；
- 選擇K個散列函數(shù)，用于對元素進(jìn)行K次散列，計算向量的位下標(biāo)；
- 添加元素：將K個散列函數(shù)作用于該元素，生成K個值作為位下標(biāo)，將向量的對應(yīng)位設(shè)置為1；
- 檢索元素：將K個散列函數(shù)作用于該元素，生成K個值作為位下標(biāo)，若向量的對應(yīng)位都是1，則說明該元素可能存在；否則，該元素肯定不存在；
Demo
依賴
<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>redis.clients</groupId>
<artifactId>jedis</artifactId>
</dependency>
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson</artifactId>
<version>3.16.0</version>
</dependency>
測試代碼
public class BloomFilterDemo {
? ? public static void main(String[] args) {
? ? ? ? Config config = new Config();
? ? ? ? config.useSingleServer().setAddress("redis://127.0.0.1:6379");
? ? ? ? RedissonClient redissonClient = Redisson.create(config);
? ? ? ? RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter("bloom-filter");
? ? ? ? // 初始化布隆過濾器
? ? ? ? bloomFilter.tryInit(200, 0.01);
? ? ? ? List<String> elements = new ArrayList<>();
? ? ? ? for (int i = 0; i < 200; i++) {
? ? ? ? ? ? elements.add(UUID.randomUUID().toString());
? ? ? ? }
? ? ? ? // 向布隆過濾器中添加內(nèi)容
? ? ? ? init(bloomFilter, elements);
? ? ? ? // 測試檢索效果
? ? ? ? test(bloomFilter, elements);
? ? ? ? redissonClient.shutdown();
? ? }
? ? public static void init(RBloomFilter<String> bloomFilter, List<String> elements) {
? ? ? ? for (int i = 0; i < elements.size(); i++) {
? ? ? ? ? ? if (i % 2 == 0) {
? ? ? ? ? ? ? ? bloomFilter.add(elements.get(i));
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? public static void test(RBloomFilter<String> bloomFilter, List<String> elements) {
? ? ? ? int counter = 0;
? ? ? ? for (String element : elements) {
? ? ? ? ? ? if (bloomFilter.contains(element)) {
? ? ? ? ? ? ? ? counter++;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? System.out.println(counter);
? ? }
}簡析
初始化
布隆過濾器的初始化方法tryInit有兩個參數(shù)：
- expectedInsertions：預(yù)期的插入元素數(shù)量；
- falseProbability：預(yù)期的錯誤率；
布隆過濾器可以明確元素不存在，但對于元素存在的判斷是存在錯誤率的；所以初始化時指定的這兩個參數(shù)會決定布隆過濾器的向量長度和散列函數(shù)的個數(shù)；
RedissonBloomFilter.tryInit方法代碼如下：
public boolean tryInit(long expectedInsertions, double falseProbability) {
? ? if (falseProbability > 1) {
? ? ? ? throw new IllegalArgumentException("Bloom filter false probability can't be greater than 1");
? ? }
? ? if (falseProbability < 0) {
? ? ? ? throw new IllegalArgumentException("Bloom filter false probability can't be negative");
? ? }
? ? // 根據(jù)元素個數(shù)和錯誤率計算得到向量長度
? ? size = optimalNumOfBits(expectedInsertions, falseProbability);
? ? if (size == 0) {
? ? ? ? throw new IllegalArgumentException("Bloom filter calculated size is " + size);
? ? }
? ? if (size > getMaxSize()) {
? ? ? ? throw new IllegalArgumentException("Bloom filter size can't be greater than " + getMaxSize() + ". But calculated size is " + size);
? ? }
? ? // 根據(jù)元素個數(shù)和向量長度計算得到散列函數(shù)的個數(shù)
? ? hashIterations = optimalNumOfHashFunctions(expectedInsertions, size);
? ? CommandBatchService executorService = new CommandBatchService(commandExecutor);
? ? executorService.evalReadAsync(configName, codec, RedisCommands.EVAL_VOID,
? ? ? ? ? ? "local size = redis.call('hget', KEYS[1], 'size');" +
? ? ? ? ? ? ? ? ? ? "local hashIterations = redis.call('hget', KEYS[1], 'hashIterations');" +
? ? ? ? ? ? ? ? ? ? "assert(size == false and hashIterations == false, 'Bloom filter config has been changed')",
? ? ? ? ? ? ? ? ? ? Arrays.<Object>asList(configName), size, hashIterations);
? ? executorService.writeAsync(configName, StringCodec.INSTANCE,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? new RedisCommand<Void>("HMSET", new VoidReplayConvertor()), configName,
? ? ? ? ? ? "size", size, "hashIterations", hashIterations,
? ? ? ? ? ? "expectedInsertions", expectedInsertions, "falseProbability", BigDecimal.valueOf(falseProbability).toPlainString());
? ? try {
? ? ? ? executorService.execute();
? ? } catch (RedisException e) {
? ? ? ? if (e.getMessage() == null || !e.getMessage().contains("Bloom filter config has been changed")) {
? ? ? ? ? ? throw e;
? ? ? ? }
? ? ? ? readConfig();
? ? ? ? return false;
? ? }
? ? return true;
}
private long optimalNumOfBits(long n, double p) {
? ? if (p == 0) {
? ? ? ? p = Double.MIN_VALUE;
? ? }
? ? return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}
private int optimalNumOfHashFunctions(long n, long m) {
? ? return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}添加元素
向布隆過濾器中添加元素時，先使用一系列散列函數(shù)根據(jù)元素得到K個位下標(biāo)，然后將向量中位下標(biāo)對應(yīng)的位設(shè)置為1；
RedissonBloomFilter.add方法代碼如下：
public boolean add(T object) {
? ? // 根據(jù)帶插入元素得到兩個long類型散列值
? ? long[] hashes = hash(object);
? ? while (true) {
? ? ? ? if (size == 0) {
? ? ? ? ? ? readConfig();
? ? ? ? }
? ? ? ? int hashIterations = this.hashIterations;
? ? ? ? long size = this.size;
? ? ? ? // 得到位下標(biāo)數(shù)組
? ? ? ? // 以兩個散列值根據(jù)指定策略生成hashIterations個散列值，從而得到位下標(biāo)
? ? ? ? long[] indexes = hash(hashes[0], hashes[1], hashIterations, size);
? ? ? ? CommandBatchService executorService = new CommandBatchService(commandExecutor);
? ? ? ? addConfigCheck(hashIterations, size, executorService);
? ? ? ? RBitSetAsync bs = createBitSet(executorService);
? ? ? ? for (int i = 0; i < indexes.length; i++) {
? ? ? ? ? ? // 將位下標(biāo)對應(yīng)位設(shè)置1
? ? ? ? ? ? bs.setAsync(indexes[i]);
? ? ? ? }
? ? ? ? try {
? ? ? ? ? ? List<Boolean> result = (List<Boolean>) executorService.execute().getResponses();
? ? ? ? ? ? for (Boolean val : result.subList(1, result.size()-1)) {
? ? ? ? ? ? ? ? if (!val) {
? ? ? ? ? ? ? ? ? ? // 元素添加成功
? ? ? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? // 元素已存在
? ? ? ? ? ? return false;
? ? ? ? } catch (RedisException e) {
? ? ? ? ? ? if (e.getMessage() == null || !e.getMessage().contains("Bloom filter config has been changed")) {
? ? ? ? ? ? ? ? throw e;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
private long[] hash(Object object) {
? ? ByteBuf state = encode(object);
? ? try {
? ? ? ? return Hash.hash128(state);
? ? } finally {
? ? ? ? state.release();
? ? }
}
private long[] hash(long hash1, long hash2, int iterations, long size) {
? ? long[] indexes = new long[iterations];
? ? long hash = hash1;
? ? for (int i = 0; i < iterations; i++) {
? ? ? ? indexes[i] = (hash & Long.MAX_VALUE) % size;
? ? ? ? // 散列函數(shù)的實(shí)現(xiàn)方式
? ? ? ? if (i % 2 == 0) {
? ? ? ? ? ? // 新散列值
? ? ? ? ? ? hash += hash2;
? ? ? ? } else {
? ? ? ? ? ? // 新散列值
? ? ? ? ? ? hash += hash1;
? ? ? ? }
? ? }
? ? return indexes;
}hash(long hash1, long hash2, int iterations, long size)方法中，利用根據(jù)元素得到的兩個散列值，生成一系列散列函數(shù)，然后得到位下標(biāo)數(shù)組；
檢索元素
檢索布隆過濾器中是否存在指定元素時，先使用一系列散列函數(shù)根據(jù)元素得到K個位下標(biāo)，然后判斷向量中位下標(biāo)對應(yīng)的位是否為1，若存在一個不為1，則該元素不存在；否則認(rèn)為存在；
RedissonBloomFilter.contains方法代碼如下：
public boolean contains(T object) {
? ? // 根據(jù)帶插入元素得到兩個long類型散列值
? ? long[] hashes = hash(object);
? ? while (true) {
? ? ? ? if (size == 0) {
? ? ? ? ? ? readConfig();
? ? ? ? }
? ? ? ? int hashIterations = this.hashIterations;
? ? ? ? long size = this.size;
? ? ? ? // 得到位下標(biāo)數(shù)組
? ? ? ? // 以兩個散列值根據(jù)指定策略生成hashIterations個散列值，從而得到位下標(biāo)
? ? ? ? long[] indexes = hash(hashes[0], hashes[1], hashIterations, size);
? ? ? ? CommandBatchService executorService = new CommandBatchService(commandExecutor);
? ? ? ? addConfigCheck(hashIterations, size, executorService);
? ? ? ? RBitSetAsync bs = createBitSet(executorService);
? ? ? ? for (int i = 0; i < indexes.length; i++) {
? ? ? ? ? ? // 獲取位下標(biāo)對應(yīng)位的值
? ? ? ? ? ? bs.getAsync(indexes[i]);
? ? ? ? }
? ? ? ? try {
? ? ? ? ? ? List<Boolean> result = (List<Boolean>) executorService.execute().getResponses();
? ? ? ? ? ? for (Boolean val : result.subList(1, result.size()-1)) {
? ? ? ? ? ? ? ? if (!val) {
? ? ? ? ? ? ? ? ? ? // 若存在不為1的位，則認(rèn)為元素不存在
? ? ? ? ? ? ? ? ? ? return false;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? // 都為1，則認(rèn)為元素存在
? ? ? ? ? ? return true;
? ? ? ? } catch (RedisException e) {
? ? ? ? ? ? if (e.getMessage() == null || !e.getMessage().contains("Bloom filter config has been changed")) {
? ? ? ? ? ? ? ? throw e;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}到此這篇關(guān)于Redis中Redisson布隆過濾器的學(xué)習(xí)的文章就介紹到這了,更多相關(guān)Redis Redisson布隆過濾器內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Redis是當(dāng)前比較熱門的NOSQL系統(tǒng)之一,它是一個key-value存儲系統(tǒng),這篇文章主要給大家介紹了關(guān)于如何停止/重啟/啟動Redis服務(wù)的相關(guān)資料,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-03-03
這篇文章介紹了Linux下快速部署Redis的方法，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-01-01
redis stream 實(shí)現(xiàn)消息隊(duì)列的實(shí)踐
本文主要介紹了redis stream 實(shí)現(xiàn)消息隊(duì)列的實(shí)踐，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-08-08
這篇文章主要介紹了詳解redis中的鎖以及使用場景，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
這篇文章主要介紹了redis 過期策略及內(nèi)存回收機(jī)制，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-11-11
這篇文章主要給大家介紹了關(guān)于Redis存取序列化與反序列化性能問題的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
利用Supervisor管理Redis進(jìn)程的方法教程
Supervisor 是可以在類 UNIX 系統(tǒng)中進(jìn)行管理和監(jiān)控各種進(jìn)程的小型系統(tǒng)。它自帶了客戶端和服務(wù)端工具，下面這篇文章主要給大家介紹了關(guān)于利用Supervisor管理Redis進(jìn)程的相關(guān)資料，需要的朋友可以參考借鑒，下面來一起看看吧。2017-08-08
Redis 中spark參數(shù)executor-cores引起的異常解決辦法
這篇文章主要介紹了Redis 中spark參數(shù)executor-cores引起的異常解決辦法的相關(guān)資料,需要的朋友可以參考下2017-03-03
在現(xiàn)有企業(yè)中80%公司大部分使用的是redis單機(jī)服務(wù)，在實(shí)際的場景當(dāng)中單一節(jié)點(diǎn)的redis容易面臨風(fēng)險。本文將介紹Redis主從復(fù)制以及主從復(fù)制原理。2021-05-05
Jedis操作Redis實(shí)現(xiàn)模擬驗(yàn)證碼發(fā)送功能
Redis是一個著名的key-value存儲系統(tǒng)，也是nosql中的最常見的一種，這篇文章主要給大家介紹Jedis操作Redis實(shí)現(xiàn)模擬驗(yàn)證碼發(fā)送功能，感興趣的朋友一起看看吧2021-09-09