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 去換記憶體,算是特化的版本...

Leave a Reply

Your email address will not be published. Required fields are marked *