In-Memory Database

The problem

An in-memory database groups fields under record keys. A field has a string value, may expire, and may change over time. The database must answer both a current read and a historical question: what value was visible at a particular logical timestamp? These responsibilities are related, but deleting expired data from a current map cannot by itself support historical reads.

Time comes from the caller as nondecreasing integers. It does not come from a clock, timer, or background thread. A value written at time 10 with a lifetime of 5 is visible at 10 through 14 and absent at 15. Defining that boundary explicitly prevents different methods from disagreeing about existence.

Naive approach

Start with a nested dictionary: record key maps to field name maps to value. Add an expiration timestamp beside each value. On every read, check whether the value has expired. This is a useful current-state design, but overwriting or deleting an entry destroys the earlier value.

Searching backwards for any unexpired value resurrects an overwritten version:

history = [(2, "new", None), (5, "ready", 8)]
query_time = 8
wrong = next(value for written, value, expires in reversed(history)
             if written <= query_time
             and (expires is None or query_time < expires))
print(wrong)
assert wrong == "new"  # The correct answer is absence.

Expiration ends the latest version’s visibility; it does not undo the replacement and restore an earlier value.

To preserve history, one simple extension copies the entire database after every successful mutation. Historical reads choose the latest snapshot at or before the requested time. The approach is understandable and may be acceptable for very small datasets, but every change duplicates unrelated records. Expiration still needs evaluation at the historical time rather than at the time of the query.

Where the naive approach breaks

Write status="new" at time 2 without expiration. At time 5 overwrite it with "ready" and lifetime 3. A historical read at 7 returns "ready"; a read at 8 returns absence. It must not fall back to "new" simply because the latest version has expired. The later write replaced that older version's visibility.

Deleting "done" at 10 must preserve its visibility at 9. Removing complete history loses that distinction. Failed conditional updates append nothing: comparing against an expired or different value is not a write.

A better design

Keep a timeline per (record, field). Each successful write appends its logical timestamp, value, and optional expiration boundary. A successful deletion appends a tombstone, an explicit marker for absence. Find the latest entry at or before the requested time, then evaluate only that entry. A tombstone or expired entry means absence; never search backwards for a replacement value.

Choose a version first, then evaluate that version alone:

from bisect import bisect_right

versions = [(2, "new", None), (5, "ready", 8), (5, "final", 9)]
query_time = 8
i = bisect_right([entry[0] for entry in versions], query_time) - 1
written, value, expires = versions[i]
visible = value if expires is None or query_time < expires else None
print(visible)
assert visible == "final"

The right insertion boundary chooses the last equal-timestamp write. This fragment assumes a nonempty eligible history and omits tombstone handling. Building its timestamp list costs O(H); store a parallel ordered timestamp sequence to obtain O(log H) lookup without that scan.

Nondecreasing call timestamps keep timelines ordered. Equal timestamps are allowed, so lookup must choose the last appended entry at that timestamp. A binary search using the right insertion boundary handles this rule. Conditional updates compare against the visible value at the operation's timestamp and append only on a match. Validate timestamps and lifetimes before advancing the accepted time or changing history.

For H versions of one field, historical lookup can take O(log H) time. Appending is amortized O(1), and retained history uses space proportional to successful mutations. A record scan examines its F known fields, performs their lookups, and sorts matching names; it is not a constant time operation. History grows until a retention policy removes it, and cleanup cannot discard versions still required by promised historical reads.

Real-world usage

This design is useful for test fixtures, expiring settings, and audit-oriented state exploration. Version timelines and deletion markers are common storage ideas, but this exercise does not implement a disk engine, indexes for arbitrary queries, or concurrent transaction isolation. Logical time makes the rules deterministic; it does not supply synchronization between independent writers.