Problem Statement

Implement the initial in-memory store with this interface:

class KeyValueStore:
    def get(self, key: str):
        pass

    def set(self, key: str, value):
        pass

    def delete(self, key: str):
        pass

Requirements

• set(key, value) must add a new key or replace its existing value.
• get(key) must return the associated value, or None when the key does not exist.
• delete(key) must remove the key when it is present.

Test Cases

db = KeyValueStore()
assert db.get("missing") is None

db.set("x", 10)
assert db.get("x") == 10

db.set("x", 20)
assert db.get("x") == 20

db.delete("x")
assert db.get("x") is None

These checks cover a missing lookup, insertion, replacement, and deletion.

Problem Statement

Expand the store with transaction operations:

class KeyValueStore:
    def begin(self):
        pass

    def commit(self):
        pass

    def rollback(self):
        pass

The complete API is:

class KeyValueStore:
    def get(self, key: str):...
    def set(self, key: str, value):...
    def delete(self, key: str):...
    def begin(self):...
    def commit(self):...
    def rollback(self):...

Requirements

• begin() must open a new transaction, which may be nested inside another active transaction.
• commit() must atomically merge the current transaction into its parent transaction. If there is no parent, it must apply the changes to the base store.
• rollback() must discard only the current transaction.
• Reads made within a transaction must observe its uncommitted writes and deletions.
• If the current transaction does not contain a key, reads must search the open ancestor transactions before falling back to the base store.
• get must return None both for absent keys and for keys deleted by an active transaction.
• Calling commit() or rollback() without an open transaction must raise an error.
• The stated performance target is O(1) amortized operations. Also discuss the cost of committing the keys changed by a transaction and the requested O(1)-style behavior for ordinary operations.

Test Cases

db = KeyValueStore()
db.set("a", 1)
assert db.get("a") == 1

db.begin()
db.set("a", 2)
db.set("b", 3)
assert db.get("a") == 2
assert db.get("b") == 3
db.rollback()
assert db.get("a") == 1
assert db.get("b") is None

db.begin()
db.delete("a")
assert db.get("a") is None
db.commit()
assert db.get("a") is None

The rollback removes both staged writes, while the later committed deletion permanently removes "a".

Nested Transaction Example

set("a", 1)
begin()
set("a", 2)
get("a") # → 2
begin()
set("a", 3)
rollback()
get("a") # → 2
commit()
get("a") # → 2

Rolling back the inner transaction exposes the parent transaction's value 2, which is then committed to the base store.

Edge Cases

Be prepared to handle and discuss:

• commit() or rollback() when no transaction is open.
• Rolling back a nested transaction after a sibling transaction has committed.
• Reading a key deleted inside a nested transaction.
• Transaction stacks with very large nesting depth.

Problem Statement

Allow multiple threads to invoke the store concurrently without violating transaction semantics.

Requirements

• Every operation must be thread-safe.
• commit() and rollback() must behave atomically.
• Each thread must have an independent transaction stack rather than sharing one global transaction context.
• Transaction behavior must remain correct when calls from different threads overlap.
• Concurrent updates to the same keys must not silently lose committed writes.

Follow-up 1: Concurrent Transactions

Discuss a design that maintains one transaction stack per thread while synchronizing access to shared committed state. Address the difficulty of preserving atomic commits when a transaction modifies several keys, including the tradeoff between a lock around base-store mutation and finer-grained per-key locks.

Follow-up 2: Large Values Stored on Disk

For the senior variant, assume values are large blobs stored on disk. Provide pseudocode for acquiring and releasing a per-key lock, and discuss contention and read amplification.

The lock must cover the complete read-from-disk, modify, write-to-disk sequence. Locking only an individual disk operation is insufficient because concurrent writers could otherwise interleave their work and observe dirty data. Also discuss what happens if an on-disk commit fails partway through, along with durability and recovery considerations such as write-ahead logging.