Design a time-based key-value store

01The design, in the six-step framework

1. Requirements and use cases

A phased phone-screen favourite: start with timestamps that only grow, then let inserts arrive in any order, then ask for a range of versions. The design must survive each phase without a rewrite.

• A caller sets a key to a value at a timestamp t.
• A caller gets a key at a timestamp t and receives the value with the largest timestamp less than or equal to t, or nothing if no such write exists.
• Phase two: timestamps for one key may arrive out of order; get must still be correct.
• Phase three: a caller asks for all versions of a key between two timestamps.
• Equal timestamps for the same key: the later call wins (stated assumption, confirmed with the interviewer).

Out of scope: expiry (that is the TTL store), persistence, and a global snapshot across keys. Non-functional constraints: get in O(log v) where v is the number of versions of that key; set amortised O(1) when timestamps are monotonic and O(v) only in the out-of-order case, which you state as the trade-off; memory holds every version, because history is the feature.

2. Core entities and relationships

• TimeMap: the public object; owns one VersionLog per key.
• VersionLog: the sorted history of one key; two parallel lists, timestamps and values, kept in timestamp order.
• Version: a value object (timestamp, value) returned by range queries.

The map composes its logs: a log exists only for its key and dies with the map. Keeping a log per key rather than one global list is what makes every operation depend on the versions of one key, not on the whole store. The parallel lists are a deliberate choice over a list of tuples: bisect works on the timestamp list directly without a key function, which keeps the search O(log v) with no allocation. See snapshots and versioning for why history is stored as appended versions rather than overwritten values.

3. Interfaces and key methods

from typing import Generic, List, Optional, TypeVar

V = TypeVar("V")


class Version(Generic[V]):
    t: int
    value: V


class TimeMap(Generic[V]):
    def set(self, key: str, value: V, t: int) -> None:
        """Record value for key at time t; any order of t is accepted; equal t overwrites."""

    def get(self, key: str, t: int) -> Optional[V]:
        """Value of the latest write with time <= t, or None."""

    def range(self, key: str, t1: int, t2: int) -> List[Version[V]]:
        """All versions with t1 <= t <= t2 in time order."""

Invariants: within a log, times is strictly increasing and len(times) == len(values); a key with no writes has no log; and get never returns a version with a timestamp greater than the one asked for. The strictly-increasing rule is what makes "equal t overwrites" true by construction.

4. Design patterns and the choices behind them

Binary search over an append-only log

The force is "latest write at or before t" over a history that mostly grows at the end. A sorted list plus bisect_right gives O(log v) reads and O(1) appends in the monotonic case. A dictionary from timestamp to value is rejected: it answers "exactly t" in O(1) but cannot answer "at or before t" without a scan. A balanced tree per key would give O(log v) inserts in the out-of-order case too; the standard library has none, and the honest trade-off is that out-of-order inserts cost O(v) here, which is fine when they are rare and the interviewer usually accepts the reasoning. This is the ordinary use of interval arithmetic on a timeline.

One method name per question

The force is ambiguity: "get at t" and "get exactly at t" are different questions. The API names only the floor version, and range covers the rest. Adding get_exact later is cheap; conflating the two in one method with a flag is the thing to avoid, per designing method signatures.

Immutable Version results

Range queries return copies as frozen value objects, never views into the internal lists, so a caller cannot corrupt the ordering invariant. That is identity and equality done simply: a Version is equal when its fields are equal and has no identity of its own.

5. Core flow and code

Flow for get("k", 7) when the log for k holds times [2, 5, 9]:

1. The map finds the log for k.
2. bisect_right(times, 7) returns 2, the number of timestamps not greater than 7.
3. Index 2 − 1 = 1 holds time 5, so the value written at 5 is returned.
4. Had the result been 0, there is no write at or before 7, so the answer is None.

from bisect import bisect_left, bisect_right
from dataclasses import dataclass
from typing import Dict, Generic, List, Optional, TypeVar

V = TypeVar("V")


@dataclass(frozen=True)
class Version(Generic[V]):
    t: int
    value: V


class VersionLog(Generic[V]):
    """History of one key: times strictly increasing, values aligned by index."""

    def __init__(self) -> None:
        self.times: List[int] = []
        self.values: List[V] = []

    def add(self, t: int, value: V) -> None:
        if not self.times or t > self.times[-1]:      # the common, monotonic case: O(1)
            self.times.append(t)
            self.values.append(value)
            return
        i = bisect_left(self.times, t)                 # out of order: O(v) insert
        if i < len(self.times) and self.times[i] == t:
            self.values[i] = value                      # equal t overwrites
        else:
            self.times.insert(i, t)
            self.values.insert(i, value)

    def at(self, t: int) -> Optional[V]:
        i = bisect_right(self.times, t)
        return self.values[i - 1] if i else None

    def between(self, t1: int, t2: int) -> List[Version[V]]:
        lo, hi = bisect_left(self.times, t1), bisect_right(self.times, t2)
        return [Version(self.times[i], self.values[i]) for i in range(lo, hi)]


class TimeMap(Generic[V]):
    def __init__(self) -> None:
        self.logs: Dict[str, VersionLog[V]] = {}

    def set(self, key: str, value: V, t: int) -> None:
        self.logs.setdefault(key, VersionLog()).add(t, value)

    def get(self, key: str, t: int) -> Optional[V]:
        log = self.logs.get(key)
        return log.at(t) if log else None

    def range(self, key: str, t1: int, t2: int) -> List[Version[V]]:
        if t1 > t2:
            raise ValueError("t1 must not exceed t2")
        log = self.logs.get(key)
        return log.between(t1, t2) if log else []


if __name__ == "__main__":
    m: TimeMap[str] = TimeMap()
    m.set("k", "a", 2)
    m.set("k", "c", 9)
    m.set("k", "b", 5)                       # out of order
    assert m.get("k", 7) == "b"
    assert m.get("k", 1) is None
    assert m.get("k", 9) == "c" and m.get("k", 100) == "c"
    m.set("k", "B", 5)                       # equal t overwrites
    assert [v.value for v in m.range("k", 3, 9)] == ["B", "c"]

6. Extensions, concurrency and what interviewers probe

• Phase changes. Monotonic to out-of-order costs one branch in add; range queries cost one more bisect. Say what each phase costs before coding it; that is what the phased format is testing.
• Equal timestamps. State the overwrite rule before the first line of code. The alternative, keeping both and returning the later insert, needs a tie-break counter.
• Many out-of-order writes. If the interviewer pushes, describe a per-key balanced tree or a skip list for O(log v) inserts, and note the standard library gap.
• Memory. Every version is kept; a retention rule (drop versions older than T) is a prefix slice on both lists, cheap because they are sorted.
• Thread safety. A lock per key (inside VersionLog) lets writers of different keys proceed in parallel; the outer dictionary needs its own lock only on first creation of a log.
• Common mistake. Using bisect_left for the floor lookup, which returns the wrong index when t equals a stored timestamp. The test with get("k", 9) catches it.

02Where this question was reported

• GitHub · Build a KV store with TTL expiry (same round: cursor-based pagination API)
• ReturnZero · Time-based KV store: read at t returns latest value <= t; phases add arbitrary-order inserts and range queries
• Land the Lab · 'Top-k points by frequency, and a closest-timestamp key-value store'
• Exponent · Practice version: TTL then fixed capacity; alive-at-exact-expiry and whether expired keys count toward size; lazy expiry vs background sweep