bloom

Ribbon filter

在 RocksDB 的 blog 上看到「Ribbon Filter」這個，主要是 RocksDB 從 6.15 開始支援 Ribbon filter，取代本來的 Bloom filter 機制。

RocksDB 的 wiki 上面是說用 CPU 資源換 memory 的使用量：

A new Bloom filter alternative is available as a drop-in replacement (since version 6.15.0), saving about 30% of Bloom filter space (most importantly, memory) but using about 3-4x as much CPU on filters. Most of the additional CPU time is in the background jobs constructing the filters, and this is usually a good trade because it is common for SST filters to use ~10% of system RAM and well under 1% of CPU.

論文則是在「Ribbon filter: practically smaller than Bloom and Xor」這邊可以看到，Facebook 之前也有提到 Ribbon filter：「Ribbon filter: Practically smaller than Bloom and Xor」，在 Hacker News 上有對應的討論可以翻：「Ribbon filter: Practically smaller than Bloom and Xor (fb.com)」。

在 Ribbon filter 的資料裡面都提到了 Xor filter 當作比較，先前在「比 Bloom filter 與 Cuckoo filter 再更進一步的 Xor filter」這邊有提到 Xor filter。

用 CPU 去換記憶體，算是特化的版本...

比 Bloom filter 與 Cuckoo filter 再更進一步的 Xor filter

Bloom filter 算是教科書上的經典演算法之一，在實際應用上有更好的選擇，像是先前提到的 Cuckoo filter：「Cuckoo Filter：比 Bloom Filter 多了 Delete」。

現在又有人提出新的資料結構，號稱又比 Bloom filter 與 Cuckoo filter 好：「Xor Filters: Faster and Smaller Than Bloom Filters」。

不過並不是完全超越，其中馬上可以看到的差異就是不支援 delete：

Deletions are generally unsafe with these filters even in principle because they track hash values and cannot deal with collisions without access to the object data: if you have two objects mapping to the same hash value, and you have a filter on hash values, it is going to be difficult to delete one without the other.

論文的預印本可以在 arXiv 上下載：「Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters」。

PostgreSQL 的 Bloom index

前幾天才跟人提到 PostgreSQL 的功能與完整性比 MySQL 多不少，剛剛又看到 Percona 的「Bloom Indexes in PostgreSQL」這篇，裡面提到了 PostgreSQL 可以使用 Bloom filter 當作 index。

查了一下資料是從 PostgreSQL 9.6 支援的 (參考「PostgreSQL: Documentation: 9.6: bloom」這邊的說明)，不過說明裡面沒看到 DELETE (以及 UPDATE) 會怎麼處理，因為原版的 Bloom filter 資料結構應該沒有能力處理刪除的情況...

另外這幾年比較有名的應該是 Cuckoo filter，不只支援刪除，而且空間與效能都比 Bloom filter 好，不知道為什麼是實做 Bloom filter...

HyperLogLog 與 Bloom Filter

看到 Facebook 在 Presto 裡增加使用 HyperLogLog 計算數量的能力，突然想到常常忘記這兩個拿準確度換速度的資料結構：「HyperLogLog in Presto: A significantly faster way to handle cardinality estimation」。

HyperLogLog (HLL) 是解決 Count-distinct problem 的資料結構，用很少的記憶體就可以給出一個誤差不大的值 (用 1.5KB 的空間處理十億等級的資料，誤差大約在 2%)，所以 Presto 利用這個資料結構引進了 APPROX_DISTINCT() 以及其他的函數，就很容易在 L2/L3 cache 裡運算，藉此大幅提昇速度。

Depending upon the problem at hand, we can achieve speed improvements of anywhere from 7x to 1,000x.

先前也提過 Reddit 也用 HLL 統計資料：「Reddit 在處理 Page View 的方式」。

Bloom Filter 也是在處理大量資料的問題，但這個資料結構的功能不太一樣，是給出「有沒有存在」，使用空間與誤差大約是 10 bits per key (1% false positive)，另外先前也有提到一些變形，可以提供其他功能。像是「Quotient filter」與「Cuckoo Filter：比 Bloom Filter 多了 Delete」。

Quotient filter

之前有提過「Cuckoo Filter：比 Bloom Filter 多了 Delete」，最近在「A general purpose counting filter: making every bit count」這邊看到 Quotient filter，也是類似 Bloom filter 的資料結構，但想要解決更多問題。

一般的 Bloom filter (BF) 會有這些問題：

The inability to delete items
Poor scaling out of RAM
The inability to resize dynamically
The inability to count the number of occurrences of each item, especially with skewed input distributions.

而文章裡提到的 Quotient filter (QF) 就是要解這些問題。另外還提到了 Rank-and-Select-based Quotient filter (RSQF) 以及 Counting Quotient filter (CQF)。雖然多了一些空間需求，但看起來解掉不少問題... (尤其是刪除的能力)

效能上也還不錯，尤其是讀取速度的部份... 不過不知道相對於 Cuckoo filter 差多少。

Cuckoo Filter：比 Bloom Filter 多了 Delete

在「Cuckoo Filter implementation in Go, better than Bloom Filters」這邊看到這個資料結構，有興趣的人也可以看「Cuckoo Filter：设计与实现」這篇介紹，下面是我抓重點整理。

Bloom Filter 支援的操作：

Add(element)
Query(element)

1970 年提出來的資料結構。優點是空間複雜度是 O(1)，Query(element) 會有可接受的 false positive，缺點是不支援 Delete(element)、以及數量變多時誤判率的增加。

Cuckoo Filter 多了一組操作：

Delete(element)

2014 年提出來的資料結構。空間複雜度一樣是 O(1)，但相同的空間用量下 false positive 變低，然後支援 Delete(element) 了。也因此論文直接寫「Cuckoo Filter: Practically Better Than Bloom」，表示可以直接替代。