Time-based key-value store in Python

Why this matters

A key-value store is a dict that keeps one value for each key. A key is the name you look up, such as a user's setting. A value is what is stored under that name. A plain dict answers one question: what is the value now? Many real systems need a second question: what was the value at some earlier time?

Some examples. A settings service records that a user changed the theme from "light" to "dark" at 10:05, and an audit tool asks what the theme was at 10:00. A feature flag system keeps a history of when each flag was turned on. A document store keeps old versions so that a user can open the file as it was last Monday.

This lesson builds a small store with two methods, set and get. The set method records a value for a key at a timestamp. The get method returns the value that was current at a given time. The main idea is a sorted list of versions for each key, and a binary search to find the right version quickly.

A timestamp here is a plain whole number, such as seconds since the start of the test. Real systems often use large numbers, but the logic is the same.

The lesson uses two terms that a beginner may not know yet. A binary search is a way to find an item in a sorted list by checking the middle item and then throwing away the half that cannot contain the answer. Its cost is O(log n), which means the number of steps grows very slowly as the list grows. A list of one million items needs at most about 20 checks.

The problem in plain words

Design a class called TimeMap with two methods.

set(key, value, timestamp) records that key had value from timestamp onward. For any one key, the timestamps passed to set always increase. A later call always has a larger timestamp.
get(key, timestamp) returns the value stored with the newest timestamp that is at or before the given time. If the key has no version at or before that time, it returns an empty string.

"At or before" is the rule that matters most. A change made at time 4 is visible at time 4 itself, and at every later time until the next change.

Here is an example. Three calls store the mood of one key.

set("mood", "sad", 1)
set("mood", "ok", 4)
set("mood", "happy", 10)

Now look at what get returns:

get("mood", 0) returns "", because the first version starts at time 1.
get("mood", 1) returns sad.
get("mood", 3) returns sad, because the change to ok happened at time 4, which is later than 3.
get("mood", 4) returns ok, because the change happened exactly at time 4.
get("mood", 9) returns ok, because happy starts at time 10.
get("mood", 50) returns happy, because it is the newest version.

Keep this table in mind while reading the code. Each get answer is the last version whose timestamp is not larger than the query time.

Why simple approaches are slow

A plain dict from key to value holds only one value per key. Overwriting it would lose the history.

A dict from key to a list of versions keeps the history. The problem is the query. If you scan the list from the start and remember the last version that is not too new, the cost grows with the length of the history. A key that has been changed one million times costs one million checks for one query.

The fix uses the fact that the list is already sorted by time. Sorted order means a binary search can find the answer in about 20 checks for a list of one million items.

The idea step by step

The structure has two parts.

A dict from each key to a list of versions. Each version is a pair of a timestamp and a value. A tuple, a fixed group of values in round brackets, such as (4, "ok"), holds one version.
For each key, the list is in increasing timestamp order. This follows from the rule that timestamps for one key always increase.

Set

To set a value, find the list for the key. If there is no list yet, create an empty one. Then add the new version to the end of the list. Adding to the end of a list is fast, so set is constant time on average, apart from the dict lookup.

Here is the list for mood after the three calls from the example. The dict holds one entry, mood, and that entry points to the list:

mood: [(1, sad), (4, ok), (10, happy)]

The list is sorted by the first number in each pair, because each set call used a larger timestamp than the last one.

Get

To answer get(key, t), find the list for the key. Then find the last position in the list whose timestamp is not larger than t.

Look at the timestamps in the list as a row of numbers: 1, 4, 10. For a query time of 9, the numbers that are at or before 9 are 1 and 4. The last of them is 4, so the answer is the version at timestamp 4, which is ok.

The numbers are sorted, so the row has a clear split. Every number on the left of the split is at or before the query time, and every number on the right is after it. The binary search finds that split.

A worked binary search

Use the list [(1, sad), (4, ok), (10, happy)] and the query time 9. Keep three positions: low, high and mid. low and high mark the part of the list still in play. mid is the middle position in that part. Also keep answer, the best position found so far, starting at -1 which means "nothing found yet".

Start with low = 0 and high = 2, the first and last positions.

Step 1. mid = 1. The timestamp at position 1 is 4. Is 4 at or before 9? Yes. So position 1 is a candidate. Save answer = 1. Later positions might also qualify, so search the right side. Set low = 2.

Step 2. low is 2 and high is 2. mid = 2. The timestamp at position 2 is 10. Is 10 at or before 9? No. The right side is too late, so search the left side. Set high = 1.

Step 3. low is 2 and high is 1. low is now greater than high, so the search stops. The saved answer is position 1, which holds ok.

The program below prints each step for the same list and the query time 9:

Python · editable

low=0 high=2 mid=1 timestamp=4 atOrBefore=True
low=2 high=2 mid=2 timestamp=10 atOrBefore=False
answer index=1 value=ok

The rule for each step is short. If the middle timestamp is at or before the query time, remember this position and search to the right, because a later position might also be at or before the query time. If it is after the query time, search to the left.

The middle position is written as low + (high - low) // 2, not (low + high) // 2. In Python both forms give the same answer, because integers do not overflow. The first form is the one that is safe in languages with fixed-size integers, and it is a habit worth keeping.

The first program

The program below builds the store and runs the example from the start of this lesson, plus two extra checks. It also shows the error raised by a bad set call.

Python · editable

class TimeMap:
    def __init__(self):
        self.history = {}

def set(self, key, value, timestamp):
        versions = self.history.setdefault(key, [])
        if versions and timestamp <= versions[-1][0]:
            raise ValueError(f"timestamp {timestamp} must be greater than {versions[-1][0]}")
        versions.append((timestamp, value))

def get(self, key, timestamp):
        versions = self.history.get(key)
        if versions is None:
            return ""
        low, high = 0, len(versions) - 1
        answer = -1
        while low <= high:
            mid = low + (high - low) // 2
            if versions[mid][0] <= timestamp:
                answer = mid
                low = mid + 1
            else:
                high = mid - 1
        return "" if answer == -1 else versions[answer][1]

store = TimeMap()
store.set("mood", "sad", 1)
store.set("mood", "ok", 4)
store.set("mood", "happy", 10)

print("get(mood, 0) = [" + store.get("mood", 0) + "]")
print("get(mood, 1) =", store.get("mood", 1))
print("get(mood, 3) =", store.get("mood", 3))
print("get(mood, 4) =", store.get("mood", 4))
print("get(mood, 9) =", store.get("mood", 9))
print("get(mood, 50) =", store.get("mood", 50))
print("get(city, 5) = [" + store.get("city", 5) + "]")

store.set("city", "Pune", 2)
print("get(city, 1) = [" + store.get("city", 1) + "]")
print("get(city, 2) =", store.get("city", 2))

try:
    store.set("mood", "angry", 7)
except ValueError as error:
    print("error:", error)

get(mood, 0) = []
get(mood, 1) = sad
get(mood, 3) = sad
get(mood, 4) = ok
get(mood, 9) = ok
get(mood, 50) = happy
get(city, 5) = []
get(city, 1) = []
get(city, 2) = Pune
error: timestamp 7 must be greater than 10

The first six lines match the table from the start of the lesson. The line get(city, 5) = [] shows the case of a key that was never set. The brackets are printed by the program so that an empty string is visible. The last line shows the check in set. The key mood already had a version at time 10, so a new version at time 7 is refused.

The get method starts by looking up the key with self.history.get(key), which returns None for a missing key. The check for None must come first, before the code uses the list. The mistakes section shows what happens without it.

The set method uses setdefault, which returns the list for the key and creates an empty list when the key is new. It is a dict method, so it does the lookup and the insert in one call.

The second program: a stress test against a linear scan

The program below checks the store against a simple reference. The reference keeps the same versions in a plain list and scans the whole list for each query. The scan is slow for long histories, but it is easy to trust. The program makes 20,000 random steps. Some steps write a new version, and the others ask for a value at a random time. Any difference between the two answers counts as a mismatch.

Python · editable

import random

class TimeMap:
    def __init__(self):
        self.history = {}

def set(self, key, value, timestamp):
        versions = self.history.setdefault(key, [])
        if versions and timestamp <= versions[-1][0]:
            raise ValueError(f"timestamp {timestamp} is not increasing")
        versions.append((timestamp, value))

def linear_get(versions, timestamp):
    best = ""
    for ts, value in versions:
        if ts <= timestamp:
            best = value
    return best

rng = random.Random(99)
store = TimeMap()
reference = {}
keys = ["a", "b", "c"]
writes = 0
queries = 0
mismatches = 0
clock = 0

for step in range(20000):
    key = keys[rng.randrange(len(keys))]
    if rng.randrange(3) == 0:
        clock += 1 + rng.randrange(5)
        value = f"v{step}"
        store.set(key, value, clock)
        reference.setdefault(key, []).append((clock, value))
        writes += 1
    else:
        t = rng.randrange(clock + 5)
        if store.get(key, t) != linear_get(reference.get(key, []), t):
            mismatches += 1
        queries += 1

print("writes:", writes)
print("queries:", queries)
print("mismatches against linear scan:", mismatches)
print("last clock value:", clock)

writes: 6785
queries: 13215
mismatches against linear scan: 0
last clock value: 20490

Zero mismatches means that all 13,215 answers matched the slow scan. The clock only moves forward, so every set call follows the rule that timestamps increase. The counts depend on the seed and on the Python version, so your numbers may differ, but the mismatch count must be zero.

Notice that the stress test does not check the list directly. It checks the answers. That is the right test here, because the answers are what a user of the store sees.

Third example: a history that answers in few steps

The search above is fast even when a key has a very long history. Each step cuts the part still in play by about half. Here is the arithmetic. A list of 1,000,000 versions needs at most 20 steps, because 2 to the power of 20 is 1,048,576, which is more than one million. A list of 1,000 versions needs at most 10 steps, because 2 to the power of 10 is 1,024.

The same idea works with any starting list. The loop stops when low is greater than high, so it always finishes. The answer is the last position that passed the test, which is the newest version at or before the query time.

The standard library already has this search. The bisect module's bisect_right returns the position just after the last timestamp that is at or before the query. The newest version is the position before that one. For the list [1, 4, 10] and the query 9, bisect_right(times, 9) returns 2, so the answer is position 1, which holds ok. Exercise 2 checks this result with bisect_right.

A small change flips the search to find the first version at or after a time. The test becomes timestamp >= query. When the test passes, remember the position and search to the left, because an earlier position might also pass. When it fails, search to the right. The rest of the code stays the same. This is a useful pattern for other problems, such as finding the first item that is large enough in a sorted list.

Common mistakes

Returning the wrong version when a time is exactly on a change. A query at time 4 must return the version set at time 4, not the one before it. The test uses <=, so the version at exactly the query time counts. Changing it to < returns the previous value at that exact time. The first program's output line get(mood, 4) = ok shows the correct behaviour.

Forgetting the check for an unknown key. A dict raises KeyError for a key that was never set when you use square brackets, and get returns None. If the code calls a method on that None, Python stops with an error. This function reads the first version without the check:

def broken_get(history, key, timestamp):
    versions = history.get(key)
    return versions[0][1]
 
 
history = {"mood": [(1, "sad")]}
print(broken_get(history, "city", 1))

TypeError: 'NoneType' object is not subscriptable

The last line of the error says that the value is None, and the code tried to read an index from it. The fix is the same as in the first program: check for None first and return "". Square brackets raise a different error for the same mistake, KeyError: 'city', which names the missing key.

Allowing timestamps that go backwards. A set call with a timestamp at or before the last one breaks the sorted list, and the binary search then returns wrong answers. The first program refuses such calls. The error it prints is:

error: timestamp 7 must be greater than 10

Check the last timestamp before adding a new version, as the code does. Do not skip the check to save a line.

Scanning the list from the start. A loop from the first version to the last works, and it passes small tests. It becomes slow when a key has many versions, because every query reads the whole list. The linear scan in the second program is for checking only. The store itself uses the binary search.

Using a result without checking for the empty string. An empty string means "no version existed yet", and it is a real value that the store can return. A caller that treats it as a normal value will misread it. Decide what an empty result means in your program, and check for it.

Practice

Exercise 1. The key x has these versions in order: (2, "a"), (5, "b"), (9, "c"). What do these calls return: get("x", 4), get("x", 5), get("x", 1), get("x", 100)?

Show the answer

get("x", 4) returns a, because the newest version at or before 4 is the one at time 2. get("x", 5) returns b, because a change at time 5 is visible at time 5. get("x", 1) returns an empty string, because the first version starts at time 2. get("x", 100) returns c, because it is the newest version.

Exercise 2. Run the binary search by hand on the timestamps [3, 6, 8, 12] for the query time 7. Which position is the answer, and which timestamp does it hold?

Show the answer

The answer is position 1, which holds timestamp 6. Start with low = 0 and high = 3. The middle is mid = 1, timestamp 6, which is at or before 7, so save answer = 1 and set low = 2. The next middle is mid = 2 + (3 - 2) // 2 = 2, timestamp 8, which is after 7, so set high = 1. Now low is greater than high, and the search stops. The check with bisect_right([3, 6, 8, 12], 7) - 1 gives the same position, 1.

Exercise 3. The store has no versions for the key city. What must get("city", 5) return, and where in the code is that handled?

Show the answer

It must return an empty string. The get method handles this with the check on self.history.get(key), which returns early with "" when the key is missing.

Exercise 4. A key has 1,000,000 versions. What is the largest number of checks a single get can make, and why?

Show the answer

At most 20 checks. Each check halves the part of the list still in play. After 20 halvings, the part has fewer than one position left, because 2 to the power of 20 is 1,048,576, which is more than 1,000,000.

Exercise 5. Change the get method so that it returns the value of the first version whose timestamp is at or after the query time, and returns an empty string if there is none. Which comparison changes, and which direction does the search move when the test passes?

Show the answer

The test changes from <= to >=. When the test passes, save the position and move high to mid - 1, so the search continues to the left and looks for an earlier position that also passes. When the test fails, move low to mid + 1. The final line still returns an empty string when answer is still -1.

Summary

A time-based store keeps a list of versions for each key, and each list stays in increasing timestamp order because set only accepts later times.
A get call finds the last version at or before the query time, which is the newest version that was already in effect.
Binary search finds that version in about log n steps, because it throws away half of the remaining list each time.
A None check is needed for a key that was never set, and a check on timestamps prevents an unsorted list.
A stress test against a simple linear scan finds mismatches that a few hand-picked examples can miss.

Time-based key-value store in Python

Why this matters

The problem in plain words

Why simple approaches are slow

The idea step by step

Set

Get

A worked binary search

The first program

The second program: a stress test against a linear scan

Third example: a history that answers in few steps

Common mistakes

Practice

Summary

Stuck? Ask the tutor