Redis中Redisson布隆过滤器的学习

目录

• 简介
• 使用
• Demo
• 依赖
• 测试代码
• 简析
• 初始化
• 添加元素
• 检索元素

简介

本文基于Spring Boot 2.6.6、redisson 3.16.0简单分析Redisson布隆过滤器的使用。

布隆过滤器是一个非常长的二进制向量和一系列随机哈希函数的组合，可用于检索一个元素是否存在；

使用场景如下：

• 解决Redis缓存穿透问题；
• 邮件过滤；

使用

• 建立一个二进制向量，所有位设置0；
• 选择K个散列函数，用于对元素进行K次散列，计算向量的位下标；
• 添加元素：将K个散列函数作用于该元素，生成K个值作为位下标，将向量的对应位设置为1；
• 检索元素：将K个散列函数作用于该元素，生成K个值作为位下标，若向量的对应位都是1，则说明该元素可能存在；否则，该元素肯定不存在；

Demo

依赖

    org.springframework.boot
    spring-boot-starter-data-redis
    
        
            io.lettuce
            lettuce-core
        
    


    redis.clients
    jedis


    org.redisson
    redisson
    3.16.0

测试代码

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 bloomFilter = redissonClient.getBloomFilter("bloom-filter");
        // 初始化布隆过滤器
        bloomFilter.tryInit(200, 0.01);

        List 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 bloomFilter, List elements) {
        for (int i = 0; i < elements.size(); i++) {
            if (i % 2 == 0) {
                bloomFilter.add(elements.get(i));
            }
        }
    }

    public static void test(RBloomFilter bloomFilter, List 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.