Design a Time-Travel Key-Field Store with TTL

Implement an in-memory "database" that stores records by key and fields within each key. Each operation is given a timestamp (an integer that is non-decreasing across calls) and should behave as if executed at that time.

A record conceptually looks like: DB[key][field] = value (where value is an integer).

Your implementation must maintain enough history to support both Time-To-Live (TTL) expiration and historical ("time-travel") queries.

Common Rules

• If a requested key or field does not exist, or is expired at the queried time, it should be treated as missing.
• Deleting a field removes it from the record at that specific time.
• Unless otherwise specified, functions that read data use the provided timestamp as the "current time" for visibility and expiration checks.
• Return formats must be deterministic. Unless specified by the interviewer, return scan results sorted by field ascending.

Level 1: Basic Operations

Implement the following:

1. set(timestamp: int, key: str, field: str, value: int) -> None
   • Sets DB[key][field] = value at the given timestamp.
2. get(timestamp: int, key: str, field: str) -> Optional[int]
   • Returns the current value for (key, field) at timestamp, or None if missing.
3. compare_and_set(timestamp: int, key: str, field: str, expected_value: int, new_value: int) -> bool
   • If the current value at timestamp equals expected_value, update it to new_value and return True.
   • Otherwise, return False (no change).
4. compare_and_delete(timestamp: int, key: str, field: str, expected_value: int) -> bool
   • If the current value at timestamp equals expected_value, delete the field and return True.
   • Otherwise, return False.

Level 2: Scans

Implement the following:

1. scan(timestamp: int, key: str) -> List[str]
   • Returns all visible fields for key at timestamp formatted as: "{field}({value})".
   • The list must be sorted by field ascending.
2. scan_with_prefix(timestamp: int, key: str, prefix: str) -> List[str]
   • Similar to scan, but only includes entries where the formatted string starts with prefix.
   • (Equivalently: include only fields whose names start with prefix.)

Level 3: TTL Support

Add per-write Time-To-Live (TTL) support. A value written with a TTL is visible only within the half-open interval: [write_timestamp, write_timestamp + ttl).

Implement the following:

1. set_with_ttl(timestamp: int, key: str, field: str, value: int, ttl: int) -> None
2. compare_and_set_with_ttl(timestamp: int, key: str, field: str, expected_value: int, new_value: int, ttl: int) -> bool
   • Same semantics as compare_and_set, but if the update occurs, new_value is written with the provided ttl.

Additionally, all previously implemented read/write operations must be updated such that:

• Reads (get, scan, scan_with_prefix) do not return expired values.
• Compare-and-* operations compare against the value visible at that timestamp (treating expired values as missing).

Level 4: Time-Travel Query

Implement the following:

• get_when(timestamp: int, key: str, field: str, at_timestamp: int) -> Optional[int]

This function should return the value of (key, field) as it was visible at at_timestamp. This includes considering:

• Historical set / set_with_ttl operations.
• Successful compare-and-* updates.
• Deletions.
• TTL expiration relative to each write time.

Assume at_timestamp <= timestamp. If the value was missing or expired at at_timestamp, return None.

Constraints

• Timestamps are non-decreasing across operations.
• The system should handle up to approximately 100,000 to 200,000 total operations.
• Aim for efficient per-operation runtime, ideally logarithmic in the number of updates per field.