~/systems/in-memory-database

In-memory database

Records of fields with scans, expiry, transactions and reads from the past. Keep every write, and answer everything through one lookup helper.

what

Store a history per field: a time-sorted list of (time, value or tombstone, expires_at). One helper finds the version in force at time t with a binary search and checks expiry; get, scans and past reads all call it.

use when

The multi-level database OA: set/get/delete on records and fields, then prefix scans, then TTLs, then backups or "value at time t", or nested transactions with rollback.

time

O(log v) per read, O(1) per write

space

O(total writes)

You’ll recognise it when

You build a store of records (a key) made of fields (name to value), with set, get and delete.
Every method takes a timestamp, even on levels where you don’t need it yet.
Later levels add scans sorted by field name, TTLs that make fields expire, backups, or “what was the value at time t”.
Or the store has transactions: begin, rollback, commit, possibly nested.

It’s often confused with a plain dict exercise, and level 1 is one. The real test is whether your level 1 design survives level 4 without a rewrite.

The idea

A careful accountant never rubs anything out. To change a figure, they add a new dated line below the old one. To delete, they add a line that says “closed”. Asking “what was this balance on March 3?” means finding the last line dated on or before March 3, and asking about today is the same question with today’s date.

Store the database the same way. For each field keep its history: the times it was written, and for each write the value (or a tombstone for a delete) and when it expires. Then write one helper, _value_at(key, field, t), that finds the last write at or before t and checks it hasn’t expired. get, delete, scans and reads from the past all call it. Expiry rules live in that one function, so a level that changes them edits one place.

How it works

Times only go up between calls, so appending keeps each field’s times list sorted, and the helper can binary search it.

Writes append. set(t, key, field, value, ttl) appends t to that field’s times, and (value, expires_at) to its entries, where expires_at is t + ttl, or forever without a TTL. A plain set therefore clears an old TTL automatically: the new entry has no expiry.
Deletes append too. delete first asks the helper whether the field is live at t; if not, it returns false. Otherwise it appends a tombstone, a None value. Nothing is ever erased, so the past stays readable.
One lookup. _value_at finds i, the last index with times[i] <= t, using bisect_right(times, t) - 1. No write yet, or a tombstone, means None. Otherwise the field is live only while t < expires_at: at exactly expires_at it’s already gone.
Scans reuse it. scan(t, key, prefix) walks the record’s field names in sorted order, keeps those with the prefix, and asks the helper for each value at t. Fields that expired or were deleted simply return None and drop out.
Reading the past is free. get_at(t, key, field, at) is the same helper called with at instead of t.

Walk through one record u1:

time	call	result
1, 2	set `name = ann`, set `city = oslo`
3	set `code = x7` with TTL 5	`expires_at` = 8
4	scan `u1`	`city(oslo), code(x7), name(ann)`
8	get `code`	none: expired exactly at 8
9, 10	set `name = bo`, delete `city`	delete returns true
11	scan `u1`	`name(bo)`
12	get `name` at 5, `city` at 9, `code` at 7	`ann`, `oslo`, `x7`

Why it’s correct: every write is kept in time order, and the helper returns exactly the last write at or before the moment asked about, unless that write was a delete or has expired. That’s the definition of the field’s value at that moment, for now and for the past alike.

from bisect import bisect_right

FOREVER = float("inf")


class FieldStore:
    """Records of fields. Every write is kept, so TTLs and past reads are lookups."""

    def __init__(self):
        # key -> field -> (times, entries); entries[i] = (value or None, expires_at)
        self.history = {}

    def _write(self, t, key, field, value, expires_at):
        times, entries = self.history.setdefault(key, {}).setdefault(field, ([], []))
        times.append(t)                    # calls come in time order, so this stays sorted
        entries.append((value, expires_at))

    def _value_at(self, key, field, t):
        # The one place that knows about versions, deletes and expiry.
        times, entries = self.history.get(key, {}).get(field, ((), ()))
        i = bisect_right(times, t) - 1     # the last write at or before t
        if i < 0:
            return None
        value, expires_at = entries[i]
        return value if t < expires_at else None

    def set(self, t, key, field, value, ttl=None):
        expires_at = FOREVER if ttl is None else t + ttl
        self._write(t, key, field, value, expires_at)

    def get(self, t, key, field):
        return self._value_at(key, field, t)

    def delete(self, t, key, field):
        if self._value_at(key, field, t) is None:
            return False
        self._write(t, key, field, None, FOREVER)   # a tombstone, not an erase
        return True

    def scan(self, t, key, prefix=""):
        live = []
        for field in sorted(self.history.get(key, {})):
            if field.startswith(prefix):
                value = self._value_at(key, field, t)
                if value is not None:
                    live.append(f"{field}({value})")
        return ", ".join(live)

    def get_at(self, t, key, field, at):
        return self._value_at(key, field, at)       # time travel is the same lookup

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

const long long FOREVER = LLONG_MAX;

// Records of fields. Every write is kept, so TTLs and past reads are lookups.
class FieldStore {
    struct Entry {
        optional<string> value;     // nullopt is a tombstone (a delete)
        long long expires_at;
    };
    struct History {
        vector<long long> times;    // calls come in time order, so this stays sorted
        vector<Entry> entries;
    };
    map<string, map<string, History>> history;   // key -> field -> versions

    void write(long long t, const string& key, const string& field, optional<string> value, long long expires_at) {
        History& h = history[key][field];
        h.times.push_back(t);
        h.entries.push_back({move(value), expires_at});
    }

    // The one place that knows about versions, deletes and expiry.
    optional<string> value_at(const string& key, const string& field, long long t) const {
        auto rec = history.find(key);
        if (rec == history.end()) return nullopt;
        auto f = rec->second.find(field);
        if (f == rec->second.end()) return nullopt;
        const History& h = f->second;
        long i = upper_bound(h.times.begin(), h.times.end(), t) - h.times.begin() - 1;  // last write at or before t
        if (i < 0) return nullopt;
        const Entry& e = h.entries[i];
        return t < e.expires_at ? e.value : nullopt;
    }

public:
    void set(long long t, const string& key, const string& field, const string& value, optional<long long> ttl = nullopt) {
        write(t, key, field, value, ttl ? t + *ttl : FOREVER);
    }

    optional<string> get(long long t, const string& key, const string& field) const {
        return value_at(key, field, t);
    }

    bool erase(long long t, const string& key, const string& field) {
        if (!value_at(key, field, t)) return false;
        write(t, key, field, nullopt, FOREVER);     // a tombstone, not an erase
        return true;
    }

    string scan(long long t, const string& key, const string& prefix = "") const {
        string out;
        auto rec = history.find(key);
        if (rec == history.end()) return out;
        for (auto& [field, h] : rec->second) {      // std::map keeps fields sorted
            if (field.rfind(prefix, 0) != 0) continue;
            if (auto value = value_at(key, field, t)) out += (out.empty() ? "" : ", ") + field + "(" + *value + ")";
        }
        return out;
    }

    optional<string> get_at(long long t, const string& key, const string& field, long long at) const {
        return value_at(key, field, at);             // time travel is the same lookup
    }
};

import java.util.*;

// Records of fields. Every write is kept, so TTLs and past reads are lookups.
class FieldStore {
    static final long FOREVER = Long.MAX_VALUE;

    record Entry(String value, long expiresAt) {}   // value == null is a tombstone (a delete)

    static class History {
        final List<Long> times = new ArrayList<>();  // calls come in time order, so this stays sorted
        final List<Entry> entries = new ArrayList<>();
    }

    private final Map<String, TreeMap<String, History>> history = new HashMap<>();   // key -> field -> versions

    private void write(long t, String key, String field, String value, long expiresAt) {
        History h = history.computeIfAbsent(key, k -> new TreeMap<>()).computeIfAbsent(field, f -> new History());
        h.times.add(t);
        h.entries.add(new Entry(value, expiresAt));
    }

    // The one place that knows about versions, deletes and expiry.
    private String valueAt(String key, String field, long t) {
        TreeMap<String, History> rec = history.get(key);
        History h = rec == null ? null : rec.get(field);
        if (h == null) return null;
        int lo = 0, hi = h.times.size();             // find the last write at or before t
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (h.times.get(mid) <= t) lo = mid + 1;
            else hi = mid;
        }
        if (lo == 0) return null;
        Entry e = h.entries.get(lo - 1);
        return t < e.expiresAt() ? e.value() : null;
    }

    void set(long t, String key, String field, String value, Long ttl) {
        write(t, key, field, value, ttl == null ? FOREVER : t + ttl);
    }

    String get(long t, String key, String field) {
        return valueAt(key, field, t);
    }

    boolean delete(long t, String key, String field) {
        if (valueAt(key, field, t) == null) return false;
        write(t, key, field, null, FOREVER);          // a tombstone, not an erase
        return true;
    }

    String scan(long t, String key, String prefix) {
        List<String> live = new ArrayList<>();
        for (String field : history.getOrDefault(key, new TreeMap<>()).keySet()) {   // sorted
            if (!field.startsWith(prefix)) continue;
            String value = valueAt(key, field, t);
            if (value != null) live.add(field + "(" + value + ")");
        }
        return String.join(", ", live);
    }

    String getAt(long t, String key, String field, long at) {
        return valueAt(key, field, at);               // time travel is the same lookup
    }
}

Transactions with an undo log

Nested transactions need a different trick: keep a stack with one undo list per open transaction. Before each change, record the key’s old value in the innermost list. Rollback pops that list and restores the old values in reverse order; commit clears the stack.

class TxStore:
    def __init__(self):
        self.data = {}
        self.undo = []                    # one list of (key, old value) per open transaction

    def set(self, key, value):
        if self.undo:
            self.undo[-1].append((key, self.data.get(key)))
        self.data[key] = value

    def begin(self):
        self.undo.append([])

    def rollback(self):
        if not self.undo:
            return False
        for key, old in reversed(self.undo.pop()):
            if old is None:
                self.data.pop(key, None)  # the key didn't exist before
            else:
                self.data[key] = old
        return True

Reads stay O(1) because the current state is always applied; only rollback pays, in proportion to the changes it undoes.

Why it’s O(log v)

A write appends to two lists: O(1) amortized. A read binary searches the field’s times, O(log v) for a field with v versions. A scan sorts the record’s field names, O(f log f) for f fields, plus one lookup each. Space is one entry per write ever made, so O(total writes). That’s the price of reading the past. If a later level never asks about the past, you can trim old versions; if it does, you can’t.

operation	cost
`set`, `delete`	O(1) amortized, plus one lookup for `delete`
`get`, `get_at`	O(log v)
`scan`	O(f log f + f log v)

Common mistakes

Expiry checked in some methods but not others

If get checks the TTL but scan and delete don’t, an expired field shows up in scans and can be “deleted”. Route every read through one helper.

value = self.data[key][field]                  # ✗ ignores expiry here
value = self._value_at(key, field, t)          # ✓ one place decides

An off-by-one on the expiry instant

A field set at 3 with TTL 5 lives during [3, 8). At exactly 8 it’s gone. Using <= keeps it one tick too long, and the tests always probe the boundary.

return value if t <= expires_at else None      # ✗ alive at 8
return value if t < expires_at else None       # ✓ gone at 8

Deleting by erasing history

del self.data[key][field] works until a level asks for the value at an earlier time; then the past is gone. Append a tombstone instead.

del self.history[key][field]                   # ✗ the past disappears
self._write(t, key, field, None, FOREVER)      # ✓ a dated "deleted" entry

Sorting scans by insertion or by value

“Sorted by field name” means string order of the names. Dict order is insertion order, which matches the tests only by luck.

for field in self.history[key]: ...            # ✗ insertion order
for field in sorted(self.history[key]): ...    # ✓ by name

Variations

Backup and restore. Save a copy of the live state with each field’s remaining lifetime, not its absolute expiry. On restore at a later time, each field expires that much after the restore.
Compare and set. compare_and_set(key, field, expected, new) writes only if the current value equals expected. It’s one lookup through the helper, then a normal write.
Counting values. “How many keys hold value v” in O(1): keep a Counter of values and update it on every change, including rollbacks.
Querying tables. A SQL-style layer stores rows as dicts, filters with a list of conditions, sorts with a key tuple (stable sorts keep insertion order on ties), and adds a value-to-rows index for equality filters.
Out-of-order times. If writes can arrive with older timestamps, append no longer keeps lists sorted. Insert in place with bisect.insort, as in the time-travel key-value store.

Climb the ladder

Our in-memory database problems in ladder order.

Records of fields in nested dicts: the data model and its edge cases.
Per-field undo in a record store: a history per field, read backwards.
Key-value store with nested transactions and rollback: O(1) counts and an undo log per transaction.
In-memory database: the full five-level OA, from fields to TTLs, backups and reads from the past.
In-memory table with SQL-style queries: filters, multi-column sorts and indexes.

Check yourself

5 quick questions. Pick an answer to see why it's right or wrong.

1
A field’s history is stored as parallel lists, oldest first. What does this print?
```
from bisect import bisect_right

times = [2, 5, 5, 9]
values = ["a", "b", "c", None]      # None is a delete

def at(t):
    i = bisect_right(times, t) - 1
    return values[i] if i >= 0 else "missing"

print(at(1), at(5), at(8), at(9))
```
bisect_right returns the position after every entry <= t, so subtracting 1 gives the last write at or before t. At 5 that’s the later of the two writes at 5, c, which is what “last write wins” means. At 1 nothing has been written yet. At 9 the latest entry is the delete.
2
A field is set at time 10 with a TTL of 5, so it lives during [10, 15). Which reads return its value?
The half-open interval includes 10 and excludes 15, so the field is live while t < 15. At exactly 15 it’s already gone. Statements spell this out because tests probe exactly that boundary, and <= instead of < is the usual slip.
3
Your store keeps a time-sorted history of writes per field so it can answer “value at time t”. How should delete(t, key, field) change that history?
A dated tombstone makes reads at or after t see nothing, while reads before t still find the old value. Removing the history, or the newest entry, rewrites the past: a read at an earlier time gives the wrong answer. Overwriting in place has the same problem for reads between the write and the delete.

Each open transaction has its own undo list of (key, old value) pairs. What does this print?

data, undo = {}, []

def set_(k, v):
    if undo:
        undo[-1].append((k, data.get(k)))
    data[k] = v

def rollback():
    for k, old in reversed(undo.pop()):
        if old is None:
            data.pop(k, None)
        else:
            data[k] = old

set_("x", 1)
undo.append([]); set_("x", 2); set_("y", 5)
undo.append([]); set_("x", 3)
rollback()
first = dict(data)
rollback()
print(first, data)

5
A field would expire at time 100. A backup is taken at time 70 and restored at time 200. If a backup freezes each field’s remaining lifetime, when does the restored field expire?
At the backup the field had 30 time units left, and the restore resumes that clock: 200 + 30 = 230. Keeping the absolute expiry of 100 would make it dead on arrival, and adding the full original lifetime ignores the time it had already used.

Practice problems

Solve these right here, in Python, C++ or Java. Tests run as you go.