站长家园(原代码之家)(www.adminjie.com)网站源码,微信源码,游戏源码,商业源码分享平台。
当前位置:网站首页 技术文章 网络编程 正文

深入浅析Redis中的布隆过滤器(Bloom Filter)

时间:2021-12-25 [网络编程]作者:fabuyuan 浏览:6 次

如何避免缓存穿透?下面本篇文章带大家了解一下Redis中避免缓存穿透的利器——布隆过滤器(Bloom Filter),希望对大家有所帮助!

深入浅析Redis中的布隆过滤器(Bloom Filter)

概述

布隆过滤器(Bloom Filter)是一个数据结构,由布隆(Burton Howard Bloom)于 1970 年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。【相关推荐:Redis视频教程

布隆过滤器可以用于高效的检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远优于一般的算法,缺点是有一定的误识别率,而且难以删除(一般不支持,需要额外的实现)。

误识率指的是可以判断元素肯定不在集合中,判断元素可能在集合中,无法判断元素一定在集合中。

布隆过滤器之所以高效,因为它是一个概率数据结构,它能确认元素肯定不在集合中,或者元素可能在集合中。之所以说是可能,是因为它有一定的误识别率,使得无法 100% 确定元素一定在集合中。

问题引出

在日常工作中,有一个比较常见的需求,就是需要判断一个元素是否在集合中。例如以下场景

  • 给定一个IP黑名单库,检查指定IP是否在黑名单中?
  • 在接收邮件的时候,判断一个邮箱地址是否为垃圾邮件?
  • 在文字处理软件中,检查一个英文单词是否拼写正确?

遇到这种问题,通常直觉会告诉我们,应该使用集合这种数据结构来实现。例如,先将 IP 黑名单库的所有 IP 全部存储到一个集合中,然后再拿指定的 IP 到该集合中检查是否存在,如果存在则说明该 IP 命中黑名单。

通过一段代码来模拟 IP 黑名单库的存储和检查。

public class IPBlackList {

	public static void main(String[] args) {
		Set<String> set = new HashSet<>();
		set.add("192.168.1.1");
		set.add("192.168.1.2");
		set.add("192.168.1.4");
		System.out.println(set.contains("192.168.1.1"));
		System.out.println(set.contains("192.168.1.2"));
		System.out.println(set.contains("192.168.1.3"));
		System.out.println(set.contains("192.168.1.4"));
	}
}

集合的内部,通常是使用散列表来实现。其优点是查询非常高效,缺点是比较耗费存储空间。

一般在数据量比较小的时候,我们会使用集合来进行存储。以空间换时间,在占用空间较小的情况下,同时又能提高查询效率。

但是,当存储的数据量比较大的时候,耗费大量空间将会成为问题。因为这些数据通常会存储到进程内存中,以加快查询效率。而机器的内存通常都是有限的,要尽可能高效的使用。

另一方面,散列表在空间和效率上是需要做平衡的。存储相同数量的元素,如果散列表容量越小,出现冲突的概率就越高,用于解决冲突的时间将会花费更多,从而影响性能。

而布隆过滤器(Bloom Filter)的产生,能够很好的解决这个问题。一方面能够以更少的内存来存储数据,另一方面能够实现非常高效的查询性能。

基本原理

  • 首先,建立一个二进制向量,并将所有位设置为 0

  • 然后,选定 K 个散列函数,用于对元素进行 K 次散列,计算向量的位下标。

添加元素

当添加一个元素到集合中时,通过 K 个散列函数分别作用于元素,生成 K 个值作为下标,并对向量的相应位设置为 1。

检查元素

如果要检查一个元素是否存在集合中,用同样的散列方法,生成 K 个下标,并检查向量的相应位是否全部是 1。

如果全为 1,则该元素很可能在集合中;否则(只要有1个或以上的位为0),该元素肯定不在集合中。

Demo

  • 假设有一个布隆过滤器,容量是15位,使用2个哈希函数,如下所示。

|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |0|||||||||||||||||||

  • 添加一个字符串 a,2次哈希得到下标为 4 和 10,将 4 和 10 对应的位由 0 标记为 1。

|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1||||||1|||||||||

  • 再添加一个字符串 b,2 次哈希得到下标为 11,将 11 对应的位由 0 标记为 1。

|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1||||||1|1||||||||

  • 再添加一个字符串 c,2 次哈希得到下标为 11 和 12,将对应的位由 0 标记为 1。

|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1||||||1|1|1|||||||

  • 最后添加一个字符串 sam,2 次哈希得到下标为 0 和 7,将对应的位由 0 标记为 1。

|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |1||||1|||1|||1|1|1|||||||

上面,我们添加了 4 个字符串,每个字符串分别进行 2 次哈希,对应的2个位标记为1,最终被标记为1的共有6位而不是8位。

这说明,不同的元素,哈希后得到的位置是可能出现重叠的。如果元素越多,出现重叠的概率会更高。如果有2个元素出现重叠的位置,我们是无法判断任一元素一定在集合中的。

如果要检查一下元素是否存在集合中,只需要以相同的方法,进行 2 次哈希,将得到的 2 个下标在布隆过滤器中的相应位进行查找。如果对应的 2 位不是全部为1,则该元素肯定不在集合中。如果对应的 2 位全部为1,则说明该元素可能在集合中,也可能不存在。

例如,检查字符串 b 是否存在集合中,哈希得到的 2 个下标都为11。检查发现,11对应的位为1。但是,这并不能说明 b 一定在集合中。这是因为,字符串 c 哈希后的下标也包含11,有可能只是字符串c在集合中,而 b 却不存在,这就是造成了误识别,也称为假阳性。

再检查字符串 foo,哈希得到的下标分别为 8 和 13,对应的位都为0。因此,字符串 foo 肯定不在集合中。

数学原理

布隆过滤器背后的数学原理是

两个完全随机的数字相冲突的概率很小,因此可以在很小的误识别率条件下,用很少的空间存储大量信息。

误识别率

误识别率(FPPfalse positive probabilistic)的计算如下。

假设布隆过滤器大小为 m 比特,存储了 n 个元素,使用 k 次散列函数来计算元素的存储位置。

  • 添加 1 个元素,则任一比特为 1 的概率为 1/m,任一比特为 0 的概率为 1-1/m
  • 添加 1 个元素,执行 k 次散列之后,则任一比特为 0 的概率为 (1-1/m)^k,任一比特为 1 的概率为 1-(1-1/m)^k
  • 如果添加 n 个元素,那么任一比特为 0 的概率为 (1-1/m)^kn,任一比特为 1 的概率为 1-(1-1/m)^kn
  • 如果将 1 个新的元素,添加到已存在 n 个元素的布隆过滤器中,则任一比特已经为 1 的概率与上面相同,概率为 1-(1-1/m)^kn。因此,k 个比特都为1的概率为:(1-(1-1/m)^kn)^k,此即为新插入元素的误识别率。

当 n 值比较大时,$(1-(1-1/m)^{kn})^k$ 约等于 $(1-e^{-kn/m})^k$

假定布隆过滤器大小 m 为 16 比特,k为 8,存储元素 n 为1,那么误识别(假阳性)的概率是万分之五(5/10000)。

此时,m/n=16,事实上这表示 1个元素使用 16 个比特的空间来存储。

因此,当 k 相同时,m/n 为 16/1、32/2、64/4 等值时具有相同的误识别率。

网站 Bloom Filters - the math 给出了布隆过滤器的误识别率表,可以很方便的查处不同 mnk 给定值下的误识别率。

解决误识别率

解决误识别率的常用方法包括

  • 白名单

  • 回溯确认

白名单

解决误识别率的常见方法,是建立一个较小的白名单,用来存储那些可能被误识别的数据。

以垃圾邮件过滤为例。假设我们有一个垃圾邮件库,用于在接收邮件的时候过滤掉垃圾邮件。

这时可以先将这个垃圾邮件库存储到布隆过滤器中,当接收到邮件的时候,可以先通过布隆过滤器高效的过滤出大部分正常邮件。

而对于少部分命中(可能为)垃圾邮件的,其中有一部分可能为正常邮件。

再创建一个白名单库,当在布隆过滤器中判断可能为垃圾邮件时,通过查询白名单来确认是否为正常邮件。

对于没在白名单中的邮件,默认会被移动到垃圾箱。通过人工识别的方式,当发现垃圾箱中存在正常邮件的时候,将其移入白名单。

回源确认

很多时候,使用布隆过滤器是为了低成本,高效率的拦截掉大量数据不在集合中的场景。例如

  • Google Bigtable,Apache HBase以及Apache Cassandra和PostgreSQL 使用 Bloom 过滤器来减少对不存在的行或列的磁盘查找。避免进行昂贵的磁盘查找,可大大提高数据库查询操作的性能。
  • 在谷歌浏览器用于使用布隆过滤器来识别恶意URL的网页浏览器。首先会针对本地 Bloom 过滤器检查所有 URL,只有在 Bloom 过滤器返回肯定结果的情况下,才对执行的 URL 进行全面检查(如果该结果也返回肯定结果,则用户会发出警告)。
  • 拦截掉大量非IP黑名单请求,对于少量可能在黑名单中的IP,再查询一次黑名单库。

这是布隆过滤器非常典型的应用场景,先过滤掉大部分请求,然后只处理少量不明确的请求。

这个方法,和白名单库的区别是,不需要再另外建立一套库来处理,而是使用本来就已经存在的数据和逻辑。

例如 Google Bigtable 查询数据行本来就是需要查的,只不过使用布隆过滤器拦截掉了大部分不必要的请求。而 IP 是否为黑名单也是需要查询的,同样是先使用布隆过滤器来拦截掉大部分IP。

而上面垃圾邮件的处理,对于可能为垃圾邮件的情况,不是通过完整的垃圾邮件库再查询一次进行确认,而是用增加白名单来进行判断的方式。因为通常来说,白名单库会更小,便于缓存。

这里所说的回源,实际上是对可能被误识别的请求,最后要回到数据源头或逻辑确认一次。

Guava中的布隆容器的实现

Guava 中就提供了一种 Bloom Filter 的实现。

guava包引入

要使用 Bloom Filter,需要引入 guava 包

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>23.0</version>
</dependency>

误判率测试

下面对布隆容器的误判率进行测试,分2步

  • 往过滤器中放一百万个数,然后去验证这一百万个数是否能通过过滤器

  • 另外找一万个数,去检验漏网之鱼的数量

/**
 * 测试布隆过滤器(可用于redis缓存穿透)
 * 
 * @author 敖丙
 */
public class TestBloomFilter {

    private static int total = 1000000;
    private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total);
//    private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total, 0.001);

    public static void main(String[] args) {
        // 初始化1000000条数据到过滤器中
        for (int i = 0; i < total; i++) {
            bf.put(i);
        }

        // 匹配已在过滤器中的值,是否有匹配不上的
        for (int i = 0; i < total; i++) {
            if (!bf.mightContain(i)) {
                System.out.println("有坏人逃脱了~~~");
            }
        }

        // 匹配不在过滤器中的10000个值,有多少匹配出来
        int count = 0;
        for (int i = total; i < total + 10000; i++) {
            if (bf.mightContain(i)) {
                count++;
            }
        }
        System.out.println("误伤的数量:" + count);
    }

}

运行结果

误伤的数量:320

运行结果表示,遍历这一百万个在过滤器中的数时,都被识别出来了。一万个不在过滤器中的数,误伤了320个,错误率是0.03左右。

Bloom Filter 源码分析

public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions) {
        return create(funnel, (long) expectedInsertions);
    }  

    public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
        return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions
    }

    public static <T> BloomFilter<T> create(
          Funnel<? super T> funnel, long expectedInsertions, double fpp) {
        return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64);
    }

    static <T> BloomFilter<T> create(
      Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
     ......
    }

Bloom Filter 一共四个 create 方法,不过最终都是走向第4个。看一下每个参数的含义

  • funnel:数据类型(一般是调用Funnels工具类中的)

  • expectedInsertions:期望插入的值的个数

  • fpp: 错误率(默认值为0.03)

  • strategy: 哈希算法 Bloom Filter的应用

更多编程相关知识,请访问:编程视频!!

以上就是深入浅析Redis中的布隆过滤器(Bloom Filter)的详细内容,更多请关注站长家园其它相关文章!

本文标签:  Redis布隆过滤器Bloom Filter

转载请注明来源:深入浅析Redis中的布隆过滤器(Bloom Filter)

本文永久链接地址:https://www.adminjie.com/post/6784.html

免责声明:
本站所发布的一切资源仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容。如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。

附:
二○○二年一月一日《计算机软件保护条例》第十七条规定:为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬!鉴于此,也希望大家按此说明研究软件!

版权声明:
一、本站致力于为软件爱好者提供国内外软件开发技术和软件共享,着力为用户提供优资资源。
二、本站提供的部分源码下载文件为网络共享资源,请于下载后的24小时内删除。如需体验更多乐趣,还请支持正版。
三、我站提供用户下载的所有内容均转自互联网。如有内容侵犯您的版权或其他利益的,若有侵犯你的权益请:提交版权证明文件到邮箱 2225329873#qq.com(#换为@) 站长会进行审查之后,情况属实的会在三个工作日内为您删除。

  • 站长家园(原代码之家)会员升级
  • 最新文章
    • 十分钟教你使用css实现烟雾效果

      十分钟教你使用css实现烟雾效果

      本篇文章给大家分享怎样利用css实现烟雾的效果,希望对大家有帮助。仔细观察烟雾效果,有两个比较重要的特点:模糊效果颗粒感首先看模糊效果,想到模糊,大部分同学首先...

    • 总结分享十个Linux环境下的替代工具

      总结分享十个Linux环境下的替代工具

      本篇文章给大家带来了linux操作系统下替代工具的相关知识,其中包括linux中安装和使用bat命令,希望对大家有帮助。在Linux操作系统下,我们经常使用...

    • 快来看一看你的git学的怎么样了(整理总结)

      快来看一看你的git学的怎么样了(整理总结)

      本篇文章给大家总结了git的相关知识,其中包括commit规范与提交验证、误操作的撤回方案和Tag与生产环境等,希望对大家有帮助。本文从前端工程,团队协作,生...

    • Docker总结分享之数据卷技术

      Docker总结分享之数据卷技术

      本篇文章给大家带来了Docker总结分享之数据卷技术的相关知识,希望对大家有帮助。Docker数据卷技术什么是容器数据卷docker的理念回顾将应和环境打包成一...

    • oracle如何修改列的值

      oracle如何修改列的值

      在oracle中,可以使用“update”命令来修改列的值,该语句可以用来修改、更新一个或多个表的数据,语法为“update表名set列名1=值1,列名2...

  • 买服务器送会员
  • 热门文章
  • 买服务器送会员