Building an LSM Tree Storage Engine from Scratch in C++
Most developers use databases.
Very few understand how they work internally.
To bridge that gap, I built a Log-Structured Merge Tree (LSM Tree) based key-value storage engine from scratch in C++ to understand how modern storage engines optimize disk I/O, durability, and performance.
What This Project Is
This project is a key-value storage engine based on the LSM Tree design.
The core idea is simple:
Convert random writes into sequential writes.
Traditional structures like B-Trees perform in-place updates, which result in random disk I/O. LSM Trees avoid this by appending data and organizing it efficiently in the background.
Why This Project Matters
Even if this implementation does not match production systems like LevelDB or RocksDB, it demonstrates an understanding of:
Disk I/O behavior
Data durability
Storage engine design
Performance tradeoffs
Internal database architecture
Most engineers use databases as black boxes. This project focuses on understanding what happens inside them.
High-Level Architecture
Write Path
PUT → Write-Ahead Log → Memtable → Immutable Memtable → SSTable → Compaction
Read Path
GET → Memtable → Bloom Filter → Block Index → Disk Block
The system is designed to optimize writes while still keeping reads efficient.
Core Components and Design Decisions
Write-Ahead Log (WAL)
The WAL is an append-only log that records all operations.
Why it exists:
Ensures durability
Enables crash recovery
Append-only writes are used because sequential disk writes are significantly faster than random writes.
On restart, the system replays the WAL to rebuild the memtable. If a partially written entry is detected, replay stops to avoid corruption.
Memtable
The memtable is an in-memory sorted structure implemented using std::map.
Why sorted order matters:
Efficient SSTable generation
Maintains ordered disk layout
std::map was chosen over unordered_map because it maintains sorted order with logarithmic insert time.
Immutable Memtable
Flushing the memtable to disk can block writes.
To avoid this:
The active memtable is converted into an immutable memtable
A new memtable is created for incoming writes
Flushing happens in the background
This decouples write performance from disk I/O.
SSTables
SSTables are immutable, sorted files stored on disk.
Why immutable:
No in-place updates
Simplifies concurrency
Enables efficient sequential writes
Binary Storage Format
Instead of storing data as text, the system uses a binary format:
[key_size][key][value_size][value]
Why:
Faster reads
Exact offsets
No parsing overhead
More compact storage
Block-Based Storage
Disk reads happen in pages (typically around 4KB).
Instead of reading individual records, the system reads blocks containing multiple records.
Structure:
[data blocks][block index][footer]
This improves read efficiency significantly.
Block Index
The block index maps a key range to a disk offset.
This allows:
Jumping directly to relevant data
Avoiding full file scans
Bloom Filters
Bloom filters are used to quickly check whether a key is definitely not present.
This prevents unnecessary disk reads, especially for negative lookups.
Bloom filters allow false positives but never false negatives.
Compaction
Over time, multiple SSTables accumulate with:
Duplicate keys
Outdated values
Deleted entries
Compaction merges SSTables, keeps the latest values, and removes unnecessary data.
This process runs in the background to avoid blocking writes.
Background Processing
A worker thread handles:
Flushing memtables
Compaction
This ensures writes remain fast and non-blocking.
The system uses std::thread with condition_variable to avoid inefficient polling.
Concurrency Design
The system uses:
mutex
condition_variable
task queue
This design separates producers (writes) from consumers (background tasks), allowing asynchronous processing.
Tradeoffs
To keep the implementation focused, several features were simplified:
No multi-level compaction
No block cache
No compression
Single background worker thread
These decisions prioritize clarity of design over full production complexity.
Running the System
Compile:
g++ -std=c++17 main.cpp storage_engine.cpp memtable.cpp wal.cpp sstable.cpp compaction.cpp bloom_filter.cpp -o lsm_store
Run:
./lsm_store
Testing
Basic operations:
PUT key value
GET key
DELETE key
Crash recovery test:
Insert data
Kill the program
Restart and verify data
Load testing can be done by inserting large numbers of keys and observing SSTable creation and compaction behavior.
Benchmarking
Key metrics:
Write throughput
Read latency
Compaction overhead
Expected behavior:
Writes are fast due to in-memory buffering and sequential logging
Reads are slower due to disk lookups
Key Concepts (Interview Focus)
Why LSM instead of B-Tree?
LSM Trees optimize for write-heavy workloads using sequential I/O, while B-Trees rely on random writes.
Why Bloom Filters?
They reduce unnecessary disk access by quickly ruling out missing keys.
What is write amplification?
Data is rewritten multiple times during compaction.
What happens on crash?
The WAL is replayed to restore the system state.
What I Would Improve
Multi-level compaction
Block caching
Compression
Parallel compaction
Conclusion
Building an LSM Tree from scratch provides a deep understanding of how modern storage engines work.
The key insight is that performance comes from designing around hardware constraints, especially disk behavior.
By converting random writes into sequential operations and using background processes, the system achieves high write throughput while maintaining acceptable read performance.