Design an in-memory database with TTL and history

Design and implement an in-memory key–field–value store with monotonic timestamps. Keys and fields are strings; values are integers. Provide these APIs and behaviors: ( 1) set(timestamp, key, field, value): store value at key-field. ( 2) get(timestamp, key, field): return the current value or null if key or field does not exist or the value has expired. ( 3) compareAndSet(timestamp, key, field, expectedValue, newValue): if the current value equals expectedValue, atomically set to newValue and return true; otherwise return false. ( 4) compareAndDelete(timestamp, key, field, expectedValue): if the current value equals expectedValue, delete it and return true; otherwise return false. ( 5) scan(timestamp, key): return an array of strings formatted as "field(value)" for all fields under key, sorted alphabetically by field; return an empty array if key does not exist. ( 6) scanByPrefix(timestamp, key, prefix): like scan but only include fields whose names start with prefix. ( 7) setWithTtl(timestamp, key, field, value, ttl): like set, but the value expires automatically at timestamp + ttl; expired values must not appear in get/scan/scanByPrefix results. ( 8) compareAndSetWithTtl(timestamp, key, field, expectedValue, newValue, ttl): like compareAndSet; on success, set newValue with the given ttl. ( 9) getWhen(timestamp, key, field, atTimestamp): return the value that would have been visible at atTimestamp (where atTimestamp < timestamp), or null if none; for example, if value 10 is set at time 10, expires at 12, and value 18 is set at 18, then getWhen(..., 5) = null, getWhen(..., 11) = 10, getWhen(..., 15) = null, getWhen(..., 20) = 18. Assume all provided timestamps across calls are strictly increasing. Describe your data structures, how you track expirations and history, and analyze time and space complexity.