Build a Mini Key-Value Store

Build a Mini Key-Value Store (log-structured)

You've built a WAL; now build a real store on top of the same idea. This is a Bitcask-style engine — the design behind Riak: an append-only data file plus an in-memory index (key → file offset). Writes are sequential (fast); reads are one index lookup + one seek (O(1)); durability comes from the append + fsync you already know. It's the clearest way to internalize why log-structured storage (LSM, Kafka) is fast, and where it pays the cost (compaction).

The spec

• Put(k,v): append [key][val] to the active file, fsync, set index[k] = offset. O(1).
• Get(k): index[k] → seek + read the value. One disk read.
• Delete(k): append a tombstone record, remove from index. (You never rewrite in place — deletes are appends too.)
• Recover(): scan the file start-to-end, rebuilding the index (last write for a key wins). Torn tail discarded (reuse your WAL framing).
• Compact(): the file grows with every overwrite; periodically rewrite only the live entries into a fresh file, dropping stale versions and tombstones.

Why this is fast — and the catch

All writes are sequential appends → no random I/O, no in-place updates, so it saturates disk bandwidth. Reads are O(1) because the index is in RAM. The catch is space amplification: an overwritten or deleted key still occupies bytes in the file until compaction reclaims them. That write-fast / compact-later trade-off is the LSM-tree story — you're building its ancestor.

Reference — core (Go)

type KV struct {
    mu    sync.Mutex
    f     *os.File
    index map[string]int64   // key -> byte offset of latest record
    off   int64
}
// record on disk: [u32 keyLen][u32 valLen][key][val]   (valLen==0 ⇒ tombstone)

func (kv *KV) Put(k, v string) error {
    kv.mu.Lock(); defer kv.mu.Unlock()
    rec := frame(k, v)                       // len-prefixed, like the WAL
    if _, err := kv.f.WriteAt(rec, kv.off); err != nil { return err }
    if err := kv.f.Sync(); err != nil { return err }   // durable
    kv.index[k] = kv.off
    kv.off += int64(len(rec))
    return nil
}
func (kv *KV) Get(k string) (string, bool, error) {
    kv.mu.Lock(); off, ok := kv.index[k]; kv.mu.Unlock()
    if !ok { return "", false, nil }
    return readValueAt(kv.f, off)            // seek + read the value only
}
func (kv *KV) Delete(k string) error {
    kv.mu.Lock(); defer kv.mu.Unlock()
    if _, err := kv.f.WriteAt(frame(k, ""), kv.off); err != nil { return err } // tombstone
    kv.f.Sync(); kv.off += int64(len(frame(k, ""))); delete(kv.index, k)
    return nil
}
// Recover: scan file, index[k] = offset of the *last* record for k; skip torn tail.
// Compact: iterate index (live keys only), copy their current values into a new file, swap.

Reference — the write path (Java, sketch)

public synchronized void put(String k, String v) throws IOException {
    byte[] rec = frame(k, v);               // [keyLen][valLen][key][val]
    long at = off;
    ch.write(ByteBuffer.wrap(rec), at);
    ch.force(true);                         // fsync — durability point
    index.put(k, at);                       // in-memory: key -> offset
    off += rec.length;
}
public synchronized Optional<String> get(String k) throws IOException {
    Long at = index.get(k);
    return at == null ? Optional.empty() : Optional.of(readValueAt(ch, at));
}
// recover(): scan from 0, rebuild index (later offset for a key overwrites earlier);
// compact(): write live entries to newFile, fsync, atomically rename over the old file.

Tests to write

• Overwrite semantics: Put k=1, Put k=2, Get → 2; after Recover, still 2 (last write wins on replay).
• Delete: Put then Delete then Get → miss; and after Recover, still miss (tombstone honored).
• Crash recovery: kill mid-write; reopen → all fsync'd puts present, torn tail dropped.
• Compaction reclaims space: overwrite one key 1000×, file grows; Compact() → file shrinks to ~one record, Gets unchanged.

Extensions

• Segments + merge: roll to new files, compact old ones in the background (toward a real LSM).
• Hint files: persist the index so recovery skips the full scan (Bitcask's actual trick).
• Range scans → LSM: a hash index can't range-scan; swap it for sorted SSTables + a memtable and you've built an LSM-tree. Now you can explain B-tree vs LSM from having built one.
• Crash-consistent compaction: write the new file fully, fsync, then atomic rename — so a crash mid-compaction never loses data.

What you've mastered

• Why append-only + in-memory index gives fast O(1) writes and reads, and why compaction is the price.
• The write path's durability point (append + fsync) and crash-consistent compaction (atomic rename).
• The bridge from this to LSM-trees — so "B-tree vs LSM" is something you've felt, not memorized.

I just read a lesson on **Build a Mini Key-Value Store** (Hands-On Builds) and want to truly understand it. Explain Build a Mini Key-Value Store from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Build a Mini Key-Value Store** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Build a Mini Key-Value Store** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Build a Mini Key-Value Store** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.