Module 08 · Lesson 6 of 15Free

LSM trees: storage designed for fast writes

Level

Advanced

Topic

Storage engines and on-disk data structures

Reading time

19 min

Fast appends leave unfinished work

A seller import sends 4,096 product updates a second into one Kartly catalog partition. Appending them is easy, but the seller’s ordered export still has to assemble scattered product records.

Kartly now has separate services and partitioned data. For this lesson, we examine one local catalog storage engine, not checkout transactions.

Our illustrative partition contains two million products. Each incoming update replaces a product’s complete stored value. The engine must support exact-key reads and exports ordered by product key.

How can it accept updates quickly without leaving reads and cleanup an ever-growing amount of work?

A sorted run is a sequence ordered by key. Think of several alphabetized lists, each containing corrections to earlier lists.

The LSM idea is to batch changes in memory, then merge them into larger disk components. It defers organization rather than maintaining one fully updated disk structure after every change.^{1The Log-Structured Merge-Tree (LSM-Tree)Patrick O’Neil, Edward Cheng, Dieter Gawlick and Elizabeth O’Neil, Acta Informatica, 1996}

That gives writes a short path. It also creates the central obligation: those batches cannot accumulate forever.

Sorting changes the storage bargain

In Append-only logs and Bitcask, a memory directory locates the latest record for each key.

That remains a useful solution. But our partition needs ordered exports, and a directory entry for every distinct product consumes memory. Adding more product keys increases that directory even when write traffic stays unchanged.

An LSM tree changes what must be organized immediately. The buffer handles current changes. Older records live in sorted files with their own lookup metadata.

The name means log-structured merge-tree. Its essential trade is deferred, batched maintenance instead of immediate disk-index maintenance.^{1The Log-Structured Merge-Tree (LSM-Tree)Patrick O’Neil, Edward Cheng, Dieter Gawlick and Elizabeth O’Neil, Acta Informatica, 1996}

The choice moves work through time. We now need to specify where an update lives before that work finishes.

Memory holds the newest changes

Call the engine’s active memory structure a memtable. When it fills, the engine writes a sorted string table, or SSTable, to storage. RocksDB uses memtables, recovery logs and sorted files as its basic storage constructs.^{3RocksDB OverviewRocksDB contributors, RocksDB documentation}

For our teaching engine, the local interface is small:

A storage error must remain different from “not found”. Otherwise an unreadable file could make an existing product disappear from an export.

The engine assigns each accepted mutation a sequence number: a local integer defining update order. We assume one serialized writer and no historical reads. This keeps the example focused on current values.

Our write path is:

1. Assign the next sequence number.
2. Record the mutation in the write-ahead log.
3. Apply it to the active memtable.
4. Acknowledge after the configured durability requirement is met.
5. When the buffer fills, freeze it and direct new writes to another buffer.
6. Write the frozen buffer as a sorted file.

“Freeze” means nobody can change that buffer. A background writer can now traverse stable input while the active buffer receives new updates.

Do not confuse acceptance with flushing. Our contract requires durable recovery information before a durable acknowledgment; an SSTable need not exist yet. The exact ordering and recovery protocol belong to The LSM write path.

The buffer therefore buys time, not permanent storage capacity. A slow flush eventually leaves nowhere to put the next update.

Newer records hide older records

Consider these illustrative mutations. p10 and p20 are product keys. The values are opaque product payloads.

A current read of p10 returns new-product. A read of p20 returns not found.

The delete marker is called a tombstone. Sorted tables retain deletion markers to hide values in older tables.^{2impl.mdGoogle LevelDB contributors, LevelDB documentation}

For this example, resolve a key by choosing its greatest sequence number across the relevant sources. If that record is a tombstone, stop with not found. Do not continue searching for an older value.

Suppose you remove the tombstone when flushing the memtable. Nothing would hide sequence 41. The retired product would reappear in the seller’s export.

A range scan applies the same rule repeatedly:

1. Position each relevant sorted source at the range’s start.
2. Compare the next keys.
3. Collect records for the smallest key.
4. Select that key’s newest record.
5. Emit it only if it is not deleted.
6. Advance those sources and repeat.

These rules explain correctness, not an efficient lookup implementation. Searching every file for every request would be expensive. The LSM read path adds ways to avoid unnecessary searches.

The important distinction is between physical records and logical products. Several physical records can represent one current product.

Turning a batch into ordered records

The engine’s flush preparation can discard earlier versions within this batch, because our model has no historical readers. It must preserve the latest deletion marker.

These functions model that transformation, not durable file writing. Keys are ASCII product identifiers, and sequences are unique positive integers within JavaScript’s safe integer range.

from dataclasses import dataclass


@dataclass(frozen=True)
class Entry:
    key: str
    seq: int
    value: str | None


def prepare_run(entries: list[Entry]) -> list[Entry]:
    latest: dict[str, Entry] = {}
    for entry in entries:
        previous = latest.get(entry.key)
        if previous is None or entry.seq > previous.seq:
            latest[entry.key] = entry
    return [latest[key] for key in sorted(latest)]


batch = [
    Entry("p20", 41, "retired-product"),
    Entry("p10", 42, "new-product"),
    Entry("p20", 43, None),
]
run = prepare_run(batch)
assert [(e.key, e.seq) for e in run] == [
    ("p10", 42), ("p20", 43)
]

type Entry = Readonly<{
  key: string;
  seq: number;
  value: string | null;
}>;

function prepareRun(entries: readonly Entry[]): Entry[] {
  const latest = new Map<string, Entry>();
  for (const entry of entries) {
    const previous = latest.get(entry.key);
    if (previous === undefined || entry.seq > previous.seq) {
      latest.set(entry.key, entry);
    }
  }
  return [...latest.values()].sort((a, b) =>
    a.key < b.key ? -1 : a.key > b.key ? 1 : 0
  );
}

const batch: Entry[] = [
  { key: "p20", seq: 41, value: "retired-product" },
  { key: "p10", seq: 42, value: "new-product" },
  { key: "p20", seq: 43, value: null },
];
const run = prepareRun(batch);
console.log(run.map(({ key, seq }) => [key, seq]));

Both produce p10 at sequence 42, followed by the p20 tombstone at sequence 43. Empty input produces an empty run.

For a batch of n records with u distinct keys, the map examines every record once. Sorting its keys costs about u log u comparisons. The transformation needs memory proportional to u.

A production ordered memtable can avoid this final sorting step. Our function makes the ordering and version-selection rules visible without implementing that data structure.

It still does nothing about obsolete values in earlier files.

Merging pays the deferred cost

Suppose every flush produces another run. An absent key may require checking them all in our unoptimized design. An export must reconcile them all. Repeated product replacements also leave obsolete payloads occupying storage.

Background merging is called compaction. LevelDB merges selected sorted files into new files and removes overwritten values when they are no longer needed.^{2impl.mdGoogle LevelDB contributors, LevelDB documentation}

The merge itself is straightforward. With two sorted inputs, compare their next keys and advance the smaller one. When keys match, apply the version rule. Each input record is visited once, giving linear work in the total input size.

The harder question is how much to merge at once.

For our engine, the components now have explicit responsibilities:

LevelDB records its serving file set in a manifest. That makes file membership explicit rather than inferred from directory contents.^{2impl.mdGoogle LevelDB contributors, LevelDB documentation}

Our replacement protocol must keep the old inputs until the outputs are complete and their membership is durably published. Existing readers also need their input files to remain accessible until they finish.

A crash before publication leaves unused output files. A crash afterward must recover the published replacement. Neither case should turn a partially written output into the database.

Exact publication mechanics and merge policies belong to Compaction. Here, their consequence is enough: background work needs both bandwidth and temporary space.

A buffer cannot fix overload

Assume each incoming mutation occupies 1 KiB, including its record overhead. Give this illustrative engine a 64 MiB flush threshold. Ignore compression and repeated-key collapse for this calculation.

The factor of five is an assumption, not an LSM constant. Measure it over a representative steady-state workload.

Now suppose only 16 MiB/s remains available for SSTable writes after other work. At amplification five, the engine supports about 3.2 MiB/s of logical input. Our import sends more than that.

Increasing the buffer only delays the consequence. Doubling its threshold doubles the interval before it fills; it does not raise sustainable storage throughput.

The tempting belief is “background work does not affect request latency”. But background and foreground operations share CPU, memory and storage. RocksDB explicitly describes writes stalling when full memtables cannot be flushed because background workers are occupied.^{3RocksDB OverviewRocksDB contributors, RocksDB documentation}

For Kartly, the visible failure is an import that stops making progress. Product changes remain unavailable, and a seller cannot finish preparing the sale.

Operate for sustained progress

For our engine, watch the age of the oldest frozen buffer and the amount of pending merge work. A rising trend means the engine is falling behind, even if individual writes still look fast.

Also measure import completion time and export latency. Engine throughput alone does not say whether sellers can finish their work.

Use the observed failure to choose a response:

These are investigation paths, not automatic diagnoses. Adding workers helps only when useful resources remain available.

Bound the number of frozen buffers and unfinished runs. When those bounds are reached, our engine waits or rejects new import writes rather than consuming unlimited memory.

Retries must respect that pressure. An immediate retry loop adds work without adding storage capacity.

For crash recovery, our design reloads the committed live-file set and replays recoverable log records. It does not treat every file found on disk as valid database content.

Where this shows up

• Design: a durable event log like Kafka also separates quick appends from background storage maintenance, though its record model differs.
• Design: a distributed key-value store needs a local storage engine beneath replication and partition routing.

We have treated recovery and publication as contracts; next, we will follow one mutation through the memtable, WAL and SSTable boundary.

Common mistakes

• Using file creation time as update order. A compaction output is newly created but can contain old records. Preserve logical sequence information.
• Deleting a tombstone because the key looks absent. Absence is the result the marker enforces. Prove that older values and required historical views no longer need it.
• Benchmarking only an empty engine. Run long enough for flushes and merges to compete with incoming traffic.
• Counting only application bytes. Capacity planning needs repeated table writes, recovery writes and merge reads.
• Treating an LSM as a transaction or replication guarantee. This lesson’s local replacement rules do not establish multi-key transactions or cross-server consistency.

Check your understanding

Summary