什么是布隆過(guò)濾器

本質(zhì)上布隆過(guò)濾器是一種數(shù)據(jù)結(jié)構(gòu)，比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)（probabilistic data structure）闪唆，特點(diǎn)是高效地插入和查詢(xú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ù)載因子的存在重归，通常空間是不能被用滿(mǎn)的镰官，而一旦你的值很多例如上億的時(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 的話(huà)舆绎，圖繼續(xù)變?yōu)椋?/p>

image

值得注意的是鲤脏，4 這個(gè) bit 位由于兩個(gè)值的哈希函數(shù)都返回了這個(gè) bit 位，因此它被覆蓋了÷蓝洌現(xiàn)在我們?nèi)绻氩樵?xún) “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)我們需要查詢(xún) “baidu” 這個(gè)值是否存在的話(huà)则拷，那么哈希函數(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è)值共同覆蓋的話(huà)橄镜，一旦你刪除其中一個(gè)值例如 “tencent” 而將其置位 0，那么下次判斷另一個(gè)值例如 “baidu” 是否存在的話(huà)冯乘，會(huì)直接返回 false洽胶，而實(shí)際上你并沒(méi)有刪除它。

如何解決這個(gè)問(wèn)題裆馒，答案是計(jì)數(shù)刪除姊氓。但是計(jì)數(shù)刪除需要存儲(chǔ)一個(gè)數(shù)值，而不是原先的 bit 位喷好，會(huì)增大占用的內(nèi)存大小翔横。這樣的話(huà)，增加一個(gè)值就是將對(duì)應(yīng)索引槽上存儲(chǔ)的值加一绒窑，刪除則是減一棕孙，判斷是否存在則是看值是否大于0舔亭。

如何選擇哈希函數(shù)個(gè)數(shù)和布隆過(guò)濾器長(zhǎng)度

很顯然些膨，過(guò)小的布隆過(guò)濾器很快所有的 bit 位均為 1，那么查詢(xún)?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ò)濾器的效率越低噩峦；但是如果太少的話(huà)锭沟，那我們的誤報(bào)率會(huì)變高。

image

k 為哈希函數(shù)個(gè)數(shù)识补，m 為布隆過(guò)濾器長(zhǎng)度族淮，n 為插入的元素個(gè)數(shù)，p 為誤報(bào)率凭涂。
至于如何推導(dǎo)這個(gè)公式祝辣，我在知乎發(fā)布的文章有涉及，感興趣可以看看切油，不感興趣的話(huà)記住上面這個(gè)公式就行了蝙斜。

最佳實(shí)踐

常見(jiàn)的適用常見(jiàn)有，利用布隆過(guò)濾器減少磁盤(pán) IO 或者網(wǎng)絡(luò)請(qǐng)求澎胡，因?yàn)橐坏┮粋€(gè)值必定不存在的話(huà)孕荠，我們可以不用進(jìn)行后續(xù)昂貴的查詢(xún)請(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 上。

作者：YoungChen__
鏈接：http://www.reibang.com/p/2104d11ee0a2
來(lái)源：簡(jiǎn)書(shū)
著作權(quán)歸作者所有甚牲。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)义郑，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

直觀的說(shuō)丈钙，bloom算法類(lèi)似一個(gè)hash set非驮，用來(lái)判斷某個(gè)元素（key）是否在某個(gè)集合中。
和一般的hash set不同的是雏赦，這個(gè)算法無(wú)需存儲(chǔ)key的值劫笙，對(duì)于每個(gè)key芙扎，只需要k個(gè)比特位，每個(gè)存儲(chǔ)一個(gè)標(biāo)志填大，用來(lái)判斷key是否在集合中戒洼。

算法：
1. 首先需要k個(gè)hash函數(shù)，每個(gè)函數(shù)可以把key散列成為1個(gè)整數(shù)
2. 初始化時(shí)允华，需要一個(gè)長(zhǎng)度為n比特的數(shù)組施逾，每個(gè)比特位初始化為0
3. 某個(gè)key加入集合時(shí)，用k個(gè)hash函數(shù)計(jì)算出k個(gè)散列值例获，并把數(shù)組中對(duì)應(yīng)的比特位置為1
4. 判斷某個(gè)key是否在集合時(shí)汉额，用k個(gè)hash函數(shù)計(jì)算出k個(gè)散列值，并查詢(xún)數(shù)組中對(duì)應(yīng)的比特位榨汤，如果所有的比特位都是1蠕搜，認(rèn)為在集合中。

優(yōu)點(diǎn)：不需要存儲(chǔ)key收壕，節(jié)省空間

缺點(diǎn)：
1. 算法判斷key在集合中時(shí)妓灌，有一定的概率key其實(shí)不在集合中
2. 無(wú)法刪除

典型的應(yīng)用場(chǎng)景：
某些存儲(chǔ)系統(tǒng)的設(shè)計(jì)中，會(huì)存在空查詢(xún)?nèi)毕荩寒?dāng)查詢(xún)一個(gè)不存在的key時(shí)蜜宪，需要訪問(wèn)慢設(shè)備虫埂，導(dǎo)致效率低下。
比如一個(gè)前端頁(yè)面的緩存系統(tǒng)圃验，可能這樣設(shè)計(jì)：先查詢(xún)某個(gè)頁(yè)面在本地是否存在掉伏，如果存在就直接返回，如果不存在澳窑，就從后端獲取斧散。但是當(dāng)頻繁從緩存系統(tǒng)查詢(xún)一個(gè)頁(yè)面時(shí)，緩存系統(tǒng)將會(huì)頻繁請(qǐng)求后端摊聋，把壓力導(dǎo)入后端鸡捐。

這是只要增加一個(gè)bloom算法的服務(wù)，后端插入一個(gè)key時(shí)麻裁，在這個(gè)服務(wù)中設(shè)置一次
需要查詢(xún)后端時(shí)箍镜，先判斷key在后端是否存在，這樣就能避免后端的壓力煎源。

image

</small>

布隆過(guò)濾器［1］（Bloom Filter）是由布律亍（Burton Howard Bloom）在1970年提出的。它實(shí)際上是由一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)組成薪夕，布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中脚草。它的優(yōu)點(diǎn)是空間效率和查詢(xún)時(shí)間都遠(yuǎn)遠(yuǎn)超過(guò)一般的算法赫悄，缺點(diǎn)是有一定的誤識(shí)別率（假正例False positives原献，即Bloom Filter報(bào)告某一元素存在于某集合中馏慨，但是實(shí)際上該元素并不在集合中）和刪除困難，但是沒(méi)有識(shí)別錯(cuò)誤的情形（即假反例False negatives姑隅，如果某個(gè)元素確實(shí)沒(méi)有在該集合中写隶，那么Bloom Filter 是不會(huì)報(bào)告該元素存在于集合中的，所以不會(huì)漏報(bào)）讲仰。

在日常生活中慕趴，包括在設(shè)計(jì)計(jì)算機(jī)軟件時(shí)，我們經(jīng)常要判斷一個(gè)元素是否在一個(gè)集合中鄙陡。比如在字處理軟件中冕房，需要檢查一個(gè)英語(yǔ)單詞是否拼寫(xiě)正確（也就是要判斷 它是否在已知的字典中）；在 FBI趁矾，一個(gè)嫌疑人的名字是否已經(jīng)在嫌疑名單上耙册；在網(wǎng)絡(luò)爬蟲(chóng)里，一個(gè)網(wǎng)址是否被訪問(wèn)過(guò)等等毫捣。最直接的方法就是將集合中全部的元素存在計(jì)算機(jī)中详拙，遇到一個(gè)新 元素時(shí)，將它和集合中的元素直接比較即可蔓同。一般來(lái)講饶辙，計(jì)算機(jī)中的集合是用哈希表（hash table）來(lái)存儲(chǔ)的。它的好處是快速準(zhǔn)確斑粱，缺點(diǎn)是費(fèi)存儲(chǔ)空間弃揽。當(dāng)集合比較小時(shí)，這個(gè)問(wèn)題不顯著则北，但是當(dāng)集合巨大時(shí)蹋宦，哈希表存儲(chǔ)效率低的問(wèn)題就顯現(xiàn)出來(lái) 了。比如說(shuō)咒锻，一個(gè)象 Yahoo,Hotmail 和 Gmai 那樣的公眾電子郵件（email）提供商冷冗，總是需要過(guò)濾來(lái)自發(fā)送垃圾郵件的人（spamer）的垃圾郵件。一個(gè)辦法就是記錄下那些發(fā)垃圾郵件的 email 地址惑艇。由于那些發(fā)送者不停地在注冊(cè)新的地址蒿辙，全世界少說(shuō)也有幾十億個(gè)發(fā)垃圾郵件的地址，將他們都存起來(lái)則需要大量的網(wǎng)絡(luò)服務(wù)器滨巴。如果用哈希表思灌，每存儲(chǔ)一億 個(gè) email 地址， 就需要 1.6GB 的內(nèi)存（用哈希表實(shí)現(xiàn)的具體辦法是將每一個(gè) email 地址對(duì)應(yīng)成一個(gè)八字節(jié)的信息指紋（詳見(jiàn)：googlechinablog.com/2006/08/blog-post.html）恭取， 然后將這些信息指紋存入哈希表泰偿，由于哈希表的存儲(chǔ)效率一般只有 50%，因此一個(gè) email 地址需要占用十六個(gè)字節(jié)蜈垮。一億個(gè)地址大約要 1.6GB耗跛， 即十六億字節(jié)的內(nèi)存）裕照。因此存貯幾十億個(gè)郵件地址可能需要上百 GB 的內(nèi)存。除非是超級(jí)計(jì)算機(jī)调塌，一般服務(wù)器是無(wú)法存儲(chǔ)的［2］晋南。（該段引用谷歌數(shù)學(xué)之美：http://www.google.com.hk/ggblog/googlechinablog/2007/07/bloom-filter_7469.html）

基本概念

如果想判斷一個(gè)元素是不是在一個(gè)集合里，一般想到的是將所有元素保存起來(lái)羔砾，然后通過(guò)比較確定负间。鏈表，樹(shù)等等數(shù)據(jù)結(jié)構(gòu)都是這種思路. 但是隨著集合中元素的增加姜凄，我們需要的存儲(chǔ)空間越來(lái)越大政溃，檢索速度也越來(lái)越慢。不過(guò)世界上還有一種叫作散列表（又叫哈希表态秧，Hash table）的數(shù)據(jù)結(jié)構(gòu)玩祟。它可以通過(guò)一個(gè)Hash函數(shù)將一個(gè)元素映射成一個(gè)位陣列（Bit Array）中的一個(gè)點(diǎn)。這樣一來(lái)屿聋，我們只要看看這個(gè)點(diǎn)是不是 1 就知道可以集合中有沒(méi)有它了空扎。這就是布隆過(guò)濾器的基本思想。

Hash面臨的問(wèn)題就是沖突润讥。假設(shè) Hash 函數(shù)是良好的转锈，如果我們的位陣列長(zhǎng)度為 m 個(gè)點(diǎn)，那么如果我們想將沖突率降低到例如 1%, 這個(gè)散列表就只能容納 m/100 個(gè)元素楚殿。顯然這就不叫空間有效了（Space-efficient）撮慨。解決方法也簡(jiǎn)單，就是使用多個(gè) Hash脆粥，如果它們有一個(gè)說(shuō)元素不在集合中砌溺，那肯定就不在。如果它們都說(shuō)在变隔，雖然也有一定可能性它們?cè)谡f(shuō)謊规伐，不過(guò)直覺(jué)上判斷這種事情的概率是比較低的。

優(yōu)點(diǎn)

相比于其它的數(shù)據(jù)結(jié)構(gòu)匣缘，布隆過(guò)濾器在空間和時(shí)間方面都有巨大的優(yōu)勢(shì)猖闪。布隆過(guò)濾器存儲(chǔ)空間和插入/查詢(xún)時(shí)間都是常數(shù)。另外, Hash 函數(shù)相互之間沒(méi)有關(guān)系肌厨，方便由硬件并行實(shí)現(xiàn)培慌。布隆過(guò)濾器不需要存儲(chǔ)元素本身，在某些對(duì)保密要求非常嚴(yán)格的場(chǎng)合有優(yōu)勢(shì)柑爸。

布隆過(guò)濾器可以表示全集吵护，其它任何數(shù)據(jù)結(jié)構(gòu)都不能；

k 和 m 相同，使用同一組 Hash 函數(shù)的兩個(gè)布隆過(guò)濾器的交并差運(yùn)算可以使用位操作進(jìn)行馅而。

缺點(diǎn)

但是布隆過(guò)濾器的缺點(diǎn)和優(yōu)點(diǎn)一樣明顯祥诽。誤算率（False Positive）是其中之一。隨著存入的元素?cái)?shù)量增加用爪，誤算率隨之增加原押。但是如果元素?cái)?shù)量太少胁镐，則使用散列表足矣偎血。

另外，一般情況下不能從布隆過(guò)濾器中刪除元素. 我們很容易想到把位列陣變成整數(shù)數(shù)組盯漂，每插入一個(gè)元素相應(yīng)的計(jì)數(shù)器加1, 這樣刪除元素時(shí)將計(jì)數(shù)器減掉就可以了颇玷。然而要保證安全的刪除元素并非如此簡(jiǎn)單。首先我們必須保證刪除的元素的確在布隆過(guò)濾器里面. 這一點(diǎn)單憑這個(gè)過(guò)濾器是無(wú)法保證的就缆。另外計(jì)數(shù)器回繞也會(huì)造成問(wèn)題帖渠。

False positives 概率推導(dǎo)

假設(shè) Hash 函數(shù)以等概率條件選擇并設(shè)置 Bit Array 中的某一位，m 是該位數(shù)組的大小竭宰，k 是 Hash 函數(shù)的個(gè)數(shù)空郊，那么位數(shù)組中某一特定的位在進(jìn)行元素插入時(shí)的 Hash 操作中沒(méi)有被置位的概率是：

image

那么在所有 k 次 Hash 操作后該位都沒(méi)有被置 "1" 的概率是：

image

如果我們插入了 n 個(gè)元素，那么某一位仍然為 "0" 的概率是：

image

因而該位為 "1"的概率是：

image

現(xiàn)在檢測(cè)某一元素是否在該集合中切揭。標(biāo)明某個(gè)元素是否在集合中所需的 k 個(gè)位置都按照如上的方法設(shè)置為 "1"狞甚，但是該方法可能會(huì)使算法錯(cuò)誤的認(rèn)為某一原本不在集合中的元素卻被檢測(cè)為在該集合中（False Positives），該概率由以下公式確定：

image

其實(shí)上述結(jié)果是在假定由每個(gè) Hash 計(jì)算出需要設(shè)置的位（bit） 的位置是相互獨(dú)立為前提計(jì)算出來(lái)的廓旬，不難看出哼审，隨著 m （位數(shù)組大小）的增加孕豹，假正例（False Positives）的概率會(huì)下降涩盾，同時(shí)隨著插入元素個(gè)數(shù) n 的增加，F(xiàn)alse Positives的概率又會(huì)上升励背，對(duì)于給定的m春霍，n，如何選擇Hash函數(shù)個(gè)數(shù) k 由以下公式確定：

image

此時(shí)False Positives的概率為：

image

而對(duì)于給定的False Positives概率 p叶眉，如何選擇最優(yōu)的位數(shù)組大小 m 呢终畅，

image

上式表明，位數(shù)組的大小最好與插入元素的個(gè)數(shù)成線(xiàn)性關(guān)系竟闪，對(duì)于給定的 m离福，n，k炼蛤，假正例概率最大為：

image

image

image

Bloom Filter 用例

Google 著名的分布式數(shù)據(jù)庫(kù) Bigtable 使用了布隆過(guò)濾器來(lái)查找不存在的行或列，以減少磁盤(pán)查找的IO次數(shù)［3］。

Squid 網(wǎng)頁(yè)代理緩存服務(wù)器在 cache digests 中使用了也布隆過(guò)濾器［4］絮识。

Venti 文檔存儲(chǔ)系統(tǒng)也采用布隆過(guò)濾器來(lái)檢測(cè)先前存儲(chǔ)的數(shù)據(jù)［5］绿聘。

SPIN 模型檢測(cè)器也使用布隆過(guò)濾器在大規(guī)模驗(yàn)證問(wèn)題時(shí)跟蹤可達(dá)狀態(tài)空間［6］。

Google Chrome瀏覽器使用了布隆過(guò)濾器加速安全瀏覽服務(wù)［7］次舌。

在很多Key-Value系統(tǒng)中也使用了布隆過(guò)濾器來(lái)加快查詢(xún)過(guò)程熄攘，如 Hbase，Accumulo彼念，Leveldb挪圾，一般而言，Value 保存在磁盤(pán)中逐沙，訪問(wèn)磁盤(pán)需要花費(fèi)大量時(shí)間哲思，然而使用布隆過(guò)濾器可以快速判斷某個(gè)Key對(duì)應(yīng)的Value是否存在，因此可以避免很多不必要的磁盤(pán)IO操作吩案，只是引入布隆過(guò)濾器會(huì)帶來(lái)一定的內(nèi)存消耗棚赔，下圖是在Key-Value系統(tǒng)中布隆過(guò)濾器的典型使用：

image

布隆過(guò)濾器相關(guān)擴(kuò)展

Counting filters

基本的布隆過(guò)濾器不支持刪除（Deletion）操作，但是 Counting filters 提供了一種可以不用重新構(gòu)建布隆過(guò)濾器但卻支持元素刪除操作的方法徘郭。在Counting filters中原來(lái)的位數(shù)組中的每一位由 bit 擴(kuò)展為 n-bit 計(jì)數(shù)器靠益，實(shí)際上，基本的布隆過(guò)濾器可以看作是只有一位的計(jì)數(shù)器的Counting filters残揉。原來(lái)的插入操作也被擴(kuò)展為把 n-bit 的位計(jì)數(shù)器加1胧后，查找操作即檢查位數(shù)組非零即可，而刪除操作定義為把位數(shù)組的相應(yīng)位減1冲甘，但是該方法也有位的算術(shù)溢出問(wèn)題绩卤，即某一位在多次刪除操作后可能變成負(fù)值，所以位數(shù)組大小 m 需要充分大江醇。另外一個(gè)問(wèn)題是Counting filters不具備伸縮性濒憋，由于Counting filters不能擴(kuò)展，所以需要保存的最大的元素個(gè)數(shù)需要提前知道陶夜。否則一旦插入的元素個(gè)數(shù)超過(guò)了位數(shù)組的容量凛驮，false positive的發(fā)生概率將會(huì)急劇增加。當(dāng)然也有人提出了一種基于 D-left Hash 方法實(shí)現(xiàn)支持刪除操作的布隆過(guò)濾器条辟，同時(shí)空間效率也比Counting filters高黔夭。

Data synchronization

Byers等人提出了使用布隆過(guò)濾器近似數(shù)據(jù)同步［9］。

Bloomier filters

Chazelle 等人提出了一個(gè)通用的布隆過(guò)濾器羽嫡，該布隆過(guò)濾器可以將某一值與每個(gè)已經(jīng)插入的元素關(guān)聯(lián)起來(lái)本姥，并實(shí)現(xiàn)了一個(gè)關(guān)聯(lián)數(shù)組Map［10］。與普通的布隆過(guò)濾器一樣杭棵，Chazelle實(shí)現(xiàn)的布隆過(guò)濾器也可以達(dá)到較低的空間消耗婚惫，但同時(shí)也會(huì)產(chǎn)生false positive，不過(guò)，在Bloomier filter中先舷，某 key 如果不在 map 中艰管，false positive在會(huì)返回時(shí)會(huì)被定義出的。該Map 結(jié)構(gòu)不會(huì)返回與 key 相關(guān)的在 map 中的錯(cuò)誤的值蒋川。

Compact approximators［11］

Stable Bloom filters［12］

Scalable Bloom filters［13］

Attenuated Bloom filters［14］

布隆過(guò)濾器是一個(gè)神奇的數(shù)據(jù)結(jié)構(gòu)牲芋，可以用來(lái)判斷一個(gè)元素是否在一個(gè)集合中。很常用的一個(gè)功能是用來(lái)去重捺球。在爬蟲(chóng)中常見(jiàn)的一個(gè)需求：目標(biāo)網(wǎng)站 URL 千千萬(wàn)缸浦，怎么判斷某個(gè) URL 爬蟲(chóng)是否寵幸過(guò)？簡(jiǎn)單點(diǎn)可以爬蟲(chóng)每采集過(guò)一個(gè) URL懒构，就把這個(gè) URL 存入數(shù)據(jù)庫(kù)中餐济，每次一個(gè)新的 URL 過(guò)來(lái)就到數(shù)據(jù)庫(kù)查詢(xún)下是否訪問(wèn)過(guò)耘擂。

select id from table where url = 'https://jaychen.cc'
復(fù)制代碼

但是隨著爬蟲(chóng)爬過(guò)的 URL 越來(lái)越多胆剧，每次請(qǐng)求前都要訪問(wèn)數(shù)據(jù)庫(kù)一次，并且對(duì)于這種字符串的 SQL 查詢(xún)效率并不高醉冤。除了數(shù)據(jù)庫(kù)之外秩霍，使用 Redis 的 set 結(jié)構(gòu)也可以滿(mǎn)足這個(gè)需求，并且性能優(yōu)于數(shù)據(jù)庫(kù)蚁阳。但是 Redis 也存在一個(gè)問(wèn)題：耗費(fèi)過(guò)多的內(nèi)存铃绒。這個(gè)時(shí)候布隆過(guò)濾器就很橫的出場(chǎng)了：這個(gè)問(wèn)題讓我來(lái)。

相比于數(shù)據(jù)庫(kù)和 Redis螺捐，使用布隆過(guò)濾器可以很好的避免性能和內(nèi)存占用的問(wèn)題颠悬。

布隆過(guò)濾器本質(zhì)是一個(gè)位數(shù)組，位數(shù)組就是數(shù)組的每個(gè)元素都只占用 1 bit 定血。每個(gè)元素只能是 0 或者 1赔癌。這樣申請(qǐng)一個(gè) 10000 個(gè)元素的位數(shù)組只占用 10000 / 8 = 1250 B 的空間。布隆過(guò)濾器除了一個(gè)位數(shù)組澜沟，還有 K 個(gè)哈希函數(shù)灾票。當(dāng)一個(gè)元素加入布隆過(guò)濾器中的時(shí)候，會(huì)進(jìn)行如下操作：

• 使用 K 個(gè)哈希函數(shù)對(duì)元素值進(jìn)行 K 次計(jì)算茫虽，得到 K 個(gè)哈希值刊苍。
• 根據(jù)得到的哈希值，在位數(shù)組中把對(duì)應(yīng)下標(biāo)的值置為 1濒析。

舉個(gè)??正什，假設(shè)布隆過(guò)濾器有 3 個(gè)哈希函數(shù)：f1, f2, f3 和一個(gè)位數(shù)組 arr。現(xiàn)在要把 https://jaychen.cc 插入布隆過(guò)濾器中：

• 對(duì)值進(jìn)行三次哈希計(jì)算号杏，得到三個(gè)值 n1, n2, n3婴氮。
• 把位數(shù)組中三個(gè)元素 arr[n1], arr[n2], arr[3] 置為 1。

當(dāng)要判斷一個(gè)值是否在布隆過(guò)濾器中，對(duì)元素再次進(jìn)行哈希計(jì)算莹妒，得到值之后判斷位數(shù)組中的每個(gè)元素是否都為 1名船，如果值都為 1，那么說(shuō)明這個(gè)值在布隆過(guò)濾器中旨怠，如果存在一個(gè)值不為 1渠驼，說(shuō)明該元素不在布隆過(guò)濾器中。

image.png

看了上面的說(shuō)明鉴腻，必然會(huì)提出一個(gè)問(wèn)題：當(dāng)插入的元素原來(lái)越多迷扇，位數(shù)組中被置為 1 的位置就越多，當(dāng)一個(gè)不在布隆過(guò)濾器中的元素爽哎，經(jīng)過(guò)哈希計(jì)算之后熏版，得到的值在位數(shù)組中查詢(xún)，有可能這些位置也都被置為 1宪躯。這樣一個(gè)不存在布隆過(guò)濾器中的也有可能被誤判成在布隆過(guò)濾器中柿顶。但是如果布隆過(guò)濾器判斷說(shuō)一個(gè)元素不在布隆過(guò)濾器中，那么這個(gè)值就一定不在布隆過(guò)濾器中渺贤。簡(jiǎn)單來(lái)說(shuō)：

• 布隆過(guò)濾器說(shuō)某個(gè)元素在雏胃，可能會(huì)被誤判。
• 布隆過(guò)濾器說(shuō)某個(gè)元素不在志鞍，那么一定不在瞭亮。

這個(gè)布隆過(guò)濾器的缺陷放到上面爬蟲(chóng)的需求中，可能存在某些沒(méi)有訪問(wèn)過(guò)的 URL 可能會(huì)被誤判為訪問(wèn)過(guò)固棚，但是如果是訪問(wèn)過(guò)的 URL 一定不會(huì)被誤判為沒(méi)訪問(wèn)過(guò)统翩。

Redis 中的布隆過(guò)濾器

redis 在 4.0 的版本中加入了 module 功能，布隆過(guò)濾器可以通過(guò) module 的形式添加到 redis 中此洲，所以使用 redis 4.0 以上的版本可以通過(guò)加載 module 來(lái)使用 redis 中的布隆過(guò)濾器厂汗。但是這不是最簡(jiǎn)單的方式，使用 docker 可以直接在 redis 中體驗(yàn)布隆過(guò)濾器黍翎。

> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
> docker exec -it bloomfilter redis-cli
復(fù)制代碼

redis 布隆過(guò)濾器主要就兩個(gè)命令：

• bf.add 添加元素到布隆過(guò)濾器中：bf.add urls https://jaychen.cc面徽。
• bf.exists 判斷某個(gè)元素是否在過(guò)濾器中：bf.exists urls https://jaychen.cc。

上面說(shuō)過(guò)布隆過(guò)濾器存在誤判的情況匣掸，在 redis 中有兩個(gè)值決定布隆過(guò)濾器的準(zhǔn)確率：

• error_rate：允許布隆過(guò)濾器的錯(cuò)誤率趟紊，這個(gè)值越低過(guò)濾器的位數(shù)組的大小越大，占用空間也就越大碰酝。
• initial_size：布隆過(guò)濾器可以?xún)?chǔ)存的元素個(gè)數(shù)霎匈，當(dāng)實(shí)際存儲(chǔ)的元素個(gè)數(shù)超過(guò)這個(gè)值之后，過(guò)濾器的準(zhǔn)確率會(huì)下降送爸。

redis 中有一個(gè)命令可以來(lái)設(shè)置這兩個(gè)值：

bf.reserve urls 0.01 100
復(fù)制代碼

三個(gè)參數(shù)的含義：

• 第一個(gè)值是過(guò)濾器的名字铛嘱。
• 第二個(gè)值為 error_rate 的值暖释。
• 第三個(gè)值為 initial_size 的值。

使用這個(gè)命令要注意一點(diǎn)：執(zhí)行這個(gè)命令之前過(guò)濾器的名字應(yīng)該不存在墨吓，如果執(zhí)行之前就存在會(huì)報(bào)錯(cuò)：(error) ERR item exists