原文鏈接：http://www.reibang.com/p/2104d11ee0a2
今天碰到個(gè)業(yè)務(wù)佩脊，他的 Redis 集群有個(gè)大 Value 用途是作為布隆過(guò)濾器，但溝通的時(shí)候被小懟了一下垫卤，意思大概是?“布隆過(guò)濾器原理都不懂威彰，還要我優(yōu)化？”穴肘。技術(shù)菜被人懟認(rèn)了歇盼、怪不得別人，自己之前確實(shí)只是聽(tīng)說(shuō)過(guò)這個(gè)评抚，但是沒(méi)深入了解過(guò)豹缀，趁這個(gè)機(jī)會(huì)補(bǔ)充一下知識(shí)。
在進(jìn)入正文之前慨代，之前看到的有句話我覺(jué)得說(shuō)得很好：
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)有不同的適用場(chǎng)景和優(yōu)缺點(diǎn)耿眉，你需要仔細(xì)權(quán)衡自己的需求之后妥善適用它們，布隆過(guò)濾器就是踐行這句話的代表鱼响。
什么是布隆過(guò)濾器
本質(zhì)上布隆過(guò)濾器是一種數(shù)據(jù)結(jié)構(gòu)，比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)（probabilistic data structure）组底，特點(diǎn)是高效地插入和查詢丈积，可以用來(lái)告訴你 “某樣?xùn)|西一定不存在或者可能存在”筐骇。
相比于傳統(tǒng)的 List、Set江滨、Map 等數(shù)據(jù)結(jié)構(gòu)铛纬，它更高效、占用空間更少唬滑，但是缺點(diǎn)是其返回的結(jié)果是概率性的告唆，而不是確切的。
實(shí)現(xiàn)原理
HashMap 的問(wèn)題
講述布隆過(guò)濾器的原理之前晶密，我們先思考一下擒悬，通常你判斷某個(gè)元素是否存在用的是什么？應(yīng)該蠻多人回答 HashMap 吧稻艰，確實(shí)可以將值映射到 HashMap 的 Key懂牧，然后可以在 O(1) 的時(shí)間復(fù)雜度內(nèi)返回結(jié)果，效率奇高尊勿。但是 HashMap 的實(shí)現(xiàn)也有缺點(diǎn)僧凤，例如存儲(chǔ)容量占比高，考慮到負(fù)載因子的存在元扔，通城＃空間是不能被用滿的，而一旦你的值很多例如上億的時(shí)候澎语，那 HashMap 占據(jù)的內(nèi)存大小就變得很可觀了途事。
還比如說(shuō)你的數(shù)據(jù)集存儲(chǔ)在遠(yuǎn)程服務(wù)器上，本地服務(wù)接受輸入咏连，而數(shù)據(jù)集非常大不可能一次性讀進(jìn)內(nèi)存構(gòu)建 HashMap 的時(shí)候盯孙，也會(huì)存在問(wèn)題。
布隆過(guò)濾器數(shù)據(jù)結(jié)構(gòu)
布隆過(guò)濾器是一個(gè) bit 向量或者說(shuō) bit 數(shù)組祟滴，長(zhǎng)這樣：
image
如果我們要映射一個(gè)值到布隆過(guò)濾器中振惰，我們需要使用多個(gè)不同的哈希函數(shù)生成多個(gè)哈希值，并對(duì)每個(gè)生成的哈希值指向的 bit 位置 1垄懂，例如針對(duì)值 “baidu” 和三個(gè)不同的哈希函數(shù)分別生成了哈希值 1骑晶、4、7草慧，則上圖轉(zhuǎn)變?yōu)椋?/p>
image
Ok桶蛔，我們現(xiàn)在再存一個(gè)值 “tencent”，如果哈希函數(shù)返回 3漫谷、4仔雷、8 的話，圖繼續(xù)變?yōu)椋?/p>
image
值得注意的是碟婆，4 這個(gè) bit 位由于兩個(gè)值的哈希函數(shù)都返回了這個(gè) bit 位电抚，因此它被覆蓋了∈玻現(xiàn)在我們?nèi)绻氩樵?“dianping” 這個(gè)值是否存在，哈希函數(shù)返回了 1公给、5借帘、8三個(gè)值，結(jié)果我們發(fā)現(xiàn) 5 這個(gè) bit 位上的值為 0肺然，說(shuō)明沒(méi)有任何一個(gè)值映射到這個(gè) bit 位上匣沼，因此我們可以很確定地說(shuō) “dianping” 這個(gè)值不存在狰挡。而當(dāng)我們需要查詢 “baidu” 這個(gè)值是否存在的話，那么哈希函數(shù)必然會(huì)返回 1释涛、4加叁、7，然后我們檢查發(fā)現(xiàn)這三個(gè) bit 位上的值均為 1它匕，那么我們可以說(shuō) “baidu” 存在了么窖认？答案是不可以，只能是 “baidu” 這個(gè)值可能存在烧给。
這是為什么呢喝噪？答案跟簡(jiǎn)單础嫡，因?yàn)殡S著增加的值越來(lái)越多酝惧，被置為 1 的 bit 位也會(huì)越來(lái)越多，這樣某個(gè)值 “taobao” 即使沒(méi)有被存儲(chǔ)過(guò)巫财，但是萬(wàn)一哈希函數(shù)返回的三個(gè) bit 位都被其他值置位了 1 哩陕，那么程序還是會(huì)判斷 “taobao” 這個(gè)值存在赫舒。
支持刪除么
目前我們知道布隆過(guò)濾器可以支持 add 和 isExist 操作闽瓢，那么 delete 操作可以么，答案是不可以，例如上圖中的 bit 位 4 被兩個(gè)值共同覆蓋的話园担，一旦你刪除其中一個(gè)值例如 “tencent” 而將其置位 0，那么下次判斷另一個(gè)值例如 “baidu” 是否存在的話艰山，會(huì)直接返回 false咏闪，而實(shí)際上你并沒(méi)有刪除它。
如何解決這個(gè)問(wèn)題纵装，答案是計(jì)數(shù)刪除据某。但是計(jì)數(shù)刪除需要存儲(chǔ)一個(gè)數(shù)值，而不是原先的 bit 位癣籽，會(huì)增大占用的內(nèi)存大小。這樣的話瓶籽，增加一個(gè)值就是將對(duì)應(yīng)索引槽上存儲(chǔ)的值加一埂材，刪除則是減一，判斷是否存在則是看值是否大于0楞遏。
如何選擇哈希函數(shù)個(gè)數(shù)和布隆過(guò)濾器長(zhǎng)度
很顯然寡喝，過(guò)小的布隆過(guò)濾器很快所有的 bit 位均為 1，那么查詢?nèi)魏沃刀紩?huì)返回“可能存在”预鬓，起不到過(guò)濾的目的了赊颠。布隆過(guò)濾器的長(zhǎng)度會(huì)直接影響誤報(bào)率劈彪，布隆過(guò)濾器越長(zhǎng)其誤報(bào)率越小。
另外痘括，哈希函數(shù)的個(gè)數(shù)也需要權(quán)衡滔吠，個(gè)數(shù)越多則布隆過(guò)濾器 bit 位置位 1 的速度越快，且布隆過(guò)濾器的效率越低翰舌；但是如果太少的話冬骚，那我們的誤報(bào)率會(huì)變高。
image
k 為哈希函數(shù)個(gè)數(shù)庇麦，m 為布隆過(guò)濾器長(zhǎng)度属愤，n 為插入的元素個(gè)數(shù)，p 為誤報(bào)率住诸。
至于如何推導(dǎo)這個(gè)公式，我在知乎發(fā)布的文章有涉及丧诺，感興趣可以看看奄薇，不感興趣的話記住上面這個(gè)公式就行了。
最佳實(shí)踐
常見(jiàn)的適用常見(jiàn)有呵晚，利用布隆過(guò)濾器減少磁盤 IO 或者網(wǎng)絡(luò)請(qǐng)求沫屡，因?yàn)橐坏┮粋€(gè)值必定不存在的話，我們可以不用進(jìn)行后續(xù)昂貴的查詢請(qǐng)求沮脖。
另外，既然你使用布隆過(guò)濾器來(lái)加速查找和判斷是否存在驶俊，那么性能很低的哈希函數(shù)不是個(gè)好選擇，推薦 MurmurHash榕酒、Fnv 這些故俐。
大Value拆分
Redis 因其支持 setbit 和 getbit 操作，且純內(nèi)存性能高等特點(diǎn)，因此天然就可以作為布隆過(guò)濾器來(lái)使用肩榕。但是布隆過(guò)濾器的不當(dāng)使用極易產(chǎn)生大 Value，增加 Redis 阻塞風(fēng)險(xiǎn)筐乳，因此生成環(huán)境中建議對(duì)體積龐大的布隆過(guò)濾器進(jìn)行拆分乔妈。
拆分的形式方法多種多樣，但是本質(zhì)是不要將 Hash(Key) 之后的請(qǐng)求分散在多個(gè)節(jié)點(diǎn)的多個(gè)小 bitmap 上勃刨，而是應(yīng)該拆分成多個(gè)小 bitmap 之后股淡，對(duì)一個(gè) Key 的所有哈希函數(shù)都落在這一個(gè)小 bitmap 上。
參考資料
probabilistic data structures:bloom filter
本文遵守創(chuàng)作共享?CC BY-NC-SA 3.0協(xié)議
