Redis 緩存主要緩存穿透、緩存擊穿與緩存雪崩異常場(chǎng)景祭犯，今天我們來講講緩存穿透帘瞭。
1 場(chǎng)景描述
緩存穿透是指客戶端請(qǐng)求一個(gè)緩存和數(shù)據(jù)庫(kù)中都不存在的 key。由于緩存中不存在吊圾，所以請(qǐng)求會(huì)透過緩存查詢數(shù)據(jù)庫(kù)；由于數(shù)據(jù)庫(kù)中也不存在翰蠢，所以也沒辦法更新緩存项乒。因此下一次同樣的請(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ù)中都沒有 key 時(shí)，就設(shè)置一個(gè)空值寫入緩存默怨，并同時(shí)設(shè)置一個(gè)比較短的過期時(shí)間讯榕。由于在緩存中設(shè)置空值，所以請(qǐng)求在緩存這一級(jí)別就返回先壕，也就不會(huì)被穿透瘩扼。這些所說的不會(huì)被穿透只是針對(duì)某個(gè) key 而言的谆甜。其它沒有設(shè)置空值的 key垃僚，仍然存在被穿透的可能。
該方法的問題是：由于不存在的 key 幾乎是無限规辱，不可被窮舉的谆棺，所以不可能都設(shè)置到緩存中。而且大量這樣的空值 key 設(shè)置到緩存，也會(huì)占用大量的內(nèi)存空間改淑。
解決：采用下面提到的布隆過濾器直接過濾掉不存在的 key碍岔。
2.3 布隆過濾器
布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)朵夏。布隆過濾器可以用于判斷一個(gè)元素是否在一個(gè)集合中2蔼啦。
布隆過濾器的特點(diǎn)是判斷為不存在的，則一定不存在仰猖；判斷存在的捏肢，則大概率存在。
2.3.1 布隆過濾器原理
布隆過濾器的原理是當(dāng)一個(gè)元素被加入集合時(shí)饥侵，通過K個(gè)散列函數(shù)將這個(gè)元素映射成一個(gè)位數(shù)組中的K個(gè)點(diǎn)鸵赫，把它們置為1。檢索時(shí)躏升，我們只要看看這些點(diǎn)是不是都是1就（大約）知道集合中有沒有它了：如果這些點(diǎn)有任何一個(gè)0辩棒，則被檢元素一定不在；如果都是1膨疏，則被檢元素很可能在一睁。這就是布隆過濾器的基本思想3。
假設(shè)有這樣一個(gè)集合 S成肘，它包含 a b c 三個(gè)元素卖局。那么布隆過濾器會(huì)利用多個(gè)哈希函數(shù)（圖中是三個(gè)哈希函數(shù) h1、h2、h3）來計(jì)算所在的位，然后將該位設(shè)置為 1蒸痹。比如元素 a澡绩，經(jīng)過三個(gè)哈希函數(shù)計(jì)算后，將相應(yīng)的位設(shè)置為 1筒扒，也就是圖中的紅線。元素 b 和 c 也是按照相應(yīng)的方法進(jìn)行計(jì)算處理。這時(shí)布隆過濾器初始化完畢单鹿。
假設(shè)有一個(gè)元素 d，需要判斷它是否在我們剛才所創(chuàng)建的布隆過濾器中（圖中的黃色線條）深纲。經(jīng)過三個(gè)哈希函數(shù) h1仲锄、h2、h3 計(jì)算后湃鹊，發(fā)現(xiàn)相應(yīng)的位都是 1儒喊，布隆過濾器會(huì)返回 true。也就是認(rèn)為這個(gè)元素可能在币呵，也可能不在集合中怀愧。看到這里，有同學(xué)就會(huì)問：“既然這個(gè)布隆過濾器都不知道這個(gè)元素是不是在集合中芯义，對(duì)我們有什么用呢哈垢？”
布隆過濾器的強(qiáng)大之處是可以利用較小的緩存，就可以判斷出某個(gè)元素是否不在集合中扛拨。比如又來了一個(gè)元素 e耘分，經(jīng)過三個(gè)哈希函數(shù) h1、h2绑警、h3 計(jì)算后陶贼，發(fā)現(xiàn) h1(e) 所對(duì)應(yīng)的位是 0。那么這個(gè)元素 e 肯定不在集合中待秃。有同學(xué)又說了：“我用 HashMap 不是也能判斷出某個(gè)元素在不在集合中呀拜秧？”
HashMap 是可以判斷，但需要存儲(chǔ)集合中所有的元素章郁。如果集合中有上億個(gè)元素枉氮，那么就會(huì)占用大量的內(nèi)存。內(nèi)存空間畢竟是有限暖庄，可能還不一定放的下這么多的元素聊替。與 HashMap 相比， 布隆過濾器占用的空間很小培廓，所以很適合判斷大集合中某個(gè)元素是否不存在惹悄。
2.3.2 布隆過濾器誤識(shí)別率
之前的示例中可以看出，布隆過濾器判斷為不存在的元素肩钠，則一定不存在泣港；而判斷存在的元素，則大概率存在价匠。也就是說当纱，有的元素可能并不在集合中，但是布隆過濾器會(huì)認(rèn)為它存在踩窖。這就涉及到一個(gè)概念：誤識(shí)別率坡氯。誤識(shí)別率指的錯(cuò)誤判斷一個(gè)元素在集合中的概率。
假設(shè)布隆過濾器有 m bit 大小洋腮，需要放入 n 個(gè)元素箫柳，每個(gè)元素使用 k 個(gè)哈希函數(shù)，那么它的誤識(shí)別率如下表所示4啥供。
2.3.3 使用布隆過濾器
Google 的 Guava 庫(kù)提供了使用布隆過濾器的 API 類（BloomFilter.class）悯恍，它是線程安全的。
首先創(chuàng)建布隆過濾器：
//創(chuàng)建存儲(chǔ)整型的布隆過濾器
bloomFilter =
BloomFilter.create(Funnels.integerFunnel(), expectedInsertions, fpp);
創(chuàng)建布隆過濾器的方法有以下幾個(gè)入?yún)ⅲ?/p>
| 入?yún)?/th> | 說明 |
|---|---|
| Funnels 實(shí)例 | 用于后續(xù)把類對(duì)象轉(zhuǎn)換為相應(yīng)的 hash 值滤灯。 |
| expectedInsertions | 期望插入過濾器的元素個(gè)數(shù)坪稽。 |
| fpp | 誤識(shí)別率，該值必須大于 0 且小于 1.0鳞骤。 |
Funnel 類定義了如何把一個(gè)具體的對(duì)象類型分解為原生字段值窒百，從而將值分解為 Byte 以供后面 BloomFilter 進(jìn)行 hash 運(yùn)算5。也就是說 Guava 的布隆過濾器會(huì)根據(jù)Funnel 類的定義豫尽，計(jì)算一個(gè)對(duì)象的哈希值篙梢，放入過濾器。
Guava 官方提供了這樣一個(gè)創(chuàng)建可插入自定義類的布隆過濾器示例美旧。
首先創(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 提供了支持各種寫入類型的方法：
接著把元素放入布隆過濾器：
bloomFilter.put(new Person("deniro","lee",20));
bloomFilter.put(new Person("lily","lee",16));
最后就是判斷某個(gè)元素是否在布隆過濾器中：
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，來創(chuàng)建包含基本類型元素的布隆過濾器嗽测，比如創(chuàng)建一個(gè)包含整型元素的布隆過濾器：
BloomFilter<Integer> bloomFilter =
BloomFilter.create(Funnels.integerFunnel(), size, fpp);
最后绪励，讓我們總結(jié)一波。
可以看到接口校驗(yàn)方法與 Guava 版的布隆過濾器方法都是在客戶側(cè)進(jìn)行處理唠粥。布隆過濾器也可以在緩存層進(jìn)行處理疏魏。相對(duì)來說，布隆過濾器方法比接口校驗(yàn)方法少了很多代碼量與維護(hù)成本晤愧。緩存空值不可取大莫，畢竟內(nèi)存空間是有限的。
利用布隆過濾器官份，我們可以攔截絕大多數(shù)不存在的 key只厘，因此很適合解決 Redis 緩存穿透問題。
參考資料：
- 緩存穿透舅巷、緩存擊穿懈凹、緩存雪崩解決方案
- 布隆過濾器
- 大數(shù)據(jù)量下的集合過濾—Bloom Filter
- 吳軍. 數(shù)學(xué)之美.第2版[M]. 人民郵電出版社, 2014. p208-209.
- 結(jié)合Guava源碼解讀布隆過濾器
