Persistent KV Engine

Project roadmap

1. 01

   Design the storage format

   ~2h

   Write DESIGN.md: the record layout (CRC32 checksum, timestamp, key length, value length or a marker for deletions, key and value, as little-endian fixed-size integers), data files named by generation number, the in-memory index (key to file, offset and length), the sync options (sync every write, or batch), and how compaction swaps files. Define the public API: open, get, set, remove and compact, returning your own error type. Done when: DESIGN.md covers the format, index, durability and compaction.

2. 02

   Write and read records

   ~2.5h

   Implement set and remove by appending encoded records to the active file through a BufWriter, updating the index. Implement get by reading the record at the stored position and checking its checksum. Define errors with thiserror (IO, corruption and key not found) and never use unwrap in the library. Done when: set, get, overwrite and remove work in unit tests.

3. 03

   Recover after a crash

   ~2.5h

   On open, scan the data files in order to rebuild the index. When the last record is incomplete or its checksum fails, truncate the file at the last good record and report it; corruption in the middle is reported as an error. Implement the sync options with File::sync_data. Done when: a test that appends garbage or half a record to the file recovers every complete record.

4. 04

   Compact the data

   ~2.5h

   Track how many bytes are stale (overwritten or deleted), and when it passes a threshold, write the live records to a new file, sync it, sync the folder, switch the index to it, and then delete the old files. A crash at any point must leave either the old or the new files complete and readable. Done when: compaction shrinks the data, every key still reads correctly, and killing the process during compaction loses nothing.

5. 05

   Make it safe for many threads

   ~2h

   Wrap the engine so it can be shared: an RwLock (or a lock-free map such as dashmap) for the index so reads run in parallel, and a Mutex around the writer so writes are serialized. Run compaction in the background without blocking reads. Done when: a test with 8 threads doing random reads and writes gives correct results and doesn't deadlock.

6. 06

   Add a TCP server with Tokio

   ~2h

   Build a server with Tokio that accepts connections and handles a simple line protocol (GET key, SET key value, DEL key), running the engine calls with spawn_blocking since they use blocking file I/O. Add a client binary and shut down cleanly on Ctrl+C, syncing data first. Done when: several clients can use the store at once, and data survives a server restart.

7. 07

   Test and benchmark

   ~2.5h

   Write a test that runs thousands of random operations against the engine and a HashMap at the same time, reopening the engine and compacting at random points, and checks they always agree. Add crash tests that truncate the file at random places. Benchmark reads and writes with criterion and record the results in README.md. Done when: all tests pass, and README.md shows the benchmark numbers.

Resources

• ArticleBitcask: a log-structured hash table (paper)
• DocsPingCAP talent plan: build a key-value store in Rust
• Docsstd::fs::File::sync_data
• DocsTokio tutorial
• DocsCriterion.rs user guide