Engineering Atlas › System Design Fundamentals

Write-optimised storage with LSM trees

13 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

Write path

A write appends to the WAL for durability, then inserts into the memtable, a sorted structure in memory (usually a skip list). When the memtable reaches its size limit (RocksDB's write_buffer_size defaults to 64 MB; options.h), it becomes immutable, a fresh memtable takes writes, and a background thread writes the frozen one to disk as an SSTable in a single sequential pass. The WAL segment for it can then be deleted.

Nothing on disk is ever modified in place. An update is a new version of the key; a delete is a tombstone record. The newest version wins.

SSTables

An SSTable is a file of key-sorted entries, split into blocks of around 4 to 64 KB, each compressed. At the end sit a sparse index (first key of each block), a Bloom filter over all keys, and metadata such as min and max key. A point lookup checks the Bloom filter (about 1% false positives at 10 bits per key), binary-searches the index, and reads one block. RocksDB 6.15 added the Ribbon filter, which reaches the same 1% at about 7 bits per key, saving roughly 30% of filter memory for 3 to 4 times the CPU, mostly paid when filters are built in the background (RocksDB wiki).

Read path

A get checks the active memtable, immutable memtables, then SSTables from newest to oldest, stopping at the first hit. A tombstone hit means "not found." Range scans must merge iterators from every overlapping source, which is why scans are the LSM's weakest operation.

Compaction

Without compaction, file count grows forever, and so do read cost and dead data. Two families dominate:

The choice no longer has to be fixed up front. Cassandra 5.0 (announced October 2024) added the Unified Compaction Strategy (ASF), which treats leveled and tiered as two ends of one scale: a single scaling parameter W picks a fan factor, negative values behave leveled and positive values tiered, and W can be changed on a live table. The docs now recommend UCS for most workloads (Cassandra docs).

Tombstones are only dropped when compaction reaches the bottom level, or when no older file could still hold the key. Until then they cost space and read time.

Amplification, in numbers

For a 1 TB leveled store with a 10x fan-out: levels are roughly 1 GB, 10 GB, 100 GB, 1 TB. Space amplification is about 1.1x because only the bottom level holds most data and upper levels hold few duplicates. A point read checks the memtable, a handful of L0 files, and one file per level, but Bloom filters skip most of those, so it usually costs one data block read.

Down the stack

Layer 1The contract

RocksDB promises a sorted key-value map with atomic batched writes (WriteBatch), point gets, ordered iterators, and consistent snapshots: an iterator opened at sequence number S sees exactly the writes up to S, even while flushes and compactions rewrite the files underneath. Durability is easy to misread. RocksDB's WriteOptions::sync defaults to false: the WAL record is written to the OS but not fsynced, so a write survives a process crash but can be lost on power failure unless sync=true or the application calls SyncWAL (RocksDB wiki). Latency is a soft promise: if compaction falls behind, writes slow and then stop.

Layer 2The mechanism

LevelDB's log format, inherited by RocksDB, splits the WAL into 32 KB blocks. Each record fragment has a 7-byte header (a 4-byte CRC32C checksum, a 2-byte length, and a 1-byte type of FULL, FIRST, MIDDLE, or LAST), so records can span blocks and a torn tail fails its checksum (LevelDB log format). Every write gets a 56-bit sequence number, packed with an 8-bit value type (put, delete, merge) into the internal key, so multiple versions of one user key sort newest first.

An SSTable (the block-based table format) is a run of data blocks, 4 KB uncompressed by default in RocksDB. Inside a block, keys are prefix-compressed: each entry stores only the bytes that differ from the previous key, and every 16th entry is a restart point stored in full, with an array of restart offsets at the block's end so a lookup can binary-search restarts and then scan a few entries. After the data blocks come a filter block (the Bloom filter), an index block with one entry per data block, a metaindex block, and a fixed-size footer with a magic number that points to the index and metaindex (LevelDB table format). The set of live files is recorded in the MANIFEST, a log of VersionEdit records (file added at level N, file deleted); a flush or compaction publishes its result by appending one edit, which makes the switch atomic.

Back-pressure is explicit: when L0 holds too many overlapping files (RocksDB defaults: slow down at 20, stop at 36), foreground writes are delayed or stalled. A second trigger watches the estimated bytes still waiting to be compacted, slowing writes at 64 GB and stopping them at 256 GB by default (advanced_options.h).

Layer 3The machine

Every disk write an LSM issues is sequential: WAL appends, flushes, and compaction outputs. On a spinning disk that avoids the several-millisecond seek per random write. On an SSD it matters differently. Flash erases in blocks of megabytes, and an SSD fed random in-place 4 KiB updates must garbage-collect partially valid erase blocks, multiplying physical writes. LSM files are written once and deleted whole, so whole erase blocks tend to become invalid together and the drive's own write amplification stays low. The engine's write amplification (10 to 30 for leveled compaction) is paid instead in large, efficient I/Os.

Reads are where the machine pushes back. A point lookup that misses memory reads a 4 KB block, decompresses it, and binary-searches restart points. Compaction competes with foreground reads for device bandwidth and CPU (decompress, merge, recompress), so RocksDB offers a rate limiter and direct I/O for compaction (use_direct_io_for_flush_and_compaction) so it does not evict hot pages from the page cache.

Why it's built this way

  1. Random small writes are the most expensive operation on both disks and flash, so the LSM buffers writes in memory and emits only sequential files.
  2. Buffered writes need crash protection, so a sequential WAL backs the memtable.
  3. Immutable files accumulate and overlap, so compaction merges them.
  4. Compaction competes with users for I/O and CPU, so it is throttled, and when it falls behind, writes stall rather than reads degrading without bound.
  5. Each lookup could touch many files, so per-file Bloom filters and in-memory indexes keep most of them off disk.

Diagram

flowchart TD
    W[Write] --> WAL["WAL (append)"]
    W --> MT["Memtable (sorted, RAM)"]
    MT -->|full| IM["Immutable memtable"]
    IM -->|flush| L0["L0 SSTables (may overlap)"]
    L0 -->|compaction| L1["L1 (non-overlapping)"]
    L1 -->|compaction| L2["L2 (10x larger)"]
    R[Read] --> MT
    R --> IM
    R --> BF{"Bloom filter says maybe?"}
    BF -->|yes| L0
    BF -->|yes| L1
    BF -->|yes| L2

Worked example

A telemetry service ingests 200,000 writes per second of 200-byte records: 40 MB/s of user data. In a B+ tree on the same NVMe drive, each write dirties a random 16 KB page; even with batching, the device would see hundreds of MB/s of random writes.

With RocksDB in leveled mode, the WAL takes 40 MB/s sequentially and memtables flush a 64 MB SSTable every 1.6 seconds. With write amplification of about 15, compaction writes 600 MB/s in total, all sequential and large. That fits on a modern NVMe drive rated for 2 to 3 GB/s, but it consumes endurance: 600 MB/s is about 52 TB per day, so a 7.68 TB drive rated for 1 drive-write per day would wear out in months. Switching the cold, bulk data to universal compaction cuts write amplification to about 5 (200 MB/s) at the cost of up to 2x space while big compactions run.

On the read side, 10 bits per key of Bloom filter for 5 billion keys is about 6 GB of RAM. Without it, a miss might probe 7 files.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Leveled compactionLow space and read amplificationHigh write amplificationRead-heavy or space-constrained
Size-tiered compactionLow write amplification, high ingestMore space, slower reads, temporary 2x diskWrite-heavy, append-mostly data
Time-window compactionDrops whole files at TTL expiryBad for out-of-order or updated dataTime series with TTL
B+ tree insteadFast reads and scans, no compaction debtRandom writes, page-level write amplificationRead-heavy OLTP
Key-value separation (WiscKey, BlobDB)Large values not rewritten by compactionExtra lookup per read, separate GCValues over a few KB

Pitfalls in production

Leadership lens

Check yourself

  1. Why are LSM writes faster than B+ tree writes on the same hardware?

    Show answer

    Writes are buffered in memory and written as large sequential files, instead of dirtying random pages that each need a later random write.

  2. Why can a delete make a database larger, temporarily?

    Show answer

    A delete writes a tombstone, and the old value plus the tombstone both remain until compaction merges them at the bottom level.

  3. What does leveled compaction buy compared with size-tiered, and what does it cost?

    Show answer

    It bounds reads to one file per level and keeps space overhead near 10%, at the cost of rewriting each byte many more times.

  4. Why do Bloom filters help point reads but not range scans?

    Show answer

    A Bloom filter answers "might this exact key be here," while a scan needs every key in an interval from every overlapping file.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →