The LSM Write Path from Memtable to Sorted Run

A B-tree performs an update by finding the page that holds the key and rewriting it, which means the update’s cost is a function of where the key lives, not of when it arrives. An LSM-tree inverts that: an update is appended to memory and to a log, and the key’s position in the on-disk structure is decided later, in batches, by sorting. The inversion buys sequential writes and costs read amplification, and the entire design is an exercise in bounding that cost.

The path an insert takes has five stages, and each one has a distinct cost and failure mode.

Stage one: the write-ahead log

The first durable act is an append to a log file. The record is the key, the value, and a sequence number that orders this write relative to all others; the sequence number is what makes the later merge able to decide which of two versions of a key is newer. The append is sequential, and the group commit batches many transactions’ records into one write and one flush, so the per-record cost approaches the device’s sequential bandwidth rather than its latency.

The log is not the index. It is a recovery device for the memtable, and it is discarded once the memtable it protects has been flushed. Its size is bounded by the memtable size, so the total log space is bounded by the number of memtables that are not yet flushed, which is a small number. When a log file is rotated, the records in it become protected by the new file, and the old file is deleted after the flush that made it redundant completes.

A crash between the append and the flush loses nothing: replay reconstructs the memtable from the log, in sequence-number order, and the tree is exactly as it was at the last append. A crash after the flush but before the log is deleted loses nothing either, because the replay is idempotent when records carry sequence numbers and the flushed run records the highest sequence it contains.

Stage two: the memtable

The in-memory structure is an ordered map. Common choices are a concurrent skiplist, which allows lock-free reads while a writer inserts, and a sorted vector of key-value pairs that is periodically sorted and merged, which is denser and faster to scan but requires a write lock at compaction time. The skiplist is the conventional choice because it makes the read path allocation-free and concurrent without a global lock, at the cost of roughly a pointer per level per entry.

The memtable holds a bounded number of bytes. When it exceeds the threshold, it is frozen: a new memtable is created to accept writes, and the frozen one is queued for flushing. The queue is the reason a write stall exists — if flushes cannot keep up with the write rate, the queue of frozen memtables grows, and the engine must either stall writers or slow them, because memory is finite.

A read must consult the active memtable, then each frozen memtable in order from newest to oldest, then the on-disk runs. Each memtable lookup is a search in an ordered structure, so the cost is logarithmic in the memtable’s entry count and, for the skiplist, involves a number of pointer dereferences proportional to the number of levels. The number of frozen memtables is normally zero or one, which keeps this term small; it is when the count grows that read latency degrades, which is the first place write pressure shows up as read pressure.

Stage three: flushing to a sorted run

Flushing writes the frozen memtable to a new file in key order, with a block index at the end. The write is sequential, so it is fast, and the file is immutable once written. Two auxiliary structures are written alongside: a filter, typically a Bloom filter over the keys, so that a lookup can skip the file entirely when the key is absent, and a set of block-level index entries so that a lookup within the file needs one or two reads rather than a binary search over blocks.

The flushed file is a run of level zero, the newest level. Its keys may overlap the keys of other level-zero files, because each file came from a different memtable and their ranges are whatever the writes happened to touch. Overlap is the reason level zero is expensive to read: a lookup must check every level-zero file that could contain the key, and the filter is what keeps that from being a binary search per file.

Level-zero files are small, typically the size of a memtable, and their count is bounded by a threshold. When the count exceeds it, a compaction is triggered. That threshold is the first place a tuning decision appears: a higher threshold amortizes compaction better and makes reads worse, because more files must be consulted.

Stage four: compaction into the next level

Compaction picks some level-zero files, reads their entries in key order, merges them with the overlapping files of the next level, and writes the result as new files in the next level. The merge is a k-way merge over sorted inputs, so it is streaming: it needs one buffer per input and writes output sequentially. Each output key is written with the newest version among the inputs, and older versions are dropped, which is where the space reclamation happens.

/* Emit the newest version of each key across sorted inputs. Inputs are
 * ordered newest first, so the lowest input index offering a key wins. */
while (!all_done(in)) {
    int best = -1;
    for (int i = 0; i < in->n; i++)
        if (!input_done(in, i) &&
            (best < 0 || key_less(input_key(in, i), input_key(in, best))))
            best = i;
    if (best < 0)
        break;
    /* Copy the entry: advancing `best` invalidates its buffer pointer. */
    struct entry e = entry_copy(input_entry(in, best));
    for (int i = 0; i < in->n; i++)          /* drop every other version */
        while (!input_done(in, i) && key_equal(input_key(in, i), entry_key(&e)))
            input_advance(in, i);
    if (!entry_is_tombstone(&e))
        run_append(out, &e);
    else
        tombstones_dropped++;
}

The tombstone check is what makes deletion work, and the ordering of the inputs is what makes it correct: an older live version must not be emitted after a newer tombstone for the same key, and it cannot be, because the loop advances past every version of the key at once and emits only the newest. Whether a tombstone may be discarded rather than written depends on whether the compaction’s inputs include the level where the oldest version of that key could live.

The output files are partitioned so that each covers a distinct key range within the level. That is the invariant that makes level one and below different from level zero: within a level, files do not overlap, so a lookup at that level needs to find at most one file. Finding it requires either a binary search over the level’s file boundaries held in memory, or a search in a manifest that records each file’s range.

The write amplification of this step is the ratio of bytes written to bytes ingested. Merging $k$ files of size $S$ with overlapping files of the next level writes roughly the input size, and the same bytes will be rewritten again when the output is compacted into the level below. With a size ratio $T$ between adjacent levels, a key that descends one level is rewritten together with about $T$ times its own volume of neighbour data, and a key that passes through $L$ levels is rewritten $L$ times. Leveled compaction therefore has write amplification near $T \cdot L$, with $L$ itself equal to $\log_T(N/M)$ for a database of $N$ bytes and a memtable of $M$ bytes.

That product is flat in $T$: a ratio of 10 with four levels gives about 40, and a ratio of 4 with about ten levels gives about the same. Choosing between them is not about write cost at all but about what the two extremes do to space and to read cost, which is the trade worked out in leveled compaction and the shape of the LSM tree.

Stage five: the merged view

The final structure is a set of immutable sorted runs at several levels, plus a mutable memtable and a manifest that records which files are live. A read consults them in order of recency and stops at the first version that satisfies the read’s snapshot, which means the read cost is the number of levels consulted plus the number of level-zero files, each term reduced by a filter that can reject a file without reading it.

The ordering matters: a read that finds the key in the memtable does not touch disk at all, a read that finds it in level zero touches one file, and a read that has to descend to the bottom level touches one file per level. The worst case is the key being absent, where the read must consult every level and every level-zero file and relies entirely on the filters to avoid reading them. That is why filter false-positive rates, and not just file counts, determine the read amplification of the tree, and why a filter’s bits-per-key setting is a real tuning parameter rather than a detail.

What the LSM write path does not avoid

The log write, the memtable insert, and the flush are all sequential or in-memory, so the write path itself is cheap. The costs deferred to compaction are not avoidable, only batched: every byte written will eventually be rewritten several times as it descends, and no amount of tuning changes the fact that the merge must read the old files to write the new ones. What tuning changes is how many times, and the answer is governed by the level structure.

There is also a cost the B-tree pays that the LSM does not, and it is worth stating in the other direction: an LSM write is never an in-place page rewrite, so it never dirties a page that a reader is scanning, and it never needs a latch on a page in the middle of the tree. Updates to hot keys do not concentrate on one page, because the update goes to the memtable regardless of which key it touches. That property is why LSM engines handle write-heavy workloads with high concurrency well, and it is the reason the design exists.

The corresponding failure is that space is not reclaimed until compaction runs, so a workload that overwrites the same keys repeatedly grows on disk until the merge catches up, and a workload that deletes keys accumulates tombstones that occupy space and slow reads until the merge that drops them runs. Both are consequences of the same deferred-merge design, and both are covered where the read path meets them, in point lookups, tombstones, and read amplification.