Redis中Redisson佈隆過濾器的學習
簡介
本文基於Spring Boot 2.6.6、redisson 3.16.0簡單分析Redisson佈隆過濾器的使用。
佈隆過濾器是一個非常長的二進制向量和一系列隨機哈希函數的組合，可用於檢索一個元素是否存在；
使用場景如下：
- 解決Redis緩存穿透問題；
- 郵件過濾；
使用
- 建立一個二進制向量，所有位設置0；
- 選擇K個散列函數，用於對元素進行K次散列，計算向量的位下標；
- 添加元素：將K個散列函數作用於該元素，生成K個值作為位下標，將向量的對應位設置為1；
- 檢索元素：將K個散列函數作用於該元素，生成K個值作為位下標，若向量的對應位都是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());
}
// 向佈隆過濾器中添加內容
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有兩個參數：
- expectedInsertions：預期的插入元素數量；
- falseProbability：預期的錯誤率；
佈隆過濾器可以明確元素不存在，但對於元素存在的判斷是存在錯誤率的；所以初始化時指定的這兩個參數會決定佈隆過濾器的向量長度和散列函數的個數；
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");
}
// 根據元素個數和錯誤率計算得到向量長度
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);
}
// 根據元素個數和向量長度計算得到散列函數的個數
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)));
}
添加元素
向佈隆過濾器中添加元素時，先使用一系列散列函數根據元素得到K個位下標，然後將向量中位下標對應的位設置為1；
RedissonBloomFilter.add方法代碼如下：
public boolean add(T object) {
// 根據帶插入元素得到兩個long類型散列值
long[] hashes = hash(object);
while (true) {
if (size == 0) {
readConfig();
}
int hashIterations = this.hashIterations;
long size = this.size;
// 得到位下標數組
// 以兩個散列值根據指定策略生成hashIterations個散列值，從而得到位下標
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++) {
// 將位下標對應位設置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;
// 散列函數的實現方式
if (i % 2 == 0) {
// 新散列值
hash += hash2;
} else {
// 新散列值
hash += hash1;
}
}
return indexes;
}
hash(long hash1, long hash2, int iterations, long size)方法中，利用根據元素得到的兩個散列值，生成一系列散列函數，然後得到位下標數組；
檢索元素
檢索佈隆過濾器中是否存在指定元素時，先使用一系列散列函數根據元素得到K個位下標，然後判斷向量中位下標對應的位是否為1，若存在一個不為1，則該元素不存在；否則認為存在；
RedissonBloomFilter.contains方法代碼如下：
public boolean contains(T object) {
// 根據帶插入元素得到兩個long類型散列值
long[] hashes = hash(object);
while (true) {
if (size == 0) {
readConfig();
}
int hashIterations = this.hashIterations;
long size = this.size;
// 得到位下標數組
// 以兩個散列值根據指定策略生成hashIterations個散列值，從而得到位下標
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++) {
// 獲取位下標對應位的值
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的位，則認為元素不存在
return false;
}
}
// 都為1，則認為元素存在
return true;
} catch (RedisException e) {
if (e.getMessage() == null || !e.getMessage().contains("Bloom filter config has been changed")) {
throw e;
}
}
}
}
到此這篇關於Redis中Redisson佈隆過濾器的學習的文章就介紹到這瞭,更多相關Redis Redisson佈隆過濾器內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！
推薦閱讀：
- 什麼是Java佈隆過濾器?如何使用你知道嗎
- redis lua腳本實戰秒殺和減庫存的實現
- Redisson RedLock紅鎖加鎖實現過程及原理
- Java Redis Redisson配置教程詳解
- Redis BloomFilter佈隆過濾器原理與實現