緩存穿透的解決方式？—布隆過濾器

作者：seven97 2025-04-30 08:47:41

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

簡要回答

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

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

圖片

發(fā)生場景：

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

緩存穿透解決方案：

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

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

圖片

業(yè)務(wù)邏輯前置校驗(yàn)

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

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

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

用戶黑名單限制：當(dāng)發(fā)生異常情況時(shí)，實(shí)時(shí)監(jiān)控訪問的對象和數(shù)據(jù)，分析用戶行為，針對故意請求、爬蟲或攻擊者，進(jìn)行特定用戶的限制；
添加反爬策略：比如添加請求簽名校驗(yàn)機(jī)制、比如添加IP訪問限制策略等等

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

擴(kuò)展-布隆過濾器

概述

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

原理

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

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

圖片

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

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

誤判率

布隆過濾器包含如下四個(gè)屬性：

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

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

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

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

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

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

圖片

布隆過濾器的效率和缺點(diǎn)

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

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

計(jì)數(shù)布隆過濾器

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

圖片

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

使用場景

Redis的緩存穿透

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

圖片

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

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

圖片

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

元素刪除場景

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

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

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

圖片

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

在刪除商品到使用新的布隆過濾器B 之間的這段時(shí)間的不存在的查詢有可能還會到數(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 實(shí)現(xiàn)，用于高效地判斷一個(gè)元素是否存在于集合中，在 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)建一個(gè)布隆過濾器，預(yù)計(jì)插入 3000000 個(gè)整數(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) 和查詢時(shí)間O(k) 都很優(yōu)秀，但是存在一定的誤判率（布隆過濾器認(rèn)為不存在，則一定不存在；布隆過濾器認(rèn)為存在，則只是可能存在）

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

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

拓展：布谷鳥過濾器

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

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

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

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

圖片

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

圖片

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

圖片

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

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

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

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

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

我們在此討論下它的刪除方法實(shí)現(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)
}

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

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

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

責(zé)任編輯：武曉燕來源： seven97

緩存穿透過濾器