Design In-Memory Transactions with Snapshots and Savepoints

Design an in-memory database with transaction and savepoint support. Explain how reads, writes, and deletions interact with a transaction, how a savepoint records a recoverable state, and how rollback and commit behave. Consider an implementation that captures an initial snapshot and records subsequent changes. The exact API and isolation contract are unspecified. State your choices for the number of active transactions, savepoint lifetime, missing keys, and value mutability before explaining the implementation. ### What a Strong Answer Covers - A clear separation between committed state and the changes of an active transaction. - Enough change information to restore overwritten and deleted keys, including repeated changes to the same key. - Savepoint creation, rollback to a savepoint, full rollback, and commit with consistent lifecycle rules. - The time and memory cost of copying the initial state and recording or undoing later changes. - An explicit limit on concurrency and durability guarantees for the in-memory design. ```hint A deletion also has an old state An undo record must distinguish a key that was absent from a key that existed with a null-like value before the operation. ``` ### Follow-up Questions - What happens when a key is written several times after a savepoint and then deleted before rollback? - How would you reduce the initial snapshot cost while preserving a stable transaction view?