缓存穿透和布隆过滤器

缓存在高并发情况下要应对三大异常情形：缓存雪崩、缓存击穿、和缓存穿透。

缓存雪崩和缓存击穿都是属于缓存失效时间的设置策略不当，导致大量的缓存key或少量但热点的缓存key在同一时刻失效，请求打到缓存后边的数据库上的现象。两者具有一定的相似性。概况来说就是“击穿是一人的雪崩，雪崩是一群人的击穿”。本质上是一个东西，都是缓存失效导致的。

而缓存穿透属于某些特殊的请求、比如黑客恶意攻击等，会去查询不存在的key，这样缓存和数据库都不会查询得到结果，但又实实在在的消耗了算力。所以应对缓存穿透的办法思想是拦截过滤，以一种识别机制快速判别这些无效的key、直接返回而不再去缓存和数据库查一遍了。

应对缓存穿透的办法
首先第一个想到的办法是可以把无效key枚举出来，然后添加到本地内存里，当请求试图查询这些key时马上返回。但是无效key的枚举太多了、或者干脆是不可枚举的，那么反过来，把全量的有效的key存起来一个布隆过滤器，然后去判定请求key在不在这个布隆过滤器里。如果不在则返回。在的话再去查缓存或数据库。举个例子，我们查询商品信息，对存量全量商品ID应用布隆过滤器，然后如果有新商品的话，就把新的ID添加到布隆过滤器里。

布隆过滤器的作用
1、缓存穿透，将所有可能存在的数据缓存放到布隆过滤器中，当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉。
2、网页爬虫对URL的去重，避免爬取相同的URL地址
3、反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱（垃圾短信）

布隆过滤器简单理解
由一个巨大的每一位都是0的bit数组和N个hash函数组成，给定一个key之后，添加到布隆过滤器的过程如下：
1、首先对这个key使用这些个hash函数分别算出对应的hash值。这些hash值对应到bit数组的下标。
2、然后把N个下标bit数组上的值都置成1。
3、数据都添加好了之后，使用布隆过滤器的时候，给定一个key，按照N个hash函数算出来对应的bit数组位置上的值如果不全为1，则这个key一定不存在。反之，如果都是1则大概率存在。布隆过滤器是有一定的误判率的、尽管很小。

布隆过滤器的实现方式
可以使用google的guava，redis等方式实现。
先用guava实现一个整数型的布隆过滤器。想象我们有一个高并发的商品服务对外开放一个根据商品ID查询商品信息的接口，缓存搭好了之后，为了防止缓存穿透，我们把全量的商品ID都存到布隆过滤器里去。然后有人再拿不属于商品ID的其他整型来攻击，那布隆过滤器都会挡掉，不会让去查缓存和数据库了。
compile group: 'com.google.guava', name: 'guava', version: '30.1-jre'

package com.wangan.redis;

import java.math.BigDecimal;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

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

/**
 * 使用google guava实现的一个本地整数型的布隆过滤器，
 * 里边存放某个全量表的ID。可以用来排除掉不存在的ID。
 * */
public class NativeBloomFilter {
    private static Logger logger = LoggerFactory.getLogger(NativeBloomFilter.class);
    
    private static int size = 1000000; //预计存放多少个key
    private static double fpp = 0.001; //期望误判率, 千分之一
    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
    
    {//for test
        bloomFilter.put(123);
        bloomFilter.put(1);
        bloomFilter.put(2);
    }
    
    public static void main(String[] args) {
        for(int i=0; i<1000000; i++) {
            bloomFilter.put(i);
        }
        int count = 0;
        for(int i=1000000; i<2000000; i++) {
            if(bloomFilter.mightContain(i)) {
                count++;
                logger.info(i + "被误判了在布隆过滤器中");
            }
        }
        BigDecimal rate =  new BigDecimal(count).divide(new BigDecimal(1000000)).multiply(new BigDecimal(100));
        logger.info("一共误判了" + count + ", 误判率" + rate + "%");
    }
}

输出：
.....
1997052被误判了在布隆过滤器中
一共误判了994, 误判率0.099400%
可见是满足了我们预期的误判率的。

除了进程内的实现之外，还可以使用redis实现布隆过滤器。
redis里边提供了bitmap这种结构，实际上是按位操作string类型，getbit setbit bitcount等操作等等。
bit数组有了，设置多长呢，hash函数如何映射、等等。水很深，幸好Redisson实现好了布隆过滤器，底层就是用的redis的bitmap。
关于Redisson可以参看作者专访：https://segmentfault.com/a/1190000015451551

package com.wangan.redis;

import java.math.BigDecimal;
import java.util.concurrent.TimeUnit;

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * 使用redis配合redisson实现的布隆过滤器
 * */
public class RedissonBloomFilter {
    private static Logger logger = LoggerFactory.getLogger(RedissonBloomFilter.class);
    
    public static void main(String[] args) {
        Config config = new Config();
        config.useSentinelServers().addSentinelAddress("redis://122.xx.xxx.xxx:26379")
                                    .addSentinelAddress("redis://122.xx.xxx.xxx:26380")
                                    .addSentinelAddress("redis://122.xx.xxx.xxx:26381") 
                                    .setMasterName("mymaster")
                                    .setPassword("password");
        RedissonClient redisson = Redisson.create(config);
        RBloomFilter<Integer> bloomFilter = redisson.getBloomFilter("GoodsIds");
        bloomFilter.tryInit(100, 0.01);  //设置的太大比如100万，跑不出来。改成100了。
        logger.info("redisson布隆过滤器初始化完毕");
        for(int i=0; i<100; i++) {
            bloomFilter.add(i);
        }
        logger.info("redisson布隆过滤器全量数据装载完毕");
        int count = 0;
        for(int i=100; i<200; i++) {
            if(bloomFilter.contains(i)) {
                count++;
                logger.info(i + "被误判了在布隆过滤器中");
            }
        }
        BigDecimal rate =  new BigDecimal(count).divide(new BigDecimal(100)).multiply(new BigDecimal(100));
        logger.info("一共误判了" + count + ", 误判率" + rate + "%");
        
        if(!redisson.isShutdown()) {
            logger.info("关闭redisson instance");
            try {
                redisson.shutdown(2, 6, TimeUnit.SECONDS); //这里稍微延迟一下shutdown、等待资源释放，直接shutdown会报exception。
            }catch(Exception e) {}
        }
    }
}

输出：
redisson布隆过滤器初始化完毕
redisson布隆过滤器全量数据装载完毕
115被误判了在布隆过滤器中
一共误判了1, 误判率1.00%
关闭redisson instance

gradle依赖用的是compile group: 'org.redisson', name: 'redisson-spring-boot-starter', version: '3.12.0' ，使用其他一些版本包括最新版本3.14.0有bug，报Exception At least two sentinels should be defined in Redis configuration!