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