In-Memory Versioned Key-Value Store (LLD)

0) Problem Restatement

Build a small key-value store library that keeps history. It supports:

• put(key, value) → returns a new version number
• get(key) → latest value
• get(key, version) or get_at(key, timestamp) → the value as it was at that version or time
• delete(key)
• Follow-ups: snapshots, rollback to an earlier version, and transactions (begin, commit, rollback, possibly nested).

LinkedIn asked a variant where you may only use maps/dictionaries (plus arrays and primitives) to build it, like a tiny embedded storage engine. Meta asked about versioning and rollback trade-offs between time and space.

1) Requirements

1.1 Functional

• Latest reads and writes, versioned reads, deletes (a delete is also a version).
• Snapshot: capture the whole store's state at a moment, and read from it later.
• Rollback: return the store to a past version.
• Transactions: group changes, then commit or discard them.

1.2 Constraints

• put O(1) amortized, get latest O(1), versioned get O(log V) where V is the number of versions of that key.
• Memory proportional to the number of changes.

2) Core Design

• A global version counter that increases on every write.
• For each key, a list of (version, value) in increasing version order. Appending is O(1), and since versions only grow, the list stays sorted, so we can binary search it.
• A delete appends (version, TOMBSTONE).

classDiagram
    class VersionedKV {
        -int clock
        -Map history
        -List txStack
        +put(key, value) int
        +get(key, version) Any
        +delete(key) int
        +snapshot() int
        +rollback(version) void
        +begin() void
        +commit() void
        +abort() void
    }
    class Entry {
        +int version
        +Any value
    }
    VersionedKV --> Entry

3) Code (Python)

import bisect

TOMBSTONE = object()

class VersionedKV:
    def __init__(self):
        self.clock = 0
        self.history = {}        # key -> ([versions], [values]) kept in parallel lists
        self.tx_stack = []       # list of dicts: pending writes per open transaction

    # ---------- basic versioned operations ----------
    def _write(self, key, value):
        self.clock += 1
        vers, vals = self.history.setdefault(key, ([], []))
        vers.append(self.clock)
        vals.append(value)
        return self.clock

    def put(self, key, value):
        if self.tx_stack:                       # inside a transaction: buffer it
            self.tx_stack[-1][key] = value
            return None
        return self._write(key, value)

    def delete(self, key):
        return self.put(key, TOMBSTONE)

    def get(self, key, version=None):
        for tx in reversed(self.tx_stack):      # uncommitted writes are visible to this tx
            if key in tx and version is None:
                v = tx[key]
                return None if v is TOMBSTONE else v
        if key not in self.history:
            return None
        vers, vals = self.history[key]
        if version is None:
            v = vals[-1]
        else:
            i = bisect.bisect_right(vers, version) - 1   # last write at or before version
            if i < 0:
                return None
            v = vals[i]
        return None if v is TOMBSTONE else v

    # ---------- snapshots and rollback ----------
    def snapshot(self):
        return self.clock                       # a snapshot is just a version number

    def rollback(self, version):
        # Record the old values as NEW writes, so history is never lost.
        for key, (vers, vals) in list(self.history.items()):
            old = self.get(key, version)
            cur = self.get(key)
            if old != cur:
                self._write(key, TOMBSTONE if old is None else old)

    # ---------- transactions ----------
    def begin(self):
        self.tx_stack.append({})

    def commit(self):
        writes = self.tx_stack.pop()
        if self.tx_stack:                       # nested: merge into the parent transaction
            self.tx_stack[-1].update(writes)
        else:
            for k, v in writes.items():
                self._write(k, v)

    def abort(self):
        self.tx_stack.pop()                     # just drop the buffered writes

• put/delete: O(1) amortized.
• get latest: O(1) plus a check of open transactions.
• get(key, version): O(log V) with binary search.
• snapshot(): O(1), because a snapshot is just "remember the current version".
• rollback(version): O(K log V) over all keys. It could be optimized by tracking keys changed after that version.

4) Design Choices Explained Simply

• Why is a snapshot just a number? We never overwrite history, so "the store at version 42" can always be rebuilt by reading each key's last write at or before 42. No copying is needed.
• Why write rollback as new versions? It keeps history append-only. We can even undo a rollback, and older snapshots still work.
• Why buffer transaction writes? Until commit, other readers shouldn't see them. Abort is then trivial (drop the buffer). Nested transactions merge into their parent on commit.
• Using only maps (the LinkedIn constraint): the parallel lists can be replaced with a map version → value per key, plus a sorted array of that key's versions for binary search.

5) Follow-ups

5.1 Concurrency

• Writers take a lock (or a lock per key) to append. Readers of old versions need no locks, because old entries never change. This is the core idea of MVCC (multi-version concurrency control) in real databases.
• A transaction can read from the snapshot version taken at begin(), so it sees a stable view while others write.

5.2 Memory and garbage collection

Keeping every version forever grows without limit. Options:

• Keep only the last N versions per key, or versions newer than the oldest active snapshot.
• Compact periodically: drop versions nobody can read anymore.

5.3 Time-based reads

Store a timestamp with each version. get_at(key, ts) binary searches the timestamps instead of versions (equivalent to LeetCode's "Time Based Key-Value Store").

5.4 Persistence

Append each write to a log file (write-ahead log) and periodically write a snapshot of the latest values. On restart, load the snapshot and replay the log.

6) Wrap-Up

Keep a global version counter and, for every key, an append-only sorted list of (version, value), with deletes as tombstones. Latest reads are O(1), versioned reads use binary search, and snapshots are just remembered version numbers. Implement rollback as new writes, buffer transaction writes in a stack of maps for commit, abort and nesting, and add garbage collection and a write-ahead log when memory and durability matter.