資料結構小教室 - Bloom Filter

Bloom Filter 的目的是為了以更高效且更節省空間的方式來找出一個東西是否存在。可以應用的地方非常廣泛，譬如確認用戶名是否已被使用、密碼是否不夠強、porn detection 等等。

設計一下查找資料的應用程式

先設想一下，身為一個工程師，如果要設計一個可以查找某樣東西的應用程式，要如何設計？最直觀我們會想到：如果是 in-memory 裡的查找我們可能會用 set, hashmap, search tree 之類的資料結構去儲存資料，可以達到 O(1), O(logn) 的搜尋效果。

如果資料量大的話，比如我們要查找的是用戶名是否已經存在，這些用戶名稱資料量大而沒有辦法存到 memory 裡。我們通常就會放在 db，然後做個 index 以便查找。

建 index 後查找資料不會太慢，但這些資料畢竟是存在 disk。如果今天流量很大，勢必還是會造成一些負擔。而 Bloom Filter 的設計就是來優化查找的效能。

Bloom Filter 設計

這個設計原理其實蠻簡單的，一個簡單的例子如下圖所示：我們先做出一個固定 size 的 bit array ，然後設定數個 hash function。假設 bit array 的 size 是 9 好了，我們讓這些 hash function 回傳出來的值會介於 0 - 8 之間，然後把輸入的資料送到這些 hash function 裡得出一系列 0-8 之間的數字，依據這些數字當作 bit array 的 index 填充為 1。

以用戶名存不存在的例子來說，我們會把所有用戶名稱資料都輸入進去。經由一系列的 hash function 轉換來填充這個 bit array。如果今天要驗證一個用戶名稱是否已經存在，我們可以把這個名稱帶進去 Bloom Filter 看看結果如何。如果每個 hash function 輸出的 index 帶到 bit array 裡得到的值都為 1，代表這個用戶名“可能”存在。如果任一為 0，則代表一定不存在。

它的設計理念其實就是：我們能夠快速地挑選出不存在的值。

再以用戶名稱搜尋的例子來說，Bloom Filter 的目的是為了做第一層篩選，如果發現不存在 (任一為 0)，那就不需要再進到 db 去查找了。如果遇到都是 1 的 case，因爲可能存在可能不存在，這時再去 db 作最終確認就好。如果 bit array 的 size 跟 hash function 都選得好，那麽在 Bloom Filter 的階段就可以過濾掉大部分需要進 db 的查詢，可以大幅提升效能。

In-memory DB 是一個很好實現 Bloom Filter 的地方，Redis 甚至都已經幫忙時做好，可以參考：

Bloom Filter 帶到了一些統計學的觀念，這種“可能存在”的例子被稱作 False Positive（偽陽性）。最近疫情常聽到快篩裡提到的偽陽性，還挺有感觸 😂。