Implement an in-memory key-field-value DB with TTL

In-Memory DB with TTL + Scan + Backup/Restore

Implement an in-memory database storing records by (key, field) -> value with optional TTL.

Data model / rules

• key and field are strings.
• value is a string (or integer; choose one and be consistent).
• Each stored (key, field) has an expiration time expire_at.
  • If a value is set without TTL, expire_at = +∞.
  • A value is visible at query time t iff t < expire_at.

API

1. set(key, field, value, timestamp) -> void

   • Store (value, +∞).

2. set_with_ttl(key, field, value, timestamp, ttl) -> void

   • Store (value, timestamp + ttl).

3. get(key, field, timestamp) -> value | null

   • Return null if missing or expired at timestamp.

4. delete(key, field, timestamp) -> bool

   • Delete the field (regardless of TTL).
   • Return false if (key, field) does not exist; otherwise true.

5. scan(key, timestamp) -> list<(field, value)>

   • Return all non-expired fields for key at timestamp.
   • Sort results by field ascending.

6. scan_with_prefix(key, prefix, timestamp) -> list<(field, value)>

   • Like scan, but only include fields that start with prefix.

7. backup(timestamp) -> void

   • Persist a full snapshot of the DB state at timestamp.

8. restore(timestamp, restore_to_time) -> void

   • Restore DB state from the most recent backup with backup_time <= restore_to_time.
   • If no such backup exists, restore to an empty DB.

Notes

• Assume timestamps are integers.
• Assume up to ~1e5 operations; aim for efficient scans and correct TTL handling.

In-Memory Key-Field-Value DB with TTL, Scan, and Backup/Restore

Implement an in-memory database that stores records keyed by (key, field) with an optional time-to-live (TTL), plus prefix scans and point-in-time backup/restore.

You are given a list of operations. Each operation is a list whose first element is the operation name, followed by its arguments:

• ["set", key, field, value, timestamp] — store value at (key, field) with no expiry. Returns nothing.
• ["set_with_ttl", key, field, value, timestamp, ttl] — store value with expire_at = timestamp + ttl. Returns nothing.
• ["get", key, field, timestamp] — return the value if present and not expired at timestamp (visible iff timestamp < expire_at), else None.
• ["delete", key, field, timestamp] — remove (key, field) regardless of TTL. Return True if it existed, else False.
• ["scan", key, timestamp] — return a list of [field, value] for every non-expired field under key, sorted by field ascending.
• ["scan_with_prefix", key, prefix, timestamp] — like scan, but only fields that start with prefix.
• ["backup", timestamp] — persist a full snapshot of the DB at timestamp. Returns nothing.
• ["restore", timestamp, restore_to_time] — replace the DB with the most recent backup whose backup_time <= restore_to_time. If none exists, the DB becomes empty. Returns nothing.

Return a list with one entry per operation: the operation's return value, or None for the void operations (set, set_with_ttl, backup, restore). Values are strings and timestamps are integers.

Constraints

• key, field, prefix, and value are strings; value is treated as a string.
• timestamps and ttl are integers; ttl > 0.
• A (key, field) is visible at time t iff t < expire_at; a no-TTL set uses expire_at = +inf.
• delete removes the field regardless of expiry and returns whether it existed.
• restore selects the most recent backup with backup_time <= restore_to_time; if none, the DB becomes empty.
• Up to ~1e5 operations total.

Examples

Example 1

Input: ([['set', 'k1', 'f1', 'v1', 1], ['get', 'k1', 'f1', 2], ['set_with_ttl', 'k1', 'f2', 'v2', 5, 10], ['get', 'k1', 'f2', 14], ['get', 'k1', 'f2', 15], ['get', 'k1', 'fX', 3], ['get', 'kX', 'f1', 3], ['delete', 'k1', 'f1', 20], ['delete', 'k1', 'f1', 21], ['get', 'k1', 'f1', 22]],)
Output: [None, 'v1', None, 'v2', None, None, None, True, False, None]

Explanation: Basic set/get with a TTL expiry boundary (t>=expire is expired), missing key/field returns null, and delete returns true only when the field exists.

Example 2

Input: ([['set', 'k', 'banana', 'B', 0], ['set', 'k', 'apple', 'A', 0], ['set_with_ttl', 'k', 'apricot', 'AP', 0, 5], ['set', 'k', 'cherry', 'C', 0], ['scan', 'k', 3], ['scan', 'k', 5], ['scan_with_prefix', 'k', 'ap', 3], ['scan_with_prefix', 'k', 'ap', 5], ['scan', 'missing', 0]],)
Output: [None, None, None, None, [['apple', 'A'], ['apricot', 'AP'], ['banana', 'B'], ['cherry', 'C']], [['apple', 'A'], ['banana', 'B'], ['cherry', 'C']], [['apple', 'A'], ['apricot', 'AP']], [['apple', 'A']], []]

Explanation: scan and scan_with_prefix return [field, value] pairs sorted by field ascending, filtering out expired entries; a missing key yields an empty list.

Hints

1. Model storage as a nested map key -> field -> (value, expire_at). Store expire_at = +inf for set without TTL and timestamp + ttl for set_with_ttl, so get/scan only need the single check t < expire_at.
2. Don't physically purge expired entries on a timer — just filter them at read time (get/scan). Deletion is the only thing that actually removes a field.
3. For backup, store a DEEP copy of the whole storage map under its timestamp; a shallow copy would let later mutations corrupt the snapshot. For restore, keep backup timestamps sorted and binary-search for the largest one <= restore_to_time (and restore to empty when there is none).