關注過 @Python大星 的小夥伴應該知道，2020 年 4 月 Python 小星最近裸面了阿里巴巴菜鳥網絡科技有限公司。
一面中面試官非常重視解決 Redis 緩存穿透問題的利器--布隆過濾器，關於 Python 小星菜鳥二面的情況，後續整理出來。
今天我們來盤一盤“布隆過濾器” 到底是何方妖孽？
一、布隆過濾器（Bloom Filter）
布隆
對不起，搞錯啦，不是這個“布隆”。
但是，這個“布隆過濾器”中的“布隆” 確實是個人名，1970 年提出的，用來測試一個元素是否在一個集合裡。有可能” 誤報 “，但肯定不會” 錯報 “：對布隆過濾器的一次查詢要麼返回 “可能在集合中 “，要麼” 肯定不在集合裡 “。
舉個例子，古代進城搜捕兇手，人物畫像的特徵太多，可能會讓兇手矇混過關進城，但是有些人可以肯定不是兇手，比如高矮胖瘦都不符合畫像的。
如果你前面理解了，我們再來說下專業術語：
布隆過濾器實際上是一個很長的二進制向量和一系列隨機映射函數，可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難。
二、為什麼我們在 Redis 緩存穿透要用布隆過濾器？
如果不用會出現什麼情況？
我們通常用 Redis 做緩存層，減少 Mysql 數據庫的連接次數。
使用 Redis 避免不了一個“緩存穿透”的問題，
緩存穿透是指查詢一個一定不存在的數據，由於緩存是不命中時被動寫的，並且出於容錯考慮，如果從存儲層查不到數據則不寫入緩存，這將導致這個不存在的數據每次請求都要到 DB 中去查詢，失去了緩存的意義。在流量大時，可能 DB 就掛掉了，要是有人利用不存在的 key 頻繁攻擊我們的應用，這就是漏洞。
如果我們這裡加上“布隆過濾器”，就可以緩解“緩存穿透”對 Mysql 數據庫的請求壓力。
三、布隆過濾器的原理
布隆過濾器會通過一定的錯誤率換取空間。
布隆過濾器通過 bit 數組來標識數據
假設 1 個元素只佔一個坑，位數組中的每個元素都只佔用 1 bit ，並且每個元素只能是 0 或者 1。
那麼申請一個 100w 個元素的位數組只佔用 1000000Bit / 8 = 125000 Byte = 125000/1024 kb ≈ 122kb 的空間。
如果你對 hashmap 原理熟悉的話，這個布隆過濾器的原理就很容易理解了。
缺點1：為什麼說布隆過濾器有一定誤識別率？？？
這是因為 hash算法計算出來的值會出現衝突，這就是我們常說的hashmap中的 hash 衝突一樣，比如我們數據沒有 id = 999 的，但是計算出來的值可能和已標識為 1 的值衝突，被“布隆過濾器” 誤識別。
那有小夥伴會問，如何提高布隆過濾器的識別率呢？
從 3 個方面可以提高：
① bit 數組長度
② hash 函數的個數
這就和買彩票一樣，數字越多，中獎概率越低。hash 函數的個數不是越多越好，需要參考 bit 數組的長度。
③ 如果布隆過濾器存儲的是黑名單，那麼可以建立小的白名單，存儲那些被誤判的信息。
布隆過濾器誤判：
如果布隆過濾器說數據存在，那有可能不存在，輸入誤判；
如果布隆過濾說數據不存在，那一定不存在。
缺點2：為什麼說布隆過濾器刪除困難？？？
一個放入容器的元素映射到 bit 數組的 k 個位置上是 1，刪除的時候不能簡單的直接置為 0，可能會影響其他元素的判斷。
如何解決布隆過濾器刪除困難的問題？？？
Counting Bloom Filter，它將標準 Bloom Filter 位數組的每一位擴展為一個小的計數器 (Counter)，在插入元素時給對應的 k(k 為哈希函數個數) 個 Counter 的值分別加 1，刪除元素時給對應的 k 個 Counter 的值分別減 1，Counting Bloom Filter 通過多佔用幾倍的存儲空間的代價，給 Bloom Filter 增加了刪除操作。
四、布隆過濾器實現
1、如何確定 bit 數組的長度和 hash 函數的個數
已知條件
- 存儲數量為 n
- 預期誤判率 為 fpp（False positive probability）
計算
- Bit 數組大小 m
- 哈希函數個數 k
① Bit 數組選擇
② hash 函數個數
2、布隆過濾器的實現
Guava 中就提供了一種 Bloom Filter 的實現。
① 在 springboot 項目中引入 maven 依賴
② 布隆過濾器測試
測試結果：
從上面的簡單測試，我們可以看到誤判率 320 / 10000 = 0.032.
從源碼中我們也可以看出 fpp = 0.03
注意：
BloomFilter.create(Funnels.integerFunnel(), n, fpp);// 可以設置自定義設置誤判率
@Python大星 | 文
