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 / KeyConstruction CPUQuery LatencyTotal Filter RAM
Standard Blocked Bloom10.01.00x (baseline)19 ns15.0 GiB
Ribbon Filter (128-bit band)7.11.38x24 ns10.65 GiB
Hybrid (Bloom L0–L1, Ribbon L2–L6)7.3 avg1.19x21 ns10.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.

← Older Note (2025-04-02)Tracing Ephemeral Port Exhaustion and TIME_WAIT Reuse Anomalies Behind L4 Load BalancersNewer Note (2025-06-28) →Anatomy of a Go Runtime Scheduler Latency Spike: Netpoller, Syscall P Hand-offs, and GOMAXPROCS

← Back to all notes · View full chronological archive (24)