【Redisson】Redisson--布隆(Bloom Filter)过滤器

这篇具有很好参考价值的文章主要介绍了【Redisson】Redisson--布隆(Bloom Filter)过滤器。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Redisson系列文章:

  • 【Redisson】Redisson–基础入门
  • 【Redisson】Redisson–布隆(Bloom Filter)过滤器
  • 【Redisson】Redisson–分布式锁的使用(推荐使用)
  • 【分布式锁】Redisson分布式锁底层原理
  • 【Redisson】Redisson–限流器

1、什么是布隆过滤器

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。

上面这句介绍比较全面的描述了什么是布隆过滤器,如果还是不太好理解的话,就可以把布隆过滤器理解为一个set集合,我们可以通过add往里面添加元素,通过contains来判断是否包含某个元素。由于本文讲述布隆过滤器时会结合Redis来讲解,因此类比为Redis中的Set数据结构会比较好理解,而且Redis中的布隆过滤器使用的指令与Set集合非常类似(后续会讲到)。

学习布隆过滤器之前有必要先聊下它的优缺点,因为好的东西我们才想要嘛!

  • 布隆过滤器的优点:

    • 时间复杂度低,增加和查询元素的时间复杂为O(N),(N为哈希函数的个数,通常情况比较小)
    • 保密性强,布隆过滤器不存储元素本身
    • 存储空间小,如果允许存在一定的误判,布隆过滤器是非常节省空间的(相比其他数据结构如Set集合)
  • 布隆过滤器的缺点:

    • 有点一定的误判率,但是可以通过调整参数来降低
    • 无法获取元素本身
    • 很难删除元素

2、布隆过滤器的使用场景

布隆过滤器可以告诉我们 “某样东西一定不存在或者可能存在”,也就是说布隆过滤器说这个数不存在则一定不存,布隆过滤器说这个数存在可能不存在(误判,后续会讲),利用这个判断是否存在的特点可以做很多有趣的事情。

  • 解决Redis缓存穿透问题(面试重点)
  • 邮件过滤,使用布隆过滤器来做邮件黑名单过滤
  • 对爬虫网址进行过滤,爬过的不再爬
  • 解决新闻推荐过的不再推荐(类似抖音刷过的往下滑动不再刷到)
  • HBase\RocksDB\LevelDB等数据库内置布隆过滤器,用于判断数据是否存在,可以减少数据库的IO请求

3、布隆过滤器的原理

3.1 数据结构

布隆过滤器它实际上是一个很长的二进制向量和一系列随机映射函数。以Redis中的布隆过滤器实现为例,Redis中的布隆过滤器底层是一个大型位数组(二进制数组)+多个无偏hash函数
一个大型位数组(二进制数组):

redisson布隆过滤器,# Redis,redis,java,数据库

多个无偏hash函数:
无偏hash函数就是能把元素的hash值计算的比较均匀的hash函数,能使得计算后的元素下标比较均匀的映射到位数组中。

如下就是一个简单的布隆过滤器示意图,其中k1、k2代表增加的元素,a、b、c即为无偏hash函数,最下层则为二进制数组。

redisson布隆过滤器,# Redis,redis,java,数据库

3.2 空间计算

在布隆过滤器增加元素之前,首先需要初始化布隆过滤器的空间,也就是上面说的二进制数组,除此之外还需要计算无偏hash函数的个数。布隆过滤器提供了两个参数,分别是预计加入元素的大小n,运行的错误率f。布隆过滤器中有算法根据这两个参数会计算出二进制数组的大小l,以及无偏hash函数的个数k。
它们之间的关系比较简单:

  • 错误率越低,位数组越长,控件占用较大
  • 错误率越低,无偏hash函数越多,计算耗时较长

如下地址是一个免费的在线布隆过滤器在线计算的网址:

https://krisives.github.io/bloom-calculator/

redisson布隆过滤器,# Redis,redis,java,数据库

3.3 增加元素

往布隆过滤器增加元素,添加的key需要根据k个无偏hash函数计算得到多个hash值,然后对数组长度进行取模得到数组下标的位置,然后将对应数组下标的位置的值置为1

  • 通过k个无偏hash函数计算得到k个hash值
  • 依次取模数组长度,得到数组索引
  • 将计算得到的数组索引下标位置数据修改为1

例如,key = Liziba,无偏hash函数的个数k=3,分别为hash1、hash2、hash3。三个hash函数计算后得到三个数组下标值,并将其值修改为1.
如图所示:

redisson布隆过滤器,# Redis,redis,java,数据库

3.4 查询元素

布隆过滤器最大的用处就在于判断某样东西一定不存在或者可能存在,而这个就是查询元素的结果。其查询元素的过程如下:

  • 通过k个无偏hash函数计算得到k个hash值
  • 依次取模数组长度,得到数组索引
  • 判断索引处的值是否全部为1,如果全部为1则存在(这种存在可能是误判),如果存在一个0则必定不存在

关于误判,其实非常好理解,hash函数在怎么好,也无法完全避免hash冲突,也就是说可能会存在多个元素计算的hash值是相同的,那么它们取模数组长度后的到的数组索引也是相同的,这就是误判的原因。例如李子捌和李子柒的hash值取模后得到的数组索引都是1,但其实这里只有李子捌,如果此时判断李子柒在不在这里,误判就出现啦!因此布隆过滤器最大的缺点误判只要知道其判断元素是否存在的原理就很容易明白了!

3.5 修改元素


3.6 删除元素

布隆过滤器对元素的删除不太支持,目前有一些变形的特定布隆过滤器支持元素的删除!关于为什么对删除不太支持,其实也非常好理解,hash冲突必然存在,删除肯定是很苦难的!

4、Redis集成布隆过滤器

4.1 版本要求

  • 推荐版本6.x,最低4.x版本,可以通过如下命令查看版本:
redis-server -v

redisson布隆过滤器,# Redis,redis,java,数据库

  • 插件安装,网上大部分推荐v1.1.1,文章写的时候v2.2.6已经是release版本了,用户自己选择,地址全在下面(2.2.6官网介绍说是1.0版本的维护版本,如果不想使用新的功能,无需升级!)

redisson布隆过滤器,# Redis,redis,java,数据库

v1.1.1

https://github.com/RedisLabsModules/rebloom/archive/v1.1.1.tar.gz

v2.2.6

https://github.com/RedisLabsModules/rebloom/archive/v2.2.6.tar.gz

4.2 安装&编译

以下安装全部在指定目录下完成,可以选择一个合适的统一目录进行软件安装和管理。

4.2.1 下载插件压缩包

wget https://github.com/RedisLabsModules/rebloom/archive/v2.2.6.tar.gz

4.2.2 解压

tar -zxvf v2.2.6.tar.gz

4.2.3 编译插件

cd RedisBloom-2.2.6/
make

redisson布隆过滤器,# Redis,redis,java,数据库

编译成功后看到redisbloom.so文件即可

4.3 Redis集成

4.3.1 Redis配置文件修改

  • 在redis.conf配置文件中加入如RedisBloom的redisbloom.so文件的地址
  • 如果是集群则每个配置文件中都需要加入redisbloom.so文件的地址
  • 添加完成后需要重启redis
loadmodule /usr/local/soft/RedisBloom-2.2.6/redisbloom.so

redis.conf配置文件中预置了loadmodule的配置项,我们可以直接在这里修改,后续修改会更加方便。
redisson布隆过滤器,# Redis,redis,java,数据库

  • 保存退出后一定要记得重启Redis!

4.3.2 测试是否成功

Redis集成布隆过滤器的主要指令如下:

  • bf.add 添加一个元素
  • bf.exists 判断一个元素是否存在
  • bf.madd 添加多个元素
  • bf.mexists 判断多个元素是否存在

连接客户端进行测试,如果指令有效则证明集成成功

redisson布隆过滤器,# Redis,redis,java,数据库

如果出现如下情况(error) ERR unknown command ,可以通过如下方法检查:

  • SHUTDOWN Redis实例,再重启实例,再次测试
  • 检查配置文件是否配置redisbloom.so文件地址正确
  • 检查Redis的版本是否过低

redisson布隆过滤器,# Redis,redis,java,数据库

5、Redis中布隆过滤器指令使用

5.1 bf.add

bf.add表示添加单个元素,添加成功返回1

127.0.0.1:6379> bf.add name liziba
(integer) 1

redisson布隆过滤器,# Redis,redis,java,数据库

5.2 bf.madd

bf.madd表示添加多个元素

127.0.0.1:6379> bf.madd name liziqi lizijiu lizishi
1) (integer) 1
2) (integer) 1
3) (integer) 1

5.3 bf.exists

bf.exists表示判断元素是否存在,存在则返回1,不存在返回0

127.0.0.1:6379> bf.mexists name liziba
1) (integer) 1

redisson布隆过滤器,# Redis,redis,java,数据库

5.4 bf.mexists

bf.mexists表示判断多个元素是否存在,存在的返回1,不存在的返回0

127.0.0.1:6379> bf.mexists name liziqi lizijiu liziliu
1) (integer) 1
2) (integer) 1
3) (integer) 0

redisson布隆过滤器,# Redis,redis,java,数据库

6、Java本地内存使用布隆过滤器

使用布隆过滤器的方式有很多,还有很多大佬自己手写的,我这里使用的是谷歌guava包中实现的布隆过滤器,这种方式的布隆过滤器是在本地内存中实现。

6.1 引入pom依赖

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>29.0-jre</version>
</dependency>

6.2 编写测试代码

package com.lizba.bf;
 
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
 
/**
 * <p>
 *        布隆过滤器测试代码
 * </p>
 *
 */
public class BloomFilterTest {
 
    /** 预计插入的数据 */
    private static Integer expectedInsertions = 10000000;
    /** 误判率 */
    private static Double fpp = 0.01;
    /** 布隆过滤器 */
    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), expectedInsertions, fpp);
 
    public static void main(String[] args) {
        // 插入 1千万数据
        for (int i = 0; i < expectedInsertions; i++) {
            bloomFilter.put(i);
        }
 
        // 用1千万数据测试误判率
        int count = 0;
        for (int i = expectedInsertions; i < expectedInsertions *2; i++) {
            if (bloomFilter.mightContain(i)) {
                count++;
            }
        }
        System.out.println("一共误判了:" + count);
 
    }
 
}

6.3 测试结果

误判了100075次,大概是expectedInsertions(1千万)的0.01,这与我们设置的 fpp = 0.01非常接近。

redisson布隆过滤器,# Redis,redis,java,数据库

6.4 参数说明

在guava包中的BloomFilter源码中,构造一个BloomFilter对象有四个参数:

  • Funnel funnel:数据类型,由Funnels类指定即可
  • long expectedInsertions:预期插入的值的数量
  • fpp:错误率
  • BloomFilter.Strategy:hash算法

6.5 fpp&expectedInsertions

  • 当expectedInsertions=10000000&&fpp=0.01时,位数组的大小numBits=95850583,hash函数的个数numHashFunctions=7

redisson布隆过滤器,# Redis,redis,java,数据库

  • 当expectedInsertions=10000000&&fpp=0.03时,位数组的大小numBits=72984408,hash函数的个数numHashFunctions=5
    redisson布隆过滤器,# Redis,redis,java,数据库

  • 当expectedInsertions=100000&&fpp=0.03时,位数组的大小numBits=729844,hash函数的个数numHashFunctions=5
    redisson布隆过滤器,# Redis,redis,java,数据库

综上三次测试可以得出如下结论:

  • 当预计插入的值的数量不变时,偏差值fpp越小,位数组越大,hash函数的个数越多
  • 当偏差值不变时,预计插入的中的数量越大,位数组越大,hash函数并没有变化(注意这个结论只是在guava实现的布隆过滤器中的算法符合,并不是说所有的算法都是这个结论,我做了多次测试,确实numHashFunctions在fpp相同时,是不变的!)

7、Java集成Redis使用布隆过滤器

Redis经常会被问道缓存击穿问题,比较优秀的解决办法是使用布隆过滤器,也有使用空对象解决的,但是最好的办法肯定是布隆过滤器,我们可以通过布隆过滤器来判断元素是否存在,避免缓存和数据库都不存在的数据进行查询访问!在如下的代码中只要通过bloomFilter.contains(xxx)即可,我这里演示的还是误判率!

7.1 引入pom依赖

<dependency>
  <groupId>org.redisson</groupId>
  <artifactId>redisson-spring-boot-starter</artifactId>
  <version>3.16.0</version>
</dependency>

7.2 编写测试代码

package com.lizba.bf;
 
import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
 
/**
 * <p>
 *      Java集成Redis使用布隆过滤器防止缓存穿透方案
 * </p>
 *
 */
public class RedisBloomFilterTest {
 
    /** 预计插入的数据 */
    private static Integer expectedInsertions = 10000;
    /** 误判率 */
    private static Double fpp = 0.01;
 
    public static void main(String[] args) {
        // Redis连接配置,无密码
        Config config = new Config();
        config.useSingleServer().setAddress("redis://192.168.211.108:6379");
        // config.useSingleServer().setPassword("123456");
 
        // 初始化布隆过滤器
        RedissonClient client = Redisson.create(config);
        RBloomFilter<Object> bloomFilter = client.getBloomFilter("user");
        bloomFilter.tryInit(expectedInsertions, fpp);
 
        // 布隆过滤器增加元素
        for (Integer i = 0; i < expectedInsertions; i++) {
            bloomFilter.add(i);
        }
 
        // 统计元素
        int count = 0;
        for (int i = expectedInsertions; i < expectedInsertions*2; i++) {
            if (bloomFilter.contains(i)) {
                count++;
            }
        }
        System.out.println("误判次数" + count);
 
    }
 
}

7.3 测试结果

redisson布隆过滤器,# Redis,redis,java,数据库文章来源地址https://www.toymoban.com/news/detail-698349.html

到了这里,关于【Redisson】Redisson--布隆(Bloom Filter)过滤器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 布隆过滤器四种实现(Java,Guava,hutool,Redisson)

    为预防大量黑客故意发起非法的时间查询请求,造成缓存击穿,建议采用布隆过滤器的方法解决。布隆过滤器通过一个很长的二进制向量和一系列随机映射函数(哈希函数)来记录与识别某个数据是否在一个集合中。如果数据不在集合中,能被识别出来,不需要到数据库中进

    2024年01月16日
    浏览(36)
  • 布隆过滤器详解

    本文全部代码地址 布隆过滤器是一种高效的数据结构,用于判断一个元素是否存在于一个集合中.它的主要优点是速度快,空间占用少,因此在需要快速判断某个元素是否在集合中的场合得到广泛引用. 布隆过滤器就是 一个大型的位数组和几个不一样的无偏hash函数. 所谓无偏就是

    2023年04月22日
    浏览(53)
  • 算法~布隆过滤器

    布隆过滤器(Bloom Filter)是一种高效的概率数据结构,用于判断一个元素是否存在于集合中。它基于位数组和多个哈希函数,并具有以下特点: Bloom Filter 是一个基于概率的数据结构:它只能告诉我们一个 元素绝对不在集合内 或 可能在集合内 快速查询:布隆过滤器具有快速

    2024年02月05日
    浏览(45)
  • 布隆过滤器及其应用

    布隆过滤器是一种数据结构,具有快速插入和查找的特性,能确定某个字符串一定存在或者可能存在。布隆过滤器有着高效的空间利用率,它不存储具体数据,只存储数据的关键标识,所以占用的空间较小。它的查询结果可能会存在一定误差,但是误差总体可控,同时不支持

    2024年02月03日
    浏览(42)
  • 位图以及布隆过滤器

    本文主要讲解哈希思想的实际应用,位图和布隆过滤器。 讲解位图之前我们先来解答这样一道腾讯的面试题 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。【腾讯】 很多人立马就想到了用哈希表或者红黑树,因为足够

    2024年02月08日
    浏览(52)
  • 布隆过滤器的原理

    布隆过滤器是一种用于检索一个元素是否在一个集合中的数据结构,具有高效的查询性能和较小的内存占用。 布隆过滤器的底层实现主要涉及以下几个步骤: 初始化数组: 首先,初始化一个比较大的数组,数组中的元素用二进制表示,初始值都为0。 Hash计算: 当一个新的元

    2024年01月18日
    浏览(38)
  • Redis----布隆过滤器

    目录 背景 解决方案 什么是布隆过滤器 布隆过滤器的原理 一些其他运用 比如我们在观看新闻或者刷微博的时候,会不停地给我们推荐新的内容,我们发现几乎没有重复的,说明后台已经进行了去重处理,基于如何去重,Redis给出了高效的方案---布隆过滤器 1.记录已经浏览过

    2024年02月09日
    浏览(37)
  • Java实现布隆过滤器

    背景: 为预防大量黑客故意发起非法的时间查询请求,造成缓存击穿,建议采用布隆过滤器的方法解决。布隆过滤器通过一个很长的二进制向量和一系列随机映射函数(哈希函数)来记录与识别某个数据是否在一个集合中。如果数据不在集合中,能被识别出来,不需要到数据

    2024年02月01日
    浏览(46)
  • 哈希的应用——布隆过滤器

    上一篇文章,我们学习了位图,位图在某些场景下是非常适用的,非常快捷方便。 但是,在文章的最后,我们也提出了位图的一些缺陷——比如位图只能映射整型数据,其它类型的数据则不行。 因为位图里面的元素去映射的其实就是下标嘛,而下标的话都是整型啊。 那有没

    2024年02月09日
    浏览(41)
  • 布隆过滤器:原理与应用

    本文已收录至GitHub,推荐阅读 👉 Java随想录 微信公众号:Java随想录 原创不易,注重版权。转载请注明原作者和原文链接 目录 布隆过滤器简介 fpp 布隆过滤器原理 布隆过滤器的特点 布隆过滤器使用 布隆过滤器中的数据可不可以删除 布隆过滤器应该设计为多大 布隆过滤器应

    2024年02月08日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包