LSM trees: compaction and the amplification triangle

The field guide's wide-column lesson had you drive the LSM basics: writes land in a memtable, flush as immutable sorted SSTables, compaction merges them later. This lesson is about the part that runs production: the debt. Every LSM design is a position in a three-way trade the literature calls the RUM/amplification triangle: and understanding it turns "Cassandra is being weird" into "compaction chose this, and here's the dial."

The three amplifications

Write amplification (WA): bytes physically written ÷ bytes logically written. Every compaction re-reads and re-writes data that was already "written": a key may be rewritten 10–30× over its life as it migrates down levels. Read amplification (RA): places checked per read: memtable plus every SSTable that might hold the key. Space amplification (SA): disk used ÷ live data: old versions and tombstones squat until compaction reclaims them. The theorem you can't escape: improve any one and at least one other degrades. Prove it to yourself:

Real engines expose exactly this dial: Cassandra ships STCS (write-friendly default), LCS (read-optimized, ~10× the compaction I/O), and TWCS (time-windowed: for time-series data, where "compact only within a time window, then drop whole windows at expiry" makes retention free, as the field guide's specialists lesson promised). RocksDB: the LSM engine inside dozens of other databases: makes leveled-with-tiered-L0 the default and exposes dozens of tuning knobs that are all, ultimately, positions on this triangle. And when compaction falls behind the write rate, all three amplifications grow together: files pile up, reads slow, disk fills: the LSM failure mode, and the first graph to check on a struggling cluster.

Bloom filters: the read-amp painkiller

With a key possibly in any of 10 SSTables, point reads should cost 10 disk probes. They don't, because each SSTable carries a bloom filter: a bit array that answers "is key K possibly in this file?" with no false negatives and a tunable false-positive rate, in nanoseconds, from RAM. Build one:

The asymmetry is the whole design: "no" is guaranteed, "yes" is probabilistic. A false positive costs one wasted disk probe: annoying, correct. A false negative would return wrong query results: impossible by construction, since adding a key can only set bits, never clear them. Production filters use ~10 bits per key and ~7 hash functions for a ~1% false-positive rate, so a read across 10 SSTables does ~10 RAM checks + 1 real disk read + 0.1 wasted ones. This is why LSM point reads stay competitive with B-trees despite the multi-file layout. (The same "cheap probabilistic no" trick shows up all over systems: cache admission, distributed joins, malware scanning: worth having in your pocket.)

So: B-tree or LSM?

One more honest note: SSDs shrank the random-write penalty that motivated LSM, but didn't kill the trade: flash has its own write-wear economics (SSD controllers run their own internal LSM-ish log!), and the CPU cost of compaction vs page management keeps the rivalry alive. Modern practice: PostgreSQL/MySQL (B-tree) for the OLTP core; RocksDB-based engines (MyRocks, Cassandra, Scylla) where write volume or space efficiency wins. Same conclusion as the whole field guide: physics, workload, pick.

Check yourself