Transactional Key-Value Store

Implement an in-memory key-value store with nested transactions, including begin, commit, rollback, read-your-write behavior, and deletion semantics. Transactional Key-Value Store Implement an in-memory key-value store with nested transactions, including begin, commit, rollback, read-your-write behavior, and deletion semantics. SWE Infra Eng in-memory-database transactions hashmap design-implementation medium Frequency Single report Last asked 2026-01-20 Stage onsite-coding · tech-screen Transactional Key-Value Store The Challenge You need to build an in-memory key-value store that supports transactions. This includes nested transactions. This setup is often used in databases, version control systems, and tools that manage settings. Your code must support atomic operations. This means you can save (commit) a group of changes at once or undo (rollback) them. Nested transactions create "safe points." You can undo a specific safe point without canceling the entire transaction. Where This Is Used Database transaction management Systems that let you "preview" changes before applying them Undo/redo buttons in text editors Staging areas in version control (like Git) Saving game checkpoints What You Need to Build Your code must support these commands: get(key): Get the value of a key. Return None if the key is missing. set(key, value): Save a value for a key. delete(key): Remove a key from the store. begin(): Start a new transaction (can be nested inside another). commit(): Save the current transaction permanently. rollback(): Undo all changes in the current transaction. How It Works db = TransactionalKVStore() db.set("a", 1) print(db.get("a")) # 1 db.begin() # Start transaction db.set("a", 2) print(db.get("a")) # 2 db.rollback() # Undo changes print(db.get("a")) # 1 (Back to original) db.begin() # Start transaction db.set("a", 3) db.commit() # Save changes print(db.get("a")) # 3 (Saved forever) # Nested transactions db.begin() # Level 1 db.set("b", 10) db.begin() # Level 2 (nested) db.set("b", 20) print(db.get("b")) # 20 db.rollback() # Undo Level 2 only print(db.get("b")) # 10 (Level 1 value) db.commit() # Save Level 1 print(db.get("b")) # 10 (Saved forever) Step 1: Simple Transactions The Task Build a TransactionalKVStore class that supports one level of transactions: class TransactionalKVStore: def __init__(self): """Initialize the store.""" pass def get(self, key: str) -> any: """ Get value for a key. Returns value if it exists, else None. """ pass def set(self, key: str, value: any) -> None: """Set a key to a value.""" pass def delete(self, key: str) -> None: """Delete a key.""" pass def begin(self) -> None: """Start a new transaction.""" pass def commit(self) -> None: """ Save the current transaction. Raises error if no transaction is running. """ pass def rollback(self) -> None: """ Undo the current transaction. Raises error if no transaction is running. """ pass Testing the Logic # Test 1: Basic usage without transaction db = TransactionalKVStore() db.set("x", 100) assert db.get("x") == 100 assert db.get("nonexistent") is None # Test 2: Saving a transaction db = TransactionalKVStore() db.set("a", 1) db.begin() db.set("a", 2) db.set("b", 3) db.commit() assert db.get("a") == 2 assert db.get("b") == 3 # Test 3: Undoing a transaction db = TransactionalKVStore() db.set("a", 1) db.begin() db.set("a", 2) db.delete("a") db.rollback() assert db.get("a") == 1 # Test 4: Delete inside a transaction db = TransactionalKVStore() db.set("key", "value") db.begin() db.delete("key") assert db.get("key") is None db.rollback() assert db.get("key") == "value" Step 2: Nested Transactions The Task Update your code to support nested transactions. Every time you call begin(), it creates a new transaction level (like a savepoint). A rollback() only cancels the most recent level. A commit() moves changes from the current level to the one above it. Rules for Nesting begin(): Starts a new nested level. Changes stay here for now. commit(): Merges changes from the current level into the parent level. If you are at the top level, the changes become permanent. rollback(): Deletes changes in the current level only. The parent level is not changed. Key Behaviors: Read-your-write: You must see your own uncommitted changes immediately. Outer rollback cancels inner commits: If you undo a main transaction, it also cancels any inner transactions you already committed. This is because inner commits only merged data to the parent; they didn't save to the final storage yet. Nested Transaction Example db = TransactionalKVStore() db.set("x", 0) db.begin() # Level 1 db.set("x", 1) db.begin() # Level 2 (nested) db.set("x", 2) print(db.get("x")) # 2 db.begin() # Level 3 (nested) db.set("x", 3) db.rollback() # Undo Level 3 print(db.get("x")) # 2 (Back to Level 2) db.commit() # Merge Level 2 into Level 1 print(db.get("x")) # 2 db.rollback() # Undo Level 1 print(db.get("x")) # 0 (Original value) Testing Nested Logic # Test 1: Multiple levels db = TransactionalKVStore() db.set("a", 1) db.begin() # Level 1 db.set("a", 2) db.begin() # Level 2 db.set("a", 3) db.commit() # Merge Level 2 -> Level 1 assert db.get("a") == 3 db.rollback() # Undo Level 1 assert db.get("a") == 1 # Back to original # Test 2: Separate keys in different levels db = TransactionalKVStore() db.begin() db.set("outer", 1) db.begin() db.set("inner", 2) db.rollback() assert db.get("inner") is None assert db.get("outer") == 1 db.commit() assert db.get("outer") == 1 # Test 3: Delete in nested transaction db = TransactionalKVStore() db.set("key", "original") db.begin() db.set("key", "modified") db.begin() db.delete("key") assert db.get("key") is None db.rollback() assert db.get("key") == "modified" # Test 4: Outer rollback undoes committed inner transaction db = TransactionalKVStore() db.set("x", 0) db.begin() # Level 1 db.begin() # Level 2 db.set("x", 100) db.commit() # Merge Level 2 -> Level 1 assert db.get("x") == 100 # We see the change db.rollback() # Undo Level 1 assert db.get("x") == 0 # Original value! Inner commit is gone too. # Test 5: Read-your-write db = TransactionalKVStore() db.begin() db.set("new_key", "new_value") assert db.get("new_key") == "new_value" # Read your own change db.rollback() Step 3: Real-World Issues Things to Discuss After writing the code, explain how you would handle these real-world problems: Concurrency & Thread Safety How do you handle multiple threads trying to write at the same time? What isolation levels (like read committed or serializable) will you use? How do you stop deadlocks? Durability & Persistence How do you save data to the hard drive? Will you use a Write-Ahead Log (WAL)? How do you recover data if the computer crashes? Memory Management How do you stop transactions from using all the RAM (OOM)? When should you save transactions to disk instead of memory? How do you handle transactions that stay open for a long time? Performance Optimization Comparing Copy-on-write vs. Logging. Using snapshots vs. storing changes (deltas). Batching commits to make them faster. How to Solve It Questions for the Interviewer Do set and delete work if no transaction is open (auto-commit)? What happens if I call commit but no transaction is running? Should delete throw an error if the key doesn't exist? What data types are allowed for keys and values? Do we need to tell the difference between "deleted" and "never existed"? Solution for Step 1 Strategy: Use a main dictionary for permanent data. Use a separate dictionary for the current transaction (uncommitted changes). Store changes as a "delta" (a list of what changed). On commit, move the delta into the main dictionary. On rollback, throw the delta away. Code: class TransactionalKVStore: def __init__(self): self.committed = {} # Permanent storage self.transaction = None # Current transaction delta (or None) def get(self, key: str): # Check transaction first, then main storage if self.transaction is not None: if key in self.transaction: value = self.transaction[key] return None if value is _DELETED else value return self.committed.get(key) def set(self, key: str, value) -> None: if self.transaction is not None: self.transaction[key] = value else: self.committed[key] = value def delete(self, key: str) -> None: if self.transaction is not None: self.transaction[key] = _DELETED else: self.committed.pop(key, None) def begin(self) -> None: if self.transaction is not None: raise Exception("Transaction already in progress") self.transaction = {} def commit(self) -> None: if self.transaction is None: raise Exception("No transaction in progress") # Move changes to main storage for key, value in self.transaction.items(): if value is _DELETED: self.committed.pop(key, None) else: self.committed[key] = value self.transaction = None def rollback(self) -> None: if self.transaction is None: raise Exception("No transaction in progress") self.transaction = None # Marker for deleted keys class _DeletedType: pass _DELETED = _DeletedType() Solution for Step 2 Strategy: Use a stack (list) of dictionaries instead of just one. begin() adds a new empty dictionary to the stack. get() looks at the top of the stack first, then goes down to the bottom (main storage). commit() merges the top dictionary into the one below it. rollback() removes the top dictionary. Code: class TransactionalKVStore: def __init__(self): self.committed = {} # Permanent storage self.transactions = [] # Stack of changes def get(self, key: str): # Check active transactions first (from newest to oldest) for txn in reversed(self.transactions): if key in txn: value = txn[key] return None if value is _DELETED else value return self.committed.get(key) def set(self, key: str, value) -> None: if self.transactions: self.transactions[-1][key] = value else: self.committed[key] = value def delete(self, key: str) -> None: if self.transactions: self.transactions[-1][key] = _DELETED else: self.committed.pop(key, None) def begin(self) -> None: self.transactions.append({}) def commit(self) -> None: if not self.transactions: raise Exception("No transaction in progress") txn = self.transactions.pop() if self.transactions: # Merge into parent transaction parent = self.transactions[-1] for key, value in txn.items(): parent[key] = value else: # Merge into main storage for key, value in txn.items(): if value is _DELETED: self.committed.pop(key, None) else: self.committed[key] = value def rollback(self) -> None: if not self.transactions: raise Exception("No transaction in progress") self.transactions.pop() def in_transaction(self) -> bool: """Check if any transaction is active.""" return len(self.transactions) > 0 def transaction_depth(self) -> int: """Return how many nested levels there are.""" return len(self.transactions) class _DeletedType: pass _DELETED = _DeletedType() Time Complexity: Operation Time Complexity Notes get() O(d) d = how deep the transaction is set() O(1) Add to current dictionary delete() O(1) Mark as deleted in current dictionary begin() O(1) Add empty dictionary commit() O(k) k = keys changed in transaction rollback() O(1) Remove top dictionary Space Complexity: O(n + m) where n = keys in main storage and m = keys in all open transactions. Bonus Discussion Handling Multiple Users Approach 1: Transaction-local copies (MVCC) # Every transaction gets a snapshot of data when it starts. # Writes are local. Commit checks for conflicts. Approach 2: Pessimistic locking # Lock keys as soon as a transaction touches them. # Use timeouts to stop deadlocks. Approach 3: Optimistic concurrency control # Don't use locks. # Before committing, check if anyone else changed the data. If so, retry. Saving to Disk Write-Ahead Logging (WAL) Log every change before applying it. If the system crashes, replay the log to restore data. Clean up the log periodically. Copy-on-Write B-Trees Don't change data in place. Create new versions of pages. Update the root pointer atomically. Log-Structured Merge Trees (LSM) Add all writes to a log. Periodically compress the log into sorted files. Great for systems with many writes. Other Data Structures Approach Pros Cons Stack of dicts (our solution) Simple code Reads take O(d), uses memory per txn Copy-on-write snapshot Fast reads O(1) Uses lots of memory for large data Undo log Less memory for small txns Rollback is slow Version chains per key Very precise control Hard to code Final Checklist Thread safety: Use locks or lock-free code. Timeouts: Close transactions if they take too long. Size limits: Limit how big a transaction can be. Metrics: Monitor how many transactions commit or fail. Deadlocks: Detect if threads are waiting on each other forever. Recovery: Ensure data survives a crash. Garbage collection: Clean up old data versions.