Bloom Filter for LSM Negative Lookups
TechniqueDatabase InternalsSeniorStaffUpdated
Attach a small probabilistic filter to each SSTable. A point lookup checks the filter first and skips the file if it says 'definitely not present'.
When to Use Bloom Filter for LSM Negative Lookups
Read paths in LSM engines where most lookups miss most files. RocksDB, Cassandra, HBase, and Parquet readers all use bloom filters to cut read amplification.
In Practice
RocksDB enables a per-SSTable bloom filter by default. With 10 bits per key the false-positive rate is ~1%, so for a 7-level LSM you typically read 1 SSTable instead of 7 on a point GET.
How Bloom Filter for LSM Negative Lookups Comes Up in Interviews
Scenario
A RocksDB workload does many point GETs for keys that don't exist. p99 read latency is terrible. Which tuning helps most?
Without bloom filters, a missing key forces a probe of every SSTable on every level. A 10-bits-per-key filter brings false positives to ~1%, so a 7-level LSM probes ~1 SSTable instead of 7.
Whole-key bloom filters help GETs; prefix bloom filters help bounded prefix iterators. They cost memory (~1.25 bytes/key for ~1% FPR) and add nothing to range scans.