Implement an Expiring Record Store

Implement a level-based in-memory record store.

The store contains records identified by a string key. Each record contains fields, where each field is a string and each value is a string.

Level 1: Basic mutations

Implement:

• set(key, field, value): Create the record if it does not exist, then set field to value.
• get(key, field): Return the current value for field, or null if the record or field does not exist.
• delete(key, field): Remove field from the record. Return true if a field was removed, otherwise return false. If a record becomes empty, it may be removed from the store.

Level 2: Scanning

Implement:

• scan(key): Return all fields for key, sorted lexicographically by field name. Format each item as field(value). Return an empty list if the record does not exist.
• scan_by_prefix(key, prefix): Return only fields whose names start with prefix, sorted lexicographically by field name and formatted as field(value).

Level 3: Timestamps and TTL

Extend the store so fields can be written with timestamps and optional time-to-live values.

Implement:

• set_at(key, field, value, timestamp): Set the field at timestamp with no expiration.
• set_at_with_ttl(key, field, value, timestamp, ttl): Set the field at timestamp; it is visible for query times t such that timestamp <= t < timestamp + ttl.
• delete_at(key, field, timestamp): Delete the field at timestamp if it exists and is not expired at that time. Return true if a field was deleted, otherwise return false.
• get_at(key, field, timestamp): Return the value visible at timestamp, or null if none exists.
• scan_at(key, timestamp): Return all fields visible at timestamp, sorted and formatted as in scan.
• scan_by_prefix_at(key, prefix, timestamp): Return all visible fields at timestamp whose names start with prefix, sorted and formatted as in scan_by_prefix.

Assume timestamps passed to timestamped operations are non-decreasing. A later write to the same (key, field) replaces the previous value and expiration policy. Expired or deleted fields must not appear in reads or scans.