In-Memory Key-Value Store with Constant-Time Nested Transactions

Implement an in-memory key-value store with transactions. It supports `get`, `set` and `delete`, plus `begin`, `commit` and `rollback`, and the question asks for every operation in constant time. The follow-ups then extend the store: several threads using it at once, keys that expire after a time to live, and "time travel" reads of a key's value at an earlier time. ```python store = TxStore() store.set("a", 1) store.begin() store.set("a", 2) store.delete("b") store.get("a") # 2 store.rollback() store.get("a") # 1 ``` ### Clarifying Questions - Can transactions be nested, and does `commit` close only the innermost transaction or all open ones? - What do `commit` and `rollback` do when no transaction is open? - What does `get` return for a missing or deleted key? - Is constant time required for each call in the worst case, or is amortized constant time acceptable, and does that include `rollback`? - In the threaded version, does each thread run its own transactions, and may one thread see another's uncommitted writes? ### Part 1 — Transactions Implement `get(key)`, `set(key, value)`, `delete(key)`, `begin()`, `commit()` and `rollback()`. A `rollback` undoes every change made since the matching `begin`; a `commit` keeps them. ```hint Where do writes go Decide whether a write inside a transaction changes the main map right away or is kept aside, and what that choice costs for reads, for commits and for rollbacks. ``` #### What This Part Should Cover - The data structures, and the cost of each operation, stated honestly - Correct undo of a key that did not exist before the transaction - Nested transactions: what a nested `commit` hands to the enclosing transaction ### Part 2 — Several threads Make the store safe when several threads call it at once. ```hint What one thread may see Separate keeping the data structures intact from deciding when one thread's changes become visible to the others. ``` #### What This Part Should Cover - What a lock protects and how long it is held - Whether transactions are per thread, and how their writes are isolated - What happens when two transactions write the same key ### Part 3 — Time to live Add `set(key, value, ttl)`: the key disappears `ttl` seconds after it was set. ```hint Expire on demand or in the background Consider what a read must check, and what keeps keys that are never read again from filling memory. ``` #### What This Part Should Cover - How reads treat expired keys - How expired keys are eventually removed, and the cost of doing so - How the clock is supplied so that expiry can be tested ### Part 4 — Time travel Add `get(key, at_time)`, which returns the value the key had at an earlier time. ```hint Keep history per key Think about what has to be kept for each key so that a read at any past time is fast. ``` #### What This Part Should Cover - The history kept per key and the lookup cost - How deletes and transactions show up in the history - How the history is bounded in memory ### What a Strong Answer Covers - Pins down nested-transaction semantics, missing-key behavior and the meaning of constant time before coding - A working store whose undo handling is correct for overwritten, newly created and deleted keys - Complexity of every operation, including the cost that `rollback` or `commit` cannot avoid - A concurrency design that names its isolation level - TTL and time travel built on the same structures, with an injectable clock and tests ### Follow-up Questions - The process may crash. How do you make committed data survive a restart? - Add `count(value)`, the number of keys currently holding a value, in constant time, and keep it correct across rollbacks. - Memory is capped. Which keys do you evict, and how does eviction interact with open transactions? - Two long transactions keep conflicting. How would you choose between locking and optimistic validation?