An OTP that disappears at exactly 30 seconds, a balance changed inside two nested transactions and then half rolled back, and eight threads incrementing one counter 4,000 times without losing a single increment.
"Build a key-value store" is two questions in one. The classic nested transactions puzzle: BEGIN, SET, BEGIN, SET, ROLLBACK, and what does GET say now? And the cache-server question: TTLs that free memory even for keys nobody reads again, eviction, and many clients at once. An Expert round wants both to fit together: what happens when two sessions read the same balance, add to it, and commit?
This lesson builds it in one process: committed data with versions, an expiry heap, a session per client with a stack of transaction layers, optimistic validation at commit, snapshots, and the eviction seam from the LRU lesson.
How the round runs#
"Build an in-memory key-value store. GET, SET with an optional TTL, DELETE. Clients can open transactions with BEGIN, nest them, and ROLLBACK or COMMIT. Uncommitted writes must be invisible to other clients. Many clients use it from different threads. When it's full, the policy should be configurable. Persistence and networking are out of scope."
- 0–10 min — clarify: commit semantics for nested transactions, isolation, TTL inside transactions, full-store behaviour
- 10–20 min —
Entry, versions, the eviction seam - 20–40 min — the store: lazy expiry, the expiry heap, apply-a-commit, eviction
- 40–65 min —
Session: a stack of layers, reads through the stack, rollback, nested commit, outermost commit with validation - 65–80 min — the demo: expiry, nesting, isolation, a conflict, an eight-thread counter, eviction, a snapshot
- 80–90 min — follow-ups: MVCC snapshots, sharding, persistence, memory accounting
Requirements and clarifying questions#
| You ask | They answer | What it changes |
|---|---|---|
What does an inner COMMIT do? |
Merge into the enclosing transaction; only the outermost commit reaches the store. | A stack of layers per session; commit pops and merges |
What does ROLLBACK undo? |
Only the innermost transaction. | Pop one layer and throw it away |
| Can other clients see uncommitted writes? | No. | Writes live in the session's layers, not the store |
| Two clients read-modify-write the same key? | The second commit must fail, not overwrite. | Versions per key; validate reads at commit |
| When does a TTL start inside a transaction? | When SET is called. |
expires_at is computed at write time |
| Expired keys nobody reads again? | They must still free memory. | Active expiry: a heap of deadlines and a bounded sweep |
| What if the store is full? | Configurable: refuse, or evict. | An EvictionPolicy interface |
Nested transactions, by hand
balance is 100. A session runs: BEGIN, SET balance 70, BEGIN, SET balance 40, DELETE user, ROLLBACK. What do GET balance and GET user return now, and what does another session see for balance?
One strong answer
The ROLLBACK discards only the inner layer, so the 40 and the delete are gone. This session reads through its remaining layer: balance is 70 and user is back. Another session reads only committed data, so it still sees 100. If the session now commits, the outer layer is the outermost, so 70 reaches the store and everyone sees it. The model that makes this easy: a transaction is a dict of pending writes stacked on top of the store; reads look from the top of the stack down, rollback pops, and commit merges into whatever is underneath.
The classes#
%% title: Key-value store: the classes
classDiagram
class KVStore {
-data dict
-expiry heap
-lock Lock
+max_keys int
+read(key) Entry
+commit(writes, reads)
+sweep(budget) int
+snapshot() Mapping
}
class Entry {
+value str
+expires_at float
+version int
}
class Session {
-stack list
+get(key) str
+set(key, value, ttl)
+delete(key)
+begin()
+rollback()
+commit()
}
class Txn {
+writes dict
+reads dict
}
class EvictionPolicy {
<<interface>>
+touch(key)
+forget(key)
+victim() str
}
KVStore "1" *-- "many" Entry
KVStore --> EvictionPolicy
Session --> KVStore
Session "1" *-- "many" Txn
EvictionPolicy <|.. NoEviction
EvictionPolicy <|.. LRUEvictionThe split that makes it work: the store holds only committed data; a session holds everything uncommitted. The store is shared and locked. A session belongs to one client thread, so its layers need no lock. They meet only in commit, which validates and applies a whole outermost transaction in one locked step.
Versions tell a commit whether someone else got there first. Every commit stamps the next number from a global counter on each entry it writes; a missing key is version 0. A transaction remembers the version of each key it read; at commit, if any has changed, the commit fails with Conflict. That's optimistic concurrency control: no locks held while a client thinks, a check at the end.
The interfaces#
Entries, pending writes, and the eviction seam:
# kv.py, part 1: entries with versions, pending writes, and the eviction seam
from __future__ import annotations
import heapq
import itertools
import threading
import time
from abc import ABC, abstractmethod
from collections import OrderedDict
from collections.abc import Callable, Mapping
from dataclasses import dataclass, field
from types import MappingProxyType
@dataclass(frozen=True)
class Entry:
value: str
expires_at: float | None # None: lives until deleted
version: int # the commit that wrote it; a missing key counts as version 0
def alive(self, now: float) -> bool:
return self.expires_at is None or now < self.expires_at
@dataclass(frozen=True)
class Pending:
value: str
expires_at: float | None
Write = Pending | None # None means "delete this key"
class EvictionPolicy(ABC):
evicts = True # False: refuse writes when full instead
@abstractmethod
def touch(self, key: str) -> None: ... # the key was read or written
@abstractmethod
def forget(self, key: str) -> None: ... # the key left the store
@abstractmethod
def victim(self) -> str: ...
class NoEviction(EvictionPolicy):
evicts = False
def touch(self, key: str) -> None:
pass
def forget(self, key: str) -> None:
pass
def victim(self) -> str:
raise LookupError("this policy never evicts")
class LRUEviction(EvictionPolicy):
"""OrderedDict is fine here; the LRU cache lesson builds the same thing by hand."""
def __init__(self) -> None:
self._order: OrderedDict[str, None] = OrderedDict()
def touch(self, key: str) -> None:
self._order[key] = None
self._order.move_to_end(key)
def forget(self, key: str) -> None:
self._order.pop(key, None)
def victim(self) -> str:
return next(iter(self._order))
class StoreFull(Exception): ...
class Conflict(Exception): ...The patterns, and why#
| Pattern | Where | Why it earns its place |
|---|---|---|
| Strategy | EvictionPolicy |
"Refuse" and "evict LRU" are both real choices; a TTL-aware or LFU policy is one more class. |
| Layered overlay (stack of dicts) | Session._stack |
Nested transactions in a few lines: read top-down, rollback pops, commit merges. |
| Optimistic concurrency control | versions, Txn.reads, KVStore.commit |
No lock is held while a client is "inside" a transaction, so a slow client can't block anyone. |
| Unit of work | KVStore.commit(writes, reads) |
A whole transaction is validated and applied in one locked step: all of it or none of it. |
| Heap with lazy deletion | the expiry heap | A key rewritten or deleted leaves a stale heap entry, recognised by its version and skipped. |
Concurrency and edge cases#
The store has one lock, and reads take it too. A read isn't read-only: it may find an expired key and delete it (lazy expiry), and it tells the eviction policy the key was used, which reorders the LRU list. That's the same lesson as in the LRU cache: in a store with recency or expiry, get writes.
Sessions don't lock. Their writes are invisible until the outermost commit, which checks every version the transaction read and applies every write, or raises Conflict and changes nothing. The client retries the whole transaction.
Why only reads are validated. Two transactions that blindly write x are fine in either order. One that read x and computed from it is only correct if x is unchanged at commit. Validating the read set makes every committed transaction equivalent to running alone at its commit moment.
- A key that expires between a transaction's read and its commit: its version is now 0, not what was read, so the commit conflicts. That's correct: the value it was based on is gone
- A TTL write inside a transaction that commits late: the TTL counted from the
SET; it may already be expired when committed. Say which rule you chose COMMITorROLLBACKwith no open transaction: an error, not a silent no-op- One commit bigger than the whole store: LRU may evict keys from the same commit; reject such commits if that matters
- A full store under
NoEviction: the check runs before any write, so the commit fails as a whole - A key rewritten many times with long TTLs: stale heap entries pile up until they come due; rebuild the heap when stale entries outnumber live ones
The code#
The store: committed data, expiry and eviction.
# part 2: the store: committed data, lazy and active expiry, eviction, all under one lock
class KVStore:
def __init__(self, max_keys: int = 1_000_000, eviction: EvictionPolicy | None = None, clock: Callable[[], float] = time.monotonic) -> None:
self.max_keys, self.clock = max_keys, clock
self.eviction = eviction or NoEviction()
self._data: dict[str, Entry] = {}
self._expiry: list[tuple[float, str, int]] = [] # min-heap of (expires_at, key, version)
self._versions = itertools.count(1)
self._lock = threading.Lock() # reads take it too: they may expire a key and they reorder the LRU
self.stats = {"expired_on_read": 0, "expired_by_sweep": 0, "evicted": 0}
def __len__(self) -> int:
return len(self._data)
def read(self, key: str) -> Entry | None:
with self._lock:
e = self._data.get(key)
if e is not None and not e.alive(self.clock()):
self._remove(key) # lazy expiry: an expired key is deleted the moment someone looks
self.stats["expired_on_read"] += 1
return None
if e is not None:
self.eviction.touch(key)
return e
def commit(self, writes: dict[str, Write], reads: dict[str, int]) -> None:
"""Validate a transaction's reads, then apply all its writes under one new version, or change nothing."""
with self._lock:
now = self.clock()
for key, seen in reads.items():
e = self._data.get(key)
if (e.version if e is not None and e.alive(now) else 0) != seen:
raise Conflict(f"{key} changed since this transaction read it")
grow = sum(1 for k, w in writes.items() if w is not None and k not in self._data)
if len(self._data) + grow > self.max_keys:
self._sweep(now, budget=len(self._expiry)) # expired keys go before live ones
grow = sum(1 for k, w in writes.items() if w is not None and k not in self._data)
if len(self._data) + grow > self.max_keys and not self.eviction.evicts:
raise StoreFull(f"{self.max_keys} keys and the policy doesn't evict")
version = next(self._versions)
for key, w in writes.items():
if w is None:
if key in self._data:
self._remove(key)
continue
self._data[key] = Entry(w.value, w.expires_at, version)
self.eviction.touch(key)
if w.expires_at is not None:
heapq.heappush(self._expiry, (w.expires_at, key, version)) # O(log n)
while len(self._data) > self.max_keys:
self._remove(self.eviction.victim())
self.stats["evicted"] += 1
def sweep(self, budget: int = 1_000) -> int:
"""Active expiry, run by a background timer: at most `budget` heap entries per call, so writers never wait long."""
with self._lock:
return self._sweep(self.clock(), budget)
def snapshot(self) -> Mapping[str, str]:
"""A point-in-time, read-only copy of the live keys. O(n) under the lock."""
with self._lock:
now = self.clock()
return MappingProxyType({k: e.value for k, e in self._data.items() if e.alive(now)})
def _sweep(self, now: float, budget: int) -> int:
removed = 0
while self._expiry and self._expiry[0][0] <= now and budget > 0:
_, key, version = heapq.heappop(self._expiry)
budget -= 1
e = self._data.get(key)
if e is not None and e.version == version: # stale entries (key rewritten or deleted) are skipped
self._remove(key)
removed += 1
self.stats["expired_by_sweep"] += removed
return removed
def _remove(self, key: str) -> None:
del self._data[key]
self.eviction.forget(key)A session: the client's view, with its stack of transactions.
# part 3: a session: one client's stack of transactions on top of the committed store
@dataclass
class Txn:
writes: dict[str, Write] = field(default_factory=dict)
reads: dict[str, int] = field(default_factory=dict) # key -> version first seen (0: missing)
class Session:
"""One client's view. Not shared between threads, so it needs no lock of its own."""
def __init__(self, store: KVStore) -> None:
self.store = store
self._stack: list[Txn] = []
def get(self, key: str) -> str | None:
for txn in reversed(self._stack): # newest layer first
if key in txn.writes:
w = txn.writes[key]
return None if w is None or (w.expires_at is not None and self.store.clock() >= w.expires_at) else w.value
e = self.store.read(key)
if self._stack:
self._stack[-1].reads.setdefault(key, e.version if e else 0) # remember what this decision was based on
return e.value if e else None
def set(self, key: str, value: str, ttl: float | None = None) -> None:
self._write(key, Pending(value, None if ttl is None else self.store.clock() + ttl))
def delete(self, key: str) -> None:
self._write(key, None)
def begin(self) -> None:
self._stack.append(Txn())
def rollback(self) -> None:
if not self._stack:
raise RuntimeError("no transaction")
self._stack.pop() # O(1): the layer is simply dropped
def commit(self) -> None:
if not self._stack:
raise RuntimeError("no transaction")
txn = self._stack.pop()
if self._stack: # nested: merge into the enclosing transaction, O(size of this layer)
parent = self._stack[-1]
parent.writes.update(txn.writes)
for key, version in txn.reads.items():
parent.reads.setdefault(key, version) # the earliest read of a key is what must still hold
else:
self.store.commit(txn.writes, txn.reads) # outermost: validate and apply, or raise Conflict
def _write(self, key: str, w: Write) -> None:
if self._stack:
self._stack[-1].writes[key] = w
else:
self.store.commit({key: w}, {}) # no transaction: a one-write commit
@property
def depth(self) -> int:
return len(self._stack)| Operation | Cost |
|---|---|
get |
O(d) for d open layers, then O(1) average in the store |
set, delete in a transaction |
O(1) |
set with a TTL, committed |
O(1), plus O(log n) to push onto the expiry heap |
begin, rollback |
O(1) |
nested commit |
O(w + r) for the layer's writes and reads |
outermost commit |
O(r + w), plus O(log n) per TTL write |
sweep |
O(k log n) for k heap entries examined, bounded by the budget |
snapshot |
O(n) |
The demo runs on a fake clock, so expiry is exact:
# part 4: expiry, nested transactions, isolation, a conflict, eight threads, eviction and a snapshot
if __name__ == "__main__":
class FakeClock:
def __init__(self) -> None:
self.t = 0.0
def __call__(self) -> float:
return self.t
clock = FakeClock()
store = KVStore(max_keys=1_000, eviction=LRUEviction(), clock=clock)
s = Session(store)
s.set("otp:asha", "4821", ttl=30)
s.set("user:asha", "Asha")
clock.t = 29.0
print("t=29:", s.get("otp:asha"))
clock.t = 30.0
print("t=30:", s.get("otp:asha"), store.stats)
for i in range(500):
s.set(f"sess:{i}", "x", ttl=60 if i % 2 else 600) # half for a minute, half for ten
clock.t = 91.0 # 61 s after they were written at t=30
print("swept:", store.sweep(), "| keys left:", len(store))
s.set("balance", "100")
s.begin()
s.set("balance", "70")
s.begin()
s.set("balance", "40")
s.delete("user:asha")
s.begin()
s.set("note", "three deep")
print("depth", s.depth, "|", s.get("balance"), s.get("user:asha"), s.get("note"))
s.rollback()
s.rollback()
print("depth", s.depth, "|", s.get("balance"), s.get("user:asha"), s.get("note"))
other = Session(store)
print("other session sees:", other.get("balance"))
s.commit()
print("after commit, other sees:", other.get("balance"))
a, b = Session(store), Session(store)
a.begin()
b.begin()
a.set("balance", str(int(a.get("balance")) + 10))
b.set("balance", str(int(b.get("balance")) + 20))
a.commit()
try:
b.commit()
except Conflict as e:
print("b:", e, "| balance:", other.get("balance"))
def incr(n: int) -> None:
sess = Session(store)
for _ in range(n):
while True: # optimistic: on conflict, run the whole transaction again
sess.begin()
sess.set("hits", str(int(sess.get("hits") or 0) + 1))
try:
sess.commit()
break
except Conflict:
pass
ts = [threading.Thread(target=incr, args=(500,)) for _ in range(8)]
for t in ts:
t.start()
for t in ts:
t.join()
print("hits after 8 threads x 500:", other.get("hits"))
snap = store.snapshot()
s.set("balance", "0")
print("snapshot:", snap["balance"], "| now:", s.get("balance"))
lru = KVStore(max_keys=3, eviction=LRUEviction(), clock=clock)
t3 = Session(lru)
for k in "abc":
t3.set(k, k.upper())
t3.get("a")
t3.set("d", "D")
print("LRU store of 3 keeps:", sorted(lru.snapshot()))
strict = Session(KVStore(max_keys=2, clock=clock))
strict.set("x", "1")
strict.set("y", "2")
try:
strict.set("z", "3")
except StoreFull as e:
print("no-eviction store:", e)t=29: 4821
t=30: None {'expired_on_read': 1, 'expired_by_sweep': 0, 'evicted': 0}
swept: 250 | keys left: 251
depth 3 | 40 None three deep
depth 1 | 70 Asha None
other session sees: 100
after commit, other sees: 70
b: balance changed since this transaction read it | balance: 80
hits after 8 threads x 500: 4000
snapshot: 80 | now: 0
LRU store of 3 keeps: ['a', 'c', 'd']
no-eviction store: 2 keys and the policy doesn't evictAt exactly 30 seconds the OTP is gone, deleted by the read itself. One sweep at t=91 removes the 250 one-minute session keys nobody read; 251 keys remain. After two rollbacks balance is 70 again, user:asha is back and note never existed, while another session sees 100 until the commit. Sessions a and b both read 70; a commits 80, and b fails instead of overwriting it with 90. Eight threads, retrying on conflict, end at exactly 4,000. The snapshot keeps 80 after balance is set to 0. The LRU store evicts b, because reading a made it recent; the no-eviction store refuses the third key.
Extending it: the follow-ups#
- "Reads in a transaction should see one consistent snapshot." That's snapshot isolation, and it needs MVCC: a short chain of versions per key, each transaction reading the newest version at or below the commit number it started at. Old versions are dropped once no open transaction can see them.
- "It's too slow under 64 threads." Shard keys into N stores by hash, a lock each. A transaction across shards locks its shards in sorted order to avoid deadlock.
- "Survive a restart." Append each committed transaction to a log before acknowledging it; replay on startup, with periodic snapshots to keep the replay short. Log TTLs as wall-clock times, since the monotonic clock resets.
- "Limit by memory, not key count." Track entry sizes and evict until the total fits; the seam doesn't change.
- "A TTL-aware policy." Evict the key closest to expiry: a new
EvictionPolicywith its own heap. Or sample a few random keys and evict the best of the sample.
Common mistakes#
- Copying the whole store on
BEGIN, O(n) per transaction, instead of a layer of changes - Writing straight to the store inside a transaction and keeping an undo log, so other sessions see uncommitted data
- Only lazy expiry, so keys nobody reads again never free their memory
- A full scan of all keys to expire them, holding the lock for the whole scan
- No version check at commit, so two read-modify-write transactions silently lose an update
- Holding the store lock from
BEGINtoCOMMIT, so one slow client stops everyone
Key-value store
Q1/3 A session runs BEGIN, SET x 1, BEGIN, SET x 2, COMMIT, ROLLBACK. What is x for everyone afterwards?
Answer & explanation
Answer: C
An inner COMMIT only merges its layer into the enclosing transaction. The ROLLBACK then discards that whole outer layer, 1 and 2 included. Only the outermost commit reaches the store.
Q2/3 Two sessions both read balance = 70 inside transactions, add 10 and 20, and commit. What happens?
Answer & explanation
Answer: D
Each transaction recorded balance's version when it read it. The first commit stamps a new version, so the second transaction's recorded version no longer matches, and its commit is rejected instead of losing the first update.
Q3/3 Why does a read take the store's lock in this design?
Answer & explanation
Answer: B
Lazy expiry turns a read into a delete, and recency tracking turns it into a reorder. Both change shared state, so reads are writes as far as the lock is concerned.
New lessons by email
New lessons, side quests and case files as they ship, at most once a week. No spam, unsubscribe anytime.
Discussion · …
Public: everyone reading this lesson sees comments. Be kind and keep it on the material.