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.