LSM Trees: Writes, Compaction, and Read Amplification

A storage engine receives a continuous stream of inserts, updates, and deletes. Updating a large on-disk search tree in place can turn those operations into scattered page writes. Buffering forever is impossible, yet flushing each key separately loses locality. A log-structured merge tree resolves the tension by accepting writes into memory, periodically emitting immutable sorted files, and reorganizing those files in the background.

The resulting write path is fast because it is sequential and batched, not because the work disappears. Compaction later reads old files, merges overlapping key ranges, discards obsolete versions when safe, and writes new files. Reads may inspect several runs before finding a key. Deletes become tombstones that persist until lower levels can no longer contain an older value.

The central thesis is that an LSM tree is an amplification budget managed over time. Memtables and sorted runs convert random foreground writes into efficient sequential I/O; compaction policy decides how much write, read, and space amplification the system pays in return. Understanding that policy is more useful than treating “LSM” as a synonym for write optimized.

Follow a Write from Memory to an SSTable #

A typical write first enters a database write batch. The engine appends enough information to its durability log, applies the mutation to an in-memory ordered structure called a memtable, and acknowledges according to its configured durability policy. The log protects mutations that have not yet reached an immutable table; it is not the sorted structure used for normal point and range reads. Database log ordering and crash recovery deserve their own treatment, so here the important boundary is simply that an acknowledged memtable write must be recoverable.

The memtable is commonly a skip list, tree, or another ordered map. Keys are stored in internal order, often combining the user key with a sequence number and operation kind. Sequence numbers let several versions of the same user key coexist while snapshots select the newest visible one. When the active memtable reaches a size threshold, the engine freezes it as immutable, starts a fresh memtable for new writes, and flushes the frozen contents as one sorted-string table (SSTable).

An SSTable is immutable after creation. It contains sorted data blocks, a block index, metadata such as smallest and largest keys, checksums, and often a per-file or partitioned Bloom filter. Immutability gives flushes and compactions a clean publication rule: write a complete new file, validate and sync it as required, then atomically add it to version metadata. Readers that already hold the old file set can continue safely while new readers use the new set.

This path batches many unrelated key updates into sequential file output. It also decouples foreground latency from immediate placement in the final on-disk organization. However, the engine now owns multiple sorted runs containing overlapping key ranges and historical versions. Flush is only the first half of the design; compaction is what prevents those runs from accumulating without bound.

Read Across Mutable and Immutable Runs #

A point lookup starts with the newest possible location. It checks the active memtable, then immutable memtables awaiting flush, then SSTables according to the engine’s recency and level rules. Within a run, file key bounds reject impossible files, a Bloom filter can reject a file that definitely lacks the key, the block index locates a candidate data block, and the block search finds the newest visible internal key.

A Bloom filter is only a read aid here. A negative result skips an SSTable lookup; a positive result still requires the real index and key comparison. Filters do not choose compaction, store values, replace key-range metadata, or establish correctness. They are especially valuable for missing point lookups when several files might overlap. Range scans generally cannot skip the same work because they must merge all runs that intersect the requested interval.

The engine reconciles candidate records by sequence number. A newer value shadows older values for the same key. A visible tombstone means “deleted” and stops the lookup even if an older SSTable contains a value. Snapshot reads may require an older version, so the reader cannot blindly take the first user-key match without checking visibility.

Read amplification is the amount of work beyond one ideal lookup. It can mean files consulted, blocks read, bytes decompressed, or I/O operations, so a metric must state its unit. A cache hit in several file indexes can make many logical probes cheap, while one false-positive filter that fetches a cold data block can dominate latency. Measure the physical path, not only the number of levels.

Worked Example: Versions Moving Through Levels #

Consider an engine whose current files contain these internal records, ordered conceptually as userKey@sequence:

Memtable:  beta@108 = B3, delta@110 = D1
L0-new:    alpha@105 = A2, beta@104 = TOMBSTONE
L0-old:    alpha@101 = A1, gamma@102 = G1
L1:        alpha@80 = A0, beta@90 = B1, epsilon@91 = E1

Level 0 contains recently flushed files whose key ranges can overlap, so a lookup may need several files in newest-first order. Lower leveled tiers usually have non-overlapping files within each level, permitting at most one candidate file per level for a point key.

A read of alpha at snapshot 109 ignores the memtable’s unrelated keys, finds alpha@105 in the newer L0 file, and returns A2; it need not expose alpha@101 or alpha@80. A read of beta at snapshot 109 does not see beta@108 = B3 if the chosen snapshot predates sequence 108 according to the engine’s boundary convention; it reaches beta@104 = TOMBSTONE and returns absent rather than falling through to beta@90 = B1. At a later snapshot, beta@108 = B3 wins and represents reinsertion after deletion.

Now suppose compaction selects both L0 files and the overlapping L1 range. A multiway merge emits records in internal-key order. If no active snapshot can need the alpha versions at 101 or 80, compaction can retain only alpha@105. It must keep the beta tombstone or an equivalent deletion boundary if an unselected lower level might still contain beta@90. Dropping it too early would resurrect B1.

An illustrative compacted output might be:

L1-output: alpha@105 = A2, beta@104 = TOMBSTONE, gamma@102 = G1
L1-other:  epsilon@91 = E1

The memtable records are unaffected because they were not compaction inputs. Publication installs the output files and removes the selected input files in one metadata version change. Old files are deleted only after no reader references the old version.

This small example exposes three distinct forms of temporary duplication: overlapping runs for search, historical versions for snapshots, and tombstones for deletion safety. Compaction can remove each only when its input coverage and the oldest required snapshot make removal correct.

Leveled and Tiered Compaction Pay Differently #

A compaction policy chooses inputs, destination, and timing. Two broad families dominate, although production engines offer hybrids and many tuning knobs.

Leveled compaction organizes data into levels with target sizes growing by a ratio, often called the fanout. Level 0 accepts flush files and may overlap. From level 1 downward, files within one level normally cover disjoint key ranges. When a level exceeds its target, the engine selects files and merges them with overlapping files in the next level. Point reads gain a predictable search shape, and old versions are consolidated aggressively. The cost is rewriting overlapping data repeatedly as it descends.

Tiered or size-tiered compaction accumulates several similarly sized runs, then merges them into a larger run. It rewrites data less frequently and can sustain heavy write throughput, but more runs overlap at once. Reads and temporary disk use are consequently higher, especially during a merge. Universal compaction is a related policy that selects runs using size and overlap heuristics rather than fixed levels.

Compaction selection also affects fairness. Always compacting the most overfull level may neglect a cold range full of tombstones. Choosing the largest overlap can reduce future write cost but starve other files. Hot keys repeatedly rewritten through one range can create a compaction hotspot even when total database size appears balanced.

No policy dominates independently of workload. Point-heavy stores often value fewer runs; ingest pipelines may value lower foreground write pressure; delete-heavy workloads need timely tombstone propagation; time-windowed data may exploit files whose entire ranges expire together.

Reason in Three Amplification Budgets #

Write amplification is commonly measured as bytes written to storage divided by logical bytes written by the application:

Metadata, durability logs, replicas, and device-internal writes may be included or excluded, so compare only measurements with the same boundary. Leveled compaction can rewrite a key as it moves through several levels and as overlapping ranges are merged. Tiered policies reduce some rewrites but leave more runs to search.

Read amplification measures extra probes or bytes needed to satisfy a logical read. Missing point lookups often show the role of filters most clearly; successful lookups may terminate in a recent run. Range queries merge iterators from all overlapping sources and may process obsolete versions before returning a smaller result.

Space amplification compares physical storage occupied with live logical data:

Obsolete versions, tombstones, uncompacted runs, snapshots, and temporary compaction outputs all raise it. During compaction, inputs and outputs coexist until publication, so an engine needs headroom beyond its steady-state estimate. Running nearly full can deadlock progress: compaction needs free space to create the files that would reclaim space.

The three budgets conflict. More aggressive compaction can lower read and space amplification while increasing write I/O. Larger memtables produce fewer, larger flushes but consume memory and make recovery replay larger. Bigger SSTable blocks improve compression and sequential scans while point reads may decompress extra bytes. Stronger compression saves storage and I/O but spends CPU. Bloom filters consume memory and cache capacity to avoid candidate reads.

Treat configuration as workload policy. A database serving latency-sensitive random reads should not inherit settings optimized for bulk ingestion merely because both use an LSM tree.

Tombstones, Snapshots, and Skew Complicate Cleanup #

A delete inserts a tombstone at a new sequence number. It is cheap in the foreground but creates future work. Compaction can discard the tombstone only when no older snapshot needs the deleted value and no unexamined lower run can contain a version that the tombstone must hide. Range tombstones add interval reasoning and can intersect many files.

Long-lived snapshots pin old versions. A compaction may read and rewrite them yet remain unable to discard them, increasing all three amplification forms. The same is true when change-data capture, backups, or replication retain a historical sequence boundary. Operators need visibility into the oldest pin, not just total disk use.

Skew creates local rather than global pressure. A small hot range may be updated repeatedly, producing many versions and overlapping L0 files. Monotonically increasing keys can concentrate every flush at the end of one level. Large values can make one compaction consume disproportionate bandwidth. Policies often split files by size and key boundaries, isolate large values, or apply subcompactions, but each choice changes read locality and scheduling.

Write stalls are a deliberate safety valve. If immutable memtables, L0 files, or compaction debt exceed thresholds, slowing or stopping foreground writes prevents unbounded memory and file growth. Hiding stalls with ever-larger thresholds merely moves failure toward disk exhaustion. The sustainable ingest rate cannot exceed the storage bandwidth and CPU available for the required compaction work over time.

Test Correctness and Operate the Compaction Loop #

Correctness tests should generate sequences of puts, deletes, reinserts, snapshots, flushes, and compactions, then compare every read and range scan with a simple reference map that retains versions. Force compaction input boundaries so a tombstone is compacted without all lower data, and assert that deleted keys never resurrect. Hold an old snapshot while newer versions compact, then verify both old and current reads. Corrupt blocks and metadata to confirm checksums fail closed.

Crash tests should interrupt file creation, synchronization, and manifest publication. After restart, the engine must expose either the old file set or the complete new set, never a version that references partial output. These tests concern safe publication of LSM files; detailed transaction-log redo and undo belong to database recovery rather than compaction policy.

Performance verification needs distinct workloads: present and absent point reads, short and long range scans, uniform and skewed updates, delete-heavy traffic, and bulk load. Run long enough to reach steady state. Record application bytes, device bytes read and written, compaction bytes, files or blocks consulted per read, filter usefulness, cache hit ratios, stall time, level sizes, pending compaction bytes, tombstone age, and free-space headroom.

Operational dashboards should make debt visible. A healthy momentary ingest spike can produce pending work that drains afterward. If debt rises indefinitely at constant load, foreground throughput exceeds sustainable compaction capacity. If read latency rises with L0 count, the engine is paying deferred write work on the read path. If disk use remains high after deletes, inspect snapshots and whether tombstones have reached the final overlapping level before increasing storage blindly.

Capacity changes require patience: modifying fanout, target file size, compression, or compaction style may trigger a full reorganization whose temporary I/O exceeds normal load. Roll out by shard or node, preserve free-space margin, and compare amplification and tail latency through an entire compaction cycle.

Takeaways #

• Memtables batch ordered updates; immutable SSTables make flush and compaction publication manageable.
• Reads reconcile versions across mutable state and sorted runs, with Bloom filters serving only as negative SSTable lookup aids.
• Compaction is the core maintenance loop, not optional cleanup after the “real” write path.
• Leveled policies favor tighter read and space bounds; tiered policies often favor lower rewrite cost and burst absorption.
• Write, read, and space amplification trade against one another and must be measured with explicit boundaries.
• Tombstones and old versions disappear only when compaction coverage and snapshot horizons make removal safe.
• Sustainable throughput is the rate at which compaction debt remains bounded, not the rate an empty engine can buffer briefly.

An LSM tree earns fast writes by scheduling where and when disorder is resolved. Once amplification, snapshot retention, and compaction debt are treated as first-class constraints, its behavior becomes explainable: every cheap foreground mutation creates a bounded obligation that the background system must eventually pay.