寫在前面

在大數(shù)據(jù)與云計(jì)算發(fā)展的時(shí)代，我們經(jīng)常會(huì)碰到這樣的問(wèn)題。我們是否能高效的判斷一個(gè)用戶是否訪問(wèn)過(guò)某網(wǎng)站的主頁(yè)（每天訪問(wèn)量上億）或者需要統(tǒng)計(jì)網(wǎng)站的pv、uv。最直接的想法是將所有的訪問(wèn)者存起來(lái)，然后每次用戶訪問(wèn)的時(shí)候與之前集合進(jìn)行比較。不管是將訪問(wèn)信息存在內(nèi)存（或數(shù)據(jù)庫(kù)）都會(huì)對(duì)服務(wù)器造成非常大的壓力。那是否存在一種方式，容忍一定的錯(cuò)誤率，高效（計(jì)算復(fù)雜度、空間復(fù)雜度）的實(shí)現(xiàn)訪問(wèn)量信息的跟蹤、統(tǒng)計(jì)呢？接下來(lái)介紹的布隆過(guò)濾器（BloomFilter）就可以滿足當(dāng)前的使用場(chǎng)景（注釋：基數(shù)計(jì)數(shù)法同樣能滿足pv、uv的統(tǒng)計(jì)）。

布隆過(guò)濾器簡(jiǎn)介

布隆過(guò)濾器（BloomFilter）是1970年由布隆提出的一種空間空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡(jiǎn)潔地表示一個(gè)集合，并判斷一個(gè)元素是否屬于這個(gè)集合。使用布隆過(guò)濾器，存在第一類出錯(cuò)（Falsepositive），但是不會(huì)存在第二類錯(cuò)誤（Falsenegative），因此，布隆過(guò)濾器擁有100%的召回率。也就是說(shuō)，布隆過(guò)濾器能夠準(zhǔn)確判斷一個(gè)元素不在集合內(nèi)，但只能判斷一個(gè)元素可能在集合內(nèi)。因此，BloomFilter不適合“零錯(cuò)誤”的應(yīng)用場(chǎng)合。在能夠容忍低錯(cuò)誤的應(yīng)用場(chǎng)合下，BloomFilter通過(guò)極少的錯(cuò)誤換取了存儲(chǔ)空間的極大節(jié)省。我們可以向布隆過(guò)濾器里添加元素，但是不能從中移除元素（普通布隆過(guò)濾器，增強(qiáng)的布隆過(guò)濾器是可以移除元素的）。隨著布隆過(guò)濾器中元素的增加，犯第一類錯(cuò)誤的可能性也隨之增大。

算法描述

一個(gè)空的布隆過(guò)濾器有長(zhǎng)度為M比特的bit數(shù)組構(gòu)成，且所有位都初始化0。一個(gè)元素通過(guò)K個(gè)不同的hash函數(shù)隨機(jī)散列到bit數(shù)組的K個(gè)位置上，K必須遠(yuǎn)小于M。K和M的大小由錯(cuò)誤率（falsepositiverate）決定。

Bloom Filter的一個(gè)例子集合S｛x，y，z｝。帶有顏色的箭頭表示元素經(jīng)過(guò)k（k＝3）hash函數(shù)的到在M（bit數(shù)組）中的位置。元素W不在S集合中，因?yàn)樵豔經(jīng)過(guò)k個(gè)hash函數(shù)得到在M（bit數(shù)組）的k個(gè)位置中存在值為0的位置。

向集合S中添加元素x：x經(jīng)過(guò)k個(gè)散列函數(shù)后，在M中得到k個(gè)位置，然后，將這k個(gè)位置的值設(shè)置為1。

判斷x元素是否在集合S中：x經(jīng)過(guò)k個(gè)散列函數(shù)后，的到k個(gè)位置的值，如果這k個(gè)值中間存在為0的，說(shuō)明元素x不在集合中——元素x曾經(jīng)插入到過(guò)集合S，則M中的k個(gè)位置會(huì)全部置為1；如果M中的k個(gè)位置全為1，則有兩種情形。情形一：這個(gè)元素在這個(gè)集合中；情形二：曾經(jīng)有元素插入的時(shí)候?qū)⑦@k個(gè)位置的值置為1了（第一類錯(cuò)誤產(chǎn)生的原因FalsePositive）。簡(jiǎn)單的布隆過(guò)濾器無(wú)法區(qū)分這兩種情況，在增強(qiáng)版中解決了這個(gè)問(wèn)題。

設(shè)計(jì)k個(gè)相互獨(dú)立的hash函數(shù)可能工作量比較大，但是一個(gè)好的hash函數(shù)是降低誤判率的關(guān)鍵。一個(gè)良好的hash函數(shù)應(yīng)該有寬輸出，他們之間的沖突應(yīng)盡量低，這樣k個(gè)hash函數(shù)能靜可能的將值hash的更多的位置。hash函數(shù)的設(shè)計(jì)是我們可以將k個(gè)不同的值（?0, 1, ...,?k???1）作為參數(shù)傳入，或者將它們加入主鍵中。對(duì)于大的M或者k，hash函數(shù)之間的獨(dú)立性對(duì)誤判率影響非常大（(Dillinger & Manolios (2004a),Kirsch & Mitzenmacher (2006))）,Dillinger在k個(gè)散列函數(shù)中，多次使用同一個(gè)函數(shù)散列，分析對(duì)誤判率的影響。

對(duì)于簡(jiǎn)單布隆過(guò)濾器來(lái)說(shuō)，從集合S中移除元素x是不可能的，且falsenegatives不允許。元素散列到k個(gè)位置，盡管可以 將這k個(gè)位置的值置為0來(lái)移除這個(gè)元素，但是這同事也移除了那些散落后，有值落在這k位中的元素。因此，沒(méi)有一種方法可以判斷移除這個(gè)元素后是否影響其它已經(jīng)加入集合中的元素，將k個(gè)位置置為0會(huì)引入二類誤差（falsenegative）。

時(shí)間復(fù)雜度和空間復(fù)雜度

在falsepositives的情況下，布隆過(guò)濾器相比其它的集合（平衡二叉樹(shù)、樹(shù)、hash表、數(shù)組、鏈表）只需要少量的存儲(chǔ)空間。布隆過(guò)濾器的添加和檢查元素是否在集合內(nèi)的復(fù)雜度為O(K)。Hash表的平均復(fù)雜度比布隆過(guò)濾器更低。Bloom過(guò)濾器在誤差最優(yōu)的情況下，平均每個(gè)元素大概是1.44bit。

錯(cuò)誤率估計(jì)

布隆過(guò)濾器判斷一個(gè)元素是否屬于它表示的集合時(shí)會(huì)存在已定的錯(cuò)誤率（falsepositiverate），接下來(lái)就估計(jì)錯(cuò)誤率的大小。在估計(jì)誤差前，我們假設(shè)kn<m(k哈希函數(shù)的個(gè)數(shù)，n集合中元素的個(gè)數(shù)，mbit數(shù)組的長(zhǎng)度）且哈希函數(shù)之間時(shí)相互獨(dú)立的，哈希函數(shù)散列的bit數(shù)組M中的位置時(shí)完全隨機(jī)的。

一個(gè)長(zhǎng)度為m的bit數(shù)組，元素在插入時(shí)經(jīng)過(guò)一次哈希散列后bit數(shù)組的某個(gè)位置的值沒(méi)有被置為1的概率為

經(jīng)過(guò)k個(gè)哈希函數(shù)散列后，還未被置為1的概率為

如果插入n個(gè)元素后，該位置還未被置為1的概率為

所以被置為1的概率為

現(xiàn)在判斷一個(gè)元素是否在結(jié)合中，經(jīng)過(guò)k個(gè)函數(shù)散列到k個(gè)bit數(shù)組的不同位置。所有這些位置的值為1的概率——誤判率。

這里使用了極限

這種計(jì)算方法不嚴(yán)格，因?yàn)榍懊婕僭O(shè)哈希函數(shù)和散列后值的分布是相互獨(dú)立的。但是，這個(gè)假設(shè)隨著m和n的增大誤判率更接近真實(shí)的誤判率。

Mitzenmacher and Upfal證明無(wú)假設(shè)情況下的誤判率的期望值相同。

最優(yōu)的哈希函數(shù)個(gè)數(shù)

既然布隆過(guò)濾器將集合映射到位數(shù)組中，那么選多少個(gè)hash函數(shù)才是錯(cuò)誤率最低的情況。這里有兩個(gè)互斥的理由：如果哈希函數(shù)的個(gè)數(shù)多，那么在對(duì)一個(gè)不屬于集合的元素進(jìn)行查詢時(shí)得到0的概率就大；但另一方面，如果哈希函數(shù)的個(gè)數(shù)少，那么位數(shù)組中的0就多。為了得到最優(yōu)的哈希函數(shù)個(gè)數(shù)，我們需要根據(jù)上一小節(jié)中的錯(cuò)誤率公式進(jìn)行計(jì)算。

誤判率

兩邊取自然對(duì)數(shù)，

，只要g取最小值，p就能取到最小值。由于p＝e^(-nk/m),我們可以將g改寫為

根據(jù)對(duì)稱法則可以得到當(dāng)p＝1/2時(shí)，也就是k＝ln2*(m/n)時(shí)，g取得最小值，在這種情況下，最小的錯(cuò)誤率p＝（1/2）^k≈(0.6185)^(m/n)。p＝1/2對(duì)應(yīng)著位數(shù)組中0和1各半。換句話說(shuō)，想保持錯(cuò)誤率低，最好讓位數(shù)組有一半還空著。

位數(shù)組的大小

在給定n（集合中元素的個(gè)數(shù)）和錯(cuò)誤率（最優(yōu)函數(shù)個(gè)數(shù)k的的錯(cuò)誤率）的情況下，位數(shù)組M的大小計(jì)算，在最優(yōu)k的情況下

化簡(jiǎn)為

得到

這意味著在錯(cuò)誤率為p的情況下，布隆過(guò)濾器的長(zhǎng)度為m才能容納n個(gè)元素（以上計(jì)算基于n,m->∞）。

布隆過(guò)濾器中元素個(gè)數(shù)的估算

Swamidass & Baldi (2007)給出了布隆過(guò)濾器元素個(gè)數(shù)估算的方法（詳細(xì)證明方式參考論文）

其中，n*表示布隆過(guò)濾元素個(gè)數(shù)的估算值，m表示布隆過(guò)濾器的大小，k表示哈希函數(shù)的個(gè)數(shù)，X表示布隆過(guò)濾器位值位1的個(gè)數(shù)。

布隆過(guò)濾器的并和交

布隆過(guò)濾器可以用來(lái)估算兩個(gè)集合之間的并合交。一下給出兩個(gè)集合之間并的計(jì)算方式：

A和B之間的并集的個(gè)數(shù)為：

所以A*與B*之間的交集的個(gè)數(shù)為：

布隆過(guò)濾的特性

布隆過(guò)濾器能夠容納任意多的元素（誤判率會(huì)增加），總是能向布隆過(guò)濾器中添加元素，不會(huì)報(bào)錯(cuò)（OutMemory等）;

布隆過(guò)濾器可以很方便的通過(guò)計(jì)算機(jī)的or \and操作計(jì)算兩個(gè)集合元素之間的交集（intersection）和并集（union）,但是同樣影響布隆過(guò)濾的準(zhǔn)確性。

例子

Googlebigtable、apachehbase和apachecassandra使用bloom過(guò)濾器判斷是否存在該行（rows）或（colums），以減少對(duì)磁盤的訪問(wèn)，提高數(shù)據(jù)庫(kù)的訪問(wèn)性能；

比特幣使用布隆過(guò)濾判斷錢包是否同步OK。

總結(jié)

在計(jì)算機(jī)這個(gè)領(lǐng)域里，我們常常碰到時(shí)間換空間\或空間換時(shí)間的情況，為了達(dá)到某一方面的性能，犧牲另外一方面。BloomFilter在時(shí)間和空間著兩者之間引入了另外一個(gè)概念——錯(cuò)誤率。也就是前文提到的布隆過(guò)濾不能準(zhǔn)確判斷一個(gè)元素是否在集合內(nèi)（類似的設(shè)計(jì)還有基數(shù)統(tǒng)計(jì)法）。引入錯(cuò)誤率后，極大的節(jié)省了存儲(chǔ)空間。

自從Burton Bloom在70年代提出Bloom Filter之后，Bloom Filter就被廣泛用于拼寫檢查和數(shù)據(jù)庫(kù)系統(tǒng)中。近一二十年，伴隨著網(wǎng)絡(luò)的普及和發(fā)展，Bloom Filter在網(wǎng)絡(luò)領(lǐng)域獲得了新生，各種Bloom Filter變種和新的應(yīng)用不斷出現(xiàn)?？梢灶A(yù)見(jiàn)，隨著網(wǎng)絡(luò)應(yīng)用的不斷深入，新的變種和應(yīng)用將會(huì)繼續(xù)出現(xiàn)，Bloom Filter必將獲得更大的發(fā)展。

---------------------

作者：永不言棄01

來(lái)源：CSDN

原文：https://blog.csdn.net/lvsaixia/article/details/51503231

版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請(qǐng)附上博文鏈接！