布隆过滤器的那点事

布隆过滤器-Bloom Filter

学习前经典3问，what，why，how；它是什么，为什么用它，怎么用它

是什么

布隆过滤器是一个节省空间的概率型数据结构。设计目的是为了判断一个元素是否在一个集合中。结果只有两种，1是可能存在，2是一定不存在。参考wiki

• 执行流程

前置知识：
1.比特数组每一个位置元素只可能是0或者1，而且布隆过滤器将数据结构都私有化，无法外部访问；
2.哈希函数可以选用murmur3,md5,sha1,crc等，可参考Hashing类；

【插入】对每一个输入依次执行k个哈希函数，并将结果映射到[0,m)上，得到k个值，这k个值对应比特数组的索引位，然后我们将这k个值插入到比特数组中对应的位置，即将默认的0或者已经修改成1的值变更为1。
【查询】对每一个输入一次执行k个哈希函数，并将结果映射到[0,m)上，得到k个值，这k个值对应比特数组的索引位，依次检查这k个值对应比特数组保存的值，全是1返回true，否则返回false。

查询存在误判，而且随着比特数组越来越满，误判概率也越来越大；

• 误判率Ffp

误判率(false positive probability)=判断错误/预测总数，布隆过滤器有一个可预测的误判断率计算

Pfp ≈ (1 - e^{-kn/m})^k

• 比特数组长度m

布隆过滤器的长度m可以根据给定或者期望的误判率FFP和预估添加的元素个数n计算得到

m = - (n·lnPfp) / ((ln2)^2)

• hash函数的个数k

哈希函数的格式可以通过比特数组长度和预估数据量进行估计

k = ln2 * (m / n)

例
目前公司日志量级激增，发现是由于大量异常访问导致，所以需要添加一个uid的黑名单过滤，估计黑名单有1千万个uid，如果过滤不完全可以后面再数据处理。要求误判率在0.1以下。
已知：

n = 1 * 10^7;
Ffp = 0.1

求解：

m = - (1 * 10^7 * ln0.1) / (ln2^2) ≈ 5 * 10^7;
k = ln2 * (5 * 10^7 / 1 * 10^7) = 3.5 = 4

为什么用它

1. 优点是空间效率和查询时间都比一般的算法要好的多；
2. 缺点是有一定的误识别率，而且删除困难(Counting_Bloom_filter可以)；
3. 实际应用中基本也是实时分桶来处理布隆过滤器(既可以放在本地内存也可以放在redis等内存系统)；
4. 可以根据输入的特性，针对性的设计hash函数，可优化性能；

有哪些实践

这些实践都有一个共同的特点，那就是数据量大但是对准确性有一定的容忍度

1. 大数据中广告等业务对DAU等准确性要求不是很高的实时统计场景；
2. 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；
3. URL去重或者黑名单系统；
4. 缓解缓存穿透的问题，减少没必要的Redis或数据库查询请求；
5. Medium使用布隆过滤器避免推荐给用户已经读过的文章

缓存穿透：大量本身就无数据的请求越过缓存(即缓存没有命中)，直接请求数据库，而我们添加布隆过滤器相当于是在缓存请求前面加了一个筛子，将肯定不存在的请求直接过滤掉，缓解缓存穿透引起的压力

如何使用

1.布隆过滤器有很多实现和优化，由Google开发著名的Guava库就提供了布隆过滤器的实现。在基于Maven的Java项目中要使用Guava提供的布隆过滤器，只需要引入以下依赖(可以从maven repository中查找稳定的依赖)：

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

代码

public static void main(String[] args) {
    // 创建布隆过滤器
    // Funnels是如何计算哈希值的抽象，即如何根据输入object将其转换为hashcode，可自定义也可使用内置,自定义自己实现funnel方法即可
    BloomFilter<String> bf = BloomFilter.create(
            Funnels.stringFunnel(Charsets.UTF_8), 10000, 0.01);


    // 将数据通过单点的方式添加，也可批量添加，比如布隆过滤器重构时
    for (int i = 0; i < 10000; i++) {
        // 添加一个元素可查看BloomFilterStrategies.put方法
        bf.put(i + "common log body");
    }

    // 统计一下确定存在的数据是否存在误判
    int wrongJudge = 0;
    for (int i = 0; i < 10000; i++) {
        // 对于确定存在的，如果判断不存在即为误判
        if (!bf.mightContain(i + "common log body")) wrongJudge++;
    }
    System.out.println("全部都是确定存在，判断错误的个数: " + wrongJudge);

    // 统计一下确定不存在的数据的误判数量
    int wrongJudge1 = 0;
    for (int i = 10000; i < 20000; i++) {
        // 对于确定不存在的，如果判断存在即为误判
        if (bf.mightContain(i + "common log body")) wrongJudge1++;
    }
    System.out.println("全部都是确定不存在，判断错误的个数: " + wrongJudge1);
}

运行结果

查看运行结果可以看到，真实误判率=110/10000=0.011，和估计的误判率相差无几

全部都是确定存在，判断错误的个数: 0
全部都是确定不存在，判断错误的个数: 110

代码源码分析

1.创建布隆过滤器，根据之前的公式计算估计的比特数组长度和哈希函数的个数

/** 创建布隆过滤器，需要参数funnel+strategy,expectedInsertions,fpp,numBits,numHashFunctions */
static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
    // 根据预估数据量n和误判率Ffp估计比特数组的长度m
    // (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    long numBits = optimalNumOfBits(expectedInsertions, fpp);
    // 根据预估数据量n和比特数组的长度m估计哈希函数的个数k，如果是小数，四舍五入取整
    // Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    // 根据计算结果创建布隆过滤器
    return new BloomFilter<T>(new LockFreeBitArray(numBits), numHashFunctions, funnel, strategy);

2.向布隆过滤器中添加元素
BloomFilterStrategies.put

public <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) {
  // 比特数组的长度
  long bitSize = bits.bitSize();
  // 根据规则计算哈希值
  long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();
  int hash1 = (int) hash64;
  int hash2 = (int) (hash64 >>> 32);// 无符号右移32位

  boolean bitsChanged = false;
  for (int i = 1; i <= numHashFunctions; i++) {
    // 这里根据哈希值模拟多个哈希函数的结果，
    // 并不是之前想的k个哈希函数分别作用输入的key,得到k个索引值
    int combinedHash = hash1 + (i * hash2);
    // Flip all the bits if it's negative (guaranteed positive number)
    if (combinedHash < 0) {
      combinedHash = ~combinedHash;
    }
    bitsChanged |= bits.set(combinedHash % bitSize);
  }
  return bitsChanged;
}

3.检查布隆过滤器是否含有某元素
BloomFilterStrategies.mightContain
流程和添加元素是一样，只是将set方法换成了get方法，只要有一个不存在即返回false

别人怎么用

• 大数据实时日活计算之Bloom Filter(58同城)

在上一个版本判断用户是否存在时，使用多个位置存储元素，就会有多次需要访问Redis；为了减少对Redis访问；可以看到，Bloom Filter使用的多个hash算出的每个位置，其实对应一个二进制数，所以我们只需把这个二进制数据转化十进制，然后根据这数字所在位置是否为1来判断用户是否存在，这样只需要访问redis一次即可(需要注意这个值大小是否越界)