Design a Versioned In-Memory Key → (Field → Value) Store with TTL, History, and Backup/Restore

You are tasked with designing an in-memory database that stores values at the granularity of (key, field). This database must support per-field Time-To-Live (TTL), maintain a full append-only history with validity intervals, and provide robust backup and restore capabilities to snapshot points.

API Specifications

All timestamps t are logical; ttl is in the same units. A ttl = null indicates no expiry.

1. set(key, field, value, t, ttl)

   • Upserts a field under a given key at a specified logical time t. This operation must append to the history for the (key, field) pair.
   • Each (key, field) entry should track its validity using [start, end) intervals, with end being optional. A deletion is represented by an optional tombstone interval.

2. get(key, field, t)

   • Returns the value associated with (key, field) only if its version visible at time t has not expired. Specifically, t must be less than start + ttl (when ttl is set) AND end must be unset or t must be less than end. Otherwise, returns null.

3. delete(key, field, t)

   • Logs a tombstone at time t that effectively ends the current valid interval for (key, field). The full history for the entry must be preserved to support replay and restore operations.

4. scan(key, t)

   • Returns all (field, value) pairs for a given key that are visible and non-expired at time t. The results must be ordered lexicographically by field.

5. scanPrefix(key, prefix, t)

   • Similar to scan, but only returns (field, value) pairs where the field starts with the specified prefix. Results must also be ordered lexicographically.

6. backup(t)

   • Records a snapshot marker at time t for the entire database. Returns the total number of non-expired (key, field) pairs visible at t across the whole database.

7. restore(t)

   • Rewinds the observable state of the database to the most recent backup taken at or before time t. Returns the count of non-expired (key, field) pairs from that backup. Deletions must be represented via tombstones so that the history remains fully replayable.

Requirements and Clarifications

• TTL Granularity: TTL applies at the (key, field) level, not at the key level. Reads and scans must strictly exclude any expired entries. When an already-expired field is updated via set, it should be treated as a fresh insert with a new start time.
• Scan Ordering: All scan operations (scan, scanPrefix) must produce deterministically ordered results. You must propose data structures that efficiently support ordered scans and prefix scans while coexisting with the requirements for TTL and history tracking.
• History Tracking: Describe in detail how to track [start, end) intervals, the value, ttl, and delete tombstones for each (key, field) pair. This tracking mechanism must effectively support time-travel semantics, backup/restore operations, and efficient read access.
• Complexity Analysis: Provide expected time and space complexities for each API. Discuss the trade-offs between different data structure choices, such as using per-key ordered maps versus a brute-force-plus-sort approach for scans, and the implications of global versus per-key expiry indexes.
• Garbage Collection: Explain your strategy for garbage-collecting fully expired history. This strategy must ensure that enough information is retained to support restore operations to any prior backup point.