簡要回答

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

緩存穿透與緩存擊穿同樣非常相似，區別點在于緩存穿透的實際請求數據在數據庫中也沒有，而緩存擊穿是僅僅在緩存中沒命中，但是在數據庫中其實是存在對應數據的。

圖片

發生場景：

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

緩存穿透解決方案：

1. 緩存空值（null）或默認值

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

圖片

2. 業務邏輯前置校驗

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

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

• 在寫入數據時，使用布隆過濾器進行標記（相當于設置白名單），業務請求發現緩存中無對應數據時，可先通過查詢布隆過濾器判斷數據是否在白名單內（布隆過濾器可以判斷數據一定不存在），如果不在白名單內，則直接返回空或失敗。

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

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

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

擴展-布隆過濾器

概述

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

原理

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

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

圖片

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

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

誤判率

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

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

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

為什么就用一個hash函數不行？

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

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

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

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

圖片

布隆過濾器的效率和缺點

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

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

計數布隆過濾器

計數過濾器（Counting Bloom Filter）是布隆過濾器的擴展，標準 Bloom Filter 位數組的每一位擴展為一個小的計數器（Counter），在插入元素時給對應的 k （k 為哈希函數個數）個 Counter 的值分別加 1，刪除元素時給對應的 k 個 Counter 的值分別減 1。

圖片

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

使用場景

Redis的緩存穿透

對于一個數據查詢，其過程大致如下：

圖片

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

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

圖片

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

元素刪除場景

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

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

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

圖片

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

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

應用布隆過濾器

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 實現，用于高效地判斷一個元素是否存在于集合中，在 23.0 及之后版本中，是線程安全的。以下是 Guava 中布隆過濾器使用示例：

• 引入依賴

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <!-- 請根據需要選擇合適的版本 -->
    <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) {
        // 創建一個布隆過濾器，預計插入 3000000 個整數，假陽率為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.");
            }
        }
    }
}

布隆過濾器總結

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

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

普通布隆過濾器無法刪除元素，但可以通過計數布隆過濾器和定時重新構建布隆過濾器兩種方案實現刪除元素的效果。

拓展：布谷鳥過濾器

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

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

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

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

圖片

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

圖片

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

圖片

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

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

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

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

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

我們在此討論下它的刪除方法實現：

// 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)
}

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

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

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

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