布隆过滤器 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实现分布式布隆过滤器的。

引入依赖

<!-- //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)));
  }

引入依赖

<!-- //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)的交集即可。

欢迎关注微信公众号:“Java之言”技术文章持续更新,请持续关注……

  • 第一时间学习最新技术文章
  • 领取最新技术学习资料视频
  • 最新互联网资讯和面试经验