Q: Name the three amplifications and say who pays for each.

Hit these points: write amp = disk bytes ÷ app bytes — pays in flash wear and write throughput → read amp = SSTables (disk reads) touched per logical read — pays in read latency and p99 → space amp = disk bytes ÷ live data bytes — pays the storage bill → the iron law (RUM conjecture): lowering one amplification raises another, so there is no free strategy → every compaction policy is just a chosen point in this trade-off space.

Q: Should one compaction strategy apply to the whole database? Make the principal-level call.

Hit these points: no — a single global setting forces one corner of the read/write/space triangle on every table regardless of its access pattern → the senior move is to choose per table / column family, the same way you choose indexes per query → a write-once-read-rarely audit log wants tiered or time-windowed; a hot read-mostly profile table wants leveled; a TTL'd time-series wants TWCS → trade-off to name: per-table tuning adds operational surface and reasoning cost, so default sensibly and only override where the workload data justifies it → the discipline is matching each table's dominant amplification to a measured access pattern, not picking one strategy by reputation.

Question 1

Walk the LSM write path from a client write to a key on disk: memtable, WAL, SSTable.

Accepted Answer

Hit these points: a write appends to the WAL for durability and inserts into the in-RAM memtable (a sorted map — skip list / RB-tree) → no in-place disk write happens, which is why writes are fast → when the memtable fills it is frozen and flushed as a new immutable SSTable: an on-disk file sorted by key → SSTables are never modified, only merged away by compaction → updates and deletes are also just writes &mdash; a newer value or a tombstone is appended and shadows the old one → the WAL exists so a crash before flush doesn't lose the memtable's contents.

Question 2

What is an SSTable, and why does its sortedness make merging cheap?

Accepted Answer

Hit these points: an SSTable is an immutable on-disk file of key,value entries sorted by key, with a sparse index so a key can be found with one seek into a block → immutability means readers and compaction never contend over in-place edits &mdash; you only ever create new files and delete old ones → because every SSTable is already sorted, merging N of them is a linear k-way merge in one pass, like merge-sort's merge step: no random I/O, no re-sorting → during the merge you keep the newest value per key and drop shadowed/tombstoned ones → that "two sorted files merge in one sequential pass" is the property the whole engine is built on.

Question 3

Name the three amplifications and say who pays for each.

Accepted Answer

Hit these points: write amp = disk bytes ÷ app bytes &mdash; pays in flash wear and write throughput → read amp = SSTables (disk reads) touched per logical read &mdash; pays in read latency and p99 → space amp = disk bytes ÷ live data bytes &mdash; pays the storage bill → the iron law (RUM conjecture): lowering one amplification raises another, so there is no free strategy → every compaction policy is just a chosen point in this trade-off space.

Question 4

What does a Bloom filter do in an LSM read path, and what guarantee does it give?

Accepted Answer

Hit these points: each SSTable carries a Bloom filter over its keys; before opening the file a read probes the filter → the guarantee is one-sided: "definitely absent" is never wrong, "probably present" can be a false positive → so a "definitely absent" answer lets the read safely skip that SSTable &mdash; turning an absent-key read that would touch every run into one (rare) false-positive open → cost is small: ~10 bits/key for a ~1% false-positive rate (illustrative) → it attacks read amp specifically for negative/point lookups; it does nothing for range scans, which must still consult overlapping runs.

Question 5

Compare size-tiered and leveled compaction. When do you pick each?

Accepted Answer

Hit these points: STCS groups SSTables by size and merges a batch of same-size tables into one of the next size up; tiers grow geometrically so a key is rewritten only ~log N times → that buys low write amp but costs space (a big merge needs ~2× the dataset, and stale copies linger across un-merged tiers) and med&ndash;high read amp → LCS keeps levels L1+ non-overlapping, each ~10× the last, merging one table down into the few it overlaps → that buys low read amp (≤1 file per level + L0) and low space amp (~1.1×) but pays write amp ~T·log_T(N) ≈ 10&ndash;30× → pick STCS for write-heavy ingest with disk to spare; LCS for read-heavy, space-constrained data.

Question 6

Why can leveled compaction guarantee a point read touches at most one SSTable per level?

Accepted Answer

Hit these points: the LCS invariant: in every level except L0, SSTables have non-overlapping key ranges → so each level below L0 is effectively one sorted run with disjoint ranges, and any given key can fall in exactly one table there → L0 is the exception because it takes raw memtable flushes that do overlap, so a read still scans all of L0 → total files consulted ≈ all of L0 + one per level ≈ log_T(N) → that bounded read amp is exactly what you pay the 10&ndash;30× write amp to get.

Question 7

Walk me through the tombstone resurrection bug and how engines prevent it.

Accepted Answer

Hit these points: a delete can't erase data in immutable SSTables, so it writes a tombstone: "this key is dead as of this sequence number" → the value still lives in an older SSTable; the tombstone shadows it on read → the bug: if the tombstone is purged before the older SSTable holding the value is compacted away, the value reappears with nothing to mask it &mdash; a deleted record comes back to life → prevention: only drop a tombstone once compaction has carried it past every older copy of that key (the bottom level / past all older tiers) → distributed twist: Cassandra holds tombstones for gc_grace_seconds (default 10d) so the delete propagates to every replica before GC, or a node that missed the delete re-replicates the stale value.

Question 8

What triggers compaction, and why does an LSM under heavy ingest start stalling writes?

Accepted Answer

Hit these points: compaction is triggered by structural thresholds, not a timer: STCS fires when enough same-size SSTables accumulate in a tier; LCS fires when a level exceeds its size target; engines also track L0 file count and pending-compaction bytes → under sustained ingest, writes can outrun compaction's drain rate, so L0 / pending-compaction-bytes crosses a slowdown then stop trigger and the engine applies back-pressure &mdash; that's the stall → what you do not do is "write faster" → the fixes give compaction more throughput (more threads, faster disk), switch to a cheaper-write strategy, or smooth/shard the ingest → the underlying truth: sustainable write rate is bounded by compaction throughput.

Question 9

Should one compaction strategy apply to the whole database? Make the principal-level call.

Accepted Answer

Hit these points: no &mdash; a single global setting forces one corner of the read/write/space triangle on every table regardless of its access pattern → the senior move is to choose per table / column family, the same way you choose indexes per query → a write-once-read-rarely audit log wants tiered or time-windowed; a hot read-mostly profile table wants leveled; a TTL'd time-series wants TWCS → trade-off to name: per-table tuning adds operational surface and reasoning cost, so default sensibly and only override where the workload data justifies it → the discipline is matching each table's dominant amplification to a measured access pattern, not picking one strategy by reputation.

Question 10

"Leveled is the modern default, just use it everywhere." Steelman it, then take it apart.

Accepted Answer

Steelman: leveled gives bounded read amp (≤1 file/level) and low space amp (~1.1×), so reads are predictable and you don't risk running out of disk during a merge &mdash; for read-mostly, space-constrained, SSD-backed data that's genuinely the right corner. Take it apart: leveled pays 10&ndash;30× write amplification, so on a write-heavy or ingest-firehose table it burns write bandwidth and flash endurance and is the first to hit write stalls → "default everywhere" forces that write tax onto tables that are mostly appended and rarely read → for append-only TTL'd time-series, TWCS beats it on all three by dropping whole old buckets at once. Synthesis: there is no globally-best strategy &mdash; leveled is one well-chosen point; match the corner to each table's workload and disk profile, and watch write-amp/stall metrics to know when you chose wrong.

Question 11

Where do TWCS and RocksDB's universal compaction sit relative to STCS and LCS, and why do hybrids exist?

Accepted Answer

Hit these points: STCS and LCS are the write-optimized and read/space-optimized corners; real workloads often sit between them, which is why hybrids exist → RocksDB universal compaction is tiered-leaning &mdash; write-friendly, fewer rewrites than leveled, accepting more space/read amp → Cassandra TWCS buckets SSTables by time window for append-only, TTL'd time-series, so whole old buckets expire and drop at once &mdash; achieving low write + low space + low read within a window by exploiting the access pattern rather than beating RUM → the staff signal is naming the workload that justifies the hybrid (time-series with TTLs, immutable events) instead of treating compaction as one global knob → the lesson: you escape the triangle only by changing the workload's shape, not by tuning harder.

Question 12

Design the compaction strategy for a write-heavy ingest table vs a read-heavy lookup table in the same cluster.

Accepted Answer

A strong answer covers: reject one global setting &mdash; choose per table / column family by access pattern → write-heavy ingest (firehose, mostly appended, rarely point-read): size-tiered, because ~log N rewrites keep write amp low and protect the sustainable write rate; accept the ~2× space spikes and med&ndash;high read amp, and provision disk headroom so a big merge can't exhaust the volume → if events carry TTLs, prefer TWCS so whole old buckets drop at once &mdash; lowest write + space + read within a window → read-heavy lookup (point reads, latency-sensitive, space-constrained): leveled, paying 10&ndash;30× write amp to buy ≤1 file/level read amp and ~1.1× space; lean on Bloom filters and block cache for negative/point lookups → name the trade-offs: STCS risks running out of disk during merges and slower reads; LCS risks write stalls if the "read-heavy" table actually takes heavy writes → monitor L0/pending-compaction and p99 read per table, and re-tune when a table's real workload diverges from the assumption &mdash; sustainable write rate is bounded by compaction throughput, so size compaction I/O to the ingest table's rate.

Question 13

Design deletes + compaction for a Cassandra time-series store that must honor data-retention (TTL) and GDPR-style erasure.

Accepted Answer

A strong answer covers: the workload is append-only, time-ordered, with TTL expiry and occasional hard deletes &mdash; that points at TWCS, bucketing SSTables by time window so whole expired windows drop in one operation instead of rewriting live data → model the partition/clustering key on time so a window maps cleanly to a bucket and old data ages out as a unit → deletes/expiry produce tombstones; the resurrection rule still binds &mdash; a tombstone must outlive every older copy, so set gc_grace_seconds long enough for the delete to reach every replica (default 10d) before GC, balanced against not letting tombstones pile up → avoid tombstone-heavy access (no queue/range-scan-over-deleted patterns) since reads scan tombstones and hit tombstone_failure_threshold → for GDPR erasure, ensure the delete propagates and is actually purged after the older SSTables compact away &mdash; TTL alone shadows but doesn't immediately reclaim, so verify space returns after compaction → name the trade-offs: TWCS gives near-free retention drops but is wrong if the table takes out-of-window updates or random deletes; tuning gc_grace_seconds trades resurrection safety against tombstone read cost and erasure latency.

Dimension	Size-tiered (STCS)	Leveled (LCS)
Groups by	Size of SSTable	Level (each ~10× the last)
Overlap	Tables can overlap	Non-overlapping below L0
Write amp	Low (~log N)	High (10–30×)
Read amp	Med–high	Low (≤1 file/level)
Space amp	High (~2× spikes)	Low (~1.1×)

Strategy	Write	Read	Space	Reach for it when
Size-tiered	low	med–high	high	write-heavy, disk to spare
Leveled	high	low	low	read-heavy, space-constrained
Time-window (TWCS)	low	low*	low	time-series with TTLs

If the table is…	Reach for
Write-heavy ingest, disk to spare	Size-tiered (STCS)
Read-heavy, space-constrained	Leveled (LCS)
Append-only time-series with TTLs	Time-window (TWCS)
Mixed / tiered-leaning, one engine	Universal (RocksDB)

LSM Compaction — the trade-off you cannot escape

The job & the three amplifications

Size-tiered (STCS) — the write-optimized corner

Leveled (LCS) — the read-and-space-optimized corner

The trade-off triangle — pick two of three

Tombstones & the resurrection bug

L0, write stalls & back-pressure

Interview — pick your bar

Retrieval practice — mix the levels

Reconstruct the deep dive from a blank page

★ Cheat sheet — compaction in one screen

Strategy → workload

Numbers to remember

Three rules for the senior chair