一次搞懂 Approximate Membership Query

什麼是 Approximate Membership Query ?

在 Approximate Membership Query (AMQ) 資料結構中，會有下面兩種操作

• Insert (item)
• Query (item)

這邊先舉一個簡單的小例子，如果給你全台灣目前有開通的手機號碼集合，之後會去問你 0912–345-678 是否是一個有開通的電話號碼。

在上面的這個例子中，問特定號碼是否有開通的問題就是一個 Membership Query，也就是查詢特定 item 是否存在於該 Set。

那麼 Approximate 又是什麼意思呢?

Approximate: close to the actual, but not completely accurate or exact.

根據 Google Translate 的解釋，我們現在知道 Approximate 就是結果不一定是完全正確的

那麼接下來就會介紹幾種常見的 Approximate Membership Query 資料結構

• Hash Set
• Hash Set without original data
• Bloom filter
• Cuckoo filter
• Quotient filter
• Xor filters

Hash Set

Hash Set 應該是大多數人第一個會想到要使用的資料結構，透過 hash function，只需要透過一次的 random access 就能快速的判斷 new item 是否是成員。

他的時間複雜度是 O(1)，空間複雜度是 O(m x b) (note: m 為成員的數量, b 單 item 的大小)

看起來使用 Hash Set 是正確的選擇，但其實空間還是使用的有點多，因為我們其實不需要儲存原始資料

那如果我們不儲存原始資料會發生什麼事情呢

Hash Set without original data

不儲存原始資料的話，那原來用來存資料的 bucket 只需要有一個 bit 的大小，用來標記 該 bucket 有沒有被 insert 過

當 insert (A) 時，我們就可以 hash (A) 並找到對應的 bucket，在 bucket 寫成 1。那麼在之後 query (A) 的時候，我們只要檢查 hash 到的 bucket 是否為 1就可以了

B = buckets, H = Hash function
insert (A) =>  B[H(A)] = 1
Query (A)  => return B[H(A)] == 1

但是因為沒有儲存原始資料，導致我們無法處理 hash collision ，一旦發生 Hash Collision，就會出現 false positive 的狀況

這邊就要去計算 false positive rate，這邊的算法是

• 假設 Hash(new item)= j
• 比他早來的前 m 個 item 都沒有被 hash 到 j 的機率

不知道怎麼在 medium 寫數學式，就直接貼圖

因為我們沒有儲存原始資料，如果有一天隨著 insert 的數量增加 buckets 不夠用，我們沒有辦法透過 rehash 的辦法來做到 resize hash set

但運用 false positive rate 我們可以算出我們需要一次建置多大的空間

• 假設預計最多會 insert 1000 個 items (m=1000)
• false positive rate 要小於 1%

那麼我們會需要至少建置 99500 個 buckets 才能夠符合條件，這樣的空間使用量似有還是有點多，且我們只使用 約 1% (1000/99500) 的空間。

是否有其他方式可以在不增加 false positive rate 的情況下，減少空間使用量呢?

Bloom Filter

沒什麼事是用 hash function 不能解決的，如果有，用兩個

我們在前一個方法觀察到兩個重點

• 還有超多空間都未被使用到
• hash collision 很容易發生

就像猜拳一樣，猜一次就算輸太殘忍了，改成連猜三次都輸才算輸好了

根據這個精神，我們使用 3 個 hash function ，只有在三個 hash function 都跟之前的 item 發生 hash collision 才會出現 false positive。

B = buckets, H = Hash function
insert (A) =>  B[H1(A)] = 1; B[H2(A)] = 1; B[H3(A)] = 1
Query (A)  => return B[H1(A)] && B[H2(A)] && B[H3(A)]

圖片來源: wikipedia

那麼我們也可以計算一下使用新的方式，它的 false positive rate 是多少

透過自然指數做一些簡化

透過 false positive rate 可以算出來，要達成

• 假設預計最多會 insert 1000 個 items (m=1000)
• false positive rate 要小於 1%

那麼我們只需要使用 7 個 hash function 及建置 9586 個 buckets，即可滿足以上條件，這樣的空間使用量比 `Hash Set without original data` 足足少了 10 倍

但是仔細計算還是只使用了 10% (1000/9586) 的空間，那們還沒有有壓縮的空間呢?

Fingerprint-based AMQ

Bloom filter 這類的 AMQ ，因為無法處理 hash collision ，對於 hash collision 只能用避免的，也就是提供足夠的 mapping 空間，減低發生 hash collision 的機率。

接下來會介紹兩個 Fingerprint-based 的 AMQ，分別是 Cuckoo filter 和 Quotient filters

這類的 AMQ 會處理 hash collision 的狀況，進而不需要預留那麼多空的 buckets 空間，遇到 hash collision 處理就可以了。

但是如果為了要處理 hash collision 去儲存原始資料，又會需要使用大量的空間，故他們會使用 fingerprint 來代表原始的資料，fingerprint 大多就是原始資料經過 hash 之後過的值，有點像是檔案的 checksum 的概念。

fingerprint of A = h(A)

有了 fingerprint 使得這類的 AMQ 使用的空間在某些情況下會比較少，並且可以支援 delete 操作，以及可以透過 rehash 來 resize AMQ

這類的 AMQ 的 false positive 大多不是因為選擇 bucket 時發生 hash collision 所造成的，大多是在產生 fingerprint 的時候發生 collision 造成的。因為儲存 fingerprint 會造成額外的空間負擔，為了要省空間，會將長度縮短，但也就造成了 fingerprint 容易發生 collision

Cuckoo filter

Cuckoo filter 就是使用 Cuckoo hashing 的 hash set。Cuckoo hashing 是一種 collision 的解決方式。每個 item 都會對應到兩個 buckets，在 insert 的時候如果有其中一個 bucket 是空的就放那邊，如果兩個都是滿的，就隨機踢走一個 bucket 中的 item，並將自己放在該 bucket。被踢走的 item 去他另一個可以放的 bucket，一樣空的就放，滿的就踢。

這樣一直持續到大家都有 bucket 放，或是踢走的次數大於一定數字。如果超過次數就會視為 table 太滿，需要擴展，使用 rehash 增大空間。

比較特別是 cuckoo filter 選擇的兩個 hash function 是

h1(x) = hash(x)
h2(x) = h1(x) xor hash(x's fingerprint)

這樣做有個好處，是在被踢走的時候，找尋另外一個 bucket 就很簡單，不用知道自己是哪個 hash function 算出來的，只要用下面的算法，就可以得到

j = i xor hash(x's fingerprint)

圖片來源: Cuckoo Filter: Practically Better Than Bloom

圖片來源: Cuckoo Filter: Practically Better Than Bloom

Quotient filter

Quotient filters 有點小複雜這邊就不細講了，不過可以把它當成使用 linear probing 解決 hash collision 的一種 hash set

linear probing 類的可以使得他的 data locality 非常好，大多也只需要一次 random access 就可以知道答案。相對於 bloom filter 這種需要好幾次的 random access 的 AMQ，Quotient filters 就非常適合 scale 到 RAM 之外的場景，例如 SSD。

Xor filters

那如果應用情境改變，只需要一次把 set 建好，之後就不會 insert 新的 item ，只會有 query 的話，還有一些選擇可以使用，其中一個就是使用 perfect hashing 來建置 hash set，另外一個就是使用 Xor filter。

也是有點小複雜這邊也就不細講了。他就是一種一但 construct 之後就不能再 insert 新 item 的 AMQ。construct 時也跟 perfect hashing 一樣要重複建個幾次，直到成功，但機率上來說很大的機率會成功。

AMQ 應用範例

以下會介紹幾個常見的應用

The Log-Structured Merge-Tree (LSM-Tree)

其實這次會看 AMQ 就是因為之前聽演講有聽到他們使用 bloom filter 來優化 LSM Tree。LSM Tree 基本上就是在寫入的時候紀錄寫入了什麼東西，有點像 log 的感覺，寫到一定的量就成為一個 block 並寫到 disk 中。這些 block 一但被寫到 disk 就不會再更動了(除非遇到 merge)。

這樣的方式相對於 B-tree 可以使得寫入速度大增，但對於讀取就會有比較大的問題。如果要用 key 讀出一個 value 來，那麼這個 value 可能存在每一個 block 當中，如果每個 block 都要去拿起來看一下，就會需要很多次的 dick I/O，所以通常 LSM-Tree 都會使用 bloom filter 來去初步判定該 block 有沒有該 key 的 value，因為 bloom filter 占用的空間夠小可以存在 RAM 內，進而就可以大幅減少實際存取 disk 的次數。

TinyLFU

這是一個用於 Cache 的資料結構，在 Cache 中常常需要根據 LFU 的規則來當作 admission rule 或是 evict rule，這類的 AMQ 其實加上個 counter 就可以拿來計算出現的次數，例如 TinyLFU 用到 count-min sketch (counting bloom-filter)。

看完覺得 Hash 真的是個好東西啊，這些 filter 都是 based on hash table 然後再做一些改變，感覺蠻有趣的。它的應用場景也非常的多，也有適合不同場景的各種變形，在許多領域都會用到 AMQ 來做一些優化。