Time-travel key-value store

You’ll recognise it when

• Each set carries a timestamp, and get(key, t) asks for the value as of time t.
• The answer is “the latest write at or before t”, and before the first write there is no value.
• Old versions must stay readable after newer writes and after deletes.
• Follow-ups ask about out-of-order timestamps, two writes at the same time, an injectable clock, or many threads.

It’s often confused with a plain dict that overwrites. The overwrite loses the past; this store keeps every version and turns each read into a binary search.

The idea

Think of the dated stamps in a passport. To know which visa was valid on a given day, you find the last stamp on or before that day. You never erase an old stamp; a cancellation is just another stamp.

Per key, keep two parallel lists in time order: times and values. A read is a floor lookup: the last position whose time is <= t. Python’s bisect_right(times, t) returns the position just after every time <= t, so subtracting one gives exactly that write, or -1 if there’s none. A delete appends a tombstone (a value of None) instead of erasing, so reads before the delete still see the old value.

How it works

1. Find the slot. For set(key, value, t), compute i = bisect_right(times, t). It’s the position after every existing write at a time <= t, including any at exactly t.
2. Insert at the slot, in both times and values. When writes arrive in time order, i is the end and this is an append. When an older timestamp shows up late, it slides into its place. Because i is after equal times, a second write at the same time lands after the first: the later call wins.
3. Delete is a write. delete(key, t) writes None at t the same way.
4. Read. get(key, t) computes bisect_right(times, t) - 1. A negative index means no write by then; otherwise return the value there, which is None after a delete.

Follow one key, door:

Why it’s correct: times stays sorted after every insert, and equal times keep the order of the calls. So for any t, the entry just before bisect_right(times, t) is the write with the largest time <= t, latest call first among equals. That’s the definition of the value at t.

from bisect import bisect_right


class TimeMap:
    """Every version of every key. Writes may arrive out of time order."""

    def __init__(self):
        self.times = {}     # key -> sorted write times
        self.values = {}    # key -> value written at the same position (None = deleted)

    def _write(self, key, value, t):
        times = self.times.setdefault(key, [])
        values = self.values.setdefault(key, [])
        i = bisect_right(times, t)       # after any equal time: the later call wins
        times.insert(i, t)
        values.insert(i, value)

    def set(self, key, value, t):
        self._write(key, value, t)

    def delete(self, key, t):
        self._write(key, None, t)        # a tombstone keeps older versions readable

    def get(self, key, t):
        times = self.times.get(key, [])
        i = bisect_right(times, t) - 1   # the last write at or before t
        return self.values[key][i] if i >= 0 else None

#include <algorithm>
#include <optional>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

// Every version of every key. Writes may arrive out of time order.
class TimeMap {
    unordered_map<string, vector<long long>> times;           // key -> sorted write times
    unordered_map<string, vector<optional<string>>> values;   // same positions; nullopt = deleted

    void write(const string& key, optional<string> value, long long t) {
        auto& ts = times[key];
        auto& vs = values[key];
        size_t i = upper_bound(ts.begin(), ts.end(), t) - ts.begin();   // after equal times: the later call wins
        ts.insert(ts.begin() + i, t);
        vs.insert(vs.begin() + i, move(value));
    }

public:
    void set(const string& key, const string& value, long long t) { write(key, value, t); }

    void erase(const string& key, long long t) { write(key, nullopt, t); }   // a tombstone

    optional<string> get(const string& key, long long t) const {
        auto it = times.find(key);
        if (it == times.end()) return nullopt;
        const auto& ts = it->second;
        long i = upper_bound(ts.begin(), ts.end(), t) - ts.begin() - 1;   // the last write at or before t
        return i >= 0 ? values.at(key)[i] : nullopt;
    }
};

import java.util.*;

// Every version of every key. Writes may arrive out of time order.
class TimeMap {
    private final Map<String, List<Long>> times = new HashMap<>();     // key -> sorted write times
    private final Map<String, List<String>> values = new HashMap<>();  // same positions; null = deleted

    // The first position whose time is greater than t.
    private static int upperBound(List<Long> ts, long t) {
        int lo = 0, hi = ts.size();
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (ts.get(mid) <= t) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    private void write(String key, String value, long t) {
        List<Long> ts = times.computeIfAbsent(key, k -> new ArrayList<>());
        List<String> vs = values.computeIfAbsent(key, k -> new ArrayList<>());
        int i = upperBound(ts, t);              // after equal times: the later call wins
        ts.add(i, t);
        vs.add(i, value);
    }

    void set(String key, String value, long t) { write(key, value, t); }

    void delete(String key, long t) { write(key, null, t); }   // a tombstone

    String get(String key, long t) {
        List<Long> ts = times.get(key);
        if (ts == null) return null;
        int i = upperBound(ts, t) - 1;          // the last write at or before t
        return i >= 0 ? values.get(key).get(i) : null;
    }
}

Real clocks, tests and threads

• Inject the clock. Code that calls time.time() inside is hard to test. Take a clock argument that defaults to time.time, and tests pass a fake that returns whatever time they want.
• Clocks go backwards. Wall clocks get corrected and can jump back. If versions must be strictly increasing per key, either reject a write that isn’t newer than the last one, or nudge it to just after it (last + epsilon) and say which policy you chose.
• Threads. Two threads inserting into the same lists can corrupt them, and a reader can see times updated but not values. Guard each key’s lists with a lock (or one lock for the whole map to start with), and make the read and the insert each happen entirely under it.

Why it’s O(log v)

A read is one binary search over the key’s v versions: O(log v). A write finds its slot in O(log v), but inserting into the middle of a Python list or a vector shifts everything after it: O(v) in the worst case. When timestamps arrive in order, which is the common case, the insert is at the end and costs O(1) amortized.

In Java, a TreeMap<Long, String> per key with floorEntry(t) does the whole job in O(log v) either way. Space is one entry per write: O(total writes).

Common mistakes

i = bisect_left(times, t) - 1     # ✗ misses a write at exactly t
i = bisect_right(times, t) - 1    # ✓ includes it

times.append(t)                   # ✗ unsorted after a late write
times.insert(bisect_right(times, t), t)   # ✓ stays sorted

del self.times[key]               # ✗ the past disappears
self._write(key, None, t)         # ✓ a tombstone at time t

return values[bisect_right(times, t) - 1]          # ✗ -1 means the last one
return values[i] if i >= 0 else None               # ✓ nothing written yet

Variations

• Range queries. “Every version between t1 and t2” is a slice between two bisects: bisect_left(times, t1) and bisect_right(times, t2).
• Whole-store snapshots. “The whole store as of t” can be one floor lookup per key, or a global version counter where a snapshot just remembers the counter.
• Fields and TTLs. Store (value, expires_at) per version and check expiry in the same lookup. The in-memory database guide builds that.
• Trimming history. If only the last k versions or the last N days matter, drop old entries from the front when writing, and say what reads before that window return.
• Persistence. Append each write to a log on disk and rebuild the lists on startup; see serialization.

Climb the ladder

Our time-travel key-value problems in ladder order.

1. The value as of time t: the floor lookup on its own.
2. Library display shelves over time: versions and clears per key.
3. Time-Based Key-Value Store: the classic store with sorted timestamps.
4. Versioned store with real clocks and threads: out-of-order writes, an injectable clock, ordering policies and thread safety.