Why is mathematics important in an LSM tree? A log-structured merge tree reorganises the geometry of database work. New writes first land in memory and sequential files; background compaction later merges sorted runs. That design can make ingestion fast, but it creates measurable read, write and space amplification.
The useful lesson is not that one storage engine is universally best. It is that performance comes from conservation equations, sorted order, growth ratios, probability and workload-specific objectives. A student who can trace one key through memory, files and compaction can see how abstract mathematics becomes storage behaviour.
Why an LSM Tree Exists
Updating a large on-disk sorted structure in place can cause random I/O. An LSM design batches writes in memory, records them in a log for recovery, then flushes an immutable sorted table to storage.
Sequential work is easier for storage
Writing a contiguous file usually needs fewer seeks and less metadata churn than editing many distant pages. Even on solid-state storage, batching and sequential patterns improve throughput and device efficiency.
Deferred work does not disappear
The system has postponed organisation. Multiple immutable files can overlap in key range, contain older versions and retain deletion markers. Compaction reads and merges them so later reads inspect fewer places and obsolete records can be dropped safely.
The tree is a hierarchy of runs
In a leveled design, newer data sits near Level 0 and progressively larger levels hold older, more organised runs. Adjacent level sizes often follow a fanout ratio T. If one level targets 10 GB and T = 10, the next targets about 100 GB.
Quick Reading Routes
- Follow one write through WAL, memtable, flush and sorted files.
- Calculate read, write and space amplification.
- Compare leveled, tiered, universal and FIFO compaction.
- Explore tombstones, Bloom filters, stalls and SSD endurance.
- Finish with student investigations, parent guidance and FAQs.
The Write Path Creates Ordered Batches
A new key–value pair is appended to a write-ahead log and inserted into an in-memory ordered structure called a memtable. When the memtable reaches a threshold, it becomes immutable and is flushed as a sorted-string table, often called an SST.
Durability and organisation are separate
The log protects recent writes if the process crashes. The memtable provides a queryable ordered view. The SST persists the batch in a format designed for range lookup and later merging.
Flush size sets frequency
If a workload ingests 240 MB per minute and each memtable flushes at 120 MB, the average system creates two flushes per minute. Bursts and compression change the exact timing, but the ratio gives a capacity baseline.
More memory reduces flush frequency, not total data
Doubling memtable size can create fewer, larger files. It may improve merge efficiency but increases recovery work and memory use. The same logical bytes still need durable storage.
Sorted Runs Enable Merge Algorithms
Two sorted files can be merged in linear time with two cursors. Compare the current keys, emit the smaller one, and advance. When keys match, version rules choose the visible record.
Linear means proportional to input size
Merging files with a and b entries requires at most on the order of a + b comparisons. It does not require sorting all a + b entries from scratch.
Versions require an order
A key can occur in several runs. Sequence numbers or timestamps distinguish newer from older versions. A merge must preserve the newest visible value while respecting snapshots that may still need an earlier version.
Range partitioning permits parallelism
If output key ranges do not overlap, several compaction jobs can process different regions concurrently. Poor partition boundaries or hot keys can create imbalance even when total bytes appear even.
Read Amplification Counts Places Consulted
A point lookup checks the memtable, immutable memtables and some number of SSTs. Read amplification is the extra storage work compared with an ideal single lookup.
Level 0 can overlap
Files flushed independently may cover similar key ranges. A missing key might require checking every overlapping Level-0 file. Higher levels in a leveled design usually maintain non-overlapping ranges, so at most one file per level is a candidate after index search.
A simple upper-bound example
Suppose there are 8 Level-0 files and 5 non-overlapping lower levels. Without filters or cached indexes, an absent point lookup could consult up to 13 files. A present key may be found earlier, so this is not the average.
Range queries behave differently
A long range scan may need data from many files and merge versions in order. A design optimised for absent point lookups is not automatically best for scans.
Bloom Filters Reduce Negative Reads
A Bloom filter can say “definitely not present” or “possibly present.” Each SST may carry one, allowing the engine to skip files that cannot contain a queried key.
False positives still cause reads
If ten candidate files each have false-positive probability p = 1%, an absent query produces an expected 10 × 0.01 = 0.1 unnecessary file probes under a simple independence model. The probability of at least one false positive is 1 − 0.99^10, about 9.56%.
Filters consume memory
More bits per key lower false positives but use cache that could hold indexes or data blocks. The best allocation depends on query mix and storage latency.
This article owns a different intent
The mathematics of the filter itself is explained in Bloom Filters, Hash Functions, False Positives and Memory Efficiency. Here the filter is one component in a larger storage-engine cost model.
Write Amplification Measures Physical Work
Write amplification factor, or WAF, is physical bytes written to storage divided by logical bytes written by the application.
A worked ratio
If applications write 100 GB while flushes and compactions cause 650 GB of device writes, WAF = 650 / 100 = 6.5. The ratio must specify whether the WAL, metadata and replication are included.
Rewriting old data drives amplification
In leveled compaction, a small incoming run may overlap a larger range in the next level. Merging rewrites existing records even when their values have not changed.
Compression changes byte accounting
Logical values might compress by 2:1. Measuring compressed device bytes against uncompressed application bytes can make WAF look lower than a count using the same representation in numerator and denominator. State the convention.
Space Amplification Measures Temporary and Retained Copies
Space amplification is physical storage occupied divided by live logical data size. Old versions, tombstones, overlapping runs and temporary compaction output increase it.
Compaction needs working space
If a 300 GB run is merged with 80 GB of overlapping input, the old files may remain until a new 380 GB output is complete and installed. Peak temporary space can be far larger than steady state.
Snapshots delay reclamation
A long-running snapshot may need older versions. Compaction cannot discard them merely because a newer version exists. Correctness constraints therefore affect disk capacity.
Free space is a reliability reserve
Running storage at 99% occupancy leaves little room for compaction output, recovery or burst growth. Capacity plans should model peak working space, not only live data.
Leveled Compaction Trades Writes for Read Organisation
Classic leveled compaction maintains approximately one sorted run per level beyond Level 0. Files within a level generally have non-overlapping key ranges.
Fanout creates geometric capacity
With base level size C and fanout T, level i has target size near C × T^i. Total capacity is a geometric series. Increasing T reduces the number of levels for a fixed database size but changes overlap and merge work.
Fewer runs help reads
Point lookups check fewer runs, and range scans merge fewer sources. Space amplification can also be controlled because old overlapping files are replaced promptly.
Existing bytes are rewritten
The cost is higher write amplification. RocksDB's compaction documentation describes leveled compaction as minimising space amplification at the expense of read and write amplification.
Tiered Compaction Trades Read and Space for Fewer Rewrites
Tiered designs keep several sorted runs of similar size, then merge them into a larger run.
New data is rewritten less often
The merge can avoid repeatedly rewriting the largest run for each smaller arrival. This reduces write amplification and can support heavy ingestion.
Reads inspect more runs
Because key ranges overlap across runs, a point lookup or scan may consult more structures. Bloom filters and caching become more important.
Peak space can be high
During a major merge, input runs and output coexist. A system with 1 TB of live data may need hundreds of extra gigabytes temporarily, depending on policy.
Universal and FIFO Policies Serve Different Workloads
RocksDB's universal compaction is a tiered-style policy that can lower write amplification while accepting more read and space amplification. FIFO policy can simply remove oldest files for cache-like data.
FIFO changes semantics
Dropping the oldest file is suitable only when age-based disappearance is acceptable. It is not a general database deletion strategy.
Policy names are not guarantees
File-size thresholds, overlap, compression, delete handling and workload skew all affect realised amplification. Measure the running shape rather than inferring performance from the label alone.
Official implementation evidence
The RocksDB architecture overview explains memtable flushes, Level-0 files, compaction styles, background work and write stalls. These implementation details ground the mathematical model.
A Complete Leveled-Capacity Example
Let a storage engine flush 256 MB files. Level targets are 1 GB, 10 GB, 100 GB and 1 TB, using fanout near 10.
How many files?
At 256 MB each, a 1 GB level holds about 4 files, 10 GB about 40, 100 GB about 400 and 1 TB about 4,000, ignoring variable output sizes and decimal/binary unit differences.
Point-query candidates
Non-overlapping files let an index select at most one file in each lower level. Level 0 might have six overlapping files. A negative query has up to ten candidates before filters: six at L0 and one in each of four lower levels.
Growth adds a level stepwise
The number of levels grows logarithmically with database size. A tenfold capacity increase adds roughly one level at the same fanout. Read path length changes slowly, while compaction volume can still be large.
Tombstones Represent Deletion Without Random Removal
Deleting key K writes a tombstone saying that earlier values are no longer visible. The engine cannot simply remove K from every immutable file immediately.
The marker must outrank old values
A read that sees an older value and a newer tombstone returns absent. Compaction can later remove both when no lower level or snapshot still needs the history.
Tombstone age is not sufficient alone
A marker may be old yet necessary if an unvisited lower level still contains the value. Safe deletion depends on coverage, sequence bounds and snapshot rules.
Deletion-heavy workloads create debt
Until compaction catches up, tombstones consume space and query work. Monitoring their distribution helps explain why logical deletion does not instantly free bytes.
Update Skew Changes Compaction Cost
Not every key is updated equally. A small hot range can receive most writes.
Local overlap can help or hurt
Some-to-some leveled compaction rewrites only files overlapping the selected key range. Concentrated writes may stop at a level large enough to contain the working set, reducing work compared with uniform updates.
Hot partitions create imbalance
One compaction worker or device region can become saturated while others stay idle. Average throughput hides the bottleneck.
Measure by key range
Per-level totals are useful, but heat maps of bytes written and compaction time by range reveal whether one tenant or prefix dominates.
Compaction Debt Is a Queue
Flushes create future merge work. Background compaction services that work. If incoming compaction demand exceeds capacity, debt grows.
Logical write rate is not compaction demand
At logical rate λ and expected compaction WAF component A, background device bandwidth demand is roughly λ × A. A 100 MB/s ingest with 5× compaction amplification needs about 500 MB/s of compaction writes, plus reads and flushes.
Headroom prevents stalls
If available compaction bandwidth barely matches average demand, any burst, device slowdown or large merge builds debt. Sustainable design keeps spare capacity.
Stall thresholds apply backpressure
When Level-0 files or pending bytes exceed limits, the engine slows or stops writes so background work can recover. A write stall is therefore a control response, not always a mysterious failure.
Compaction Scheduling Is an Optimisation Problem
Several files may be eligible. The scheduler chooses work under limits on threads, I/O bandwidth and temporary space.
Priorities encode objectives
A policy can reduce Level-0 overlap, reclaim deletes, lower space amplification or compact a hot range. Improving one objective can postpone another.
Large jobs have long tails
A 500 GB merge may be efficient per byte but occupy resources for hours. Splitting work improves responsiveness but may increase repeated overlap and metadata.
Preemption is not free
Stopping and restarting compaction can waste already-read data or temporary output. Scheduling should account for job progress and downstream risk.
SSD Endurance Connects WAF to Hardware
Flash cells tolerate a finite number of program–erase cycles. Storage-engine writes add to the device's own internal write amplification.
Amplifications can multiply
If the database writes 5 physical bytes per logical byte and the SSD internally writes 1.4 NAND bytes per host byte, total NAND work is approximately 7 bytes per logical byte under that simplified model.
Endurance forecasting needs units
A device rated for 3 PB written and receiving 2 TB of host writes per day has a nominal 1,500-day write budget before other factors, because 3 PB / 2 TB ≈ 1,500 using consistent decimal units. Workload growth and vendor definitions matter.
Wear levelling is related but separate
The SSD controller distributes erases across flash blocks. The storage engine controls logical layout and compaction. Both layers influence total work but expose different measurements. Read Solid-State Drives, NAND Pages, Wear Levelling and Error Correction for the device layer.
Compression Alters Several Objectives
Compression reduces stored bytes and device writes but costs CPU and may make small reads decompress a larger block.
Level-specific choices can help
Newer levels are rewritten more often, so fast compression may be preferable. The bottom level holds most data and changes less, so stronger compression can save more space.
Compression ratio varies by data
Textual repetition, encoded images and encrypted values behave differently. A single global 3:1 assumption can misprice capacity.
CPU is part of the system budget
If compaction becomes CPU-bound, spare storage bandwidth cannot increase merge rate. Profile the limiting resource.
Cache and Filter Budgets Interact
Memory can hold data blocks, indexes, filters and memtables. Each allocation reduces another.
More memtable can delay flushes
This helps ingestion but may evict read cache. More Bloom-filter bits reduce negative I/O but also consume memory.
Marginal benefit guides allocation
Add memory where one extra megabyte prevents the most costly work. The answer changes with read miss cost, absent-query fraction and write bursts.
Static percentages are only starting points
Monitor cache hit ratios, filter usefulness, flush frequency and stall time. Reallocate when the workload changes.
Snapshots and Iterators Pin History
A snapshot promises a consistent view at sequence number S. Values newer than S must be ignored, while some older versions remain necessary.
Long-lived readers create retention cost
An analytical scan lasting hours can prevent compaction from discarding overwritten data. The reader uses no extra logical rows but increases physical space.
Cancellation policy is a product decision
A system may limit snapshot duration, move analytics to another copy or accept higher space. Correctness and user needs come before reclamation convenience.
Monitoring the Shape of the Tree
- Number and bytes of SSTs by level.
- Pending compaction bytes and estimated debt.
- Logical ingest, flush, compaction read and compaction write rates.
- Read, write and space amplification under a stated definition.
- Level-0 file count, stall duration and stall causes.
- Tombstones, obsolete versions, cache hits and Bloom-filter usefulness.
Ratios need time windows
WAF over one second can spike during a large merge even when weekly average is healthy. Use windows matched to capacity and endurance decisions.
Averages need tails
Median write latency can remain low while occasional stalls block a critical request. Report high percentiles and maximum stall duration with volume.
Four Workloads, Four Different Answers
The phrase “LSM tree performance” has no single value. Each workload assigns different importance to ingestion, point lookups, scans, deletion, recovery and device endurance.
Case 1: time-series ingestion
Sensors append timestamped records at high rate, and most reads cover recent time windows. Large sequential flushes are attractive. If keys arrive mostly in time order, range overlap may be predictable, and an age-based policy can expire whole old files when retention semantics allow it.
However, late-arriving records break perfect time ordering. Before using FIFO deletion, the system must define whether a late event belongs to the old window and whether removing a file can expose an earlier version.
Case 2: a read-heavy catalogue
A product catalogue serves many absent and present point lookups while receiving modest updates. Leveled compaction, indexes, block cache and Bloom filters may deserve more resources because query latency dominates. The extra rewrite cost can be acceptable if SSD endurance and background bandwidth remain within budget.
Case 3: an update-heavy counter store
The same keys change repeatedly. New versions and tombstones overlap a small hot range. Average database size hides concentrated compaction work. Partitioning hot keys, changing merge semantics or using an in-memory aggregation layer may matter more than increasing global background threads.
Case 4: a temporary cache
The dataset is reproducible and old records can be discarded by file age. FIFO-style file deletion may avoid expensive merging. That would be inappropriate for a database where an old value could reappear after a newer tombstone file was dropped.
These cases show why a storage recommendation must state the workload and correctness requirement. A benchmark victory under one mixture is not a universal ranking.
A Storage-Budget Calculation
Suppose an application writes 2 TB of logical new data per day. Compaction causes a storage-engine write amplification of 8, and the filesystem plus device adds a measured factor of 1.3.
Estimate physical writes
Approximate device writes are 2 × 8 × 1.3 = 20.8 TB per day. Over a 30-day month, that is about 624 TB. The multiplication is a model; compression, discarded overwrites and measurement boundaries can make actual counters differ.
Add burst headroom
If daily writes arrive unevenly, average bandwidth is insufficient. During a four-hour peak that contains half the day's logical writes, the engine receives 1 TB in four hours, 250 GB per hour. At amplification 8, compaction-related engine output averages 2 TB per hour during that interval before other effects.
Calculate free-space reserve
Assume live data is 12 TB, normal space amplification is 1.2 and one large compaction temporarily needs another 1.5 TB. Baseline occupied space is 14.4 TB; the job can raise it near 15.9 TB. A 16 TB volume leaves almost no operational margin for estimation error, snapshots or recovery.
Do not confuse endurance ratings
Drive endurance specifications have conditions, units and warranty periods. Convert units consistently and use device telemetry rather than promising life from one calculation. Temperature, write size, compression and firmware behaviour all matter.
Reading the Compaction Dashboard as a System
A collection of counters becomes useful when linked by causal hypotheses.
Start with incoming work
Measure logical write bytes, flush bytes, files created and distribution by key range. This describes demand entering the storage engine.
Follow queued work
Pending compaction bytes estimate debt. A rising queue alongside sustained background utilisation suggests demand exceeds service. A flat queue during stalls may instead mean admission control is successfully holding new work back.
Observe the service rate
Track bytes read and written by compaction, job duration, concurrency and device utilisation. More threads can lower queue time until CPU, disk or write bandwidth saturates; after that they compete.
Check user consequences
Link tree shape to write stalls, read latency percentiles, cache misses and space alarms. A high byte counter is not automatically harmful if user objectives remain healthy and reserve capacity is adequate.
Inspect ranges, not only totals
One shard can carry most overlap while fleet averages look comfortable. Heat maps by key range or partition reveal whether rebalancing or key redesign is needed.
Designing a Compaction Experiment
A disciplined experiment changes one major factor at a time and preserves enough context to reproduce the result.
Define the logical workload
Record key distribution, value sizes, update-to-insert ratio, deletion rate, range-scan fraction and request concurrency. A phrase such as “database benchmark” is not enough.
Warm the system
An empty database has no old levels to rewrite. Run until level sizes and amplification stabilise, or explicitly label the test as growth-phase behaviour.
Compare equal outcomes
Two configurations should meet the same durability, correctness and latency objective. A configuration that drops writes or retains more obsolete data has not achieved the same result more efficiently.
Report distributions
Give median and tail latencies, amplification over the full interval, maximum space usage and stall duration. Averages can hide a five-minute freeze.
Repeat and randomise
Background scheduling and device garbage collection add noise. Repeat trials, vary ordering and report uncertainty. Do not select only the best run.
Deletion, Privacy and Retention
A logical delete creates a tombstone; it does not prove that all previous bytes vanished from every layer.
Define deletion scope
Data may remain in older SSTs, snapshots, replicas, backups, caches and device remapping. Each layer has a different retention and erasure mechanism.
Compaction enables reclamation
Once the engine can prove no older value or snapshot needs the record, compaction can omit it from new output. Old files must then be unreferenced and deleted. This is a lifecycle, not an instantaneous overwrite.
Encryption can change the strategy
Encrypting data with separable keys can support cryptographic erasure when destroying a key makes retained ciphertext unreadable. That claim still depends on key copies, backups and threat model.
Communicate accurately
An application should not promise immediate physical erasure merely because its API returned success. Engineering, policy and legal teams need the same definition of completion.
A Paper-and-Pencil Merge Investigation
Prepare three sorted runs: `[A1, C1, F1]`, `[A2, B2, E2]` and `[B3, D3, F3]`, where the number is the version and larger is newer. Merge them by key while retaining only the newest version when no snapshot needs an older one.
The visible result is A2, B3, C1, D3, E2 and F3. Count every input record read and every output record written. The merge reads nine logical records and writes six, so this one job performs fifteen record operations under that simplified counting rule. If a snapshot still needs version B2, output must retain more history.
Repeat with a tombstone for C at version 4. The tombstone cannot be discarded while C1 might exist below the merge's input range. This exercise makes the safety condition concrete: reclamation depends on what older data could still be visible, not only the tombstone's age.
Learners can also colour each source run, making rewrite frequency visible and comparing the extra work created by different merge groupings.
Common Misconceptions to Correct
“LSM trees eliminate random I/O”
They transform much foreground write work into sequential batches and background merges. Reads and metadata can still be random.
“Compaction is compression”
Compaction merges and reorganises runs; compression encodes bytes more compactly. A compaction may also compress output, but the concepts differ.
“Lower WAF is always better”
It may come with more read amplification, space, latency or complexity. Optimise the workload objective.
“A delete immediately frees storage”
It first writes a tombstone. Reclamation waits for safe compaction and snapshot rules.
“More background threads always fix stalls”
Threads can contend for device bandwidth and CPU. Identify the limiting resource.
“One benchmark predicts production”
Key distribution, value size, update skew, reads, snapshots, compression and device behaviour all change outcomes.
How Students Can Build Transferable Skill
Merge paper cards
Create two sorted decks of key–version cards. Merge them, keeping the newest visible value. Count comparisons.
Build a geometric level model
Choose base capacity and fanout. Calculate level sizes, total capacity and approximate number of levels for several database sizes.
Measure three amplifications
For a toy simulator, count logical bytes, physical writes, candidate reads and peak space. State each denominator.
Inject a burst
Increase flush creation above compaction service for ten intervals. Graph pending debt, then calculate net catch-up time after the burst.
Guidance for Parents and Teachers
Start with sorted revision piles
Imagine students place new flashcards in small sorted piles. Periodically merging piles creates a cleaner library but takes work. This makes deferred organisation visible.
Ask where the work moved
When a design makes writes fast, ask whether it moved cost to reads, background merging, memory or storage. This is a powerful systems habit.
Reward denominator discipline
“Amplification is six” is incomplete. Six physical write bytes per logical byte over which interval and including which layers?
Mathematics Learning in Singapore
The MOE secondary mathematics syllabuses emphasise reasoning, applications, modelling and communication. LSM trees connect geometric sequences, ratios, logarithmic growth, probability and rate equations in one authentic problem.
Use official SEAB documents for current cohort and examination information. This article shows mathematical transfer into computing; it does not create a school subject requirement or guarantee a career.
Did You Know?
The “merge” in LSM is not occasional housekeeping around the edge of the design. Sustained write throughput can depend directly on how quickly compaction completes.
A database may hold only 1 TB of live values yet need substantially more physical room during a major merge because old input and new output coexist until installation is safe.
Frequently Asked Questions
What mathematics is most useful for LSM trees?
Ratios, geometric sequences, logarithms, probability, sorting, queueing and optimisation.
What is an SST?
It is an immutable sorted table file containing keys, values or versions plus supporting indexes and filters.
Why compact immutable files?
To combine runs, reduce lookup work, reclaim obsolete versions and maintain the chosen level structure.
What is write amplification?
Physical storage bytes written divided by logical application bytes written, under a stated measurement boundary.
Why can writes stall?
Flushes may create merge work faster than background compaction can service it. Backpressure prevents unbounded debt.
Is leveled compaction always best?
No. It often improves read and space behaviour while increasing rewrites. Tiered or specialised policies suit other workloads.
Does learning LSM trees guarantee a storage career?
No. It develops useful reasoning alongside algorithms, operating systems, databases, hardware, testing and communication.
Useful Next Reading
- Read the official RocksDB compaction guide.
- Connect filters to Bloom Filters, False Positives and Memory Efficiency.
- Connect device endurance to Solid-State Drives, NAND Pages and Wear Levelling.
- Compare query cost with Database Query Planners, Cardinality Estimates and Join Costs.
Final Perspective
An LSM tree demonstrates a central truth of engineering mathematics: fast work is often deferred work. Sorted runs make merging efficient, geometric levels control growth, Bloom probabilities reduce unnecessary reads and queue equations reveal when compaction debt will become a stall.
The strongest question is not “Which compaction style is fastest?” It is “For this read–write mix, key distribution, device and retention rule, which policy places the acceptable cost in the acceptable place?” That question turns ratios into design judgement and helps students see that an optimisation is always an optimisation of something specific.