分布式緩存擊穿（布隆過濾器 Bloom Filter）

• 緩存中無值（未當機）
  • 互斥鎖
  • 緩存永不過期
• 緩存當機
  • 白名單
  • 布隆過濾器
    • 代碼實作

前面的文章介紹了緩存的分類和使用的場景。通常情況下，緩存是加速系統響應的一種途徑，通常情況下隻有系統的部分資料。當請求了緩存中沒有的資料時，這時候就會回源到DB裡面。此時如果黑客故意對上面資料發起大量請求，則DB有可能會挂掉，這就是緩存擊穿。當然緩存挂掉的話，正常的使用者請求也有可能造成緩存擊穿的效果。

緩存中無值（未當機）

互斥鎖

我們最先想到的應該是加鎖擷取緩存。也就是當擷取的value值為空時（

這裡的空表示緩存過期

），先加鎖，然後從資料庫加載并放入緩存，最後釋放鎖。如果其他線程擷取鎖失敗，則睡眠一段時間後重試。下面使用Redis的setnx來實作分布式鎖，如下所示：

String get(String key) {
    String value = redis.get(key);  
    if (value  == null) {  
        if (redis.setnx(key_mutex, "1")) {  
            // 3 min timeout to avoid mutex holder crash  
            redis.expire(key_mutex,  * )  
            value = db.get(key);  
            redis.set(key, value);  
            redis.delete(key_mutex);  
        } else {  
            //其他線程休息50毫秒後重試  
            Thread.sleep();
            get(key);
        }
    }  
}
           

緩存永不過期

緩存永不過期的意思是：真正的緩存過期時間不有Redis控制，而是由程式代碼控制。當擷取資料時發現資料逾時時，就需要發起一個異步請求去加載資料。這種政策的有點就是不會産生死鎖等現象，但是有可能會造成緩存不一緻的現象，但是筆者看來一般情況下都是可以适用的。

String get(final String key) {
    V v = redis.get(key);
    String value = v.getValue();
    long timeout = v.getTimeout();
    if (v.timeout <= System.currentTimeMillis()) {
        // 異步更新背景異常執行
        threadPool.execute(new Runnable() {
            public void run() {
                String keyMutex = "mutex:" + key;
                if (redis.setnx(keyMutex, "1")) {
                    // 3 min timeout to avoid mutex holder crash
                    redis.expire(keyMutex,  * );
                    String dbValue = db.get(key);
                    redis.set(key, dbValue);
                    redis.delete(keyMutex);
                }
            }
        });
    }
    return value;
}
           

緩存當機

上面說到的場景是緩存依舊有效的，當Redis挂掉時，這個時候如何來應對大量的回源請求呢？先來說一種簡單的方式：

白名單

。

白名單

白名單顧名思義就是：在緩存當機之前的一段時間裡，會将請求的資料在系統中的有無，記錄在一個Map中。當緩存當機後，首先在Map中判斷是否含有資料，有則回源DB，沒有的話就直接傳回結果。

這種方式實作起來比較簡單（Demo就不提供了），但是占用的記憶體空間比較龐大。如一個value是10位元組，那麼要存儲大小為1億的Map時，其所需的記憶體大小大約是：10 * 2 * 10e8 = 2G（假設Map的使用率為50%）。由此可見其對于一種類型的資料判斷就需要一個 2G 的Map去操作，這種方式就不可行了。

布隆過濾器

布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列随機映射函數。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識别率和删除困難。

如果想判斷一個元素是不是在一個集合裡，一般想到的是将集合中所有元素儲存起來，然後通過比較确定。連結清單、樹、散清單（又叫哈希表，Hash table）等等資料結構都是這種思路。但是随着集合中元素的增加，我們需要的存儲空間越來越大。同時檢索速度也越來越慢，上述三種結構的檢索時間複雜度分别為：O(n), O(log n), O(n/k)。

布隆過濾器的原理是，當一個元素被加入集合時，通過K個Hash函數将這個元素映射成一個位數組中的K個點，把它們置為1。檢索時，我們隻要看看這些點是不是都是1就（大約）知道集合中有沒有它了：如果這些點有任何一個0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。這就是布隆過濾器的基本思想。

代碼實作

在實際應用當中，我們不需要自己去實作BloomFilter。可以使用Guava提供的相關類庫即可。

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>25.1-jre</version>
</dependency>
           

判斷一個元素是否在集合中

public class Test1 {

    private static int size = ;

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

    public static void main(String[] args) {
        for (int i = ; i < size; i++) {
            bloomFilter.put(i);
        }

        long startTime = System.nanoTime(); // 擷取開始時間
        //判斷這一百萬個數中是否包含29999這個數
        if (bloomFilter.mightContain()) {
            System.out.println("命中了");
        }
        long endTime = System.nanoTime();   // 擷取結束時間
        System.out.println("程式運作時間： " + (endTime - startTime) + "納秒");
    }

}
           

運作結果如下：

命中了
程式運作時間： 441616納秒
           

自定義錯誤率

public class Test3 {

    private static int size = ;

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

    public static void main(String[] args) {
        for (int i = ; i < size; i++) {
            bloomFilter.put(i);
        }
        List<Integer> list = new ArrayList<Integer>();
        // 故意取10000個不在過濾器裡的值，看看有多少個會被認為在過濾器裡
        for (int i = size + ; i < size + ; i++) {
            if (bloomFilter.mightContain(i)) {
                list.add(i);
            }
        }
        System.out.println("誤判的數量：" + list.size());
    }

}
           

運作結果如下：

誤判的數量：94
           

對于緩存當機的場景，使用

白名單或者布隆過濾器都有可能會造成一定程度的誤判

。原因是除了Bloom Filter

本身有誤判率

，當機之前的緩存不一定能

覆寫到所有DB中的資料

，當當機後使用者請求了一個以前從未請求的資料，這個時候就會産生誤判。當然，緩存當機時使用白名單/布隆過濾器作為應急的方式，這種情況應該也是可以忍受的。

連結：http://moguhu.com/article/detail?articleId=96