Redis 緩存主要緩存穿透、緩存擊穿與緩存雪崩異常場(chǎng)景，今天我們來(lái)講講緩存穿透。

1 場(chǎng)景描述

緩存穿透是指客戶端請(qǐng)求一個(gè)緩存和數(shù)據(jù)庫(kù)中都不存在的 key。由于緩存中不存在，所以請(qǐng)求會(huì)透過(guò)緩存查詢數(shù)據(jù)庫(kù)；由于數(shù)據(jù)庫(kù)中也不存在，所以也沒(méi)辦法更新緩存。因此下一次同樣的請(qǐng)求還是會(huì)打在數(shù)據(jù)庫(kù)上。

好像緩存被穿透了一樣，緩存形如虛設(shè)。所有的壓力都在數(shù)據(jù)庫(kù)之上，如果請(qǐng)求量巨大，可能造成數(shù)據(jù)庫(kù)崩潰。

2 解決方法

緩存穿透有以下幾種解決方法。

2.1 接口校驗(yàn)

在請(qǐng)求入口進(jìn)行校驗(yàn)，比如對(duì)用戶進(jìn)行鑒權(quán)、數(shù)據(jù)合法性檢查等操作，這樣可以減少緩存穿透發(fā)生的概率。

這種方式減輕了對(duì) Redis 以及數(shù)據(jù)庫(kù)的壓力，但是增加了客戶端的編碼與維護(hù)的工作量。如果請(qǐng)求的入口很多，那么工作量很大。

2.2 緩存空值

當(dāng)緩存與數(shù)據(jù)庫(kù)中都沒(méi)有 key 時(shí)，就設(shè)置一個(gè)空值寫入緩存，并同時(shí)設(shè)置一個(gè)比較短的過(guò)期時(shí)間。由于在緩存中設(shè)置空值，所以請(qǐng)求在緩存這一級(jí)別就返回，也就不會(huì)被穿透。這些所說(shuō)的不會(huì)被穿透只是針對(duì)某個(gè) key 而言的。其它沒(méi)有設(shè)置空值的 key，仍然存在被穿透的可能。

該方法的問(wèn)題是：由于不存在的 key 幾乎是無(wú)限，不可被窮舉的，所以不可能都設(shè)置到緩存中。而且大量這樣的空值 key 設(shè)置到緩存，也會(huì)占用大量的內(nèi)存空間。

解決：采用下面提到的布隆過(guò)濾器直接過(guò)濾掉不存在的 key。

2.3 布隆過(guò)濾器

布隆過(guò)濾器（Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過(guò)濾器可以用于判斷一個(gè)元素是否在一個(gè)集合中²。

布隆過(guò)濾器的特點(diǎn)是判斷為不存在的，則一定不存在；判斷存在的，則大概率存在。

2.3.1 布隆過(guò)濾器原理

布隆過(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ò)濾器的基本思想³。

假設(shè)有這樣一個(gè)集合 S，它包含 a b c 三個(gè)元素。那么布隆過(guò)濾器會(huì)利用多個(gè)哈希函數(shù)（圖中是三個(gè)哈希函數(shù) h1、h2、h3）來(lái)計(jì)算所在的位，然后將該位設(shè)置為 1。比如元素 a，經(jīng)過(guò)三個(gè)哈希函數(shù)計(jì)算后，將相應(yīng)的位設(shè)置為 1，也就是圖中的紅線。元素 b 和 c 也是按照相應(yīng)的方法進(jìn)行計(jì)算處理。這時(shí)布隆過(guò)濾器初始化完畢。

假設(shè)有一個(gè)元素 d，需要判斷它是否在我們剛才所創(chuàng)建的布隆過(guò)濾器中（圖中的黃色線條）。經(jīng)過(guò)三個(gè)哈希函數(shù) h1、h2、h3 計(jì)算后，發(fā)現(xiàn)相應(yīng)的位都是 1，布隆過(guò)濾器會(huì)返回 true。也就是認(rèn)為這個(gè)元素可能在，也可能不在集合中?？吹竭@里，有同學(xué)就會(huì)問(wèn)：“既然這個(gè)布隆過(guò)濾器都不知道這個(gè)元素是不是在集合中，對(duì)我們有什么用呢？”

布隆過(guò)濾器的強(qiáng)大之處是可以利用較小的緩存，就可以判斷出某個(gè)元素是否不在集合中。比如又來(lái)了一個(gè)元素 e，經(jīng)過(guò)三個(gè)哈希函數(shù) h1、h2、h3 計(jì)算后，發(fā)現(xiàn) h1(e) 所對(duì)應(yīng)的位是 0。那么這個(gè)元素 e 肯定不在集合中。有同學(xué)又說(shuō)了：“我用 HashMap 不是也能判斷出某個(gè)元素在不在集合中呀？”

HashMap 是可以判斷，但需要存儲(chǔ)集合中所有的元素。如果集合中有上億個(gè)元素，那么就會(huì)占用大量的內(nèi)存。內(nèi)存空間畢竟是有限，可能還不一定放的下這么多的元素。與 HashMap 相比， 布隆過(guò)濾器占用的空間很小，所以很適合判斷大集合中某個(gè)元素是否不存在。

2.3.2 布隆過(guò)濾器誤識(shí)別率

之前的示例中可以看出，布隆過(guò)濾器判斷為不存在的元素，則一定不存在；而判斷存在的元素，則大概率存在。也就是說(shuō)，有的元素可能并不在集合中，但是布隆過(guò)濾器會(huì)認(rèn)為它存在。這就涉及到一個(gè)概念：誤識(shí)別率。誤識(shí)別率指的錯(cuò)誤判斷一個(gè)元素在集合中的概率。

假設(shè)布隆過(guò)濾器有 m bit 大小，需要放入 n 個(gè)元素，每個(gè)元素使用 k 個(gè)哈希函數(shù)，那么它的誤識(shí)別率如下表所示⁴。

2.3.3 使用布隆過(guò)濾器

Google 的 Guava 庫(kù)提供了使用布隆過(guò)濾器的 API 類（BloomFilter.class），它是線程安全的。

首先創(chuàng)建布隆過(guò)濾器：

//創(chuàng)建存儲(chǔ)整型的布隆過(guò)濾器
bloomFilter =
        BloomFilter.create(Funnels.integerFunnel(), expectedInsertions, fpp);

創(chuàng)建布隆過(guò)濾器的方法有以下幾個(gè)入?yún)ⅲ?/p>

Funnel 類定義了如何把一個(gè)具體的對(duì)象類型分解為原生字段值，從而將值分解為 Byte 以供后面 BloomFilter 進(jìn)行 hash 運(yùn)算⁵。也就是說(shuō) Guava 的布隆過(guò)濾器會(huì)根據(jù)Funnel 類的定義，計(jì)算一個(gè)對(duì)象的哈希值，放入過(guò)濾器。

Guava 官方提供了這樣一個(gè)創(chuàng)建可插入自定義類的布隆過(guò)濾器示例。

首先創(chuàng)建一個(gè) Person 類：

@Data
@AllArgsConstructor
public class Person {
    private String firstName;
    private String lastName;
    private int age;
}

然后創(chuàng)建一個(gè) PersonFunnel 類，它實(shí)現(xiàn)了 Funnel 類中的 funnel(Person from, PrimitiveSink into) 方法：

public class PersonFunnel implements Funnel<Person> {

    @Override
    public void funnel(Person from, PrimitiveSink into) {
        into.putUnencodedChars(from.getFirstName()).putUnencodedChars(from.getLastName()).putInt(from.getAge());
    }
}

這個(gè)方法主要是把 Person 類中的各個(gè)屬性（名字、年齡）寫入 PrimitiveSink 對(duì)象。 PrimitiveSink 提供了支持各種寫入類型的方法：

接著把元素放入布隆過(guò)濾器：

bloomFilter.put(new Person("deniro","lee",20));
bloomFilter.put(new Person("lily","lee",16));

最后就是判斷某個(gè)元素是否在布隆過(guò)濾器中：

Assert.assertFalse(bloomFilter.mightContain(new Person("jack","lee",20)));
Assert.assertTrue(bloomFilter.mightContain(new Person("deniro","lee",20)));

Funnels 是個(gè)工具類，內(nèi)置了一些創(chuàng)建基本類型的 Funnel：

我們可以利用這些 Funnel，來(lái)創(chuàng)建包含基本類型元素的布隆過(guò)濾器，比如創(chuàng)建一個(gè)包含整型元素的布隆過(guò)濾器：

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

最后，讓我們總結(jié)一波。

可以看到接口校驗(yàn)方法與 Guava 版的布隆過(guò)濾器方法都是在客戶側(cè)進(jìn)行處理。布隆過(guò)濾器也可以在緩存層進(jìn)行處理。相對(duì)來(lái)說(shuō)，布隆過(guò)濾器方法比接口校驗(yàn)方法少了很多代碼量與維護(hù)成本。緩存空值不可取，畢竟內(nèi)存空間是有限的。

利用布隆過(guò)濾器，我們可以攔截絕大多數(shù)不存在的 key，因此很適合解決 Redis 緩存穿透問(wèn)題。

參考資料：

1. 緩存穿透、緩存擊穿、緩存雪崩解決方案
2. 布隆過(guò)濾器
3. 大數(shù)據(jù)量下的集合過(guò)濾—Bloom Filter
4. 吳軍. 數(shù)學(xué)之美.第2版[M]. 人民郵電出版社, 2014. p208-209.
5. 結(jié)合Guava源碼解讀布隆過(guò)濾器