Database field guide · 21

LSM-Tree Storage

Memtables, SST files, compaction, and amplification

Understand how log-structured merge trees turn random writes into sequential files and pay for that efficiency through reads and compaction.

Franck Pachot7 chaptersLSM tree · SST · compaction · amplification

Build the mental model before choosing the mechanism.

This minibook was AI-generated from Franck Pachot's archived blog posts. Links to the original articles are included for source context and verification.

Writes land in memory first

An LSM tree records a durable write in a log and inserts its sorted key into a mutable memtable. Full memtables become immutable and flush as sorted-string-table files.

The WAL protects data before an SST flush.
Memtable size controls flush frequency and memory use.
A flush creates sorted durable input for later merging.

Reads merge several generations

A point or range read may consult memory and multiple SST files. Bloom filters, block indexes, caches, and key bounds avoid opening files that cannot contain the answer.

A newer value shadows older versions of the same key.
Bloom filters accelerate absence but do not return values.
Range scans benefit from sorted files but still merge iterators.

Compaction repays deferred work

Compaction merges overlapping SST files, discards obsolete versions when safe, and restores read efficiency. It converts cheap foreground writes into background CPU, read I/O, and write I/O.

Leveled and size-tiered policies choose different trade-offs.
Backlog can throttle writes to preserve stability.
Compaction concurrency must respect storage bandwidth.

Tombstones make deletion asynchronous

A delete writes a tombstone because older SST files are immutable. Compaction removes the tombstone and covered values only after snapshots and lower levels no longer need them.

Delete-heavy workloads can increase reads before reclaiming space.
TTL expiration follows the same deferred-reclamation principle.
A tombstone is correctness metadata, not wasted data by definition.

Amplification has three dimensions

Write amplification counts physical bytes rewritten per logical write; read amplification counts structures consulted; space amplification measures obsolete or duplicated bytes retained.

Optimizing one amplification often worsens another.
Measure at steady state, including compaction debt.
Small updates can rewrite large compressed blocks and SST ranges.

Distribution adds tablets and consensus

In distributed SQL, each tablet owns an LSM tree replicated through consensus. Query cost therefore combines local LSM work with RPCs, leader placement, and replica durability.

Tablet splitting creates new compaction domains.
Global indexes are additional distributed LSM trees.
The optimizer needs a cost model for both storage and network work.

Field manual

Concrete mechanics, diagnostic evidence, and executable patterns to carry into a real system.

Observe SST structure

YugabyteDB tablet diagnostics expose SST file counts, sizes, levels, and compaction state. Interpret them per tablet because one hot shard can hide behind cluster averages.

-- On a YugabyteDB node, inspect tablet-server metrics and tablet details.
-- Track per-tablet SST file count, bytes, flushes, compactions,
-- pending compaction bytes, and write stalls over the same interval.

Measure write amplification

Compare logical bytes accepted from the application with WAL and SST bytes written after compaction reaches a representative steady state.

write_amplification =
  (wal_bytes + flush_bytes + compaction_bytes_written)
  / logical_user_bytes_written

# Keep ingestion rate and compaction backlog in the same report.

Recognize tombstone debt

Deletes and TTL expiration create tombstones that remain until compaction can safely discard covered versions. Test reads before and after compaction rather than inferring reclamation from row counts.

EXPLAIN (ANALYZE, DIST, COSTS OFF)
SELECT * FROM event
WHERE tenant_id = 42 AND event_time >= now() - interval '1 day';
-- Compare storage rows scanned with rows returned.

Protect compaction headroom

Compaction shares CPU and storage bandwidth with foreground traffic. Alert on backlog and stalls early, then change concurrency or rate limits with the storage device's sustained bandwidth in mind.

capacity_headroom = sustained_device_write_bandwidth
                    - foreground_flush_bandwidth
                    - required_compaction_bandwidth
# A positive short benchmark is insufficient if backlog keeps growing.

Source articles

Optional deep dives with the complete experiments and product-version context behind this guide.

LSM-Tree compaction in YugabyteDB - starting a series of postsdev.to · 2023-01-31 Testing LSM-Tree merge for Size Amplification in YugabyteDBdev.to · 2023-01-31 B-Tree vs. LSM-Tree: measuring the write amplification on Oracle Database and YugabyteDBdev.to · 2024-03-21 Performance of range queries in B-Tree and LSM indexesdev.to · 2024-08-05 LSM Tree, Tombstones and YugabyteDB (No Vacuum)dev.to · 2022-11-08 Fast PITR and MVCC reads with Key-Value LSM Treedev.to · 2024-09-09 YugabyteDB Cost-Based Optimizer and cost model for Distributed LSM-Treedev.to · 2023-09-18