We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
2 system design questions lean on this idea. Each walks through the full answer.
System Design Masterclass · Database Fundamentals
Free preview: the first 2 parts of this 12-part lesson.
Already bought the course? Sign in to read the whole lesson.
this lesson is part of
System Design Masterclass
Unlock this lesson and the 751 other paid lessons
$25 once, by PayPal
See the System Design courseread the rest of this lesson in
System Design Masterclass
Unlock this lesson and the 751 other paid lessons
$25 once, by PayPal
See the System Design coursein Database Fundamentals
This lesson is part of the full System Design Masterclass. Unlock it along with 769 other lessons for a one-time payment.
One-time payment by card or PayPal
Get Lifetime AccessOne-time payment: UPI, card or netbanking
Get Lifetime Access18 Foundation lessons are free, no payment needed. Try them now
It is easy and good
“It is really nice and good Please join the course”
Think about your desk at the end of a busy workday. Papers everywhere, some relevant, some outdated, some duplicates. You were productive because you just kept dropping papers on the pile instead of filing them. But now finding anything is a nightmare.
LSM-tree databases (Log-Structured Merge trees) work the same way. They achieve blazing fast writes by dumping data into sorted files on disk, one after another. No in-place updates, no searching for the right spot. Just append and move on.
The problem: after thousands of these write batches, you have hundreds of files, many containing outdated or duplicate entries for the same key. Reading a single key might require checking dozens of files.
Compaction is the cleanup process. It merges multiple files into fewer, larger files, discarding outdated versions and tombstones along the way. It's the janitor that keeps the whole system from drowning in its own output.
Without compaction, LSM-tree databases would eventually grind to a halt. Read would increase linearly with the number of files, and storage would grow without bound.
To understand compaction, you need to know how data gets written in an LSM-tree:
Step 1. Memtable (in-memory): Writes go to an in-memory sorted structure (usually a red-black tree or skip list) called the memtable. This is where the speed comes from, writing to memory is microseconds.
Step 2. WAL (Write-Ahead Log): Simultaneously, the write is appended to a WAL on disk for durability. If the process crashes, the memtable can be rebuilt from the WAL.
Step 3. Flush to SSTable: When the memtable reaches a size threshold (typically 64MB), it's flushed to disk as an SSTable (Sorted String Table), an immutable, sorted file. Once written, an SSTable never changes.
Step 4. Accumulation: Over time, you accumulate many SSTables. Each represents a snapshot of writes during a specific time window. A key might appear in 5 different SSTables, each with a different value at a different timestamp.
The read problem: To find the current value for a key, the database must check the memtable, then the most recent SSTable, then the next, and so on, until it finds the key. Bloom filters help skip SSTables that definitely don't contain the key, but it's still slower than a single-file lookup.