深入解析Bloom Filter(中)

本篇將介紹：

在上篇文章，我們介紹了Standard Bloom Filter(SBF)和Counting Bloom Filter(CBF)。簡單回顧下，我們大概思路和歷程是：為了解決允許false positive下的membership問題，我們設計了哈希表算法，由于它所需空間巨大，我們引入bitmap方法；因為它false positive possibility太大，我們引入了SBF，它使用多個獨立的、均勻分布的哈希函數。而SBF的一個缺點是不支持刪除操作，為了能夠刪除，我們引入了CBF，然而，CBF存在一個問題。

什么問題呢？那就是空間利用率不高。這可以通過簡單的數學計算知道大概：

考察某個位置，該位置的計數器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=\frac{km}{n}$，并結合$k = \frac{n}{m}ln2$，可以得到，counter的期望值為：

$E(\xi) = \lambda = np = ln2 \approx 0.7$

即大量的counter的值都是0，空間效率不高。

在介紹新的Bloom Filter之前，我們一起先看看什么是所謂的d-left hashing。

d-left hashing

在d-left hashing中，我們有d張哈希子表（序號分別為1,2,…d，并且假設是從左到右），每張子表都包含B個bucket，每個bucket都包含w個cell，每個cell可以存放一個元素。

為了插入一個元素x，我們：

1，首先通過一個哈希函數hf，得到x的哈希函數值value = hf(x)

2，通過value，得到d個位置（每個位置對應每張子表），表示為：

(1,$B_1$) , (2,$B_2$),… (d,$B_d$)

其中(i,$B_i$)表示第i張子表，Bucket的index為$B_i$。

那么，到底插入哪張表呢？d-left hashing選擇$B_i$中負載最小（已經存放的元素最少）的位置。注意，這里說的是bucket的負載，不是子表的負載。如果有多個子表對應的位置負載都是最小，那么選擇最左邊（序號最小）的子表插入。

為了查找該元素，我們需要檢查d個位置，wd個cell（元素）。

d-left counting bloom filter

在基于d-left hashing的CBF中，我們有d張哈希子表（序號分別為1,2,…d，并且假設是從左到右），每張子表都包含B個bucket，每個bucket都包含w個cell，每個cell可以存放一個counter和一個fingerprint。

為了插入一個元素x，我們：

1，首先通過一個哈希函數hf，得到x的哈希函數值value = hf(x)

2，通過value，得到d個位置（每個位置對應每張子表）和對應的fingerprint，表示為d個位置向量：

(1,$B_1$,$fp_1$) , (2,$B_2$,$fp_2$),… (d,$B_d$,$fp_d$)

其中位置向量(i,$B_i$,$fp_i$)表示第i張子表，Bucket的index為$B_i$，fingerprint為$fp_i$。

3，通過d-left hashing將x插入，如果插入的位置(i,$B_i$,$fp_i$)上已經有cell的fingerprint等于$fp_i$，那么只需要將它的counter++即可。

舉個栗子，假設某時刻，我們有：

2張子表（d=2），每張子表有6個bucket（B=6），每個bucket包括3個cell（w=3），每個cell可以存放一個counter(4位表示，最大值為16)和fingerprint（6位表示）。

假如我們要插入元素x，我們對它進行hash，得到兩個位置向量：

(1, 1, 010100)和(2, 2, 010101)

$d_1$子表中index為1的bucket的負載，要小于$d_2$子表中index為2的bucket的負載，因此，我們選擇插入$d_1$中，如下：

如果得到的位置向量分別是(1, 1, 001100)和(2, 2, 010101)呢？那么，還是插入到$d_1$中index為1的bucket中，但是只需要將第二個cell里的counter++即可，如下圖：

看起來很完美，但是這種方案在刪除時會有問題。比如說，還是剛才的例子，我們欲插入x和y。分別得到x和y的位置向量們：

x: (1, 1, 010100)和(2, 2, 010101)

y: (1, 1, 010100)和(2, 4, 111111)

根據d-left hashing，x被插入到$d_1$中index為1的bucket中；y被插入到$d_2$中index為4的bucket中。好，這沒問題。如果現在要刪除y呢？我們需要檢查兩個位置，$d_1$中的index為1的bucket，以及$d_2$中index為4的bucket，要刪哪個？fp都是010100啊。這就出現問題。

什么時候會出現這種問題？當以下條件滿足時：

1，兩個元素的有公共【重合】的位置向量。位置向量相同，表示同一個子表，同一個bucket，以及相同的fingerprint。

2，其中一個元素被插入了公共位置向量對應的位置，另外一個元素沒有。

3，欲刪除未使用公共位置向量的元素（比如說上例中的y）

為了解決這個問題，作者做了兩點改進：

I 引入d輪隨機置換。

置換，即一一映射。假設置換為P，輸入為a和b，那么將滿足：

如果a = b，那么P(a) = P(b)

如果a != b ，那么P(a) != P(b)

以及它們的逆否命題

如果P(a) ！= P(b)，那么a ！= b

如果P(a) = P(b)，那么a = b

為了插入x，我們首先通過一個哈希函數hf，計算它的哈希函數值value = hf(x)。然后，我們對value進行d輪隨機置換，得到d個位置向量：

$P_1(value) = (1, B_1, fp_1)$

$P_2(value) = (2, B_2, fp_2)$

……

$P_d(value) = (d, B_d, fp_d)$

這里面有一個小問題：如果要插入的元素x和y不等，那么它們的置換可能相等嗎？當然可能。因為x和y雖然不等，但是它們的hash value可能相等，這樣它們的置換結果即位置向量可能相同。

別忘了，我們是對x和y的hash value進行置換，不是對x和y進行置換。

網上流傳很廣的 這篇 文章的解釋是錯誤的，小心！！！

II 插入修正

當得到d個位置向量后，和上面介紹的過程稍微不同：我們首先需要根據d個位置向量，從第1個子表開始，對每個子表$d_i$，去對應的位置$B_i$處查找是否有cell中的fp等于$fp_i$，如果有，我們把相應的counter++，插入動作完成，不用再繼續檢查后續子表了。

否則，當所有d個子表都沒有對應的$fp_i$時，我們運用d-left hashing，插入x。

綜合運用這兩點，我們知道上面所說的刪除時的問題已經不存在了。

假如欲插入x和y，分別對它們的hash value進行d輪（這里d=2）隨機置換后，有沒有可能得到如下的位置向量？

x: (1, 1, 010100)和(2, 2, 010101)

y: (1, 1, 010100)和(2, 4, 010111)

不可能。

注意到，x和y的第一個位置向量（對應第一張子表）完全相同（bucket index相同，fp也相同），也就是

$P_1(hf(x)) = P_1(hf(y))$

那么可以推出hf(x) = hf(y)，也就是x和y的哈希函數值相等，那么對于任何的i都有$P_i(hf(x)) = P_i(hf(y))$。

因此：

如果hf(x) = hf(y)，那么$P_i(hf(x)) \eq P_i(hf(y))$ (i=1,2,3…d)，假如先插入x后插入y。插入y的時候，會更新counter。后續刪除x或者y都不存在上述問題。

如果hf(x) != hf(y)，那么那么$P_i(hf(x)) \neq P_i(hf(y))$ (i=1,2,3…d)，那么x和y沒有公共的位置向量。后續刪除x或者y都不存在上述問題。

附錄

如何隨機置換

作者提供了一個簡單的函數：

$P_i(value) = (a * value ) mod 2^B$

其中value的范圍是[0, $2^B$]，a是隨機的一個奇數。

數學分析

首先，如果z是false positive，那么它的哈希函數值會和集合S中的某個元素的哈希函數值相等。也就是

hf(z) = hf(e) 其中 $e\in S$

這是因為，如果z是false positive，那么

$p_i(hf(z)) = p_i(hf(e))$

根據置換的性質，可得hf(z) = hf(e)

因此，false positive possibility為

$P = 1 - (1 - \frac{1}{B}*\frac{1}{2^r})^m$

根據伯努利公式，當x很小時，$(1+x)^a \approx 1 + ax$，所以

$P \approx 1 - (1 - m * \frac{1}{B} * \frac{1}{2^r}) \approx \frac{m}{B*2^r}$

那么d-left CBF的false positive和空間利用情況如何？我們下面簡單分析一下：

比較嘛，肯定是相同的空間利用，比較誰的false positive possibility小；相同的false positive possibility下，誰所需空間少。

在CBF中，假設counter需要c位（上次我們分析過，c取4足矣），那么所需的空間是cn。結合$k = \frac{n}{m}ln2$，false positive possibility大約為$(0.6185)^{\frac{n}{m}}$。

在d-left CBF中，我們選擇d=4，B=$\frac{m}{24}$，w=8（平均負載為6，這樣$4 * \frac{m}{24} * 6 = m$），counter占用2位，fingerprint占用r位。那么它的空間占用為

$4 * \frac{m}{24} * 8 * (2+r) = \frac{4m(r+2)}{3}$

而false positive possibility的大概為 $\frac{m}{B*2^r} = 24 * \frac{1}{2^r}$ (別忘了，B=$\frac{m}{24}$ )

通過計算不難發現，當空間占用相等時，d-left CBF的false positive possibility是CBF的百分之一；當false positive possibility相等時，d-left CBF所需空間是CBF的一半。

感謝

特別感謝 汪立 大神參與討論。