How LSM-trees make writes fast without losing ordered data

The storage-engine idea that clicked for me here is simple: keep disk files sorted, but do not try to sort every write directly on disk. Let memory absorb random writes first, flush them as sorted files, and merge those files in the background. That design is the foundation of an LSM-tree.

Sorting changes what a segment file can do

An earlier append-only log stores records in write order. An SSTable, short for Sorted String Table, stores key-value pairs in key order. After compaction, each key appears once in a given file. If the same key exists in several files, the newest file holds the current value.

WRITE-ORDERED LOG
  cat -> black
  dog -> brown
  cat -> white

SSTABLE
  cat -> white
  dog -> brown

Sorting opens up efficient merging, range scans, sparse indexing, and block compression.

Sorted files are easy to merge

Two sorted SSTables can be merged by reading them forward side by side, like the merge step in merge sort. The engine writes the lower key next. When both files contain a key, it keeps the value from the newer segment. This works with files larger than RAM because it streams rather than fully loads them.

OLDER FILE             NEWER FILE
  cat -> black           cat -> white
  dog -> brown           fox -> red

MERGED OUTPUT
  cat -> white
  dog -> brown
  fox -> red

A sparse index replaces a full hash index

A hash-indexed log needs an in-memory entry for every key. An SSTable only needs offsets for occasional keys. For a lookup between two index entries, the database jumps to the earlier offset and scans the small sorted region that follows. Nearby records can be stored in compressed blocks, saving disk space and I/O bandwidth.

SPARSE INDEX IN RAM
  handbag  -> offset 0
  handsome -> offset 8 KB

LOOK UP: handiwork
  jump to handbag
  -> scan forward
  -> stop at handiwork or handsome

Memory turns random writes into sorted files

Writes arrive in arbitrary order, so the database does not insert them straight into an on-disk SSTable. It first adds them to a balanced in-memory tree called a memtable. That tree accepts arbitrary inserts but can produce its contents in sorted order.

When the memtable reaches a threshold, usually a few megabytes, the database flushes it as an immutable SSTable and continues writing to a fresh memtable.

RANDOM WRITES
  dog -> brown
  cat -> white
  fox -> red

MEMTABLE IN RAM
  cat -> white
  dog -> brown
  fox -> red

FLUSH TO DISK
  -> immutable sorted SSTable

Crash recovery needs a separate log

A memtable lives in RAM, so a crash before the flush would lose recent writes. The database also appends every write to a recovery log on disk. After a crash it replays that log to rebuild the memtable. Once a memtable is safely flushed as an SSTable, its matching recovery log can be discarded.

WRITE(key, value)
  -> append to recovery log on disk
  -> add to memtable in RAM

CRASH
  -> replay log
  -> rebuild memtable

An LSM-tree is a stack of sorted files

LSM means Log-Structured Merge-Tree. Recent writes are in a memtable, completed writes are immutable SSTables, and background compaction merges files while removing overwritten values and safe-to-delete tombstones.

Reads check the memtable first and then SSTables from newest to oldest. That preserves correctness because the newest matching value wins, but a read may have to inspect several structures.

GET key
  1. memtable
  2. newest SSTable
  3. next-oldest SSTable
  4. continue until found or exhausted

Bloom filters make absent-key lookups cheaper

A missing key can be expensive because the database may check many SSTables before proving it is absent. A Bloom filter is a compact probabilistic filter that can say a key is definitely absent from a particular file, so the database can skip that disk read. If it says the key may be present, the file still needs to be checked.

LOOK UP: unicorn

BLOOM FILTER
  definitely absent
  -> skip this SSTable

  may be present
  -> read the SSTable to confirm

Compaction decides the cost profile

Size-tiered compaction merges newer small SSTables into older larger ones. Leveled compaction organizes data into levels and key ranges, moving data incrementally into older levels. Leveled compaction generally uses less disk space, while both strategies try to limit how many files a read examines.

SIZE-TIERED
  small files -> larger files -> larger files

LEVELED
  recent level -> older levels
  key ranges kept more organized
  compaction happens incrementally

Where this design is a good fit

LSM-trees are strong for write-heavy workloads because they turn arbitrary writes into sequential SSTable writes. They also support efficient range queries because data remains sorted. The cost is that reads may inspect multiple files, and background compaction consumes resources while the database serves live traffic.

The same broad idea appears in full-text search: map each word to the IDs of documents containing it, store the mapping in sorted files, and merge files as the index grows.

LSM-TREE
  + high write throughput
  + efficient range scans
  + compact sorted files

THE COST
  - reads may inspect several files
  - absent-key lookups need care
  - compaction uses background resources

What I will carry forward

LSM-trees are not automatically the best storage engine. Their value is that sorted immutable files make merging cheap, keep indexes small, preserve range-query performance, and avoid random disk writes. The design pays for those benefits with recovery logging, multi-file reads, and continuous compaction. A storage engine is always deciding where the work should happen.

These are my personal learning notes from Designing Data-Intensive Applications by Martin Kleppmann.