難纏的布隆過濾器，這次終於通透了

• 2021 年 7 月 5 日
• 筆記
• .NET

今天來聊一聊面試八股文：布隆過濾器。

說道布隆過濾器，就免不了說到緩存穿透。

緩存穿透

在高並發下，查詢一個並不存在的值時，緩存不會被命中，導致大量請求直接落到數據庫。

數據庫的響應能力肯定沒有緩存大，出線這樣的情況，一般是黑客攻擊，拖慢了系統的響應速度。

頭腦風暴

樸素的分析思路： 在緩存前加一道屏障：放置存在(可能存在)的查詢鍵，屏蔽不可能存在的查詢鍵，
業內一般使用布隆過濾器來做這個屏障。

布隆過濾器的實現過程

布隆過濾器內部維護了一個全為0的bit數組，幾個hash函數（f1,f2）

假設有輸入集合{N1,N2}，哈希函數f1、f2

1. 經過計算 f1(N1)=2, f2(N1)=5, 則將數組下表為2,5的位置標記為1：

2. 同理計算f2(N1)=3, f2(N2)=4,則將數組下表為3,4的位置標記為1：

3. 有第三個數N3，我們判斷N3在不在集合{N1,N2}中， 就進行f1(N3)、f2(N3)的計算

• 如果f1(N3),f2(N3)計算的值均落在上圖紅色區域， 則說明N3可能屬於集合{N1,N2}中的一員
• 如果f1(N3),f2(N3)計算的值有一個落在紅色區域的外面，則說明N3一定不屬於集合{N1,N2}

布隆過濾器的設計原理

(這裡是重點，再看不懂，私聊我)

數據庫所有的鍵，經過一次哈希運算，收斂到(A,B)區間，

某個待查詢的鍵K，如果經過同樣的哈希運算，落在(A,B)區間，因為存在哈希碰撞，所以我們說K有可能屬於數據庫中所有的鍵中的一員；

但是如果該K經過哈希運算，沒有落在收斂區間，則證明K一定不屬於原數據庫鍵。

那為什麼要使用多個哈希函數？
因為經過一次哈希函數落在收斂區間，只能說該K有可能屬於原數據庫鍵，但是如果經過多個哈希函數，還是落到收斂區間，概率疊加，無形中增大了該K屬於原數據庫鍵的概率。

總體上看： 布隆過濾器是利用了哈希算法的單向收斂性+概率論。

時間複雜度： 要判斷N是否屬於原查詢鍵，只需要經過幾次哈希運算，所以布隆過濾器判斷的過程是很快的，

布隆過濾器的應用

很明顯，布隆過濾器存在誤報， 經過上面的分析:誤報率跟哈希碰撞和有幾個哈希函數有關，

成熟的布隆過濾器，這些你都不需要考慮，只需要指定 ① 哈希結果的存儲區 ②容量 ③誤報率

using BloomFilter;
using System;
using System.Collections.Generic;

namespace BoomFilter
{
    class Program
    {
        static readonly IBloomFilter bf = FilterBuilder.Build(10000000, 0.03);
        static void Main(string[] args)
        {
            int size = 10000000;
            for (int i = 0; i < size; i++)
            {
                bf.Add(i);
            }

            var list = new List<int>();
            // 故意取100個不在布隆過濾器中的值，看下有多少值誤報
            for(int i= size+1;i<size+100;i++)
            {
                if (bf.Contains(i))
                {
                    list.Add(i);
                }
            }
            Console.WriteLine($"誤報的個數為：{list.Count}");
        }
    }
}

總結

布隆過濾器是 哈希函數單向收斂和 概率論的完美結合，

從上面的分析看，解決緩存穿透，我們在Cache前面預熱一個布隆過濾器，就可以阻止絕大部分非法的查詢鍵。

注意，布隆過濾器對刪除不友好，所以如果數據庫鍵有大量變更，需要重建布隆過濾器。