Random writes are slow because they scatter the disk head. The log-structured merge-tree makes every write sequential: buffer it in a memtable, flush it as an immutable sorted run, and merge later. Reads walk the memtable then the runs newest-first; a delete is a tombstone; compaction reclaims the space. Down the center, data flows: writes go in, the engine resolves a key, the answer comes out. The blue team builds and defends it; the red team tries to break it.
source O'Neil, Cheng, Gawlick & O'Neil, The Log-Structured Merge-Tree (LSM-tree), Acta Informatica 33 (1996), 351–385 — doi.org/10.1007/s002360050048. Rendered, not quoted.
Three parts, one invariant: a read returns the newest write.
MEMTABLE — an in-memory sorted map of the most recent writes. RUNS — immutable sorted files (SSTables), each a frozen former memtable, ordered newest→oldest. TOMBSTONE — a delete writes a marker, not an erase. A read checks the memtable, then the runs newest-first, and stops at the first hit.
Live read path for the panel's current state — which layer answers each key:
| key | resolved at | value |
|---|
One idea: buffer, flush sorted, merge later. Trade many small random writes for a few big sequential ones, and pay it back with background compaction. That is the write-optimized structure under Cassandra, RocksDB, and LevelDB.
It is the opposite bet from the-b-plus-tree: that structure pays on writes to keep every read a single lookup; the LSM pays on reads (and space) to keep every write an append. Each sphere is the other's premise.
The blue team's live check: replay the canonical write/delete log, then read every key back and confirm each equals the reference map. If red reverses precedence, this badge is where it shows.
Every mutation is an append, never an in-place edit of a run:
| op | what it does |
|---|---|
| put k,v | write (k,v) into the memtable — newest wins on read |
| del k | write a tombstone for k into the memtable |
| flush | freeze the memtable as a new immutable newest run |
| compact | merge runs, keep latest per key, drop tombstones |
Runs are write-once. A newer value for a key does not overwrite the old one — it sits in a newer run and shadows it. That is what you feed the engine below.
Every result is computed live from the read path — memtable first, then runs newest-first — never looked up.
The reference map is a plain dictionary updated by the same ops. The engine's reads must match it exactly — that is the LIT claim.
What the machine proves, exactly: after any mix of puts and deletes over a fixed log, an LSM read equals a reference key→value map for every key — newest wins, tombstones mask, compaction preserves the latest live value and drops the dead. Integer and set truths, checked by full comparison.
The blue team's witness (left) confirms it live; the red team (right) tries to make a read go stale.
Real systems paper over the read cost with Bloom filters and fence pointers per run, and bound the space with tiered/leveled compaction policies — none of which is in the base structure. A B+tree keeps reads at one lookup; the LSM is the write-heavy specialist, not a universal win.
"LSM-trees make reads free." Cut. A read can touch the memtable and every run; unhelped, a point lookup is O(runs). The gain is write throughput, not read latency.
"A delete removes the data at once." Cut. A delete writes a tombstone; the old value physically survives in older runs until a compaction that spans them reaches it.
"Compaction is a background nicety." Kept, corrected. Compaction is load-bearing — it bounds run count, reclaims tombstones and stale versions, and is where the read/space debt is paid down.
The red team's move: on a read, take the value from the OLDEST run first instead of the newest — reverse the precedence. An updated key then returns a stale value. The blue team's witness (window 7) is watching.
Reverse the precedence — read the OLDEST run first instead of the newest — and an updated key returns a stale value. The witness recomputes against the reference map, disagrees, and turns red. Nothing is faked; the attack is real and it is caught.