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.

Versioned In-Memory DB Operations

Constraints

• Operation timestamps are non-decreasing

Examples

Example 1

Input: ((('set', 1, 'u', 'name', 'Ann'), ('get', 2, 'u', 'name'), ('cas', 3, 'u', 'name', 'Ann', 'Ana'), ('get', 4, 'u', 'name')),)
Output: ['Ann', True, 'Ana']

Explanation: Set, get, compare-and-set.

Example 2

Input: ((('set_ttl', 1, 'k', 'a', 'v', 3), ('get', 3, 'k', 'a'), ('get', 4, 'k', 'a'), ('get_at', 5, 'k', 'a', 2)),)
Output: ['v', None, 'v']

Explanation: TTL visibility and historical read.

Hints

1. Keep current state for live reads and append history entries for historical reads.