簡要回答

緩存穿透（cache penetration）是用戶訪問的數(shù)據(jù)既不在緩存當(dāng)中，也不在數(shù)據(jù)庫中。出于容錯的考慮，如果從底層數(shù)據(jù)庫查詢不到數(shù)據(jù)，則不寫入緩存。這就導(dǎo)致每次請求都會到底層數(shù)據(jù)庫進(jìn)行查詢，緩存也失去了意義。當(dāng)高并發(fā)或有人利用不存在的Key頻繁攻擊時，數(shù)據(jù)庫的壓力驟增，甚至崩潰，這就是緩存穿透問題。

緩存穿透與緩存擊穿同樣非常相似，區(qū)別點在于緩存穿透的實際請求數(shù)據(jù)在數(shù)據(jù)庫中也沒有，而緩存擊穿是僅僅在緩存中沒命中，但是在數(shù)據(jù)庫中其實是存在對應(yīng)數(shù)據(jù)的。

圖片

發(fā)生場景：

• 原來數(shù)據(jù)是存在的，但由于某些原因（誤刪除、主動清理等）在緩存和數(shù)據(jù)庫層面被刪除了，但前端或前置的應(yīng)用程序依舊保有這些數(shù)據(jù)；
• 黑客惡意攻擊，外部爬蟲，故意大量訪問某些讀取不存在數(shù)據(jù)的業(yè)務(wù)；

緩存穿透解決方案：

1. 緩存空值（null）或默認(rèn)值

• 分析業(yè)務(wù)請求，如果是正常業(yè)務(wù)請求時發(fā)生緩存穿透現(xiàn)象，可針對相應(yīng)的業(yè)務(wù)數(shù)據(jù)，在數(shù)據(jù)庫查詢不存在時，將其緩存為空值（null）或默認(rèn)值，但是需要注意的是，針對空值的緩存失效時間不宜過長，一般設(shè)置為5分鐘之內(nèi)。當(dāng)數(shù)據(jù)庫被寫入或更新該key的新數(shù)據(jù)時，緩存必須同時被刷新，避免數(shù)據(jù)不一致。

圖片

2. 業(yè)務(wù)邏輯前置校驗

• 在業(yè)務(wù)請求的入口處進(jìn)行數(shù)據(jù)合法性校驗，檢查請求參數(shù)是否合理、是否包含非法值、是否惡意請求等，提前有效阻斷非法請求。比如，根據(jù)年齡查詢時，請求的年齡為-10歲，這顯然是不合法的請求參數(shù)，直接在參數(shù)校驗時進(jìn)行判斷返回。

3. 使用布隆過濾器快速判斷數(shù)據(jù)不存在（推薦）

• 在寫入數(shù)據(jù)時，使用布隆過濾器進(jìn)行標(biāo)記（相當(dāng)于設(shè)置白名單），業(yè)務(wù)請求發(fā)現(xiàn)緩存中無對應(yīng)數(shù)據(jù)時，可先通過查詢布隆過濾器判斷數(shù)據(jù)是否在白名單內(nèi)（布隆過濾器可以判斷數(shù)據(jù)一定不存在），如果不在白名單內(nèi)，則直接返回空或失敗。

4. 用戶黑名單限制：當(dāng)發(fā)生異常情況時，實時監(jiān)控訪問的對象和數(shù)據(jù)，分析用戶行為，針對故意請求、爬蟲或攻擊者，進(jìn)行特定用戶的限制；

5. 添加反爬策略：比如添加請求簽名校驗機制、比如添加IP訪問限制策略等等

接下來本文會詳細(xì)介紹一下布隆過濾器及其使用場景

擴展-布隆過濾器

概述

布隆過濾器是由布?。˙urton Howard Bloom）在1970年提出的 一種緊湊型的、比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)，特點是高效地插入和查詢，查詢時可以用來判斷 “一定不存在或者可能存在”，它是用多個哈希函數(shù)，將一個數(shù)據(jù)映射到位圖結(jié)構(gòu)中。

原理

當(dāng)一個元素被加入集合時，通過 K 個散列函數(shù)將這個元素映射成一個位圖中的 K 個位置，把它們置為 1。查詢時，只要查看這些位置是不是都是 1 ，就知道集合中有沒有它了：如果這些位置有任何一個 0，則被查詢元素一定不存在；如果都是 1，則被查詢元素很可能存在。

簡單來說就是將一個長度為 m 的位數(shù)組的所有元素初始化為 0，用 k 個散列函數(shù)對元素進(jìn)行 k 次散列運算跟 len (m) 取余得到 k 個位置并將 m 中對應(yīng)位置設(shè)置為 1。

圖片

如上圖，位數(shù)組的長度是８，散列函數(shù)個數(shù)是 3，兩個元素ｘ，ｙ。這兩個元素都經(jīng)過三次哈希函數(shù)生成三個哈希值，并映射到位數(shù)組的不同的位置，并置為1。元素 x 映射到位數(shù)組的第０位，第４位，第７位，元素ｙ映射到數(shù)組的位數(shù)組的第１位，第４位，第６位。

當(dāng)布隆過濾器保存的元素越多，被置為 1 的 bit 位也會越來越多，元素 z 即便沒有存儲過，假設(shè)哈希函數(shù)將z映射到位數(shù)組的三個位都被其他值設(shè)置為 1 了，對于布隆過濾器的機制來講，元素 z 這個值也是存在的，也就是說布隆過濾器存在一定的誤判率。因此布隆過濾器只能保證一定不存在和可能存在。

誤判率

布隆過濾器包含如下四個屬性：

• k : 哈希函數(shù)個數(shù)
• m : 位數(shù)組長度
• n : 插入的元素個數(shù)
• p : 誤判率

若位數(shù)組長度太小則會導(dǎo)致所有 bit 位很快都會被置為 1 ，那么檢索任意值都會返回“可能存在” ， 起不到過濾的效果。位數(shù)組長度越大，則誤判率越小。同時，哈希函數(shù)的個數(shù)也需要考量，哈希函數(shù)的個數(shù)越大，檢索的速度會越慢，誤判率也越小，反之，則誤判率越高。

為什么就用一個hash函數(shù)不行？

其實布隆過濾器底層是用 位圖 實現(xiàn)的，而多個hash函數(shù)就是為了減少位圖的誤判率的。具體可往下看

假設(shè)布隆過濾器中的hash函數(shù)滿足simple uniform hashing假設(shè)：每個元素都等概率地hash到m個位中的任何一個，與其它元素被hash到哪個位無關(guān)。那么

顯然，當(dāng)m越大，n減少時，誤判率就越低。并且當(dāng)k越大，誤判率p也就越小，也就是說，hash函數(shù)越多，誤判率越低，但相對檢索的速度會越慢。

如圖：相同位數(shù)組長度的情況下，隨著哈希函數(shù)的個數(shù)的增長，誤判率顯著的下降。

圖片

布隆過濾器的效率和缺點

布隆過濾器的空間復(fù)雜度為 O(m) ，插入和查詢時間復(fù)雜度都是 O(k) 。 存儲空間和插入、查詢時間都不會隨元素增加而增大。 空間、時間效率都很高。

但是布隆過濾器并不支持刪除元素，因為多個元素可能哈希到一個布隆過濾器的同一個位置，如果直接刪除該位置的元素，則會影響其他元素的判斷。因此，就提出了 計數(shù)布隆過濾器

計數(shù)布隆過濾器

計數(shù)過濾器（Counting Bloom Filter）是布隆過濾器的擴展，標(biāo)準(zhǔn) Bloom Filter 位數(shù)組的每一位擴展為一個小的計數(shù)器（Counter），在插入元素時給對應(yīng)的 k （k 為哈希函數(shù)個數(shù)）個 Counter 的值分別加 1，刪除元素時給對應(yīng)的 k 個 Counter 的值分別減 1。

圖片

顯然，又引入了另一個問題：更多的資源占用，而且在很多時候會造成極大的空間浪費

使用場景

Redis的緩存穿透

對于一個數(shù)據(jù)查詢，其過程大致如下：

圖片

但是當(dāng)查詢的數(shù)據(jù)既不在緩存中，也不存在數(shù)據(jù)庫中，則沒有辦法回寫緩存，當(dāng)有類似這樣大量的請求訪問服務(wù)時，數(shù)據(jù)庫的壓力就會極大。這就是緩存穿透

因此，引入布隆過濾器，當(dāng)用戶請求時，判斷過濾器中是否存在該元素，若不存在該元素，則直接返回不存在。若包含則從緩存中查詢數(shù)據(jù)，若緩存中也沒有，則查詢數(shù)據(jù)庫并回寫到緩存里，最后給前端返回。

圖片

盡管布隆過濾器有少量的誤判，即可能不存在的數(shù)據(jù)會判定存在，從而繼續(xù)查詢緩存和數(shù)據(jù)庫，但只要將m和k的值設(shè)置相對理想，少量的不存在查詢也是可以接受的。

元素刪除場景

實際上，元素不僅僅是只有增加，還存在刪除元素的場景，比如說商品的刪除，刪除后數(shù)據(jù)其實已經(jīng)不存在了，但是布隆過濾器中還沒刪除，則會判定其存在。

第一種方案就是使用計數(shù)布隆過濾器。

第二種方案，則是通過 定時重新構(gòu)建布隆過濾器

圖片

1. 定時任務(wù)觸發(fā)全量商品查詢，更新數(shù)據(jù);
2. 將商品添加到新的布隆過濾器 ;
3. 修改商品布隆過濾器的映射（從舊 A 修改成 新 B ）;
4. 商品服務(wù)根據(jù)布隆過濾器的映射，選擇新的布隆過濾器 B進(jìn)行相關(guān)的查詢操作 ；
5. 選擇合適的時間點，刪除舊的布隆過濾器 A。

在刪除商品 到 使用新的布隆過濾器B 之間的這段時間的不存在的查詢有可能還會到數(shù)據(jù)庫層面，但這種少量的不存在查詢也是可以接受的。

應(yīng)用布隆過濾器

Redisson

Redisson 提供了操作布隆過濾器的簡單易用 API，以下是使用布隆過濾器的示例：

• 引入依賴

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>3.37.0</version>
</dependency>

• 使用示例

private void redisson() {
    RedissonClient redissonClient = Redisson.create();

    RBloomFilter < Object > bloomFilter = redissonClient.getBloomFilter("bloomFilter");
    // 初始化大小為 10億，假陽率為 0.001（在使用布隆過濾器之前，必須完成初始化操作）
    bloomFilter.tryInit(1000000000, 0.001);

    Object object = new Object();
    // 添加元素
    bloomFilter.add(object);

    // 檢查元素是否存在
    boolean exist = bloomFilter.contains(object);
}

Guava

Guava 也提供了 BloomFilter 實現(xiàn)，用于高效地判斷一個元素是否存在于集合中，在 23.0 及之后版本中，是線程安全的。以下是 Guava 中布隆過濾器使用示例：

• 引入依賴

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <!-- 請根據(jù)需要選擇合適的版本 -->
    <version>33.3.1-jre</version>
</dependency>

• 使用示例

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

public class BloomFilterExample {
    public static void main(String[] args) {
        // 創(chuàng)建一個布隆過濾器，預(yù)計插入 3000000 個整數(shù)，假陽率為0.01
        BloomFilter < Integer > bloomFilter = BloomFilter.create(
            Funnels.integerFunnel(), 3000000, 0.01);

        // 向布隆過濾器中添加元素
        for (int i = 0; i < 3000000; i++) {
            bloomFilter.put(i);
        }

        // 測試布隆過濾器
        for (int i = 0; i < 3001000; i++) {
            if (bloomFilter.mightContain(i)) {
                System.out.println(i + " might be in the filter.");
            } else {
                System.out.println(i + " is definitely not in the filter.");
            }
        }
    }
}

布隆過濾器總結(jié)

布隆過濾器的空間效率O(m) 和查詢時間O(k) 都很優(yōu)秀，但是存在一定的誤判率 （布隆過濾器認(rèn)為不存在，則一定不存在；布隆過濾器認(rèn)為存在，則只是可能存在）

bit數(shù)組的位數(shù)m越大，hash函數(shù)的個數(shù)k越多，誤判率就越低。但也需要控制合適的大小，比如m越大，但存儲的數(shù)據(jù)少，則會引起空間浪費，k的個數(shù)越多，則會一定程度降低查存效率

普通布隆過濾器無法刪除元素，但可以通過計數(shù)布隆過濾器和定時重新構(gòu)建布隆過濾器兩種方案實現(xiàn)刪除元素的效果。

拓展：布谷鳥過濾器

布隆過濾器不記錄元素本身，并且存在一個位被多個元素共用的情況，所以它不支持刪除元素。布谷鳥過濾器（詳細(xì)了解可以參考這篇論文《布谷鳥過濾器：實際上優(yōu)于布隆過濾器》）的提出解決了這個問題，它支持刪除操作，此外它還帶來了其他優(yōu)勢：

1. 查找性能更高：布隆過濾器要采用多種哈希函數(shù)進(jìn)行多次哈希，而布谷鳥過濾器只需一次哈希
2. 節(jié)省更多空間：布谷鳥過濾器記錄元素更加緊湊，論文中提到，如果期望誤報率在 3% 以下，半排序桶布谷鳥過濾器每個元素所占用的空間要比布隆過濾器中單個元素占用空間要小

布谷鳥過濾器之所以被稱為“布谷鳥”，是因為它的工作原理類似于布谷鳥在自然界中的行為。布谷鳥以將自己的蛋產(chǎn)在其他鳥類的巢中而聞名，這樣一來，寄主鳥就會撫養(yǎng)布谷鳥的幼鳥。在布谷鳥過濾器中，如果一個位置已經(jīng)被占用，新元素會“驅(qū)逐”現(xiàn)有元素，將其移到其他位置。這種“驅(qū)逐”行為類似于布谷鳥將其他鳥蛋推出巢外，以便安置自己的蛋。因此，這種過濾器得名為“布谷鳥”過濾器。

布谷鳥過濾器本質(zhì)上是一個 桶數(shù)組，每個桶中保存若干數(shù)量的 指紋（指紋由元素的部分 Hash 值計算出來）。定義一個布谷鳥過濾器，每個桶記錄 2 個指紋，5 號桶和 11 號桶分別記錄保存 a, b 和 c, d 元素的指紋，如下所示：

圖片

此時，向其中插入新的元素 e，發(fā)現(xiàn)它被哈希到的兩個候選桶分別為 5 號 和 11 號，但是這兩個桶中的元素已經(jīng)添加滿了：

圖片

按照布谷鳥過濾器的特性，它會將其中的一個元素重哈希到其他的桶中（具體選擇哪個元素，由具體的算法指定），新元素占據(jù)該元素的位置，如下：

圖片

以上便是向布谷鳥過濾器中添加元素并發(fā)生沖突時的操作流程，在我們的例子中，重新放置元素 e 觸發(fā)了另一個重置，將現(xiàn)有的項 a 從桶 5 踢到桶 15。這個過程可能會重復(fù)，直到找到一個能容納元素的桶，這就使得布谷鳥哈希表更加緊湊，因此可以更加節(jié)省空間。如果沒有找到空桶則認(rèn)為此哈希表太滿，無法插入。雖然布谷鳥哈?？赡軋?zhí)行一系列重置，但其均攤插入時間為 **O(1)**。

與布隆過濾器一樣，布谷鳥過濾器同樣會造成假陽性，造成假陽性的有以下原因：

1. 有限的空間：布谷鳥過濾器使用有限數(shù)量的桶和每個桶中的有限空間來存儲元素的指紋。當(dāng)多個元素的指紋映射到相同的桶時，可能會導(dǎo)致不同元素的指紋存儲在同一位置
2. 指紋沖突：由于指紋是元素的哈希值的縮減版本，可能會有不同的元素產(chǎn)生相同的指紋。當(dāng)查詢一個不存在的元素時，可能會發(fā)現(xiàn)其指紋已經(jīng)存在于過濾器中，從而導(dǎo)致假陽性
3. 哈希函數(shù)的性質(zhì)：哈希函數(shù)的選擇和指紋長度決定了指紋的唯一性和沖突概率。較短的指紋更容易產(chǎn)生沖突，從而增加假陽性的概率
4. 負(fù)載因子：隨著過濾器接近滿載，沖突的概率增加，這會導(dǎo)致更多的“驅(qū)逐”操作。在高負(fù)載情況下，假陽性率也可能上升

cuckoofilter 是 Github 上 Star 數(shù)較多的一個倉庫，它參考了論文內(nèi)容，并用 Golang 實現(xiàn)了布谷鳥過濾器，大家感興趣的話可以直接去參考它的源碼。該過濾器重要的參數(shù)如下：

1. 每個元素有 2 個候選桶，每個桶記錄 4 個指紋：該配置能夠使桶的利用率達(dá)到 95%，能夠滿足多數(shù)場景，當(dāng)指定假陽性率在 0.00001 和 0.002 之間時，可以將每個元素占用空間最小化
2. 指紋的靜態(tài)大小為 8 位：指定誤報率為 0.03，根據(jù)公式 f >= log2(2b/r) b為桶的大小 r為誤報率，計算出指紋大小為 8。在 2 個候選桶和 4 個指紋的配置下，隨著指紋大小變大，空間利用率不會再隨之增加，僅降低假陽率

我們在此討論下它的刪除方法實現(xiàn)：

// Delete 刪除過濾器中的指紋
func (cf *Filter) Delete(data []byte) bool {
  // 嘗試在首選桶中刪除
  i1, fp := getIndexAndFingerprint(data, cf.bucketPow)
  if cf.delete(fp, i1) {
    return true
  }
  // 刪除失敗，則嘗試從備用桶刪除
  i2 := getAltIndex(fp, i1, cf.bucketPow)
  return cf.delete(fp, i2)
}

它的刪除方法實現(xiàn)比較簡單：它檢查給定元素的兩個候選桶，如果在首選桶中匹配到則將該指紋移除，否則去備用桶中匹配，在備用桶中則移除備用桶指紋，如果備用桶中沒有，則會提示刪除失敗。如果兩個元素 a, b 發(fā)生碰撞（共享桶和指紋），那么在 a 元素刪除后，因為 b 元素的存在，仍然會判斷 a 元素在過濾器中，表現(xiàn)出假陽性。需要注意的是，想要安全的刪除某元素，必須事先插入它，否則刪除插入項可能會無意中刪除共享指紋的真實存在的項，而且如果多次插入重復(fù)元素，想要將其刪除干凈還需要知道該元素插入了多少次。

此外，相比于布隆過濾器它也存在一些的劣勢：

1. 插入性能可能會受到影響：隨著插入元素越多，空間利用率不斷提高，發(fā)生沖突的可能性越大，發(fā)生沖突之后，可能會不斷的觸發(fā)元素的重定位，插入性能會變差，一般通過最大重試次數(shù)來限制
2. 插入重復(fù)元素次數(shù)存在上限：布隆過濾器插入重復(fù)元素沒有負(fù)面影響，只是再標(biāo)記相同的位，而布谷鳥過濾器插入重復(fù)元素會觸發(fā)元素的重定位，因此它的重復(fù)元素插入存在上限

對于過濾器緩存的使用，大部分情景都是讀多寫少的，而重復(fù)插入并沒有什么意義，布谷鳥過濾器的刪除雖然不完美但總好過沒有（因為布隆過濾器想要刪除元素便需要重建，上億甚至幾十億的數(shù)據(jù)重建緩存也蠻花時間），同時還有更優(yōu)的查詢和存儲效率，應(yīng)該說在絕大多數(shù)情況下其都是一個性價比更高的選擇。