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

You are building an in-memory database that stores values at the granularity of (key, field), supports per-field TTL, maintains full append-only history with validity intervals, and can backup and restore to snapshot points.

APIs (all timestamps t are logical; ttl is in the same units; ttl = null means no expiry):

1. set(key, field, value, t, ttl)
   • Upsert a field under key at time t. Append to history.
   • Each (key, field) keeps intervals [start, end), with an optional tombstone (delete) interval.
2. get(key, field, t)
   • Return the value only if the version visible at t has not expired: t < start + ttl (when ttl is set) AND end is unset or t < end. Otherwise return null.
3. delete(key, field, t)
   • Log a tombstone at time t that ends the current interval but keeps history (for replay/restore).
4. scan(key, t)
   • Return all (field, value) pairs for key visible and non-expired at t, ordered lexicographically by field.
5. scanPrefix(key, prefix, t)
   • Same as scan, but only for fields starting with prefix, ordered lexicographically.
6. backup(t)
   • Record a snapshot marker at time t and return the total number of non-expired (key, field) pairs visible at t across the whole DB.
7. restore(t)
   • Rewind the observable state to the most recent backup at or before time t and return that backup's count. Deletions must be represented via tombstones so history remains replayable.

Requirements and clarifications:

• TTL applies at the (key, field) level, not at the key level. Reads and scans must exclude expired entries. When updating an already-expired field, treat it as a fresh insert.
• Scans must be deterministically ordered. Propose data structures that support efficient ordered scans and prefix scans while coexisting with TTL and history.
• Describe how to track [start, end), value, ttl, and delete tombstones per (key, field) to support time-travel semantics, backup/restore, and efficient reads.
• Provide expected time and space complexities for each API. Discuss trade-offs between per-key ordered maps vs. brute-force-plus-sort, and global vs. per-key expiry indexes.
• Explain how to garbage-collect fully expired history while keeping enough information to support restore to a prior backup.