黑客攻防：缓存穿透终极解决方案——布隆过滤器

com.google.guava
guava
21.0

//插入多少数据
privatestaticfinalintinsertions=1000000;
//期望的误判率
privatestaticdoublefpp=0.02;
publicstaticvoidmain(String[]args){
//初始化一个存储string数据的布隆过滤器,默认误判率是0.03
BloomFilter<String>bf=BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),insertions,fpp);
//用于存放所有实际存在的key，用于是否存在
Set<String>sets=newHashSet<String>(insertions);
//用于存放所有实际存在的key，用于取出
List<String>lists=newArrayList<String>(insertions);
//插入随机字符串
for(inti=0;i<insertions;i++){
Stringuuid=UUID.randomUUID().toString();
bf.put(uuid);
sets.add(uuid);
lists.add(uuid);
}
intrightNum=0;
intwrongNum=0;
for(inti=0;i<10000;i++){
//0-10000之间，可以被100整除的数有100个（100的倍数）
Stringdata=i%100==0?lists.get(i/100):UUID.randomUUID().toString();
//这里用了might,看上去不是很自信，所以如果布隆过滤器判断存在了,我们还要去sets中实锤
if(bf.mightContain(data)){
if(sets.contains(data)){
rightNum++;
continue;
}
wrongNum++;
}
}
BigDecimalpercent=newBigDecimal(wrongNum).divide(newBigDecimal(9900),2,RoundingMode.HALF_UP);
BigDecimalbingo=newBigDecimal(9900-wrongNum).divide(newBigDecimal(9900),2,RoundingMode.HALF_UP);
System.out.println("在100W个元素中，判断100个实际存在的元素，布隆过滤器认为存在的："+rightNum);
System.out.println("在100W个元素中，判断9900个实际不存在的元素，误认为存在的："+wrongNum+"，命中率："+bingo+"，误判率："+percent);
}

/**
* 布隆过滤器核心类
*
* @param <T>
* @author jack xu
*/
publicclassBloomFilterHelper {
privateintnumHashFunctions;
privateintbitSize;
privateFunnel funnel;
publicBloomFilterHelper(intexpectedInsertions){
this.funnel = (Funnel) Funnels.stringFunnel(Charset.defaultCharset());
bitSize = optimalNumOfBits(expectedInsertions,0.03);
numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);    }publicBloomFilterHelper(Funnel funnel,intexpectedInsertions,doublefpp){
this.funnel = funnel;
bitSize = optimalNumOfBits(expectedInsertions, fpp);        numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);    }publicint[] murmurHashOffset(T value) {
int[] offset =newint[numHashFunctions];
longhash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();
inthash1 = (int) hash64;
inthash2 = (int) (hash64 >>>32);
for(inti =1; i <= numHashFunctions; i++) {
intnextHash = hash1 + i * hash2;
if(nextHash <0) {
nextHash = ~nextHash;            }            offset[i -1] = nextHash % bitSize;
}returnoffset;
}/**
    * 计算bit数组长度
    */
privateintoptimalNumOfBits(longn,doublep){
if(p ==0) {
p = Double.MIN_VALUE;        }return(int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}/**
    * 计算hash方法执行次数
    */
privateintoptimalNumOfHashFunctions(longn,longm){
returnMath.max(1, (int) Math.round((double) m / n * Math.log(2)));
} }

/**
* redis操作布隆过滤器
*
*@param
*@authorxhj
*/
publicclassRedisBloomFilter{
@Autowired
privateRedisTemplate redisTemplate;
/**
    * 删除缓存的KEY
    *
*@paramkey KEY
    */
publicvoiddelete(String key){
redisTemplate.delete(key);    }/**
    * 根据给定的布隆过滤器添加值，在添加一个元素的时候使用，批量添加的性能差
    *
*@parambloomFilterHelper 布隆过滤器对象
*@paramkey              KEY
*@paramvalue            值
*@param              泛型，可以传入任何类型的value
    */
publicvoidadd(BloomFilterHelper<T> bloomFilterHelper, String key, T value){
int[] offset = bloomFilterHelper.murmurHashOffset(value);
for(inti : offset) {
redisTemplate.opsForValue().setBit(key, i,true);
}    }/**
    * 根据给定的布隆过滤器添加值，在添加一批元素的时候使用，批量添加的性能好，使用pipeline方式(如果是集群下，请使用优化后RedisPipeline的操作)
    *
*@parambloomFilterHelper 布隆过滤器对象
*@paramkey              KEY
*@paramvalueList        值，列表
*@param              泛型，可以传入任何类型的value
    */
publicvoidaddList(BloomFilterHelper<T> bloomFilterHelper, String key, List<T> valueList){
redisTemplate.executePipelined(newRedisCallback() {
@Override
publicLongdoInRedis(RedisConnection connection)throwsDataAccessException{
connection.openPipeline();for(T value : valueList) {
int[] offset = bloomFilterHelper.murmurHashOffset(value);
for(inti : offset) {
connection.setBit(key.getBytes(), i,true);
}                }returnnull;
}        });    }/**
    * 根据给定的布隆过滤器判断值是否存在
    *
*@parambloomFilterHelper 布隆过滤器对象
*@paramkey              KEY
*@paramvalue            值
*@param              泛型，可以传入任何类型的value
*@return是否存在
    */
publicbooleancontains(BloomFilterHelper<T> bloomFilterHelper, String key, T value){
int[] offset = bloomFilterHelper.murmurHashOffset(value);
for(inti : offset) {
if(!redisTemplate.opsForValue().getBit(key, i)) {
returnfalse;
}        }returntrue;
} }

publicstaticvoidmain(String[] args){
RedisBloomFilter redisBloomFilter =newRedisBloomFilter();
intexpectedInsertions =1000;
doublefpp =0.1;
redisBloomFilter.delete("bloom");
BloomFilterHelper bloomFilterHelper =newBloomFilterHelper<>(Funnels.stringFunnel(Charset.defaultCharset()), expectedInsertions, fpp);
intj =0;
// 添加100个元素
        List<String> valueList = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            valueList.add(i + "");
        }
        long beginTime = System.currentTimeMillis();
        redisBloomFilter.addList(bloomFilterHelper, "bloom", valueList);
        long costMs = System.currentTimeMillis() - beginTime;
        log.info("布隆过滤器添加{}个值，耗时：{}ms", 100, costMs);
        for (int i = 0; i < 1000; i++) {
            boolean result = redisBloomFilter.contains(bloomFilterHelper, "bloom", i + "");
            if (!result) {
                j++;
            }
        }
        log.info("漏掉了{}个,验证结果耗时：{}ms", j, System.currentTimeMillis() - beginTime);
    }