引言
Data structures are nothing different. They are like the bookshelves of your application where you can organize your data. Different data structures will give you different facility and benefits. To properly use the power and accessibility of the data structures you need to know the trade-offs of using one.
不同的數(shù)據(jù)結(jié)構(gòu)有不同的適用場景和優(yōu)缺點(diǎn)，你需要仔細(xì)權(quán)衡自己的需求之后妥善適用它們。
布隆過濾器就是踐行這句話的代表。
我們先思考一下，通常你判斷某個元素是否存在用的是什么？應(yīng)該蠻多人回答 HashMap 吧，確實(shí)可以將值映射到 HashMap 的 Key，然后可以在 O(1) 的時間復(fù)雜度內(nèi)返回結(jié)果，效率奇高。但是 HashMap 的實(shí)現(xiàn)也有缺點(diǎn)，例如存儲容量占比高，而一旦你的數(shù)據(jù)量很多例如上億的時候，那 HashMap 占據(jù)的內(nèi)存大小就變得很可怕了。
還比如說你的數(shù)據(jù)集存儲在遠(yuǎn)程服務(wù)器上，本地服務(wù)接受輸入，而數(shù)據(jù)集非常大不可能一次性讀進(jìn)內(nèi)存構(gòu)建 HashMap 的時候，也會存在問題。
布隆過濾器
布隆過濾器即解決上述問題，本質(zhì)是一種比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)（probabilistic data structure），特點(diǎn)是高效地插入和查詢，可以用來告訴你 “某樣?xùn)|西一定不存在或者可能存在”。
相比于傳統(tǒng)的 List、Set、Map 等數(shù)據(jù)結(jié)構(gòu)，它更高效、占用空間更少，但是缺點(diǎn)是其返回的結(jié)果是概率性的，而不是確切的。
結(jié)構(gòu)模型及實(shí)現(xiàn)原理
布隆過濾器數(shù)據(jù)結(jié)構(gòu)
布隆過濾器是一個 bit 向量或者說 bit 數(shù)組，長這樣：
如果我們要映射一個數(shù)據(jù)（字符串、對象等）到布隆過濾器中，我們需要使用多個不同的哈希函數(shù)生成多個哈希值，并對每個生成的哈希值指向的 bit 位置更新為 1，例如針對值 “baidu” 和三個不同的哈希函數(shù)分別生成了哈希值 1、4、7，則上圖轉(zhuǎn)變?yōu)椋?/p>
Ok，我們現(xiàn)在再存一個值 “tencent”，如果哈希函數(shù)返回 3、4、8 的話，圖繼續(xù)變?yōu)椋?/p>
值得注意的是，4 這個 bit 位由于兩個值的哈希函數(shù)都返回了這個 bit 位，因此它被覆蓋了?，F(xiàn)在我們?nèi)绻氩樵?“dianping” 這個值是否存在，哈希函數(shù)返回了 1、5、8三個值，結(jié)果我們發(fā)現(xiàn) 5 這個 bit 位上的值為 0，說明沒有任何一個值映射到這個 bit 位上，因此我們可以很確定地說 “dianping” 這個值不存在。而當(dāng)我們需要查詢 “baidu” 這個值是否存在的話，那么哈希函數(shù)必然會返回 1、4、7，然后我們檢查發(fā)現(xiàn)這三個 bit 位上的值均為 1，那么我們可以說 “baidu” 存在了么？答案是不可以，只能是 “baidu” 這個值可能存在。
這是為什么呢？答案跟簡單，因?yàn)殡S著增加的值越來越多，被置為 1 的 bit 位也會越來越多，這樣某個值 “taobao” 即使沒有被存儲過，但是萬一哈希函數(shù)返回的三個 bit 位都被其他值置位了 1 ，那么程序還是會判斷 “taobao” 這個值存在。
支持刪除么
傳統(tǒng)的布隆過濾器并不支持刪除操作。但是名為 Counting Bloom filter 的變種可以用來測試元素計(jì)數(shù)個數(shù)是否絕對小于某個閾值，它支持元素刪除。
https://cloud.tencent.com/developer/article/1136056
如何選擇哈希函數(shù)個數(shù)和布隆過濾器長度
很顯然，過小的布隆過濾器很快所有的 bit 位均為 1，那么查詢?nèi)魏沃刀紩祷亍翱赡艽嬖凇保鸩坏竭^濾的目的了。布隆過濾器的長度會直接影響誤報(bào)率，布隆過濾器越長其誤報(bào)率越小。
另外，哈希函數(shù)的個數(shù)也需要權(quán)衡，個數(shù)越多則布隆過濾器 bit 位置位 1 的速度越快，且布隆過濾器的效率越低；但是如果太少的話，那我們的誤報(bào)率會變高。
如何選擇適合業(yè)務(wù)的 k 和 m 值呢，這里直接貼一個公式：
如何推導(dǎo)這個公式這里只是提一句，因?yàn)閷τ谑褂脕碚f并沒有太大的意義，你讓一個高中生來推會推得很快。k 次哈希函數(shù)某一 bit 位未被置為 1 的概率為：
插入n個元素后依舊為 0 的概率和為 1 的概率分別是：
標(biāo)明某個元素是否在集合中所需的 k 個位置都按照如上的方法設(shè)置為 1，但是該方法可能會使算法錯誤的認(rèn)為某一原本不在集合中的元素卻被檢測為在該集合中（False Positives），該概率由以下公式確定
最佳實(shí)踐
常見的適用常見有，利用布隆過濾器減少磁盤 IO 或者網(wǎng)絡(luò)請求，因?yàn)橐坏┮粋€值必定不存在的話，我們可以不用進(jìn)行后續(xù)昂貴的查詢請求。
另外，既然你使用布隆過濾器來加速查找和判斷是否存在，那么性能很低的哈希函數(shù)不是個好選擇，推薦 MurmurHash、Fnv 這些。
緩存穿透
如上，用戶進(jìn)行了一次條件錯誤的查詢，這時候redis是不存在的，按照常規(guī)流程就是去數(shù)據(jù)庫找了，可是這是一次錯誤的條件查詢，數(shù)據(jù)庫當(dāng)然也不會存在，也不會往redis里面寫值，返回給用戶一個空，這樣的操作一次兩次還好，可是次數(shù)多了還了得，我放redis本來就是為了擋一擋，減輕數(shù)據(jù)庫的壓力，現(xiàn)在redis變成了形同虛設(shè)，每次還是去數(shù)據(jù)庫查找了，這個就叫做緩存穿透，相當(dāng)于redis不存在了，被擊穿了。
對于這種良性情況還好解決，我們可以在redis緩存一個空字符串或者特殊字符串，比如&&，下次我們?nèi)edis中查詢的時候，當(dāng)取到的值是空或者&&，我們就知道這個值在數(shù)據(jù)庫中是沒有的，就不會在去數(shù)據(jù)庫中查詢，ps：這里緩存一定要設(shè)置過期時間，不然當(dāng)數(shù)據(jù)庫已經(jīng)新增（更新）了這一條記錄的時候，這樣會導(dǎo)致緩存和數(shù)據(jù)庫不一致的情況
但如果存在惡性情況（網(wǎng)絡(luò)攻擊），每次查詢的錯誤值是不一樣的，你每次都緩存特殊字符串就會有很大問題。比如我們的數(shù)據(jù)庫用戶id是111，112，113，114依次遞增，別人要攻擊你，故意拿-100，-936，-545這種亂七八糟的key來查詢，這時候redis和數(shù)據(jù)庫這種值都是不存在的，來一個穿透到數(shù)據(jù)庫查詢，又緩存起來，這時候數(shù)據(jù)庫的壓力加大，緩存壓力也會加大，這就可拍的多了。怎么辦呢，這時候我們今天的主角布隆過濾器就登場了。
布隆過濾器工作位置
第一步，將數(shù)據(jù)庫所有的數(shù)據(jù)加載到布隆過濾器。
第二步，當(dāng)有請求來的時候先去布隆過濾器查詢。
第三步，如果bf說沒有，直接返回；如果bf說有，在往下走之前的流程。
大Value拆分
Redis 因其支持 setbit 和 getbit 操作，且純內(nèi)存性能高等特點(diǎn)，因此天然就可以作為布隆過濾器來使用。但是布隆過濾器的不當(dāng)使用極易產(chǎn)生大 Value，增加 Redis 阻塞風(fēng)險，因此生成環(huán)境中建議對體積龐大的布隆過濾器進(jìn)行拆分。
拆分的形式方法多種多樣，但是本質(zhì)是不要將 Hash(Key) 之后的請求分散在多個節(jié)點(diǎn)的多個小 bitmap 上，而是應(yīng)該拆分成多個小 bitmap 之后，對一個 Key 的所有哈希函數(shù)都落在這一個小 bitmap 上。
