Chapter

LSM Trees and Compaction

Part E · Storage and Recovery|3,714 words|about 16 min read|Volume E

29.0 What this chapter gives you#

Some storage engines accept new writes into memory and later produce sorted immutable files instead of continually updating one in-place search tree. This chapter explains that family of designs.
You will follow a key through a memory table, sorted runs, older versions and deletion markers, then examine how compaction trades write work, read work and temporary space.
The companion model is an in-memory sorted-run exercise, not a RocksDB implementation. It has no real WAL, concurrent snapshots, file manifest or crash-safe installation protocol.

29.1 Sequential writes#

29.1.1 PLAIN — in simple words#

A system receiving many scattered key updates can collect them before writing larger organized groups to storage. That changes the physical work performed for each incoming request.
Writing sequentially can avoid some scattered access costs, but the work does not disappear. The engine must later find the latest values and reorganize accumulated files.
An LSM design is therefore not “writes are free.” It moves and batches work, creating trade-offs that depend on the workload and storage system.

29.1.2 PLAIN — a picture in your head#

Rather than walking to the filing cabinet for every arriving note, Mira collects notes in an organized tray and periodically files a sorted batch.
Later searches may need to consult several batches until the office merges them into a cleaner arrangement.
Where the comparison breaks: real engines need durable logs, ordered installation of files and concurrency controls. An ordinary tray that vanishes in a fire does not provide durable acknowledged writes.

29.1.3 PLAIN — a worked example#

Ten thousand synthetic updates each contain 100 bytes of logical key/value payload. The incoming payload totals 1,000,000 bytes, or 1 MB decimal.
If storage writes those values first into new sorted files and later rewrites them during compaction, total bytes written can exceed 1 MB. WAL, indexes, filters, compression and metadata add further differences.
Define write amplification as physical bytes written divided by logical bytes written over a stated interval and boundary. If the measured boundary writes 5 MB for 1 MB of logical input, the ratio is 5.
This arithmetic does not predict RocksDB’s ratio. The real ratio depends on configuration, key distribution, updates and which storage layers the measurement includes.

29.1.4 PLAIN — what is really happening inside#

New entries are organized in a memory structure and may also be logged for recovery. A flush creates a sorted persistent run under the engine’s durability protocol.
Older runs remain available while newer runs accumulate. A lookup must choose the correct visible version across these structures.
Background compaction merges selected runs, discards eligible obsolete versions and installs replacement files safely. This is ongoing maintenance work, not a one-time setup step.

29.1.5 TECHNICAL — the engineer’s version#

RocksDB’s documented architecture includes a memtable, log files and sorted-string-table files. It is an embedded storage-engine library, not by itself a complete networked database service. [S140]
Log-structured merge designs batch updates into sorted runs and reorganize them over time. Their compaction policy determines the shape of the stored levels and which runs reads may need to consult. [S134]
Distinguish the engine’s write amplification from a flash device’s internal write amplification. Multiplying or comparing ratios requires compatible boundaries and denominators.

29.1.6 WORDS — remember these#

LSM tree: organize writes through memory and merged sorted runs — a log-structured merge family of storage designs with deferred reorganization. Write amplification: storage writes exceed logical input — a measured ratio of bytes written at a named layer to logical bytes accepted over a stated interval. Sorted run: a sequence already ordered by its search key — a file or logical collection that can be searched and merged using key order.

29.2 Memory tables and immutable files#

29.2.1 PLAIN — in simple words#

A memory table holds recent entries in a searchable structure. When it reaches a chosen limit, the engine can freeze it and flush its contents into an immutable sorted file.
Immutable means the installed file is not edited in place by ordinary key updates. Later updates appear in newer structures, and compaction eventually replaces groups of files.
An immutable file is not automatically a complete immutable history. Old files can be retired, and the engine can discard obsolete versions under its retention rules.

29.2.2 PLAIN — a picture in your head#

Mira writes into today’s tray. When it fills, she seals it for filing and starts a new tray so incoming work can continue.
The sealed batch does not receive handwritten corrections. New correction notes go into the active tray and take precedence under the office’s version rules.
Where the comparison breaks: a real flush can fail partway. The engine needs metadata identifying which files are complete and installed, not merely files whose names happen to exist in a directory.

29.2.3 PLAIN — a worked example#

Let the active table hold entries (A,1,'red'), (B,2,'blue') and (A,3,'green'), where the middle number is a strictly ordered model version.
A current lookup for A returns green because version 3 supersedes version 1. A snapshot lookup at version 2 returns red under the model’s visibility rule.
After flush, the sorted representation groups A’s versions and B’s entry. The same logical answers should hold before and after the flush.
A flush that accidentally drops version 1 while a permitted version-2 snapshot still exists would violate that snapshot contract.

29.2.4 PLAIN — what is really happening inside#

Engines can keep active and immutable memory tables concurrently while background workers flush completed batches.
Recovery logging protects recent acknowledged work according to the chosen settings. Disabling or weakening logging changes the failure contract; sorted files alone do not protect entries still only in memory.
A manifest or equivalent metadata identifies the active file set and related state. Installing new files and retiring old ones must survive interruption without exposing an arbitrary mixture.

29.2.5 TECHNICAL — the engineer’s version#

RocksDB describes memtable flushes producing sorted table files and associated log lifecycle management. Its configurable recovery and synchronization behaviour must be read separately from its high-level architecture. [S140]
Internal keys commonly combine user-key identity with sequence or version information in LSM implementations. The exact encoding and comparison order are product details; this book’s tuples are a teaching representation.
A correct flush preserves every version required by active snapshots and the current visibility contract. A latest-value-only export is not a valid substitute when historical snapshot reads remain supported.

29.2.6 WORDS — remember these#

Memtable: the searchable workspace for recent writes — an in-memory structure holding entries before or alongside persistent sorted files. Immutable table file: a sorted file replaced rather than updated in place — an installed run whose ordinary contents do not change after creation. Manifest: the record of which storage files belong to the current state — metadata coordinating installed runs and their lifecycle.

29.3 Sorted runs#

29.3.1 PLAIN — in simple words#

Sorting makes each run easier to search and combine with another run. But a key may appear in several runs, so finding one occurrence is not necessarily enough.
The engine must select the version visible to the reader. A newer deletion marker can override an older value that still exists in a lower run.
Range queries must merge ordered candidates and resolve duplicates or versions while preserving the requested key order.

29.3.2 PLAIN — a picture in your head#

Three alphabetized card boxes contain successive batches of corrections. Looking up a name requires considering the newest relevant card, not accepting the first old card you find.
Printing all names in order requires merging the boxes and removing superseded copies under a clear rule.
Where the comparison breaks: engine lookups use indexes, filters and metadata to skip irrelevant runs. They do not necessarily scan every card in every box.

29.3.3 PLAIN — a worked example#

Run R1 contains A at version 1 with value red and C at version 2 with value black. Run R2 contains A at version 3 with value green and B at version 4 with value blue.
A current ordered merge returns A=green, B=blue, C=black. It does not return A twice merely because two physical versions exist.
A permitted snapshot at version 2 returns A=red and C=black; B did not yet exist in that snapshot. The version limit changes the answer even though the same files may be consulted.
The model explicitly orders versions numerically. Wall-clock timestamps from unsynchronized writers are not silently substituted for this ordering rule.

29.3.4 PLAIN — what is really happening inside#

Key-range metadata can rule out runs that cannot contain the requested key. Within a run, an index can locate the relevant block.
A Bloom filter can help reject absent keys without reading their data blocks, subject to its construction and lookup contract. A possible match still needs verification against real entries.
Snapshot visibility, key comparison and deletion handling must agree across memory tables, file indexes and compaction. A mismatch can create lost or resurrected records.

29.3.5 TECHNICAL — the engineer’s version#

A merge iterator can combine ordered runs using a priority structure while grouping equal user keys and selecting the highest visible version under the defined comparator.
In the simple model with k runs and n emitted candidates, a heap-based merge can organize candidate selection in approximately O(n log k) comparisons, excluding decoding, I/O and version-resolution costs. This is an algorithmic model, not a device-latency estimate.
Real compaction strategies constrain run overlap and hence lookup work. RocksDB’s documentation distinguishes leveled and tiered/universal approaches rather than one universal LSM layout. [S134]

29.3.6 WORDS — remember these#

Merge iterator: read several ordered runs as one ordered sequence — an iterator that combines candidates while resolving key and version rules. Visible sequence limit: the newest version a snapshot may use — a model or engine boundary excluding later updates from that reader. Run overlap: several files cover some of the same key range — a layout property affecting how many candidates a lookup may need to inspect.

29.4 Read amplification#

29.4.1 PLAIN — in simple words#

A request for one small value can require several checks and reads across memory, indexes, filters and runs. That extra work is part of read amplification.
The term needs a definition. It can refer to bytes read relative to bytes returned, or to the number of storage probes required for one logical lookup. These are different metrics.
Optimizing only write speed can leave readers doing excessive work later. A storage design should be judged against the complete workload, not one convenient operation.

29.4.2 PLAIN — a picture in your head#

Filing each arriving batch immediately is easy, but finding one customer’s latest note becomes harder if the office keeps hundreds of overlapping boxes.
A directory and “not in this box” filters reduce unnecessary opening, while merging boxes reduces the number of places to check.
Where the comparison breaks: one physical read can bring many useful entries into cache. Counting boxes without naming the cache and block boundary can misrepresent actual device work.

29.4.3 PLAIN — a worked example#

A toy absent-key lookup checks four overlapping runs. Filters reject three runs, leaving one candidate block read that ultimately finds no matching key.
Without those filters, the same model might read four candidate blocks. The logical result is still “not found”; the physical work differs.
If each block is 4,096 bytes and the model reads four, it transfers 16,384 bytes at that modeled boundary. A real cache can reduce device reads below this count.
A filter false positive costs extra checking. A false negative caused by a broken filter protocol can hide a real record and is a correctness failure, not merely a performance cost.

29.4.4 PLAIN — what is really happening inside#

Read cost depends on run count, overlap, filters, block indexes, cache state and how many obsolete versions must be examined.
Negative lookups can be especially revealing because they may need to establish absence across all relevant structures.
Range scans have different behaviour from point lookups. A filter designed for exact-key membership may help less when the request spans a broad interval.

29.4.5 TECHNICAL — the engineer’s version#

Define separate metrics for run probes, data-block reads, bytes read and user-visible latency. Report warm and cold cache assumptions rather than treating these metrics as interchangeable.
Leveled and tiered compaction make different read/write/space trade-offs; workload skew and implementation optimizations can change the practical result. [S134]
The companion records model probe counts only. It does not measure RocksDB file I/O or claim a particular production read-amplification factor.

29.4.6 WORDS — remember these#

Read amplification: extra storage work for a logical read — a defined ratio or probe count measured at a specified layer. Negative lookup: a search that establishes absence — a lookup returning no visible matching key after checking relevant structures. Filter false positive: a filter suggests a candidate that is absent — extra verification work without a false final membership claim.

29.5 Compaction and tombstones#

29.5.1 PLAIN — in simple words#

Compaction merges selected runs and removes versions that are no longer needed under the visibility and retention rules.
Deletion often begins as a tombstone: a newer marker saying that an older value must not be returned. The older bytes may still exist until safe cleanup occurs.
Dropping the marker too early can resurrect an older value from an unmerged file. Deletion correctness depends on which older versions remain reachable.

29.5.2 PLAIN — a picture in your head#

A new card says “this account entry is deleted,” while an older card remains in a lower archive box. Throwing away only the deletion card makes the old card look current again.
The cleanup clerk must know whether all older relevant copies have been covered before removing the marker.
Where the comparison breaks: real deletion also involves snapshots, backups and replicas. Safe removal from one LSM structure does not prove erasure from every system copy.

29.5.3 PLAIN — a worked example#

R1 contains (A,1,'red'). R2 contains (A,3,TOMBSTONE). A current lookup returns no A; a permitted snapshot at version 2 returns red.
Compacting only R2 and dropping its tombstone while R1 remains would wrongly expose red to a current lookup.
In a latest-only toy mode with no older snapshots and all relevant runs included, compaction can remove both the obsolete value and its deletion marker. The assumptions are part of the result.
If a later (A,4,'green') is added, current A is green while a version-3 snapshot remains deleted. Recreation is another versioned state, not evidence that the earlier deletion never occurred.

29.5.4 PLAIN — what is really happening inside#

Compaction reads selected runs, resolves versions and writes replacement runs. The old files remain necessary until the new file set is safely installed and no reader still requires them.
This can require temporary space for both input and output files. A nearly full disk can prevent the cleanup work intended to reclaim space.
Tombstone removal requires knowledge of older versions and snapshot requirements. A simple age threshold is not universally sufficient without the protocol’s supporting assumptions.

29.5.5 TECHNICAL — the engineer’s version#

Leveled compaction typically trades more rewriting for tighter run organization, while tiered/universal approaches can reduce some write amplification at the cost of read and space amplification. These are design tendencies, not universal numeric rankings. [S134]
The model exposes two operations: a visibility-preserving merge retaining versions, and latest-only compaction allowed only when the caller declares complete run coverage and no retained snapshots. Tests demonstrate the unsafe tombstone-drop counterexample.
Neither operation implements crash-safe file installation, concurrent reader references or a real deletion guarantee across backups. Those are separate protocol layers.

29.5.6 WORDS — remember these#

Compaction: merge and reorganize stored runs — background work that installs a new representation and discards only eligible obsolete state. Tombstone: a newer marker hiding an older value — a deletion record retained until older visible copies and snapshot requirements permit removal. Resurrection: an old deleted value becomes visible again — a correctness failure caused by losing the deletion information while older state remains reachable.

29.6 Workload trade-offs#

29.6.1 PLAIN — in simple words#

A useful storage choice asks what the application actually does: frequent small updates, large range scans, mostly reads, repeated changes to a few hot keys or mostly new keys.
Background maintenance must keep up with the long-term write rate. A short benchmark can look fast while leaving a growing backlog of compaction work.
The right comparison includes steady-state latency, throughput, space, recovery and operational effort. One peak write number is not a complete description of the system.

29.6.2 PLAIN — a picture in your head#

An office can accept incoming boxes quickly by stacking them in the corridor. That speed is not sustainable if nobody can sort the boxes and the corridor eventually fills.
A steady-state test asks whether incoming work and cleanup can continue together without an ever-growing backlog.
Where the comparison breaks: engines can throttle or stall writes deliberately to avoid exhausting memory or storage. A slowdown can be a protective response to accumulated work, not arbitrary malfunction.

29.6.3 PLAIN — a worked example#

A synthetic service accepts 10 MB/s of logical writes. At a chosen measured storage boundary, steady-state write amplification is 6, implying about 60 MB/s of writes before other uncounted work.
If the device and competing workload leave only 40 MB/s for that work, the long-run demand exceeds the available budget by 20 MB/s under these assumptions.
A brief test may temporarily absorb the difference in memory and pending files. It cannot continue indefinitely without reducing demand, increasing capacity or changing the layout and workload.
These values are illustrative. Measure actual amplification and sustained capacity rather than selecting a product from this arithmetic alone.

29.6.4 PLAIN — what is really happening inside#

Compaction competes with foreground reads and writes for CPU, memory, bandwidth and temporary space.
Skew matters: repeatedly updating a small key range can behave differently from uniformly rewriting the entire dataset. Compression and value sizes also change the balance.
A benchmark should include sufficient duration for maintenance to occur and should report pending work, not merely completed foreground requests.

29.6.5 TECHNICAL — the engineer’s version#

Report workload distribution, key/value sizes, update ratio, point/range reads, cache state, compaction policy, durability settings and storage headroom. Keep acknowledged-write guarantees equivalent across comparisons. [S134] [S140]
Test restore and recovery alongside steady-state performance. An engine that meets latency targets but cannot meet the required recovery objective does not meet the complete application requirement.
The book’s model develops the mechanisms; it is not a benchmark ranking of LSM and B-tree products. Both families have sophisticated implementations and workload-dependent trade-offs.

29.6.6 WORDS — remember these#

Compaction backlog: reorganization work waiting to be completed — pending maintenance that can increase read cost, space use or write stalls. Steady state: workload and maintenance remain sustainable together — an operating regime without unbounded growth of deferred work under the stated conditions. Space amplification: physical footprint exceeds live logical data — a ratio whose scope includes the selected files, versions and temporary maintenance state.

29.97 Practice and worked answers#

Compute write amplification. One MB of logical input causes five MB of writes at the measured boundary. Answer: the ratio is 5; name whether WAL and device-internal writes are included.
Read versions. A has red at sequence 1 and green at sequence 3. Answer: latest reads green; a sequence-2 snapshot reads red under the model.
Merge runs. R1 has A1=red,C2=black; R2 has A3=green,B4=blue. Answer: latest ordered output is A=green,B=blue,C=black.
Interpret filter work. Three filters reject and one candidate block is read. Answer: one modeled block read, not necessarily one physical-device read.
Find resurrection. Drop A’s sequence-3 tombstone while its sequence-1 value remains in another run. Answer: a current read can wrongly expose the old value.
Allow latest-only cleanup. All relevant runs are covered and no older snapshots are supported. Answer: the model can remove obsolete versions and a fully covered tombstone; the assumptions must remain explicit.
Budget sustained work. Ten MB/s logical input with amplification six needs sixty MB/s at the named boundary, but forty is available. Answer: demand exceeds that budget by twenty MB/s; temporary buffering does not solve the long-run mismatch.
Limit the model. Does the sorted-run exercise validate RocksDB crash recovery? Answer: no. It lacks real files, logging, manifest installation and concurrency.

29.98 Common wrong ideas#

Wrong: LSM writes create no later work. Right: flushing and compaction move and rewrite data.
Wrong: immutable files mean eternal immutable history. Right: files and obsolete versions can be retired.
Wrong: finding any key occurrence gives its current value. Right: visibility and newer versions or tombstones matter.
Wrong: a filter’s possible match proves a record exists. Right: verify against the actual entries.
Wrong: a tombstone can be discarded immediately. Right: older reachable values and snapshots can still require it.
Wrong: compaction always reduces instantaneous disk usage. Right: input and replacement files can coexist temporarily.
Wrong: a short burst benchmark demonstrates sustainable throughput. Right: deferred maintenance must keep up in steady state.
Wrong: LSM or B-tree is universally faster. Right: compare complete implementations under the actual workload and guarantees.

29.99 Chapter summary in 20 lines#

LSM designs organize recent writes in memory and persistent sorted runs.
Batching changes the timing and shape of work rather than eliminating it.
Recovery logging protects recent work according to the selected durability contract.
Immutable files are replaced through controlled installation rather than ordinary in-place edits.
A manifest identifies which runs belong to the installed state.
Multiple versions of one key can coexist across memory and files.
A reader chooses the highest version visible to its snapshot.
Sorted runs support ordered search and merging.
Filters and range metadata can avoid some unnecessary probes.
Read amplification needs a defined metric and cache boundary.
Write amplification compares physical writes with logical input at a named layer.
Compaction reorganizes runs and removes only eligible obsolete versions.
A tombstone prevents an older deleted value from being returned.
Dropping a tombstone too early can resurrect old data.
Older snapshots can require versions that current readers no longer need.
Compaction can require temporary space for old and new files together.
Leveled and tiered strategies trade read, write and space costs differently.
Background maintenance must keep up with the sustained workload.
Measure backlog, latency, throughput and recovery, not just peak ingestion.
The educational run model is not a production storage engine or crash-safety proof.

Return to contents