Design In-Memory Transactions with Snapshots and Savepoints

Problem Statement

Design an in-memory transactional key-value store that supports nested transactions, named savepoints, and accurate restoration of previous states (including key deletions).

Implement the TransactionalKVStore class with the following methods:

• get(key: str) -> Optional[str]: Returns the value of key, or None if the key does not exist.
• set(key: str, value: str) -> None: Sets key to value in the current transactional context.
• delete(key: str) -> None: Deletes key in the current transactional context. If the key does not exist, does nothing.
• begin() -> None: Starts a new transaction block. Transactions can be nested.
• savepoint(name: str) -> None: Creates a named checkpoint within the current transaction block. If a savepoint with the same name already exists in the current transaction block, it is overwritten.
• rollback_to(name: str) -> bool: Rolls back all changes made since the savepoint name within the active transaction stack, keeping the savepoint active. Returns True if the savepoint exists, or False if no such savepoint is found.
• rollback() -> bool: Rolls back all changes in the most recent uncommitted transaction block and closes it. Returns True on success, or False if there is no open transaction.
• commit() -> bool: Persists all changes from all active transactions to the base state and closes all open transactions. Returns True on success, or False if there is no open transaction.

Complexity Requirements

• Operations outside transactions must take O(1) average time.
• get, set, and delete should take O(1) amortized time even when multiple transactions are active.
• Be explicit about the space and time trade-offs between an undo-log approach and a snapshot/layered-map approach.

Example

kv = TransactionalKVStore()
kv.set("a", "10")
kv.begin()
kv.set("a", "20")
kv.savepoint("sp1")
kv.set("b", "30")
kv.delete("a")
assert kv.get("a") is None
assert kv.get("b") == "30"

# Roll back to savepoint sp1
assert kv.rollback_to("sp1") is True
assert kv.get("a") == "20"
assert kv.get("b") is None

# Roll back outer transaction
assert kv.rollback() is True
assert kv.get("a") == "10"
assert kv.get("b") is None

Edge Cases

• Deleting a key that was created in the current transaction vs. deleting a key that existed before the transaction began.
• Calling commit(), rollback(), or rollback_to() when no transaction is active.
• Rolling back to a savepoint multiple times.