深入解析Bloom Filter(上)

本文將介紹：

提出問題

Google的爬蟲每天需要抓取大量的網頁。于是就有一個問題：每當爬蟲分析出一個url的時候，是抓呢，還是不抓呢？如何知道這個url已經爬過了？

這個問題，歸納抽象后可以定義為：

給定一個集合S（注意，這里的集合是傳統意義上的集合：元素彼此不同。本文不考慮multiset），給定一個元素e，需要判斷$e\in S$ 是否成立。（學術界一般稱為membership問題）

分析問題

都有哪些方案可以解決這個問題？

一種簡單的想法是把url存儲在一個哈希表中，每次去表里look up下判斷是否存在。假如每個url占用40B，那么10億條url將占用大概30多GB的內存！Can this be more space efficient ?

解決問題

我們可不可以不存url本身？這樣子所需空間就會大大減少了。于是我們想到一個很經典的做法：bitmap（位圖）。將集合S中的url哈希到bitmap上，給定一個url，只需要將它hash，得到它在bitmap的下標，檢查該位置是否為1即可。

這樣做空間是省了，可是也產生了一個問題：由于沖突（碰撞），不是集合S中的元素也可能被哈希到值為1的位置上，導致誤報。

給定一個元素e，如果實際上$e\notin S$ 而被判為 $e\in S$，那么我們稱e是false positive（偽正例。順便說一句，false positive等的分析在machine learning的classification任務里評價model時非常重要）。

如何降低false positive的概率呢？Bloom Filter的想法是使用多個獨立的哈希函數。

Standard Bloom Filter

在傳統的Bloom Filter中，我們有：

集合S：其大小為m。也就是說，集合中有m個不同元素。

可用內存B：B被當成位數組bitmap來使用，大小為n。（有n個bit）。

哈希函數：有k個獨立的、均勻分布的哈希函數。

Bloom Filter的做法是：初始時，所有比特位都初始化為0。對于集合中的每個元素，利用k個哈希函數，對它哈希得到k個位置，將bitmap中的對應的k個位置置為1。

給定一個元素e，為了判斷它是否是集合中的元素，也利用該k個函數得到k個位置，檢查該k個位置是否都為1，如果是，認為$e\in S$，否則認為$e\notin S$。

不難看出，如果$e\in S$，那么Bloom Filter肯定會正確判斷出$e\in S$，但是它還是可能產生false positive。那么，如何分析false positive的概率呢？

false positive發生時，表示哈希該元素后得到的k個位置都為1。這個概率大概為：

$P\approx p_1^k$

其中$p_1$代表某位為1的概率，它等于：

$p_1 = 1 - p_0$

對于$p_0$，表示某個特定的比特位為0。什么時候該位才為0呢？也就是說m個元素各自經過k次哈希得到km個對象，沒有一個對象定位到了該位置。某個對象定位到該位置的概率為$\frac{1}{n}$，因此我們可以得到：

$p_0 = (1 - \frac{1}{n})^{mk}$

分析$p_0$。在實際應用中，n一般很大，根據重要極限公式，我們不難得到：

$p_0 = (1 - \frac{1}{n})^{mk} = (1-\frac{1}{n})^{-n{\frac{mk}{-n}}} \approx e^{-\frac{mk}{n}} $

代入到最上面的那個式子，我們不難得到：

$P \approx ({1 - e^{-\frac{mk}{n}}})^{k}$

當k為何值時，P取得最小，false positive possibility最低呢？

令 $f(k) = ({1 - e^{-\frac{mk}{n}}})^{k}$

$ln(f(k)) = kln({1 - e^{-\frac{mk}{n}}})$

$\frac{f\prime(k)}{f(k)} = ln({1 - e^{-\frac{mk}{n}}}) + k(\frac{1}{1 - e^{- \frac{mk}{n}}})(- e^{-\frac{mk}{n}})(\frac{-m}{n})$

$f\prime(k) = f(k)(ln({1 - e^{-\frac{mk}{n}}}) + k(\frac{1}{1 - e^{- \frac{mk}{n}}})(- e^{-\frac{mk}{n}})(\frac{-m}{n}))$

看起來夠復雜了，然而別怕！！！

令$f\prime(k) = 0$ ， 我們有(注意到$f(k) > 0$ 恒成立)：

$ln({1 - e^{-\frac{mk}{n}}}) + k(\frac{1}{1 - e^{- \frac{mk}{n}}})(- e^{- \frac{mk}{n}})(\frac{-m}{n}) = 0$

作代換，令$\lambda = e^{-\frac{mk}{n}}$ 則 $k = \frac{-nln\lambda}{m}$，代入上式，得到

$(1-\lambda)ln(1-\lambda) = \lambda ln\lambda$

因此$\lambda = \frac{1}{2}$ ， $k = \frac{n}{m}ln2$

也就是說，當n和m固定時，選擇$k = \frac{n}{m}ln2$ 附近的一個整數，將使false positive possibility最小。

工程實現時，我們需要k個哈希函數或者哈希函數值。如何構造和獲得k個獨立的哈希函數呢？這篇 論文 提出，只需要兩個獨立的哈希函數hf1和hf2即可。那么可以通過如下方式獲得k個哈希函數值：

hash value = hf1(key) + i*hf2(key)

其中i=0、1、2…k-1

Counting Bloom Filter

除了存在false positive這個問題之外，傳統的Bloom Filter還有一個不足：無法支持刪除操作（想想看，是不是這樣的）。而Counting Bloom Filter(CBF)就是用來解決這個問題的。

在CBF中，維護的不是單純的標示0或者1的比特位，而是若干計數器counter。對于集合中的每個元素，利用k個哈希函數，對它哈希得到k個位置，將對應的k個位置上的k個counter都加1。刪除時，只需要把k個counter都減1即可。

那么，這個counter應該占用幾位呢？分配太多，浪費空間；分配太少，容易溢出。通過下面的分析，我們可以知道，實際使用時，4位足矣。

考察（是考察，不是考查。這兩個詞有什么區別？）某個位置，該位置的計數器counter的值$\xi$

$P(\xi = c) \approx \binom{mk}{c} {(\frac{1}{n})}^{c}({1-\frac{1}{n}})^{mk-c} = B(km,\frac{1}{n})$

這個式子有點點復雜（當然，可以用斯特林公式近似一下），然而回憶下概率論里的知識：若二項分布B(n,p)里n很大，p很小時，二項分布的極限近似分布是泊松分布$P(\lambda=k) = \frac{\lambda^k}{k!}{e}^{-\lambda}$，其中$\lambda=np$，因此：

$P(\xi = c) \approx \binom{mk}{c} {(\frac{1}{n})}^{c}({1-\frac{1}{n}})^{mk-c} \approx \frac{({\frac{km}{n}})^{c}}{c!}{e}^{-{\frac{km}{n}}}$

令$k = \frac{n}{m}ln2$，代入，我們得到

$P(\xi >16) \approx \frac{(ln2)^{16}}{16!} * \frac{1}{2} < \frac{1}{16!} = \frac{1}{20922789888000}$

也就是說，選擇4位來存counter在實際情況中已經足矣，發生溢出的概率極小。

本文小結

總結下，Bloom Filter可以用在什么地方，或者說，在什么場景下，你應該想到這種技術：

1，回答是或者不是的問題。你需要判斷一個元素是否屬于某個集合，僅僅這樣。你不應該要求更多。如果你想獲得該元素對應的value或者還有其他payload，那么bloom filter不適合你，你需要哈希表。

2，允許false positive。也就是說，發生false positive不應該是致命的。比如說，搜索引擎的爬蟲里，如果url不是set的元素，卻被bloom filter過濾了，那么頂多就是不抓它而已，沒啥特別大的損失。

3，空間敏感。作為一種概率數據結構，Bloom Filter不存儲原始數據（比如說url），這也是它為什么space efficient的本質原因。

有了Standard Bloom Filter和Couting Bloom Filter，似乎可以滿足絕大多數需求了，然而，這里面還是有問題。什么問題？請看下集。