Commentary: lsm-tree

A store where a delete is a write, and where compaction — the 3am housekeeping chore — hands a deleted key back with its original value. A study guide for lsm.py.

cd lsm-tree
python3 demo.py       # the aha (§6)
python3 test_lsm.py   # pins every number this page claims
cat data/store/*.sst  # the whole database, after a demo run

1. Orientation

This toy implements the write path of a log-structured merge tree — the storage engine underneath Cassandra, RocksDB, LevelDB, ScyllaDB, HBase, and (as of 2018) MySQL at Facebook. The whole design follows from one refusal: never modify data that has already been written. A write goes into an in-memory MemTable; when that fills, it is flushed whole into an immutable sorted file called an SSTable; files are later merged into new files by compaction and the originals deleted.

That refusal has a consequence that is easy to state and surprisingly hard to believe until you watch it: a delete is a write. It appends a tombstone, a record saying "as of here, this key is gone."

And that leads to the aha, which is that compaction — the routine space-reclaiming chore, the thing you'd schedule at 3am and never think about — can resurrect a deleted key. Not corrupt it. Not lose it. Hand back its old value as if the delete never happened.

By the end you should be able to:

• explain why an append-only store cannot delete anything, and what it does instead;
• work out, from a list of segments, exactly what get(key) will return — and how many files it has to open to say so;
• state the precise condition under which dropping a tombstone during compaction is safe, and name what breaks when you get it wrong;
• read Cassandra's gc_grace_seconds documentation and know what it is actually protecting you from.

The last one is the real payoff. "Run repair within gc_grace_seconds or you get zombie rows" is a sentence in operational runbooks that most people follow without understanding. After this toy, you'll have made the zombie yourself, in six lines of trace.

2. The problem this mechanism exists to solve

You have a disk and a key-value workload with far more writes than reads. The obvious data structure is a B-tree: keep the keys sorted on disk, and to write a key, seek to its page and modify it in place. This is what Postgres, MySQL's InnoDB, and SQLite do, and it is an excellent design.

It has one property that becomes expensive at high write rates: a write is a random write. The key you are inserting determines where on disk it goes, and consecutive inserts go to unrelated pages. On spinning disks that meant a seek per write. On SSDs the seek is gone, but the page must be read, modified, and written back, and the flash translation layer beneath it turns a 100-byte update into a whole erase-block rewrite.

The LSM tree's answer: make every write sequential by refusing to modify anything. Buffer writes in memory, and when the buffer is full, dump it to a brand-new file in one contiguous pass. Never go back and edit that file.

That buys a lot, and it costs three things that pull against each other — the "RUM" trade-off that every storage engine is a position on:

• Reads get harder. One key can now have entries in many files. A read has to check them newest-first. This is read amplification, and §6.6 measures it.
• Space gets wasted. Old versions and tombstones sit on disk long after they stop being true. This is space amplification, and §6.5 shows it going the wrong way: deleting every key in the store makes it bigger.
• Fixing either one requires rewriting data you already wrote. That is compaction, and it is write amplification: the same bytes get written several times over their life.

You cannot have all three. B-trees pick low read and space amplification and pay in write amplification and random I/O. LSM trees pick low, sequential write cost and pay in reads and space, then hire compaction to claw some of it back.

3. Background you need

None of this is deep, but the commentary below leans on it.

The two that carry the result are the first and the second. A tombstone is a positive assertion of absence, and it only outranks the value it hides because it is newer. Compaction can destroy that ordering relationship without destroying either record — and then the assertion of absence is gone while the value is still there. Every other row is supporting detail.

4. The mental model

Before any code. The store is a stack of immutable files, oldest at the bottom, plus one mutable dict on top.

Three things to hold onto:

1. Time is encoded as position, and nothing else. There is no timestamp anywhere in this toy. "Newer" means "further up the stack." A key's current value is whatever the highest segment containing it says — including "deleted."
2. A tombstone (✝) is not the absence of data. It is data. It occupies a line in a file. It is the only thing standing between get("apple") and the perfectly intact apple=red sitting one layer below.
3. A read stops at the first hit. It never sees what is underneath. That is what makes it fast, and it is also what makes the tombstone sufficient — and what makes losing the tombstone fatal.

Now compaction. It squashes some contiguous window of that stack into one file:

The merged file is perfectly correct about the two segments it merged. The tombstone was the newest word on apple within that window, and dropping it looked like garbage collection — the key is deleted, why keep a record of something that doesn't exist? Because the record of absence was load-bearing for a segment that wasn't in the window.

5. Reading the source

The file is 200 lines and three classes. Read it in this order.

5.1 MemTable.delete — the four lines the whole toy is about

    def delete(self, key):
        # Not `del self.entries[key]`. Dropping the key here would hide it
        # only from *this* memtable; older segments on disk would still
        # answer the next get(). The tombstone out-votes them by being newer.
        self.entries[key] = (DEL, "")

The memtable is a dict. The obvious implementation of delete on a dict is del self.entries[key], and it is wrong here for a reason that has nothing to do with dicts: this object is not the database. It is the newest layer of one. Removing the key from the dict removes the store's opinion about the key, and in a stack where "no opinion" means "ask the layer below," that is the opposite of deleting it.

So a delete writes. That single decision propagates through everything else: deletes cost disk space (§6.5), deletes are asynchronous (the old value stays on disk until some compaction happens to squash it), and deletes create an object that compaction has to reason about rather than discard (§5.5).

Note the value: "". That is not a real value and nothing should ever read it, which is exactly why it's worth checking that nothing does — see §5.4 and the counterfactual there.

5.2 SSTable.write — sorting at the boundary

    @classmethod
    def write(cls, path, entries):
        with open(path, "w") as f:
            for key in sorted(entries):
                op, value = entries[key]
                f.write(f"{key}\t{op}\t{value}\n")
        return cls(path)

The sorted() is the only sort in the toy, and its placement is the design. The memtable is an unsorted dict, so a write is O(1); the sort happens once, at flush, over the whole batch. A store that kept its memtable sorted at all times would pay per write for a property it only needs per flush.

The three-column format (key, op, value) is a choice too. A real engine uses a type byte packed into the key; a toy could get away with a magic value string like <<deleted>>. The separate column is worth its width because it makes cat an inspection tool:

head data/store/*.sst

That apple del line with an empty third column is the tombstone. There is nothing else to it. Once you have seen it as a line of text sitting in a file, "a delete is a write" stops being a slogan.

5.3 SSTable.lookup — a linear scan, on purpose

        lines = 0
        for k, entry in self.items():
            lines += 1
            if k == key:
                return entry, lines
            if k > key:
                break
        return None, lines

Two things here are deliberate and one is a measurement instrument.

The scan is linear, not a binary search, even though the file is sorted and Python ships bisect. §7.3 has the full argument; the short version is that a real SSTable's lookup is a block-index seek whose cost the reader cannot see, and the point of this toy is that read cost is countable.

if k > key: break is the payoff of sorting. Once the scan passes where the key would have been, the key is not in this file. It changes no answer — only work. I ran it both ways over the 5-segment store from §6.6:

Identical answers; get(k00) costs 5 lines instead of 9. This is a line that is not where the behaviour lives, which is worth knowing before writing a paragraph claiming otherwise. Note it does nothing at all for get(zzz) — "zzz" sorts after every key, so the break never fires and the miss reads every line of every file either way.

lines is returned only so the demo can count. No real SSTable does this. It is here because "reads get more expensive" is a claim, and a claim with a number attached is a different thing from a claim.

5.4 LSMTree.get — searching backwards through time

    def get(self, key):
        """Newest to oldest; the first entry found wins, tombstone or not."""
        self.last_get_segments = 0
        self.last_get_lines = 0

        entry = self.memtable.get(key)
        if entry is None:
            for seg in reversed(self.segments):
                self.last_get_segments += 1
                entry, lines = seg.lookup(key)
                self.last_get_lines += lines
                if entry is not None:
                    break

        # A tombstone found first means deleted; running off the end of the
        # oldest segment means the same -- so a miss is the costliest read.
        if entry is None or entry[0] == DEL:
            return None
        return entry[1]

Nineteen lines holding three load-bearing decisions. I checked each by running the variant, not by reading.

reversed(self.segments). self.segments is oldest-first, so this walks newest-first. It is the only place recency is expressed, and it is what makes the tombstone work at all:

Reverse one iteration and the deleted key comes straight back — while banana, which was only ever written once, is unaffected. That contrast is the point: order only matters for keys with more than one entry, which is every key you ever updated or deleted.

if entry is not None: break. The read stops at the first hit, not the first SET. A tombstone terminates the search exactly like a value does. Continuing past it "to find a real value" would be a search for the oldest version, which is precisely backwards.

entry[0] == DEL. The translation from storage-layer entry to application-layer answer. Delete that clause and the tombstone's placeholder value leaks out:

Not an exception, not a crash — an empty string, which in most calling code is a perfectly plausible value. That is the shape of the worst class of storage bug: a sentinel escaping the layer that was supposed to interpret it.

And entry is None. Falling off the bottom of the oldest segment means the same thing as finding a tombstone: the key isn't there. Both return None, but they cost wildly different amounts — the tombstone stopped the search early, the miss read everything. §6.6.

5.5 LSMTree.compact — the unsafe parameter

        assert 2 <= n <= len(self.segments)
        victims = self.segments[-n:]

        merged = {}
        for seg in victims:  # oldest first, so newer entries overwrite
            for key, entry in seg.items():
                merged[key] = entry

        if drop_tombstones:
            merged = {k: e for k, e in merged.items() if e[0] != DEL}

        new = SSTable.write(self._new_path(), merged)
        for seg in victims:
            os.remove(seg.path)
        self.segments[-n:] = [new]
        return new

Sixteen lines, and the docstring above them (lsm.py:169-181) says the important part: drop_tombstones is deliberately unsafe, and it is the lesson rather than a bug. A real engine does not expose this; it computes the answer internally. Exposing it is what lets the demo run the safe and unsafe policies against one trace.

for seg in victims: iterates oldest-first so later writes overwrite earlier ones in the merged dict. This is the merge's entire conflict resolution: last writer wins, and "last" means "in the newest segment." My first counterfactual on this line came back unchanged, because the two victims in the demo trace share no keys — so I built one where they do (two writes to apple, one per segment):

Load-bearing, but only on overlapping keys — and worth reporting that the first, more obvious test said nothing.

victims = self.segments[-n:] — the newest n. This is where the aha actually lives, and it is not the word "partial." Compacting the oldest two segments with drop_tombstones=True is perfectly safe on the same trace:

Same n, same drop_tombstones, opposite outcome. The oldest-two window contains both apple=red and its tombstone, so the merge sees the whole story of that key and correctly emits nothing. The newest-two window contains only the tombstone.

LevelDB implements exactly this: "Compactions drop overwritten values. They also drop deletion markers if there are no higher numbered levels that contain a file whose range overlaps the current key." In this toy, "no lower segment could contain it" reduces to n == len(self.segments), because a linear stack of segments has no range metadata to be cleverer with.

os.remove(seg.path) happens after the new segment is written, and the list is swapped after that. That ordering is the crash-safety story of a real compaction, and it is the only part of it this toy gets right by accident; §8 covers what it's missing.

6. The demo, and what it proves

demo.py builds the same six-write store four times over — once to look at, three times to compact differently — plus two side measurements. Every scenario gets its own wiped directory under data/, so nothing leaks between them.

TRACE = [
    ("put", "apple", "red"),
    ("put", "banana", "yellow"),
    ("del", "apple", None),
    ("put", "cherry", "dark"),
    ("put", "date", "brown"),
    ("put", "elder", "black"),
]

With flush_threshold=2, every second distinct key seals a segment. That puts apple=red in seg0000 and its tombstone in seg0001 — one segment apart. §6.4 shows that gap is the whole experiment.

6.1 The store, and why get("apple") is already correct

python3 demo.py

Six writes, six entries, three files, four live keys. get("apple") reads seg0002 (no apple), then seg0001 (tombstone → stop) and returns None. Two segments, not three: it never opens the file containing apple=red. That is fine — and it is also the vulnerability.

The 90 bytes are worth deriving, because every byte figure below is arithmetic on them. Each line is key \t op \t value \n:

wc -c data/store/*.sst

Note the tombstone is the smallest line in the store, at 11 bytes. It costs almost nothing to keep, which will matter in a moment.

6.2 The aha: partial compaction that drops tombstones

seg0001 and seg0002 are merged into seg0003. The merge is internally correct: within those two segments, apple is deleted, so the merged result should contain no live apple, and it doesn't. Dropping the tombstone looks like tidying up after yourself.

But seg0000 was not in the merge, and it still holds apple=red. The next get("apple") reads seg0003 — where apple is now genuinely absent, not tombstoned — falls through to seg0000, finds red, and returns it.

A deleted key came back with its original value. No error was raised, no file was corrupted, and every individual step was locally reasonable. The database just started telling a different story about the past.

11 bytes reclaimed, one key resurrected. 90 − 79 = 11, which is exactly the tombstone line from §6.1. The entire "space saving" that motivated dropping it was 12% of the store, purchased with a correctness bug.

6.3 The two controls

Change one thing at a time. Keep the tombstone:

The tombstone is carried up into the merged segment, where it goes on doing its job. Note 90 bytes → 90 bytes: this compaction reclaimed nothing. Three files became two with the same total content, because the merged segments shared no keys. That is the honest price of correctness here, and it is the pressure that makes engineers reach for drop_tombstones=True in the first place.

Now widen the window instead:

apple=red and its tombstone are now in the same merge, so the merge sees both, resolves them to "deleted," and correctly emits neither. One segment, 65 bytes — 25 bytes reclaimed against 11 for the unsafe version, because a full merge also gets to drop the shadowed apple=red (14 bytes) that the partial merge had to leave alone. The safe policy reclaimed more than twice the space of the unsafe one.

That inverts the intuition the bug depends on. Dropping tombstones eagerly feels like the aggressive, space-saving choice; here it is the choice that saves less space and returns wrong answers. What actually reclaims space is widening the merge, not weakening the safety rule.

6.4 The trace counterfactual: the gap is the experiment

Remove one thing from the setup — not a line of the trace, but the flush threshold that decides how the trace is cut into segments:

At threshold 3, apple=red never reaches disk at all. The put and the delete land in the same memtable, where self.entries[key] = (DEL, "") overwrites the earlier (SET, "red") in the dict, and the flush writes only the tombstone. Nothing to resurrect. Same six writes, same order, same compact code — no bug, and no way to produce one.

So the resurrection isn't a property of the trace. It is a property of a value and its tombstone landing in different segments — which is what always happens when the delete arrives more than a memtable-flush after the write. In production, that is every delete of anything older than a few seconds.

(The same effect shows up if you flip >= to > in _maybe_flush (lsm.py:127): the threshold effectively becomes 3, one segment is produced, and the bug is unreachable.)

6.5 Supporting measurement: deleting everything makes the store bigger

Four keys in: apple set red (14) + banana set yellow (18) = 32 in seg0000, cherry set dark (16) + date set brown (15) = 31 in seg0001. 63 bytes.

Then delete all four. Each delete appends a tombstone; two more segments seal. apple del (11) + banana del (12) = 23, cherry del (12) + date del (10) = 22. 63 + 45 = 108 bytes.

A store containing zero live keys is 71% larger than the same store holding four. Every query against it correctly returns None, and it takes eight on-disk entries to say so. This is what "space amplification" means when it stops being a word: an append-only store cannot shrink except by compaction, and until compaction runs, deleting is a way of adding.

Cassandra operators meet this as tombstone hell — a partition that has been written and deleted repeatedly can accumulate so many tombstones that reads time out scanning them, and the fix is a compaction strategy change rather than anything the application can do.

6.6 Supporting measurement: the miss is the expensive read

Ten keys k00…k09 at threshold 2 make five segments of two keys each. Deriving all three:

• get(k09) — k09 is in the newest segment, seg0004 = [k08, k09]. Scan k08 (line 1, keep going), k09 (line 2, hit). 1 segment, 2 lines.
• get(k00) — the oldest key, so every newer segment must be checked and eliminated. In each, the first key already sorts after k00 (k08, k06, k04, k02), so the k > key break fires after one line. Then seg0000 hits on its first line. 5 segments, 5 lines.
• get(zzz) — never written. There is no early exit and no hit; every line of every segment is read. 5 segments, 10 lines — the entire database.

The shape to take away: an LSM tree's worst read is the one that finds nothing. A hit can stop early; a miss cannot stop at all. That is a miserable property for a cache-like workload, where "not present" is the common case — and it is precisely why every production LSM engine puts a Bloom filter in front of each segment. The filter answers "definitely not here" without touching the file, converting the most expensive read into the cheapest one.

Compaction is the other half of the answer. Running compact(all, drop=True) on stores of 10, 20 and 40 keys:

The segment count — the number of files you open, which on real hardware dominates — collapses from 20 to 1. The line count doesn't move, because this toy still scans linearly and a miss still touches every key; a real SSTable's block index makes that part logarithmic. Compaction fixes the file count. It does not fix the miss.

6.7 Every number here is pinned by a test

python3 test_lsm.py

test_partial_compaction_dropping_tombstones_resurrects_the_key (test_lsm.py lines 51–58) is the headline: it asserts get("apple") is None before the compaction and == "red" after. A test that asserts a bug is unusual, and correct here — the bug is the deliverable. If a future edit made the resurrection stop happening, this page would be wrong and the test would say so.

test_deleting_every_key_grows_the_store (test_lsm.py lines 87–98) pins the exact pair (63, 108), and test_a_miss_reads_every_segment (test_lsm.py lines 101–114) pins (1, 2), (5, 5), (5, 10).

6.8 The boundary condition — when none of this can happen

Worth naming each one so you can place your own system:

1. a key that is written, then deleted (a key that's only ever written can't come back — see banana in §5.4);
2. enough time between them that the value and the tombstone land in different segments (§6.4 — at flush_threshold=3 the whole thing evaporates);
3. a compaction that drops tombstones;
4. that compaction covering the tombstone's segment but not the value's.

In particular, a write-only or append-only workload can never hit this, no matter how badly its compaction is configured, because condition 1 never holds. If your table has no deletes, compaction really is just housekeeping and you can stop reading here. The moment it has deletes, compaction scope becomes a correctness constraint.

7. Design decisions and roads not taken

7.1 Why compact(n, drop_tombstones) is an unsafe API on purpose

A real engine has no such parameter — it decides internally whether each tombstone is droppable, per key, using the segment's key range and its level. Exposing the decision as a boolean is the toy's central liberty, and it needs justifying, because an unsafe API in a teaching artifact reads like a bug unless it announces itself.

It announces itself in the docstring (lsm.py:171-180), in capitals. The reason to expose it is that the safe and unsafe policies must run against the identical trace, in the same process, in one transcript. If the toy simply implemented the correct rule, the reader would see a store that works, learn nothing about why, and have no way to feel the pull of the wrong choice — which is a real pull, since dropping tombstones is what reclaims space, and space is why compaction exists.

The alternative I rejected: implement the correct rule and add a # TODO: this is subtly wrong comment on a commented-out branch. That teaches by assertion. This toy teaches by transcript.

7.2 Why a stack of segments, and not levels

Real LSM engines organise segments into levels (LevelDB, RocksDB) or size tiers (Cassandra's default), with rules about which files may be merged with which, and metadata about each file's key range so a read can skip files that cannot contain the key.

All of that is absent. The segments are a flat list, ordered by age, and a read checks every one. This costs realism and buys the ability to say "compaction covers the newest n" and have it mean something unambiguous. It also makes the safety rule collapse to something you can hold in your head — n == len(self.segments) — instead of a range-overlap test against a level hierarchy.

The trade-off levels exist to manage is worth naming even though it's not here: levelled compaction keeps files small and non-overlapping within a level, giving low read and space amplification at the cost of rewriting data many times (high write amplification). Size-tiered compaction merges files of similar size only when several accumulate, giving low write amplification but letting several copies of a key coexist (high space amplification, and worse reads). Same three-way trade-off from §2, different corner.

7.3 Why a linear scan rather than bisect

The file is sorted. Python ships bisect. Using it would be four lines and turn each lookup from O(n) into O(log n), which is what a real SSTable does via a block index.

I chose the scan because the toy's job is to make read cost visible, and a visible cost has to be a countable one. lines read: 10 in §6.6 is a number a reader can check against the segment contents by eye. bisect would replace it with a number that is smaller, harder to derive, and — crucially — unchanged in the shape that matters. The thing this toy wants you to feel is that a read touches five files, and file count is what a block index does not help with. Bloom filters and compaction do.

If you want the other version, it is a genuinely small change: sort the lines into a list at load, bisect_left for the key, compare. The answers will all be identical; only last_get_lines moves.

7.4 Why no write-ahead log

An LSM tree's memtable is in RAM, so a crash loses every write since the last flush. Real engines fix this with a WAL: append the mutation to a log file first, then apply it to the memtable, and on restart replay the log to rebuild what was lost.

That is a whole mechanism, and it already has its own toy in this repo — wal-kv, which additionally shows why kill -9 is unable to test it. Building a second WAL here would have doubled the LOC budget to re-teach something one directory over. The seam is clean: an LSM tree is a WAL plus a memtable plus segments plus compaction, and this toy is the last three.

7.5 Why no Bloom filter

§6.6's headline — a miss reads every segment — is exactly the problem Bloom filters solve, and leaving the problem unsolved is the point. A filter here would compress the toy's most instructive measurement into a False return and hide the reason anyone bothered. It deserves its own toy — bloom-filter takes this one as its motivation, and that is where the argument belongs. It also answers the question this section raises but cannot: a filter per segment turns the 5-segment miss into a probabilistic skip, and ten segments at 1% each waste 8.76% of reads rather than 1%.

7.6 Why the segment counter is not a timestamp

_new_path (lsm.py:139-142) names segments from self.next_id, a plain counter. Real engines use timestamps or sequence numbers with a timestamp component, and a real distributed engine needs them: Cassandra resolves a conflict between two replicas by comparing cell timestamps, and its whole delete story depends on a tombstone's timestamp being greater than the value it hides.

A counter is here for determinism — §8 covers what it costs. It is not a simplification of detail; it is a simplification of the model. In a single process with one writer, position in a list is a perfectly good clock. Add a second writer and it stops being one, which is the entire reason distributed databases are hard.

8. What's simplified vs. the real thing

• No write-ahead log, so a crash loses the memtable. Everything written since the last flush is gone on restart, and this toy doesn't even have a restart — LSMTree.__init__ starts with an empty self.segments and never reads the directory it was given. A real engine recovers its segment list from a manifest file and its memtable from a WAL. See wal-kv.
• Compaction is not crash-safe. compact writes the new segment, then os.removes the victims, then swaps the list (lsm.py:193-196). A crash between the write and the removes leaves orphan files; a crash mid-remove leaves the store's on-disk state disagreeing with any manifest. Real engines make the swap a single atomic manifest edit and treat leftover files as garbage to be collected at startup.
• Compaction is synchronous and blocking. It happens on the calling thread, so a merge of a 500 GB level would block every write for hours. Real engines run compaction on a background thread pool, throttle it against foreground I/O, and add back-pressure — deliberately slowing writes when compaction falls behind, because the alternative is unbounded segment growth and unbounded read amplification.
• No key ranges, no levels, no filters. A read opens every segment (§6.6). Real segments carry min/max key metadata, so most files can be skipped without opening them, plus a Bloom filter per file for the rest, plus a block index inside each file so a hit is a seek rather than a scan.
• The merge is a dict, not a merge. compact builds merged = {} and reads whole segments into memory (lsm.py:185-188). A real compaction streams a k-way merge over sorted iterators with bounded memory, which is what sorted segments are for; this toy sorts them and then doesn't exploit it.
• No timestamps, so no distributed conflict resolution. Segment order is the only clock (§7.6). Across replicas there is no such order, which is why real systems put a timestamp on every cell and why gc_grace_seconds is a duration — it is the window in which a repair must propagate a tombstone to every replica before it becomes safe to drop.
• Text format, unescaped. A key or value containing a tab or newline corrupts the file, since items() splits on \t and iterates lines (lsm.py:76-81). Real SSTables use length-prefixed binary records with per-block checksums, compression, and a footer.
• No concurrency control. put and get are not thread-safe, and a compaction running concurrently with a read would delete files out from under it. Real engines use immutable snapshots and reference counting so a reader holds its segments alive until it's done.
• Flush triggers on entry count, not bytes. flush_threshold=2 is chosen to make the demo legible. Real engines flush on memtable size (RocksDB's default is 64 MB) because memory is the constrained resource, and the resulting segment count depends on your value sizes, not your key count.

9. Check yourself

Answer before expanding. Each answer is derivable from the source, and each was verified by running it.

10. Further reading

Every link below was fetched and confirmed live when this was written.

• LevelDB implementation notes — short, and contains the exact rule this toy breaks: "Compactions drop overwritten values. They also drop deletion markers if there are no higher numbered levels that contain a file whose range overlaps the current key." If you read one thing after this page, read that sentence with §5.5 in mind.
• Cassandra: Tombstones — gc_grace_seconds (default 864,000 s, ten days), and the condition that matters: a tombstone is only removable during a compaction that includes every SSTable holding older data for that partition. That is §6.3 in production wording.
• The Last Pickle: About Deletes and Tombstones in Cassandra — the operational war story: why "deletes would often lead to reappearing data, called 'zombie' or 'ghost'," and why you must repair every cluster performing deletes at least once per gc_grace_seconds. Q6's answer in full.
• O'Neil, Cheng, Gawlick & O'Neil: The Log-Structured Merge-Tree (1996) — the original paper. Written about disk arms and a TPC-A History table, so the motivation reads as dated while the structure it proposes is what everything above is still doing.
• RocksDB: Compaction — levelled vs. universal vs. FIFO, and the amplification each one optimises for. This is §7.2's trade-off written by the people who had to ship all of them.
• Wikipedia: Log-structured merge-tree — the quickest orientation to the whole family, including the levelled diagram, if the terms in §2 were new.