摘要：方案二布隆過濾器攔截布隆過濾器介紹概念布隆過濾器英語是年由布隆提出的。這就是布隆過濾器的基本思想。防緩存穿透的布隆過濾器判斷是否為合法非法則不允許繼續查庫從緩存中獲取數據緩存為空從數據庫中獲取緩存空對象參考書籍開發與運維

上周在工作中遇到了一個問題場景，即查詢商品的配件信息時（商品：配件為1：N的關系），如若商品并未配置配件信息，則查數據庫為空，且不會加入緩存，這就會導致，下次在查詢同樣商品的配件時，由于緩存未命中，則仍舊會查底層數據庫，所以緩存就一直未起到應有的作用，當并發流量大時，會很容易把DB打垮。

緩存穿透是指查詢一個根本不存在的數據，緩存層和存儲層都不會命中，通常出于容錯的考慮，如果從存儲層查不到數據則不寫入緩存層。
一般對于未命中的數據我們是按照如下方式進行處理的：

1.緩存層不命中。
2.存儲層不命中，不將空結果寫回緩存。
3.返回空結果。

/**
 * 緩存穿透問題：
 * 在數據庫層沒有查到數據，未存入緩存，
 * 則下次查詢同樣的數據時，還會查庫。
 * 
 * @param id
 * @return
 */
private Object getObjectById(Integer id) {
    // 從緩存中獲取數據
    Object cacheValue = cache.get(id);
    if (cacheValue != null) {
        return cacheValue;
    }
    // 從數據庫中獲取
    Object storageValue = storage.get(id);
    // 如果這里按照id查詢DB為空，那么便會出現緩存穿透
    if (storageValue != null) {
        cache.set(id, storageValue);
    }
    return storageValue;
}

緩存穿透將導致不存在的數據每次請求都要到存儲層去查詢，失去了緩存保護后端存儲的意義。
緩存穿透問題可能會使后端存儲負載加大，由于很多后端存儲不具備高并發性，甚至可能造成后端存儲宕掉。

/**
 * 緩存空對象：
 * 此種方式存在漏洞，不經過判斷就直接將Null對象存入到緩存中，
 * 如果惡意制造不存在的id那么，緩存中的鍵值就會很多，惡意攻擊時，很可能會被打爆，所以需設置較短的過期時間。
 *
 * @param id
 * @return
 */
public Object getObjectInclNullById(Integer id) {
    // 從緩存中獲取數據
    Object cacheValue = cache.get(id);
    // 緩存為空
    if (cacheValue == null) {
        // 從數據庫中獲取
        Object storageValue = storage.get(key);
        // 緩存空對象
        cache.set(key, storageValue);
        // 如果存儲數據為空，需要設置一個過期時間(300秒)
        if (storageValue == null) {
            // 必須設置過期時間，否則有被攻擊的風險
            cache.expire(key, 60 * 5);
        }
        return storageValue;
    }
    // 緩存不為空則直接返回
    return cacheValue;
}

緩存空對象會有一個必須考慮的問題：

空值做了緩存，意味著緩存層中存了更多的鍵，需要更多的內存空間（如果是攻擊，問題更嚴重），比較有效的方法是針對這類數據設置一個較短的過期時間，讓其自動剔除。

概念：

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

如果想判斷一個元素是不是在一個集合里，一般想到的是將集合中所有元素保存起來，然后通過比較確定。鏈表、樹、散列表（又叫哈希表，Hash table）等等數據結構都是這種思路。但是隨著集合中元素的增加，我們需要的存儲空間越來越大。同時檢索速度也越來越慢，上述三種結構的檢索時間復雜度分別為 O(n),O(log n),O(n/k)

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

示例：

google guava包下有對布隆過濾器的封裝，BloomFilter。

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

public class BloomFilterTest {

    // 初始化一個能夠容納10000個元素且容錯率為0.01布隆過濾器
    private static final BloomFilter bloomFilter = BloomFilter.create(Funnels.integerFunnel(), 10000, 0.01);

    /**
     * 初始化布隆過濾器
     */
    private static void initLegalIdsBloomFilter() {
        // 初始化10000個合法Id并加入到過濾器中
        for (int legalId = 0; legalId < 10000; legalId++) {
            bloomFilter.put(legalId);
        }
    }

    /**
     * id是否合法有效，即是否在過濾器中
     *
     * @param id
     * @return
     */
    public static boolean validateIdInBloomFilter(Integer id) {
        return bloomFilter.mightContain(id);
    }

    public static void main(String[] args) {
        // 初始化過濾器
        initLegalIdsBloomFilter();
        // 誤判個數
        int errorNum=0;
        // 驗證從10000個非法id是否有效
        for (int id = 10000; id < 20000; id++) {
            if (validateIdInBloomFilter(id)){
                // 誤判數
                errorNum++;
            }
        }
        System.out.println("judge error num is : " + errorNum);
    }
}

設置過期時間，讓其自動過期失效，這種在很多時候不是最佳的實踐方案。

我們可以提前將真實正確的商品Id，在添加完成之后便加入到過濾器當中，每次再進行查詢時，先確認要查詢的Id是否在過濾器當中，如果不在，則說明Id為非法Id，則不需要進行后續的查詢步驟了。

/**
 * 防緩存穿透的：布隆過濾器
 * 
 * @param id
 * @return
 */
public Object getObjectByBloom(Integer id) {
    // 判斷是否為合法id
    if (!bloomFilter.mightContain(id)) {
        // 非法id,則不允許繼續查庫
        return null;
    } else {
        // 從緩存中獲取數據
        Object cacheValue = cache.get(id);
        // 緩存為空
        if (cacheValue == null) {
            // 從數據庫中獲取
            Object storageValue = storage.get(id);
            // 緩存空對象
            cache.set(id, storageValue);
        }
        return cacheValue;
    }
}

參考書籍：《Redis開發與運維》