data-stateestablished · medium operational burden

LSM Tree Storage

Also known as: log-structured-merge-tree, memtable-sstable

Intent

Absorb high write volume by buffering writes in memory and flushing them as immutable sorted files that are merged in the background.

Problem

Update-in-place structures turn every write into random disk I/O, which caps write throughput. Workloads such as ingestion, messaging and activity feeds write far more than they read. The store must stay fast to write while keeping reads reasonably cheap.

Forces

•Sequential disk writes are much faster than random writes
•Reads must check more than one place if data is spread across files
•Background compaction competes with foreground traffic for I/O
•Deletes and overwrites leave obsolete data that must be reclaimed

Solution

Overview

A log-structured merge tree trades read work for write speed. Instead of modifying pages in place, it turns all writes into sequential appends and sorts the data later. It underlies Cassandra, RocksDB, LevelDB, HBase and many others.

How it works

Writes land in a log and a memtable, flush to level files, and compaction merges them downward.

write -> WAL (disk) + memtable (RAM, sorted)
memtable full -> flush -> L0 SSTable
compaction: L0 + L1 -> merged sorted L1 ... Ln
read -> memtable -> L0 files -> L1 ... (bloom filter skips files)

Size-tiered compaction favors write throughput and uses more space. Leveled compaction keeps one sorted run per level, which lowers read and space amplification at the price of more write amplification.

Three amplification factors describe the trade-off. Write amplification is how many times a byte is rewritten by compaction, read amplification is how many files a lookup may consult, and space amplification is how much extra disk obsolete versions occupy. Tuning one pushes the others. For example, adding more bloom filter bits lowers read cost for a little memory, while a larger memtable produces fewer, bigger flushes. Measure on production-like data, because synthetic uniform keys hide the skew that makes real compactions expensive.

Pitfalls

Ignoring write amplification: each byte may be rewritten many times across levels, which wears SSDs.
Deleting heavily without planning for tombstone cleanup, so scans slow down.
Running disks near full, leaving compaction no room to work.
Choosing a compaction strategy without measuring the real read to write ratio.

Key takeaways

LSM trees convert random writes into sequential ones.
Compaction is the hidden cost; monitor its backlog.
Bloom filters and indexes keep reads tolerable.
Pick the engine by workload shape, not popularity.

✓ When to Use

•Write-heavy workloads such as logs, events and metrics
•Datasets larger than memory with mostly key-based access
•Systems where sustained ingest rate matters more than point-read latency

✗ When Not to Use

•Read-dominated workloads needing predictable low-latency point reads
•Small datasets that fit comfortably in a B-tree
•Workloads with heavy in-place updates to the same hot keys and tight space limits

Pros

+Very high sequential write throughput
+Good compression because files are sorted and immutable
+Immutable files simplify snapshots and replication

Cons

−Read and space amplification until compaction catches up
−Compaction causes I/O spikes and tail latency
−Tuning compaction strategy requires expertise

Cost Profile

Infrastructure

Medium - needs spare disk and I/O headroom for compaction

Operational

Medium - monitor compaction backlog and write stalls

Cognitive

High - amplification trade-offs are non-obvious

Failure Modes

Compaction falls behind and the engine throttles or stalls writes
Tombstones accumulate and slow range scans
Disk fills because compaction needs temporary extra space

Real-World Examples

Alternatives

Related Patterns

database-indexing
partitioning

Competency Domains

data stateeconomics evolution