Course contents
On this page
Log-structured storage — extended reference
Original detailed coverage and citations accompanying the focused log-structured storage lesson.
This reference preserves the earlier detailed chapter and its citations. Start with the guided explanation, then use these sections for additional mechanisms and qualifications. References to the original lesson sequence are historical.
Part 2: Representing and locating data
Prerequisites: Lesson 10 and the preceding foundations.
Learning outcomes
- Trace writes through a mutable table, immutable sorted files, and compaction.
- Explain Bloom-filter false positives, tombstone retention, and version selection on reads.
- Calculate read, write, and space amplification and connect them to background capacity debt.
Fast ingestion can accumulate future work
A write-heavy service accepts mutations quickly by appending to a log and updating memory. For several minutes its latency looks excellent. Later, background merging falls behind. Files overlap, reads inspect more candidates, disk bandwidth is consumed by maintenance, and writes begin to stall. The initial ingestion rate was real, but it was not sustainable.
A log-structured merge design organizes updates so foreground writes can be sequential or memory-oriented while immutable sorted files are merged later. The architecture changes when and where work occurs. It does not eliminate the work of maintaining an efficient searchable representation.
The mutation path
A conceptual write first records recoverable information in a log under the configured durability policy, then updates a memory structure called a memtable. A full memtable becomes immutable and is flushed to a sorted file, often called an SSTable. Metadata records which files make up the current database version.
mutation -> log + mutable memtable
|
freeze
|
immutable sorted run
|
flush file, publish metadata
|
compactionThe diagram describes responsibilities rather than prescribing a universal ordering for every engine. A real implementation must define when a write becomes visible, when it is acknowledged, and how recovery reconciles the log and published files. An SSTable existing on disk does not make it part of the database until authoritative metadata references it.
Crash-safe publication commonly requires writing a complete new file, ensuring its required persistence, and publishing metadata through a recoverable update. Deleting old files before the new representation is safely authoritative can lose data. Retaining old files too long wastes space but is generally easier to recover from than deleting required state too early.
Reading across versions and runs
A lookup searches relevant memory structures and immutable files. Newer versions can shadow older values. A tombstone represents deletion so an old value in another run does not reappear. The search must use sequence or timestamp rules consistent with snapshot visibility.
If a key may exist in many overlapping runs, a miss can require examining many candidates. File key ranges and indexes eliminate impossible candidates. Bloom filters can say that a key is definitely absent from a represented set or possibly present. A false positive causes extra work; a false negative would violate correctness and is not an allowed behavior of the intended filter.
Filters must match the indexed key and comparison semantics. Prefix filters can accelerate a particular access shape while being inappropriate for another. Filter memory competes with data cache memory. Allocating more bits reduces false positives but does not make hot-key updates independent or remove compaction work.
Compaction policies
Compaction reads existing runs and writes a new representation with selected obsolete versions removed. A leveled policy tends to constrain overlap in lower levels, often trading more rewriting for predictable reads and space. A tiered policy can allow more runs before merging, often reducing write amplification while increasing read or space costs. Actual engines provide variants and tuning parameters.
Compaction is not merely sorting files again. It must preserve snapshots, respect deletion semantics, and handle concurrent writes and metadata versions. A version that is obsolete for current reads may still be required by an older snapshot. A tombstone may be removable only when no older relevant value can survive outside the compacted input and no required historical reader needs it.
Distributed replicas introduce another retention problem. A deletion removed too early on one replica can be undermined by old data arriving from another replica or repair. The safe rule depends on the distributed engine’s deletion and repair protocol. An embedded storage library cannot infer every higher-level replica obligation automatically.
Read, write, and space amplification
Write amplification compares physical bytes written with logical mutation bytes, under a stated boundary. Read amplification describes extra reads or bytes examined to answer a logical read. Space amplification describes retained physical space relative to a chosen logical live-data baseline. Definitions must say whether logs, replicas, compression, and device-internal work are included.
For an illustrative 30 MB/s logical mutation stream and total host-level write amplification 8, device writes consume 240 MB/s. If the device can sustain only 300 MB/s for the relevant mixed workload, little headroom remains for reads, checkpoints, backups, or bursts. Compression can change byte rates while adding CPU. Replication multiplies cluster work separately.
A design that lowers write amplification may increase the number of runs consulted by a lookup. A design that reduces space amplification may compact more aggressively. These are competing goals constrained by workload. A dashboard should therefore track debt and amplification rather than judging health from foreground append speed alone.
Compaction debt and stalls
Compaction debt is work needed to maintain the intended layout that has not yet been performed. If writes generate debt faster than maintenance can retire it, the system eventually violates its steady-state assumptions. Files accumulate, lookup work rises, and free space can become unsafe.
A controlled stall or write slowdown can protect the engine from unbounded accumulation. It is a visible symptom, but avoiding every stall by disabling limits can produce worse failure later. The useful operational question is why debt grows: insufficient bandwidth, too little compaction concurrency, excessive overlap, large values, workload skew, or another bottleneck.
Compaction competes with foreground I/O and CPU. More threads may retire debt faster until they saturate the device or disturb caches. Too much background parallelism can worsen interactive latency. Resource governance should protect both immediate requests and the maintenance needed for sustainability.
Snapshots and garbage collection
A snapshot defines which versions remain observable. Long-lived snapshots can prevent reclamation even if current readers no longer need old values. A small number of slow or abandoned snapshots can therefore create substantial storage growth.
Version retention must be connected to transaction, backup, and change-stream semantics. A backup may need a consistent view while copying files. A consumer may need log history from an earlier position. Releasing one retention mechanism does not prove all old state is disposable. Explicit reference tracking or retention horizons make these dependencies inspectable.
Consider an illustrative key updated once per second for a day. If every version must remain available to a snapshot or history feature, compaction cannot reduce it to one current value without violating that feature. A workload with rapid overwrites and short snapshots can reclaim much more aggressively. The same logical update rate can therefore have very different space behavior.
Large values and separation
Writing a large value through multiple compaction levels can be expensive. Some designs separate values from sorted key metadata, so compaction moves references rather than repeatedly moving the full payload. That introduces value-log garbage collection and another indirection on reads.
The benefit depends on value sizes, overwrite patterns, and access locality. Small values may not justify the extra metadata and lookup. Large values with frequent updates can benefit substantially from reduced rewriting, but the engine must still reclaim obsolete value records safely. Separation moves maintenance into another subsystem rather than abolishing it.
Merge a point lookup across explicit versions
Consider three immutable runs plus a memtable, with larger sequence numbers representing later mutations. The memtable contains K -> value_C at sequence 90. Run A contains K -> tombstone at 80, run B contains K -> value_B at 60, and run C contains K -> value_A at 20. A current read selects value C. A snapshot at sequence 85 selects the tombstone and reports absence. A snapshot at 70 selects value B. One key therefore has different valid answers depending on the requested visibility boundary.
The lookup cannot simply stop at the first physical match unless its search order and snapshot checks prove that match is the newest visible version. A newer-than-snapshot entry must be skipped, not returned. A visible tombstone must stop older values from resurfacing. During compaction, retaining only value C would break snapshots at 85 and 70 if those snapshots remain supported.
snapshot 95: sequence 90 -> value C
snapshot 85: sequence 80 -> deleted
snapshot 70: sequence 60 -> value B
snapshot 30: sequence 20 -> value AThe trace is constructed to separate version visibility from file location. A real engine may encode sequence and record type into internal keys and order those keys so merging can apply the rule efficiently. The important invariant is that compaction must preserve every answer allowed by the supported snapshot set. Discarding a version is safe only after proving no required read can distinguish its removal.
Range reads perform a related merge over iterators from relevant runs. A priority structure can choose the next key while suppressing shadowed versions and applying tombstones. With many overlapping runs, this merge performs extra comparisons and block reads even when the final result is small. Read amplification therefore depends on run layout and version density, not merely the number of live keys.
Bloom filters reduce negative work under a defined probability
A Bloom filter uses several hash-derived bit positions to represent inserted keys. If any required bit is clear, the key is absent from that represented set. If all are set, the key may be present and the engine must check the underlying structure. In the conventional idealized model with m bits, n inserted keys, and k independent hash positions, false-positive probability is approximately (1 - exp(-kn/m))^k.
With ten bits per key, choosing k near 10 × ln(2), or roughly seven, gives an illustrative false-positive probability around 0.8%. The calculation assumes suitable hashing and the standard model; actual implementations, blocked layouts, and key distributions can differ. More bits consume memory that might otherwise cache data blocks. The correct allocation minimizes total expected work, rather than simply minimizing the filter’s error rate.
For an absent key checked against twenty independent candidate files with 1% false-positive probability each, expected unnecessary positive checks are 0.2. The probability of at least one is approximately 1 - 0.99^20, or 18.2%, under independence. This shows why a small per-file false-positive rate can still appear in a meaningful fraction of misses when many files overlap. File-range pruning can reduce the candidate count before filters are consulted.
Filters must be built and published consistently with file contents. A corrupted or incorrectly constructed filter that produces a false negative can hide existing data. Deletions cannot safely clear arbitrary shared bits in the ordinary structure because other keys may rely on them. Immutable-file filters avoid that maintenance issue by rebuilding with the new file. The filter remains a correctness-sensitive index even though its positive answers are deliberately approximate.
Manifest publication and orphan handling
Imagine a compaction merges input files A and B into new file C. The engine writes C completely, validates its footer and metadata, makes the required bytes persistent, and publishes a recoverable metadata change replacing A and B with C. Only after the published version and all relevant readers no longer need A and B may their physical files be deleted. Actual engines can combine or batch these steps, but their ordering obligations remain.
A crash before publication can leave C as an orphan: complete on disk but not part of authoritative state. A crash after durable publication can leave A and B as obsolete files awaiting cleanup. Both cases can be recoverable if metadata unambiguously identifies the valid file set. Deleting A and B before publication is safe would instead destroy the only authoritative representation if the crash loses C’s registration.
The metadata itself needs integrity and atomicity. A partially appended edit cannot be interpreted as a complete version transition. Recovery uses framing, checksums, and sequence rules to find a valid prefix or another safe representation. Directory entries and file creation/deletion durability also belong to the storage protocol; writing file contents alone does not automatically prove a file can be rediscovered after every failure.
Readers can retain references to an older file-set version while compaction publishes a newer one. Reference counting, epochs, or another lifetime protocol prevents deletion of files still being read. This is the same ownership pattern seen in buffer frames and tree nodes, applied to immutable storage objects. Immutability simplifies concurrent content access while leaving publication and reclamation work.
Quantify maintenance debt over time
Suppose a constructed service ingests 30 MB/s of logical mutations and generates an additional 150 MB/s of future compaction rewriting, for 180 MB/s of required host writes before another specified log cost. If available maintenance capacity retires only 120 MB/s of that compaction work, debt grows by 30 MB/s. Over ten minutes, it accumulates about 18 GB of pending rewrite work using decimal units.
The exact debt-to-latency relationship depends on file layout, but indefinite growth cannot represent a stable operating point. Larger memory can delay a flush or absorb a burst; it cannot fix a long-run maintenance deficit. More compaction workers can help if concurrency was limiting, but not if the device is already saturated. Faster devices can help until CPU decompression, checksumming, or metadata becomes the next limit.
Temporary free-space demand matters during catch-up. A compaction writes outputs while inputs remain needed. If inputs and outputs are both large, the system can run out of space before reaching the compacted smaller result. Reserving space for maintenance and rejecting or slowing writes early protects recoverability. A disk that is “only” 90% full can be unsafe for one compaction policy and comfortable for another, depending on overlap and output size.
A useful control policy monitors pending bytes, file counts, write rates, and free-space headroom. It can throttle foreground ingestion before runaway debt produces a crisis. The threshold must account for how long intervention takes. Waiting until no safe compaction can start leaves little room for recovery.
Tombstones preserve negative information
A deletion is information: an older value must no longer be returned. If run A contains a tombstone for K and an unmerged older run B contains K’s value, dropping the tombstone while keeping B can resurrect K. Compaction can remove both when it proves that no surviving lower-priority source or required snapshot needs the older representation. The proof is about the relevant key range and version horizon, not the tombstone’s age alone.
Range tombstones compactly delete intervals, such as all keys in a tenant’s retired namespace. They can reduce foreground per-key work, while reads and compaction must combine interval deletion state with point entries. Overlapping range tombstones can make visibility and fragmentation more complex. A logical bulk delete is cheap only if the later maintenance costs and access checks remain manageable.
Distributed repair adds a different source of old values. An embedded engine can know its local run set, but a distributed database must also ensure a disconnected replica will not reintroduce deleted data under its reconciliation rules. Retention periods, repair guarantees, and replica replacement policy establish that boundary. Applying an embedded compaction rule directly to a distributed deletion contract can be unsafe.
Compare leveled and tiered layouts through a scenario
Consider an append-heavy event stream with few overwrites and queries scanning recent time ranges. A policy allowing several sorted runs can avoid repeatedly rewriting the same data, and time-based file removal may efficiently expire old events. If queries are mostly point misses across all retained history, the same number of overlapping runs can cause more filter checks and candidate reads. Workload shape changes the preferred layout.
Now consider a small frequently overwritten key set. Compaction can discard many obsolete versions, reducing retained bytes and lookup work. However, if long snapshots pin those versions, expected reclamation may not occur. A configuration chosen from overwrite rate alone can disappoint because visibility retention blocks the optimization. A realistic test includes snapshot lifetimes and history features.
RocksDB’s compaction documentation describes several policy families. The source-specific fact is that those policies impose different shapes on runs and overlaps. The analysis here is conditional: a lower write-amplification shape can be attractive for sustained ingestion, while lower read and space amplification can justify additional rewriting for another workload. RocksDB compaction policies
Large-value separation adds another collector
Suppose sorted metadata stores a 24-byte key/reference entry instead of a 4 KiB value. Compaction can move the small entry while leaving the large value in a value log. Across several levels this can save substantial rewriting. A point read now follows the reference, potentially adding I/O if the value is not cached. Sequential access locality depends on how references and values are arranged.
Overwrites leave obsolete value-log regions. Garbage collection identifies segments with enough dead bytes, copies surviving values, updates their references safely, and eventually reclaims old segments. Publishing the new reference before its value is durable risks data loss. Reclaiming the old segment while readers still use it risks invalid reads. The same publication and lifetime obligations reappear in a different structure.
The separation can therefore help when saved value rewriting exceeds added indirection and collection costs. It can hurt for tiny values or workloads already well served by sequential compacted files. An engine designer should draw both maintenance loops—sorted-run compaction and value-log collection—before claiming that one was removed.
A tombstone-removal trace exposes the hidden read source
before compaction:
newer file A: K -> DELETE at sequence 80
older file B: K -> VALUE at sequence 60
unsafe output:
remove DELETE from A, leave B untouched
current lookup reaches B -> deleted value reappears
safe decision requires proof:
no required snapshot needs an older state
no retained lower-priority source can expose the old value
distributed repair rules, if any, also permit removalThe trace is a local correctness counterexample. Age alone cannot justify dropping the deletion marker when an older source remains visible. A complete compaction can remove both records if the relevant snapshot and source-set proof holds. If it only compacts A while B lies outside the selected input range, it needs another basis for proving B cannot contain the key.
Read amplification can be expressed as candidate file or block work per logical lookup, while space amplification compares retained bytes with an explicitly chosen live-data baseline. For example, 150 GB retained for 100 GB of live logical data gives a 1.5 ratio under that boundary. Including logs or excluding compression changes the meaning, so the boundary belongs beside the number. Those metrics complement the earlier write-amplification calculation and expose why a policy that saves writes may retain more data or perform more read checks.
Case connection: a storage library supplies one layer
RocksDB documents an LSM-oriented embedded storage engine with configurable compaction and write-stall behavior. Its library interface can be used inside a larger database. The larger system still decides distributed ownership, replication, client protocol, and application guarantees.
The interpretation is that LSM mechanisms are reusable building blocks, not a complete distributed architecture. Two products using related storage ideas can make different decisions about transactions, topology, and acknowledgment. Their workload performance can diverge because those other layers alter the critical path and maintenance obligations.
Design conclusion
An LSM design is sustainable when its background work fits the long-term resource budget under the required visibility and retention contracts. Evaluate it after enough time for flushing, compaction, deletion, and snapshots to matter. Compare total cost rather than only the foreground mutation path.
Lesson 12 extends the access-path discussion to structures optimized for particular predicates and workloads. Those structures also trade candidate reduction against maintenance, memory, and result guarantees.