Redis中Redisson布隆过滤器的学习

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

简介

本文基于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布隆过滤器内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 布隆过滤器的概述及Python实现方法

    布隆过滤器 布隆过滤器是一种概率空间高效的数据结构.它与hashmap非常相似,用于检索一个元素是否在一个集合中.它在检索元素是否存在时,能很好地取舍空间使用率与误报比例.正是由于这个特性,它被称作概率性数据结构(probabilistic data structure). 空间效率 我们来仔细地看看它的空间效率.如果你想在集合中存储一系列的元素,有很多种不同的做法.你可以把数据存储在hashmap,随后在hashmap中检索元素是否存在,hashmap的插入和查询的效率都非常高.但是,由于ha

  • Redis使用元素删除的布隆过滤器来解决缓存穿透问题

    目录 前言 缓存雪崩 解决方案 缓存击穿 解决方案 缓存穿透 解决方案 布隆过滤器(Bloom Filter) 什么是布隆过滤器 位图(Bitmap) 哈希碰撞 布隆过滤器的2大特点 fpp 布隆过滤器的实现(Guava) 布隆过滤器的如何删除 带有计数器的布隆过滤器 总结 前言 在我们日常开发中,Redis使用场景最多的就是作为缓存和分布式锁等功能来使用,而其用作缓存最大的目的就是为了降低数据库访问.但是假如我们某些数据并不存在于Redis当中,那么请求还是会直接到达数据库,而一旦在同一时间大

  • 布隆过滤器(Bloom Filter)的Java实现方法

    布隆过滤器原理很简单:就是把一个字符串哈希成一个整数key,然后选取一个很长的比特序列,开始都是0,在key把此位置的0变为1:下次进来一个字符串,哈希之后的值key,如果在此比特位上的值也是1,那么就说明这个字符串存在了. 如果按照上面的做法,那就和哈希算法没有什么区别了,哈希算法还有重复的呢. 布隆过滤器是将一个字符串哈希成多个key,我还是按照书上的说吧. 先建立一个16亿二进制常量,然后将这16亿个二进制位全部置0.对于每个字符串,用8个不同的随机产生器(F1,F2,.....,F8)产

  • Redis实现布隆过滤器的方法及原理

    布隆过滤器(Bloom Filter)是1970年由布隆提出的.它实际上是一个很长的二进制向量和一系列随机映射函数.布隆过滤器可以用于检索一个元素是否在一个集合中.它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难. 本文将介绍布隆过滤器的原理以及Redis如何实现布隆过滤器. 应用场景 1.50亿个电话号码,现有10万个电话号码,如何判断这10万个是否已经存在在50亿个之中?(可能方案:数据库,set, hyperloglog) 2.新闻客户端看新闻时,它会不

  • 布隆过滤器的原理以及java 简单实现

    一.布隆过滤器 布隆过滤器(Bloom Filter)是1970年由布隆提出的.它实际上是一个很长的二进制向量和一系列随机映射函数.布隆过滤器可以用于检索一个元素是否在一个集合中.它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难. 如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定.链表.树.散列表(又叫哈希表,Hash table)等等数据结构都是这种思路.但是随着集合中元素的增加,我们需要的存储空间越来越大.同时检索

  • 布隆过滤器(bloom filter)及php和redis实现布隆过滤器的方法

    引言 在介绍布隆过滤器之前我们首先引入几个场景. 场景一 在一个高并发的计数系统中,如果一个key没有计数,此时我们应该返回0,但是访问的key不存在,相当于每次访问缓存都不起作用了.那么如何避免频繁访问数量为0的key而导致的缓存被击穿? 有人说, 将这个key的值置为0存入缓存不就行了吗?确实,这是一个好的方案.大部分情况我们都是这样做的,当访问一个不存在的key的时候,设置一个带有过期时间的标志,然后放入缓存.不过这样做的缺点也很明显,浪费内存和无法抵御随机key攻击. 场景二 在一个黑名

  • Redis 中的布隆过滤器的实现

    什么是『布隆过滤器』 布隆过滤器是一个神奇的数据结构,可以用来判断一个元素是否在一个集合中.很常用的一个功能是用来去重.在爬虫中常见的一个需求:目标网站 URL 千千万,怎么判断某个 URL 爬虫是否宠幸过?简单点可以爬虫每采集过一个 URL,就把这个 URL 存入数据库中,每次一个新的 URL 过来就到数据库查询下是否访问过. select id from table where url = 'https://jaychen.cc' 但是随着爬虫爬过的 URL 越来越多,每次请求前都要访问数据

  • Redis中Redisson布隆过滤器的学习

    目录 简介 使用 Demo 依赖 测试代码 简析 初始化 添加元素 检索元素 简介 本文基于Spring Boot 2.6.6.redisson 3.16.0简单分析Redisson布隆过滤器的使用. 布隆过滤器是一个非常长的二进制向量和一系列随机哈希函数的组合,可用于检索一个元素是否存在: 使用场景如下: 解决Redis缓存穿透问题: 邮件过滤: 使用 建立一个二进制向量,所有位设置0: 选择K个散列函数,用于对元素进行K次散列,计算向量的位下标: 添加元素:将K个散列函数作用于该元素,生成K

  • Redis中Bloom filter布隆过滤器的学习

    目录 1.概念 2.guava实现 2.1.依赖 2.2.初始化布隆过滤器 2.3.布隆过滤器 2.4.添加元素或者判断是否存在 3.Redisson实现 3.1.依赖 3.2.注入或测试 1.概念 ​ 布隆过滤器是一个高空间利用率的概率性数据结构,主要目的是节省内存空间以及判断一个元素是否存在于一个集合中(存在误判的情况),可以理解为一个不怎么精确的 set 结构,当你使用它的 contains 方法判断某个对象是否存在时,它可能会误判.但是布隆过滤器也不是特别不精确,只要参数设置的合理,它的

  • Redis中Redisson红锁(Redlock)使用原理

    目录 简介 为什么使用Redis的红锁 解决方案:使用红锁 Redisson红锁实例 Redisson红锁原理 参考文章 简介 说明 本文介绍为什么要使用Redis的红锁(Redlock).什么是Redis的红锁以及Redis红锁的原理. 本文用Redisson来介绍Redis红锁的用法. Redisson 高版本会根据redisClient的模式来决定getLock返回的锁类型,如果集群模式,满足红锁的条件,则会直接返回红锁. 官网 REDIS distlock -- Redis中国用户组(C

  • 浅析python实现布隆过滤器及Redis中的缓存穿透原理

    目录 布隆过滤器的原理 在 Python 中使用布隆过滤器 1.标准布隆过滤器. 2.计数布隆过滤器. 3.标准扩容布隆过滤器. 4.计数扩容布隆过滤器. Redis 中使用布隆过滤器 最后的话 在开发软件时,我们经常需要判断一个元素是否在一个集合中,比如,如何判断单词的拼写是否错误(判断单词是否在已知的字典中):在网络爬虫里,如何确认一个网址是否已经爬取过:反垃圾邮件系统中,如何判断一个邮件地址是否为垃圾邮件地址等等. 如果这些作为面试题那就很有区分度了,初级工程师就会说,把全部的元素都存在

  • python实现布隆过滤器及原理解析

    在学习redis过程中提到一个缓存击穿的问题, 书中参考的解决方案之一是使用布隆过滤器, 那么就有必要来了解一下什么是布隆过滤器.在参考了许多博客之后, 写个总结记录一下. 一.布隆过滤器简介 什么是布隆过滤器? 本质上布隆过滤器( BloomFilter )是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 "某样东西一定不存在或者可能存在". 相比于传统的 Set.Map 等数据结构,它更高效

  • SpringBoot+Redis实现布隆过滤器的示例代码

    目录 简述 Redis安装BloomFilter 基本指令 结合SpingBoot 方式一 方式二 简述 关于布隆过滤器的详细介绍,我在这里就不再赘述一遍了 我们首先知道:BloomFilter使用长度为m bit的字节数组,使用k个hash函数,增加一个元素: 通过k次hash将元素映射到字节数组中k个位置中,并设置对应位置的字节为1.查询元素是否存在: 将元素k次hash得到k个位置,如果对应k个位置的bit是1则认为存在,反之则认为不存在. Guava 中已经有具体的实现,而在我们实际生产

  • 详解SpringBoot中如何使用布隆过滤器

    目录 前言 一.Guava 实现布隆过滤器 二.Hutool 布隆过滤器 三.Redission 布隆过滤器 四.小结 五.Guava 布隆过滤器结合 Redis 使用 昨天写了一篇Redis布隆过滤器相关的命令的文章,今天来说一说springboot中如何简单在代码中使用布隆过滤器吧. 目前市面上也有好几种实现方式,如果你需要高度定制化,可以完全从零实现,当然这不是一个简单的工程. 如果只是想快速开始的话,那么市面上现成的实现,无疑是最快的. 前言 今天说到的实现方式有以下几种: 引入 Gua

随机推荐