布隆(Bloom Filter)过滤器-阿里云开发者社区

开发者社区> 李子捌> 正文

布隆(Bloom Filter)过滤器

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

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函数。

一个大型位数组(二进制数组)

image

多个无偏hash函数:

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

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

image

3.2 空间计算

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

它们之间的关系比较简单:

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

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

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

image


3.3 增加元素

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

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

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

如图所示:

image

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

image

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

image

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

image

编译成功后看到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的配置项,我们可以直接在这里修改,后续修改会更加方便。

image

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

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

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

4.3.2 测试是否成功

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

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


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

image


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

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

image

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

5.1 bf.add

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

127.0.0.1:6379> bf.add name liziba

(integer) 1

image

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

image


5.3 bf.exists

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

127.0.0.1:6379> bf.mexists name liziba

1) (integer) 1

image


5.3 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

image


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>

 *

 * @Author: Liziba

 * @Date: 2021/8/29 14:51

 */

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非常接近。

image

6.4 参数说明

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

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

6.5 fpp&expectedInsertions

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

image

  • 当expectedInsertions=10000000&&fpp=0.03时,位数组的大小numBits=72984408,hash函数的个数numHashFunctions=5

image

  • 当expectedInsertions=100000&&fpp=0.03时,位数组的大小numBits=729844,hash函数的个数numHashFunctions=5

image

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

  • 当预计插入的值的数量不变时,偏差值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>

 *

 * @Author: Liziba

 * @Date: 2021/8/29 16:13

 */

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 测试结果

image

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
9591 0
Java Intercepting Filter Pattern(拦截过滤器)
拦截过滤器模式(Intercepting Filter Pattern)用于对应用程序的请求或响应做一些预处理/后处理。定义过滤器,并在把请求传给实际目标应用程序之前应用在请求上。
744 0
[1] JSP里的一个最简单的过滤器(filter)的例子
一个每隔五秒钟自动刷新的jsp页面:
9 0
[1] JSP里的一个最简单的过滤器(filter)的例子
[1] JSP里的一个最简单的过滤器(filter)的例子
4 0
【Filter 页面重定向循环】写一个过滤器造成的页面重定向循环的问题
今天做一个过滤器,碰上页面重定向循环的情况: 浏览器的访问路径是:http://192.168.16.104:8080/biologyInfo/login/login/login/login/login/login/login/login/login/login/login/login/login...
980 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
10852 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13301 0
输入过滤器——InputFilter
一般情况下我们通过请求体读取器InputStreamInputBuffer获取的仅仅是源数据,即未经过任何处理发送方发来的字节。但有些时候在这个读取的过程中希望做一些额外的处理,并且这些额外处理可能是根据不同条件做不同的处理,考虑到程序解耦与扩展,于是引入过滤器(过滤器模式)——输入过滤器InputFilter。
889 0
+关注
李子捌
简介: CSDN优秀作者、华为云专家 领域: Java框架、并发编程、分布式、微服务、Redis、HarmonyOS、中间件等技术
240
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载