Design in-memory DB with TTL and backup

Question

Design and implement an in-memory, versioned key → (field → value) database that supports per-field TTL, time-travel reads, lexicographically ordered scans, and snapshot backup/restore. Every read and write carries a logical timestamp t; all reads are evaluated as of t (not just "now"). ttl is expressed in the same units as t, and ttl = null means no expiry.

Implement the following timestamped operations:

1. set(key, field, value, t, ttl) — Upsert value at (key, field). Maintain append-only history so each (key, field) has a sequence of validity intervals [start, end). A field's value expires at start + ttl (when ttl is set). Define behavior when ttl is null (no expiry) and when ttl is non-positive. Updating an already-expired field is treated as a fresh insert.
2. get(key, field, t) — Return the value visible at time t, i.e. the latest version with start ≤ t that has not expired (t < start + ttl when TTL is set, and the interval has not been closed/tombstoned by t). Otherwise return null.
3. delete(key, field, t) — Log a tombstone that ends the current interval at t while preserving prior history for future replay/restore.
4. scan(key, t) — Return all non-expired (field, value) pairs under key as of t, ordered lexicographically by raw field name.
5. scanPrefix(key, prefix, t) — Same as scan, but only fields whose name starts with prefix, again ordered lexicographically.
6. backup(t) — Record a snapshot marker at time t and return the total count of non-expired (key, field) pairs across the whole database as of t.
7. restore(t) — Rewind the database's observable state to the most recent backup at or before t, and return the count that backup had recorded. Because deletions are tombstones, history remains replayable.

Requirements and clarifications:

• TTL granularity: TTL applies at the (key, field) level, not the key level. All reads and scans must exclude entries expired as of the query timestamp. Describe how you store per-field expiry and how you garbage-collect or lazily purge expired data — while keeping enough history to restore to any retained backup.
• Deterministic ordering with special characters: Scans must be deterministically ordered by the raw field name. Field names and prefixes may contain parentheses, punctuation, or other delimiters (e.g. "a(1)", "a(2)"). Explain how you keep ordering correct (e.g. compare raw field strings by Unicode code point / UTF-8 byte order, store the ordering key separately from any serialized metadata, and never tokenize or split on punctuation).
• Time-travel semantics: Reads use the latest version with start ≤ t; a later write at t' > t must not be visible at t. Describe how you track [start, end), value, ttl, and tombstones per (key, field) to support this.
• Complexity & trade-offs: Give expected time and space complexity for every operation. Discuss per-key ordered maps (for ordered/prefix scans) vs. brute-force-plus-sort, and global vs. per-key expiry indexes for answering backup(t) at arbitrary t. Discuss concurrency and how you would test corner cases (special characters in prefixes, very large field counts, mass expirations).