In-Memory Key-Field-Value Store with TTL and Time-Travel

Implement an in-memory storage system that functions as a tiny key-field-value database.

Data Model

The data model is a 2-level map: key -> field -> value. Each operation is associated with a timestamp ts, which is guaranteed to be non-decreasing across the sequence of input queries. Individual (key, field) entries can optionally have a Time-To-Live (TTL). An entry is considered expired after its TTL elapses and must behave as if it no longer exists.

You will be provided with a sequence of commands to process in order. For commands that produce an output, collect and return these outputs.

Commands

Assume all key, field, value, and prefix strings are non-empty and contain no spaces. ts and ttl are integers.

Basic Operations

1. SET ts key field value
   • Sets the value for the (key, field) pair at time ts.
   • This write has no TTL (it never expires) and overwrites any existing value or TTL for that (key, field) pair.
2. GET ts key field
   • Returns the current value of (key, field) at time ts.
   • If the entry is missing or expired at ts, an empty string "" should be returned.
3. COMPARE_AND_SET ts key field expected newValue
   • If the current (non-expired) value of (key, field) at time ts equals expected, the value is updated to newValue. This new value has no TTL.
   • Returns "true" if the update occurred, otherwise "false".
4. COMPARE_AND_DELETE ts key field expected
   • If the current (non-expired) value of (key, field) at time ts equals expected, the field is deleted.
   • Returns "true" if the deletion occurred, otherwise "false".

Scan Operations

1. SCAN ts key
   • Returns all non-expired fields for the given key at time ts.
   • The fields must be sorted lexicographically by their field names.
   • The output format for each field-value pair is field(value), joined by commas (e.g., a(1),b(2)).
   • If key has no non-expired fields, return "".
2. SCAN_BY_PREFIX ts key prefix
   • Identical to SCAN, but only includes fields whose names start with the specified prefix.

TTL Support

1. SET_WITH_TTL ts key field value ttl
   • Sets the value for (key, field) at time ts with an expiration time expireAt = ts + ttl.
   • The entry is considered valid for any timestamp t such that ts <= t < expireAt.
   • This operation overwrites any previous value or TTL for the (key, field) pair.

TTL Rule: At any given timestamp ts, an entry is visible only if it exists and is not expired at ts.

Time-Travel Queries (Advanced)

1. GET_AT ts key field atTs
   • Returns the value that (key, field) had at a specific historical timestamp atTs.
   • TTL rules and deletions are respected for atTs.
   • If the entry did not exist or was expired at atTs, return "".
   • It is guaranteed that atTs <= ts.

Input and Output

• Input: queries, a list where each element is a list of strings representing a single command (tokens in the order shown above).
• Output: A list of strings containing the results of each command that produces output.
  • Commands producing output: GET, COMPARE_AND_SET, COMPARE_AND_DELETE, SCAN, SCAN_BY_PREFIX, GET_AT.
  • SET and SET_WITH_TTL produce no output.

Constraints

• The number of queries len(queries) is between 1 and 100,000.
• Timestamps are strictly non-decreasing.
• The total length of all strings involved is manageable within typical memory limits.

Implement a function that processes the given list of queries and returns the corresponding list of outputs.