Key-value store with nested transaction rollback

Implement an in-memory key-value store whose string keys map to string values. It supports transactions, and transactions can be nested.

Implement the class KeyValueStore:

• KeyValueStore() creates an empty store.
• set(key: str, value: str) -> None stores value under key and overwrites any existing value.
• get(key: str) -> str | None returns the current value for key, or None if the key is absent.
• unset(key: str) -> None removes key. Removing a key that does not exist does nothing.
• begin() -> None opens a new transaction. If a transaction is already open, the new one is nested inside it.
• rollback() -> bool discards every change made in the innermost open transaction and closes it. Returns False if no transaction is open.
• commit() -> bool closes the innermost open transaction and keeps its changes. If it is nested, its changes become part of the enclosing transaction, so a later rollback of the parent still undoes them. Only committing the outermost transaction makes changes permanent. Returns False if no transaction is open.

Reads always see the latest changes, including uncommitted ones in open transactions.

Constraints

• Up to 10^5 operations; transactions can nest up to 10^4 deep.
• get, set and unset should run in O(1) average time.
• begin should be O(1). commit and rollback should cost time proportional to the number of keys the innermost transaction changed, not the size of the store.

Example 1

kv.set("color", "red")
kv.begin()
kv.set("color", "blue")
kv.set("size", "L")
kv.get("color")   -> "blue"
kv.rollback()      -> True
kv.get("color")   -> "red"
kv.get("size")    -> None
kv.rollback()      -> False

Example 2 (nested)

kv.set("n", "0")
kv.begin()
kv.set("n", "1")
kv.begin()
kv.unset("n")
kv.commit()        -> True    # folds into the outer transaction
kv.get("n")       -> None
kv.rollback()      -> True    # undoes both levels
kv.get("n")       -> "0"