Problem 77 · Object & System Design

Versioned (MVCC) Key-Value Store

MediumClassic DSA & systems

01Problem

Implement put(key, value) -> version using a global monotonically increasing version, get(key, version=None) returning the value as of that version (latest if None), and delete(key) -> version.

02Key insight

Append-only per-key version chains with a global commit counter: a read at version v binary-searches the newest entry <= v. Deletes are tombstone versions, so readers at older versions still see the old value (snapshot isolation for reads).

03Solution

solution.pypython41 lines

import bisect
from typing import Any

_DELETED = object()


class MVCCStore:
    def __init__(self) -> None:
        self.version = 0
        self.versions: dict[str, list[int]] = {}
        self.values: dict[str, list[Any]] = {}

    def _append(self, key: str, value: Any) -> int:
        self.version += 1
        self.versions.setdefault(key, []).append(self.version)
        self.values.setdefault(key, []).append(value)
        return self.version

    def put(self, key: str, value: Any) -> int:
        return self._append(key, value)

    def delete(self, key: str) -> int:
        return self._append(key, _DELETED)

    def get(self, key: str, version: int | None = None, default: Any = None) -> Any:
        vs = self.versions.get(key)
        if not vs:
            return default
        at = self.version if version is None else version
        i = bisect.bisect_right(vs, at) - 1
        if i < 0:
            return default
        v = self.values[key][i]
        return default if v is _DELETED else v

    def gc(self, oldest_active: int) -> None:
        """Drop versions no reader at >= oldest_active can observe."""
        for key, vs in self.versions.items():
            keep_from = max(bisect.bisect_right(vs, oldest_active) - 1, 0)
            del vs[:keep_from]
            del self.values[key][:keep_from]

Try it first.

TimeO(1) put; O(log V) get

SpaceO(total versions)

tests.py · 4 passing

tests.pypython7 lines

s = MVCCStore()
v1 = s.put("x", "a"); v2 = s.put("y", "b"); v3 = s.put("x", "c"); v4 = s.delete("x")
assert (v1, v2, v3, v4) == (1, 2, 3, 4)
assert s.get("x", 0) is None and s.get("x", 1) == "a" and s.get("x", 2) == "a"
assert s.get("x", 3) == "c" and s.get("x") is None and s.get("y") == "b"
s.gc(oldest_active=3)
assert s.get("x", 3) == "c" and len(s.versions["x"]) == 2

04Staff-level follow-up

Concurrent write transactions? Snapshot isolation: read at start_ts, buffer writes, at commit check first-committer-wins (any key written by another txn with commit_ts > start_ts aborts), then stamp commit_ts.