Bloom Filter 原理與應(yīng)用
介紹
Bloom Filter是一種簡(jiǎn)單的節(jié)省空間的隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)，支持用戶查詢的集合。一般我們使用STL的std::set, stdext::hash_set，std::set是用紅黑樹實(shí)現(xiàn)的，stdext::hash_set是用桶式哈希表。上述兩種數(shù)據(jù)結(jié)構(gòu)，都會(huì)需要保存原始數(shù)據(jù)信息，當(dāng)數(shù)據(jù)量較大時(shí)，內(nèi)存就會(huì)是個(gè)問(wèn)題。如果應(yīng)用場(chǎng)景中允許出現(xiàn)一定幾率的誤判，且不需要逆向遍歷集合中的數(shù)據(jù)時(shí)，Bloom Filter是很好的結(jié)構(gòu)。
優(yōu)點(diǎn)
- 查詢操作十分高效。
- 節(jié)省空間。
- 易于擴(kuò)展成并行。
- 集合計(jì)算方便。
- 代碼實(shí)現(xiàn)方便。
- 有誤判的概率，即存在False Position。
- 無(wú)法獲取集合中的元素?cái)?shù)據(jù)。
- 不支持刪除操作。
缺點(diǎn)
- 有誤判的概率，即存在False Position。
- 無(wú)法獲取集合中的元素?cái)?shù)據(jù)。
- 不支持刪除操作。
定義
Bloom Filter是一個(gè)有m位的位數(shù)組，初始全為0，并有k個(gè)各自獨(dú)立的哈希函數(shù)。
圖1
添加操作
每個(gè)元素，用k個(gè)哈希函數(shù)計(jì)算出大小為k的哈希向量  "\bg_white \left (H_{1},H_{2}\cdots ,H_{k} \right )")
，將向量里的每個(gè)哈希值對(duì)應(yīng)的位設(shè)置為1。時(shí)間復(fù)雜度為  "\bg_white k\cdot O(F_{H})")
，一般字符串哈希函數(shù)的時(shí)間復(fù)雜度也就是 "\bg_white O(n)")
。
查詢操作
和添加類似，先計(jì)算出哈希向量，如果每個(gè)哈希值對(duì)應(yīng)的位都為1，則該元素存在。時(shí)間復(fù)雜度與添加操作相同。
示例
圖2表示m=16，k=2的Bloom Filter， 和 的哈希值分別為(3, 6)和(10, 3)。
圖2
False Position
如果某元素不在Bloom Filter中，但是它所有哈希值的位置均被設(shè)為1。這種情況就是False Position，也就是誤判。
借用示例，如下：
圖3
這個(gè)問(wèn)題其實(shí)和哈希表中的沖突是相同的道理，哈希表中可以使用開(kāi)散列和閉散列的方法，而Bloom Filter則允許這樣的情況發(fā)生，它更關(guān)心于誤判的發(fā)生概率。
概率
宏觀上，我們能得出以下結(jié)論：
| 參數(shù)表 | 變量 | 減少 | 增加 |
| 哈希函數(shù)總數(shù) | K | l 更少的哈希值計(jì)算 l 增加False Position的概率 | l 更多的計(jì)算 l 位值0減少 |
| Bloom Filter 大小 | M | l 更少的內(nèi)存 l 增加False Position的概率 | l 更多的內(nèi)存 l 降低概率 |
| 元素總數(shù) | N | l 降低False Position的概率 | l 增加概率 |
False Position的概率為 ^{k} "F=(1-e^{-\frac{kn}{m}})^{k}")
。
假設(shè)m和n已知，為了最小化False Position，則 
。
數(shù)據(jù)
圖4
擴(kuò)展
Counter Bloom Filter
Bloom Filter有個(gè)缺點(diǎn)，就是不支持刪除操作，因?yàn)樗恢滥骋粋€(gè)位從屬于哪些向量。那我們可以給Bloom Filter加上計(jì)數(shù)器，添加時(shí)增加計(jì)數(shù)器，刪除時(shí)減少計(jì)數(shù)器。
但這樣的Filter需要考慮附加的計(jì)數(shù)器大小，假如同個(gè)元素多次插入的話，計(jì)數(shù)器位數(shù)較少的情況下，就會(huì)出現(xiàn)溢出問(wèn)題。如果對(duì)計(jì)數(shù)器設(shè)置上限值的話，會(huì)導(dǎo)致Cache Miss，但對(duì)某些應(yīng)用來(lái)說(shuō)，這并不是什么問(wèn)題，如Web Sharing。
Compressed Bloom Filter
為了能在服務(wù)器之間更快地通過(guò)網(wǎng)絡(luò)傳輸Bloom Filter，我們有方法能在已完成Bloom Filter之后，得到一些實(shí)際參數(shù)的情況下進(jìn)行壓縮。
將元素全部添加入Bloom Filter后，我們能得到真實(shí)的空間使用率，用這個(gè)值代入公式計(jì)算出一個(gè)比m小的值，重新構(gòu)造Bloom Filter，對(duì)原先的哈希值進(jìn)行求余處理，在誤判率不變的情況下，使得其內(nèi)存大小更合適。
應(yīng)用
加速查詢
適用于一些key-value存儲(chǔ)系統(tǒng)，當(dāng)values存在硬盤時(shí)，查詢就是件費(fèi)時(shí)的事。
將Storage的數(shù)據(jù)都插入Filter，在Filter中查詢都不存在時(shí)，那就不需要去Storage查詢了。
當(dāng)False Position出現(xiàn)時(shí)，只是會(huì)導(dǎo)致一次多余的Storage查詢。
圖5
l Google的BigTable也使用了Bloom Filter，以減少不存在的行或列在磁盤上的查詢，大大提高了數(shù)據(jù)庫(kù)的查詢操作的性能。
l 在Internet Cache Protocol中的Proxy-Cache很多都是使用Bloom Filter存儲(chǔ)URLs，除了高效的查詢外，還能很方便得傳輸交換Cache信息。
網(wǎng)絡(luò)應(yīng)用
l P2P網(wǎng)絡(luò)中查找資源操作，可以對(duì)每條網(wǎng)絡(luò)通路保存Bloom Filter，當(dāng)命中時(shí)，則選擇該通路訪問(wèn)。
l 廣播消息時(shí)，可以檢測(cè)某個(gè)IP是否已發(fā)包。
l 檢測(cè)廣播消息包的環(huán)路，將Bloom Filter保存在包里，每個(gè)節(jié)點(diǎn)將自己添加入Bloom Filter。
l 信息隊(duì)列管理，使用Counter Bloom Filter管理信息流量。
垃圾郵件地址過(guò)濾
來(lái)自于Google黑板報(bào)的例子。
像網(wǎng)易，QQ這樣的公眾電子郵件（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é)的信息指紋，然后將這些信息指紋存入哈希表，由于哈希表的存儲(chǔ)效率一般只有 50%，因此一個(gè) email 地址需要占用十六個(gè)字節(jié)。一億個(gè)地址大約要 1.6GB， 即十六億字節(jié)的內(nèi)存）。因此存貯幾十億個(gè)郵件地址可能需要上百 GB 的內(nèi)存。
而Bloom Filter只需要哈希表 1/8 到 1/4 的大小就能解決同樣的問(wèn)題。
Bloom Filter決不會(huì)漏掉任何一個(gè)在黑名單中的可疑地址。而至于誤判問(wèn)題，常見(jiàn)的補(bǔ)救辦法是在建立一個(gè)小的白名單，存儲(chǔ)那些可能別誤判的郵件地址。
引用
[1] Bloom filter; http://en.wikipedia.org/wiki/Bloom_filter
[2] Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol;http://pages.cs.wisc.edu/~cao/papers/summary-cache/
[3] Network Applications of Bloom Filters: A Survey;http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.127.9672&rep=rep1&type=pdf
[4] An Examination of Bloom Filters and their Applications;http://cs.unc.edu/~fabian/courses/CS600.624/slides/bloomslides.pdf
[5] 數(shù)學(xué)之美系列二十一 － 布隆過(guò)濾器（Bloom Filter）;http://www.google.com.hk/ggblog/googlechinablog/2007/07/bloom-filter_7469.html