Sorted runs and tombstones: model an LSM read path

Last updated: 4 Oct 20269 min read

tutorial

A log-structured merge design buffers writes in a mutable memtable and periodically produces immutable sorted runs. A point lookup checks the memtable first, then runs from newest to oldest; the first matching key decides visibility. A deletion is represented by a tombstone so an older value does not reappear after a later run is written. This in-memory model flushes when the memtable reaches a distinct-key threshold. It stores each run as a sorted tuple and uses binary search within that run. Full compaction visits runs oldest to newest so newer entries overwrite older ones; after all older runs are consumed, their tombstones can be dropped.

Operational case

Write A-19 as west and A-47 as north; the first two-key memtable flushes. Then update A-19 to east and delete A-47; another run flushes. A lookup finds east from the newer run, while the tombstone makes A-47 absent despite its north value in the older run. There are two runs before compaction and one run containing only A-19 afterward. If compaction merged only some runs while older runs remained elsewhere, discarding a tombstone could resurrect a deleted value. This example avoids that hazard by compacting all existing runs together and keeping the current memtable as the newest layer.

Working Python program

"""An in-memory model of memtable flushes, immutable runs, and tombstones."""

from bisect import bisect_left


class RunIndex:
    def __init__(self, flush_limit: int = 3):
        if flush_limit <= 0:
            raise ValueError("flush_limit must be positive")
        self.flush_limit = flush_limit
        self.memtable: dict[str, str | None] = {}
        self.runs: list[tuple[tuple[str, str | None], ...]] = []

    def put(self, asset_id: str, value: str) -> None:
        self.memtable[asset_id] = value
        self._flush_if_full()

    def delete(self, asset_id: str) -> None:
        self.memtable[asset_id] = None
        self._flush_if_full()

    def _flush_if_full(self) -> None:
        if len(self.memtable) >= self.flush_limit:
            self.runs.append(tuple(sorted(self.memtable.items())))
            self.memtable.clear()

    def get(self, asset_id: str) -> str | None:
        if asset_id in self.memtable:
            return self.memtable[asset_id]
        for run in reversed(self.runs):
            position = bisect_left(run, asset_id, key=lambda item: item[0])
            if position < len(run) and run[position][0] == asset_id:
                return run[position][1]
        return None

    def compact_all(self) -> None:
        latest: dict[str, str | None] = {}
        for run in self.runs:
            latest.update(run)
        # All older runs are consumed, so their deletion markers can be dropped.
        self.runs = [tuple(sorted((key, value) for key, value in latest.items() if value is not None))] if latest else []


assets = RunIndex(flush_limit=2)
assets.put("A-19", "west")
assets.put("A-47", "north")
assets.put("A-19", "east")
assets.delete("A-47")
print(assets.get("A-19"))
print(assets.get("A-47"))
print(len(assets.runs))
assets.compact_all()
print(assets.runs)

Output

east
None
2
[(('A-19', 'east'),)]

Time, space, and tradeoff

A memtable write is expected O(1) until a flush; sorting M distinct memtable entries costs O(M log M) time and O(M) new-run space. With R runs, a missing-key lookup performs up to R binary searches, costing O(sum log size(run)) and incurring read amplification. Full compaction over T stored entries and D distinct keys costs expected O(T + D log D) time in this dictionary-and-sort model and O(D) additional space. Keeping multiple versions increases space until compaction. These are in-memory algorithm costs, not disk I/O or durability guarantees. The code has no write-ahead log, fsync, manifest, snapshots, concurrent reads, or crash recovery.

Common Mistakes

Do not search older runs before the memtable or newer runs.
Do not treat a tombstone as an absent entry while an older value still exists.
Do not discard tombstones during partial compaction when older layers remain.
Do not call this in-memory demonstration a durable database.

Connected lessons

Test this invariant in the incident flag and path audit, then answer the contract quiz.

Inverted indexes: intersect sorted incident postings adds a related indexing contract.

Scalable Bloom filters: grow without discarding old members extends the membership design choices.

Tournament trees: merge sorted runs through one winner path adds a related structure with a different operation boundary.

data structures

range-query-structures