Overview
Log-Structured Merge trees power RocksDB, LevelDB, Cassandra, and most modern write-heavy storage systems. Understanding them from the inside — not just the API — is prerequisite knowledge for doing anything serious with storage engines.
This is my working implementation, built alongside Alex Chi's Mini-LSM course. The course covers the core components; what comes after the course is where it gets interesting.
What's implemented
- Memtable — in-memory skip list with O(log n) reads and writes
- WAL — write-ahead log for crash recovery before memtable flush
- SSTable — sorted string table with block-level encoding and bloom filters
- Merge iterators — multi-way merge across memtable + L0 + leveled SSTables
- Compaction — tiered and leveled compaction strategies
- Manifest — persistent metadata tracking SSTable versions and compaction state
- MVCC — multi-version concurrency control for snapshot reads
What comes next
The course gives you a working engine. The interesting work is what you do after:
Custom compaction policies — RocksDB's universal compaction has known weaknesses for time-series data (write amplification grows with dataset age). I want to implement a time-window compaction strategy similar to Cassandra's TWCS, where SSTables are bucketed by write time and only compacted within windows.
Tiered storage — hot SSTables on NVMe, cold SSTables on slower storage, automatic migration based on access frequency. The manifest layer already tracks enough metadata to make this tractable.
Vectorized block decoding — SSTable blocks are currently decoded row-by-row. SIMD-accelerated decoding for fixed-width value types could significantly reduce read amplification on range scans.
The goal is an engine tuned for append-heavy, time-ordered workloads — the access pattern that most production telemetry and event-sourcing systems actually have.