Design an in-memory key-value store with transactions¶
TL;DR¶
- You build a store whose committed state is one dict and whose transactions are a stack of write-sets layered over it; a read walks the stack outward and stops at the first level that mentions the key.
- Three decisions carry the interview: a delete is a tombstone, not a removal, a nested
COMMITmerges into its parent rather than into storage, and the transaction stack is per session so one thread's rollback cannot discard another's work. - Patterns that earn their place: Unit of Work (the write-set), Memento (a savepoint you pop), Strategy (isolation), Command (the log record you replay), Facade (the REPL).
Problem statement¶
"Design an in-memory key-value store with transactions. It supports get, set, delete, exists, incr and a prefix scan, plus BEGIN, COMMIT and ROLLBACK — and transactions nest. A read inside a transaction must see that transaction's own uncommitted writes. Keys may carry a TTL. Several threads use the store at once. Walk me through what BEGIN; SET a 1; BEGIN; DELETE a; ROLLBACK; COMMIT leaves behind, and then tell me how you would make it durable."
Requirements¶
Functional
get,set,delete,exists, plusincranddecron integer values.BEGIN,COMMITandROLLBACK, arbitrarily nested.- Reads inside a transaction see that transaction's own uncommitted writes.
- Per-key TTL, expired lazily on read, with an explicit purge.
- Prefix scan and snapshot iteration over the merged view.
- Thread safety, with an explicit answer for what two concurrent transactions see.
- An optional append-only log, and recovery by replaying it.
- An optional command parser, so the store can be driven as a REPL.
Non-functional and constraints
getandsetstay O(1) at depth zero, and O(depth) inside nested transactions — depth is a handful, not a scale factor.- A commit is atomic: either every staged write lands, or none does, and the log records it as one batch.
- Deterministic and testable: the clock is injected, so a five-minute TTL is proven in microseconds.
Out of scope: multi-version concurrency control, replication, Redis data types beyond strings and integers, and any network protocol.
Clarifying questions and assumptions¶
| Question to ask | Assumption taken here |
|---|---|
What does a nested COMMIT mean? |
It merges into the parent write-set. Only the outermost commit touches storage — say this before writing anything. |
| Are transactions per connection or global? | Per session. The stack lives in threading.local, so two threads are isolated by construction. |
| What do concurrent transactions see of each other? | Nothing until commit. The conflict rule is a Strategy: last-write-wins by default, optimistic version checks when you ask for them. |
| Is TTL fixed at write time or at commit time? | At write time, because the value is what carries the deadline. A long transaction can therefore commit an already-expired key. |
Does delete inside a transaction return whether the key existed? |
Yes, judged through the chain, which is what the caller means by "existed". |
What should incr do on a missing key? |
Treat it as 0. On a string it raises rather than coercing. |
| How durable does this need to be? | An append-only log behind a Protocol, one append per commit. The fsync policy is the real durability question and belongs in the discussion. |
Core entities and relationships¶
KVStore— the aggregate: committedStorageunder oneRLock, a per-sessionTransactionStack, anIsolationPolicyand anAppendOnlyLog.Storage— the committed dict plus a version per key and lazy TTL evaluation. It never locks; the store holds the lock around every call.Entry— a frozen cell: value plus an absoluteexpires_at.Transaction— one savepoint:writes(aNonevalue is a tombstone) andreads(key to the base version seen).TransactionStack— the chain, withlookupwalking innermost outward.IsolationPolicywithLastWriteWinsandOptimisticIsolation— what happens at the outermost commit.AppendOnlyLogwithNullLogandInMemoryLog;LogEntryis the record.CommandParser— the REPL facade.
Multiplicities: store 1 → 1 storage, store 1 → 1 stack per thread, stack 1 → * transactions, transaction 1 → * staged entries, store 1 → 1 isolation policy and 1 → 1 log.
Class diagram¶
One dict of committed truth, a stack of write-sets over it, and two seams: isolation and durability.
classDiagram
class KVStore {
-_lock: RLock
-_sessions: local
+stack: TransactionStack
+depth: int
+begin() str
+commit() str
+rollback() str
+get(key, default) Value
+set(key, value, ttl)
+delete(key) bool
+incr(key, by) int
+scan(prefix) List
+restore(log, clock) KVStore
}
class Storage {
-_entries: Dict~str,Entry~
-_versions: Dict~str,int~
+get(key, now) Entry
+version(key) int
+set(key, entry)
+delete(key) bool
+snapshot(now) Dict~str,Entry~
}
class Entry {
+value: Value
+expires_at: float
+is_expired(now) bool
}
class Transaction {
+id: str
+writes: Dict~str,Entry~
+reads: Dict~str,int~
+stage(key, entry)
+lookup(key) Tuple
+merge_into(parent)
}
class TransactionStack {
+push(transaction)
+pop() Transaction
+top() Transaction
+lookup(key) Tuple
+levels() List~Transaction~
}
class IsolationPolicy {
<<interface>>
+validate(transaction, storage)
}
class LastWriteWins
class OptimisticIsolation
class VersionSource {
<<interface>>
+version(key) int
}
class AppendOnlyLog {
<<interface>>
+append(records)
+replay() List~LogEntry~
}
class NullLog
class InMemoryLog {
+batches: int
}
class LogEntry {
+operation: Operation
+key: str
+value: Value
+of(key, entry) LogEntry
}
class CommandParser {
+execute(line) str
+run(script) List~str~
}
KVStore "1" *-- "1" Storage
KVStore "1" *-- "many" TransactionStack
KVStore --> IsolationPolicy
KVStore --> AppendOnlyLog
Storage "1" o-- "many" Entry
Storage ..|> VersionSource
TransactionStack "1" o-- "many" Transaction
Transaction "1" o-- "many" Entry
IsolationPolicy <|.. LastWriteWins
IsolationPolicy <|.. OptimisticIsolation
OptimisticIsolation ..> VersionSource : checks
AppendOnlyLog <|.. NullLog
AppendOnlyLog <|.. InMemoryLog
AppendOnlyLog ..> LogEntry : stores
CommandParser --> KVStoreDesign patterns applied¶
| Pattern | Where | Why it earns its place |
|---|---|---|
| Unit of Work | Transaction.writes |
Changes are collected and applied in one step at commit, which is the definition of atomicity here. Nothing reaches Storage until the outermost commit runs. |
| Memento | TransactionStack |
Each BEGIN captures a savepoint that ROLLBACK pops. The caretaker (the stack) never reads inside a transaction — it only pushes, pops and merges. |
| Command | LogEntry and the replay in restore |
Every mutation is reified as a record with enough information to be re-applied, which is what makes recovery a for loop instead of a special case. |
| Strategy | IsolationPolicy |
"What if two transactions touch the same key?" is a policy question with more than one right answer. Swapping LastWriteWins for OptimisticIsolation changes nothing else. |
| Facade | CommandParser |
String handling, argument counts and reply formatting stay out of the store, which keeps a Python API for callers who have one. |
| Iterator | KVStore.__iter__ |
Iteration is over a snapshot, so writing during a loop cannot corrupt it — the failure mode a naive for key in self._entries produces. |
| Null Object | NullLog |
The default log does nothing, so the store never asks whether durability is configured. |
What was deliberately not used: MVCC. Keeping a version chain per key and giving each transaction a read snapshot is what a real database does, and it is the right answer to "how do I stop writers from blocking readers" — but it is a different problem with garbage collection attached, and pretending to it in forty-five minutes produces something subtly wrong. Name it as the next step instead. A class per transaction state is also skipped: a transaction is open until it is popped, and that is not three states.
Key flows¶
A read walks the chain from the innermost savepoint outward and stops at the first level that mentions the key.
sequenceDiagram
autonumber
actor C as Client
participant K as KVStore
participant T as TransactionStack
participant S as Storage
C->>K: SET a alice
K->>S: depth 0, so write straight through
C->>K: BEGIN
K->>T: push Transaction(tx-1)
C->>K: SET a bob
K->>T: stage a to bob on tx-1
C->>K: GET a
K->>T: lookup(a)
T-->>K: found on tx-1, value bob
C->>K: BEGIN then DELETE a
K->>T: push tx-2, stage a to a tombstone
C->>K: GET a
T-->>K: found on tx-2, tombstone, so absent
C->>K: ROLLBACK
K->>T: pop tx-2 and discard it
C->>K: COMMIT
T-->>K: tx-1 is outermost
K->>S: apply the whole write-set, then append one log batchOptimistic isolation: the losing commit is refused, not silently merged.
sequenceDiagram
autonumber
participant A as SessionA
participant B as SessionB
participant K as KVStore
participant S as Storage
A->>K: BEGIN then GET balance
K->>S: version(balance)
S-->>K: 1
K->>K: record reads balance to 1
B->>K: SET balance 90 at depth 0
K->>S: set, version becomes 2
A->>K: SET balance 80 then COMMIT
K->>S: version(balance)
S-->>K: 2
K-->>A: TransactionConflictError, retry your work
Note over A,S: with LastWriteWins the same commit succeeds and B's write is lostImplementation¶
Write the vocabulary, then the chain — the chain is the problem — then the store that wraps it.
Two errors carry the design conversation: NoTransactionError for a COMMIT with nothing open, and TransactionConflictError for a commit built on a stale read.
code/lld/kv_store_transactions/models.py — operations and errors
class Operation(StrEnum):
SET = "set"
DELETE = "delete"
class NoTransactionError(InvalidStateError):
"""COMMIT or ROLLBACK with nothing open."""
class TransactionConflictError(ConflictError):
"""Under optimistic isolation, a key this transaction read changed underneath it."""
class KeyMissingError(NotFoundError):
"""A strict read (``store[key]``) for a key that is absent or expired."""
class ValueTypeError(ValidationError):
"""INCR or DECR on a value that is not an integer."""
class CommandError(ValidationError):
"""The REPL could not parse or dispatch a line."""
Entry is frozen so that copying a write-set into a parent copies references and cannot alias mutable state. LogEntry.of is the one place a staged cell becomes a durable record.
code/lld/kv_store_transactions/models.py — the stored cell and the log record
@dataclass(frozen=True, slots=True)
class Entry:
"""One committed or staged cell: a value and an optional absolute deadline.
Frozen because a write replaces the cell rather than mutating it - which is
what makes a write-set safe to copy into a parent on commit.
"""
value: Value
expires_at: float | None = None
def is_expired(self, now: float) -> bool:
return self.expires_at is not None and now >= self.expires_at
@dataclass(frozen=True, slots=True)
class LogEntry:
"""One durable record. A commit appends its whole write-set as a single batch,
so recovery can never observe half a transaction."""
operation: Operation
key: str
value: Value | None = None
expires_at: float | None = None
@classmethod
def of(cls, key: str, entry: Entry | None) -> LogEntry:
if entry is None:
return cls(Operation.DELETE, key)
return cls(Operation.SET, key, entry.value, entry.expires_at)
Now the heart of it. Two details are worth saying out loud before you type them: a tombstone is a key mapped to None, not a missing key, and merge_into moves writes down one level rather than committing them.
code/lld/kv_store_transactions/transactions.py — the write-set chain
@dataclass(slots=True)
class Transaction:
"""One savepoint: what it wrote, and what it read from the level below.
A delete is a tombstone - ``writes[key] = None`` - and not a removal from the
dict. The difference is the whole trick: "deleted at this level" has to be
distinguishable from "this level never mentioned the key", or a DELETE inside
a transaction would fall through and return the committed value.
"""
id: str
writes: dict[str, Entry | None] = field(default_factory=dict)
reads: dict[str, int] = field(default_factory=dict) # key -> base version when first read
def stage(self, key: str, entry: Entry | None) -> None:
self.writes[key] = entry
def lookup(self, key: str) -> tuple[bool, Entry | None]:
"""``(True, entry)`` or ``(True, None)`` for a tombstone; ``MISSING`` otherwise."""
if key in self.writes:
return True, self.writes[key]
return MISSING
def observe(self, key: str, version: int) -> None:
"""Record the committed version behind a read, once, for conflict detection."""
self.reads.setdefault(key, version)
def merge_into(self, parent: Transaction) -> None:
"""Nested COMMIT: the writes move down one level, they do not become durable.
This is the semantic interviewers probe. After ``BEGIN; SET a 1; BEGIN;
SET a 2; COMMIT; ROLLBACK`` the store must hold nothing: the inner commit
only handed ``a = 2`` to its parent, and the outer rollback threw it away.
"""
parent.writes.update(self.writes)
for key, version in self.reads.items():
parent.observe(key, version)
class TransactionStack:
"""A per-session stack of savepoints. Depth zero means autocommit.
It is per session, not per store: two threads each running a transaction must
not see each other's staged writes, and a stack shared between them would
make ``ROLLBACK`` on one thread discard the other's work.
"""
def __init__(self) -> None:
self._levels: list[Transaction] = []
def __len__(self) -> int:
return len(self._levels)
def push(self, transaction: Transaction) -> None:
self._levels.append(transaction)
def pop(self) -> Transaction:
return self._levels.pop()
def top(self) -> Transaction | None:
return self._levels[-1] if self._levels else None
def levels(self) -> list[Transaction]:
"""Outermost first. A merged view layers them in this order."""
return list(self._levels)
def clear(self) -> None:
self._levels.clear()
def lookup(self, key: str) -> tuple[bool, Entry | None]:
"""Walk from the innermost savepoint outward: the nearest write wins."""
for level in reversed(self._levels):
found, entry = level.lookup(key)
if found:
return True, entry
return MISSING
def staged_keys(self) -> set[str]:
return {key for level in self._levels for key in level.writes}
Isolation is a policy object because the question has more than one defensible answer. OptimisticIsolation is compare-and-set widened from one key to a whole read-set.
code/lld/kv_store_transactions/transactions.py — isolation policies
class VersionSource(Protocol):
"""What an isolation policy needs from committed storage: the version of a key."""
def version(self, key: str) -> int: ...
class IsolationPolicy(Protocol):
"""Runs at the outermost COMMIT, just before the write-set becomes durable."""
def validate(self, transaction: Transaction, storage: VersionSource) -> None: ...
class LastWriteWins:
"""No validation: whoever commits last overwrites. Cheap, and lost updates are possible."""
def validate(self, transaction: Transaction, storage: VersionSource) -> None:
return None
class OptimisticIsolation:
"""Refuse the commit if any key this transaction read has changed since it read it.
This is compare-and-set widened to a whole transaction, and it is what turns
read-modify-write sequences such as INCR into something safe without holding
a lock across the caller's thinking time. The cost is that a loser must redo
its work, so it suits low-conflict workloads and not a single hot key.
"""
def validate(self, transaction: Transaction, storage: VersionSource) -> None:
for key, seen in transaction.reads.items():
current = storage.version(key)
if current != seen:
raise TransactionConflictError(
f"key {key!r} changed from version {seen} to {current} during the transaction"
)
Committed storage keeps a version per key, and the versions outlive their keys — a transaction that read a key as absent still has to notice that someone created it.
code/lld/kv_store_transactions/services.py — storage and the log
class Storage:
"""Committed state: the values, a version per key, and lazy TTL expiry.
Versions outlive their keys. A transaction that read a key and found nothing
still needs to notice if someone created it before the commit, so "absent"
has to carry a version too - which it does, because ``delete`` bumps the
counter instead of dropping it.
Nothing here locks. The store owns the lock and holds it around every call.
"""
def __init__(self) -> None:
self._entries: dict[str, Entry] = {}
self._versions: dict[str, int] = {}
def get(self, key: str, now: float) -> Entry | None:
"""A pure read: an expired entry reports absent but is not removed here."""
entry = self._entries.get(key)
return None if entry is None or entry.is_expired(now) else entry
def version(self, key: str) -> int:
return self._versions.get(key, 0)
def set(self, key: str, entry: Entry) -> None:
self._entries[key] = entry
self._versions[key] = self._versions.get(key, 0) + 1
def delete(self, key: str) -> bool:
if key not in self._entries:
return False
del self._entries[key]
self._versions[key] = self._versions.get(key, 0) + 1
return True
def snapshot(self, now: float) -> dict[str, Entry]:
return {key: entry for key, entry in self._entries.items() if not entry.is_expired(now)}
def purge_expired(self, now: float) -> int:
dead = [key for key, entry in self._entries.items() if entry.is_expired(now)]
for key in dead:
self.delete(key)
return len(dead)
def __len__(self) -> int:
return len(self._entries)
class AppendOnlyLog(Protocol):
"""Durability seam. One ``append`` per commit, never one per write."""
def append(self, records: Sequence[LogEntry]) -> None: ...
def replay(self) -> list[LogEntry]: ...
class NullLog:
"""Null Object: the default, so the store never has to ask whether logging is on."""
def append(self, records: Sequence[LogEntry]) -> None:
return None
def replay(self) -> list[LogEntry]:
return []
class InMemoryLog:
"""Stands in for an append-only file. ``batches`` is what proves commits are atomic."""
def __init__(self) -> None:
self._lock = threading.Lock()
self._records: list[LogEntry] = []
self._batches = 0
def append(self, records: Sequence[LogEntry]) -> None:
if not records:
return
with self._lock:
self._records.extend(records)
self._batches += 1
def replay(self) -> list[LogEntry]:
with self._lock:
return list(self._records)
@property
def batches(self) -> int:
with self._lock:
return self._batches
The store itself is then thin: _read walks the chain and falls through, _write stages or autocommits, and commit has exactly two branches.
code/lld/kv_store_transactions/services.py — the store
class KVStore:
"""The store: committed storage under one lock, plus a write-set chain per session.
Two pieces of state, and they are guarded very differently.
* ``_storage`` is shared, so a single ``threading.RLock`` covers every read
and write of it. One coarse lock is the honest answer for interactive
transactions: the alternative is multi-version concurrency control, and
claiming per-key locks would be a lie, because a commit has to apply a
whole write-set atomically.
* The transaction stack is *per session*, kept in ``threading.local``. It
needs no lock at all, because exactly one thread can reach it - and it is
the reason one thread's ``ROLLBACK`` cannot throw away another's work.
"""
def __init__(
self,
clock: Clock | None = None,
ids: IdGenerator | None = None,
isolation: IsolationPolicy | None = None,
log: AppendOnlyLog | None = None,
) -> None:
self._clock = clock or SystemClock()
self._ids = ids or SequentialIdGenerator("tx")
self._isolation = isolation or LastWriteWins()
self._log: AppendOnlyLog = log or NullLog()
self._storage = Storage()
self._lock = threading.RLock()
self._sessions = threading.local()
# -- transactions ------------------------------------------------------------
@property
def stack(self) -> TransactionStack:
"""This thread's savepoints. Created on first use, never shared."""
existing = getattr(self._sessions, "stack", None)
if existing is None:
existing = TransactionStack()
self._sessions.stack = existing
return existing
@property
def depth(self) -> int:
return len(self.stack)
def begin(self) -> str:
transaction = Transaction(self._ids.next_id())
self.stack.push(transaction)
return transaction.id
def rollback(self) -> str:
"""Discard the innermost savepoint. Everything below it is untouched."""
if not self.stack:
raise NoTransactionError("ROLLBACK with no open transaction")
return self.stack.pop().id
def commit(self) -> str:
"""Inner COMMIT merges into the parent; the outermost one becomes durable."""
if not self.stack:
raise NoTransactionError("COMMIT with no open transaction")
transaction = self.stack.pop()
parent = self.stack.top()
if parent is not None:
transaction.merge_into(parent)
return transaction.id
with self._lock:
self._isolation.validate(transaction, self._storage) # raises, and the work is lost
self._apply(transaction.writes)
self._log.append([LogEntry.of(key, entry) for key, entry in transaction.writes.items()])
return transaction.id
# -- data --------------------------------------------------------------------
def get(self, key: str, default: Value | None = None) -> Value | None:
entry = self._read(key)
return default if entry is None else entry.value
def __getitem__(self, key: str) -> Value:
entry = self._read(key)
if entry is None:
raise KeyMissingError(f"{key!r} is not in the store")
return entry.value
def exists(self, key: str) -> bool:
return self._read(key) is not None
def set(self, key: str, value: Value, ttl: float | None = None) -> None:
if not key:
raise ValidationError("key must be non-empty")
if ttl is not None and ttl <= 0:
raise ValidationError("ttl must be positive; use delete() to remove a key")
deadline = None if ttl is None else self._clock.now() + ttl
self._write(key, Entry(value, deadline))
def delete(self, key: str) -> bool:
existed = self._read(key) is not None
self._write(key, None)
return existed
def incr(self, key: str, by: int = 1) -> int:
"""Read-modify-write. Outside a transaction it is one atomic step under the lock.
Inside a transaction it cannot be: the read happens now and the write
lands at COMMIT, so the gap between them is real. That gap is exactly
what ``OptimisticIsolation`` exists to detect.
"""
if self.stack.top() is None:
with self._lock:
entry = self._storage.get(key, self._clock.now())
updated = Entry(_as_int(key, entry) + by, entry.expires_at if entry else None)
self._apply({key: updated})
self._log.append([LogEntry.of(key, updated)])
return int(updated.value)
entry = self._read(key)
updated = Entry(_as_int(key, entry) + by, entry.expires_at if entry else None)
self._write(key, updated)
return int(updated.value)
def decr(self, key: str, by: int = 1) -> int:
return self.incr(key, -by)
def scan(self, prefix: str = "") -> list[tuple[str, Value]]:
"""The merged view: committed state with every open savepoint layered on top."""
now = self._clock.now()
with self._lock:
merged = self._storage.snapshot(now)
visible = {key: entry for key, entry in merged.items() if key.startswith(prefix)}
for level in self.stack.levels(): # outermost first, so the innermost wins
for key, entry in level.writes.items():
if not key.startswith(prefix):
continue
if entry is None or entry.is_expired(now):
visible.pop(key, None)
else:
visible[key] = entry
return sorted((key, entry.value) for key, entry in visible.items())
def count(self, value: Value) -> int:
"""How many visible keys hold ``value``. O(n) - see the page for the index variant."""
return sum(1 for _, held in self.scan() if held == value)
def __iter__(self) -> Iterator[tuple[str, Value]]:
"""Iterate a *snapshot*, so writing during the loop cannot corrupt it."""
return iter(self.scan())
def __len__(self) -> int:
return len(self.scan())
def purge_expired(self) -> int:
with self._lock:
return self._storage.purge_expired(self._clock.now())
# -- recovery ----------------------------------------------------------------
@classmethod
def restore(cls, log: AppendOnlyLog, clock: Clock | None = None, **kwargs: object) -> KVStore:
"""Rebuild committed state by replaying the log, then keep writing to it."""
store = cls(clock=clock, **kwargs) # type: ignore[arg-type]
for record in log.replay():
if record.operation is Operation.DELETE:
store._storage.delete(record.key)
else:
store._storage.set(record.key, Entry(record.value, record.expires_at)) # type: ignore[arg-type]
store._log = log
return store
# -- internals ---------------------------------------------------------------
def _read(self, key: str) -> Entry | None:
"""Walk the chain, then fall through to committed storage and record the version."""
found, staged = self.stack.lookup(key)
if found:
if staged is None or staged.is_expired(self._clock.now()):
return None
return staged
with self._lock:
now = self._clock.now()
entry = self._storage.get(key, now)
version = self._storage.version(key)
top = self.stack.top()
if top is not None:
top.observe(key, version)
return entry
def _write(self, key: str, entry: Entry | None) -> None:
top = self.stack.top()
if top is not None:
top.stage(key, entry)
return
with self._lock: # autocommit: one write is its own transaction
self._apply({key: entry})
self._log.append([LogEntry.of(key, entry)])
def _apply(self, writes: dict[str, Entry | None]) -> None:
"""Caller holds the lock. Tombstones delete, everything else overwrites."""
for key, entry in writes.items():
if entry is None:
self._storage.delete(key)
else:
self._storage.set(key, entry)
def _as_int(key: str, entry: Entry | None) -> int:
"""A missing key counts as 0; anything non-integer is a type error, not a coercion."""
current = 0 if entry is None else entry.value
if not isinstance(current, int):
raise ValueTypeError(f"{key!r} holds {current!r}, which is not an integer")
return current
The parser exists because interviewers hand you a script, not a Python API:
code/lld/kv_store_transactions/repl.py — the command facade
class CommandParser:
"""One line in, one line out - the shape an interviewer asks you to drive the store with.
A Facade: it owns argument counts, type coercion and the reply format, so the
store keeps a Python API and never grows string handling. The dispatch table
means adding a verb is one method plus one entry.
"""
def __init__(self, store: KVStore) -> None:
self._store = store
self._verbs: dict[str, Callable[[Sequence[str]], str]] = {
"GET": self._get,
"SET": self._set,
"DEL": self._delete,
"DELETE": self._delete,
"EXISTS": self._exists,
"INCR": self._incr,
"DECR": self._decr,
"SCAN": self._scan,
"COUNT": self._count,
"BEGIN": self._begin,
"COMMIT": self._commit,
"ROLLBACK": self._rollback,
}
def execute(self, line: str) -> str:
parts = line.split()
if not parts:
raise CommandError("empty command")
verb, args = parts[0].upper(), parts[1:]
handler = self._verbs.get(verb)
if handler is None:
raise CommandError(f"unknown command {parts[0]!r}")
return handler(args)
def run(self, script: Iterable[str]) -> list[str]:
"""Run a script, turning a domain error into its message instead of raising."""
replies: list[str] = []
for line in script:
try:
replies.append(self.execute(line))
except HandbookError as exc:
replies.append(f"ERR {exc}")
return replies
# -- verbs -------------------------------------------------------------------
def _get(self, args: Sequence[str]) -> str:
value = self._store.get(self._one(args, "GET"))
return NIL if value is None else str(value)
def _set(self, args: Sequence[str]) -> str:
if len(args) not in (2, 4):
raise CommandError("usage: SET <key> <value> [EX <seconds>]")
ttl: float | None = None
if len(args) == 4:
if args[2].upper() != EXPIRY_FLAG:
raise CommandError(f"usage: SET <key> <value> [{EXPIRY_FLAG} <seconds>]")
ttl = float(args[3])
self._store.set(args[0], _coerce(args[1]), ttl=ttl)
return OK
def _delete(self, args: Sequence[str]) -> str:
return "1" if self._store.delete(self._one(args, "DEL")) else "0"
def _exists(self, args: Sequence[str]) -> str:
return "1" if self._store.exists(self._one(args, "EXISTS")) else "0"
def _incr(self, args: Sequence[str]) -> str:
return str(self._store.incr(args[0], int(args[1]) if len(args) > 1 else 1))
def _decr(self, args: Sequence[str]) -> str:
return str(self._store.decr(args[0], int(args[1]) if len(args) > 1 else 1))
def _scan(self, args: Sequence[str]) -> str:
pairs = self._store.scan(args[0] if args else "")
return " ".join(f"{key}={value}" for key, value in pairs) or "(empty)"
def _count(self, args: Sequence[str]) -> str:
return str(self._store.count(_coerce(self._one(args, "COUNT"))))
def _begin(self, args: Sequence[str]) -> str:
self._store.begin()
return f"{OK} depth={self._store.depth}"
def _commit(self, args: Sequence[str]) -> str:
self._store.commit()
return f"{OK} depth={self._store.depth}"
def _rollback(self, args: Sequence[str]) -> str:
self._store.rollback()
return f"{OK} depth={self._store.depth}"
@staticmethod
def _one(args: Sequence[str], verb: str) -> str:
if len(args) != 1:
raise CommandError(f"usage: {verb} <key>")
return args[0]
def _coerce(text: str) -> Value:
"""Integers stay integers so INCR works; everything else is a string."""
try:
return int(text)
except ValueError:
return text
Running python -m lld.kv_store_transactions.demo drives the store as a REPL, then shows TTL, recovery and a refused commit:
--- nesting: an inner ROLLBACK drops its own level and nothing else ---
SET user:1 alice -> OK
BEGIN -> OK depth=1
SET user:1 bob -> OK
BEGIN -> OK depth=2
DEL user:1 -> 1
GET user:1 -> (nil)
ROLLBACK -> OK depth=1
GET user:1 -> bob
COMMIT -> OK depth=0
GET user:1 -> bob
inner COMMIT only reaches the parent: after the outer ROLLBACK, GET flag -> (nil)
counters: OK | 5 | 3 | 3
prefix scan: user:1=bob user:2=bob
TTL: at 299 s -> token, at 301 s -> (nil), 4 keys visible
durability: a 3-write transaction appended 1 batch, 11 records in the log
recovery: restored user:1=bob hits=3 with 7 visible keys
optimistic isolation: slow session rejected, fast writer committed, balance=90
Concurrency and edge cases¶
Which lock protects what. One lock, and one deliberate absence of a lock.
KVStore._lockis a singlethreading.RLockaround every read and write ofStorage. It is coarse on purpose. A commit has to apply a whole write-set atomically, so per-key locks would have to be taken as a set, in a fixed order, and released together — that is a distributed-transaction protocol inside one process, for a store whose operations are a dict lookup. Redis makes exactly this trade, with one thread and no locks at all, and still serves on the order of 100k operations per second; an uncontended acquire here costs about 17 ns against a 100 ns main-memory reference, so the lock is not what limits you.- The transaction stack has no lock, because it lives in
threading.local. Exactly one thread can reach it. This is the answer to the question candidates usually miss: if the stack were an attribute of the store, one session'sROLLBACKwould discard another session's staged writes, anddepthwould be meaningless.
Where read-modify-write actually races. incr at depth zero holds the lock across the read and the write, so eight threads incrementing 800 times produce exactly 800. Inside a transaction it cannot: the read happens when you call it and the write lands at commit, and that gap is real. OptimisticIsolation is what closes it — it re-checks, at commit time and under the lock, that every version the transaction read is still current, and refuses the commit otherwise. The loser's work is gone and the caller must redo it, which is the trade optimistic control always makes.
Visibility rules, stated precisely. A read consults each open savepoint from innermost outward. A level "mentions" a key if the key is in its writes dict, tombstone included; that level's answer wins and the walk stops. If no level mentions it, the committed value applies, and the version behind it is recorded for conflict detection. Nothing outside the session can see a staged write, ever.
Nested commit and rollback. ROLLBACK pops and discards, which is why savepoints are a stack and not a list of diffs to invert. COMMIT pops and merges into the parent — parent.writes.update(child.writes) — so an inner commit is durable only if every enclosing transaction also commits. That single line is the semantic the whole question is built around.
TTL inside a transaction. The deadline is computed at set time from the injected clock, not at commit. A transaction open for longer than the TTL therefore commits a key that is already expired, and the next read reports it absent. That is defensible — the value carries its own lifetime — but it is a decision, so say it. The alternative, resolving deadlines at commit, makes GET inside the transaction inconsistent with GET after it.
Edge cases handled: COMMIT and ROLLBACK with nothing open raise instead of silently succeeding; delete reports existence judged through the chain, not from storage; incr treats a missing key as 0 and refuses a string rather than coercing; an empty key and a non-positive TTL are rejected; iteration is over a snapshot so writing mid-loop is safe; a rollback appends nothing to the log; and recovery replays TTLs as absolute instants, so a key that expired while the process was down stays expired.
Common mistake
Implementing DELETE inside a transaction as del write_set[key]. It looks right and it is exactly backwards: removing the key from the write-set means the read falls through to the committed value, so BEGIN; DELETE a; GET a returns the old value. The write-set is not a cache of pending values, it is a record of decisions, and "deleted" is a decision that has to be stored.
Extensibility and follow-ups¶
- MVCC: give each key a chain of versioned values and each transaction a read timestamp. Readers then never block writers, which is the real reason databases pay for it, and the cost is garbage collecting versions no live transaction can still see.
- Write-ahead log recovery in earnest: the log here appends one batch per commit, which is the property recovery depends on. Production adds a commit marker per batch so a torn tail can be discarded, a checkpoint so replay does not start from the beginning, and a stated fsync policy — every commit is durable and slow, every few milliseconds is fast and loses a window.
- A value-count index: answering "how many keys hold this value?" in O(1) needs a
dict[value, int]— and that index has to be transactional too, staged in the write-set and merged at commit, or a rollback leaves the counts wrong. Todaycountscans, which is O(n) and honest; explaining why the index is hard is worth more than a half-correct one. - Memory caps: track the byte size of committed state and reject or evict on a limit. A large write-set is the other half of that problem, since an uncommitted transaction is unbounded memory held by one session.
- Richer types: lists, sets and hashes turn
Entry.valueinto a union and every mutation into a typed command. The chain does not change; the merge does, because merging a list append is not the same as overwriting a value. - Distribution: partitioning by key, replication and cross-shard transactions is where this becomes a Dynamo-style design, and the transaction semantics become two-phase commit or sagas.
Interview tip
Before you write anything, say the invariant out loud: "a read walks the stack from the innermost transaction outward and stops at the first level that mentions the key — where a tombstone counts as mentioning it." Then write lookup. Candidates who start from get end up with special cases for delete; candidates who state the walk first get the whole problem in about fifteen lines.
Tests¶
tests/test_kv_store_transactions.py has 17 cases. The two to walk through are the nesting semantics and the per-session isolation.
code/lld/kv_store_transactions/tests/test_kv_store_transactions.py — nesting
def test_an_inner_commit_reaches_the_parent_and_no_further(store: KVStore) -> None:
"""The semantic every interviewer checks: a nested COMMIT is not durable.
`SET a 2` is committed by the inner transaction, so the outer one can see it -
and the outer ROLLBACK then throws away both levels of work.
"""
store.begin()
store.set("a", 1)
store.begin()
store.set("a", 2)
store.commit() # merges into the outer write-set, not into storage
assert store.get("a") == 2 and store.depth == 1
store.rollback()
assert store.get("a") is None and store.depth == 0
def test_an_inner_rollback_drops_only_its_own_level(store: KVStore) -> None:
store.set("a", "base")
store.begin()
store.set("a", "outer")
store.begin()
store.delete("a")
assert store.get("a") is None # the tombstone hides the outer write
store.rollback()
assert store.get("a") == "outer" # ... and only the tombstone went away
store.commit()
assert store.get("a") == "outer"
The first case is the one an interviewer will dictate; the second proves the tombstone rule, because after the inner rollback the outer write has to reappear rather than the committed value.
code/lld/kv_store_transactions/tests/test_kv_store_transactions.py — isolation
def test_two_sessions_never_see_each_other_s_staged_writes(store: KVStore) -> None:
"""The stack is per thread, so a transaction is invisible until it commits."""
store.set("k", "base")
gate = threading.Barrier(2)
seen: dict[str, object] = {}
def writer() -> None:
store.begin()
store.set("k", "staged")
gate.wait() # hold the transaction open while the reader looks
gate.wait()
store.commit()
def reader() -> None:
gate.wait()
seen["during"] = store.get("k")
gate.wait()
with ThreadPoolExecutor(max_workers=2) as pool:
list(pool.map(lambda job: job(), [writer, reader]))
assert seen["during"] == "base" # uncommitted work was never visible
assert store.get("k") == "staged"
def test_autocommit_incr_is_atomic_under_load(store: KVStore) -> None:
with ThreadPoolExecutor(max_workers=8) as pool:
list(pool.map(lambda _: store.incr("counter"), range(800)))
assert store.get("counter") == 800 # read-modify-write happens under one lock
A threading.Barrier makes the interleaving deterministic: the reader looks while the writer is provably mid-transaction, so "invisible until commit" is tested rather than hoped for. The second test is the counterpart on the committed side — 800 increments from eight threads, and no lost update.
The rest cover: read-your-own-writes; a delete committing as a removal; COMMIT and ROLLBACK with nothing open, via parametrize; incr inside a transaction and on a string; a TTL fixed at write time and surviving a commit; a prefix scan over the merged chain and snapshot iteration; optimistic isolation refusing a stale commit and last-write-wins accepting the same one; one log batch per commit with a rollback writing nothing, and a restore that replays it; and the parser running a script and reporting errors without aborting it. Run them with uv run pytest code/lld/kv_store_transactions -q.
45-minute pacing¶
| Minutes | What to do | What to say or write |
|---|---|---|
| 0–5 | Clarify | Do transactions nest? Per connection or global? What does a nested commit mean? TTL? Durability? |
| 5–9 | The model | Committed dict plus a stack of write-sets on the board. State the read walk and the tombstone rule before coding. |
| 9–18 | The chain | Transaction.stage and lookup, then TransactionStack.lookup. Draw the three-level example while writing it. |
| 18–26 | The store | get, set, delete, then begin, commit, rollback — with the two-branch commit called out explicitly. |
| 26–32 | Concurrency | Why the stack is per session, why one coarse lock, and where incr actually races. |
| 32–38 | Durability | One append per commit, replay on start, and the fsync trade. |
| 38–45 | Extensions | MVCC, the transactional value-count index, memory caps, and the hand-off to a distributed store. |
Related¶
- Design a Dynamo-style key-value store — the same store once it is partitioned and replicated
- Transactions, 2PC, sagas and idempotency — isolation levels and what a commit means across machines
- Unit of Work — collecting changes and applying them once
- Memento — savepoints as snapshots a caretaker cannot read into
- Command — the reified mutation behind log replay
- Facade — the shape of the command parser
- Primary sources: Gray and Reuter, Transaction Processing: Concepts and Techniques (1992), chapters on savepoints and logging; the PostgreSQL documentation on
SAVEPOINT