Mini-LSM

A learner-oriented LSM-tree key-value storage engine written in Rust. This repository starts with a small complete vertical slice: writes enter a checksummed write-ahead log and ordered memtable, flush into immutable sorted tables, recover through a manifest, and are reclaimed through full compaction.

Implemented

• Byte-oriented put, get, delete, and ordered scan
• Ordered in-memory memtable with configurable automatic flushing
• Checksummed, length-delimited WAL and recovery of unflushed writes
• Checksummed immutable SST files
• Atomic manifest replacement
• Newest-value-wins reads across multiple SSTs
• Full compaction and tombstone reclamation
• Corruption, restart, range, flush, and compaction tests
• Small command-line interface

Run

cargo test
cargo run -- /tmp/example-lsm put hello world
cargo run -- /tmp/example-lsm get hello
cargo run -- /tmp/example-lsm scan
cargo run -- /tmp/example-lsm compact

Architecture

put/delete -> WAL -> mutable BTreeMap -> flush -> immutable SST files
                    ^                         |
                    |--- reads merge newest--|

MANIFEST records the ordered list of live SST files.
Compaction merges all SSTs and removes overwritten values and tombstones.

Durability contract

put and delete append to the process's WAL buffer. sync establishes the durability boundary. Automatic or explicit flush synchronizes the WAL before publishing a new SST in the manifest. A torn final WAL record is ignored; checksum failures in complete records and malformed SSTs are reported as corruption.

Learner roadmap

1. Replace eager SST loading with indexed blocks and lazy I/O.
2. Add prefix compression, Bloom filters, and a block cache.
3. Introduce immutable memtables and a background flush worker.
4. Replace full compaction with leveled and tiered policies.
5. Upgrade the manifest to an append-only checksummed log.
6. Add atomic write batches and deterministic crash injection.
7. Add timestamped internal keys, snapshots, MVCC, and conflict validation.
8. Benchmark read, write, and space amplification.

The implementation deliberately favors visible invariants over production optimizations so each roadmap step can be learned independently.