Transactional Key-Value Store

Role: Software Engineer

Problem Overview

Design and implement an in-memory key-value store with full transaction support, including nested transactions. This is a common pattern in databases, version control systems, and configuration management tools.

Your implementation should support atomic operations that can be committed or rolled back, with nested transactions creating savepoints that can be independently rolled back without affecting the parent transaction.

Real-World Applications

Database transaction management
Configuration systems with preview/apply workflows
Undo/redo functionality in editors
Version control staging areas
Game state checkpointing

Requirements

Your implementation should support these operations:

get(key): Retrieve the value associated with the key. Returns None if the key doesn't exist.
set(key, value): Set a key to a value.
delete(key): Remove a key from the store.
begin(): Start a new transaction (can be nested).
commit(): Commit the current transaction, making changes permanent.
rollback(): Discard all changes made in the current transaction.

Example

python

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()         # Discard changes
print(db.get("a"))    # 1 (restored)

db.begin()            # Start transaction
db.set("a", 3)
db.commit()           # Commit changes
print(db.get("a"))    # 3 (persisted)

# Nested transactions
db.begin()            # Outer transaction
db.set("b", 10)
db.begin()            # Inner transaction (nested)
db.set("b", 20)
print(db.get("b"))    # 20
db.rollback()         # Rollback inner only
print(db.get("b"))    # 10 (outer transaction value)
db.commit()           # Commit outer
print(db.get("b"))    # 10 (persisted)

Part 1: Basic Transactions

Problem Statement

Implement a TransactionalKVStore class with single-level transaction support:

python

class TransactionalKVStore:
    def __init__(self):
        """Initialize the key-value store."""
        pass

    def get(self, key: str) -> any:
        """
        Get the value for a key.

        Returns:
            The value if key exists, None otherwise.
        """
        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 from the store."""
        pass

    def begin(self) -> None:
        """Start a new transaction."""
        pass

    def commit(self) -> None:
        """
        Commit the current transaction.

        Raises:
            Exception: If no transaction is in progress.
        """
        pass

    def rollback(self) -> None:
        """
        Rollback the current transaction.

        Raises:
            Exception: If no transaction is in progress.
        """
        pass

Test Cases

python

# Test 1: Basic get/set without transaction
db = TransactionalKVStore()
db.set("x", 100)
assert db.get("x") == 100
assert db.get("nonexistent") is None

# Test 2: Transaction commit
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: Transaction rollback
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 within 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"

Part 2: Nested Transactions

Problem Statement

Extend your implementation to support nested transactions. Each begin() call creates a new transaction level (like a savepoint). A rollback() only affects the innermost transaction, while a commit() merges changes into the parent transaction.

Nested Transaction Semantics

begin(): Creates a new nested transaction. Changes are isolated to this level.
commit(): Merges changes from the current transaction into the parent. If this is the outermost transaction, changes become permanent.
rollback(): Discards changes from the current transaction only. Parent transaction remains unaffected.

Key Behaviors:

Read-your-write consistency: Within a transaction, you must be able to read your own uncommitted writes immediately.
Outer rollback affects inner commits: If an outer transaction rolls back, all changes from already-committed inner transactions are also discarded (since inner commits only merge into the parent, not into permanent storage).

Example with Nested Transactions

python

db = TransactionalKVStore()
db.set("x", 0)

db.begin()            # Transaction level 1
db.set("x", 1)

db.begin()            # Transaction level 2 (nested)
db.set("x", 2)
print(db.get("x"))    # 2

db.begin()            # Transaction level 3 (nested)
db.set("x", 3)
db.rollback()         # Rollback level 3
print(db.get("x"))    # 2 (level 2's value)

db.commit()           # Commit level 2 into level 1
print(db.get("x"))    # 2

db.rollback()         # Rollback level 1
print(db.get("x"))    # 0 (original value)

Test Cases for Nested Transactions

python

# Test 1: Multi-level nesting
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()    # Rollback level 1
assert db.get("a") == 1  # Original value restored

# Test 2: Independent keys across 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()           # Commit level 2 -> merges into level 1
assert db.get("x") == 100  # Can see committed inner change
db.rollback()         # Rollback level 1
assert db.get("x") == 0    # Original value! Inner commit was also discarded

# Test 5: Read-your-write within transaction
db = TransactionalKVStore()
db.begin()
db.set("new_key", "new_value")
assert db.get("new_key") == "new_value"  # Read your own uncommitted write
db.rollback()

Part 3: Production Considerations

Discussion Topics

After implementing the core functionality, discuss how you would handle these production concerns:

Concurrency & Thread Safety
How would you handle concurrent transactions from multiple threads?
What isolation levels would you support (read uncommitted, read committed, repeatable read, serializable)?
How do you prevent deadlocks?
Durability & Persistence
How would you persist transactions to disk?
What's your write-ahead logging (WAL) strategy?
How do you handle crash recovery?
Memory Management
How do you limit transaction size to prevent OOM?
When should you spill transactions to disk?
How do you handle very long-running transactions?
Performance Optimization
Copy-on-write vs. logging-based approaches
When to use snapshots vs. delta-based storage
Batching commits for throughput

Solution Approach

Clarification Questions to Ask

Should set and delete work outside of a transaction (auto-commit mode)?
What should happen if commit() or rollback() is called with no active transaction?
Should delete() on a non-existent key raise an error or be a no-op?
What types should keys and values support?
Should we track if a key was deleted vs never existed?

Part 1: Basic Implementation

Strategy:

Use a main dictionary for committed data
Use a single transaction dictionary to track uncommitted changes
Each transaction records changes as a delta (overlay)
On commit, merge the delta into committed storage; on rollback, discard it

Basic Implementation:

python

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 committed 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")

        # Apply transaction changes to committed 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

# Sentinel for deleted keys
class _DeletedType:
    pass

_DELETED = _DeletedType()

Part 2: Nested Transaction Implementation

Strategy:

Use a stack of transaction deltas instead of a single delta
Each begin() pushes a new empty delta onto the stack
get() searches from top of stack down to committed storage
commit() merges the top delta into the one below (or committed if at root)
rollback() simply pops the top delta

Enhanced Implementation:

python

class TransactionalKVStore:
    def __init__(self):
        self.committed = {}       # Permanent storage
        self.transactions = []    # Stack of transaction deltas

    def get(self, key: str):
        # Search from innermost transaction outward
        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 committed 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 current nesting level (0 if no transaction)."""
        return len(self.transactions)

class _DeletedType:
    pass

_DELETED = _DeletedType()

Time Complexity:

Operation	Time Complexity	Notes
`get()`	O(d)	d = transaction depth
`set()`	O(1)	Insert into current delta
`delete()`	O(1)	Mark as deleted in current delta
`begin()`	O(1)	Push empty dict
`commit()`	O(k)	k = keys modified in transaction
`rollback()`	O(1)	Pop and discard

Space Complexity:

O(n + m) where n = committed keys and m = total keys across all transaction deltas

Follow-Up Discussion Topics

Concurrency Approaches

Approach 1: Transaction-local copies (MVCC-style)

python

# Each transaction sees a snapshot of the data at begin() time
# Writes are local; commit does conflict detection

Approach 2: Pessimistic locking

python

# Lock keys on first access within a transaction
# Detect deadlocks with timeout or wait-die scheme

Approach 3: Optimistic concurrency control

python

# No locks during transaction
# Validate and retry at commit time if conflicts detected

Persistence Strategies

Write-Ahead Logging (WAL)
Log all operations before applying
On crash, replay log to recover
Periodically checkpoint to truncate log
Copy-on-Write B-Trees
Never modify pages in place
Create new versions of modified pages
Atomic commit by updating root pointer
Log-Structured Merge Trees (LSM)
Append all writes to log
Periodically compact into sorted runs
Good for write-heavy workloads

Alternative Data Structures

Approach	Pros	Cons
Stack of dicts (above)	Simple, easy to understand	O(d) reads, memory per txn
Copy-on-write snapshot	O(1) reads, immutable	High memory for large data
Undo log	Lower memory for small txns	Rollback can be expensive
Version chains per key	Fine-grained versioning	More complex implementation

Production Checklist

Thread safety: Locks or lock-free structures
Transaction timeout: Prevent resource leaks from abandoned transactions
Size limits: Cap transaction delta size
Metrics: Track active transactions, commit/rollback rates
Deadlock detection: For multi-key transactions with locking
Recovery: WAL or checkpoint-based crash recovery
Garbage collection: Clean up old versions in MVCC systems