LSM Storage Engine
A Rust key-value store with Redis-compatible commands, write-ahead logging, and background compaction.
Storage and recovery
The server accepts Redis-compatible commands through RESP. An unmodified
redis-cli can connect and issue GET, SET, and DEL.
A write-ahead log records changes before they enter the memtable. Immutable SSTables hold flushed data, with sparse indexes and Bloom filters to narrow reads. Background compaction merges the files while clients continue to read and write.
The fsync policy controls the durability/throughput tradeoff. Recovery tests interrupt the server during writes and check the resulting state. Property-based tests compare operation sequences with a reference HashMap, including sequences that cross a compaction or recovery boundary.
Why I built it
I could draw the storage engines behind the backends I used, but I could not explain their recovery behaviour in much detail. Implementing one made me work through the ordering of writes, file creation, and manifest updates. A crash between any two of those steps still needs a recoverable state.