布隆过滤器 Bloom Filter

一 前言

假如有一个15亿用户的系统，每天有几亿用户访问系统，要如何快速判断是否为系统中的用户呢？

• 方法一，将15亿用户存储在数据库中，每次用户访问系统，都到数据库进行查询判断，准确性高，但是查询速度会比较慢。
• 方法二，将15亿用户缓存在Redis内存中，每次用户访问系统，都到Redis中进行查询判断，准确性高，查询速度也快，但是占用内存极大。即使只存储用户ID，一个用户ID一个字符，则15亿*8字节=12GB，对于一些内存空间有限的服务器来说相对浪费。

还有对于网站爬虫的项目，我们都知道世界上的网站数量及其之多，每当我们爬一个新的网站url时，如何快速判断是否爬虫过了呢？还有垃圾邮箱的过滤，广告电话的过滤等等。如果还是用上面2种方法，显然不是最好的解决方案。

再者，查询是一个系统最高频的操作，当查询一个数据，首先会先到缓存查询（例如Redis），如果缓存没命中，于是到持久层数据库（mongo，mysql等）查询，发现也没有此数据，于是本此查询失败。如果用户很多的时候，并且缓存都没命中，进而全部请求了持久层数据库，这就给数据库带来很大压力，严重可能拖垮数据库。俗称缓存穿透。

可能大家也听到另一个词叫缓存击穿，它是指一个热点key，不停着扛着高并发，突然这个key失效了，在失效的瞬间，大量的请求缓存就没命中，全部请求到数据库。

对于以上这些以及类似的场景，如何高效的解决呢？针对此，布隆过滤器应运而生了。

二 布隆过滤器

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

二进制向量，简单理解就是一个二进制数组。这个数组里面存放的值要么是0，要么是1。

映射函数，它可以将一个元素映射成一个位阵列（Bit array）中的一个点。所以通过这个点，就能判断集合中是否有此元素。

基本思想

• 当一个元素被加入集合时，通过K个散列函数将这个元素映射到一个位数组中的K个点，把它们置为1。
• 检索某个元素时，再通过这K个散列函数将这个元素映射，看看这些位置是不是都是1就能知道集合中这个元素存不存在。如果这些位置有任何一个0，则该元素一定不存在；如果都是1，则被检元素很可能存在。

Bloom Filter跟单个哈希函数映射不同，Bloom Filter使用了k个哈希函数，每个元素跟k个bit对应。从而降低了冲突的概率。

优点

1. 二进制组成的数组，内存占用空间少，并且插入和查询速度很快，常数级别。
2. Hash函数相互之间没有必然联系，方便由硬件并行实现。
3. 只存储0和1，不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

缺点

1. 存在误差率。随着存入的元素数量增加，误算率随之增加。（比如现实中你是否遇到正常邮件也被放入垃圾邮件目录，正常短信被拦截）可以增加一个小的白名单，存储那些可能被误判的元素。
2. 删除困难。一个元素映射到bit数组的k个位置上是1，删除的时候不能简单的直接置为0，可能会影响其他元素的判断。因为其他元素的映射也有可能在相同的位置置为1。可以采用Counting Bloom Filter解决。

三 Redis实现

在Redis中，有一种数据结构叫位图，即bitmap。以下是一些常用的操作命令。

在Redis命令中，SETBIT key offset value，此命令表示将key对应的值的二进制数组，从左向右起，offset下标的二进制数字设置为value。

键k1对应的值为keke，对应ASCII码为107 101 107 101，对应的二进制为 0110 1011，0110 0101，0110 1011，0110 0101。将下标5的位置设置为1，所以变成 0110 1111，0110 0101，0110 1011，0110 0101。即 oeke。

GETBIT key offset命令，它用来获取指定下标的值。

还有一个比较常用的命令，BITCOUNT key [start end]，用来获取位图中指定范围值为1的个数。注意，start和end指定的是字节的个数，而不是位数组下标。

Redisson是用于在Java程序中操作Redis的库，利用Redisson我们可以在程序中轻松地使用Redis。Redisson这个客户端工具实现了布隆过滤器，其底层就是通过bitmap这种数据结构来实现的。

Redis 4.0提供了插件功能之后，Redis就提供了布隆过滤器功能。布隆过滤器作为一个插件加载到了Redis Server之中，给Redis提供了强大的布隆去重功能。此文就不细讲了，大家感兴趣地可到官方查看详细文档介绍。它又如下常用命令：

1. bf.add：添加元素
2. bf.madd：批量添加元素
3. bf.exists：检索元素是否存在
4. bf.mexists：检索多个元素是否存在
5. bf.reserve：自定义布隆过滤器，设置key，error_rate和initial_size

下面演示是在本地单节点Redis实现的，如果数据量很大，并且误差率又很低的情况下，那单节点内存可能会不足。当然，在集群Redis中，也是可以通过Redisson实现分布式布隆过滤器的。

引入依赖

<!-- https://mvnrepository.com/artifact/org.redisson/redisson -->
<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>3.13.6</version>
</dependency>

代码测试

package com.nobody;

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;

/**
 * @Description
 * @Author Mr.nobody
 * @Date 2021/3/6
 * @Version 1.0
 */
public class RedissonDemo {

    public static void main(String[] args) {

        Config config = new Config();
        config.useSingleServer().setAddress("redis://127.0.0.1:6379");
        // config.useSingleServer().setPassword("123456");

        RedissonClient redissonClient = Redisson.create(config);
        // 获取一个redis key为users的布隆过滤器
        RBloomFilter<Integer> bloomFilter = redissonClient.getBloomFilter("users");

        // 假设元素个数为10万
        int size = 100000;

        // 进行初始化，预计元素为10万，误差率为1%
        bloomFilter.tryInit(size, 0.01);

        // 将1至100000这十万个数映射到布隆过滤器中
        for (int i = 1; i <= size; i++) {
            bloomFilter.add(i);
        }

        // 检查已在过滤器中的值，是否有匹配不上的
        for (int i = 1; i <= size; i++) {
            if (!bloomFilter.contains(i)) {
                System.out.println("存在不匹配的值：" + i);
            }
        }

        // 检查不在过滤器中的1000个值，是否有匹配上的
        int matchCount = 0;
        for (int i = size + 1; i <= size + 1000; i++) {
            if (bloomFilter.contains(i)) {
                matchCount++;
            }
        }
        System.out.println("误判个数：" + matchCount);
    }
}

结果存在的10万个元素都匹配上了；不存在布隆过滤器中的1千个元素，有23个误判。

误判个数：23

四 Guava实现

布隆过滤器有许多实现与优化，Guava中就提供了一种实现。Google Guava提供的布隆过滤器的位数组是存储在JVM内存中，故是单机版的，并且最大位长为int类型的最大值。

• 使用布隆过滤器时，重要关注点是预估数据量n以及期望的误判率fpp。
• 实现布隆过滤器时，重要关注点是hash函数的选取以及bit数组的大小。

Bit数组大小选择

根据预估数据量n以及误判率fpp，bit数组大小的m的计算方式：

Guava中源码实现如下：

@VisibleForTesting
static long optimalNumOfBits(long n, double p) {
  if (p == 0) {
    p = Double.MIN_VALUE;
  }
  return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}

哈希函数选择

​哈希函数的个数的选择也是挺讲究的，哈希函数的选择影响着性能的好坏，而且一个好的哈希函数能近似等概率的将元素映射到各个Bit。如何选择构造k个函数呢，一种简单的方法是选择一个哈希函数，然后送入k个不同的参数。

哈希函数的个数k，可以根据预估数据量n和bit数组长度m计算而来：

Guava中源码实现如下：

@VisibleForTesting
  static int optimalNumOfHashFunctions(long n, long m) {
    // (m / n) * log(2), but avoid truncation due to division!
    return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
  }

引入依赖

<!-- https://mvnrepository.com/artifact/com.google.guava/guava -->
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>28.2-jre</version>
</dependency>

代码测试

package com.nobody;

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

/**
 * @Description
 * @Author Mr.nobody
 * @Date 2021/3/6
 * @Version 1.0
 */
public class GuavaDemo {

    public static void main(String[] args) {

        // 假设元素个数为10万
        int size = 100000;

        // 预计元素为10万，误差率为1%
        BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, 0.01);

        // 将1至100000这十万个数映射到布隆过滤器中
        for (int i = 1; i <= size; i++) {
            bloomFilter.put(i);
        }

        // 检查已在过滤器中的值，是否有匹配不上的
        for (int i = 1; i <= size; i++) {
            if (!bloomFilter.mightContain(i)) {
                System.out.println("存在不匹配的值：" + i);
            }
        }

        // 检查不在过滤器中的1000个值，是否有匹配上的
        int matchCount = 0;
        for (int i = size + 1; i <= size + 1000; i++) {
            if (bloomFilter.mightContain(i)) {
                matchCount++;
            }
        }
        System.out.println("误判个数：" + matchCount);

    }
}

结果存在的10万个元素都匹配上了；不存在布隆过滤器中的1千个元素，有10个误判。

误判个数：10

当fpp的值改为为0.001，即降低误差率时，误判个数为0个。

误判个数：0

分析结果可知，误判率确实跟我们传入的容错率差不多，而且在布隆过滤器中的元素都匹配到了。

源码分析

通过debug创建布隆过滤器的方法，当预计元素为10万个，fpp的值为0.01时，需要位数958505个，hash函数个数为7个。

当预计元素为10万个，fpp的值为0.001时，需要位数1437758个，hash函数个数为10个。

得出结论

• 容错率越大，所需空间和时间越小，容错率越小，所需空间和时间越大。
• 理论上存10万个数，一个int是4字节，即32位，需要320万位。如果使用HashMap存储，按HashMap50%的存储效率，需要640万位。而布隆过滤器即使容错率fpp为0.001，也才需要1437758位，可以看出BloomFilter的存储空间很小。

五 扩展知识点

假如有一台服务器，内存只有4GB，磁盘上有2个大文件，文件A存储100亿个URL，文件B存储100亿个URL。请问如何模糊找出两个文件的URL交集？如何精致找出两个文件的URL交集。

模糊交集：

借助布隆过滤器思想，先将一个文件的URL通过hash函数映射到bit数组中，这样大大减少了内存存储，再读取另一个文件URL，去bit数组中进行匹配。

精致交集：

对大文件进行hash拆分成小文件，例如拆分成1000个小文件（如果服务器内存更小，则可以拆分更多个更小的文件），比如文件A拆分为A1，A2，A3...An，文件B拆分为B1，B2，B3...Bn。而且通过相同的hash函数，相同的URL一定被映射到相同下标的小文件中，例如A文件的www.baidu.com被映射到A1中，那B文件的www.baidu.com也一定被映射到B1文件中。最后再通过求相同下标的小文件（例如A1和B1）（A2和B2）的交集即可。