Temporal key-value store with point-in-time reads and restore

Question: Temporal key-value store with point-in-time reads and restore

Companies: Perplexity, Microsoft, Together AI, Amazon, OpenAI, Uber

Difficulty: Medium

Problem statement

Build an in-memory key-value store that keeps every version of every key, so you can ask what a key held at any point in time.

Implement the TemporalKVStore class:

• TemporalKVStore() creates an empty store.
• set(key: str, value, ts: int) -> None records that key holds value from time ts on.
• remove(key: str, ts: int) -> None records that key is absent from time ts on, until a later set.
• get(key: str, ts: int) -> value | None returns the value of the latest write to key with timestamp <= ts. It returns None if there is no such write or if that write was a remove.
• restore(ts: int) -> None rolls the whole store back to its state at time ts. All writes with a timestamp greater than ts are discarded permanently. New writes after a restore are allowed at any timestamp.

Rules:

• Timestamps are integers and may arrive out of order. A late write must take effect at its own timestamp. It must not change answers for earlier times, and it must not hide newer writes.
• Two writes to the same key at the same timestamp: the later call wins.
• Removing a key must not erase its history. Reads at earlier times still see the old values.
• Expect up to about 10^5 operations, mostly in timestamp order. get should be faster than a scan of the key's history.

Example

s = TemporalKVStore()
s.set("flag", "off", 100)
s.set("flag", "on", 200)
s.get("flag", 150)    -> "off"
s.get("flag", 200)    -> "on"
s.remove("flag", 300)
s.get("flag", 350)    -> None
s.set("flag", "beta", 150)   # arrives late
s.get("flag", 170)    -> "beta"
s.get("flag", 250)    -> "on"
s.restore(160)
s.get("flag", 500)    -> "beta"

Example 2

s = TemporalKVStore()
s.get("x", 10)        -> None
s.set("x", 1, 10)
s.set("x", 2, 10)     # same timestamp, last call wins
s.get("x", 10)        -> 2
s.get("x", 9)         -> None

Approach

The store never overwrites history. Each key owns a timeline: a list of
(timestamp, value) versions sorted by timestamp. A read at time t asks
"what was the last write to this key at or before t?", which is a
predecessor search on that timeline.

Brute force. Keep every write in one flat list and, on get, scan for
the matching key with the largest timestamp <= t. Writes are O(1) and
reads are O(total writes). That is fine for a first pass, and it makes the
read rule explicit before you optimize.

Per-key sorted timelines + binary search. Group writes by key and keep
two parallel lists per key, times and values, sorted by time.

• set(key, value, ts): if ts is newer than the last version (the usual
  case), append in O(1). Otherwise binary-search for the slot. An equal
  timestamp replaces the value there (last write wins). A smaller one is a
  late event and gets inserted in place.
• remove(key, ts): write a tombstone at ts instead of deleting
  anything. Deleting entries would destroy history, so reads before ts
  would break. A tombstone means "absent from here until the next set", and
  it uses the same insert path, so late removes work too.
• get(key, ts): bisect_right(times, ts) - 1 finds the newest version at
  or before ts. Return None if there is none or if it is a tombstone.
• restore(ts): roll the whole store back to time ts. Every version
  newer than ts is cut off each timeline for good. Keys whose first
  version is after ts disappear. New writes after a restore start a fresh
  future.

Invariants.

• times[key] is strictly increasing, and values[key][i] belongs to
  times[key][i].
• The state at any time is a pure function of the stored versions, so the
  order in which writes arrived does not matter. Only their timestamps do.
• A tombstone hides older values only for reads at or after its timestamp.

Code

from bisect import bisect_left, bisect_right
from typing import Any, Optional

_TOMBSTONE = object()  # marks "key removed at this timestamp"


class TemporalKVStore:
    """Versioned key-value store: every write is kept, reads are point-in-time."""

    def __init__(self) -> None:
        # key -> parallel lists, both sorted by timestamp
        self._times: dict[str, list[int]] = {}
        self._values: dict[str, list[Any]] = {}

    def _write(self, key: str, value: Any, ts: int) -> None:
        times = self._times.setdefault(key, [])
        values = self._values.setdefault(key, [])
        if not times or ts > times[-1]:          # common case: in-order append
            times.append(ts)
            values.append(value)
            return
        i = bisect_left(times, ts)
        if i < len(times) and times[i] == ts:    # same timestamp: last write wins
            values[i] = value
        else:                                    # late (out-of-order) event
            times.insert(i, ts)
            values.insert(i, value)

    def set(self, key: str, value: Any, ts: int) -> None:
        self._write(key, value, ts)

    def remove(self, key: str, ts: int) -> None:
        """Key reads as absent from ts until a later set."""
        self._write(key, _TOMBSTONE, ts)

    def get(self, key: str, ts: int) -> Optional[Any]:
        """Value of the latest write at or before ts, or None."""
        times = self._times.get(key)
        if not times:
            return None
        i = bisect_right(times, ts) - 1
        if i < 0:
            return None
        value = self._values[key][i]
        return None if value is _TOMBSTONE else value

    def restore(self, ts: int) -> None:
        """Roll the whole store back to its state at ts.

        Every write with timestamp > ts is discarded for good; later sets may
        write new history after ts.
        """
        for key in list(self._times):
            times = self._times[key]
            cut = bisect_right(times, ts)
            if cut == 0:
                del self._times[key]
                del self._values[key]
            elif cut < len(times):
                del times[cut:]
                del self._values[key][cut:]

Complexity

Let n be the number of versions for one key and K the number of keys.

Space is O(total writes), including tombstones.

Test cases

• set("a","x",10), then get("a",5) returns None (before the first write).
• get("a",10) returns "x", because the bound is inclusive.
• set("a","y",20), then get("a",15) returns "x" and get("a",1000) returns "y".
• remove("a",30), then get("a",29) returns "y" and get("a",30) returns None.
• set("a","z",40) after the remove, then get("a",45) returns "z".
• Late write: set("a","w",15) after the others, then get("a",17) returns "w" and get("a",14) returns "x".
• Same timestamp: set("a","y2",20) replaces "y", so get("a",20) returns "y2".
• Late remove: remove("a",12), then get("a",13) returns None and get("a",15) still returns "w".
• Unknown key: get("nope",100) returns None.
• Restore: set("b","us",25), restore(20), then get("a",100) returns "y2" and get("b",100) returns None.
• Write after restore: set("a","v9",50), then get("a",35) returns "y2" and get("a",50) returns "v9".
• restore(0) before every write empties the store.

Follow-ups

1. Undoable restore / branching history. "Restore, but let me go
   back." Instead of truncating, keep an append-only log of writes, each
   tagged with a global sequence number. A restore records a new view
   (as_of = ts, starting at sequence s) rather than deleting anything.
   Reads filter versions by sequence and by the active view. This is how
   MVCC databases and git-style branches avoid losing data.
2. O(1) restore. Restore touches every key. Make it lazy instead: store
   a global list of (restore_seq, cutoff_ts) and, per key, the sequence
   of each write. On access, trim a key only if a restore happened since
   its last trim. That is amortized O(log n) per access, with no global
   sweep.
3. Range and history queries. history(key, t1, t2) uses two
   bisects and a slice: O(log n + k). snapshot(ts) for all keys costs
   O(K log n). For prefix scans, keep keys in a sorted structure too (for
   example a SortedDict or a B-tree).
4. Memory and compaction. With a retention window W, drop versions
   older than now - W but keep the newest one at or before the cutoff,
   so reads at the cutoff are still correct. Drop leading tombstones. You
   could also spill cold versions to disk as immutable sorted runs
   (LSM-style) and keep only recent versions in memory.
5. Concurrency and throughput. Many readers and few writers: shard
   keys across lock stripes, or copy-on-write each key's timeline so
   readers never block. With heavy out-of-order writes, swap the lists for
   a skip list or SortedList so inserts stay O(log n).

Interviewer expectations

Mid-level (L4)

• Gets per-key sorted timelines and bisect_right - 1 right, including
  the inclusive bound and the "before the first write" case.
• Implements remove with a tombstone, not by deleting history, and
  explains why.
• Walks through tests by hand, including the same-timestamp overwrite.

Senior (L5)

• Handles out-of-order writes without re-sorting, and names the O(n)
  insert cost and its fix.
• Defines restore precisely (what happens to later writes and to keys
  that did not exist yet) before coding it. Keeps the invariants in view
  across parts.
• Discusses the hot path (append in O(1)) and the memory growth from
  keeping every version.

Staff (L6+)

• Frames the problem as MVCC: separates event time from arrival order,
  and proposes lazy or non-destructive restore with sequence numbers.
• Covers retention, compaction, and moving cold history to disk, and how
  each one changes read semantics.
• Reasons about concurrent readers and writers, sharding, and what
  consistency a reader at time t gets while late events keep arriving.