BloomFilter 缓存穿透

需求: BloomFilter 如何防止DB 回源攻击?

介绍: 

Bloomfilter: 布隆过滤器, 它是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率。即Bloom Filter报告某一元素存在于某集合中，但是实际上该元素并不在集合中。但是如果某个元素确实没有在该集合中，那么Bloom Filter 是不会报告该元素存在于集合中的，所以不会漏报。

Bloomfilter 算法逻辑: 

1.  首先需要k个hash函数，每个函数可以把key散列成为1个整数 

2. 初始化时，需要一个长度为n比特的数组，每个比特位初始化为0

3. 某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1

4. 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中

那么需要多少个K函数呢? 是不是觉得很神奇。那下面来算一算。K 是hash 函数的个数，m 是 位数组大小。插入元素个数 n

最优的 k 如下

k = (m/n)ln2.

接下来看看缓存:

缓存问题，一共有以下几类:

1. 缓存穿透: 请求去查询一条数据库中不存在的数据，就是数据库和缓存中都不存在，但是请求每次都会打到数据库上面去。

2. 缓存击穿: 大量的请求同时查询一个key的时候，此时key正好失效，就会导正大量的请求打到数据库中去

3.缓存雪崩: 某一时刻发生大规模缓存失效的情况， 比如缓存数据库crash掉了，导致大量请求打到数据库，DB撑不住就挂掉了。

4.热点数据失效: 设置缓存的时候，一般会设置失效时间，对于一些热点数据，当缓存失效的时候会存在大量的请求打到数据库中去，从而导致数据库崩掉。

根据上面·BloomFilter 的介绍，针对第一个问题，缓存穿透。可以把存在key的集合都放到BoolmFilter里面，再访问某个key的时候，先会去BloomFilter 查看有没有key，存在的话，再去查缓存，缓存没有再去查DB, BloomFilter 判断没有key，就直接返回。 

BloomFilter在时间和空间上占有优势，但是会有一定的错误率。

具体的使用，可以采用guava 的BloomFilter， 很简单。

private static int size = 1000000;

private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size);

    public static void main(String[] args) {

        for (int i = 0; i < size; i++) {

            bloomFilter.put(i);

        }

        long startTime = System.nanoTime(); // 获取开始时间

        //判断这一百万个数中是否包含29999这个数

        if (bloomFilter.mightContain(29999)) {

            System.out.println("命中了");

        }

        long endTime = System.nanoTime();  // 获取结束时间

        System.out.println("程序运行时间： " + (endTime - startTime) + "纳秒");

    }