advanced practice · implementation task
Build a memtable + SSTable flush
Implement an in-memory memtable that flushes to an immutable sorted file (SSTable). Support reads that merge memtable and SSTables; deletes as tombstones.
The mechanism
An LSM tree turns random writes into sequential ones: buffer writes in an in-memory memtable, flush to immutable sorted files (SSTables), and merge them in the background. Writes are fast; reads may touch several files (bloom filters help).
Expected evidence
Writes go to the memtable; reads see the latest value across files.
Try this drill in the practice workspace →
Hints when you need them
- SSTables are immutable and sorted.
- A read may need to check several files newest-first.
Watch for these mistakes
- Ignoring read amplification across SSTable levels
- No bloom filters, so every read scans every file
- Forgetting that deletes are tombstones, not removals