Skip to content

Read amplification tradeoffs#

2024-09-25

LSMs trade write amplification for read amplification. How much read amp you actually pay depends on your workload and your filter setup.

Where read amp comes from#

For a point lookup in a leveled LSM with L levels:

  • You have to consult the L0 files (there might be several with overlapping ranges).
  • Then check each level L1 through L(L-1) — one file per level, thanks to the non-overlapping invariant.
  • Each file check is: bloom filter → index block → data block.

Without bloom filters, you'd read at least one data block per level. With filters at 1% FPR, ~99% of the "does key exist in this level" checks are answered from RAM.

Range scans are different#

Bloom filters don't help for range scans — you have to actually merge iterators from every level. This is where LSMs get their reputation for slow scans. Common mitigations:

  • Partition-level filters (Cassandra's approach) — helps if your scans are confined to a partition.
  • Prefix bloom filters in RocksDB — filter on a prefix of the key, useful if your queries have a natural prefix.
  • Level compaction with big files — fewer files per level means fewer iterators to merge. RocksDB's target_file_size_base=256MB is the common tuning.

Point-lookup RA in practice#

For a well-tuned RocksDB with 10 bits/key filters, 7 levels, and a warm block cache:

Cache hit rate 95%:   ~0.35 disk reads per lookup (mostly filter/index)
Cache hit rate 90%:   ~0.5 disk reads per lookup
Cache hit rate 50%:   ~2-3 disk reads per lookup

The block cache matters way more than the filter tuning past 10 bits.

When to think about read amp#

  • If your workload is scan-heavy: use B-Tree (SQLite, InnoDB), not an LSM.
  • If your workload is point-lookup-heavy with hot working set: LSM is fine, block cache does the work.
  • If your workload is point-lookup-heavy with cold working set: every read goes to disk anyway, LSM is fine too (bloom filter avoids extra reads).