Implement an in-memory DB with TTL backup/restore

Problem

Design an in-memory database that stores values in a nested structure:

• key (string) → field (string) → value (string)
• Each (key, field) entry may optionally have a TTL (time-to-live) measured in the same time units as the provided timestamps.
• All operations are evaluated at a given integer timestamp ts .
• If an entry is expired at time ts , it must behave as if it does not exist.

You are given a sequence of queries. Each query is one of the operations below. Implement the database so that each query that produces an output returns the correct string.

Supported operations

Assume all timestamps are non-decreasing across the query list.

1. Set without TTL
   • SET ts key field value
   • Stores value at (key, field) with no expiration .
2. Set with TTL
   • SET_TTL ts key field value ttl
   • Stores value at (key, field) that is valid on the interval [ts, ts + ttl) .
3. Get
   • GET ts key field
   • Returns the stored value, or an empty string "" if missing/expired.
4. Delete
   • DELETE ts key field
   • Deletes the field if present (and not expired at ts ).
   • Returns "true" if something was deleted, else "false" .
5. Scan all fields of a key
   • SCAN ts key
   • Returns all non-expired fields under key formatted as:
     • field1(value1),field2(value2),...
   • Fields must be sorted lexicographically by field .
   • If no fields exist, return an empty string "" .
6. Scan fields by prefix
   • SCAN_PREFIX ts key prefix
   • Same output format as SCAN , but include only fields whose names start with prefix .
7. Backup
   • BACKUP ts
   • Creates a snapshot of the entire database state at time ts (including TTL state).
   • Conceptually, TTL countdown is paused in the snapshot: when restoring later, each TTL-based entry should resume with the remaining TTL it had at backup time .
   • (If you need a return value, return the number of top-level keys present in the snapshot; otherwise no output.)
8. Restore
   • RESTORE ts at_timestamp
   • Restores the database to the most recent snapshot whose backup time t_backup satisfies t_backup <= at_timestamp .
   • After restore at current time ts , TTL entries must have their expiration recomputed using the remaining TTL at backup time:
     • If an entry had expiration t_exp originally, then at backup time t_backup it had remaining TTL rem = t_exp - t_backup .
     • After restoring at ts , its new expiration becomes ts + rem .
   • Entries that were already expired at t_backup must not appear in the restored state.
   • (If you need a return value, return "true" if a snapshot was found and restored, else "false" .)

Task

Implement a function/class to process the queries in order and return the list of outputs (strings) for the queries that produce outputs (GET, DELETE, SCAN, SCAN_PREFIX, and any required outputs for BACKUP/RESTORE depending on your chosen interface).

Constraints (typical)

• Up to ~10^5 queries
• Keys/fields/values are non-empty strings of reasonable length
• Timestamps and TTLs fit in 32-bit signed integers
• Query timestamps are non-decreasing