Versioning, history and point-in-time queries

intermediateCommon atAnthropicOpenAIStripeGoogleRead firstBinary searchHash mapsPractise in the Sandbox →

Instead of overwriting a value, append a version (timestamp, value) to that key’s list and keep the list sorted by timestamp. “Value as of t” is then the floor: the last version with timestamp ≤ t, found by binary search in O(log v) for v versions. Deletes become tombstone versions, so history stays intact.

The idea in plain words

A plain map forgets. put("price", 12.50) destroys 9.99, and nobody can ever ask what the price was last Tuesday.

A versioned store keeps a logbook per key. Each entry says “from this moment, the value is X”. To read the value at some moment t, open that key’s logbook and find the last entry written at or before t. Everything after t hasn’t happened yet from that moment’s point of view.

Because the logbook is sorted by time, “the last entry at or before t” is a binary search, not a scan. That’s the whole trick, and it shows up everywhere: databases (multi-version concurrency control), Git, configuration systems, feature flags, and audit logs.

Three words to know:

• Version: one (timestamp, value) entry. The value is in effect from its timestamp until the next version.
• Floor: the greatest element ≤ t. The opposite, the least element ≥ t, is the ceiling.
• Tombstone: a version that says “deleted”. Reads that land on it return nothing, but older versions are still there for older reads.

See it

Drag t to read the store at any moment. The search panel shows every probe of the binary search for the selected key. Then write a version with a past timestamp: it lands in the middle of the list, not the end. Write a delete and watch a tombstone hide the value only for reads after it.

Point-in-time reads: a version list per key + binary search

sandbox

keypriceownerflagvalueat ts putdelete↺

read as of t = 45

binary search in price's timestamps3 probes

10

25

40

55

70

01234

floor

1. lo=0 hi=5 mid=2: ts 40 ≤ 45? yes → lo=mid+12. lo=3 hi=5 mid=4: ts 70 ≤ 45? no → hi=mid3. lo=3 hi=4 mid=3: ts 55 ≤ 45? no → hi=midanswer index = lo − 1 = 2

snapshot of every key as of t=45

price11.00 (@40)ownerraj (@30)flagnone yet

price = 11.00: the newest version written at or before 45.

version in effect at tprobed by the searchtombstone (delete)

Write a version at a past timestamp (out of order) and watch where it lands. Drag t to read history.

When to reach for it

The problem says…	What it’s asking for
“get the value as of time t” / “at or before ts”	Floor search in a per-key sorted version list.
“keep the history” / “list every version”	Never overwrite. The version list is the history.
“delete, but old reads still see the value”	Tombstone versions, not removal.
“writes may arrive out of timestamp order”	Insert in sorted position, not append.
“who had access / what was the status at time t”	The same floor query over a list of state changes.
“what changed between t1 and t2”	Two binary searches give the index range; count or slice it.

How it works

1. One list per key: a map from key to a list of versions, sorted by timestamp. Parallel arrays (times, values) make binary search simple.
2. Write: if the timestamp is newer than the last one, append (O(1)). If it’s older, insert at its sorted position. If it equals an existing one, decide with the interviewer: replace, or reject.
3. Delete: append a tombstone version. Don’t remove anything.
4. Read at t: binary search for the first timestamp > t. The version just before it is the floor. Index -1 means the key didn’t exist yet; a tombstone means it was deleted.

Here are steps 2 and 4 for a single history (one thermostat’s setpoints). In a store, there’s one of these per key.

Python

floor_index.py

import bisect


def floor_index(times: list[int], t: int) -> int:
    """Index of the last time <= t in a sorted list, or -1 if every time is > t."""
    lo, hi = 0, len(times)  # 1. search the half-open range [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if times[mid] <= t:
            lo = mid + 1  # 2. mid is a candidate; the answer is mid or later
        else:
            hi = mid  # 3. mid is too new; the answer is before it
    return lo - 1  # 4. lo = first index with time > t, so the floor is just before it


# A thermostat's setpoint history, kept sorted by time.
times: list[int] = []
temps: list[float] = []


def record(t: int, temp: float) -> None:
    i = bisect.bisect_left(times, t)
    if i < len(times) and times[i] == t:
        temps[i] = temp  # same instant: replace
    else:
        times.insert(i, t)  # out-of-order writes land in the middle: O(n) shift
        temps.insert(i, temp)


def setpoint_at(t: int) -> float | None:
    i = floor_index(times, t)
    return None if i < 0 else temps[i]


if __name__ == "__main__":
    for t, temp in [(10, 19.0), (40, 21.5), (25, 20.0), (40, 22.0)]:
        record(t, temp)
    assert times == [10, 25, 40] and temps == [19.0, 20.0, 22.0]
    assert setpoint_at(9) is None and setpoint_at(10) == 19.0
    assert setpoint_at(39) == 20.0 and setpoint_at(1000) == 22.0
    assert floor_index(times, 25) == bisect.bisect_right(times, 25) - 1  # same thing, stdlib
    print("ok")

TypeScript

floor_index.ts

import assert from "node:assert/strict";

/** Index of the last time <= t in a sorted array, or -1 if every time is > t. */
function floorIndex(times: number[], t: number): number {
  let lo = 0, hi = times.length; // 1. search the half-open range [lo, hi)
  while (lo < hi) {
    const mid = (lo + hi) >>> 1;
    if (times[mid] <= t) lo = mid + 1; // 2. mid is a candidate; the answer is mid or later
    else hi = mid; // 3. mid is too new; the answer is before it
  }
  return lo - 1; // 4. lo = first index with time > t, so the floor is just before it
}

// A thermostat's setpoint history, kept sorted by time.
const times: number[] = [];
const temps: number[] = [];

function record(t: number, temp: number): void {
  const i = floorIndex(times, t);
  if (i >= 0 && times[i] === t) { temps[i] = temp; return; } // same instant: replace
  times.splice(i + 1, 0, t); // out-of-order writes land in the middle: O(n) shift
  temps.splice(i + 1, 0, temp);
}

function setpointAt(t: number): number | undefined {
  const i = floorIndex(times, t);
  return i < 0 ? undefined : temps[i];
}

for (const [t, temp] of [[10, 19], [40, 21.5], [25, 20], [40, 22]]) record(t, temp);
assert.deepEqual(times, [10, 25, 40]);
assert.deepEqual(temps, [19, 20, 22]);
assert.equal(setpointAt(9), undefined);
assert.equal(setpointAt(10), 19);
assert.equal(setpointAt(39), 20);
assert.equal(setpointAt(1000), 22);
console.log("ok");

C#

floor_index.cs

// Index of the last time <= t in a sorted list, or -1 if every time is > t.
static int FloorIndex(List<int> times, int t)
{
    int lo = 0, hi = times.Count; // 1. search the half-open range [lo, hi)
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (times[mid] <= t) lo = mid + 1; // 2. mid is a candidate; answer is mid or later
        else hi = mid;                     // 3. mid is too new; answer is before it
    }
    return lo - 1; // 4. lo = first index with time > t, so the floor is just before it
}

// A thermostat's setpoint history, kept sorted by time.
var times = new List<int>();
var temps = new List<double>();

void Record(int t, double temp)
{
    int i = FloorIndex(times, t);
    if (i >= 0 && times[i] == t) { temps[i] = temp; return; } // same instant: replace
    times.Insert(i + 1, t); // out-of-order writes land in the middle: O(n) shift
    temps.Insert(i + 1, temp);
}

double? SetpointAt(int t) { int i = FloorIndex(times, t); return i < 0 ? null : temps[i]; }

foreach (var (t, temp) in new[] { (10, 19.0), (40, 21.5), (25, 20.0), (40, 22.0) }) Record(t, temp);
if (!times.SequenceEqual([10, 25, 40]) || !temps.SequenceEqual([19.0, 20.0, 22.0])) throw new Exception("order");
if (SetpointAt(9) != null || SetpointAt(10) != 19.0) throw new Exception("before/at first");
if (SetpointAt(39) != 20.0 || SetpointAt(1000) != 22.0) throw new Exception("floor");
// List<T>.BinarySearch returns ~insertionPoint when absent; the hand-written loop is clearer.
Console.WriteLine("ok");

Standard-library floor searches

Python: bisect.bisect_right(times, t) - 1. C#: List<T>.BinarySearch returns the index if found, or the bitwise complement ~i of the insertion point if not; SortedList<K,V> also exposes its sorted Keys. TypeScript has no built-in, so write the eight-line loop above. Know which variant you need: bisect_right (first index > t) gives the floor; bisect_left (first index ≥ t) gives the ceiling.

Retention: dropping history nobody can read

Unbounded history grows forever. If reads are only allowed at or after some horizon (say, the last 30 days), versions older than the floor of the horizon can never be seen again. Keep the floor itself: a read exactly at the horizon still needs it.

Python

compact.py

def compact(times: list[int], vals: list[str], horizon: int) -> tuple[list[int], list[str]]:
    """Drop versions no read at time >= horizon can ever see.

    Keeps the version in effect at `horizon` (the floor) and everything after it.
    """
    keep_from = 0
    for i, t in enumerate(times):  # 1. find the floor of horizon (linear for clarity;
        if t <= horizon:  #    use binary search on long lists)
            keep_from = i
        else:
            break
    return times[keep_from:], vals[keep_from:]  # 2. older versions are unreachable


if __name__ == "__main__":
    ts, vs = [5, 10, 20, 30], ["a", "b", "c", "d"]
    assert compact(ts, vs, 25) == ([20, 30], ["c", "d"])  # a read at 25 needs "c"
    assert compact(ts, vs, 20) == ([20, 30], ["c", "d"])
    assert compact(ts, vs, 1) == (ts, vs)  # horizon before all versions: keep everything
    assert compact([], [], 9) == ([], [])
    print("ok")

TypeScript

compact.ts

import assert from "node:assert/strict";

/**
 * Drop versions no read at time >= horizon can ever see.
 * Keeps the version in effect at `horizon` (the floor) and everything after it.
 */
function compact(times: number[], vals: string[], horizon: number): [number[], string[]] {
  let keepFrom = 0;
  for (let i = 0; i < times.length && times[i] <= horizon; i++) keepFrom = i; // 1. floor of horizon
  return [times.slice(keepFrom), vals.slice(keepFrom)]; // 2. older versions are unreachable
}

const ts = [5, 10, 20, 30], vs = ["a", "b", "c", "d"];
assert.deepEqual(compact(ts, vs, 25), [[20, 30], ["c", "d"]]); // a read at 25 needs "c"
assert.deepEqual(compact(ts, vs, 20), [[20, 30], ["c", "d"]]);
assert.deepEqual(compact(ts, vs, 1), [ts, vs]); // horizon before all versions: keep everything
assert.deepEqual(compact([], [], 9), [[], []]);
console.log("ok");

C#

compact.cs

// Drop versions no read at time >= horizon can ever see.
// Keeps the version in effect at `horizon` (the floor) and everything after it.
static (int[] Times, string[] Vals) Compact(int[] times, string[] vals, int horizon)
{
    int keepFrom = 0;
    for (int i = 0; i < times.Length && times[i] <= horizon; i++) keepFrom = i; // 1. floor of horizon
    return (times[keepFrom..], vals[keepFrom..]); // 2. older versions are unreachable
}

int[] ts = [5, 10, 20, 30];
string[] vs = ["a", "b", "c", "d"];
var (t1, v1) = Compact(ts, vs, 25); // a read at 25 needs "c"
if (!t1.SequenceEqual([20, 30]) || !v1.SequenceEqual(["c", "d"])) throw new Exception("horizon 25");
if (!Compact(ts, vs, 20).Times.SequenceEqual([20, 30])) throw new Exception("horizon 20");
if (Compact(ts, vs, 1).Times.Length != 4) throw new Exception("keep everything");
if (Compact([], [], 9).Times.Length != 0) throw new Exception("empty");
Console.WriteLine("ok");

What it costs

Operation	Sorted array per key	Balanced tree / sorted map per key	Overwriting map (no history)
write, in time order	O(1) amortized append	O(log v)	O(1)
write, out of order	O(v) shift	O(log v)	O(1)
read latest	O(1) (last element)	O(log v)	O(1)
read at t	O(log v)	O(log v)	impossible
history of a key	O(v)	O(v)	impossible
snapshot of all k keys at t	O(k log v)	O(k log v)	impossible
memory	every version	every version + node overhead	latest only

Most real workloads write in time order, so the sorted array with append is the default. Reach for a tree (.NET SortedDictionary, Python’s third-party sortedcontainers) only when out-of-order writes are common and lists are long.

A whole-store snapshot at t costs one floor search per key. If that query is frequent and keys are many, consider also keeping a global, time-ordered change log, or periodic checkpoints (see snapshots).

Variations you’ll meet

• Version numbers instead of times. Each write bumps a global counter, and “version 7” is a point in time. Same floor search, just on integers you hand out.
• Optimistic concurrency. “Update only if the version is still 7” (compare-and-set). The version number doubles as a conflict detector, the way HTTP ETag / If-Match and database row versions work.
• MVCC. Databases like PostgreSQL keep multiple row versions so a reader sees a consistent snapshot as of its start time, while writers create new versions. Old versions are cleaned up later (PostgreSQL’s VACUUM).
• Bitemporal data. Two time axes: when something was true in the world (valid time) and when the system learned it (transaction time). Needed for “what did we believe on March 1 about February?”
• Range queries over history. Changes in [t1, t2]: bisect_left(t1) to bisect_right(t2), a count in O(log v).
• Event sourcing. Store the events and derive the value by replay. Versioning is the cached result of that replay per key.

Pitfalls

• Floor vs ceiling. “Value at t” wants the last version ≤ t. Using bisect_left gives the first ≥ t, which is wrong whenever there’s no version exactly at t.
• Equal timestamps. Two writes to the same key at the same t: replace, keep both in arrival order, or reject? Ask. Your binary search must agree with the choice.
• Appending out-of-order writes. If you always append, the list is no longer sorted and binary search silently returns garbage.
• Treating a tombstone as “not found” in history. A tombstone hides the value for reads after it, but it is still a version: it belongs in history listings and change counts.
• Before the first version. Index -1. Don’t let it wrap around to the last element (a classic Python bug: values[-1]).
• Mutable values. Storing a reference to a list or dict as a version means a later mutation rewrites history. Store immutable values or copies.

In the interview

• Ask: “Can writes arrive out of order? Can two writes share a timestamp, and if so who wins? Is a delete a version? Do I need full history or only point reads?”
• Say: “Each key maps to a list of versions sorted by timestamp. A read at t is a floor search: binary search for the first timestamp greater than t, then step back one.”
• Give costs for both cases: append in order is O(1), out-of-order insert is O(v) in an array, reads are O(log v).
• Expect follow-ups: deletes and history, counts of changes in a time range, a snapshot of every key at t, memory limits (retention and compaction), and making it concurrent.

Check yourself

Check yourself

pick one

A key has versions at times [10, 25, 40]. What does a read at t = 30 return, and what does bisect_right(times, 30) return?

AThe version at 40; bisect_right returns 2BThe version at 25; bisect_right returns 2CThe version at 25; bisect_right returns 1DNothing; 30 is not a stored time

Check yourself

pick one

Versions: 5 → 'a', 12 → tombstone, 20 → 'b'. What do reads at t=4, t=12 and t=15 return?

A'a', 'a', nothingBnothing, nothing, nothingCnothing, nothing, 'a'D'a', nothing, 'b'

Check yourself

pick one

Writes for one key always arrive in increasing time order. What's the cost of n writes followed by one point-in-time read?

AO(n²) + O(log n)BO(n) + O(log n)CO(n log n) + O(1)DO(n) + O(n)

Practice on your own

These are classic exercises, not gym questions:

• Stock price history: record trades with timestamps, answer “last trade price at time t” and “how many trades between t1 and t2”.
• A feature-flag service that answers “was this flag on for this user at time t?”, with rules that change over time.
• An array of n integers supporting set(i, v), checkpoint() → id and get(i, id) without copying the array on each checkpoint.
• Git-style blame for a list of lines: for each line, which version last changed it?

Go deeper

• Python bisect docs, including “Searching Sorted Lists” recipes for floor and ceiling.
• .NET List<T>.BinarySearch and its complement-of-insertion-point return value.
• PostgreSQL docs, “Concurrency Control: Introduction”: multi-version concurrency control in a production database.
• Martin Kleppmann, Designing Data-Intensive Applications, ch. 7: snapshot isolation and MVCC.

Related

Binary searchFloor, ceiling and the half-open loop.

Snapshots, backup and restoreWhole-store copies vs per-key versions.

Sorted containersWhen out-of-order writes are the norm.

Time handlingTimestamps, ties and boundaries.