技术大道上开拓前进

高并发系统一定要考虑的 Bloom Filter 布隆过滤器

Posted on Mar 10, 2020 By Holy place

开篇思考

  1. 你能想到哪些方式判断一个元素是否存在集合中？
  2. 布隆过滤器并不存储数据本身，那么是怎么做到过滤的？
  3. 布隆过滤器实现？参数配置？

一般我们用来判断一个元素是否存在，会想到用 List，Map，Set 等，会将元素先保存下来，然后进行筛选。
但是这样的形式都有一个弊端就是一定要保存数据才行，可是我们仅仅想知道是否存在数据，并不要求获取实际数据， 这时候就会觉得这种方式实在是浪费空间。

什么情况下我们只需要判断是否存在这个元素呢？
在系统设计的时候，我们会考虑大量并发的形式，但是很多请求可能是在访问不存在的数据， 那么我们就没有必要继续这个请求，可以在 API 网关层就直接过滤掉。

Bloom Filter 布隆过滤器原理

Bloom filter 是由 Howard Bloom 在 1970 年提出的二进制向量数据结构，它具有很好的空间和时间效率， 被用来检测一个元素是不是集合中的一个成员。

布隆过滤器实现是不保存数据本身，而是通过 K 个 hash 函数来计算在 byte[] 数组中的存放位置， 并把这个位置的值设置为 1， 而这个 K 到底是多少个呢，要根据公式来算出，待会列出。
除了这个 K 值，我们还要计算 byte[] 数组的长度 m ，下面一并列出计算公式：

m 值计算

  • fpp : 误判率参数，(must be 0 < fpp < 1)
  • n ：预估的需要过滤的总数量
  • ln ：求对数，不会的把高中老师的名字写下来

K 值计算

  • m ：数组长度
  • n ：预估的需要过滤的总数量

下面我们以数字 11 为例来使用，有个网站可以测试布隆过滤器， 在线测试布隆

11 过滤

布隆过滤器的优点、缺点

优点：

  • 节省空间，不用保存所有数据，知识通过 hash 值来计算位置，并通过 byte[] 记录下来。
  • 速度快，时间复杂度低 O(1);

缺点：

  • 精度低，假设：a 计算的位置 1 ，3 ；b 计算的位置 5，7；c 计算的位置 1，7，那么 c 一定存在吗？
  • 不能直接删除，因为想要删除就要把对应的位置置为 0 ，如果这样做，可能会影响其他值的过滤。

11 过滤

# 布隆过滤器实现

这个其实在 google guava 包中有现成的实现，不用我们自己去实现。我们看看是怎么实现的；

    /**
    * 计算 bit 数组的长度公式
    * n ： 预估数据量
    * p ： 误差率 0-1
    */
    @VisibleForTesting
    static long optimalNumOfBits(long n, double p) {
        if (p == 0.0D) {
            p = 4.9E-324D;
        }

        return (long)((double)(-n) * Math.log(p) / (Math.log(2.0D) * Math.log(2.0D)));
    }

    /**
    * 计算 hash 函数个数的方法
    * n ： 预估数据量
    * m ： bit 数组长度
    */
    @VisibleForTesting
    static int optimalNumOfHashFunctions(long n, long m) {
        return Math.max(1, (int)Math.round((double)(m / n) * Math.log(2.0D)));
    }

动手玩一玩

  • expectedInsertions 代表预估数量，越大越准确，在下面的例子中，可以自己随意设置 p 值，过小会发现后面会返回 true
  • fpp ： 误差率 0-1

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

public class BloomFilterTest {

    public static void main(String[] args) {

        int expectedInsertions = 800000000;
        double fpp = 0.00001;

        BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), expectedInsertions, fpp);
        int i = 10000;
        while (i > 1){
            bloomFilter.put("aa" + i);
            System.out.println(bloomFilter.mightContain("ab" + i));
            i--;
        }

    }
}

喜欢文章请关注我

程序领域
点击关注+转发，私信发送【面试】或者【资料】可以收获更多资源

公众号