Bloom Filter

Nini 經營一座大鳥園，裡面有 1000 個鳥籠。今天客人指名想看一種很稀有的鳥：「藍喙彩羽大鴅」。

最笨的方法，就是 Nini 一籠一籠跑去找。如果這隻鳥真的不在園裡，她還是得把整座鳥園幾乎翻完，才能回答：「沒有這隻鳥。」

所以 Nini 先做了一本很小的鳥類特徵索引簿，不記每隻鳥在哪一籠，只記一些快速判斷用的特徵。每當新鳥進園，Nini 就根據幾個特徵（鳥喙顏色、翅膀長度、尾羽形狀、叫聲頻率），在索引簿上做記號。客人問「藍喙彩羽大鴅」在不在時，Nini 不必先衝進鳥園，只要先翻這本小簿子：只要有任何一個特徵記號對不上，她就能立刻說「這隻鳥一定不在園裡」，完全不用跑去查鳥籠。如果所有特徵都對得上，她也只能說「有可能在」，這時才值得真的進鳥園找。

這就是 Bloom filter：它不能保證「一定存在」，但可以很快保證「一定不存在」，用很少的記憶體，省掉大量白跑的 disk I/O。

Bloom Filter 的結構

Bloom filter 的組成非常簡單：一個長度為 $m$ 的 bit array（所有 bit 初始為 0），加上 $k$ 個獨立的 hash function。

插入一個元素時，用 $k$ 個 hash function 分別算出 $k$ 個位置，把這 $k$ 個 bit 都設為 1。查詢一個元素時，同樣算出 $k$ 個位置，檢查這 $k$ 個 bit 是否全部為 1。如果全部是 1，回答「可能存在」；如果任何一個是 0，回答「絕對不存在」。

Bloom filter insert and query operations on a bit array with k=3 hash functions — Bloom filter 的插入與查詢：k=3 個 hash function 映射到 bit array

注意 bit array 裡面只有 0 和 1，沒有存任何原始資料。你沒辦法從 Bloom filter 裡面「取出」元素，也沒辦法列舉裡面有哪些元素。它只能回答一個問題：這個東西在不在？而且回答還不是百分之百準確。

False Positive 與 False Negative

Bloom filter 保證沒有 false negative。如果一個元素確實被插入過，查詢時它對應的 $k$ 個 bit 一定都是 1（因為插入時已經設為 1 了，而且 Bloom filter 不支援刪除，bit 一旦設為 1 就不會變回 0）。所以「存在的東西一定查得到」。

但 Bloom filter 允許 false positive。一個從未被插入的元素，查詢時對應的 $k$ 個 bit 可能「恰好」都被其他元素設成了 1。這時 Bloom filter 會錯誤地回答「可能存在」。你把它當成「在裡面」，結果去 disk 上一查，發現根本沒有。

這是 Bloom filter 的根本性質：它說「不在」就真的不在，它說「在」則未必。在儲存系統的應用場景中，false positive 只是浪費一次 disk read，不會造成正確性問題。但 false negative 如果發生（告訴你不在但其實在），就等於資料不見了，這才是災難。Bloom filter 的設計正好符合這個需求。

False Positive Rate 的數學

false positive rate (FPR) 取決於三個參數：bit array 大小 $m$ 、hash function 數量 $k$ 、已插入的元素數量 $n$ 。

插入 $n$ 個元素後，某個特定 bit 仍然是 0 的機率是：

$P(\text{bit} = 0) = \Big(1 - \tfrac{1}{m}\Big)^{kn} \approx e^{-kn/m}$

查詢一個不存在的元素時，它對應的 $k$ 個 bit 要全部是 1 才會產生 false positive，所以：

$\text{FPR} \approx \Big(1 - e^{-kn/m}\Big)^k$

(不用背公式！)

假設我們要存 $n = 1{,}000{,}000$ 個元素，希望 FPR 不超過 1%：

如果 $m = 9{,}585{,}059$ bits（約 1.14 MB）， $k = 7$ ，FPR $\approx$ 1%
每個元素只需要約 9.6 bits 的空間

一百萬個元素，只用 1.14 MB 就能達到 99% 的過濾準確率。相比之下，如果你用 hash set 存這些元素（假設每個 key 平均 20 bytes），至少需要 20 MB，Bloom filter 的空間效率是 hash set 的 17 倍以上。

請參考 Bloom Filter 計算機

怎麼選參數

你通常知道兩件事：預計要存多少元素（ $n$ ），以及可以接受多少的 false positive rate（目標 FPR）。要算出需要多大的 bit array（ $m$ ）和幾個 hash function（ $k$ ）。

最佳的 bit array 大小：

$m = -\frac{n \ln(\text{FPR})}{(\ln 2)^2}$

最佳的 hash function 數量：

$k = \frac{m}{n} \cdot \ln 2 \approx 0.693 \cdot \frac{m}{n}$

(不用背公式！)

舉個你每天都在用的例子。Google Chrome 用 LevelDB 作為瀏覽器內部的 local storage engine（IndexedDB、瀏覽紀錄、Safe Browsing 資料庫等等都靠它）。當你瀏覽網頁時，Chrome 需要頻繁查詢某個 URL 是否出現在本機的 Safe Browsing 黑名單裡，這個黑名單可能有數百萬筆惡意 URL。如果每次查詢都要從 disk 讀取比對，Chrome 會卡到不行。 LevelDB 的做法是在每個 SSTable 檔案上配一個 Bloom filter，設定 bits per key $= 10$ 。根據上面的公式， $k = 10 \times \ln 2 \approx 6.93$ ，取整為 7，對應的 FPR 大約是 0.82%。也就是每 100 次查詢不存在的 URL，平均只有不到 1 次會白跑一趟 disk read，其餘 99 次都在記憶體裡就擋掉了。

Bloom Filter 有 Diminishing Return 喔： $m/n$ 從 10 增加到 15（多 50% 的記憶體），FPR 從 0.82% 降到 0.03%，降了 27 倍。但繼續從 15 增加到 20（再多 33% 的記憶體），FPR 只從 0.03% 降到 0.001%，降幅變得很小。所以大部分系統選在 $m/n = 8 \sim 12$ 之間就夠了。

為什麼不能刪除？

標準 Bloom filter 不支援刪除，因為多個元素的 hash 位置可能重疊。如果你把某個元素對應的 bit 設回 0，可能會把另一個元素的 bit 一起清掉，導致本來存在的元素被誤判為不存在，也就是產生 false negative。

如果需要刪除功能，可以使用 counting Bloom filter：把每個 bit 換成一個計數器（通常 4 bits），插入時計數器加 1，刪除時減 1。這樣就能安全地刪除而不影響其他元素。代價是空間從每位置 1 bit 變成 4 bits，記憶體用量是標準版的 4 倍。

在 LSM-Tree 中的應用

Bloom filter 最經典的應用場景之一就是 LSM-Tree。LSM-Tree 的 read path 需要逐層搜尋多個 SSTable 檔案，查一個不存在的 key 可能要白跑好幾層 disk I/O。如果在每個 SSTable 配上 Bloom filter，查詢前先問一句「這個 key 在不在這個檔案裡？」，回答「不在」就直接跳過，省掉大量無謂的 disk read。下次上課我們會深入講 LSM-Tree 的結構，到時候會更清楚 Bloom filter 在裡面扮演多重要的角色。

延伸：Cuckoo Filter

標準 Bloom filter 有兩個比較麻煩的限制：不能刪除，而且查詢效能會隨著 bit array 填滿而下降（越來越多 bit 是 1，false positive rate 上升）。2014 年 CMU 的研究者提出了 cuckoo filter，用不同的思路解決了這些問題。

Cuckoo filter 不用 bit array，而是把元素的 fingerprint（一小段 hash 值）存進一張類似 hash table 的結構，用 cuckoo hashing 的方式處理碰撞：一個元素有兩個候選位置，插入時如果兩個都滿了，就把其中一個「踢走」到它的另一個候選位置，像杜鵑鳥把別人的蛋踢出巢一樣。因為存的是 fingerprint 而不是單純的 bit，刪除時可以精確移除特定元素的 fingerprint，不會影響其他元素。

在相同的 FPR 下，cuckoo filter 的空間效率和 Bloom filter 差不多，但額外支援了刪除操作，而且每次查詢只需要檢查 2 個位置（對 cache 非常友善），比 Bloom filter 的 $k$ 次 random access 更快。不過 cuckoo filter 有容量上限，塞太滿的時候插入可能失敗，這點和 Bloom filter 的「永遠能插入」不同。

這裡只是讓你知道有這個東西存在，不用背細節喔！

自問自答

試著用自己的話回答以下問題。如果卡住了，回去重讀對應的段落。

為什麼 Bloom filter 保證沒有 false negative，但無法避免 false positive？請從 bit array 的操作機制解釋。
一個系統要追蹤 5,000,000 個 URL 是否出現在黑名單中，可接受的 false positive rate 為 0.1%。請計算需要多大的 bit array（多少 MB）以及最佳的 hash function 數量 k。
為什麼標準 Bloom filter 不支援刪除操作？如果硬把某個元素對應的 bit 設回 0，可能產生什麼後果？Counting Bloom filter 如何解決這個問題，代價是什麼？
在什麼情境下 Bloom filter 的效益最大？在什麼情境下效益很小甚至不值得用？請從 workload 的 read/write 比例和 key 存在率的角度分析。