Implement a versioned in-memory DB with CAS and history

In-Memory DB V2: TTL + Compare-And-Set/Delete + Historical Reads

Implement an in-memory database keyed by (key, field) supporting TTL, conditional updates, scans, and historical queries.

Data model / rules

• For each (key, field) store:
  • value
  • expire_at (integer; +∞ means never expires)
• A record is visible at time t iff t < expire_at .
• All operations are given a timestamp . You may assume operations are provided in non-decreasing timestamp order .
• You must also support historical queries: retrieve what value was valid at some earlier time.

API

1. set(timestamp, key, field, value) -> void
   • Set with no TTL ( expire_at = +∞ ).
2. set_with_ttl(timestamp, key, field, value, ttl) -> void
   • Set with expire_at = timestamp + ttl .
3. get(timestamp, key, field) -> value | null
   • Return current value if exists and not expired at timestamp , else null .
4. compare_and_set(timestamp, key, field, expected_value, new_value) -> bool
   • If (key, field) exists and is not expired at timestamp and its current value equals expected_value , update it to new_value ( expire_at = +∞ ) and return true .
   • Otherwise return false .
5. compare_and_set_with_ttl(timestamp, key, field, expected_value, new_value, ttl) -> bool
   • Same as above, but sets expire_at = timestamp + ttl .
6. compare_and_delete(timestamp, key, field, expected_value) -> bool
   • If current visible value equals expected_value , delete it and return true , else return false .
7. scan(timestamp, key) -> list<string>
   • Return all non-expired fields for key at timestamp .
   • Sort by field ascending.
   • Format each item as "field(value)" .
8. scan_by_prefix(timestamp, key, prefix) -> list<string>
   • Like scan , but only fields starting with prefix .
9. get_value_at(timestamp, key, field, at_timestamp) -> value | null
   • Return the value that was valid for (key, field) at time at_timestamp .
   • Return null if it did not exist, was deleted, or was expired at at_timestamp .

Notes

• You will likely need to keep a per-(key,field) history of changes to answer get_value_at efficiently.
• Assume up to ~1e5 operations.