jlzzjlzz亚洲乱熟在线播放

系統城裝機大師 - 唯一官網:www.farandoo.com!

當前位置:首頁 > 數據庫 > Redis > 詳細頁面

Redis中Redisson布隆過濾器的學習

時間:2022-05-17來源:www.farandoo.com作者:電腦系統城

簡介

本文基于Spring Boot 2.6.6、redisson 3.16.0簡單分析Redisson布隆過濾器的使用。

布隆過濾器是一個非常長的二進制向量和一系列隨機哈希函數的組合,可用于檢索一個元素是否存在;

使用場景如下:

  • 解決Redis緩存穿透問題;
  • 郵件過濾;

使用

  • 建立一個二進制向量,所有位設置0;
  • 選擇K個散列函數,用于對元素進行K次散列,計算向量的位下標;
  • 添加元素:將K個散列函數作用于該元素,生成K個值作為位下標,將向量的對應位設置為1;
  • 檢索元素:將K個散列函數作用于該元素,生成K個值作為位下標,若向量的對應位都是1,則說明該元素可能存在;否則,該元素肯定不存在;

Demo

依賴

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<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>

測試代碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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方法代碼如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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方法代碼如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
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方法代碼如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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布隆過濾器的學習的文章就介紹到這了

分享到:

相關信息

系統教程欄目

欄目熱門教程

人氣教程排行

站長推薦

熱門系統下載