初探布隆过滤器(Bloom Filter)基本原理和使用场景

1 背景

如何在海量数据中,快速判断一个元素是否存在?

如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定考虑以下情况:

  • 如果集合用线性表存储,查找的时间复杂度为O(n)。
  • 如果用平衡BST(如AVL树、红黑树)存储,时间复杂度为O(logn)。
  • 如果用哈希表存储,并用链地址法与平衡BST解决哈希冲突(参考JDK8的HashMap实现方法),时间复杂度也要有O[log(n/m)],m为哈希分桶数。
    image.png

总而言之,当集合中元素的数量极多时,不仅查找会变得很慢,而且占用的空间也会大到无法想象。

比如说,一个email提供商,需要过滤来自发送垃圾邮件的人的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址,全世界少说也有几十亿个发垃圾邮件的地址,将他们都存起来则需要大量的网络服务器。如果用哈希表,每存储一亿 个 email 地址, 就需要 1.6GB 的内存(用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹(详见), 然后将这些信息指纹存入哈希表,由于哈希表的存储效率一般只有 50%,因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB, 即十六亿字节的内存)。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机,一般服务器是无法存储的 -- Google黑板报

又比如,一个网站有 100 亿 url 存在一个黑名单中,每条 url 平均 64 字节。问这个黑名单要怎么存?若此时随便输入一个 url,如何判断该 url 是否在这个黑名单中?

那么有没有其他的方式来实现同样的事呢?本文介绍一下布隆过滤器及其原理和应用。

2 布隆过滤器介绍

2.1 什么是布隆过滤器

首先,我们需要了解布隆过滤器的概念。
布隆过滤器(Bloom Filter)是一个叫做 Bloom 的老哥于1970年提出的。我们可以把它看作由:

  • 二进制向量(或者说位数组)
  • 一系列随机映射函数(哈希函数)

两部分组成的数据结构。
image.png

位数组中的每个元素都只占用 1 bit ,并且每个元素只能是 0 或者 1。这样申请一个 100w 个元素的位数组只占用 1000000Bit / 8 = 125000 Byte = 125000/1024 kb ≈ 122kb 的空间。
相比于我们平时常用的的 List、Map 、Set 等数据结构,它占用空间更少并且效率更高。

布隆过滤器(bloom filter)可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除元素困难

一般的布隆过滤器会提供两个方法:Test 和 Add。

Add用来添加元素到集合内,这里没有删除,在讲到原理部分时会比较清楚的讲解为什么布隆过滤器删除元素困难。

Test用来确认某个元素是否在集合内。如果它返回:

  • false,那么这个元素一定不在集合内。
  • true,那么这个元素只是有可能在集合里面

部分不在集合内的元素会被误判在集合内,布隆过滤器的假正率(False positive rate)用来描述这一概率,其随着数据的增大而增大,同时也和所使用的hash函数有关。
image.png

总结:一个名叫 Bloom 的人提出了一种来检索元素是否在给定大集合中的数据结构,这种数据结构是高效且性能很好的,但缺点是具有一定的错误识别率和删除难度。并且,理论情况下,添加到集合中的元素越多,误报的可能性就越大。

2.2 布隆过滤器的基本原理

布隆过滤器的原理是,当一个元素被加入集合时,通过K个hash函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。

布隆过滤器是一个 bit 向量,长这样:
image.png

往布隆过滤器中添加一个元素时,我们将这个值传入 k 个hash函数,然后将结果位置bit置为1,在图中例子向量或者说数组的长度为50,使用3个hash函数。
image.png

当我们要判断一个元素是否在布隆过滤器中时,我们把这个值传入k个hash函数中获得映射的k个点。这一次我们确认下是否所有的点都被置为1了,如果有某一位没有置为1则这个元素肯定不在集合中。如果都在那这个元素就有可能在集合中。
image.png

看完原理后我们就知道了为什么布隆过滤器中有可能误判以及元素越多假正率(误判几率)越大,因为随着增加的值越来越多,被置为 1 的 bit 位也会越来越多,这样某个值即使没有被存储过,但是有可能元素的hash函数返回的k个 bit 位都被其他值置位了 1 ,那么程序还是会判断这个值存在。
image.png

同时hash函数的个数也需要权衡,个数越多则布隆过滤器 bit 位置位 1 的速度越快,且布隆过滤器的效率越低;但是如果太少的话,那我们的误报率会变高。
image.png

关于如何选择合适的hash函数个数k和布隆过滤器长度m,经验公式如下
image.png

详情可在Probabilistic Data structures: Bloom filter中了解。

3 布隆过滤器的常用使用场景

3.1 减少缓存穿透,防止缓存雪崩

image.png

  • 1、离线数据加载到布隆过滤器
  • 2、通过布隆过滤器查询、过滤
  • 3、布隆过滤器不存在,直接返回
  • 4、布隆过滤器存在,缓存不存在,查询数据库
  • 5、数据库返回

3.2 减少磁盘IO

用布隆过滤器减少磁盘IO或者网络请求(都是代价很高的操作)查找不存在的key的时候。

布隆过滤器返回false那么这个值肯定不在

因为一旦一个值必定不存在的话,我们可以不用进行后续昂贵的查询请求。如果它在,那么我们就去做查找,由于误判率不会太高所以这种代价一般也能承受。

  • Google 著名的分布式数据库 Bigtable 使用了布隆过滤器来查找不存在的行或列,以减少磁盘查找的IO次数
  • 在很多Key-Value系统中也使用了布隆过滤器来加快查询过程,如 Hbase,Accumulo,一般而言,Value 保存在磁盘中,访问磁盘需要花费大量时间,然而使用布隆过滤器

3.3 减少网络请求

  • 比如高并发秒杀系统中抢红包系统中判断用户是否今天已领取红包
  • 在爬虫系统中,我们需要对URL进行去重,已经爬过的网页就可以不用爬了。但是URL太多了,几千万几个亿,如果用一个集合装下这些URL地址那是非常浪费空间的。这时候就可以考虑使用布隆过滤器。它可以大幅降低去重存储消耗,只不过也会使得爬虫系统错过少量的页面。

3.4 垃圾邮件分类

  • 邮箱系统的垃圾邮件过滤功能也普遍用到了布隆过滤器,因为用了这个过滤器,所以平时也会遇到某些正常的邮件被放进了垃圾邮件目录中,这个就是误判所致,概率很低。

4 布隆过滤器的实现方案

4.1 手动实现布隆过滤器

如果你想要手动实现一个的话,你需要:

  • 一个合适大小的位数组保存数据
  • 几个不同的哈希函数
  • 添加元素到位数组(布隆过滤器)的方法实现
  • 判断给定元素是否存在于位数组(布隆过滤器)的方法实现。
public class MyBloomFilter {

    /**
     * 位数组的大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;
    /**
     * 通过这个数组可以创建 6 个不同的哈希函数
     */
    private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};

    /**
     * 位数组。数组中的元素只能是 0 或者 1
     */
    private BitSet bits = new BitSet(DEFAULT_SIZE);

    /**
     * 存放包含 hash 函数的类的数组
     */
    private SimpleHash[] func = new SimpleHash[SEEDS.length];

    /**
     * 初始化多个包含 hash 函数的类的数组,每个类中的 hash 函数都不一样
     */
    public MyBloomFilter() {
        // 初始化多个不同的 Hash 函数
        for (int i = 0; i < SEEDS.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    /**
     * 添加元素到位数组
     */
    public void add(Object value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    /**
     * 判断指定元素是否存在于位数组
     */
    public boolean contains(Object value) {
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    /**
     * 静态内部类。用于 hash 操作!
     */
    public static class SimpleHash {

        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        /**
         * 计算 hash 值
         */
        public int hash(Object value) {
            int h;
            return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
        }

    }
}

测试:

String value1 = "https://javaguide.cn/";
String value2 = "https://github.com/Snailclimb";
MyBloomFilter filter = new MyBloomFilter();
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
filter.add(value1);
filter.add(value2);
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
Output:
false
false
true
true

测试:

Integer value1 = 13423;
Integer value2 = 22131;
MyBloomFilter filter = new MyBloomFilter();
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
filter.add(value1);
filter.add(value2);
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
Output:
false
false
true
true

4.2 Guava中自带的布隆过滤器

自己实现的目的主要是为了让自己搞懂布隆过滤器的原理,Guava 中布隆过滤器的实现算是比较权威的,所以实际项目中我们不需要手动实现一个布隆过滤器。
首先我们需要在项目中引入 Guava 的依赖:

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

实际使用如下:
我们创建了一个最多存放 最多 1500个整数的布隆过滤器,并且我们可以容忍误判的概率为百分之(0.01)

// 创建布隆过滤器对象
BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(),1500,0.01);
// 判断指定元素是否存在
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
// 将元素添加进布隆过滤器
filter.put(1);
filter.put(2);
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));

在我们的示例中,当mightContain() 方法返回true时,我们可以99%确定该元素在过滤器中,当过滤器返回false时,我们可以100%确定该元素不存在于过滤器中。

Guava 提供的布隆过滤器的实现还是很不错的(想要详细了解的可以看一下它的源码实现),但是它有一个重大的缺陷就是只能单机使用(另外,容量扩展也不容易),而现在互联网一般都是分布式的场景。为了解决这个问题,我们就需要用到 Redis 中的布隆过滤器了。

4.3 Redis 中的布隆过滤器

注:
[也借助Redis Bitmap实现简单的布隆过滤器](https://www.jianshu.com/p/c2defe549b40)

Redis v4.0 之后有了 Module(模块/插件) 功能,Redis Modules 让 Redis 可以使用外部模块扩展其功能 。布隆过滤器就是其中的 Module。详情可以查看 Redis 官方对 Redis Modules 的介绍 :redis.io/modules。

另外,官网推荐了一个 RedisBloom 作为 Redis 布隆过滤器的 Module,地址:github.com/RedisBloom/…redis-lua-scaling-bloom-filter
(lua 脚本实现):github.com/erikdubbelb…pyreBloom
(Python中的快速Redis 布隆过滤器) :github.com/seomoz/pyre…
RedisBloom 提供了多种语言的客户端支持,包括:Python、Java、JavaScript 和 PHP。

使用Docker安装

如果我们需要体验 Redis 中的布隆过滤器非常简单,通过 Docker 就可以了!我们直接在 Google 搜索docker redis bloomfilter 然后在排除广告的第一条搜素结果就找到了我们想要的答案(这是我平常解决问题的一种方式,分享一下),具体地址:hub.docker.com/r/redislabs… (介绍的很详细 )。

➜  ~ docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest
➜  ~ docker exec -it redis-redisbloom bash
root@21396d02c252:/data# redis-cli
127.0.0.1:6379>

常用命令一览

注意: key:布隆过滤器的名称,item : 添加的元素。
  • BF.ADD:将元素添加到布隆过滤器中,如果该过滤器尚不存在,则创建该过滤器。
    格式:BF.ADD
  • BF.MADD : 将一个或多个元素添加到“布隆过滤器”中,并创建一个尚不存在的过滤器。该命令的操作方式BF.ADD与之相同,只不过它允许多个输入并返回多个值。
    格式:BF.MADD
    [item ...] 。
  • *BF.EXISTS * : 确定元素是否在布隆过滤器中存在。
    格式:BF.EXISTS
  • BF.MEXISTS : 确定一个或者多个元素是否在布隆过滤器中存在
    格式:BF.MEXISTS
    [item ...]。

另外,BF.RESERVE 命令需要单独介绍一下:
这个命令的格式如下:
BF.RESERVE
[EXPANSION expansion]。
下面简单介绍一下每个参数的具体含义:

  • key:布隆过滤器的名称
  • error_rate :误报的期望概率。这应该是介于0到1之间的十进制值。例如,对于期望的误报率0.1%(1000中为1)
    ,error_rate应该设置为0.001。该数字越接近零,则每个项目的内存消耗越大,并且每个操作的CPU使用率越高。
  • capacity: 过滤器的容量。当实际存储的元素个数超过这个值之后,性能将开始下降。实际的降级将取决于超出限制的程度。随着过滤器元素数量呈指数增长,性能将线性下降。
127.0.0.1:6379> bf.reserve user 0.01 100
OK

可选参数

  • expansion:如果创建了一个新的子过滤器,则其大小将是当前过滤器的大小乘以expansion。默认扩展值为2。这意味着每个后续子过滤器将是前一个子过滤器的两倍。

实际使用

127.0.0.1:6379> BF.ADD myFilter java
(integer) 1
127.0.0.1:6379> BF.ADD myFilter javaguide
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter java
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter javaguide
(integer) 1
127.0.0.1:6379> BF.EXISTS myFilter github
(integer) 0

4.4 Guava布隆过滤器与Redis布隆过滤器对比

  • Guava布隆过滤器的缺点:
    基于JVM内存的一种布隆过滤器重启即失效本地内存无法用在分布式场景不支持大数据量存储

  • Redis布隆过滤器:
    可扩展性Bloom过滤器:一旦Bloom过滤器达到容量,就会在其上创建一个新的过滤器不存在重启即失效或者定时任务维护的成本:基于Google实现的布隆过滤器需要启动之后初始化布隆过滤器缺点:需要网络IO,性能比Google布隆过滤器低

5 参考文献

java  redis 
更新时间:2020-08-26 18:14:21

本文由 清水河恶霸 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:http://ql.magic-seven.top/2020/08/14/布隆过滤器.html
最后更新:2020-08-26 18:14:21

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×