DSA A Time-Based Key-Value Store

The problem

A time-based key-value store is a data structure with two operations. The set operation stores a value under a key together with a timestamp. The get operation asks for a key at a timestamp and returns the value from the latest set at or before that timestamp, or an empty string when no such set exists.

Timestamps under one key arrive in rising order. Different keys keep separate timelines. The operation script below is the test this article runs against every design.

script = [
    ("set", "love", "high", 10),
    ("set", "love", "low", 20),
    ("set", "foo", "bar", 5),
    ("get", "love", 5, ""),
    ("get", "love", 10, "high"),
    ("get", "love", 15, "high"),
    ("get", "love", 20, "low"),
    ("get", "love", 25, "low"),
    ("get", "foo", 7, "bar"),
    ("get", "missing", 9, ""),
]
for op in script:
    print(op)

Read the gets one at a time. A get at time 15 returns the value set at time 10, because 10 is the largest stored time at or before 15. That largest time has a name, the floor, and the whole design turns on finding floors fast.

Intuition: one big list of every set

The first design keeps one list of every set ever made. Each entry holds its key, its value, and its timestamp. A get then walks the list and keeps the best floor it has seen for the asked key.

The design is correct. Its cost is the trap. Every get pays for every set, including sets under keys the get never asked about.

entries = []

def set_value(key, value, timestamp):
    entries.append((key, value, timestamp))

def get_value(key, timestamp):
    scanned = 0
    best_time = -1
    best_value = ""
    for k, v, t in entries:
        scanned += 1
        if k == key and t <= timestamp and t > best_time:
            best_time = t
            best_value = v
    return best_value, scanned

set_value("love", "high", 10)
set_value("love", "low", 20)
set_value("foo", "bar", 5)
value, scanned = get_value("love", 15)
print("get love at 15:", repr(value), "entries scanned:", scanned)
value, scanned = get_value("foo", 7)
print("get foo at 7:", repr(value), "entries scanned:", scanned)

A get for foo scanned the love entries too. The list mixes every key's timeline into one pile. Separating the timelines is the fix, and searching one timeline fast is the rest of it.

Brute force: the one-list design, counted

The brute force is the one-list design, written as a class. A class groups the data and the two operations that use it. The get scans the whole list on every call and counts its scans.

class NaiveStore:
    def __init__(self):
        self.entries = []
        self.scanned = 0

    def set(self, key, value, timestamp):
        self.entries.append((key, value, timestamp))

    def get(self, key, timestamp):
        best_time = -1
        best_value = ""
        for k, v, t in self.entries:
            self.scanned += 1
            if k == key and t <= timestamp and t > best_time:
                best_time = t
                best_value = v
        return best_value

store = NaiveStore()
store.set("love", "high", 10)
store.set("love", "low", 20)
store.set("foo", "bar", 5)
for key, t in [("love", 5), ("love", 10), ("love", 15), ("love", 20), ("love", 25), ("foo", 7), ("missing", 9)]:
    print("get", key, "at", t, "->", repr(store.get(key, t)))
print("total entries scanned:", store.scanned)

Seven gets scanned twenty-one entries on a three-set store. The scan count is the number of gets times the number of sets. A busy store makes both numbers large at once.

The optimal solution: one sorted timeline per key

A floor is the largest stored time at or before the asked time, and keeping each key's times in a sorted list of its own lets a binary search find that floor directly. That one sentence is the whole design.

Each key owns two parallel lists, one for times and one for values. Rising arrival order means a set simply appends to both lists. The bisect module from the standard library supplies the binary search over the times.

from bisect import bisect_right

class TimeStore:
    def __init__(self):
        self.times = {}
        self.values = {}

    def set(self, key, value, timestamp):
        if key not in self.times:
            self.times[key] = []
            self.values[key] = []
        self.times[key].append(timestamp)
        self.values[key].append(value)

    def get(self, key, timestamp):
        if key not in self.times:
            return ""
        index = bisect_right(self.times[key], timestamp) - 1
        if index < 0:
            return ""
        return self.values[key][index]

store = TimeStore()
store.set("love", "high", 10)
store.set("love", "low", 20)
store.set("foo", "bar", 5)
expected = ["", "high", "high", "low", "low", "bar", ""]
queries = [("love", 5), ("love", 10), ("love", 15), ("love", 20), ("love", 25), ("foo", 7), ("missing", 9)]
for (key, t), want in zip(queries, expected):
    result = store.get(key, t)
    print("get", key, "at", t, "->", repr(result), "expected:", repr(want), "match:", result == want)

Every query in the script passes. The get touches only the asked key's timeline. Sets under other keys cost it nothing.

Walkthrough: the love timeline, step by step

The walk runs the script's sets first, then its love gets one by one. The state after the sets is two timelines. Each get shows its insertion point, the position where its timestamp would slot into the sorted times.

from bisect import bisect_right

times = {}
values = {}

def do_set(key, value, timestamp):
    times.setdefault(key, []).append(timestamp)
    values.setdefault(key, []).append(value)
    print("set", key, repr(value), "at", timestamp, "- times now:", times[key])

do_set("love", "high", 10)
do_set("love", "low", 20)
do_set("foo", "bar", 5)
for t in [5, 10, 15, 20, 25]:
    point = bisect_right(times["love"], t)
    floor_index = point - 1
    result = values["love"][floor_index] if floor_index >= 0 else ""
    print("get love at", t, "- insertion point:", point, "floor index:", floor_index, "->", repr(result))

The floor index is always one left of the insertion point. At time 5 the floor index is -1, which is the design's way of saying no set is early enough. The empty string answers that case.

Complexity

A set appends to one key's two lists, so its time is O(1). A get runs one binary search over that key's stored times, so its time is O(log k) for k sets under the key.

The store holds every set exactly once across all timelines, so its space is O(n) for n sets. The naive design holds the same data, and pays its extra cost in get time instead.

def binary_steps(k):
    steps = 0
    size = k
    while size >= 1:
        steps += 1
        size //= 2
    return steps

for total_sets in [8, 64, 512]:
    print("sets stored:", total_sets, "naive get scans:", total_sets, "timeline get steps (all under one key):", binary_steps(total_sets))

At 512 sets the naive get scans 512 entries. The timeline get takes ten steps in the worst case, where every set sits under the one asked key. Real stores spread sets across keys, which only shortens each timeline.

Edge cases and pitfalls

The classic mistake is forgetting the minus one after the binary search. The search returns the insertion point, one past the floor. Reading the value at the insertion point returns the next set's value, or falls off the end of the list.

A set at exactly the asked time counts. At or before includes equality, and the search used here lands after any equal entries, so an exact-time get finds its own set.

from bisect import bisect_right

class TimeStore:
    def __init__(self):
        self.times = {}
        self.values = {}

    def set(self, key, value, timestamp):
        if key not in self.times:
            self.times[key] = []
            self.values[key] = []
        self.times[key].append(timestamp)
        self.values[key].append(value)

    def get(self, key, timestamp):
        if key not in self.times:
            return ""
        index = bisect_right(self.times[key], timestamp) - 1
        if index < 0:
            return ""
        return self.values[key][index]

store = TimeStore()
print("get on an empty store:", repr(store.get("love", 10)))
store.set("love", "high", 10)
print("before the first set:", repr(store.get("love", 9)))
print("at exactly the set time:", repr(store.get("love", 10)))
print("a missing key:", repr(store.get("hate", 99)))
store.set("love", "low", 20)
print("between sets, far later key time:", repr(store.get("love", 1000)))

The design rests on one promise from the spec. Timestamps under a key arrive in rising order, so appends keep the times sorted. A store that cannot promise that order must sort or insert in position, and pay for it in set time.