What is an LSM-Tree and How Does it Handle Writes?
Learn how LSM-trees buffer writes in memory, flush to sorted SSTables, and use compaction to power write-heavy databases.
Expected Interview Answer
A Log-Structured Merge-tree (LSM-tree) is a storage engine design that turns random writes into fast sequential appends by first buffering writes in an in-memory sorted structure (the memtable) and a write-ahead log, then periodically flushing that structure to disk as an immutable sorted file, later merging those files together in the background through compaction.
Instead of updating a value in place on disk, which requires slow random-access writes, an LSM-tree appends every write to a write-ahead log for durability and inserts it into an in-memory sorted memtable. When the memtable fills, it is flushed to disk as a new immutable sorted string table (SSTable). Over time, many SSTables accumulate, so a background compaction process merges them, discarding overwritten and deleted entries and keeping the number of files a read must check manageable. Reads therefore may need to check the memtable and multiple SSTables from newest to oldest, which is why LSM-trees pair with Bloom filters per SSTable to skip files that provably do not contain a key. This design, used by RocksDB, Cassandra, and LevelDB, trades some read amplification and background compaction I/O for dramatically better write throughput than in-place B-tree updates.
- Converts random writes into fast sequential disk appends
- High write throughput, ideal for write-heavy workloads
- Immutable SSTables simplify concurrency and crash recovery
- Background compaction reclaims space from overwrites and deletes
AI Mentor Explanation
Think of a scorer who never erases and rewrites the master scorebook mid-innings; instead, every new event is jotted on a fresh notepad page, and once a notepad fills up, it is filed away as a sealed, dated bundle. Periodically, an assistant merges older bundles together, discarding superseded corrections, so the shelf of bundles stays manageable. An LSM-tree writes the same way: new data always goes to a fast in-memory notepad and later gets flushed and merged into sealed, sorted files rather than editing old files in place.
Step-by-Step Explanation
Step 1
Write to the log and memtable
Every write is appended to a write-ahead log for durability and inserted into an in-memory sorted memtable.
Step 2
Flush the memtable to an SSTable
When the memtable fills, it is written to disk as an immutable, sorted, Bloom-filter-backed SSTable.
Step 3
Serve reads across layers
A read checks the memtable, then SSTables newest-to-oldest, using Bloom filters to skip files without the key.
Step 4
Compact SSTables in the background
A background process merges SSTables, discarding overwritten or deleted entries to control read amplification.
What Interviewer Expects
- Understanding of the memtable, WAL, and SSTable flow
- Explanation of why sequential appends beat random in-place writes
- Awareness of compaction and its role in bounding read amplification
- Ability to name real systems using LSM-trees (RocksDB, Cassandra, LevelDB)
Common Mistakes
- Confusing an LSM-tree with a B-tree that updates pages in place
- Forgetting to mention the write-ahead log for durability
- Not explaining why compaction is necessary over time
- Ignoring the read-amplification trade-off from checking multiple SSTables
Best Answer (HR Friendly)
“An LSM-tree speeds up writes by buffering them in memory first and appending to disk in large sequential batches called SSTables, instead of updating data randomly in place. A background process later merges those batches together, cleaning up old and deleted data, which is why LSM-trees are popular in write-heavy databases like Cassandra and RocksDB.”
Code Example
-- Pseudocode representing an LSM-tree storage engine
function put(key, value) {
writeAheadLog.append(key, value);
memtable.insert(key, value); -- kept sorted in memory
if (memtable.size() > FLUSH_THRESHOLD) {
const sstable = memtable.flushToDisk(); -- immutable, sorted, Bloom-filtered
sstables.push(sstable);
memtable = newMemtable();
}
}
-- Background job runs periodically:
function compact() {
const merged = mergeSortedSStables(sstables, dropTombstonesAndOverwrites = true);
replaceOldSStablesWith(merged);
}
-- The equivalent SQL the application issues:
INSERT INTO KeyValueStore (key, value) VALUES ('user:42', 'Alice');Follow-up Questions
- What is write amplification in the context of LSM-tree compaction?
- How does a Bloom filter reduce read amplification in an LSM-tree?
- What is the difference between size-tiered and leveled compaction?
- Why do LSM-trees favor write throughput over read latency compared to B-trees?
MCQ Practice
1. What does an LSM-tree write first when a new key-value pair arrives?
Writes are appended to a durable log and inserted into the sorted in-memory memtable before ever touching an SSTable.
2. What is the purpose of compaction in an LSM-tree?
Compaction merges accumulated SSTables, reclaiming space and bounding how many files a read must check.
3. Why do LSM-trees generally achieve higher write throughput than in-place B-tree updates?
Buffering writes and flushing them as sequential sorted files avoids the costly random disk seeks that in-place updates require.
Flash Cards
What is an LSM-tree? — A storage engine that buffers writes in memory and flushes them as immutable sorted files, merged later by compaction.
What is a memtable? — The in-memory sorted structure that receives new writes before they are flushed to disk.
What is an SSTable? — An immutable, sorted, on-disk file produced when a memtable is flushed.
Why does compaction matter? — It merges SSTables and removes stale data, keeping read amplification and disk usage bounded.