Topic 5.1
LSM Trees and SSTable Filters
In one line
An LSM tree writes to a MemTable, flushes sorted immutable SSTables to disk, and compacts them over time. A point read may have to look in many SSTables; a Bloom filter per SSTable (kept in memory) says "definitely not here" for most of them, so a lookup costs about one disk read instead of dozens.
Think of it like this
Finding a receipt in 100 labelled shoeboxes. Each box has a small index card on the outside listing roughly what might be inside. You only open the boxes whose card says "maybe", instead of emptying all 100.
Key ideas
- 01
Write path: writes go to a WAL and an in-memory MemTable; when full, it's flushed as a sorted SSTable file; compaction merges files into larger levels. Files are immutable, so their filters are built once at write time.
- 02
Read path for key K: check the MemTable, then SSTables from newest to oldest (or level by level). Without filters, each file may need an index lookup and a disk read. With a filter per file, files whose filter says "absent" are skipped with no I/O.
- 03
Cost model: with F candidate files and false-positive rate p, a lookup for a missing key costs about F × p disk reads instead of F; for an existing key, 1 + (F − 1) × p. At F = 100 and p = 1%, that's ~1 wasted read instead of 99.
- 04
Filters live in memory (block cache or pinned), so their size matters: 10 bits per key is a common default (≈1%). Memory for filters scales with the total number of keys across files.
- 05
Range scans don't benefit (a filter answers only point membership); prefix Bloom filters (RocksDB prefix extractors) help for prefix seeks.
Code & diagrams
100 SSTables could contain the key, point lookup for a MISSING key:
no filters: up to 100 index/block reads
filters at 1%: ~100 x 0.01 = 1 wasted read on average
filters at 0.1%: ~0.1 wasted reads (costs ~50% more filter memory)
Existing key (present in exactly one file):
~1 real read + 99 x p wasted reads -> ~2 reads at 1%Interview problem
The problem
100 SSTables per lookup
A key-value store has 100 SSTables that a point lookup may have to check. How do Bloom filters reduce disk I/O, what's the memory cost for 2 billion keys, and what happens with range scans?
Explain it without notes
Why are Bloom filters such a natural fit for SSTables?
Practice
Compute expected disk reads per missing-key lookup for 40 SSTables at 10 bits/key and at 5 bits/key.
Trade-offs
- ↔
More bits per key mean less wasted I/O and more RAM; engines tune this per level.
Done when you can
I can explain the LSM read path with filters and calculate wasted reads and filter memory.