Time-based key-value store

Why this matters

A key-value store is a program that saves values under names. You give it a key, such as a user name or a setting name, and a value, such as the user's city or the setting's text. Later you ask for the value under that key. Most people meet one every day, in a phone's contact list or a web app's saved settings.

A plain key-value store keeps only the newest value for each key. Once you overwrite a value, the old one is gone. Some tasks need the old values too. A feature flag system may need to know which setting was active at 9:00 yesterday. An audit log needs to know what a price was when an order was placed. A configuration service may need to roll back to the value that was live at a given moment.

This lesson builds a store that keeps every version of each value and answers questions about the past. The main tool is a binary search, which finds an item in a sorted list by checking the middle, then the half that remains. This lesson assumes you know what a sorted list is.

Start with a plain map

A C++ std::unordered_map stores one value for each key. Suppose a program sets the key color to red, then later sets it to blue.

std::unordered_map<std::string, std::string> store;
store["color"] = "red";
store["color"] = "blue";

After the second line, the value red is gone. Looking up color now gives blue, no matter when you ask. If someone asks "what was the color at time 4", the store has no answer, because it does not record times at all.

The fix is to store more than one value per key. Each value needs a time next to it. A key then holds a list of pairs, where each pair is a time and a value.

Here is the same history with times added:

• At time 1, color becomes red.
• At time 5, color becomes blue.
• At time 9, color becomes green.

The time is a plain integer. It can be seconds since a start date, a counter, or any number that goes up as time passes. This lesson uses small numbers so the examples are easy to follow.

The idea: a time-ordered list per key

Each key maps to a list of versions. A version is one saved value together with the time it was set. The list for color holds three versions: (1, red), (5, blue) and (9, green). The list is ordered by time.

Two operations use this list.

• set adds a new version to the end of the key's list. Because new versions arrive with later times, the list stays in time order without any extra work.
• get takes a key and a time, and returns the value of the latest version whose time is at or before the given time. It must find the right version without scanning the whole list.

The second operation is the interesting one. For get("color", 4), the version at time 1 is at or before 4, and the version at time 5 is not. The answer is red, because red was set at time 1 and nothing newer existed by time 4.

For get("color", 5), the version at time 5 counts, because "at or before" includes the same time. The answer is blue.

For get("color", 0), no version was set by time 0. The answer is an empty string, which is the convention this lesson uses for "no value".

Finding the latest version with a binary search

Because the list is sorted by time, you can use a binary search. Here is the search for get("color", 4) on the times 1, 5 and 9.

Ask a different question first. Find the position of the first version whose time is greater than 4. That is the version at time 5, at position 1. Every version before position 1 has a time at or before 4. The version just before that position, at position 0, is the answer.

This question has a standard name in the library. std::ranges::upper_bound returns the first position where the value is greater than the target. Here is the trace for four different queries.

For query 5, the first position with a larger time is position 2, because time 5 is not greater than 5. So the position just before is 1, and the answer is blue. That is why the search uses the "greater than" boundary instead of "equal or greater". An equal time must count as a match.

The search takes about log base 2 of n steps, where n is the number of versions for that key. For a key with one million versions, that is about 20 steps. Scanning the list from the start would take up to one million steps.

Writing the store

The class below has one map from key to list of versions. The Version struct is placed before the map so the code reads from top to bottom.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <unordered_map>
#include <vector>
 
class TimeMap {
public:
    void set(const std::string& key, const std::string& value, int timestamp) {
        history_[key].push_back({timestamp, value});
    }
 
    std::string get(const std::string& key, int timestamp) const {
        auto found = history_.find(key);
        if (found == history_.end()) {
            return "";
        }
        const std::vector<Version>& versions = found->second;
        auto after = std::ranges::upper_bound(versions, timestamp, {}, &Version::time);
        if (after == versions.begin()) {
            return "";
        }
        return std::prev(after)->value;
    }
 
private:
    struct Version {
        int time;
        std::string value;
    };
 
    std::unordered_map<std::string, std::vector<Version>> history_;
};
 
int main() {
    TimeMap store;
    store.set("color", "red", 1);
    store.set("color", "blue", 5);
    store.set("color", "green", 9);
 
    std::cout << "get color at 0: [" << store.get("color", 0) << "]\n";
    std::cout << "get color at 1: " << store.get("color", 1) << '\n';
    std::cout << "get color at 4: " << store.get("color", 4) << '\n';
    std::cout << "get color at 5: " << store.get("color", 5) << '\n';
    std::cout << "get color at 100: " << store.get("color", 100) << '\n';
    std::cout << "get size at 3: [" << store.get("size", 3) << "]\n";
}

Three details in the code need explaining.

The &Version::time argument is a projection. It tells upper_bound to compare only the time field of each version with the target time. Without it, the search would try to compare a whole Version with an int, which does not compile.

The {} after the target is the default comparison, meaning "less than". It tells the search that the list is sorted from smallest to largest time.

The std::prev(after) call steps back one position. The code checks after == versions.begin() first. If the search returns the first position, there is no earlier version, and calling std::prev on the first position would step off the front of the list, which is undefined behavior.

Save the code as time_map.cpp. Compile and run the program with warnings turned on.

g++ -std=c++20 -Wall -o time_map time_map.cpp
./time_map

The output is:

get color at 0: []
get color at 1: red
get color at 4: red
get color at 5: blue
get color at 100: green
get size at 3: []

Each line matches the trace table above. The last line shows the case of a key that was never set. The store returns the empty string for it.

A second example: the same key set several times

This example follows the usual form of the problem. A key foo is set to bar at time 1, and then to bar2 at time 4. The question is what get returns at a few times. Two helper functions show the same search with the boundary chosen two different ways.

struct Version {
    int time;
    std::string value;
};
 
std::string get_upper(const std::vector<Version>& v, int t) {
    auto after = std::ranges::upper_bound(v, t, {}, &Version::time);
    if (after == v.begin()) return "";
    return std::prev(after)->value;
}
 
std::string get_lower(const std::vector<Version>& v, int t) {
    auto after = std::ranges::lower_bound(v, t, {}, &Version::time);
    if (after == v.begin()) return "";
    return std::prev(after)->value;
}

The program below runs both functions on the same list.

std::vector<Version> foo = {{1, "bar"}, {4, "bar2"}};
std::cout << "upper_bound: get(1)=" << get_upper(foo, 1)
          << " get(3)=" << get_upper(foo, 3)
          << " get(4)=" << get_upper(foo, 4)
          << " get(5)=" << get_upper(foo, 5) << '\n';
std::cout << "lower_bound bug: get(4)=" << get_lower(foo, 4)
          << " get(1)=" << get_lower(foo, 1) << '\n';

The output is:

upper_bound: get(1)=bar get(3)=bar get(4)=bar2 get(5)=bar2
lower_bound bug: get(4)=bar get(1)=

The upper_bound version gives the right answer at every time. The lower_bound version returns the wrong answer at both exact matches. At time 4 it returns bar, the old value, because lower_bound stops at the first position whose time is not less than 4, which is the version at time 4 itself. Stepping back one position then lands on the version at time 1. At time 1 it returns the empty string, for the same reason. The boundary decides whether an exact match counts, and it must count.

A third example: versions that arrive out of order

The usual problem promises that each key's times arrive in increasing order. Some systems do not promise that. A message can arrive late, or two servers can report at slightly different times. You can keep the list sorted by inserting each new version in the right place instead of at the end.

std::vector<Version> out_of_order;
for (auto [t, s] : std::vector<Version>{{9, "c"}, {1, "a"}, {5, "b"}}) {
    auto pos = std::ranges::upper_bound(out_of_order, t, {}, &Version::time);
    out_of_order.insert(pos, Version{t, s});
}
for (const auto& v : out_of_order) std::cout << '(' << v.time << ',' << v.value << ") ";
std::cout << '\n';
std::cout << "get(6)=" << get_upper(out_of_order, 6) << " get(0)=[" << get_upper(out_of_order, 0) << "]\n";

The output is:

(1,a) (5,b) (9,c) 
get(6)=b get(0)=[]

The insert uses the same upper_bound search as get. It finds the first position with a larger time and puts the new version just before it. The insert costs more than an append, because the vector may shift the later versions one place to the right. For a key with many versions, a late write therefore costs more than a normal write. Most workloads append in time order, so the simple push_back in the class above is the usual choice.

A fourth example: two keys with different histories

Each key has its own list, so the times of one key do not affect another. The program below sets two keys, with their versions interleaved in time.

TimeMap store;
store.set("theme", "light", 2);
store.set("mode", "beta", 3);
store.set("theme", "dark", 6);
store.set("mode", "stable", 8);
 
std::cout << "theme at 5: " << store.get("theme", 5) << '\n';
std::cout << "mode at 5: " << store.get("mode", 5) << '\n';
std::cout << "theme at 6: " << store.get("theme", 6) << '\n';
std::cout << "mode at 2: [" << store.get("mode", 2) << "]\n";
std::cout << "mode at 9: " << store.get("mode", 9) << '\n';

The output is:

theme at 5: light
mode at 5: beta
theme at 6: dark
mode at 2: []
mode at 9: stable

The theme list holds times 2 and 6, and the mode list holds times 3 and 8. A query for theme at time 5 finds only the version at time 2, even though mode was set at time 3 in between. A query for mode at time 2 has no version yet, because its first version is at time 3, so the store returns the empty string. The search for each query only looks at the list of the key that was asked about.

Common mistakes

Using lower_bound instead of upper_bound

This was shown in the second example. A query at an exact timestamp returns the version before it, not the one set at that time. Check the rule in your head with a small case: with a version at time 5, a query at time 5 must return that version.

Using [] inside a const get

Some programmers write get as a const member function (one that promises not to change the object), then use history_[key] to read the list. The [] operator on a std::unordered_map can add a new key, so it cannot be used in a const function. g++ 15 reports this error:

err_const_index.cpp: In member function ‘std::string TimeMap::get(const std::string&, int) const’:
err_const_index.cpp:15:38: error: passing ‘const std::unordered_map<std::__cxx11::basic_string<char>, std::vector<TimeMap::Version> >’ as ‘this’ argument discards qualifiers [-fpermissive]
   15 |         auto& versions = history_[key];
      |                                      ^

The fix is find, which looks up a key without adding one. The class above uses find in get for this reason.

Stepping back before the first version

If the query time is earlier than the first version, upper_bound returns the first position. Calling std::prev on that position goes before the start of the list. The after == versions.begin() check prevents this. Without that check the program has undefined behavior, which may appear to work on some inputs and crash on others.

Forgetting the missing key

A key that was never set has no list. Calling history_[key] in get would create an empty list for it, and the find in the class avoids that. The empty-key check returns the empty string before any search runs.

Scanning the whole list

A loop from the start of the list that stops when it passes the query time gives the right answer. It is slow when a key has many versions, because each lookup reads every version up to the query time. For the store to handle many versions per key, the binary search is required.

Practice

Exercise 1. Using the color history from the first example, what does get("color", 7) return? Explain your answer in one sentence.

Show the answer

It returns blue. The versions are at times 1, 5 and 9. The last version at or before time 7 is the one at time 5, which is blue. The version at time 9 is later than 7, so it does not count.

Exercise 2. Write a function count_at_or_before that takes a sorted vector of versions and a time, and returns how many versions have a time at or before that time. Use std::ranges::upper_bound. Then run it on the versions at times 1, 4 and 9 for the query times 0, 4 and 8.

Show the answer

The first position with a larger time is the number of versions at or before the query, because every version before that position qualifies. The function returns the distance from the start of the vector to that position.

std::size_t count_at_or_before(const std::vector<Version>& versions, int t) {
    auto after = std::ranges::upper_bound(versions, t, {}, &Version::time);
    return static_cast<std::size_t>(std::distance(versions.begin(), after));
}

With the versions at 1, 4 and 9, the function returns 0 for time 0, 2 for time 4 and 2 for time 8. Query 0 has no version at or before it. Query 4 includes times 1 and 4. Query 8 includes times 1 and 4, because the next version is at time 9.

Exercise 3. Explain in two or three sentences why set can use push_back without checking the list, and what goes wrong for get if a version is appended with a time smaller than the last one.

Show the answer

Under the usual rule, each new version has a time later than all earlier versions of the same key, so appending keeps the list sorted. If a version with time 5 is appended after one with time 9, the list becomes 1, 9, 5. The binary search assumes a sorted list, so on that list get may return the wrong version. The out-of-order example above avoids this by inserting at the right position.

Exercise 4. A key has versions at times 1 and 4, with values bar and bar2. Give the result of get_upper at times 0, 3 and 4 in one line each, and say which step of the search causes the answer at time 4.

Show the answer

At time 0, the result is the empty string, because no version is at or before 0. At time 3, the result is bar, because the version at time 4 is later than 3. At time 4, the result is bar2. The upper_bound search returns the position of the first version with a time greater than 4, which is the end of the list. Stepping back one position gives the version at time 4.

Exercise 5. A system has one million versions for a single key and receives one million get calls on it. Explain how the cost of the lookups changes between a linear scan from the start and the binary search, using the numbers from this lesson.

Show the answer

A binary search takes about 20 steps for one million versions, because 2 to the power 20 is about one million. One million lookups then take about 20 million steps. A linear scan can take up to one million steps for each lookup, so the same calls take up to about one trillion steps. The binary search is about fifty thousand times fewer steps in the worst case.

Summary

• A plain map keeps only the newest value, so the store keeps a time-ordered list of versions for each key.
• set appends a version. When times arrive in order, this keeps the list sorted with no search.
• get uses upper_bound on the time, then steps back one position to find the latest version at or before the query time.
• The boundary must be upper_bound, so that a version set at exactly the query time counts.
• The search takes about log base 2 of the number of versions for the key, which is far fewer steps than a scan.
• Check for the first position before stepping back, and use find instead of [] when reading a key from a const function.