Bloom Filter False Positives vs. Ribbon Filters in Memory-Constrained SSTable Caches
Saving 31% of filter RAM in a 12-billion-key LSM store by adopting cache-local Ribbon filters for L2–L6 SSTables while keeping FastLocalBloom in L0/L1.
1. The RAM Cost of 10 Bits Per Key at 12 Billion Keys
At 10 bits per key (approx. 0.9% false positive rate for a standard cache-local Bloom filter), pinning filter blocks in memory for 12 billion keys requires 15 GiB of un-evictable RAM per storage node. Ribbon filters ( Rapid Incremental Boolean Banding ON the fly) construct a compact banded linear system over GF(2) that achieves the same 1% FPR in roughly 7.0–7.2 bits per key.
| Filter Type (1% Target FPR) | Bits / Key | Construction CPU | Query Latency | Total Filter RAM |
|---|---|---|---|---|
| Standard Blocked Bloom | 10.0 | 1.00x (baseline) | 19 ns | 15.0 GiB |
| Ribbon Filter (128-bit band) | 7.1 | 1.38x | 24 ns | 10.65 GiB |
| Hybrid (Bloom L0–L1, Ribbon L2–L6) | 7.3 avg | 1.19x | 21 ns | 10.95 GiB |
Using hybrid placement—fast-building Bloom filters for short-lived L0/L1 SSTables and compact Ribbon filters for bottom levels holding 90% of keys—saved 4.05 GiB of RAM per node with negligible compaction CPU impact.