● Stage 04 • Storage Engines
LSM-Tree Storage Engine
Construct an embedded persistent storage engine based on Log-Structured Merge-Trees. Implement Write-Ahead Logging, in-memory SkipLists, immutable SSTable disk files, and compaction.
First steps
- Implement put and get with an in-memory map.
- Append each write to a log before updating the map. Replay the log on startup.
- Write one key. Restart the program and check its value before adding disk tables.
Project Goal
- Understand disk write amplification and why modern databases (RocksDB, Cassandra) use LSM-Trees.
- Implement Write-Ahead Logging (WAL) with CRC32 checksums for zero data loss on unexpected crashes.
- Build an in-memory sorted SkipList that flushes to immutable on-disk SSTable files upon reaching capacity.
- Implement Bloom filters and multi-way merge compaction to eliminate deleted records and speed up lookups.
Skills Acquired
Write-Ahead Logging (WAL)
SkipList Data Structure
SSTable File Layout
Murmur3 Bloom Filters
Multi-Way Merge Compaction
Crash Consistency Testing
Technical Specification
- API Functions: put(key, val), get(key), delete(key), and scan(start_key, end_key).
- Flush Trigger: MemTable size threshold of 4MB triggers asynchronous disk flush.
- WAL Format: [4B CRC32][2B key_len][4B val_len][1B op_type][key][val].
Milestones
04.1
Write-Ahead Log (WAL) & Replay Engine
Append every mutation to wal.log with length headers and CRC32 checksums before touching memory. On reboot, verify checksums and replay valid entries.
04.2
In-Memory SkipList MemTable
Implement a sorted SkipList data structure (probability $p=0.5$, max height 16). Track byte memory usage and trigger a background disk flush when size reaches 4MB.
04.3
Immutable SSTable Serializer
Flush sorted entries into immutable SSTable files. Include a sparse index every 64 records for fast binary search, and append a 16-byte offset footer.
04.4
Bloom Filter Integration
Build a probabilistic Bloom filter bit array ($k=3$ hash functions) per SSTable file. Reject non-existent key lookups before initiating disk reads.
04.5
Multi-Way Compaction Engine
Merge multiple overlapping SSTables into consolidated runs using a min-heap iterator. Discard tombstoned deletion markers and obsolete key versions.
Verification Commands
Write storage_test as a harness for your engine. It should record which writes were acknowledged so --verify-all can check them after a crash. Run against disposable test data; the PID below belongs only to this test process.
# 1. Run insertion stress test (50,000 keys) in background
./storage_test --ops 50000 &
PID=$!
# 2. Terminate forcefully with SIGKILL mid-execution
sleep 2
kill -9 $PID
# 3. Verify recovery and consistency
./storage_test --verify-allAcceptance Criteria
Following forceful process termination with kill -9, the storage engine must recover state without crashes. All writes confirmed before the crash must be verified via CRC32 checks, and scan() must return keys in sorted order.