Wait, What?
Some databases become fast at writing by refusing to update most on-disk data in place.
Instead of repeatedly seeking to old locations, a log-structured merge-tree buffers new writes in memory, flushes sorted immutable files and repairs the growing collection later through background compaction. That simple idea creates a powerful systems algorithm—and a three-way tension among write amplification, read amplification and space amplification.
An LSM tree is therefore not merely “a database data structure.” It is a sequence of algorithms coordinating memory, sorted runs, filtering, merging, deletion markers, scheduling and storage devices.
Quick Answer
Learn LSM-tree algorithms through the route append-oriented writes → in-memory memtable → durability log → sorted flush → immutable SSTables → lookup across runs → Bloom filters → tombstones → compaction → size-tiered versus leveled organisation → read/write/space amplification → compaction debt → cache and filter budgets → workload-aware tuning → professional storage-engine diagnosis. A beginner should be able to simulate writes, flushes and reads across two SSTables. A professional should be able to explain why a chosen compaction policy helps one workload while increasing another form of amplification.
1. Start With the Problem: Random Writes Are Expensive
If every logical update required locating and modifying an arbitrary on-disk page immediately, the storage engine would perform many small writes and coordination steps. LSM designs transform much of that activity into sequential or batched work.
2. The Memtable Is the First Sorted State
New key-value updates enter an in-memory structure called a memtable. Implementations vary, but the important learner model is that the memtable supports fast updates while maintaining enough order to later produce a sorted on-disk run.
Apache Cassandra describes the write path as commit log plus memtable, followed by flushing immutable SSTables: Cassandra Storage Engine.
3. The Commit Log Solves a Different Problem: Durability
Memory is fast but volatile. A write-ahead or commit log records mutations durably so the memtable can be reconstructed after a crash. The memtable is primarily about efficient organisation; the log is about recovery.
4. Flushing Turns Mutable Memory Into an Immutable Sorted File
When a memtable reaches a threshold, it is written to storage as a sorted immutable table, commonly called an SSTable. Immutability simplifies concurrent reads and sequential writing, but it means updates do not overwrite old versions immediately.
5. One Logical Key Can Exist in Several Physical Files
Suppose key K was written Monday, updated Tuesday and deleted Wednesday. Those events may live in different immutable runs. A read must determine which visible version is newest while respecting deletion markers and consistency rules.
6. Reads Search From Newer State Toward Older State
A typical point lookup checks mutable memory first, then immutable in-memory state if present, then candidate SSTables from newer to older levels or runs. Indexes and filters reduce how many files require expensive inspection.
7. Bloom Filters Avoid Many Unnecessary File Reads
A Bloom filter can say “definitely not here” or “possibly here.” LSM engines exploit that asymmetry to skip SSTables that cannot contain the requested key.
The existing How to Learn Bloom Filters article owns probabilistic membership. LSM trees add the engineering question of how filter memory should be distributed across levels and workloads.
8. False Positives Become Read Amplification
If a filter says an absent key may be present, the engine performs extra lookup work. Across many levels or runs, those false positives accumulate into real I/O and CPU cost.
The Monkey research line formalises the interaction among filters, merge policy, memory and lookup cost: Monkey: Optimal Navigable Key-Value Store.
9. Tombstones Represent Deletion Without Immediate In-Place Removal
Deleting a key commonly writes a tombstone rather than editing every older SSTable immediately. Reads interpret the tombstone as newer evidence that suppresses older values.
10. Tombstones Explain Why Compaction Is Necessary
Old values and deletion markers accumulate because immutable files cannot be rewritten cheaply one record at a time. Compaction periodically merges sorted runs, discards obsolete versions when safe and rewrites live state into a cleaner shape.
Cassandra’s current compaction overview describes this role directly: Compaction overview.
11. Compaction Is Merge Sort as a Storage Service
Because SSTables are sorted, multiple runs can be merged in key order. The algorithm can resolve newer versus older versions while streaming through the inputs.
The existing How to Learn Sorting Algorithms article owns general sorting. LSM compaction turns merging into a continuous background maintenance workload constrained by storage bandwidth.
12. Write Amplification Means One Logical Write Causes Multiple Physical Writes
A key may be flushed once, then rewritten repeatedly as compactions move it through the structure. The ratio between physical bytes written and logical bytes accepted is a central LSM metric.
Cassandra explicitly notes that compaction creates write amplification because data is rewritten during merges.
13. Read Amplification Means One Logical Read Consults Multiple Structures
Point lookups may inspect memory, indexes, filters and several SSTables. Range queries may merge overlapping runs. The number of structures touched contributes to read amplification.
14. Space Amplification Means Old and New Versions Coexist
During normal operation and especially during compaction, obsolete data and temporary outputs can coexist with live data. A database may therefore require substantially more physical space than the live logical dataset.
15. You Cannot Optimise All Three Amplifications Independently
A strategy that reduces read amplification may rewrite data more aggressively. A strategy that minimises rewriting may leave more overlapping runs for reads. A strategy that limits temporary space may alter compaction granularity.
Professional tuning is therefore multi-objective, not a search for one globally minimal number.
16. Size-Tiered Compaction Groups Similar-Sized Runs
Size-tiered strategies accumulate runs of comparable size and merge them into larger runs. This can provide strong write behaviour because data is not continuously rewritten into tightly controlled levels, but reads may need to consult more overlapping runs.
ScyllaDB documents size-tiered, leveled, incremental and time-window strategies and their workload trade-offs: ScyllaDB Compaction.
17. Leveled Compaction Controls Overlap More Aggressively
Leveled strategies organise SSTables into levels with bounded size growth and limited overlap in higher levels. Point reads can inspect fewer candidate files, but maintaining those level invariants generally rewrites data more often.
Apache Cassandra describes the non-overlapping property and read-oriented motivation of leveled compaction: Leveled Compaction Strategy.
18. Time-Window Compaction Uses Time as a Structural Hint
Time-series workloads often have a special property: old windows become immutable and eventually expire together. Time-window strategies exploit that structure so old data is not repeatedly mixed with current writes.
19. Compaction Debt Is Deferred Work
If writes arrive faster than compaction can reorganise them, pending merge work grows. Latency may look excellent temporarily while the engine quietly accumulates debt that later consumes I/O, CPU and disk space.
This is a useful systems lesson: background maintenance is still part of the write cost even when the client request has already returned.
20. Compaction Scheduling Is an Algorithm Too
The engine must choose which files to merge, when to start, how much bandwidth to consume, how many compactions to run concurrently and how to avoid starving foreground reads or writes.
21. File Size and Level Ratio Change the Shape of the System
Larger files reduce metadata and file-count overhead but make individual compactions coarser. Smaller files offer finer scheduling but create more indexes, filters and open-file work. Level growth factors similarly trade tree depth against rewrite behaviour.
22. Cache Memory, Filter Memory and Memtable Memory Compete
A fixed memory budget can be spent on larger memtables, more block cache, richer indexes or better Bloom filters. Improving one path can reduce memory available to another.
The Monkey work is especially useful here because it treats filter allocation and LSM shape as a joint optimisation problem rather than independent knobs.
23. SSDs Change Constants, Not the Basic Trade-Offs
Flash reduces seek penalties compared with spinning disks, but write endurance, bandwidth, garbage collection, parallelism and tail latency still matter. Modern LSM systems therefore remain sensitive to write amplification and background I/O even on fast storage.
24. Range Queries and Point Queries Want Different Things
Point lookups benefit strongly from accurate filters and low file overlap. Range scans benefit from long sorted runs and sequential access. A workload dominated by one can justify different LSM choices from a workload dominated by the other.
25. Hot Keys Break Uniform Workload Assumptions
A small fraction of heavily updated or frequently read keys can dominate caches, filters and compaction behaviour. Time-aware or workload-aware strategies exist because recency and access frequency are rarely perfectly uniform.
RocksDB discusses the practical difficulty of identifying hot and cold data in tiered storage: Time-Aware Tiered Storage in RocksDB.
26. B+ Trees and LSM Trees Optimise Different Update Paths
B+ trees update page-oriented structures and are excellent for many read-heavy and transactional workloads. LSM trees buffer and merge writes. Neither structure dominates every workload.
The existing How to Learn B+ Tree Algorithms article owns page-oriented tree indexing. This article owns log-structured merging and compaction.
27. Common Learning Failure States
- Thinking an LSM tree is simply a tree of files.
- Confusing the commit log with the memtable.
- Assuming SSTables are updated in place.
- Forgetting that one key may exist in multiple runs.
- Treating tombstones as immediate physical deletion.
- Calling compaction optional maintenance rather than part of correctness and performance.
- Optimising write latency while ignoring compaction debt.
- Comparing compaction strategies using only throughput.
- Ignoring read, write and space amplification as a coupled system.
- Assuming SSDs eliminate storage-engine trade-offs.
28. A Beginner-to-Professional Learning Ladder
- Level 1: write keys into a tiny memtable and flush a sorted SSTable.
- Level 2: read a key that exists in both a newer and older file.
- Level 3: add a tombstone and determine the visible result.
- Level 4: use Bloom filters to skip irrelevant files.
- Level 5: manually compact two sorted runs.
- Level 6: compare size-tiered and leveled layouts.
- Level 7: calculate simple read, write and space amplification examples.
- Level 8: reason about memtable, cache and filter memory budgets.
- Level 9: model compaction debt under sustained writes.
- Level 10: diagnose a production storage engine using latency distribution, amplification, pending compaction, cache hit rate and device bandwidth together.
29. Teach the Immutable-Run Story With Paper Cards
Write key-value pairs on cards. Build one sorted run, then create a newer run containing updates and tombstones. Ask the learner to answer reads before any compaction occurs. Then merge the runs physically and compare the logical answer before and after.
This prediction-first progression aligns with PRIMM: Using PRIMM to teach programming.
30. Fade Worked Compactions Into Independent Reasoning
Initially annotate which version wins, which tombstone is safe to discard and where each output key goes. Then remove the annotations and ask the learner to reconstruct the merge decisions. Finally change the workload from point reads to write-heavy time series and ask which strategy should change.
Faded worked examples combined with metacognitive scaffolding have empirical support in programming problem solving: Shin et al. (2023).
31. Immediate, Delayed and Transfer Checks
- Immediate: trace one write, flush, read and compaction cycle.
- Counterexample: create a workload where lower read amplification causes higher write amplification.
- Explain: distinguish memtable, commit log and SSTable roles.
- Delayed: reconstruct why tombstones and compaction are needed.
- Transfer: choose between leveled, size-tiered and time-window organisation for contrasting workloads.
- Professional: explain a latency spike using compaction debt, amplification, device bandwidth and cache evidence together.
32. AI Assistance Boundary
AI can generate toy SSTable states, simulate merge sequences, explain documentation and compare compaction strategies. The learner should still be able to determine the visible value of a key, trace a compaction, identify the relevant amplification trade-off and verify configuration claims against authoritative engine documentation.
Professional Direction
Advanced study includes partitioned memtables, skip-list and tree memtables, block indexes, fence pointers, prefix compression, partitioned Bloom filters, universal compaction, leveled compaction, tiered storage, compaction picking, tombstone safety, snapshots, write stalls, rate limiting, subcompactions, key-range overlap, compression, WAL design, direct I/O, NVMe parallelism, zoned storage, learned filters and research systems that co-optimise filters and merge policy.
Algorithm-learning rule: when an LSM-backed store looks fast, ask which work was completed synchronously, which work was deferred into compaction, how many versions and runs reads must consult, how much data is rewritten, and whether the storage engine is accumulating debt faster than it can repay it.
eduKate Sengkang 