大家好，我是周末還在肝文的卷溪。

陌溪之前在面試字節(jié)提前批的時(shí)候，二面的面試官就問過 Redis 緩存穿透的問題，下面讓我們一起深度還原一下陌溪當(dāng)初的面試場景吧~

面試官：你的蘑菇博客項(xiàng)目用到了 Redis ？

陌溪：主要是為了緩解數(shù)據(jù)庫壓力，將首頁的一些熱門文章信息儲(chǔ)存在 Redis 中。

面試官：好，那你知道什么是緩存穿透么？

陌溪：那我以蘑菇博客的場景來聊聊什么是緩存穿透。

什么是緩存穿透？

舉個(gè)蘑菇博客中的案例來說，現(xiàn)在有一個(gè)博客詳情頁，詳情頁中的內(nèi)容是存儲(chǔ)在 Redis 中的，通過博客的 uid 進(jìn)行獲取，正常的情況是：用戶進(jìn)入博客詳情頁，傳遞 uid 獲取 Redis 中緩存的文章詳情，如果有內(nèi)容就直接訪問，如果緩存為空，那么需要訪問數(shù)據(jù)庫，然后從數(shù)據(jù)庫中查詢我們的博客詳情后，再存儲(chǔ)到 Redis 中，最后把數(shù)據(jù)返回給我們的頁面。

但是可能存在一些非法用戶，會(huì)通過不合法的 uid 去請求博客后臺(tái)，首先 redis 的緩存沒有命中該 key，那么就會(huì)去請求數(shù)據(jù)庫，這樣大量非法的請求直接打在數(shù)據(jù)庫中，可能會(huì)導(dǎo)致數(shù)據(jù)庫直接宕機(jī)，無法對外提供服務(wù)，這就是我們所說的緩存穿透問題。

面試官：OK，那來談?wù)勀⒐绞窃趺唇鉀Q緩存穿透的？

陌溪（內(nèi)心）：糟糕，蘑菇博客中我并沒有去解決緩存穿透問題，要是直接說沒有解決，豈不是 回家等通知 了？

陌溪：針對上面出現(xiàn)的情況，我們有一種簡單的解決方法就是，在數(shù)據(jù)庫沒有查詢該條數(shù)據(jù)的時(shí)候，我們讓該 key緩存一個(gè) 空數(shù)據(jù)，這樣用戶再次以該 key 請求后臺(tái)的時(shí)候，會(huì)直接返回 null，避免了再次請求數(shù)據(jù)庫。

面試官：好的，但是如果非法用戶使用不同的 key 去請求后臺(tái)時(shí)，那這樣還是每次都不會(huì)命中緩存，都會(huì)查詢數(shù)據(jù)庫，針對這種情況，你有什么解決方法呢？

陌溪（內(nèi)心）：這面試連環(huán)炮有些遭不住，還好之前看八股文的時(shí)候，有看到過布隆過濾器，這會(huì)剛好可以說了。

陌溪：這種情況，我會(huì)使用布隆過濾器來解決這個(gè)問題~

什么是布隆過濾器？

布隆過濾器的巨大作用 ，就是能夠迅速判斷一個(gè)元素是否存在一個(gè)集合中。因此它有如下幾個(gè)使用場景

• 網(wǎng)站爬蟲對 URL 的去重，避免爬取相同的 URL。

• 反垃圾郵件，從數(shù)十億個(gè)垃圾郵件列表中判斷某郵箱是否是垃圾郵件（同理，垃圾短信）

• 緩存穿透，將所有可能的數(shù)據(jù)緩存放到布隆過濾器中，當(dāng)黑客訪問不存在的緩存時(shí)，迅速返回避免緩存以及DB 掛掉。

布隆過濾器其內(nèi)部維護(hù)了一個(gè)全為 0 的 bit 數(shù)組，需要說明的是，布隆過濾器有一個(gè)誤判的概念，誤判率越低，則數(shù)組越長，所占空間越大。誤判率越高則數(shù)組越小，所占的空間多少。

假設(shè)，根據(jù)誤判率，我們生成一個(gè) 10 位的 bit 數(shù)組，以及 2 個(gè) hash 函數(shù) f1 和 f2，如下圖所示：生成的數(shù)組的位數(shù) 和 hash 函數(shù)的數(shù)量。這里我們不用去關(guān)心如何生成的，因?yàn)橛袛?shù)學(xué)論文進(jìn)行驗(yàn)證。

然后我們輸入一個(gè)集合，集合中包含 N1 和 N2，我們通過計(jì)算 f1(N1) = 2，f2(N1) = 5，則將數(shù)組下標(biāo)為 2 和下標(biāo)為 5 的位置設(shè)置成 1，就得到了下圖。

同理，我們再次進(jìn)行計(jì)算 N2的值， f1(N2) = 3，f2(N2) = 6。得到如下所示的圖

這個(gè)時(shí)候，假設(shè)我們有第三個(gè)數(shù) N3 過來了，需要判斷 N3 是否在集合 [N1,N2] 中，需要做的操作就是，使用 f1 和 f2 計(jì)算出數(shù)組中的地址

• 若值恰巧都位于上圖的紅色位置，我們認(rèn)為 N3在集合 [N1,N2] 中

• 若值有一個(gè)不位于上圖的紅色部分，我們認(rèn)為N3不在集合 [N1,N2] 中

這就是布隆過濾器的計(jì)算原理。

如何使用布隆過濾器

在 Java 中使用布隆過濾器，首先需要引入依賴，布隆過濾器擁有 Google 提供的一個(gè)開箱即用的組件，來幫助實(shí)現(xiàn)布隆過濾器。其實(shí)布隆過濾器的核心思想其實(shí)并不難，難的是在于如何設(shè)計(jì)隨機(jī)映射函數(shù)，到底映射幾次，二進(jìn)制向量設(shè)置多少比較合適。

然后編寫代碼，測試某元素是否存在于百萬元素集合中

    private static int size = 1000000;//預(yù)計(jì)要插入多少數(shù)據(jù)

    private static double fpp = 0.01;//期望的誤判率

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

    public static void main(String[] args) {
        //插入數(shù)據(jù)
        for (int i = 0; i < 1000000; i++) {
            bloomFilter.put(i);
        }
        int count = 0;
        for (int i = 1000000; i < 2000000; i++) {
            if (bloomFilter.mightContain(i)) {
                count++;
                System.out.println(i + '誤判了');
            }
        }
        System.out.println('總共的誤判數(shù):' + count);
    }

代碼分析

上面的代碼中，我們創(chuàng)建了一個(gè)布隆過濾器，其中有兩個(gè)重要的參數(shù)，分別是要預(yù)計(jì)插入的數(shù)據(jù)和我們所期望的誤判率，誤判率率不能為 0 。

首先向布隆過濾器中插入 0 ~ 100萬 條數(shù)據(jù)，然后在用 100萬 ~ 200萬的數(shù)據(jù)進(jìn)行測試

最后輸出結(jié)果，查看一下誤判率

現(xiàn)在有 100萬 不存在的數(shù)據(jù)，誤判了 10314 次，通過計(jì)算可以得出誤判率

10314 / 1000000 = 0.010314

和之前定義的誤判率為 0.01 相差無幾，這也說明了布隆過濾器在處理 Redis 緩存穿透問題上，也具有比較好的表現(xiàn)。

我是陌溪，我們下期再見~