关于java:搞定面试官系列避免缓存穿透的利器之Bloom-Filter

7次阅读

共计 4502 个字符，预计需要花费 12 分钟才能阅读完成。

在开发或者面试过程中，时常遇到过海量数据须要查问，秒杀时缓存击穿怎么防止等等这样的问题呢？把握好本篇介绍的知识点将有助于你在之后的工作、面试中策马奔流。

Bloom Filter，即传说中的布隆过滤器。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器能够 用于检索一个元素是否在一个汇合中。它的长处是空间效率和查问工夫都远远超过个别的算法，毛病是有肯定的误识别率和删除艰难。

布隆过滤器的原理是，<font color=”red”> 当一个元素被退出汇合时，通过 K 个散列函数将这个元素映射成一个位数组中的 K 个点，把它们置为 1。检索时，咱们只有看看这些点是不是都是 1 就（大概）晓得汇合中有没有它了：如果这些点有任何一个 0，则被检元素肯定不在；如果都是 1，则被检元素很可能在。</font> 这就是布隆过滤器的根本思维。

Bloom Filter 跟单哈希函数 Bit-Map 不同之处在于：Bloom Filter 应用了 k 个哈希函数，每个字符串跟 k 个 bit 对应。从而升高了抵触的概率。

Bloom Filter 在防止缓存击穿中的利用办法：简而言之就是先把咱们数据库的数据都加载到咱们的过滤器中，比方数据库的 id 当初有：1,2,3…,n，以下面的原理图为例，将 id 所有值通过三次 hash 之后，将 hash 失去的后果对应的中央由 0 批改为 1。这样做之后，每次申请过去通过 id 查问数据，如果缓存没有命中，再在过滤器中查问，通过同样的 hash 算法将申请的 id 值进行运算，取得三个索引值，如果有任何一个对应索引的值为 0，阐明 MySQL 中也不存在该 id，则间接报错返回。
<font color=”#E96900″> 试想想这样做的益处是什么？假如这样的一种场景，如果有 1000 个参数非法申请同时拜访（所谓参数非法是指数据库也不存在这类的值，比方 id 全为负值），缓存中都没有命中，此时如果这 1000 个申请同时打到 DB，数据库层是扛不住的，所以此时 Bloom Filter 就显得十分必要。</font>

Bloom Filter 之所以能做到在工夫和空间上的效率比拟高，是因为就义了判断的准确率、删除的便利性

存在误判，可能要查到的元素并没有在容器中，然而 hash 之后失去的 k 个地位上值都是 1。如果 Bloom Filter 中存储的是黑名单，那么能够通过建设一个白名单来存储可能会误判的元素。
删除艰难。一个放入容器的元素映射到 bit 数组的 k 个地位上是 1，删除的时候不能简略的间接置为 0，可能会影响其余元素的判断。

## Bloom Filter 实现
在实现 Bloom Filter 时，绕不过的两点就是 hash 函数的选取以及 bit 数组的大小。
对于一个确定的场景，咱们预估要存的数据量为 n，冀望的误判率为 fpp，而后须要计算咱们须要的 Bit 数组的大小 m，以及 hash 函数的个数 k，并抉择 hash 函数。
1 Bit 数组大小抉择
依据预估数据量 n 以及误判率 fpp，bit 数组大小的 m 的计算形式：

2 哈希函数抉择
由预估数据量 n 以及 bit 数组长度 m，能够失去一个 hash 函数的个数 k：
3 利用测试
本篇采纳的是 Google 的 Bloom Filter，首先须要引入 jar 包：

 <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>23.0</version>
 </dependency>

测试分两步：

1、往过滤器中放五千万个数，而后去验证这五千万个数是否能顺利通过过滤器；

2、另外找一万个不在过滤器中的数，查看 Bloom Filter 误判的几率。

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

/**
 * @author Carson Chu
 * @date 2020/3/15 14:48
 * @description 布隆过滤器测试样例
 */
public class BloomFilterTest {
    private static int capacity = 50000000;
    private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), capacity);
//    private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total, 0.001);

    public static void main(String[] args) {
        // 初始化 50000000 条数据到过滤器中
        for (int i = 0; i < capacity; i++) {bf.put(i);
        }

        // 匹配已在过滤器中的值，是否有匹配不上的
        for (int i = 0; i < capacity; i++) {if (!bf.mightContain(i)) {System.out.println("有好人逃脱了~~~");
            }
        }

        // 匹配不在过滤器中的 10000 个值，有多少匹配进去
        int count = 0;
        for (int i = capacity; i < capacity + 10000; i++) {if (bf.mightContain(i)) {count++;}
        }
        System.out.println("误命中的数量：" + count);
    }
}

运行后果示意，遍历这五千万个在过滤器中的数时，都被辨认进去了。一万个不在过滤器中的数，误伤了 297 个，误判率是 2.9% 左右。
如果想要升高误判率该怎么做呢，不要急，源码为咱们提供了这一机制：

@CheckReturnValue
    public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions) {return create(funnel, (long)expectedInsertions);
    }

    @CheckReturnValue
    public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {return create(funnel, expectedInsertions, 0.03D);
    }
 @CheckReturnValue
    public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions, double fpp) {return create(funnel, (long)expectedInsertions, fpp);
    }

    @CheckReturnValue
    public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp) {return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64);
    }
    
    /* create()办法的最底层实现 */
    @VisibleForTesting
    static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, BloomFilter.Strategy strategy) {Preconditions.checkNotNull(funnel);
        Preconditions.checkArgument(expectedInsertions >= 0L, "Expected insertions (%s) must be >= 0", new Object[]{expectedInsertions});
        Preconditions.checkArgument(fpp > 0.0D, "False positive probability (%s) must be > 0.0", new Object[]{fpp});
        Preconditions.checkArgument(fpp < 1.0D, "False positive probability (%s) must be < 1.0", new Object[]{fpp});
        Preconditions.checkNotNull(strategy);
        if (expectedInsertions == 0L) {expectedInsertions = 1L;}

        long numBits = optimalNumOfBits(expectedInsertions, fpp);
        int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);

        try {return new BloomFilter(new BitArray(numBits), numHashFunctions, funnel, strategy);
        } catch (IllegalArgumentException var10) {throw new IllegalArgumentException("Could not create BloomFilter of" + numBits + "bits", var10);
        }
    }

BloomFilter 一共四个 create 办法，不过最终都是走向第四个。看一下每个参数的含意：
funnel：数据类型 (个别是调用Funnels 工具类中的)
expectedInsertions：冀望插入的值的个数
fpp：错误率(默认值为 0.03)
strategy ：Bloom Filter 的算法策略

错误率越大，所需空间和工夫越小，错误率越小，所需空间和工夫约大。

cerberus 在收集监控数据的时候, 有的零碎的监控项量会很大, 须要查看一个监控项的名字是否曾经被记录到 DB 过了, 如果没有的话就须要写入 DB；
爬虫过滤已抓到的 url 就不再抓，可用 Bloom Filter 过滤；
垃圾邮件过滤。如果用哈希表，每存储一亿个 email 地址，就须要 1.6GB 的内存（用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹，而后将这些信息指纹存入哈希表，因为哈希表的存储效率个别只有 50%，因而一个 email 地址须要占用十六个字节。一亿个地址大概要 1.6GB，即十六亿字节的内存）。因而存贮几十亿个邮件地址可能须要上百 GB 的内存。而 Bloom Filter 只须要哈希表 1/ 8 到 1/4 的大小就能解决同样的问题。

布隆过滤器次要是在解决缓存穿透问题的时候引出来的，理解他的原理并能实习使用，在开发和面试中都是大有裨益的。

正文完