Time-versioned key-value store

Q: How is this different from the LeetCode time-based store?

The classic version guarantees timestamps arrive strictly increasing and has no delete, so an append plus binary search is enough. Allowing late writes, overwrites and tombstones is closer to real systems: clocks on different writers disagree, retried writes arrive late, and deletes must not erase history.

Q: How would this look in Go, and in production?

In Go: map[string][]version, where version has a ts int64, a value any and a deleted bool flag instead of a sentinel. Look up with sort.Search, and append in the common case. Production systems must also bound history. etcd compacts revisions older than a retention point, and MVCC databases vacuum versions no transaction can still see. Without compaction, memory grows forever.

mediumRouting and distribution

Build a key-value store that keeps every version of each key, so you can ask what a value was at any point in time. It is how you answer "what was the replica count of this deployment when the incident started at 14:02?", and the same idea underlies etcd revisions and MVCC databases.

API (Java: long timestamps, values are Object, getLatest)

◈ DIAGRAM

VersionedStore()
put(key: str, value, ts: int) -> None
delete(key: str, ts: int) -> None
get(key: str, ts: int) -> value or None     # value as of time ts
get_latest(key: str) -> value or None

Rules

get(key, ts) returns the value of the version with the greatest timestamp <= ts. If there is none, return None.
delete(key, ts) records a tombstone at ts. Reads at or after ts, until the next put, return None. Older reads still see older values.
Writes may arrive out of order: a put at 150 after a put at 200 is valid and must be visible to reads between 150 and 199.
Two writes to the same key at the same timestamp: the later call wins, whether it is a put or a delete.
get_latest returns the version with the highest timestamp, or None if that version is a tombstone.
get must be O(log v) for v versions of the key. In-order writes, the common case, should be O(1).

Outputs are the return values of the get and get_latest calls, in order.

Examples

Example 1

Input: s.put("replicas", 3, 100) s.put("replicas", 5, 200) s.put("replicas", 4, 150) # late write s.get("replicas", 99) s.get("replicas", 100) s.get("replicas", 175) s.get("replicas", 1000) s.delete("replicas", 300) s.get("replicas", 301) s.get("replicas", 250) s.put("replicas", 6, 200) # same timestamp: overwrite s.get("replicas", 250) s.get_latest("replicas")

Output: null 3 4 5 null 5 6 null

Explanation: The late write at 150 is found by the read at 175. The tombstone at 300 hides the value from later reads, and makes the latest version "deleted".

Example 2

Input: s.get("missing", 5) s.put("image", "api:v1", 10) s.get_latest("image") s.delete("image", 5) # tombstone older than the value s.get("image", 7) s.get("image", 10) s.get_latest("image")

Output: null api:v1 null api:v1 api:v1

Explanation: A delete only affects reads from its own timestamp until the next newer version.

Hints

Approach

Keep each key's versions sorted by timestamp.

Python: two parallel lists, times and values. A write newer than the last timestamp is appended in O(1). A late write uses bisect_left to find its slot, overwriting if the timestamp already exists and inserting otherwise. Insertion shifts elements, O(v), but only for out-of-order writes.
Java: a TreeMap<Long, Object> per key. put is O(log v) in every case, and floorEntry(ts) returns the greatest timestamp <= ts directly.

A read is bisect_right(times, ts) - 1: the index of the last version at or before ts, or -1 if none exists. A delete writes a _TOMBSTONE sentinel, so reads before the delete still see the old value, and it follows the same last-write-wins rule as a put.

ComplexityTime O(log v) get; O(1) in-order put (Python), O(log v) put (Java)Space O(total versions)

Python

import bisect
 
_TOMBSTONE = object()     # "deleted at this timestamp"
 
 
class VersionedStore:
    def __init__(self):
        self.times = {}       # key -> sorted list of timestamps
        self.values = {}      # key -> values, parallel to times[key]
 
    def _write(self, key, value, ts):
        times = self.times.setdefault(key, [])
        values = self.values.setdefault(key, [])
        if not times or ts > times[-1]:          # the common case: in-order write, O(1)
            times.append(ts)
            values.append(value)
            return
        i = bisect.bisect_left(times, ts)
        if i < len(times) and times[i] == ts:    # same timestamp: last write wins
            values[i] = value
        else:                                    # late write: insert in place
            times.insert(i, ts)
            values.insert(i, value)
 
    def put(self, key, value, ts):
        self._write(key, value, ts)
 
    def delete(self, key, ts):
        self._write(key, _TOMBSTONE, ts)
 
    def get(self, key, ts):
        times = self.times.get(key)
        if not times:
            return None
        i = bisect.bisect_right(times, ts) - 1   # last version with time <= ts
        if i < 0:
            return None
        v = self.values[key][i]
        return None if v is _TOMBSTONE else v
 
    def get_latest(self, key):
        values = self.values.get(key)
        if not values or values[-1] is _TOMBSTONE:
            return None
        return values[-1]

Follow-up questions

Add compact(before_ts) that drops versions no read at or after before_ts can see, keeping exactly one version at or before it.
Return all keys as of time ts (a point-in-time snapshot).
Timestamps come from different machines with clock skew. What goes wrong, and what would you use instead? (Logical clocks or a single sequencer.)

Frequently asked questions

The classic version guarantees timestamps arrive strictly increasing and has no delete, so an append plus binary search is enough. Allowing late writes, overwrites and tombstones is closer to real systems: clocks on different writers disagree, retried writes arrive late, and deletes must not erase history.

In Go: map[string][]version, where version has a ts int64, a value any and a deleted bool flag instead of a sentinel. Look up with sort.Search, and append in the common case. Production systems must also bound history. etcd compacts revisions older than a retention point, and MVCC databases vacuum versions no transaction can still see. Without compaction, memory grows forever.