解决缓存击穿的利器-布隆过滤器

一。什么是缓存击穿

       在高并发场景下，如果某一个key被高并发访问，没有被命中，出于对容错性考虑，会尝试去从后端数据库中获取，从而导致了大量请求达到数据库，而当该key对应的数据本身就是空的情况下，这就导致数据库中并发的去执行了很多不必要的查询操作，从而导致巨大冲击和压力。

        在高并发的场景下，缓存相当于数据库的防火墙，如果用一个肯定不存在的key去访问系统，每次都会绕过缓存去访问数据库，缓存则失去了作用。

二。解决缓存击穿的一点思考

（1）解决方案一：将所有的可用的key放入缓存，hashtable中。

以一个圆通单号为例，一个圆通单号是32位的byte，圆通的订单量大概有50亿

32byte * 50 亿 ≈ 120G  

需要120G的内存，成本太高

（2）解决方案二：利用分布式存储，比如elasticsearch，不太优雅

三。解决缓存击穿的利器-bloomFilter

（1）什么是bloomFilter

        Bloom-Filter，即布隆过滤器，1970年由Bloom中提出。它可以用于检索一个元素是否在一个集合中。

       Bloom Filter（BF）是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。它是一个判断元素是否存在集合的快速的概率算法。Bloom Filter有可能会出现错误判断，但不会漏掉判断。也就是Bloom Filter判断元素不再集合，那肯定不在。如果判断元素存在集合中，有一定的概率判断错误。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter比其他常见的算法（如hash，折半查找）极大节省了空间。 

图一

（2）这里有一个google guava包对布隆过滤器经典实现：

<pre>

import com.google.common.hash.BloomFilter;import com.google.common.hash.Funnels;import java.util.HashSet;import java.util.Random;public classtestBloomFilter{ static int sizeOfNumberSet = Integer.MAX_VALUE >> 4;

    static Random generator = new Random();

    public static void main(String[] args) {

        int error = 0;

        HashSet hashSet = new HashSet();

        BloomFilter filter = BloomFilter.create(Funnels.integerFunnel(), sizeOfNumberSet);

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

            int number = generator.nextInt();

            if(filter.mightContain(number) != hashSet.contains(number)) {

                error++;

            }

            filter.put(number);

            hashSet.add(number);

        }

        System.out.println("Error count: " + error + ", error rate = " + String.format("%f", (float)error/(float)sizeOfNumberSet));

    }

}

</pre>