面试题：海量数据处理利器-布隆过滤器

浅浅的花香味﹌ 2024-04-06 13:51 87阅读 0赞

### 概念 ###

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为`O(n), O(logn), O(1)`。这个时候，布隆过滤器就应运而生。  
布隆过滤器（Bloom Filter）是1970年由布隆提出的。布隆过滤器其实就是一个很长的二进制向量和一系列随机映射函数。可以用于`快速检索一个元素是否在一个集合中出现`的方法。

### 原理 ###

如果想判断一个元素是不是在一个集合里，我们一般想到的是将所有元素保存起来，然后通过比较确定。我们熟悉的链表，树等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢。不过世界上还有一种叫作散列表（又叫哈希表）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列中的一个点。这样一来，我们只要看看这个点是不是 1 就知道可以集合中有没有它了。这其实就是布隆过滤器的基本思想。

Hash算法面临的问题就是hash冲突。假设 Hash 函数是良好的，如果我们的位阵列长度为 m 个点，那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳 m/100 个元素。显然这就不叫空间有效了（Space-efficient）。解决方法：就是**使用多个 Hash算法**，`如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，有一定可能性它们在说谎，虽然概率比较低`。

算法：

1.  首先需要k个hash函数，每个函数可以把key散列成为1个整数
2.  初始化时，需要一个长度为n比特的数组，每个比特位初始化为0
3.  某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1
4.  判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。

![16d7d903bd316db1707082bc04f2f340.png][]

其优点：

1.  空间效率和查询时间都比一般的算法要好的多,比如增加和查询元素的时间复杂为O(N)
2.  由于不需要存储key，所以特别节省存储空间。
3.  保密性强，布隆过滤器不存储元素本身~~

其缺点：

1.  由于采用hash算法，可能出现hash冲突，导致有一定的**误判率**，但是可以通过调整参数来降低

> 布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。

1.  无法获取元素本身
2.  由于hash算法导致hash冲突必然存在，所以删除元素是很困难的，而且删掉元素会导致**误判率**增加。

### 布隆过滤器的使用场景 ###

我们可以充分利用布隆过滤器的特点：**如果布隆过滤器说有一个说元素不在集合中，那肯定就不在。如果布隆过滤器说在，有一定可能性它在说谎**。

1.  比较热门的场景就是：解决Redis缓存穿透问题

> 缓存穿透: 指用户的请求去查询缓存和数据库中都不存在的数据，可用户还是源源不断的发起请求，导致每次请求都会打到数据库上，从而压垮数据库

1.  邮件过滤，使用布隆过滤器来做邮件黑名单过滤，还有重复推荐内容过滤，网址过滤, web请求访问拦截器，等等
2.  许多数据库内置布隆过滤器，用于判断数据是否存在，可以减少数据库很多不必要的磁盘IO操作

### 简单模拟布隆过滤器 ###

我们来看一个例子：

public class MyBloomFilter {
    
        /**
         * 一个长度为10 亿的比特位
         */
        private static final int DEFAULT_SIZE = 256 << 22;
    
        /**
         * 为了降低错误率，使用加法hash算法，所以定义一个8个元素的质数数组
         */
        private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};
    
        /**
         * 相当于构建 8 个不同的hash算法
         */
        private static HashFunction[] functions = new HashFunction[seeds.length];
    
        /**
         * 初始化布隆过滤器的 bitmap
         */
        private static BitSet bitset = new BitSet(DEFAULT_SIZE);
    
        /**
         * 添加数据
         *
         * @param value 需要加入的值
         */
        public static void add(String value) {
            if (value != null) {
                for (HashFunction f : functions) {
                    //计算 hash 值并修改 bitmap 中相应位置为 true
                    bitset.set(f.hash(value), true);
                }
            }
        }
    
        /**
         * 判断相应元素是否存在
         * @param value 需要判断的元素
         * @return 结果
         */
        public static boolean contains(String value) {
            if (value == null) {
                return false;
            }
            boolean ret = true;
            for (HashFunction f : functions) {
                ret = bitset.get(f.hash(value));
                //一个 hash 函数返回 false 则跳出循环
                if (!ret) {
                    break;
                }
            }
            return ret;
        }
    
        /**
         * 模拟用户在不在线。。。
         */
        public static void main(String[] args) {
    
            for (int i = 0; i < seeds.length; i++) {
                functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);
            }
    
            // 添加1亿数据
            for (int i = 0; i < 100000000; i++) {
                add(String.valueOf(i));
            }
            String id = "123456789";
            add(id);
    
            System.out.println(contains(id));   //结果： true
            System.out.println("" + contains("234567890"));  //结果： false
        }
    }
    
    class HashFunction {
    
        private int size;
        private int seed;
    
        public HashFunction(int size, int seed) {
            this.size = size;
            this.seed = seed;
        }
    
        public int hash(String value) {
            int result = 0;
            int len = value.length();
            for (int i = 0; i < len; i++) {
                result = seed * result + value.charAt(i);
            }
            int r = (size - 1) & result;
            return (size - 1) & result;
        }
    }

我们平时学习的时候可以去实现一下算法，但实际开发过程中，一般不推荐重复造轮子，简单的实现布隆过滤器, 我们一般可以用`google.guava`库

### Guava布隆过滤器 ###

首先引入依赖：

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

举个例子：

// 创建布隆过滤器对象，预计包含的数据量：2000个，和允许的误差值0.01
    BloomFilter<Integer> filter = BloomFilter.create(
            Funnels.integerFunnel(),
            2000,
            0.01);
    
    System.out.println(filter.mightContain(10));// 判断指定元素是否存在
    System.out.println(filter.mightContain(20));
    filter.put(10);// 将元素添加进布隆过滤器
    filter.put(20);
    System.out.println(filter.mightContain(10));// 判断指定元素是否存在
    System.out.println(filter.mightContain(20));

其中：当`mightContain()`方法返回`_true_`时，我们可以大概率确定该元素在过滤器中，但当过滤器返回`_false_`时，我们可以100％确定该元素不存在于过滤器中。  
布隆过滤器的 允许的误差值 越小，需要的存储空间就越大，对于不需要过于精确的场景，允许的误差值 设置稍大一点也可以。  
Guava 提供的布隆过滤器的实现还是很不错的,但是随着微服务、分布式的不断发展，对于微服务多实例的场景下就不太适用了，只适合单机，解决方案是：一般是借助Redis中的布隆过滤器

### Redis布隆过滤器 ###

Redis 4.0 的时候官方提供了插件机制，布隆过滤器正式登场。以下网站可以下载官方提供的已经编译好的可拓展模块。  
[https://redis.com/redis-enterprise-software/download-center/modules][https_redis.com_redis-enterprise-software_download-center_modules]

这边使用docker安装,自己挑选合适的镜像

~ docker pull redislabs/rebloom:latest
    ~ docker run -p 6379:6379 --name redis-bloom redislabs/rebloom:latest
    ~ docker exec -it redis-bloom bash 
    root@113d012d35:/data# redis-cli
    127.0.0.1:6379>

进入容器内部后，常用的命令：

//-------------------------常用命令
    BF.ADD --添加一个元素到布隆过滤器
    BF.EXISTS --判断元素是否在布隆过滤器
    BF.MADD --添加多个元素到布隆过滤器
    BF.MEXISTS --判断多个元素是否在布隆过滤器
    
    //-------------------------具体操作
    
    127.0.0.1:6379> BF.ADD myFilter hello
    (integer) 1
    127.0.0.1:6379> BF.ADD myFilter people
    (integer) 1
    127.0.0.1:6379> BF.EXISTS myFilter hello
    (integer) 1
    127.0.0.1:6379> BF.EXISTS myFilter people
    (integer) 1
    127.0.0.1:6379> BF.EXISTS myFilter github
    (integer) 0

### 布谷鸟过滤器 ###

为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器应运而生。论文[《Cuckoo Filter：Better Than Bloom》][Cuckoo Filter_Better Than Bloom]作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。但是其删除并不完美，存在误删的概率，还存在插入复杂度比较高等问题。由于使用较少，本文就不过多介绍了，感兴趣的自行了解[文章][Link 1]。

[16d7d903bd316db1707082bc04f2f340.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/f64463609218460ca5d1acd0232e469e.png
[https_redis.com_redis-enterprise-software_download-center_modules]: https://redis.com/redis-enterprise-software/download-center/modules/
[Cuckoo Filter_Better Than Bloom]: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
[Link 1]: https://www.cnblogs.com/zhaodongge/p/15067657.html