What is Space Amplification in Storage Engines?
Learn what space amplification is, why LSM-trees accumulate stale data and tombstones, and how compaction reclaims wasted disk space.
Expected Interview Answer
Space amplification is the ratio between the actual disk space a storage engine consumes and the size of the logical, deduplicated data it is meant to represent, and it grows because storage engines keep stale and deleted versions of data around until compaction or garbage collection removes them.
In an LSM-tree, every update or delete is written as a new immutable record rather than overwriting in place, so an old value, a newer overwritten value, and even tombstones marking deletions can all sit on disk simultaneously for the same logical key until compaction merges and discards the obsolete versions. The longer compaction is deferred (to save write I/O and reduce write amplification), the more obsolete data piles up and the higher the space amplification climbs. B-tree engines have lower baseline space amplification since updates overwrite in place, but they still waste space from page fragmentation and reserved free space in partially filled pages. Tuning space amplification means choosing a compaction strategy and trigger threshold that reclaims stale data often enough to bound wasted disk, without compacting so aggressively that write amplification and I/O cost become unacceptable.
- Understanding it lets teams provision disk correctly instead of being surprised by wasted space
- Tuning compaction thresholds directly controls how much stale data accumulates
- Tombstone and TTL policies can be tuned to reclaim deleted-data space faster
- It is one leg of the RUM conjecture, so tuning it explicitly trades off against read and write cost
AI Mentor Explanation
Space amplification is like a scoring room that keeps every crossed-out and corrected scoresheet from the whole tournament instead of shredding old ones once a match is finalized. The room needs storage space for every superseded sheet, not just the one final scoresheet per match, so its total paper usage far exceeds what the tournament record actually needs. Periodically clearing out superseded sheets (compaction) reclaims that wasted space, but doing it too rarely lets the pile grow. That gap between space used and space logically needed is exactly space amplification.
Step-by-Step Explanation
Step 1
Writes accumulate as new immutable records
An LSM-tree never overwrites in place; every update or delete is a fresh append plus possibly a tombstone.
Step 2
Stale versions coexist on disk
Old values, newer overwrites, and deletion tombstones for the same key can all be present across memtable and SSTables at once.
Step 3
Space grows beyond logical data size
Actual disk usage includes all that stale data, so it exceeds the size of the deduplicated, current dataset — the space amplification ratio.
Step 4
Compaction reclaims space
Merging SSTables discards obsolete versions and expired tombstones, shrinking disk usage back toward the logical size, at the cost of extra write I/O.
What Interviewer Expects
- Defines space amplification as actual disk usage divided by logical (deduplicated) data size
- Explains why LSM-trees accumulate stale versions and tombstones before compaction
- Mentions B-trees have lower baseline space amplification but still waste space via page fragmentation
- Connects the metric to the RUM conjecture trade-off against read and write amplification
Common Mistakes
- Confusing space amplification with replication factor or backup storage overhead
- Assuming deletes free space immediately (tombstones actually add data until compacted away)
- Not mentioning the write-amplification cost of compacting more aggressively to reduce space amplification
- Treating it as a fixed property rather than something tunable via compaction strategy and TTLs
Best Answer (HR Friendly)
“Space amplification is how much extra disk space a database uses compared to the actual size of your data. Because many databases write new copies instead of overwriting old ones, and mark deletions with special markers rather than removing them instantly, old and obsolete data can pile up until a background cleanup process merges everything and reclaims that wasted space.”
Code Example
def space_amplification(sstable_sizes_bytes, logical_dataset_bytes):
"""sstable_sizes_bytes: sizes of all on-disk SSTables, including
stale overwritten versions and delete tombstones not yet compacted.
logical_dataset_bytes: size of the current, deduplicated key set."""
total_disk_bytes = sum(sstable_sizes_bytes)
if logical_dataset_bytes == 0:
return 0.0
return total_disk_bytes / logical_dataset_bytes
# Example: 40 GB of physical SSTables representing 10 GB of live,
# deduplicated data -> a space amplification factor of 4.0.
# amp = space_amplification([25e9, 10e9, 5e9], 10e9) # -> 4.0
# Running compaction merges and drops stale/tombstoned records,
# pulling total_disk_bytes back down toward logical_dataset_bytes.Follow-up Questions
- How do delete tombstones temporarily increase space amplification before compaction removes them?
- Why do B-tree engines generally have lower space amplification than LSM-trees, and what still wastes space in a B-tree?
- How would you tune a compaction trigger threshold to bound space amplification without hurting write throughput?
- How does TTL-based expiration interact with space amplification in a time-series or cache workload?
MCQ Practice
1. Space amplification is best defined as which ratio?
Space amplification compares real disk usage, including stale and unmerged data, to the true logical size of the dataset.
2. In an LSM-tree, why does deleting a key not immediately reduce space amplification?
A tombstone is a new record marking a key as deleted; it adds data on disk and only reclaims space once compaction discards it along with the obsolete value.
3. What is the typical trade-off when reducing space amplification via more frequent compaction?
More frequent compaction reclaims stale space faster but rewrites data more often, raising write amplification and background I/O cost.
Flash Cards
What is space amplification? — The ratio of actual disk space used to the logical, deduplicated size of the data.
Why does it happen in LSM-trees? — Updates and deletes are appended as new records, so stale versions and tombstones coexist with current data until compaction merges them away.
How is it reclaimed? — Compaction merges SSTables, discarding obsolete versions and expired tombstones, at the cost of extra write I/O.
Do B-trees have space amplification? — Yes but generally lower — updates overwrite in place, though partially filled pages and fragmentation still waste some space.