Key-Value Storage Engine

This project implements a key-value storage engine in Rust. Based on Build Your Own Key-Value Storage Engine by The Coder Cafe.

Assumptions

• Keys are lowercase ASCII strings.
• Values are ASCII strings.
• Implementation is single-threaded (Will be revisited later).

NOTE: Assumptions persist for the rest of the series unless explicitly discarded.

Architecture

Storage Engine Module

The StorageEngine struct provides the core key-value storage functionality:

• WAL: Every write is first appended to a write-ahead log (wal.db) and synced to disk for durability. On startup, unflushed WAL entries are replayed into the memtable to recover the last session
• Memtable: Writes are buffered in an in-memory HashMap<String, MemtableEntry> for fast key-value operations. Deletions are represented as tombstones (MemtableEntry::Deleted) rather than immediate removals
• SST files: When the memtable reaches 2000 entries, it is flushed to a sorted JSON SST file under the l0/ directory and the WAL is cleared. Tombstones are written to SST files so deletions survive a restart
• Leveled compaction: Once the L0 directory accumulates 5 SST files, all L0 files and any existing L1 files are merged via a k-way min-heap merge into new key-range-partitioned SST files under the l1/ directory. Duplicate keys are resolved by keeping the newest value; tombstones are dropped entirely. Old L0/L1 files are removed and the manifest is updated atomically
• Manifest: Tracks SST files in two sections — a flat [L0] list and a [L1] list of key-range-to-file mappings. Kept in memory on the StorageEngine and updated atomically via a temp file rename on each flush and compaction
• Negative cache: An LRU cache of recently queried absent or deleted keys to avoid redundant SST scans
• Thread-safe access: Wrapped in Arc<Mutex<>> for concurrent access across HTTP handlers
• Simple interface: Provides get(), set(), and delete() methods for basic operations

Methods

• new(path) - Creates a storage engine rooted at path, creating the l0//l1/ directories if needed, recovering the SST counter and in-memory manifest from the MANIFEST file, and replaying any unflushed WAL entries into the memtable
• set(key: String, value: String) -> Result<()> - Appends to the WAL, inserts into the memtable, flushes to disk if the memtable is full, and triggers compaction if L0 has reached 5 files
• get(key: &str) -> Option<String> - Retrieves a value by key; checks the memtable, then the negative cache, then L0 SST files newest-to-oldest, then the single L1 SST file whose key range contains the key. Returns None for missing or deleted keys
• delete(key: &str) -> Result<()> - Appends a delete record to the WAL, inserts a tombstone into the memtable, and triggers compaction if L0 has reached 5 files

HTTP API

The server exposes a REST API on 127.0.0.1:8080 with the following endpoints:

GET /{key}

Retrieves the value associated with the given key.

Response:

• 200 OK - Returns the value as plain text
• 404 Not Found - Key does not exist

Example:

curl http://127.0.0.1:8080/mykey

PUT /{key}

Sets or updates the value for the given key.

Response:

• 200 OK - Value successfully stored
• 500 Internal Server Error - Failed to write to WAL or flush memtable to disk

Example:

curl -X PUT http://127.0.0.1:8080/mykey \
  -H "Content-Type: text/plain" \
  -d 'Hello, World!'

DELETE /{key}

Marks the given key as deleted.

Response:

• 202 Accepted - Key successfully deleted
• 500 Internal Server Error - Failed to write to WAL

Example:

curl -X DELETE http://127.0.0.1:8080/mykey

Client

The client crate is a load-testing and consistency-checking tool for the HTTP API. It reads a sequence of operations from put.txt or put-delete.txt (PUT/GET/DELETE requests), replays them against the running server with retry-on-transient-failure logic, and reports:

• Consistency checks: if a request takes longer than 1 second, it verifies that the last successful PUT is actually readable back from the server
• Latency metrics: p50/p95/p99 latency (in ms) for each request type

Run it with:

cargo run -p client

Usage

1. Start the server:

   cargo run

2. Store a value:

   curl -X PUT http://127.0.0.1:8080/greeting \
     -H "Content-Type: text/plain" \
     -d 'Hello, World!'

3. Retrieve the value:

   curl http://127.0.0.1:8080/greeting
   # Output: Hello, World!

4. Try to get a non-existent key:

   curl http://127.0.0.1:8080/nonexistent
   # Output: 404 Not Found

Agenda

• Week 1: In-Memory Store
• Week 2: LSM Tree Foundations
• Week 3: Durability with Write-Ahead Logging
• Week 4: Deletes, Tombstones, and Compaction
• Week 5: Leveling and Key-Range Partitioning
• Week 6: Block-Based SSTables and Indexing
• Week 7: Bloom Filters and Trie Memtable
• Week 8: Concurrency