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

上周在工作中遇到了一個(gè)問(wèn)題場(chǎng)景，即查詢商品的配件信息時(shí)（商品：配件為1：N的關(guān)系），如若商品并未配置配件信息，則查數(shù)據(jù)庫(kù)為空，且不會(huì)加入緩存，這就會(huì)導(dǎo)致，下次在查詢同樣商品的配件時(shí)，由于緩存未命中，則仍舊會(huì)查底層數(shù)據(jù)庫(kù)，所以緩存就一直未起到應(yīng)有的作用，當(dāng)并發(fā)流量大時(shí)，會(huì)很容易把DB打垮。

緩存穿透是指查詢一個(gè)根本不存在的數(shù)據(jù)，緩存層和存儲(chǔ)層都不會(huì)命中，通常出于容錯(cuò)的考慮，如果從存儲(chǔ)層查不到數(shù)據(jù)則不寫入緩存層。
一般對(duì)于未命中的數(shù)據(jù)我們是按照如下方式進(jìn)行處理的：

1.緩存層不命中。
2.存儲(chǔ)層不命中，不將空結(jié)果寫回緩存。
3.返回空結(jié)果。

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

緩存穿透將導(dǎo)致不存在的數(shù)據(jù)每次請(qǐng)求都要到存儲(chǔ)層去查詢，失去了緩存保護(hù)后端存儲(chǔ)的意義。
緩存穿透問(wèn)題可能會(huì)使后端存儲(chǔ)負(fù)載加大，由于很多后端存儲(chǔ)不具備高并發(fā)性，甚至可能造成后端存儲(chǔ)宕掉。

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

緩存空對(duì)象會(huì)有一個(gè)必須考慮的問(wèn)題：

空值做了緩存，意味著緩存層中存了更多的鍵，需要更多的內(nèi)存空間（如果是攻擊，問(wèn)題更嚴(yán)重），比較有效的方法是針對(duì)這類數(shù)據(jù)設(shè)置一個(gè)較短的過(guò)期時(shí)間，讓其自動(dòng)剔除。

概念：

布隆過(guò)濾器（英語(yǔ)：Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過(guò)一般的算法，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。

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

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

示例：

google guava包下有對(duì)布隆過(guò)濾器的封裝，BloomFilter。

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

public class BloomFilterTest {

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

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

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

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

設(shè)置過(guò)期時(shí)間，讓其自動(dòng)過(guò)期失效，這種在很多時(shí)候不是最佳的實(shí)踐方案。

我們可以提前將真實(shí)正確的商品Id，在添加完成之后便加入到過(guò)濾器當(dāng)中，每次再進(jìn)行查詢時(shí)，先確認(rèn)要查詢的Id是否在過(guò)濾器當(dāng)中，如果不在，則說(shuō)明Id為非法Id，則不需要進(jìn)行后續(xù)的查詢步驟了。

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

參考書籍：《Redis開(kāi)發(fā)與運(yùn)維》