Durable KV Store

Overview

Implement a single-machine key-value store that survives crashes. put and delete change an in-memory map, but the store must recover its state after a restart, so every mutation is first appended to a write-ahead log (WAL) on disk. The in-memory map needs no fancy optimization; the interesting parts are durability, thread safety, and keeping the WAL from growing forever.

The key ordering rule is: write the WAL and fsync it before updating the in-memory map. If you update memory first and crash before the log is on disk, recovery loses that mutation and the state is inconsistent.

Interfaces

class DurableKVStore:
    def __init__(self, wal_path):
        self._map = {}
        self._lock = Lock()
        self._wal = open(wal_path, "a+")
        self.recover()                    # rebuild state from disk on startup

    def put(self, key, value):
        with self._lock:
            self._append_wal({"op": "PUT", "key": key, "value": value})
            self._map[key] = value

    def get(self, key):
        with self._lock:
            return self._map.get(key)

    def delete(self, key):
        with self._lock:
            self._append_wal({"op": "DELETE", "key": key})
            self._map.pop(key, None)

    def _append_wal(self, record):
        self._wal.write(encode(record) + "\n")
        self._wal.flush()                 # hand buffer to the OS
        os.fsync(self._wal.fileno())      # force it durably to disk

A single global lock around both the WAL append and the map update is the simplest correct version: thread-safe, durable, and it preserves operation order. Its costs are that all reads and writes serialize and every write pays an fsync.

Inputs and outputs

• Input: put(key, value), get(key), and delete(key) from one or many threads.
• Output: after a crash and restart, the store recovers exactly the mutations that were acknowledged before the crash.

Requirements

• A mutation is durable before its call returns: WAL append, then fsync, then the memory update.
• Concurrent access is safe — readers never see a half-applied write.
• Recovery rebuilds the map by replaying the log (and snapshot, see below).
• The WAL must not grow without bound; support compaction.

Locking choices

• Global lock — the baseline above. Simple and obviously correct.
• Read-write lock — for read-heavy workloads, many gets run together; writes stay exclusive.
• Sharded / striped locks — partition keys into N shards each with its own lock so writes to different shards run in parallel. This is the simplified ConcurrentHashMap idea.
• Single writer thread — all writes go through a queue to one writer that owns the WAL; easy to reason about durability, and fsync can be batched.

WAL compaction and recovery

def compact(self):
    with self._lock:
        with open("snapshot.tmp", "w") as f:
            for key, value in self._map.items():
                f.write(encode({"key": key, "value": value}) + "\n")
            f.flush()
            os.fsync(f.fileno())
        os.rename("snapshot.tmp", "snapshot")   # atomic swap
        self._truncate_wal()                     # old log no longer needed

def recover(self):
    self._map = {}
    if snapshot_exists():
        for rec in read_snapshot():
            self._map[rec.key] = rec.value
    for rec in read_wal():                       # replay log after the snapshot
        apply(rec, self._map)

The WAL accumulates dead history (PUT a 1, PUT a 2, PUT a 3...). Compaction writes the live map to a temp snapshot, fsyncs it, atomically renames it into place, then truncates the WAL — all crash-safe. On recovery you load the snapshot first, then replay only the WAL entries written after it.

Follow-ups

• Every write pays its own fsync. How would group commit let several writes share one — and what do callers give up?

• The WAL grows forever. When should compaction kick in, and how do you keep it crash-safe while writes are still coming?

• How would a copy-on-write snapshot let readers run without ever blocking a writer?

• And more...