Design an In-Memory Key-Value Store
"Build a small in-memory database" is one of the most common machine-coding prompts, and one of the most deceptive. It starts innocently with SET a 10 and GET a. Ten minutes later the interviewer adds BEGIN and ROLLBACK, then asks how many keys currently hold the value 10, then wants keys to expire, then wants a snapshot. Each addition is small on its own. Together they interact in ways that break a careless design: a rollback has to fix the value index, an expired key must not be counted, a snapshot taken mid-transaction must not leak uncommitted writes, and a key that expires during a transaction must not come back to life when that transaction rolls back.
That's why this problem makes a good capstone for the course. It needs nothing exotic. A hash map, a list of maps and a couple of indexes are the whole data model. What it tests is whether you can keep several structures consistent through every path that changes them. The candidates who do well find the one method that every write passes through and put all the bookkeeping there. The candidates who struggle sprinkle index updates across ten command handlers and miss two.
This page is the low-level design of the store: classes inside one process, no network and no disk. The distributed version, with partitioning, replication and quorums, is a different question, covered in Design a Key-Value Store. If you've worked through Design an LRU / LFU Cache, you already have half of the TTL story. Here the focus moves from eviction to transactions, indexes and the command layer.
The page follows the steps from The LLD Interview Framework, and the code is shaped the way Machine Coding Rounds recommends: an in-memory model, a thin service, a text driver and tests.
1. Clarifying questions and requirements
The prompt is usually something like: "Implement an in-memory key-value store that supports get, set and delete, plus transactions." Before writing anything, turn it into a spec. These are the questions that change the design.
| Question | Why it matters | Answer we'll assume |
|---|---|---|
| What types are keys and values? | Typed values need a type tag and type errors | Both are strings. INCR parses the string as a 64-bit integer |
| Is it one client or many? | Many clients means isolation between transactions | One client in the core, many discussed in the concurrency section |
| Can transactions nest? | Nesting means a stack of layers, not one undo buffer | Yes, to any depth |
Does ROLLBACK undo everything or only the innermost BEGIN? | Defines the stack discipline | Only the innermost |
Does COMMIT close one level or all of them? | Classic puzzle versions close all levels | One level: the changes merge into the parent. An outer rollback still undoes them |
| Do keys expire? Per key? | Adds a clock and a second way for keys to vanish | Yes, per-key TTL, settable with SET ... EX or EXPIRE |
| Must expired keys be freed even if nobody reads them? | Lazy-only expiry leaks memory | Yes: lazy on read plus periodic active expiry |
| What does "count by value" return, and how fast? | An index, and whether it can be stale | Exact count of live keys with that value, without a full scan |
| What is a snapshot, and can it be taken mid-transaction? | Decides whether snapshots include uncommitted writes | An in-memory copy of committed state that can be restored later |
| What happens on a bad command? | Parser robustness | An ERR ... reply. The driver never crashes |
Does SET keep an existing TTL? | Redis clears it, and people get this wrong | SET clears it, INCR keeps it, as in Redis |
Functional requirements
get(key)returns the value, or nothing if the key is missing or expired.set(key, value)stores a value and clears any TTL.set(key, value, ttl)stores it with a TTL.delete(key)removes a key and reports whether it existed.exists(key)reports whether a live key exists.incr(key, by)treats the value as a signed 64-bit integer, with a missing key counting as zero. It rejects non-integers and overflow, and keeps the key's TTL.expire(key, ttl),persist(key)andttl(key)manage a key's time to live.ttlreturns -2 for a missing key and -1 for a key without a TTL, as Redis does.begin(),rollback()andcommit()support nested transactions. Rollback undoes only the innermost open transaction. Commit merges the innermost into its parent, and at depth one it makes the changes permanent.count(value)returns how many live keys hold exactly that value, inside or outside a transaction.snapshot()captures the committed state as an opaque object, andrestore(snapshot)puts it back.- A text driver accepts lines such as
SET a 10,BEGINandROLLBACKand returns one reply per line.
Non-functional requirements
get,set,delete,exists,incrandexpireare O(1) expected.countis O(k), where k is the number of keys holding that value, and never a scan of the whole store.rollbackandcommitcost O(keys touched in that layer), not O(store size).- Time comes from an injected clock, so TTL tests are instant and exact.
- Every index stays consistent with the data after every operation, including expiry, rollback and restore.
- Thread-safe in Java and Python. TypeScript runs on Node's single thread.
- Active expiry does bounded work per cycle, so it never stalls the store.
Out of scope
Persistence, networking, replication, typed values (lists, hashes, sets), pub/sub, and Lua scripting. Say them out loud. The interviewer wants to know you know they exist, and that you've chosen not to build them in 90 minutes.
Pacing it in the interview
In a 45-minute whiteboard round, you won't write all of this. Spend five minutes on the table above, five on entities and the transaction decision below, and then code set, get, the write path and the undo layers. Mention TTL and the index, and show where they would hook in. In a 90-minute machine-coding round, build in this order: the map and the driver, then transactions, then the value index (run your tests), then TTL with lazy expiry, then active expiry, then snapshots. Every step leaves a working program, and if the clock runs out, what you have still runs.
2. Entities
| Entity | Responsibility | Notes |
|---|---|---|
KvStore | The public API. Owns the data map, the value index, the TTL key set, the transaction layers and the lock | A facade over a few small structures |
Entry | A value plus an optional absolute expiry time | Immutable: a write replaces the entry rather than editing it |
| Transaction layer | For each key the layer has changed, the entry it had before the layer first touched it | A map. The layers form a stack |
| Value index | value → set of keys holding it | Keeps count away from a full scan |
VolatileKeys | The set of keys that have a TTL, with O(1) random pick | What active expiry samples from |
ExpiryStrategy | Decides how active expiry finds expired keys | Strategy: sampling, full scan, or none |
Clock | Supplies "now" in milliseconds | System clock in production, manual clock in tests |
Snapshot | An opaque copy of committed state | Memento |
Command | One parsed request that can execute against a session | Command: Get, SetCmd, Begin, and so on |
CommandParser | Turns a text line into a Command, checking name and arity | A table of name → (allowed arities, builder) |
Session | One client's context: the store plus the snapshots that client has named | Where per-client transaction state would live in a multi-client design |
The decision that shapes everything: where uncommitted writes live
There are two sound ways to implement nested transactions. Pick one deliberately and say why. This decision affects the value index, snapshots, TTL and concurrency.
Option A, overlay change sets. Writes inside a transaction go into the top layer as key → new value (or a deletion marker). The base map holds only committed data. A read walks the layers from top to bottom and falls through to the base. Commit merges the top layer into the one below. Rollback simply drops the top layer.
Option B, write-through with undo layers. Writes go straight into the one live map. Before a layer changes a key for the first time, it records the key's previous entry, its before-image. Rollback writes the before-images back. Commit merges the top layer's before-images into the parent, keeping the parent's own image where both have one, because the parent's is older.
Both are layered change sets. In A, the layers hold new values. In B, they hold old values. The trade-offs:
| Concern | A: overlay | B: write-through + undo |
|---|---|---|
get inside a transaction | O(depth): walk the layers | O(1): the map is always current |
count(value) inside a transaction | Hard. The index describes the base, so every layer needs its own index delta | Free. The single index is always current |
| TTL expiry inside a transaction | Must check every layer's copy | One place to check |
| Rollback | O(1): drop the layer | O(keys touched): write the before-images back |
| Other clients' visibility of uncommitted writes | Invisible: they read the base | Visible: dirty reads, unless something else prevents it |
| Snapshot of committed state | Copy the base | Copy the map, then apply the before-images to the copy |
For a single-client store, B wins clearly. The requirement that sinks A is count inside a transaction. An exact count over an overlay means either rescanning or maintaining a per-layer index delta, and merging deltas on commit. With B, the one index is correct at every moment, because every write, undo and expiry passes through a single method that maintains it.
B's weakness is the last two rows. Other clients would see uncommitted writes, and a snapshot has to subtract the open layers. The snapshot cost is small and handled below. The visibility problem matters only with several clients, and the concurrency section (section 7) shows how per-client overlay contexts (option A, used at the session level) fix it.
Two invariants to state out loud
- One write path. Every change to the data map goes through
apply(key, newEntry, cause). That method, and only that method, updates the value index and the TTL key set. Client writes, rollback, expiry, restore and later extensions all call it. - Every logged write records its before-image first. Client mutations go through
write(key, entry), which records the before-image in the top layer (once per key per layer) and then callsapply. Expiry callsapplydirectly, because expiry is a physical removal and not a client change that a rollback should undo.
If you say these two sentences early, the interviewer knows you've found the crux of the problem.
3. Class diagram
classDiagram
class KvStore {
-data: Map of String to Entry
-byValue: Map of String to Set of String
-volatileKeys: VolatileKeys
-layers: Stack of Map of String to Entry
-clock: Clock
-expiry: ExpiryStrategy
-lock: ReentrantLock
+get(key) String
+set(key, value, ttl)
+delete(key) bool
+exists(key) bool
+incr(key, by) long
+expire(key, ttl) bool
+persist(key) bool
+ttl(key) long
+count(value) int
+begin()
+rollback()
+commit()
+snapshot() Snapshot
+restore(snapshot)
+activeExpireCycle() int
#live(key) Entry
-write(key, entry)
#apply(key, entry, cause)
}
class Entry {
+value: String
+expiresAt: long
+expired(now) bool
}
class Snapshot {
-entries: Map of String to Entry
+takenAt: long
}
class VolatileKeys {
-keys: List of String
-pos: Map of String to int
+add(key)
+remove(key)
+pick(rng) String
}
class ExpiryTarget {
<<interface>>
+volatileCount() int
+randomVolatileKey(rng) String
+volatileKeys() List
+reapIfExpired(key, now) bool
}
class ExpiryStrategy {
<<interface>>
+run(target, now) int
}
class SamplingExpiry
class FullScan
class LazyOnly
class Clock {
<<interface>>
+nowMillis() long
}
class ManualClock {
+advance(ms)
}
class Command {
<<interface>>
+execute(session) String
}
class Session {
+store: KvStore
+snapshots: Map of String to Snapshot
}
class CommandParser {
+parse(line) Command
+run(session, line) String
}
KvStore ..|> ExpiryTarget
KvStore *-- "many" Entry
KvStore *-- VolatileKeys
KvStore o-- Clock
KvStore o-- ExpiryStrategy
KvStore ..> Snapshot : creates and restores
Snapshot o-- "many" Entry
ExpiryStrategy <|.. SamplingExpiry
ExpiryStrategy <|.. FullScan
ExpiryStrategy <|.. LazyOnly
ExpiryStrategy ..> ExpiryTarget : uses
Clock <|.. ManualClock
Session o-- KvStore
Session o-- "many" Snapshot
CommandParser ..> Command : builds
Command ..> Session : executes against
Command <|.. Get
Command <|.. SetCmd
Command <|.. Incr
Command <|.. Begin
Command <|.. Rollback
Command <|.. Commit
Command <|.. TakeSnapshot
Some things to notice:
- The strategy doesn't see the store.
ExpiryStrategydepends onExpiryTarget, a four-method interface, and not onKvStore. A strategy can sample keys and reap them, but it can't callsetor open a transaction. That narrow interface is what makes a new strategy safe to write. Python skips the formal interface (duck typing) but keeps the same four methods. SnapshotholdsEntryobjects but exposes none of them. Because entries are immutable, the snapshot can share them with the live map instead of deep-copying, and still be safe.liveandapplyare protected, not private. They're the two hooks the extensions in section 8 override:livefor "a key was used" andapplyfor "a key changed".writestays private, because nobody should be able to skip the undo log.- The diagram shows six command classes. The code has fifteen. They're all the same shape.
4. Key flows
A read that finds an expired key (lazy expiry)
The first half of TTL. Nobody runs a timer per key. Instead, every read checks the deadline, and an expired entry is removed on the spot, as if it had never been there.
sequenceDiagram
participant D as Driver
participant P as CommandParser
participant G as Get command
participant S as KvStore
participant C as Clock
D->>P: parse("GET session")
P-->>D: Get("session")
D->>G: execute(session)
G->>S: get("session")
S->>S: lock
S->>C: nowMillis()
C-->>S: 5000
S->>S: entry = data.get("session")
alt expiresAt is at or before now
S->>S: apply("session", null, EXPIRE)
Note over S: removes from data, value index and volatile set
S-->>G: null
G-->>D: "(nil)"
else still live
S-->>G: entry.value
G-->>D: value
end
S->>S: unlock
Two details matter. First, the comparison is now >= expiresAt: a key set with a 5,000 ms TTL at time 0 is gone at exactly 5,000. Pick a boundary and test it. Second, the removal goes through apply with cause EXPIRE, not through write. Expiry isn't recorded in the transaction layer, so a rollback can't undo it. If the transaction had changed this key earlier, its before-image is still in the layer, and rollback checks that image's own deadline before restoring it (see the walkthrough in section 6).
An active expiry cycle
Lazy expiry alone leaks: a key that's written once with a TTL and never read stays in memory forever. Active expiry runs on a timer and samples keys that have a TTL.
sequenceDiagram
participant T as Scheduler
participant S as KvStore
participant E as SamplingExpiry
T->>S: activeExpireCycle()
S->>S: lock
S->>E: run(store, now)
loop up to 16 rounds
loop up to 20 samples
E->>S: randomVolatileKey(rng)
S-->>E: key
E->>S: reapIfExpired(key, now)
S-->>E: true or false
end
alt more than a quarter of the sample was expired
Note over E: probably many more, go again
else few expired
Note over E: stop, the rest can wait for the next tick
end
end
E-->>S: reaped count
S->>S: unlock
S-->>T: reaped count
The arithmetic behind this: if fewer than 25% of a random sample is expired, then with high probability fewer than about 25% of all TTL keys are expired, so the memory wasted is bounded relative to the live set. If more than 25% is expired, the cycle goes again, up to a cap, so a cycle can never hold the lock for long. The numbers 20 and 25% come from Redis's documented expiry algorithm. They're tuning knobs, and the strategy takes them as constructor arguments.
Nested transactions
This is the flow interviewers probe hardest. Follow key a through two levels.
sequenceDiagram
participant D as Driver
participant S as KvStore
participant L1 as Layer 1
participant L2 as Layer 2
Note over S: a = 10 and b = 5
D->>S: BEGIN
S->>L1: push empty layer
D->>S: SET a 20
S->>L1: a not recorded yet, so record before-image a = 10
S->>S: apply a = 20
D->>S: BEGIN
S->>L2: push empty layer
D->>S: SET a 30
S->>L2: record before-image a = 20
S->>S: apply a = 30
D->>S: SET a 40
Note over L2: a already recorded, nothing to log
S->>S: apply a = 40
D->>S: ROLLBACK
S->>L2: pop layer 2
S->>S: apply a = 20 from layer 2 image
Note over S: a = 20, layer 1 untouched
D->>S: BEGIN
S->>L2: push a new empty layer 2
D->>S: DEL b
S->>L2: record before-image b = 5
S->>S: apply b deleted
D->>S: COMMIT
S->>L2: pop layer 2
S->>L1: b not in layer 1, so copy image b = 5 into layer 1
D->>S: ROLLBACK
S->>L1: pop layer 1
S->>S: apply a = 10 and b = 5
Note over S: back to the state before the first BEGIN
Three rules make this work:
- A layer records a key's before-image once, at the first change. Later changes in the same layer don't touch the log, because the oldest image is the only one rollback needs. That's why
SET a 40logs nothing. - Rollback pops exactly one layer and writes its images back through
apply. The layer below is untouched. - Commit merges down, and the parent's image wins on conflict. If both layers changed
a, the parent's image (a = 10) is older, and it's the one an outer rollback must restore. The child's image (a = 20) is discarded. If only the child changedb, the child's image is copied down, so the parent now knows how to undobtoo.
At depth one, commit pops the layer and throws it away. The changes are already in the map, which is the point of write-through.
The transaction context as a state machine
stateDiagram-v2
[*] --> Autocommit
Autocommit --> InTransaction : BEGIN, depth becomes 1
InTransaction --> InTransaction : BEGIN, depth plus 1
InTransaction --> InTransaction : COMMIT or ROLLBACK at depth above 1
InTransaction --> Autocommit : COMMIT at depth 1, changes kept
InTransaction --> Autocommit : ROLLBACK at depth 1, changes undone
Autocommit --> Autocommit : COMMIT or ROLLBACK, reply ERR no transaction
Autocommit --> Autocommit : RESTORE allowed
InTransaction --> InTransaction : RESTORE rejected
InTransaction --> InTransaction : SNAPSHOT copies committed state only
Autocommit means every write is final the moment it happens. InTransaction carries a depth counter, which is simply the size of the layer stack. Two transitions are worth defending in the interview:
COMMITorROLLBACKwith no transaction is an error reply, not a crash and not a silent no-op. A silent no-op hides client bugs. The driver turns the exception intoERR no transaction.RESTOREis rejected inside a transaction. What would a rollback after a restore mean? The layers hold before-images of a world that the restore just replaced. You could log every key the restore touches into the top layer, but that turns a bulk operation into a giant transaction for little benefit. Rejecting it is simpler and easy to explain.
Lifecycle of a key
stateDiagram-v2
[*] --> Absent
Absent --> Live : SET or INCR
Live --> Live : SET, INCR, EXPIRE, PERSIST
Live --> Absent : DEL
Live --> ExpiredInMemory : deadline passes
ExpiredInMemory --> Absent : a read finds it, or active expiry samples it
ExpiredInMemory --> Live : SET overwrites it
Live --> Absent : ROLLBACK of the layer that created it
Absent --> Live : ROLLBACK of the layer that deleted it
ExpiredInMemory is the state that catches people. The entry is still in the map and still in the value index, but no read may ever return it. Every read path, including count, must treat it as absent. In this design, every read path goes through live or reapIfExpired, which turns ExpiredInMemory into Absent on the spot.
5. Patterns used, and the alternatives rejected
Command: one object per request
Each line of text becomes an object: Get("a"), SetCmd("a", "10", null), Begin(). The parser builds it, and the driver calls execute(session) on it. This is the Command pattern, and in this problem it pays off in four concrete ways.
- Parsing and executing are separate. The parser checks the command name and arity, and converts
EX 5into milliseconds. It can be tested without a store. The store never sees a string token. - Adding a command is one new class and one table row.
PERSISTwas added late and touched nothing else. That's the Open/Closed Principle applied for real, not as a slogan. - A command is data. It can be logged, sent to a replica, queued (Redis's
MULTIqueues commands and runs them all atEXEC), or written to an append-only file and replayed on startup. All of those are one-line additions once requests are objects. - It's where the undo log comes from. The classic Command pattern gives each command an
undo()method. The next subsection explains why this design keeps the idea but moves it one level down.
The undo log: commands that undo themselves, or before-images?
The textbook way to support rollback with Command is to give every mutating command an inverse. Set remembers the old value, Incr(5) undoes with Incr(-5), and Del remembers what it deleted. A transaction is a list of executed commands, and rollback runs their undo() in reverse order.
It works, and it's a reasonable first answer. This design rejects it for three reasons:
- Every command has to get its inverse right, forever.
INCRon a missing key creates it, so the inverse is a delete, not a decrement.SETon a key with a TTL clears the TTL, so the inverse must restore the TTL too.EXPIRE 0deletes. Each new command is a new chance to write a subtly wrongundo(). - The log grows with operations, not keys. A loop that increments one counter a million times inside a transaction logs a million inverses. Before-images log one entry per key per layer, however many times it's written.
- Inverses don't compose with expiry. If the key expired between the command and the rollback, replaying "decrement by 5" on a missing key creates
-5. Restoring a before-image, and then checking that image's own deadline, gets it right.
So the undo log works at the level of the primitive write: write(key, entry) records key → previous entry once per layer. Each log record is in effect a tiny restore command, "put this entry back for this key", so the Command idea survives. It's just applied to the one operation that all the others are built from. Commands stay simple (execute only), and correctness lives in one twelve-line method.
Strategy: how active expiry finds expired keys
ExpiryStrategy has one method, run(target, now), and three implementations:
| Strategy | Work per cycle | Leaves garbage? | Use it for |
|---|---|---|---|
SamplingExpiry | Bounded: at most rounds × sample size checks | Briefly, a bounded fraction | Production default |
FullScan | O(keys with a TTL) | No | Small stores, or a nightly cleanup |
LazyOnly | Zero | Yes, until read | Tests that want full control over removal |
The Strategy earns its place because the requirements genuinely contain more than one reasonable algorithm, and the right one depends on the deployment. A test wants determinism, a small embedded store wants exactness, and a big store wants bounded pauses. The store's code doesn't change between them.
Lazy expiry is not a strategy. It's always on, because returning an expired value would be a correctness bug, and no configuration should allow it. Only the background clean-up varies. Drawing that line clearly is part of the answer.
Rejected: a min-heap (priority queue) ordered by deadline. It finds every expired key exactly and in order, but each set with a TTL costs O(log n), and changing or removing a TTL needs either an indexed heap or lazy deletion with stale heap entries. It's a perfectly good design and it could be a fourth strategy. Mention it as the "precise" alternative. A timing wheel is the other precise option, with O(1) insert and coarse buckets, which suits millions of short TTLs.
Rejected: one timer per key. setTimeout per key in Node, or a scheduled task per key in Java, gives exact expiry. But it creates one timer object per key, it needs cancelling on every overwrite, and it pushes deletions onto a timer thread that must take the store lock at unpredictable moments. It doesn't scale past a few thousand keys.
Memento: snapshots that nobody can read
snapshot() returns a Snapshot. A caller can hold it, pass it around, and give it back to restore, but it can't look inside. That's Memento: the store (the originator) packs its own state, and the session (the caretaker) stores it by name without understanding it.
Why bother with opacity? Because the snapshot's internals (the entry map, absolute deadlines) are implementation details. If callers could read them, they would. Then changing expiresAt from absolute to relative time, or switching to a persistent data structure, would break them. Each language enforces opacity differently:
- Java: the
entries()accessor is package-private, so only classes in the store's package can call it. - Python: the field is
_entries, which is a convention, not enforcement. Say so honestly in the interview. - TypeScript: the field is an ECMAScript
#privatefield, which really is invisible outside the class. A staticentriesOfaccessor onSnapshotitself lets the store read it.
Two design points make the snapshot cheap and correct:
- Shallow copy is enough because
Entryis immutable. The copy of the map is O(n) references, and no values are duplicated. A mutable entry would force a deep copy, and forgetting that is the classic Memento bug: the "snapshot" changes when the live data does. - Snapshots hold committed state only. With write-through, the live map contains uncommitted writes.
snapshot()copies the map and then, for each open layer from innermost to outermost, writes that layer's before-images into the copy. The outermost layer goes last, so its images, which are the oldest, win. The result is exactly the state an outer rollback would produce.
Rejected: snapshot as a command log replay. You could record every command since startup and restore by replaying up to a point. It takes no memory up front, but restore costs O(history), and expiry makes replay time-dependent. That's how persistence logs (Redis's AOF) work, and it's a fine extension. It's not a fast in-memory restore.
Rejected: copy-on-write persistent maps. A hash array mapped trie (as in Clojure or Scala's immutable maps) makes snapshot() O(1) by sharing structure. That's excellent if snapshots are frequent and the store is large. It's also a lot of code to write in an interview, and it makes every write slower by a constant factor. Mention it as the scaling answer.
Other choices, briefly
- Injectable clock (dependency injection). Without it, testing TTL means
sleep, which makes tests slow and flaky. The clock is a constructor parameter, as in the rate limiter and LRU cache designs. KvStoreas a facade. It hides four structures (data, value index, volatile set, layers) behind one API. Splitting them into separate public services would let a caller update one without the others, which is exactly the bug to avoid.- Rejected: State pattern for the transaction context. The state diagram above has two states, and the only behaviour that differs is "is there a layer to log into?". A
layers.peek() != nullcheck is clearer than two state classes. Use State when the states differ in many methods. Here they differ in oneif. - Rejected: a Singleton store. It makes tests share state and rules out per-test clocks. Create the store in
mainand pass it in. - Rejected: an
Interpreterfor the command language. The grammar is "a word, then words". A table from command name to (arities, builder) is enough. If the interviewer adds quoted strings or nested expressions, a tokenizer comes first, and a real grammar only after that.
6. Complete implementation
All three listings are complete and runnable, and each one is a single file. Each ends with a main that replays the same command transcript and asserts every reply. It then fills the store with 1,000 short-lived keys, checks that sampled active expiry clears them in a few bounded cycles without touching anything else, runs the background sweeper once on a real timer with a manual clock (Java and TypeScript), and (in Java and Python) checks that eight threads incrementing one counter lose no updates.
To run them: javac -d out KvDemo.java && java -cp out KvDemo, python kv.py, and npx tsx kv.ts. The TypeScript file type-checks under tsc --strict.
// file: KvDemo.java
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.Function;
import java.util.function.Supplier;
/** Source of "now" in milliseconds. Injected so tests can move time by hand. */
interface Clock {
long nowMillis();
Clock SYSTEM = () -> System.nanoTime() / 1_000_000; // monotonic: NTP can't un-expire a key
}
final class ManualClock implements Clock {
private final AtomicLong now = new AtomicLong();
public long nowMillis() { return now.get(); }
void advance(long millis) { now.addAndGet(millis); }
}
/** A client error: wrong type, bad argument, no open transaction. */
class KvException extends RuntimeException {
KvException(String message) { super(message); }
}
/** Immutable. A write replaces the entry, so an undo log can keep the old one safely. */
record Entry(String value, long expiresAt) {
static final long NO_TTL = Long.MAX_VALUE;
Entry(String value) { this(value, NO_TTL); }
boolean hasTtl() { return expiresAt != NO_TTL; }
boolean expired(long now) { return now >= expiresAt; }
}
enum Cause { WRITE, EXPIRE, UNDO, RESTORE, EVICT }
/** Memento: an opaque copy of committed state. Only KvStore reads the entries. */
final class Snapshot {
private final Map<String, Entry> entries;
final long takenAt;
Snapshot(Map<String, Entry> entries, long takenAt) { this.entries = entries; this.takenAt = takenAt; }
Map<String, Entry> entries() { return entries; } // package-private: callers outside can't see it
int size() { return entries.size(); }
}
/** Keys that carry a TTL, with O(1) add, remove and uniform random pick. */
final class VolatileKeys {
private final ArrayList<String> keys = new ArrayList<>();
private final HashMap<String, Integer> pos = new HashMap<>();
void add(String key) {
if (pos.putIfAbsent(key, keys.size()) == null) keys.add(key);
}
void remove(String key) {
Integer i = pos.remove(key);
if (i == null) return;
String last = keys.remove(keys.size() - 1);
if (i < keys.size()) { keys.set(i, last); pos.put(last, i); } // move the last key into the hole
}
String pick(Random rng) { return keys.get(rng.nextInt(keys.size())); }
List<String> keys() { return new ArrayList<>(keys); }
int size() { return keys.size(); }
boolean contains(String key) { return pos.containsKey(key); }
}
/** What an expiry strategy may do to the store. Called with the store's lock held. */
interface ExpiryTarget {
int volatileCount();
String randomVolatileKey(Random rng);
List<String> volatileKeys();
boolean reapIfExpired(String key, long now);
}
/** Strategy: how active expiry finds expired keys. Returns how many it removed. */
interface ExpiryStrategy {
int run(ExpiryTarget store, long now);
}
/** No active expiry: keys go only when read. Fine for tests, leaks in production. */
final class LazyOnly implements ExpiryStrategy {
public int run(ExpiryTarget store, long now) { return 0; }
}
/** Check every key with a TTL. Exact, but O(volatile keys) while holding the lock. */
final class FullScan implements ExpiryStrategy {
public int run(ExpiryTarget store, long now) {
int n = 0;
for (String k : store.volatileKeys()) if (store.reapIfExpired(k, now)) n++;
return n;
}
}
/** Redis-style: sample keys with a TTL, reap the expired ones, repeat while many were expired. */
final class SamplingExpiry implements ExpiryStrategy {
private final int sampleSize, maxRounds;
private final double repeatAbove;
private final Random rng;
SamplingExpiry(int sampleSize, double repeatAbove, int maxRounds, Random rng) {
this.sampleSize = sampleSize; this.repeatAbove = repeatAbove; this.maxRounds = maxRounds; this.rng = rng;
}
SamplingExpiry(Random rng) { this(20, 0.25, 16, rng); }
public int run(ExpiryTarget store, long now) {
int reaped = 0;
for (int round = 0; round < maxRounds; round++) {
int sampled = 0, hits = 0;
while (sampled < sampleSize && store.volatileCount() > 0) {
sampled++;
if (store.reapIfExpired(store.randomVolatileKey(rng), now)) hits++;
}
reaped += hits;
if (sampled == 0 || hits <= sampled * repeatAbove) break;
}
return reaped;
}
}
class KvStore implements ExpiryTarget {
protected final ReentrantLock lock = new ReentrantLock(); // one lock for everything: see the concurrency section
private final Clock clock;
private final ExpiryStrategy expiry;
private final HashMap<String, Entry> data = new HashMap<>();
private final HashMap<String, Set<String>> byValue = new HashMap<>();
private final VolatileKeys volatileKeys = new VolatileKeys();
/** One map per open transaction: key -> entry before this layer first touched it (null = absent). */
private final ArrayDeque<LinkedHashMap<String, Entry>> layers = new ArrayDeque<>();
private long expiredTotal;
KvStore(Clock clock, ExpiryStrategy expiry) { this.clock = clock; this.expiry = expiry; }
protected final <T> T locked(Supplier<T> body) {
lock.lock();
try { return body.get(); } finally { lock.unlock(); }
}
protected final long now() { return clock.nowMillis(); }
// ----- reads -----
String get(String key) { return locked(() -> { Entry e = live(key); return e == null ? null : e.value(); }); }
boolean exists(String key) { return locked(() -> live(key) != null); }
/** Milliseconds left, -1 if the key has no TTL, -2 if it doesn't exist. */
long ttlMillis(String key) {
return locked(() -> {
Entry e = live(key);
if (e == null) return -2L;
return e.hasTtl() ? e.expiresAt() - now() : -1L;
});
}
/** Live keys holding exactly this value. O(keys with that value). */
int count(String value) {
return locked(() -> {
long now = now();
for (String k : List.copyOf(byValue.getOrDefault(value, Set.of()))) reapIfExpired(k, now);
return byValue.getOrDefault(value, Set.of()).size();
});
}
/** Entries in memory, including expired ones nobody has touched yet. */
int size() { return locked(data::size); }
long expiredTotal() { return locked(() -> expiredTotal); }
// ----- writes -----
/** Plain SET clears any TTL, as in Redis. */
void set(String key, String value) { locked(() -> { write(key, new Entry(value)); return null; }); }
void set(String key, String value, long ttlMillis) {
if (ttlMillis <= 0) throw new KvException("invalid expire time");
locked(() -> { write(key, new Entry(value, now() + ttlMillis)); return null; });
}
boolean delete(String key) {
return locked(() -> {
if (live(key) == null) return false;
write(key, null);
return true;
});
}
/** Missing key counts as 0. Keeps the key's TTL. */
long incr(String key, long by) {
return locked(() -> {
Entry e = live(key);
long current = e == null ? 0 : parseLong(e.value());
long result;
try { result = Math.addExact(current, by); }
catch (ArithmeticException ex) { throw new KvException("increment or decrement would overflow"); }
write(key, new Entry(Long.toString(result), e == null ? Entry.NO_TTL : e.expiresAt()));
return result;
});
}
/** A TTL of zero or less deletes the key, as in Redis. */
boolean expire(String key, long ttlMillis) {
return locked(() -> {
Entry e = live(key);
if (e == null) return false;
write(key, ttlMillis <= 0 ? null : new Entry(e.value(), now() + ttlMillis));
return true;
});
}
boolean persist(String key) {
return locked(() -> {
Entry e = live(key);
if (e == null || !e.hasTtl()) return false;
write(key, new Entry(e.value()));
return true;
});
}
// ----- transactions -----
void begin() { locked(() -> { layers.push(new LinkedHashMap<>()); return null; }); }
/** Undo only the innermost transaction. */
void rollback() {
locked(() -> {
if (layers.isEmpty()) throw new KvException("no transaction");
long now = now();
for (Map.Entry<String, Entry> undo : layers.pop().entrySet()) {
Entry before = undo.getValue();
apply(undo.getKey(), before != null && !before.expired(now) ? before : null, Cause.UNDO);
}
return null;
});
}
/** Close the innermost transaction. Its changes now belong to the parent, if any. */
void commit() {
locked(() -> {
if (layers.isEmpty()) throw new KvException("no transaction");
LinkedHashMap<String, Entry> top = layers.pop();
LinkedHashMap<String, Entry> parent = layers.peek();
if (parent == null) return null;
// The parent's older image wins. Not putIfAbsent: it treats a null ("was absent") image as missing.
top.forEach((k, before) -> { if (!parent.containsKey(k)) parent.put(k, before); });
return null;
});
}
int depth() { return locked(layers::size); }
// ----- snapshots (Memento) -----
/** Committed state only: open transactions are peeled off the copy. */
Snapshot snapshot() {
return locked(() -> {
HashMap<String, Entry> committed = new HashMap<>(data); // entries are immutable
for (LinkedHashMap<String, Entry> layer : layers) { // innermost first, outermost wins
layer.forEach((k, before) -> {
if (before == null) committed.remove(k); else committed.put(k, before);
});
}
return new Snapshot(committed, now());
});
}
void restore(Snapshot snap) {
locked(() -> {
if (!layers.isEmpty()) throw new KvException("cannot restore inside a transaction");
long now = now();
for (String k : List.copyOf(data.keySet())) apply(k, null, Cause.RESTORE);
snap.entries().forEach((k, e) -> { if (!e.expired(now)) apply(k, e, Cause.RESTORE); });
return null;
});
}
// ----- active expiry -----
int activeExpireCycle() { return locked(() -> expiry.run(this, now())); }
/** Run a cycle every period on the given scheduler. Cancel the returned future to stop. */
ScheduledFuture<?> startActiveExpiry(ScheduledExecutorService scheduler, long periodMillis) {
return scheduler.scheduleAtFixedRate(this::activeExpireCycle, periodMillis, periodMillis, TimeUnit.MILLISECONDS);
}
public int volatileCount() { return volatileKeys.size(); }
public String randomVolatileKey(Random rng) { return volatileKeys.pick(rng); }
public List<String> volatileKeys() { return volatileKeys.keys(); }
public boolean reapIfExpired(String key, long now) {
Entry e = data.get(key);
if (e == null || !e.expired(now)) return false;
apply(key, null, Cause.EXPIRE);
expiredTotal++;
return true;
}
// ----- internals -----
/** Lazy expiry: an expired entry is removed the moment someone looks at it. */
protected Entry live(String key) {
return reapIfExpired(key, now()) ? null : data.get(key);
}
/** Every client mutation goes through here, so the undo log can't be bypassed. */
private void write(String key, Entry entry) {
LinkedHashMap<String, Entry> top = layers.peek();
if (top != null && !top.containsKey(key)) top.put(key, data.get(key));
apply(key, entry, Cause.WRITE);
}
/** The only place that touches data, so the indexes can't drift. Lock must be held. */
protected void apply(String key, Entry entry, Cause cause) {
Entry old = data.remove(key);
if (old != null) {
Set<String> holders = byValue.get(old.value());
holders.remove(key);
if (holders.isEmpty()) byValue.remove(old.value());
volatileKeys.remove(key);
}
if (entry != null) {
data.put(key, entry);
byValue.computeIfAbsent(entry.value(), v -> new HashSet<>()).add(key);
if (entry.hasTtl()) volatileKeys.add(key);
}
}
void checkInvariants() {
locked(() -> {
HashMap<String, Set<String>> rebuilt = new HashMap<>();
data.forEach((k, e) -> rebuilt.computeIfAbsent(e.value(), v -> new HashSet<>()).add(k));
if (!rebuilt.equals(byValue)) throw new AssertionError("value index drifted");
for (String k : data.keySet()) {
if (data.get(k).hasTtl() != volatileKeys.contains(k)) throw new AssertionError("volatile set drifted");
}
if (volatileKeys.size() > data.size()) throw new AssertionError("volatile set has ghosts");
return null;
});
}
static long parseLong(String text) {
if (!text.matches("-?[0-9]+")) throw new KvException("value is not an integer or out of range");
try { return Long.parseLong(text); }
catch (NumberFormatException ex) { throw new KvException("value is not an integer or out of range"); }
}
}
// ---------- commands (Command pattern) ----------
/** One client's connection: the store plus the snapshots this client has named. */
final class Session {
final KvStore store;
final Map<String, Snapshot> snapshots = new HashMap<>();
Session(KvStore store) { this.store = store; }
}
interface Command {
String execute(Session s);
}
record Get(String key) implements Command {
public String execute(Session s) { String v = s.store.get(key); return v == null ? "(nil)" : v; }
}
record SetCmd(String key, String value, long ttlMillis) implements Command {
public String execute(Session s) {
if (ttlMillis == 0) s.store.set(key, value); else s.store.set(key, value, ttlMillis);
return "OK";
}
}
record Del(String key) implements Command {
public String execute(Session s) { return s.store.delete(key) ? "1" : "0"; }
}
record Exists(String key) implements Command {
public String execute(Session s) { return s.store.exists(key) ? "1" : "0"; }
}
record Incr(String key, long by) implements Command {
public String execute(Session s) { return Long.toString(s.store.incr(key, by)); }
}
record Expire(String key, long seconds) implements Command {
public String execute(Session s) { return s.store.expire(key, seconds * 1000) ? "1" : "0"; }
}
record Persist(String key) implements Command {
public String execute(Session s) { return s.store.persist(key) ? "1" : "0"; }
}
record Ttl(String key) implements Command {
public String execute(Session s) {
long ms = s.store.ttlMillis(key);
return Long.toString(ms < 0 ? ms : (ms + 999) / 1000); // whole seconds, rounded up
}
}
record Count(String value) implements Command {
public String execute(Session s) { return Integer.toString(s.store.count(value)); }
}
record Begin() implements Command {
public String execute(Session s) { s.store.begin(); return "OK"; }
}
record Rollback() implements Command {
public String execute(Session s) { s.store.rollback(); return "OK"; }
}
record Commit() implements Command {
public String execute(Session s) { s.store.commit(); return "OK"; }
}
record TakeSnapshot(String name) implements Command {
public String execute(Session s) { s.snapshots.put(name, s.store.snapshot()); return "OK"; }
}
record RestoreSnapshot(String name) implements Command {
public String execute(Session s) {
Snapshot snap = s.snapshots.get(name);
if (snap == null) throw new KvException("no such snapshot '" + name + "'");
s.store.restore(snap);
return "OK";
}
}
final class CommandParser {
private record Spec(Set<Integer> arities, Function<String[], Command> build) {}
private static final Map<String, Spec> COMMANDS = Map.ofEntries(
Map.entry("GET", new Spec(Set.of(1), a -> new Get(a[0]))),
Map.entry("SET", new Spec(Set.of(2, 4), CommandParser::parseSet)),
Map.entry("DEL", new Spec(Set.of(1), a -> new Del(a[0]))),
Map.entry("EXISTS", new Spec(Set.of(1), a -> new Exists(a[0]))),
Map.entry("INCR", new Spec(Set.of(1), a -> new Incr(a[0], 1))),
Map.entry("INCRBY", new Spec(Set.of(2), a -> new Incr(a[0], KvStore.parseLong(a[1])))),
Map.entry("EXPIRE", new Spec(Set.of(2), a -> new Expire(a[0], KvStore.parseLong(a[1])))),
Map.entry("PERSIST", new Spec(Set.of(1), a -> new Persist(a[0]))),
Map.entry("TTL", new Spec(Set.of(1), a -> new Ttl(a[0]))),
Map.entry("COUNT", new Spec(Set.of(1), a -> new Count(a[0]))),
Map.entry("BEGIN", new Spec(Set.of(0), a -> new Begin())),
Map.entry("ROLLBACK", new Spec(Set.of(0), a -> new Rollback())),
Map.entry("COMMIT", new Spec(Set.of(0), a -> new Commit())),
Map.entry("SNAPSHOT", new Spec(Set.of(1), a -> new TakeSnapshot(a[0]))),
Map.entry("RESTORE", new Spec(Set.of(1), a -> new RestoreSnapshot(a[0]))));
private static Command parseSet(String[] a) {
if (a.length == 2) return new SetCmd(a[0], a[1], 0);
if (!a[2].equalsIgnoreCase("EX")) throw new KvException("syntax error");
long seconds = KvStore.parseLong(a[3]);
if (seconds <= 0 || seconds > Long.MAX_VALUE / 1000) throw new KvException("invalid expire time");
return new SetCmd(a[0], a[1], seconds * 1000);
}
static Command parse(String line) {
String trimmed = line.strip();
if (trimmed.isEmpty()) throw new KvException("empty command");
String[] parts = trimmed.split("\\s+");
String name = parts[0].toUpperCase(Locale.ROOT);
Spec spec = COMMANDS.get(name);
if (spec == null) throw new KvException("unknown command '" + parts[0] + "'");
String[] args = Arrays.copyOfRange(parts, 1, parts.length);
if (!spec.arities().contains(args.length)) {
throw new KvException("wrong number of arguments for '" + name.toLowerCase(Locale.ROOT) + "'");
}
return spec.build().apply(args);
}
/** The driver: one line in, one reply out. Errors become replies, never crashes. */
static String run(Session session, String line) {
try { return parse(line).execute(session); }
catch (KvException e) { return "ERR " + e.getMessage(); }
}
}
public class KvDemo {
static void check(Session s, String line, String expected) {
String got = CommandParser.run(s, line);
System.out.printf("> %-22s %s%n", line, got);
if (!got.equals(expected)) throw new AssertionError(line + ": expected " + expected + ", got " + got);
}
public static void main(String[] args) throws Exception {
ManualClock clock = new ManualClock();
KvStore store = new KvStore(clock, new SamplingExpiry(new Random(7)));
Session s = new Session(store);
check(s, "SET a 10", "OK");
check(s, "INCR a", "11");
check(s, "COUNT 11", "1");
check(s, "BEGIN", "OK");
check(s, "SET b 11", "OK");
check(s, "COUNT 11", "2");
check(s, "BEGIN", "OK");
check(s, "DEL a", "1");
check(s, "COUNT 11", "1");
check(s, "ROLLBACK", "OK"); // only the inner layer is undone
check(s, "GET a", "11");
check(s, "SNAPSHOT s1", "OK"); // taken inside a transaction: b is not in it
check(s, "COMMIT", "OK");
check(s, "GET b", "11");
check(s, "ROLLBACK", "ERR no transaction");
check(s, "SET a 99", "OK");
check(s, "RESTORE s1", "OK");
check(s, "GET a", "11");
check(s, "GET b", "(nil)");
check(s, "SET s hello EX 5", "OK");
check(s, "TTL s", "5");
clock.advance(4_001);
check(s, "TTL s", "1");
clock.advance(999);
check(s, "GET s", "(nil)"); // lazy expiry, exactly at the deadline
check(s, "SET w abc", "OK");
check(s, "INCR w", "ERR value is not an integer or out of range");
check(s, "SET x 1 EX 0", "ERR invalid expire time");
check(s, "GET", "ERR wrong number of arguments for 'get'");
check(s, "FLY a", "ERR unknown command 'FLY'");
for (int i = 0; i < 1_000; i++) store.set("tmp:" + i, "t", 100);
clock.advance(100);
int cycles = 0;
while (store.volatileCount() > 0) {
int reaped = store.activeExpireCycle();
if (reaped <= 0 || reaped > 16 * 20) throw new AssertionError("cycle reaped " + reaped);
cycles++;
}
if (!"11".equals(store.get("a")) || store.count("t") != 0) throw new AssertionError("expiry hit live keys");
store.checkInvariants();
System.out.println("active expiry cleared 1000 keys in " + cycles + " cycles");
// The scheduled sweeper, driven by a real thread but a manual clock.
ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor();
store.set("soon", "x", 10);
ScheduledFuture<?> sweeper = store.startActiveExpiry(scheduler, 5);
clock.advance(10);
long deadline = System.nanoTime() + TimeUnit.SECONDS.toNanos(2);
while (store.size() != 2 && System.nanoTime() < deadline) Thread.onSpinWait();
sweeper.cancel(false);
scheduler.shutdown();
if (store.size() != 2) throw new AssertionError("sweeper did not run");
KvStore shared = new KvStore(new ManualClock(), new LazyOnly());
ExecutorService pool = Executors.newFixedThreadPool(8);
List<Future<?>> jobs = new ArrayList<>();
for (int t = 0; t < 8; t++) jobs.add(pool.submit(() -> { for (int i = 0; i < 10_000; i++) shared.incr("hits", 1); }));
for (Future<?> f : jobs) f.get();
pool.shutdown();
if (!"80000".equals(shared.get("hits"))) throw new AssertionError("lost updates: " + shared.get("hits"));
System.out.println("KvDemo ok");
}
}
# file: kv.py
"""An in-memory key-value store: TTL, nested transactions, a value index and snapshots."""
from __future__ import annotations
import random
import re
import threading
import time
from dataclasses import dataclass
from enum import Enum
from typing import Callable, Dict, List, Optional, Protocol, Set, Tuple
INT64_MIN, INT64_MAX = -(2**63), 2**63 - 1
_INTEGER = re.compile(r"-?[0-9]+")
class KvError(Exception):
"""A client error: wrong type, bad argument, no open transaction."""
# ---------- time ----------
class Clock(Protocol):
def now_ms(self) -> int: ...
class SystemClock:
def now_ms(self) -> int:
return time.monotonic_ns() // 1_000_000 # monotonic: NTP can't make keys un-expire
class ManualClock:
def __init__(self, start: int = 0) -> None:
self._now = start
def now_ms(self) -> int:
return self._now
def advance(self, ms: int) -> None:
self._now += ms
# ---------- data ----------
@dataclass(frozen=True)
class Entry:
"""Immutable. A write replaces the entry, so an undo log can keep the old one safely."""
value: str
expires_at: Optional[int] = None # absolute ms on the store's clock, None = no TTL
def expired(self, now: int) -> bool:
return self.expires_at is not None and now >= self.expires_at
class Cause(Enum):
WRITE = "write" # a client command
EXPIRE = "expire" # lazy or active expiry removed it
UNDO = "undo" # rollback put the old entry back
RESTORE = "restore" # a snapshot was loaded
EVICT = "evict" # a memory limit pushed it out (extension A)
class Snapshot:
"""Memento: an opaque copy of committed state. Only KvStore reads _entries."""
def __init__(self, entries: Dict[str, Entry], taken_at: int) -> None:
self._entries = entries
self.taken_at = taken_at
def __len__(self) -> int:
return len(self._entries)
class VolatileKeys:
"""Keys that carry a TTL, with O(1) add, remove and uniform random pick."""
def __init__(self) -> None:
self._keys: List[str] = []
self._pos: Dict[str, int] = {}
def add(self, key: str) -> None:
if key not in self._pos:
self._pos[key] = len(self._keys)
self._keys.append(key)
def remove(self, key: str) -> None:
i = self._pos.pop(key, None)
if i is None:
return
last = self._keys.pop()
if i < len(self._keys): # move the last key into the hole
self._keys[i] = last
self._pos[last] = i
def pick(self, rng: random.Random) -> str:
return self._keys[rng.randrange(len(self._keys))]
def keys(self) -> List[str]:
return list(self._keys)
def __len__(self) -> int:
return len(self._keys)
# ---------- expiry strategies ----------
class ExpiryStrategy(Protocol):
def run(self, store: "KvStore", now: int) -> int:
"""Remove some expired keys. Return how many were removed."""
...
class LazyOnly:
"""No active expiry: keys go only when read. Fine for tests, leaks in production."""
def run(self, store: "KvStore", now: int) -> int:
return 0
class FullScan:
"""Check every key with a TTL. Exact, but O(volatile keys) while holding the lock."""
def run(self, store: "KvStore", now: int) -> int:
return sum(store.reap_if_expired(k, now) for k in store.volatile_keys())
class SamplingExpiry:
"""Redis-style: sample keys with a TTL, reap the expired ones, repeat while many were expired."""
def __init__(self, sample_size: int = 20, repeat_above: float = 0.25,
max_rounds: int = 16, rng: Optional[random.Random] = None) -> None:
self.sample_size = sample_size
self.repeat_above = repeat_above
self.max_rounds = max_rounds
self.rng = rng or random.Random()
def run(self, store: "KvStore", now: int) -> int:
reaped = 0
for _ in range(self.max_rounds):
sampled = hits = 0
while sampled < self.sample_size and store.volatile_count() > 0:
sampled += 1
hits += store.reap_if_expired(store.random_volatile_key(self.rng), now)
reaped += hits
if sampled == 0 or hits <= sampled * self.repeat_above:
break
return reaped
# ---------- the store ----------
class KvStore:
def __init__(self, clock: Optional[Clock] = None, expiry: Optional[ExpiryStrategy] = None) -> None:
self._clock: Clock = clock or SystemClock()
self._expiry: ExpiryStrategy = expiry or SamplingExpiry()
self._data: Dict[str, Entry] = {}
self._by_value: Dict[str, Set[str]] = {}
self._volatile = VolatileKeys()
# One dict per open transaction: key -> entry before this layer first touched it.
self._layers: List[Dict[str, Optional[Entry]]] = []
self._lock = threading.RLock() # one lock for everything: see the concurrency section
self.expired_total = 0
# ----- reads -----
def get(self, key: str) -> Optional[str]:
with self._lock:
e = self._live(key)
return None if e is None else e.value
def exists(self, key: str) -> bool:
with self._lock:
return self._live(key) is not None
def ttl_ms(self, key: str) -> int:
"""Milliseconds left, -1 if the key has no TTL, -2 if it doesn't exist."""
with self._lock:
e = self._live(key)
if e is None:
return -2
if e.expires_at is None:
return -1
return e.expires_at - self._clock.now_ms()
def count(self, value: str) -> int:
"""Live keys holding exactly this value. O(keys with that value)."""
with self._lock:
now = self._clock.now_ms()
for k in list(self._by_value.get(value, ())):
self.reap_if_expired(k, now)
return len(self._by_value.get(value, ()))
def size(self) -> int:
"""Entries in memory, including expired ones nobody has touched yet."""
with self._lock:
return len(self._data)
# ----- writes -----
def set(self, key: str, value: str, ttl_ms: Optional[int] = None) -> None:
"""Plain SET clears any TTL, as in Redis."""
if ttl_ms is not None and ttl_ms <= 0:
raise KvError("invalid expire time")
with self._lock:
expires = None if ttl_ms is None else self._clock.now_ms() + ttl_ms
self._write(key, Entry(value, expires))
def delete(self, key: str) -> bool:
with self._lock:
if self._live(key) is None:
return False
self._write(key, None)
return True
def incr(self, key: str, by: int = 1) -> int:
"""Missing key counts as 0. Keeps the key's TTL."""
with self._lock:
e = self._live(key)
current = 0 if e is None else parse_int(e.value)
result = current + by
if not INT64_MIN <= result <= INT64_MAX:
raise KvError("increment or decrement would overflow")
self._write(key, Entry(str(result), None if e is None else e.expires_at))
return result
def expire(self, key: str, ttl_ms: int) -> bool:
"""A TTL of zero or less deletes the key, as in Redis."""
with self._lock:
e = self._live(key)
if e is None:
return False
if ttl_ms <= 0:
self._write(key, None)
else:
self._write(key, Entry(e.value, self._clock.now_ms() + ttl_ms))
return True
def persist(self, key: str) -> bool:
with self._lock:
e = self._live(key)
if e is None or e.expires_at is None:
return False
self._write(key, Entry(e.value, None))
return True
# ----- transactions -----
def begin(self) -> None:
with self._lock:
self._layers.append({})
def rollback(self) -> None:
"""Undo only the innermost transaction."""
with self._lock:
if not self._layers:
raise KvError("no transaction")
layer = self._layers.pop()
now = self._clock.now_ms()
for key, before in layer.items():
keep = before is not None and not before.expired(now)
self._apply(key, before if keep else None, Cause.UNDO)
def commit(self) -> None:
"""Close the innermost transaction. Its changes now belong to the parent, if any."""
with self._lock:
if not self._layers:
raise KvError("no transaction")
top = self._layers.pop()
if self._layers:
parent = self._layers[-1]
for key, before in top.items():
parent.setdefault(key, before) # the parent's older image wins
def depth(self) -> int:
with self._lock:
return len(self._layers)
# ----- snapshots (Memento) -----
def snapshot(self) -> Snapshot:
"""Committed state only: open transactions are peeled off the copy."""
with self._lock:
committed = dict(self._data) # entries are immutable, so a shallow copy is enough
for layer in reversed(self._layers): # innermost first, so the outermost image wins
for key, before in layer.items():
if before is None:
committed.pop(key, None)
else:
committed[key] = before
return Snapshot(committed, self._clock.now_ms())
def restore(self, snap: Snapshot) -> None:
with self._lock:
if self._layers:
raise KvError("cannot restore inside a transaction")
now = self._clock.now_ms()
for key in list(self._data):
self._apply(key, None, Cause.RESTORE)
for key, e in snap._entries.items():
if not e.expired(now):
self._apply(key, e, Cause.RESTORE)
# ----- active expiry -----
def active_expire_cycle(self) -> int:
with self._lock:
return self._expiry.run(self, self._clock.now_ms())
def start_active_expiry(self, interval_s: float = 0.1) -> Callable[[], None]:
"""Run a cycle every interval on a daemon thread. Returns a function that stops it."""
stop = threading.Event()
def loop() -> None:
while not stop.wait(interval_s):
self.active_expire_cycle()
threading.Thread(target=loop, daemon=True).start()
return stop.set
# The four methods strategies use. Called with the lock held.
def volatile_count(self) -> int:
return len(self._volatile)
def random_volatile_key(self, rng: random.Random) -> str:
return self._volatile.pick(rng)
def volatile_keys(self) -> List[str]:
return self._volatile.keys()
def reap_if_expired(self, key: str, now: int) -> bool:
e = self._data.get(key)
if e is None or not e.expired(now):
return False
self._apply(key, None, Cause.EXPIRE)
self.expired_total += 1
return True
# ----- internals -----
def _live(self, key: str) -> Optional[Entry]:
"""Lazy expiry: an expired entry is removed the moment someone looks at it."""
if self.reap_if_expired(key, self._clock.now_ms()):
return None
return self._data.get(key)
def _write(self, key: str, entry: Optional[Entry]) -> None:
"""Every client mutation goes through here, so the undo log can't be bypassed."""
if self._layers:
top = self._layers[-1]
if key not in top:
top[key] = self._data.get(key)
self._apply(key, entry, Cause.WRITE)
def _apply(self, key: str, entry: Optional[Entry], cause: Cause) -> None:
"""The only place that touches _data, so the indexes can't drift."""
old = self._data.pop(key, None)
if old is not None:
holders = self._by_value[old.value]
holders.discard(key)
if not holders:
del self._by_value[old.value]
self._volatile.remove(key)
if entry is not None:
self._data[key] = entry
self._by_value.setdefault(entry.value, set()).add(key)
if entry.expires_at is not None:
self._volatile.add(key)
def check_invariants(self) -> None:
with self._lock:
rebuilt: Dict[str, Set[str]] = {}
for k, e in self._data.items():
rebuilt.setdefault(e.value, set()).add(k)
assert rebuilt == self._by_value, "value index drifted"
ttl_keys = {k for k, e in self._data.items() if e.expires_at is not None}
assert ttl_keys == set(self._volatile.keys()), "volatile set drifted"
def parse_int(text: str) -> int:
if not _INTEGER.fullmatch(text) or not INT64_MIN <= int(text) <= INT64_MAX:
raise KvError("value is not an integer or out of range")
return int(text)
# ---------- commands (Command pattern) ----------
class Session:
"""One client's connection: the store plus the snapshots this client has named."""
def __init__(self, store: KvStore) -> None:
self.store = store
self.snapshots: Dict[str, Snapshot] = {}
class Command(Protocol):
def execute(self, s: Session) -> str: ...
def _flag(b: bool) -> str:
return "1" if b else "0"
@dataclass(frozen=True)
class Get:
key: str
def execute(self, s: Session) -> str:
v = s.store.get(self.key)
return "(nil)" if v is None else v
@dataclass(frozen=True)
class SetCmd:
key: str
value: str
ttl_ms: Optional[int] = None
def execute(self, s: Session) -> str:
s.store.set(self.key, self.value, self.ttl_ms)
return "OK"
@dataclass(frozen=True)
class Del:
key: str
def execute(self, s: Session) -> str:
return _flag(s.store.delete(self.key))
@dataclass(frozen=True)
class Exists:
key: str
def execute(self, s: Session) -> str:
return _flag(s.store.exists(self.key))
@dataclass(frozen=True)
class Incr:
key: str
by: int = 1
def execute(self, s: Session) -> str:
return str(s.store.incr(self.key, self.by))
@dataclass(frozen=True)
class Expire:
key: str
seconds: int
def execute(self, s: Session) -> str:
return _flag(s.store.expire(self.key, self.seconds * 1000))
@dataclass(frozen=True)
class Persist:
key: str
def execute(self, s: Session) -> str:
return _flag(s.store.persist(self.key))
@dataclass(frozen=True)
class Ttl:
key: str
def execute(self, s: Session) -> str:
ms = s.store.ttl_ms(self.key)
return str(ms if ms < 0 else -(-ms // 1000)) # whole seconds, rounded up
@dataclass(frozen=True)
class Count:
value: str
def execute(self, s: Session) -> str:
return str(s.store.count(self.value))
@dataclass(frozen=True)
class Begin:
def execute(self, s: Session) -> str:
s.store.begin()
return "OK"
@dataclass(frozen=True)
class Rollback:
def execute(self, s: Session) -> str:
s.store.rollback()
return "OK"
@dataclass(frozen=True)
class Commit:
def execute(self, s: Session) -> str:
s.store.commit()
return "OK"
@dataclass(frozen=True)
class TakeSnapshot:
name: str
def execute(self, s: Session) -> str:
s.snapshots[self.name] = s.store.snapshot()
return "OK"
@dataclass(frozen=True)
class RestoreSnapshot:
name: str
def execute(self, s: Session) -> str:
snap = s.snapshots.get(self.name)
if snap is None:
raise KvError(f"no such snapshot '{self.name}'")
s.store.restore(snap)
return "OK"
def _parse_set(a: List[str]) -> Command:
if len(a) == 2:
return SetCmd(a[0], a[1])
if a[2].upper() != "EX":
raise KvError("syntax error")
seconds = parse_int(a[3])
if seconds <= 0:
raise KvError("invalid expire time")
return SetCmd(a[0], a[1], seconds * 1000)
_COMMANDS: Dict[str, Tuple[Set[int], Callable[[List[str]], Command]]] = {
"GET": ({1}, lambda a: Get(a[0])),
"SET": ({2, 4}, _parse_set),
"DEL": ({1}, lambda a: Del(a[0])),
"EXISTS": ({1}, lambda a: Exists(a[0])),
"INCR": ({1}, lambda a: Incr(a[0])),
"INCRBY": ({2}, lambda a: Incr(a[0], parse_int(a[1]))),
"EXPIRE": ({2}, lambda a: Expire(a[0], parse_int(a[1]))),
"PERSIST": ({1}, lambda a: Persist(a[0])),
"TTL": ({1}, lambda a: Ttl(a[0])),
"COUNT": ({1}, lambda a: Count(a[0])),
"BEGIN": ({0}, lambda a: Begin()),
"ROLLBACK": ({0}, lambda a: Rollback()),
"COMMIT": ({0}, lambda a: Commit()),
"SNAPSHOT": ({1}, lambda a: TakeSnapshot(a[0])),
"RESTORE": ({1}, lambda a: RestoreSnapshot(a[0])),
}
def parse(line: str) -> Command:
parts = line.split()
if not parts:
raise KvError("empty command")
name, args = parts[0].upper(), parts[1:]
spec = _COMMANDS.get(name)
if spec is None:
raise KvError(f"unknown command '{parts[0]}'")
arities, build = spec
if len(args) not in arities:
raise KvError(f"wrong number of arguments for '{name.lower()}'")
return build(args)
def run(session: Session, line: str) -> str:
"""The driver: one line in, one reply out. Errors become replies, never crashes."""
try:
return parse(line).execute(session)
except KvError as e:
return f"ERR {e}"
# ---------- demo ----------
def demo() -> None:
clock = ManualClock()
store = KvStore(clock, SamplingExpiry(rng=random.Random(7)))
session = Session(store)
def check(line: str, expected: str) -> None:
got = run(session, line)
print(f"> {line:<22} {got}")
assert got == expected, f"{line!r}: expected {expected!r}, got {got!r}"
check("SET a 10", "OK")
check("INCR a", "11")
check("COUNT 11", "1")
check("BEGIN", "OK")
check("SET b 11", "OK")
check("COUNT 11", "2")
check("BEGIN", "OK")
check("DEL a", "1")
check("COUNT 11", "1")
check("ROLLBACK", "OK") # only the inner layer is undone
check("GET a", "11")
check("SNAPSHOT s1", "OK") # taken inside a transaction: b is not in it
check("COMMIT", "OK")
check("GET b", "11")
check("ROLLBACK", "ERR no transaction")
check("SET a 99", "OK")
check("RESTORE s1", "OK")
check("GET a", "11")
check("GET b", "(nil)")
check("SET s hello EX 5", "OK")
check("TTL s", "5")
clock.advance(4_001)
check("TTL s", "1")
clock.advance(999)
check("GET s", "(nil)") # lazy expiry, exactly at the deadline
check("SET w abc", "OK")
check("INCR w", "ERR value is not an integer or out of range")
check("SET x 1 EX 0", "ERR invalid expire time")
check("GET", "ERR wrong number of arguments for 'get'")
check("FLY a", "ERR unknown command 'FLY'")
for i in range(1_000):
store.set(f"tmp:{i}", "t", ttl_ms=100)
clock.advance(100)
cycles = 0
while store.volatile_count() > 0:
reaped = store.active_expire_cycle()
assert 0 < reaped <= 16 * 20
cycles += 1
assert store.get("a") == "11" and store.count("t") == 0
store.check_invariants()
print(f"active expiry cleared 1000 keys in {cycles} cycles")
shared = KvStore(ManualClock())
def hammer() -> None:
for _ in range(2_000):
shared.incr("hits")
threads = [threading.Thread(target=hammer) for _ in range(8)]
for t in threads:
t.start()
for t in threads:
t.join()
assert shared.get("hits") == "16000"
print("kv.py ok")
if __name__ == "__main__":
demo()
// file: kv.ts
// An in-memory key-value store: TTL, nested transactions, a value index and snapshots.
export class KvError extends Error {}
// ---------- time ----------
export interface Clock {
nowMs(): number;
}
export const systemClock: Clock = { nowMs: () => Math.floor(performance.now()) }; // monotonic
export class ManualClock implements Clock {
private now = 0;
nowMs(): number {
return this.now;
}
advance(ms: number): void {
this.now += ms;
}
}
/** Seeded random numbers in [0, 1), so sampling is repeatable in tests. */
export function mulberry32(seed: number): () => number {
let a = seed >>> 0;
return () => {
a = (a + 0x6d2b79f5) >>> 0;
let t = a;
t = Math.imul(t ^ (t >>> 15), t | 1);
t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};
}
// ---------- data ----------
/** Immutable. A write replaces the entry, so an undo log can keep the old one safely. */
export class Entry {
constructor(
readonly value: string,
readonly expiresAt: number | null = null, // absolute ms on the store's clock
) {}
expired(now: number): boolean {
return this.expiresAt !== null && now >= this.expiresAt;
}
}
export type Cause = "write" | "expire" | "undo" | "restore" | "evict";
/** Memento: an opaque copy of committed state. */
export class Snapshot {
readonly #entries: ReadonlyMap<string, Entry>;
constructor(entries: Map<string, Entry>, readonly takenAt: number) {
this.#entries = entries;
}
get size(): number {
return this.#entries.size;
}
/** @internal Only KvStore should call this. */
static entriesOf(s: Snapshot): ReadonlyMap<string, Entry> {
return s.#entries;
}
}
/** Keys that carry a TTL, with O(1) add, remove and uniform random pick. */
class VolatileKeys {
private readonly keys: string[] = [];
private readonly pos = new Map<string, number>();
add(key: string): void {
if (this.pos.has(key)) return;
this.pos.set(key, this.keys.length);
this.keys.push(key);
}
remove(key: string): void {
const i = this.pos.get(key);
if (i === undefined) return;
this.pos.delete(key);
const last = this.keys.pop()!;
if (i < this.keys.length) {
this.keys[i] = last; // move the last key into the hole
this.pos.set(last, i);
}
}
pick(rng: () => number): string {
return this.keys[Math.floor(rng() * this.keys.length)];
}
list(): string[] {
return [...this.keys];
}
has(key: string): boolean {
return this.pos.has(key);
}
get size(): number {
return this.keys.length;
}
}
// ---------- expiry strategies ----------
/** What an expiry strategy may do to the store. */
export interface ExpiryTarget {
volatileCount(): number;
randomVolatileKey(rng: () => number): string;
volatileKeys(): string[];
reapIfExpired(key: string, now: number): boolean;
}
export interface ExpiryStrategy {
/** Remove some expired keys. Return how many were removed. */
run(store: ExpiryTarget, now: number): number;
}
/** No active expiry: keys go only when read. Fine for tests, leaks in production. */
export class LazyOnly implements ExpiryStrategy {
run(): number {
return 0;
}
}
/** Check every key with a TTL. Exact, but O(volatile keys) per cycle. */
export class FullScan implements ExpiryStrategy {
run(store: ExpiryTarget, now: number): number {
return store.volatileKeys().filter((k) => store.reapIfExpired(k, now)).length;
}
}
/** Redis-style: sample keys with a TTL, reap the expired ones, repeat while many were expired. */
export class SamplingExpiry implements ExpiryStrategy {
constructor(
private readonly rng: () => number = Math.random,
private readonly sampleSize = 20,
private readonly repeatAbove = 0.25,
private readonly maxRounds = 16,
) {}
run(store: ExpiryTarget, now: number): number {
let reaped = 0;
for (let round = 0; round < this.maxRounds; round++) {
let sampled = 0;
let hits = 0;
while (sampled < this.sampleSize && store.volatileCount() > 0) {
sampled++;
if (store.reapIfExpired(store.randomVolatileKey(this.rng), now)) hits++;
}
reaped += hits;
if (sampled === 0 || hits <= sampled * this.repeatAbove) break;
}
return reaped;
}
}
// ---------- the store ----------
const INT64_MIN = -(2n ** 63n);
const INT64_MAX = 2n ** 63n - 1n;
export function parseInt64(text: string): bigint {
if (!/^-?[0-9]+$/.test(text)) throw new KvError("value is not an integer or out of range");
const n = BigInt(text);
if (n < INT64_MIN || n > INT64_MAX) throw new KvError("value is not an integer or out of range");
return n;
}
/** Undo layer: key -> entry before this layer first touched it (null = absent). */
type Layer = Map<string, Entry | null>;
// Node runs this on one thread, so no lock is needed: each method finishes before the next starts.
export class KvStore implements ExpiryTarget {
private readonly data = new Map<string, Entry>();
private readonly byValue = new Map<string, Set<string>>();
private readonly volatile = new VolatileKeys();
private readonly layers: Layer[] = [];
expiredTotal = 0;
constructor(
protected readonly clock: Clock = systemClock,
private readonly expiry: ExpiryStrategy = new SamplingExpiry(),
) {}
// ----- reads -----
get(key: string): string | null {
return this.live(key)?.value ?? null;
}
exists(key: string): boolean {
return this.live(key) !== undefined;
}
/** Milliseconds left, -1 if the key has no TTL, -2 if it doesn't exist. */
ttlMs(key: string): number {
const e = this.live(key);
if (e === undefined) return -2;
return e.expiresAt === null ? -1 : e.expiresAt - this.clock.nowMs();
}
/** Live keys holding exactly this value. O(keys with that value). */
count(value: string): number {
const now = this.clock.nowMs();
for (const k of [...(this.byValue.get(value) ?? [])]) this.reapIfExpired(k, now);
return this.byValue.get(value)?.size ?? 0;
}
/** Entries in memory, including expired ones nobody has touched yet. */
get size(): number {
return this.data.size;
}
// ----- writes -----
/** Plain SET clears any TTL, as in Redis. */
set(key: string, value: string, ttlMs?: number): void {
if (ttlMs !== undefined && !(ttlMs > 0)) throw new KvError("invalid expire time");
const expires = ttlMs === undefined ? null : this.clock.nowMs() + ttlMs;
this.write(key, new Entry(value, expires));
}
delete(key: string): boolean {
if (this.live(key) === undefined) return false;
this.write(key, null);
return true;
}
/** Missing key counts as 0. Keeps the key's TTL. */
incr(key: string, by = 1n): bigint {
const e = this.live(key);
const result = (e === undefined ? 0n : parseInt64(e.value)) + by;
if (result < INT64_MIN || result > INT64_MAX) throw new KvError("increment or decrement would overflow");
this.write(key, new Entry(result.toString(), e?.expiresAt ?? null));
return result;
}
/** A TTL of zero or less deletes the key, as in Redis. */
expire(key: string, ttlMs: number): boolean {
const e = this.live(key);
if (e === undefined) return false;
this.write(key, ttlMs <= 0 ? null : new Entry(e.value, this.clock.nowMs() + ttlMs));
return true;
}
persist(key: string): boolean {
const e = this.live(key);
if (e === undefined || e.expiresAt === null) return false;
this.write(key, new Entry(e.value));
return true;
}
// ----- transactions -----
begin(): void {
this.layers.push(new Map());
}
/** Undo only the innermost transaction. */
rollback(): void {
const layer = this.layers.pop();
if (layer === undefined) throw new KvError("no transaction");
const now = this.clock.nowMs();
for (const [key, before] of layer) {
this.apply(key, before !== null && !before.expired(now) ? before : null, "undo");
}
}
/** Close the innermost transaction. Its changes now belong to the parent, if any. */
commit(): void {
const top = this.layers.pop();
if (top === undefined) throw new KvError("no transaction");
const parent = this.layers.at(-1);
if (parent === undefined) return;
for (const [key, before] of top) if (!parent.has(key)) parent.set(key, before); // older image wins
}
get depth(): number {
return this.layers.length;
}
// ----- snapshots (Memento) -----
/** Committed state only: open transactions are peeled off the copy. */
snapshot(): Snapshot {
const committed = new Map(this.data); // entries are immutable, so a shallow copy is enough
for (const layer of [...this.layers].reverse()) {
// innermost first, so the outermost image wins
for (const [key, before] of layer) {
if (before === null) committed.delete(key);
else committed.set(key, before);
}
}
return new Snapshot(committed, this.clock.nowMs());
}
restore(snap: Snapshot): void {
if (this.layers.length > 0) throw new KvError("cannot restore inside a transaction");
const now = this.clock.nowMs();
for (const key of [...this.data.keys()]) this.apply(key, null, "restore");
for (const [key, e] of Snapshot.entriesOf(snap)) if (!e.expired(now)) this.apply(key, e, "restore");
}
// ----- active expiry -----
activeExpireCycle(): number {
return this.expiry.run(this, this.clock.nowMs());
}
/** Run a cycle every interval. Returns a function that stops it. */
startActiveExpiry(intervalMs = 100): () => void {
const handle = setInterval(() => this.activeExpireCycle(), intervalMs);
handle.unref(); // don't keep the process alive just for the sweeper
return () => clearInterval(handle);
}
volatileCount(): number {
return this.volatile.size;
}
randomVolatileKey(rng: () => number): string {
return this.volatile.pick(rng);
}
volatileKeys(): string[] {
return this.volatile.list();
}
reapIfExpired(key: string, now: number): boolean {
const e = this.data.get(key);
if (e === undefined || !e.expired(now)) return false;
this.apply(key, null, "expire");
this.expiredTotal++;
return true;
}
// ----- internals -----
/** Lazy expiry: an expired entry is removed the moment someone looks at it. */
protected live(key: string): Entry | undefined {
return this.reapIfExpired(key, this.clock.nowMs()) ? undefined : this.data.get(key);
}
/** Every client mutation goes through here, so the undo log can't be bypassed. */
private write(key: string, entry: Entry | null): void {
const top = this.layers.at(-1);
if (top !== undefined && !top.has(key)) top.set(key, this.data.get(key) ?? null);
this.apply(key, entry, "write");
}
/** The only place that touches data, so the indexes can't drift. */
protected apply(key: string, entry: Entry | null, _cause: Cause): void {
const old = this.data.get(key);
if (old !== undefined) {
this.data.delete(key);
const holders = this.byValue.get(old.value)!;
holders.delete(key);
if (holders.size === 0) this.byValue.delete(old.value);
this.volatile.remove(key);
}
if (entry !== null) {
this.data.set(key, entry);
let holders = this.byValue.get(entry.value);
if (holders === undefined) this.byValue.set(entry.value, (holders = new Set()));
holders.add(key);
if (entry.expiresAt !== null) this.volatile.add(key);
}
}
checkInvariants(): void {
let indexed = 0;
for (const [value, keys] of this.byValue) {
for (const k of keys) {
if (this.data.get(k)?.value !== value) throw new Error(`value index drifted at ${k}`);
indexed++;
}
}
if (indexed !== this.data.size) throw new Error("value index drifted");
for (const [k, e] of this.data) {
if ((e.expiresAt !== null) !== this.volatile.has(k)) throw new Error(`volatile set drifted at ${k}`);
}
if (this.volatile.size > this.data.size) throw new Error("volatile set has ghosts");
}
}
// ---------- commands (Command pattern) ----------
/** One client's connection: the store plus the snapshots this client has named. */
export class Session {
readonly snapshots = new Map<string, Snapshot>();
constructor(readonly store: KvStore) {}
}
export interface Command {
execute(s: Session): string;
}
const flag = (b: boolean) => (b ? "1" : "0");
export class Get implements Command {
constructor(readonly key: string) {}
execute(s: Session) {
return s.store.get(this.key) ?? "(nil)";
}
}
export class SetCmd implements Command {
constructor(readonly key: string, readonly value: string, readonly ttlMs?: number) {}
execute(s: Session) {
s.store.set(this.key, this.value, this.ttlMs);
return "OK";
}
}
export class Del implements Command {
constructor(readonly key: string) {}
execute(s: Session) {
return flag(s.store.delete(this.key));
}
}
export class Exists implements Command {
constructor(readonly key: string) {}
execute(s: Session) {
return flag(s.store.exists(this.key));
}
}
export class Incr implements Command {
constructor(readonly key: string, readonly by = 1n) {}
execute(s: Session) {
return s.store.incr(this.key, this.by).toString();
}
}
export class Expire implements Command {
constructor(readonly key: string, readonly seconds: bigint) {}
execute(s: Session) {
return flag(s.store.expire(this.key, Number(this.seconds) * 1000));
}
}
export class Persist implements Command {
constructor(readonly key: string) {}
execute(s: Session) {
return flag(s.store.persist(this.key));
}
}
export class Ttl implements Command {
constructor(readonly key: string) {}
execute(s: Session) {
const ms = s.store.ttlMs(this.key);
return String(ms < 0 ? ms : Math.ceil(ms / 1000)); // whole seconds, rounded up
}
}
export class Count implements Command {
constructor(readonly value: string) {}
execute(s: Session) {
return String(s.store.count(this.value));
}
}
export class Begin implements Command {
execute(s: Session) {
s.store.begin();
return "OK";
}
}
export class Rollback implements Command {
execute(s: Session) {
s.store.rollback();
return "OK";
}
}
export class Commit implements Command {
execute(s: Session) {
s.store.commit();
return "OK";
}
}
export class TakeSnapshot implements Command {
constructor(readonly name: string) {}
execute(s: Session) {
s.snapshots.set(this.name, s.store.snapshot());
return "OK";
}
}
export class RestoreSnapshot implements Command {
constructor(readonly name: string) {}
execute(s: Session) {
const snap = s.snapshots.get(this.name);
if (snap === undefined) throw new KvError(`no such snapshot '${this.name}'`);
s.store.restore(snap);
return "OK";
}
}
function parseSet(a: string[]): Command {
if (a.length === 2) return new SetCmd(a[0], a[1]);
if (a[2].toUpperCase() !== "EX") throw new KvError("syntax error");
const seconds = parseInt64(a[3]);
if (seconds <= 0n || seconds > 9_000_000_000n) throw new KvError("invalid expire time");
return new SetCmd(a[0], a[1], Number(seconds) * 1000);
}
const COMMANDS: Record<string, [number[], (a: string[]) => Command]> = {
GET: [[1], (a) => new Get(a[0])],
SET: [[2, 4], parseSet],
DEL: [[1], (a) => new Del(a[0])],
EXISTS: [[1], (a) => new Exists(a[0])],
INCR: [[1], (a) => new Incr(a[0])],
INCRBY: [[2], (a) => new Incr(a[0], parseInt64(a[1]))],
EXPIRE: [[2], (a) => new Expire(a[0], parseInt64(a[1]))],
PERSIST: [[1], (a) => new Persist(a[0])],
TTL: [[1], (a) => new Ttl(a[0])],
COUNT: [[1], (a) => new Count(a[0])],
BEGIN: [[0], () => new Begin()],
ROLLBACK: [[0], () => new Rollback()],
COMMIT: [[0], () => new Commit()],
SNAPSHOT: [[1], (a) => new TakeSnapshot(a[0])],
RESTORE: [[1], (a) => new RestoreSnapshot(a[0])],
};
export function parse(line: string): Command {
const parts = line.trim().split(/\s+/).filter(Boolean);
if (parts.length === 0) throw new KvError("empty command");
const name = parts[0].toUpperCase();
const spec = Object.hasOwn(COMMANDS, name) ? COMMANDS[name] : undefined;
if (spec === undefined) throw new KvError(`unknown command '${parts[0]}'`);
const [arities, build] = spec;
const args = parts.slice(1);
if (!arities.includes(args.length)) throw new KvError(`wrong number of arguments for '${name.toLowerCase()}'`);
return build(args);
}
/** The driver: one line in, one reply out. Errors become replies, never crashes. */
export function run(session: Session, line: string): string {
try {
return parse(line).execute(session);
} catch (e) {
if (e instanceof KvError) return `ERR ${e.message}`;
throw e;
}
}
// ---------- demo ----------
async function main(): Promise<void> {
const clock = new ManualClock();
const store = new KvStore(clock, new SamplingExpiry(mulberry32(7)));
const session = new Session(store);
const check = (line: string, expected: string) => {
const got = run(session, line);
console.log(`> ${line.padEnd(22)} ${got}`);
if (got !== expected) throw new Error(`${line}: expected ${expected}, got ${got}`);
};
check("SET a 10", "OK");
check("INCR a", "11");
check("COUNT 11", "1");
check("BEGIN", "OK");
check("SET b 11", "OK");
check("COUNT 11", "2");
check("BEGIN", "OK");
check("DEL a", "1");
check("COUNT 11", "1");
check("ROLLBACK", "OK"); // only the inner layer is undone
check("GET a", "11");
check("SNAPSHOT s1", "OK"); // taken inside a transaction: b is not in it
check("COMMIT", "OK");
check("GET b", "11");
check("ROLLBACK", "ERR no transaction");
check("SET a 99", "OK");
check("RESTORE s1", "OK");
check("GET a", "11");
check("GET b", "(nil)");
check("SET s hello EX 5", "OK");
check("TTL s", "5");
clock.advance(4_001);
check("TTL s", "1");
clock.advance(999);
check("GET s", "(nil)"); // lazy expiry, exactly at the deadline
check("SET w abc", "OK");
check("INCR w", "ERR value is not an integer or out of range");
check("SET x 1 EX 0", "ERR invalid expire time");
check("GET", "ERR wrong number of arguments for 'get'");
check("FLY a", "ERR unknown command 'FLY'");
for (let i = 0; i < 1_000; i++) store.set(`tmp:${i}`, "t", 100);
clock.advance(100);
let cycles = 0;
while (store.volatileCount() > 0) {
const reaped = store.activeExpireCycle();
if (reaped <= 0 || reaped > 16 * 20) throw new Error(`cycle reaped ${reaped}`);
cycles++;
}
if (store.get("a") !== "11" || store.count("t") !== 0) throw new Error("expiry hit live keys");
store.checkInvariants();
console.log(`active expiry cleared 1000 keys in ${cycles} cycles`);
// The timer-driven sweeper, with a manual clock.
store.set("soon", "x", 10);
const stop = store.startActiveExpiry(5);
clock.advance(10);
await new Promise((resolve) => setTimeout(resolve, 50));
stop();
if (store.size !== 2) throw new Error("sweeper did not run");
console.log("kv.ts ok");
}
if (require.main === module) {
main().catch((e) => {
console.error(e);
process.exit(1);
});
}
Every listing prints the same transcript:
> SET a 10 OK
> INCR a 11
> COUNT 11 1
> BEGIN OK
> SET b 11 OK
> COUNT 11 2
> BEGIN OK
> DEL a 1
> COUNT 11 1
> ROLLBACK OK
> GET a 11
> SNAPSHOT s1 OK
> COMMIT OK
> GET b 11
> ROLLBACK ERR no transaction
> SET a 99 OK
> RESTORE s1 OK
> GET a 11
> GET b (nil)
> SET s hello EX 5 OK
> TTL s 5
> TTL s 1
> GET s (nil)
> SET w abc OK
> INCR w ERR value is not an integer or out of range
> SET x 1 EX 0 ERR invalid expire time
> GET ERR wrong number of arguments for 'get'
> FLY a ERR unknown command 'FLY'
active expiry cleared 1000 keys in 4 cycles
Look at the snapshot lines. SNAPSHOT s1 runs while a transaction that set b is still open, so s1 doesn't contain b. The transaction then commits, b becomes permanent, and RESTORE s1 removes it again. That's the behaviour you'd expect from a snapshot of committed state, and it falls straight out of the peeling step in snapshot().
Walking through the code
apply is the only method that touches the data map. It removes the old entry from the value index and the volatile set, then adds the new one. Client writes, rollback, expiry, restore, and every extension in section 8 go through it. When an interviewer asks "how do you know the index is consistent after a rollback?", point at this method: rollback has no index code of its own, so it can't get the index wrong.
write is the only method that logs. It records the before-image if the top layer hasn't seen the key yet, then calls apply. It's private, so neither a subclass nor a command can skip it.
Before-images are entries, not values. The layer stores the whole old Entry, including its deadline. That's why PERSIST followed by ROLLBACK brings the TTL back, and why INCR inside a transaction doesn't lose the key's expiry on rollback.
Rollback checks the image's deadline. Suppose k has a 10 ms TTL, a transaction overwrites it, and 20 ms pass before the rollback. The before-image says "k = old value, expires at 10". Restoring it as-is would put an expired entry back. That would be harmless for reads, because lazy expiry would catch it, but it would still be wrong for size() and for the value index until something reaped it. So rollback restores the image only if it's still live, and otherwise restores absence. There's a test for exactly this.
count reaps before it counts. The value index maps a value to the keys holding it, and some of them may have expired without anyone noticing. count walks that set (O(k)), reaps the dead ones, and returns what's left. The alternative, an O(1) counter per value, can't tell live keys from expired ones. It would return a number that includes keys GET says don't exist. This trade-off is worth stating: O(k) exact, or O(1) approximate. This design chooses exact, because a count that disagrees with GET is a bug report waiting to happen.
incr validates strictly. Python's int() accepts " 7", "+7" and "1_000". Java's Long.parseLong accepts "+7". Redis accepts none of these, and a store that sometimes accepts them is a store whose behaviour depends on its implementation language. A regular expression -?[0-9]+, followed by a 64-bit range check, makes all three languages agree. TypeScript uses BigInt, because a JavaScript number can't represent integers above 2^53 exactly. One of the tests increments 9007199254740993 to prove it.
VolatileKeys is an array plus an index map. Sampling needs a uniformly random key with a TTL in O(1). A hash set can't give you that, so this is the standard "insert, delete, get random in O(1)" structure. Removal swaps the last element into the hole.
The parser is a table. Each row says which argument counts are legal and how to build the command. Arity errors are produced in one place, with one message format. TypeScript looks commands up with Object.hasOwn, so toString is an unknown command, not a crash. A plain object lookup would have found Object.prototype.toString instead.
The driver never throws for client errors. run(session, line) catches KvError and returns ERR .... Anything else, a genuine bug, propagates, because hiding bugs as error replies makes them impossible to find.
7. Concurrency
What's shared
Everything in KvStore is shared: the data map, the value index, the volatile set, the layer stack and the expiry counter. Several of them must change together. An apply that has updated the map but not yet the index is a moment when count returns the wrong number. So the unit of atomicity is a whole operation, not a single map access.
The trap: reads are writes
It's tempting to use a read-write lock with get under the read lock. That's broken here, because get can delete. A read that finds an expired entry removes it from three structures. Two readers doing that at once corrupt the value index. The same applies to exists, ttl and count. This mirrors the LRU cache, where get reorders the recency list. Any design with lazy side effects on reads has the same property. You could make reads pure (return null for expired entries, but leave the removal to the sweeper), and then a read lock becomes legal. It's a reasonable trade if reads dominate heavily.
Option 1: one lock (what the listings do)
Java uses one ReentrantLock and Python one RLock, held for the duration of every public method. Every operation is a few hash map operations, so the critical section is well under a microsecond, and a single lock handles hundreds of thousands of operations per second. The lock is reentrant because strategies call back into the store (reapIfExpired) while activeExpireCycle holds it.
It's simple and obviously correct, and the active expiry cycle is bounded (at most 16 × 20 key checks), so it can't hold the lock for long. The ceiling is that throughput doesn't grow with cores. Redis makes the same choice in a stronger form: one thread executes every command, so there's no lock at all and still no parallelism within the keyspace. That's evidence that the simple answer is often the right one.
Option 2: striped locks, and why transactions get in the way
Striping splits the keyspace into N segments by hash(key) % N, each with its own map and lock. Threads working on different segments don't contend. It's how ConcurrentHashMap scaled in Java 7, and for plain GET and SET it works well.
Then the other requirements arrive, and each one fights striping:
- The value index is global.
count("10")needs keys from every segment. Either each segment keeps its own index andcountlocks all N segments (in a fixed order, to avoid deadlock) and sums them, or there's a global index with its own lock, which every write takes. That puts the contention right back. - Transactions span keys, and so span segments.
BEGIN; SET a 1; SET b 2; ROLLBACKtouches two segments. Rollback must restore both atomically, or another thread can seearestored andbnot. That means taking several segment locks at once, always in ascending segment order, so two transactions can't deadlock by locking in opposite orders. - The undo layers are per transaction, not per segment. A layer is a cross-segment structure, and so is the snapshot, which needs every segment locked at once to be consistent.
- Active expiry samples across all TTL keys. Each segment needs its own volatile set and its own sampler, or the sampler takes each lock in turn.
So the honest answer is: stripe the data, keep transactions coarse. Plain single-key commands outside a transaction take one stripe lock. Multi-key operations (rollback, commit at depth one, snapshot, count) take all stripes in order. If transactions are rare, that's a real win. If they're common, striping buys little, and a single lock plus shorter critical sections is better. Being able to say why is worth more than drawing the striped version.
Option 3: per-client transaction contexts
With a single client, write-through is ideal. With many clients, it has a serious flaw: Alice's uncommitted SET balance 70 is immediately visible to Bob (a dirty read). Worse, if Bob writes balance and Alice then rolls back, Alice's before-image overwrites Bob's committed write. That's a lost update.
There are three ways out:
- A global transaction lock.
BEGINtakes a store-wide lock and the outermostCOMMITorROLLBACKreleases it. Transactions become serial, and every problem disappears. So does concurrency, and a client that forgets to commit blocks everyone. You'd need a timeout. It's fine for an embedded store with one writer. - Redis-style queueing.
MULTIdoesn't execute anything. It queues commands in the client's session, andEXECruns the whole queue under the lock in one go. Nobody sees partial results. The cost is that a command can't read its own earlier writes inside the transaction, because nothing has run yet, and there's no rollback, only discard. Redis addsWATCHfor optimistic checks. - Per-client overlay contexts with validated commit. Each session keeps its own layer stack of new values (option A from section 2) and reads through it to the shared map. Other clients never see uncommitted data. At the outermost commit, the session takes the lock, checks that no key it read or wrote has changed since it first touched it (each key carries a version number), and applies its writes atomically, or aborts. That's optimistic concurrency control: reads see the latest committed data, and a commit fails if anything it read or wrote has changed since.
Here's option 3 as a compact, runnable sketch. It leaves out TTL and the value index to keep the idea visible:
# file: sessions.py
"""Per-client transaction contexts over one shared map: buffered writes, validated commit."""
import threading
from typing import Dict, List, Optional
_DELETED = object()
class SharedMap:
def __init__(self) -> None:
self.lock = threading.Lock()
self.data: Dict[str, str] = {}
self.version: Dict[str, int] = {} # bumped on every committed write
class ClientContext:
"""Uncommitted writes live here, so other clients never see them."""
def __init__(self, shared: SharedMap) -> None:
self.shared = shared
self.layers: List[Dict[str, object]] = [] # key -> value or _DELETED
self.seen: Dict[str, int] = {} # version of each key when first touched
def begin(self) -> None:
self.layers.append({})
def get(self, key: str) -> Optional[str]:
for layer in reversed(self.layers):
if key in layer:
v = layer[key]
return None if v is _DELETED else v # type: ignore[return-value]
with self.shared.lock:
if self.layers:
self.seen.setdefault(key, self.shared.version.get(key, 0))
return self.shared.data.get(key)
def set(self, key: str, value: Optional[str]) -> None:
if not self.layers:
self._publish({key: _DELETED if value is None else value})
return
with self.shared.lock:
self.seen.setdefault(key, self.shared.version.get(key, 0))
self.layers[-1][key] = _DELETED if value is None else value
def rollback(self) -> None:
self.layers.pop()
if not self.layers:
self.seen.clear()
def commit(self) -> bool:
"""False means another client changed a key we touched: nothing was applied."""
top = self.layers.pop()
if self.layers:
self.layers[-1].update(top) # nested commit: merge down, publish nothing
return True
with self.shared.lock:
stale = any(self.shared.version.get(k, 0) != v for k, v in self.seen.items())
self.seen.clear()
if stale:
return False
self._apply_locked(top)
return True
def _publish(self, writes: Dict[str, object]) -> None:
with self.shared.lock:
self._apply_locked(writes)
def _apply_locked(self, writes: Dict[str, object]) -> None:
for k, v in writes.items():
if v is _DELETED:
self.shared.data.pop(k, None)
else:
self.shared.data[k] = v # type: ignore[assignment]
self.shared.version[k] = self.shared.version.get(k, 0) + 1
if __name__ == "__main__":
shared = SharedMap()
alice, bob = ClientContext(shared), ClientContext(shared)
alice.set("balance", "100")
alice.begin()
alice.set("balance", str(int(alice.get("balance") or 0) - 30))
assert bob.get("balance") == "100" # Bob can't see Alice's uncommitted write
bob.set("balance", "500") # Bob writes outside a transaction
assert alice.commit() is False # Alice's read is stale, so her commit aborts
assert shared.data["balance"] == "500"
alice.begin()
alice.set("balance", str(int(alice.get("balance") or 0) - 30))
alice.begin()
alice.set("note", "draft")
alice.rollback() # only the inner layer goes
assert alice.commit() is True
assert shared.data == {"balance": "470"}
print("sessions.py ok")
Notice where the transaction state lives now: in ClientContext, one per connection. That's what the Session class in the main listing is for. The single-client design keeps the layer stack in the store for simplicity, and moving it into the session is the first step towards multiple clients. The price of the overlay is the one section 2 described: reads walk the layers, and an exact count inside a transaction has to combine the shared index with the session's pending changes.
Python and TypeScript
Python's threading.RLock is used the same way as Java's lock. The GIL makes individual dictionary operations atomic, but not a sequence of them, so apply still needs the lock. Without it, the eight-thread INCR test in the demo can lose updates, because incr reads, computes and writes in separate steps. TypeScript runs JavaScript on a single thread, so each method runs to completion without interleaving, as long as none of them awaits in the middle. The sweeper is a setInterval callback, which runs between operations, never inside one. If you ever share the store across worker_threads, you need a different design (a dedicated owner thread with message passing), because ordinary JavaScript objects aren't shared between workers.
8. Extensions: "the interviewer adds X"
Extension A: "Cap the store at N keys and evict the least recently used one"
This is where the LRU cache design plugs in. The store already has the two hooks it needs. live is called on every read that finds a key, so it can record a use. apply is called on every change, so it can track insertions, deletions and enforce the cap. A subclass overrides both and keeps an OrderedDict (the hash map plus linked list from the LRU page, built in) in recency order.
# file: ext_bounded.py
"""Extension A: cap the number of keys and evict the least recently used one."""
from collections import OrderedDict
from typing import Optional
from kv import Cause, Entry, ExpiryStrategy, KvStore, LazyOnly, ManualClock, Clock
class BoundedKvStore(KvStore):
def __init__(self, max_keys: int, clock: Optional[Clock] = None,
expiry: Optional[ExpiryStrategy] = None) -> None:
if max_keys < 1:
raise ValueError("max_keys must be at least 1")
super().__init__(clock, expiry)
self.max_keys = max_keys
self._recency: "OrderedDict[str, None]" = OrderedDict() # oldest first
self.evicted_total = 0
def _live(self, key: str) -> Optional[Entry]:
e = super()._live(key)
if e is not None:
self._recency.move_to_end(key) # a read is a use
return e
def _apply(self, key: str, entry: Optional[Entry], cause: Cause) -> None:
super()._apply(key, entry, cause)
if entry is None:
self._recency.pop(key, None)
return
self._recency[key] = None
self._recency.move_to_end(key)
while len(self._recency) > self.max_keys:
victim, _ = self._recency.popitem(last=False)
super()._apply(victim, None, Cause.EVICT) # not logged: rollback won't resurrect it
self.evicted_total += 1
if __name__ == "__main__":
s = BoundedKvStore(3, ManualClock(), LazyOnly())
for k in "abc":
s.set(k, k)
s.get("a") # b is now the least recently used
s.set("d", "d")
assert [s.exists(k) for k in "abcd"] == [True, False, True, True]
assert s.count("b") == 0 # the value index saw the eviction
# EXISTS counts as a use too, so the assert above left the order a, c, d.
s.begin()
s.set("e", "e") # evicts a
s.rollback() # removes e, but a stays evicted
assert [s.exists(k) for k in "acde"] == [False, True, True, False]
assert s.size() <= 3 and s.evicted_total == 2
s.check_invariants()
print("ext_bounded.py ok")
The interesting questions are about interactions, not about LRU:
- Is an eviction a transactional change? No. Like expiry, it's a physical removal, so it calls the base
applydirectly and isn't logged. A rollback won't bring an evicted key back, unless the rolled-back layer had itself changed that key, in which case the before-image is restored. The cap is then enforced again by the sameapplyoverride, which may evict something else. Say this out loud, because "rollback restores exactly the old state" is no longer strictly true once memory limits exist. - Should expired keys be evicted first? Usually yes. An expired key is free to remove and nobody will miss it. A refinement samples a few keys with TTLs before falling back to the LRU victim, which is close to Redis's
volatile-lrupolicy. - Keys or bytes? Real limits are on memory. Track an estimated size per entry (key length plus value length plus overhead) in
apply, and evict while the total is over budget. - Does
COUNTcount as a use? Here, no, becausecountdoesn't go throughlive. That's a choice. A scan that touched every key would otherwise flatten the recency order.
Extension B: "Tell subscribers when keys change"
Keyspace notifications are an Observer. The transaction layers make them more interesting than usual: should a subscriber hear about a SET that's later rolled back? It shouldn't, because then subscribers would see changes that, as far as the database is concerned, never happened. So events from inside a transaction are buffered per layer, merged into the parent on commit, published at the outermost commit, and dropped on rollback. That's the same discipline as the undo layers, applied to events. Expiry and eviction events aren't transactional, so they're published immediately.
// file: notify.ts
// Extension B: keyspace notifications. Observers hear about committed changes only.
import { Cause, Entry, KvStore, LazyOnly, ManualClock } from "./kv";
export type KeyEvent = { key: string; kind: "set" | "del" | "expired" | "evicted" };
export type Listener = (event: KeyEvent) => void;
export class NotifyingKvStore extends KvStore {
private readonly listeners = new Set<Listener>();
private readonly pending: KeyEvent[][] = []; // one buffer per open transaction
private outbox: KeyEvent[] = [];
subscribe(listener: Listener): () => void {
this.listeners.add(listener);
return () => this.listeners.delete(listener);
}
override begin(): void {
super.begin();
this.pending.push([]);
}
override rollback(): void {
super.rollback(); // throws first if there is no transaction
this.pending.pop(); // the events never happened, as far as anyone else knows
}
override commit(): void {
super.commit();
const top = this.pending.pop()!;
const parent = this.pending.at(-1);
if (parent !== undefined) parent.push(...top);
else this.publish(top);
}
protected override apply(key: string, entry: Entry | null, cause: Cause): void {
super.apply(key, entry, cause);
if (cause === "write") {
const event: KeyEvent = { key, kind: entry === null ? "del" : "set" };
const buffer = this.pending.at(-1);
if (buffer !== undefined) buffer.push(event);
else this.publish([event]);
} else if (cause === "expire" || cause === "evict") {
this.publish([{ key, kind: cause === "expire" ? "expired" : "evicted" }]); // not transactional
} // "undo" cancels buffered events, and "restore" is a bulk reload: neither is announced
}
/** Deliver after the current operation returns, so a listener can safely call the store. */
private publish(events: KeyEvent[]): void {
if (events.length === 0) return;
const first = this.outbox.length === 0;
this.outbox.push(...events);
if (first) queueMicrotask(() => this.flush());
}
private flush(): void {
const batch = this.outbox;
this.outbox = [];
for (const event of batch) {
for (const listener of [...this.listeners]) {
try {
listener(event);
} catch (err) {
console.error("listener failed", err); // one bad listener can't break the others
}
}
}
}
}
async function main(): Promise<void> {
const clock = new ManualClock();
const store = new NotifyingKvStore(clock, new LazyOnly());
const seen: string[] = [];
store.subscribe((e) => seen.push(`${e.kind}:${e.key}`));
store.subscribe(() => {
throw new Error("buggy listener");
});
const settle = () => new Promise((resolve) => setImmediate(resolve));
const quiet = console.error;
console.error = () => {}; // keep the demo output clean
store.set("a", "1");
store.begin();
store.set("b", "2");
store.begin();
store.delete("a");
store.rollback(); // del:a is dropped
store.set("c", "3", 10);
await settle();
if (seen.join() !== "set:a") throw new Error(`uncommitted events leaked: ${seen}`);
store.commit(); // outermost commit releases set:b and set:c, in order
clock.advance(10);
store.get("c"); // lazy expiry fires immediately, no transaction involved
await settle();
console.error = quiet;
const want = "set:a,set:b,set:c,expired:c";
if (seen.join() !== want) throw new Error(`got ${seen}, want ${want}`);
console.log("notify.ts ok");
}
if (require.main === module) {
main().catch((e) => {
console.error(e);
process.exit(1);
});
}
Three design points:
- Delivery happens after the operation, not inside it.
applyruns in the middle of loops such as rollback, restore andcount. A listener that called back into the store from insideapplywould mutate structures that the loop is iterating. Queuing events and delivering them on a microtask is the single-threaded version of "collect under the lock, notify after releasing it". In Java you'd collect events in a list while holding the lock and deliver them afterunlock(), ideally on a separate executor so a slow subscriber can't stall writers. - Listener failures are isolated. One throwing listener doesn't stop the others or corrupt the store.
- Undo and restore are silent. A rollback's undo writes cancel events that were never published, so announcing them would be noise. A restore is a bulk reload. If subscribers need to know about it, publish one
restoreevent, not one per key.
Extension C: "Support SCAN from to: keys in sorted order"
A hash map has no order. The options are to replace it with a sorted map (a TreeMap, a red-black tree), which makes every operation O(log n), or to keep the hash map for point lookups and maintain a sorted index of keys beside it. The second keeps GET at O(1), and the sorted index costs O(log n) only on inserts and deletes. Since every insert and delete already goes through apply, the index is one override.
// file: RangeScanDemo.java
import java.util.*;
/** Extension C: a sorted index of keys beside the hash map, for SCAN from to. */
class SortedKvStore extends KvStore {
private final TreeSet<String> sortedKeys = new TreeSet<>();
SortedKvStore(Clock clock, ExpiryStrategy expiry) { super(clock, expiry); }
@Override
protected void apply(String key, Entry entry, Cause cause) {
super.apply(key, entry, cause); // every change to the map passes through here
if (entry == null) sortedKeys.remove(key); else sortedKeys.add(key);
}
/** Live keys in [from, to), in order, at most limit of them. O((scanned) log n). */
List<String> range(String from, String to, int limit) {
return locked(() -> {
List<String> out = new ArrayList<>();
// Step with ceiling/higher instead of an iterator: live() may reap a key,
// which removes it from sortedKeys, and higher() works on a removed key too.
for (String k = sortedKeys.ceiling(from); k != null && k.compareTo(to) < 0 && out.size() < limit;
k = sortedKeys.higher(k)) {
if (live(k) != null) out.add(k);
}
return out;
});
}
}
public class RangeScanDemo {
public static void main(String[] args) {
ManualClock clock = new ManualClock();
SortedKvStore s = new SortedKvStore(clock, new LazyOnly());
for (String k : List.of("user:3", "user:1", "order:9", "user:2", "user:10", "vip:1")) s.set(k, "x");
s.set("user:15", "x", 50);
// Strings sort lexicographically, so user:10 and user:15 come before user:2.
KvTests.eq(List.of("user:1", "user:10", "user:15", "user:2", "user:3"), s.range("user:", "user;", 100));
KvTests.eq(List.of("user:1", "user:10"), s.range("user:", "user;", 2));
clock.advance(50);
KvTests.eq(List.of("user:1", "user:10", "user:2", "user:3"), s.range("user:", "user;", 100));
KvTests.eq(6, s.size()); // the scan reaped user:15 as it went
s.begin();
s.delete("user:2");
s.set("user:4", "x");
KvTests.eq(List.of("user:1", "user:10", "user:3", "user:4"), s.range("user:", "user;", 100));
s.rollback(); // undo goes through apply(), so the sorted index follows
KvTests.eq(List.of("user:1", "user:10", "user:2", "user:3"), s.range("user:", "user;", 100));
s.checkInvariants();
System.out.println("RangeScanDemo ok");
}
}
Details that matter:
- Iterating while reaping. The scan must skip expired keys, and reaping one removes it from
sortedKeys. Removing from aTreeSetwhile iterating over it throwsConcurrentModificationException. Stepping withceilingandhigheravoids the iterator entirely, andhigher(k)still works afterkitself has been removed. - Lexicographic order.
user:10sorts beforeuser:2. Real systems pad numbers in keys (user:0002) or offer a numeric index. Point it out before the interviewer does. - Half-open ranges and a limit.
[from, to)composes cleanly (the next page starts where the last one ended), and the limit keeps one call from holding the lock across millions of keys. For a cursor that survives concurrent writes, return the last key seen and start the next call from it. - Transactions work for free. The rollback in the demo restores
user:2and removesuser:4throughapply, so the sorted index follows without any transaction-specific code. That's the payoff of having one write path.
In Python, the standard library has no sorted set. bisect on a sorted list gives O(log n) search but O(n) insert, which is fine up to around a hundred thousand keys. Past that, use the third-party sortedcontainers package. TypeScript has no built-in sorted map either. Use a library or a hand-written skip list. In the interview, name the structure and its complexity, and don't write a red-black tree.
9. Testing
The demo in each listing checks one long scenario. A proper suite tests one behaviour per test, never sleeps, and includes one test that's worth more than all the others: a model-based random test.
What to cover:
- TTL boundary. Live at
deadline - 1, gone atdeadline, and the read that found it expired also removed it (sizedrops). - TTL semantics.
SETclears a TTL,INCRkeeps it,EXPIRE 0deletes, andttlreturns -2 for a missing key and -1 for a key without a TTL. INCRstrictness. Missing keys start at zero. Junk such as" 7","+7"and"1.5"is rejected, overflow is rejected, and a failedINCRchanges nothing.- Rollback scope. Only the top layer is undone. An outer rollback undoes an inner commit.
- TTL through transactions. Rollback restores a TTL removed by
PERSIST. A key that expires during a transaction stays gone after rollback. - Count consistency.
countfollows overwrite, delete, expiry (without aGETin between) and rollback. - Snapshots. They exclude open transactions, they're isolated from later writes, restore drops entries that expired in the meantime while keeping absolute deadlines, and restore is rejected inside a transaction.
- Active expiry. Sampling and full scan both eventually clear every expired key and never touch persistent ones. A seeded RNG makes this deterministic.
- Parser. Case-insensitive names, arity errors, unknown commands,
SET ... PXas a syntax error, and blank lines. - The model test. Five thousand random
set,del,incr,begin,rollbackandcommitoperations against a naive reference: a stack of full dictionary copies, wherebegincopies the top,rollbackpops it andcommitreplaces the parent with it. After every operation, every key's value and every value's count must match the model. Finally,checkInvariantsrebuilds the index from scratch and compares.
The model test is the one that finds real bugs. While writing this page, it caught one in the Java listing that the hand-written tests missed. The first version of commit merged the layers with parent.putIfAbsent(key, image). But putIfAbsent treats a key that's mapped to null as absent, and in an undo layer null means "the key didn't exist before". So when both layers had touched a key that the outer layer had created, the child's image overwrote the parent's, and an outer rollback restored a value that should have vanished. The fix is an explicit containsKey check. The bug lives in the gap between "absent" and "present with no value", which only a random sequence of nested operations reliably hits. To confirm that a test can fail, break the code on purpose once: change the merge so the child's image wins, and the model test fails within a few hundred operations.
// file: KvTests.java
import java.util.*;
class KvTests {
static int passed;
static void test(String name, Runnable body) {
body.run();
passed++;
System.out.println(" ok " + name);
}
static void eq(Object expected, Object actual) {
if (!Objects.equals(expected, actual)) throw new AssertionError("expected " + expected + ", got " + actual);
}
static void expectKvError(Runnable r) {
try { r.run(); } catch (KvException e) { return; }
throw new AssertionError("expected KvException");
}
public static void main(String[] args) {
test("ttl deadline is exclusive and the read removes the key", () -> {
ManualClock clock = new ManualClock();
KvStore s = new KvStore(clock, new LazyOnly());
s.set("k", "v", 50);
clock.advance(49);
eq("v", s.get("k"));
clock.advance(1);
eq(null, s.get("k"));
eq(0, s.size());
});
test("set clears ttl, incr keeps it", () -> {
KvStore s = new KvStore(new ManualClock(), new LazyOnly());
s.set("n", "1", 100);
s.incr("n", 1);
eq(100L, s.ttlMillis("n"));
s.set("n", "5");
eq(-1L, s.ttlMillis("n"));
eq(-2L, s.ttlMillis("missing"));
});
test("incr rejects non-integers and overflow without changing anything", () -> {
KvStore s = new KvStore(new ManualClock(), new LazyOnly());
for (String bad : List.of("abc", "1.5", " 7", "+7", "")) {
s.set("k", bad);
expectKvError(() -> s.incr("k", 1));
}
s.set("k", Long.toString(Long.MAX_VALUE));
expectKvError(() -> s.incr("k", 1));
eq(Long.toString(Long.MAX_VALUE), s.get("k"));
});
test("rollback discards only the top layer", () -> {
KvStore s = new KvStore(new ManualClock(), new LazyOnly());
s.set("a", "1");
s.begin(); s.set("a", "2");
s.begin(); s.set("a", "3"); s.delete("a");
s.rollback();
eq("2", s.get("a"));
s.rollback();
eq("1", s.get("a"));
});
test("inner commit is undone by outer rollback", () -> {
KvStore s = new KvStore(new ManualClock(), new LazyOnly());
s.begin(); s.begin();
s.set("x", "inner");
s.commit();
s.rollback();
eq(null, s.get("x"));
expectKvError(s::commit);
});
test("count follows writes, expiry and rollback", () -> {
ManualClock clock = new ManualClock();
KvStore s = new KvStore(clock, new LazyOnly());
s.set("a", "v"); s.set("b", "v", 5);
eq(2, s.count("v"));
clock.advance(5);
eq(1, s.count("v"));
s.begin(); s.delete("a");
eq(0, s.count("v"));
s.rollback();
eq(1, s.count("v"));
s.checkInvariants();
});
test("snapshot holds committed state only", () -> {
KvStore s = new KvStore(new ManualClock(), new LazyOnly());
s.set("a", "1");
s.begin(); s.set("a", "2"); s.set("b", "2");
Snapshot snap = s.snapshot();
s.commit();
s.restore(snap);
eq("1", s.get("a"));
eq(null, s.get("b"));
s.begin();
expectKvError(() -> s.restore(snap));
});
test("sampling expiry never touches persistent keys", () -> {
ManualClock clock = new ManualClock();
KvStore s = new KvStore(clock, new SamplingExpiry(new Random(1)));
for (int i = 0; i < 300; i++) { s.set("t" + i, "x", 10); s.set("p" + i, "y"); }
clock.advance(10);
while (s.volatileCount() > 0) s.activeExpireCycle();
eq(300, s.size());
eq(300, s.count("y"));
s.checkInvariants();
});
test("parser replies", () -> {
Session sess = new Session(new KvStore(new ManualClock(), new LazyOnly()));
String[][] cases = {
{"set k 5", "OK"}, {"INCRBY k 10", "15"}, {"SET k v PX 5", "ERR syntax error"},
{"COMMIT", "ERR no transaction"}, {" ", "ERR empty command"},
{"DEL k extra", "ERR wrong number of arguments for 'del'"}, {"DEL k", "1"}, {"TTL k", "-2"},
};
for (String[] c : cases) eq(c[1], CommandParser.run(sess, c[0]));
});
test("random operations match a naive model", () -> {
Random rng = new Random(42);
KvStore s = new KvStore(new ManualClock(), new LazyOnly());
ArrayDeque<Map<String, String>> model = new ArrayDeque<>();
model.push(new HashMap<>());
List<String> keys = List.of("a", "b", "c", "d"), values = List.of("1", "2", "x");
String[] ops = {"set", "set", "del", "incr", "begin", "rollback", "commit"};
for (int i = 0; i < 5_000; i++) {
String op = ops[rng.nextInt(ops.length)], k = keys.get(rng.nextInt(keys.size()));
Map<String, String> top = model.peek();
switch (op) {
case "set" -> { String v = values.get(rng.nextInt(values.size())); s.set(k, v); top.put(k, v); }
case "del" -> { eq(top.containsKey(k), s.delete(k)); top.remove(k); }
case "incr" -> {
String cur = top.getOrDefault(k, "0");
if (cur.matches("-?[0-9]+")) top.put(k, Long.toString(s.incr(k, 1)));
else expectKvError(() -> s.incr(k, 1));
}
case "begin" -> { s.begin(); model.push(new HashMap<>(top)); }
default -> {
if (model.size() == 1) break;
if (op.equals("rollback")) { s.rollback(); model.pop(); }
else { s.commit(); Map<String, String> done = model.pop(); model.pop(); model.push(done); }
}
}
Map<String, String> now = model.peek();
for (String key : keys) eq(now.get(key), s.get(key));
for (String v : values) eq((int) now.values().stream().filter(v::equals).count(), s.count(v));
}
s.checkInvariants();
});
System.out.println("KvTests: " + passed + " passed");
}
}
# file: test_kv.py (run with: python -m unittest test_kv)
import random
import unittest
from kv import FullScan, KvError, KvStore, LazyOnly, ManualClock, SamplingExpiry, Session, run
def fresh(expiry=None):
clock = ManualClock()
return KvStore(clock, expiry or LazyOnly()), clock
class TtlTest(unittest.TestCase):
def test_deadline_is_exclusive(self):
s, clock = fresh()
s.set("k", "v", ttl_ms=50)
clock.advance(49)
self.assertEqual(s.get("k"), "v")
clock.advance(1)
self.assertIsNone(s.get("k"))
self.assertEqual(s.size(), 0) # the read removed it
def test_set_clears_ttl_and_incr_keeps_it(self):
s, clock = fresh()
s.set("n", "1", ttl_ms=100)
s.incr("n")
self.assertEqual(s.ttl_ms("n"), 100)
s.set("n", "5")
self.assertEqual(s.ttl_ms("n"), -1)
self.assertEqual(s.ttl_ms("missing"), -2)
def test_expire_zero_deletes(self):
s, _ = fresh()
s.set("k", "v")
self.assertTrue(s.expire("k", 0))
self.assertFalse(s.exists("k"))
def test_lazy_only_leaves_garbage_until_read(self):
s, clock = fresh(LazyOnly())
s.set("k", "v", ttl_ms=1)
clock.advance(5)
self.assertEqual(s.active_expire_cycle(), 0)
self.assertEqual(s.size(), 1)
def test_full_scan_and_sampling_never_touch_persistent_keys(self):
for strategy in (FullScan(), SamplingExpiry(rng=random.Random(1))):
s, clock = fresh(strategy)
for i in range(300):
s.set(f"t{i}", "x", ttl_ms=10)
s.set(f"p{i}", "y")
clock.advance(10)
while s.volatile_count():
s.active_expire_cycle()
self.assertEqual(s.size(), 300)
self.assertEqual(s.count("y"), 300)
s.check_invariants()
class IncrTest(unittest.TestCase):
def test_missing_key_starts_at_zero(self):
s, _ = fresh()
self.assertEqual(s.incr("c"), 1)
self.assertEqual(s.incr("c", -3), -2)
def test_rejects_non_integers_and_overflow(self):
s, _ = fresh()
for bad in ["abc", "1.5", " 7", "+7", "1_000", ""]:
s.set("k", bad)
with self.assertRaises(KvError):
s.incr("k")
s.set("k", str(2**63 - 1))
with self.assertRaises(KvError):
s.incr("k")
self.assertEqual(s.get("k"), str(2**63 - 1)) # a failed INCR changes nothing
class TransactionTest(unittest.TestCase):
def test_rollback_discards_only_the_top_layer(self):
s, _ = fresh()
s.set("a", "1")
s.begin()
s.set("a", "2")
s.begin()
s.set("a", "3")
s.delete("a")
s.rollback()
self.assertEqual(s.get("a"), "2")
s.rollback()
self.assertEqual(s.get("a"), "1")
def test_inner_commit_is_undone_by_outer_rollback(self):
s, _ = fresh()
s.begin()
s.begin()
s.set("x", "inner")
s.commit()
self.assertEqual(s.get("x"), "inner")
s.rollback()
self.assertIsNone(s.get("x"))
s.check_invariants()
def test_rollback_restores_ttl(self):
s, clock = fresh()
s.set("k", "v", ttl_ms=100)
s.begin()
s.persist("k")
s.rollback()
self.assertEqual(s.ttl_ms("k"), 100)
clock.advance(100)
self.assertIsNone(s.get("k"))
def test_key_that_expired_during_transaction_stays_gone(self):
s, clock = fresh()
s.set("k", "v", ttl_ms=10)
s.begin()
s.set("k", "new")
clock.advance(20)
s.rollback()
self.assertIsNone(s.get("k"))
s.check_invariants()
def test_no_transaction(self):
s, _ = fresh()
with self.assertRaises(KvError):
s.commit()
with self.assertRaises(KvError):
s.rollback()
class CountTest(unittest.TestCase):
def test_count_follows_every_kind_of_change(self):
s, clock = fresh()
s.set("a", "v")
s.set("b", "v", ttl_ms=5)
self.assertEqual(s.count("v"), 2)
s.set("a", "w")
self.assertEqual((s.count("v"), s.count("w")), (1, 1))
clock.advance(5)
self.assertEqual(s.count("v"), 0) # expiry is visible to COUNT without a GET
s.begin()
s.delete("a")
self.assertEqual(s.count("w"), 0)
s.rollback()
self.assertEqual(s.count("w"), 1)
s.check_invariants()
class SnapshotTest(unittest.TestCase):
def test_snapshot_excludes_open_transactions_and_is_isolated(self):
s, _ = fresh()
s.set("a", "1")
s.begin()
s.set("a", "2")
s.set("b", "2")
snap = s.snapshot()
s.commit()
s.set("c", "3")
s.restore(snap)
self.assertEqual((s.get("a"), s.get("b"), s.get("c")), ("1", None, None))
self.assertEqual(len(snap), 1)
def test_restore_drops_entries_that_expired_meanwhile(self):
s, clock = fresh()
s.set("short", "x", ttl_ms=10)
s.set("long", "x", ttl_ms=1000)
snap = s.snapshot()
clock.advance(50)
s.restore(snap)
self.assertEqual(s.size(), 1)
self.assertEqual(s.ttl_ms("long"), 950) # absolute deadlines survive
def test_restore_inside_transaction_is_rejected(self):
s, _ = fresh()
snap = s.snapshot()
s.begin()
with self.assertRaises(KvError):
s.restore(snap)
class ParserTest(unittest.TestCase):
def test_replies(self):
sess = Session(fresh()[0])
cases = [
("set k 5", "OK"), ("INCRBY k 10", "15"), ("exists k", "1"),
("SET k v PX 5", "ERR syntax error"), ("SET k v EX x", "ERR value is not an integer or out of range"),
("COMMIT", "ERR no transaction"), ("RESTORE nope", "ERR no such snapshot 'nope'"),
(" ", "ERR empty command"), ("DEL k extra", "ERR wrong number of arguments for 'del'"),
("DEL k", "1"), ("DEL k", "0"), ("TTL k", "-2"),
]
for line, want in cases:
self.assertEqual(run(sess, line), want, line)
class ModelTest(unittest.TestCase):
"""Random operations against a naive model: a stack of full dict copies."""
def test_matches_naive_model(self):
rng = random.Random(42)
s, _ = fresh()
model = [{}]
keys, values = ["a", "b", "c", "d"], ["1", "2", "x"]
for _ in range(5_000):
op = rng.choice(["set", "set", "del", "incr", "begin", "rollback", "commit"])
k = rng.choice(keys)
if op == "set":
v = rng.choice(values)
s.set(k, v)
model[-1][k] = v
elif op == "del":
self.assertEqual(s.delete(k), k in model[-1])
model[-1].pop(k, None)
elif op == "incr":
cur = model[-1].get(k, "0")
if cur.lstrip("-").isdigit():
model[-1][k] = str(s.incr(k))
else:
self.assertRaises(KvError, s.incr, k)
elif op == "begin":
s.begin()
model.append(dict(model[-1]))
elif len(model) > 1:
if op == "rollback":
s.rollback()
model.pop()
else:
s.commit()
top = model.pop()
model[-1] = top
for key in keys:
self.assertEqual(s.get(key), model[-1].get(key))
for v in values:
self.assertEqual(s.count(v), sum(1 for x in model[-1].values() if x == v))
s.check_invariants()
if __name__ == "__main__":
unittest.main()
// file: kv.test.ts (run with: npx tsx --test kv.test.ts)
import { test } from "node:test";
import assert from "node:assert/strict";
import { KvError, KvStore, LazyOnly, ManualClock, SamplingExpiry, Session, mulberry32, run } from "./kv";
const fresh = () => {
const clock = new ManualClock();
return { clock, s: new KvStore(clock, new LazyOnly()) };
};
test("ttl deadline is exclusive and the read removes the key", () => {
const { clock, s } = fresh();
s.set("k", "v", 50);
clock.advance(49);
assert.equal(s.get("k"), "v");
clock.advance(1);
assert.equal(s.get("k"), null);
assert.equal(s.size, 0);
});
test("set clears ttl, incr keeps it", () => {
const { s } = fresh();
s.set("n", "1", 100);
s.incr("n");
assert.equal(s.ttlMs("n"), 100);
s.set("n", "5");
assert.equal(s.ttlMs("n"), -1);
assert.equal(s.ttlMs("missing"), -2);
});
test("incr is exact at 64 bits and rejects junk", () => {
const { s } = fresh();
s.set("big", "9007199254740993"); // 2^53 + 1: a plain number would round this
assert.equal(s.incr("big"), 9007199254740994n);
for (const bad of ["abc", "1.5", " 7", "+7", "1e3", ""]) {
s.set("k", bad);
assert.throws(() => s.incr("k"), KvError);
}
s.set("k", "9223372036854775807");
assert.throws(() => s.incr("k"), KvError);
assert.equal(s.get("k"), "9223372036854775807");
});
test("rollback discards only the top layer, outer rollback undoes inner commit", () => {
const { s } = fresh();
s.set("a", "1");
s.begin();
s.set("a", "2");
s.begin();
s.set("a", "3");
s.rollback();
assert.equal(s.get("a"), "2");
s.begin();
s.set("x", "inner");
s.commit();
s.rollback();
assert.deepEqual([s.get("a"), s.get("x")], ["1", null]);
assert.throws(() => s.commit(), KvError);
});
test("count follows writes, expiry and rollback", () => {
const { clock, s } = fresh();
s.set("a", "v");
s.set("b", "v", 5);
assert.equal(s.count("v"), 2);
clock.advance(5);
assert.equal(s.count("v"), 1);
s.begin();
s.delete("a");
assert.equal(s.count("v"), 0);
s.rollback();
assert.equal(s.count("v"), 1);
s.checkInvariants();
});
test("snapshot holds committed state only and restore keeps absolute deadlines", () => {
const { clock, s } = fresh();
s.set("a", "1", 1000);
s.begin();
s.set("b", "2");
const snap = s.snapshot();
s.commit();
clock.advance(50);
s.restore(snap);
assert.deepEqual([s.get("a"), s.get("b"), s.ttlMs("a")], ["1", null, 950]);
s.begin();
assert.throws(() => s.restore(snap), KvError);
});
test("sampling expiry never touches persistent keys", () => {
const clock = new ManualClock();
const s = new KvStore(clock, new SamplingExpiry(mulberry32(1)));
for (let i = 0; i < 300; i++) {
s.set(`t${i}`, "x", 10);
s.set(`p${i}`, "y");
}
clock.advance(10);
while (s.volatileCount() > 0) s.activeExpireCycle();
assert.equal(s.size, 300);
assert.equal(s.count("y"), 300);
s.checkInvariants();
});
test("parser replies", () => {
const sess = new Session(fresh().s);
const cases: [string, string][] = [
["set k 5", "OK"], ["INCRBY k 10", "15"], ["SET k v PX 5", "ERR syntax error"],
["COMMIT", "ERR no transaction"], [" ", "ERR empty command"], ["toString", "ERR unknown command 'toString'"],
["DEL k extra", "ERR wrong number of arguments for 'del'"], ["DEL k", "1"], ["TTL k", "-2"],
];
for (const [line, want] of cases) assert.equal(run(sess, line), want, line);
});
test("random operations match a naive model", () => {
const rng = mulberry32(42);
const pick = <T,>(xs: T[]) => xs[Math.floor(rng() * xs.length)];
const { s } = fresh();
const model: Map<string, string>[] = [new Map()];
const keys = ["a", "b", "c", "d"];
const values = ["1", "2", "x"];
for (let i = 0; i < 5_000; i++) {
const op = pick(["set", "set", "del", "incr", "begin", "rollback", "commit"]);
const k = pick(keys);
const top = model.at(-1)!;
if (op === "set") {
const v = pick(values);
s.set(k, v);
top.set(k, v);
} else if (op === "del") {
assert.equal(s.delete(k), top.has(k));
top.delete(k);
} else if (op === "incr") {
const cur = top.get(k) ?? "0";
if (/^-?[0-9]+$/.test(cur)) top.set(k, s.incr(k).toString());
else assert.throws(() => s.incr(k), KvError);
} else if (op === "begin") {
s.begin();
model.push(new Map(top));
} else if (model.length > 1) {
if (op === "rollback") {
s.rollback();
model.pop();
} else {
s.commit();
const done = model.pop()!;
model[model.length - 1] = done;
}
}
const now = model.at(-1)!;
for (const key of keys) assert.equal(s.get(key), now.get(key) ?? null);
for (const v of values) assert.equal(s.count(v), [...now.values()].filter((x) => x === v).length);
}
s.checkInvariants();
});
10. Common mistakes
- Updating indexes in each command handler.
SetCmdupdates the value index,Delupdates it, and thenROLLBACKand expiry forget to. Put every index update in oneapplymethod that every path calls. - Logging after writing. If
writeapplies the new entry first and records the before-image second, it records the new value as the old one, and rollback becomes a no-op. Record first, then apply. - Logging on every write instead of the first. The second
SET ain a layer overwrites the before-image with an intermediate value, and rollback restores the wrong state. Record once per key per layer. - Letting the child's image win on commit. The parent's image is older, and it's the one an outer rollback needs. Watch out for
putIfAbsentandsetdefaulton maps whose values can be null orNone. Python'ssetdefaultis fine here, because it checks the key and not the value, but Java'sputIfAbsentisn't. COMMITthat closes every level when the spec says one, or the reverse. Both exist in the wild. Ask, then implement what you were told.- Undoing expiry on rollback. If expiry goes through the logged write path, a rollback resurrects expired keys. Expiry is physical, not transactional.
- Restoring an expired before-image. Restoring an image whose deadline has passed puts a dead entry back into the map and the index. Check the deadline at restore time.
- Counting expired keys. An O(1) counter per value can't see expiry. Either reap the matching keys first, or document that the count is approximate. Never return a count that disagrees with
GETwithout saying so. - Comparing with
>instead of>=at the deadline, or the other way round, without a test. Choose a boundary and pin it with a test. - Reading the system clock directly. You then test TTL with
sleep(1.1), which is slow and flaky. Inject the clock. For in-process deadlines, use a monotonic source (System.nanoTime,time.monotonic,performance.now), because wall-clock time can jump backwards. - Lazy expiry only. A write-once key with a TTL that nobody reads again never leaves memory. Active expiry is not optional in a long-running store.
- Active expiry that scans everything under the lock. With ten million TTL keys, a full scan every 100 ms stalls every client. Bound the work per cycle.
- Shallow-copying mutable entries into a snapshot. If entries were mutable, a later
INCRwould change the snapshot too. Make entries immutable, or deep-copy. - Snapshotting uncommitted state. With write-through, the live map contains the open transaction's writes. Peel the layers off the copy.
- Lenient integer parsing.
int(" 7")in Python andLong.parseLong("+7")in Java succeed. Validate with an explicit pattern so that behaviour doesn't depend on the language. - A parser that crashes the driver.
split()[1]on"GET"throws an index error. Check arity in one place and turn client errors intoERRreplies. - A read-write lock with
getunder the read lock. Lazy expiry makesgeta write. - Over-patterning. A
CommandFactoryProvider, aTransactionManagersingleton, aValueIndexObserverand an abstractAbstractCommanddon't make this better. Command, Strategy and Memento each solve a problem the requirements actually state. Stop there.
11. Interview follow-ups
"What's the complexity of each operation?"
get, set, delete, exists, incr, expire, persist and ttl are O(1) expected, plus O(1) to log a before-image inside a transaction. count(v) is O(k), where k is the number of keys holding v, because it reaps expired ones as it goes. begin is O(1). rollback and commit are O(keys touched in the layer). snapshot is O(n + total keys in open layers). restore is O(n + snapshot size). An active expiry cycle is O(1), bounded by rounds × sample size.
"How much memory per key?" One map entry for the data, one membership in a value-index set, and, for keys with a TTL, one slot in the volatile array plus a position-map entry. On the JVM that's roughly 100 to 200 bytes of overhead per key before the key and value strings themselves. Inside a transaction, add one layer entry per touched key. Redis spends real engineering effort on compact encodings (small hashes stored as flat arrays, shared integer objects) precisely because this overhead dominates for small values.
"Why not just copy the whole map on BEGIN?"
It's correct and simple, and it's exactly what the naive model in the tests does. But BEGIN becomes O(n) and memory doubles per level, so a nested transaction on a million-key store copies millions of entries to change one. The undo layer costs O(1) at BEGIN and O(changes) afterwards. It's worth mentioning as the "obviously correct" baseline you test against.
"A transaction sets the same key a thousand times. How big is the undo log?" One entry. Only the first write per key per layer is logged. That's the main advantage of before-images over a per-command undo list.
"COUNT must be O(1). What changes?"
Keep a counter per value and accept one of two compromises. Either the count includes expired keys that haven't been reaped yet (document it as approximate), or you need precise expiry, such as a timer wheel or a deadline heap, run before every count, so no expired key is ever still counted. A third option keeps a separate counter for keys without a TTL (always exact) and only does the O(k) walk over the TTL keys with that value.
"What happens if the clock goes backwards?" With a monotonic clock, it can't. With wall-clock time, a backwards jump makes expired keys live again (if they haven't been reaped yet) and extends TTLs. Deadlines are stored as absolute times on the store's own clock, which is why the clock is injected and should be monotonic. If TTLs must survive a restart, as with Redis persistence, they have to be stored as wall-clock deadlines. Then you accept the jump risk and rely on NTP slewing rather than stepping the clock.
"Your snapshot is O(n). Make it O(1)."
Use a persistent (immutable, structurally shared) map, such as a hash array mapped trie. A snapshot is then a pointer to the current root, and writes copy only the path from the root to the changed leaf, O(log32 n). Redis gets the same effect at the operating-system level: BGSAVE forks the process, and copy-on-write pages give the child a frozen view while the parent keeps serving.
"How would you persist this?" Two classic answers, often combined. An append-only log of the write commands (the Command objects serialise naturally) is replayed at startup. Periodic snapshots bound the replay time. Log only committed changes: buffer a transaction's commands and append them at the outermost commit, or log a commit marker and skip unterminated transactions during replay. That's the write-ahead log idea, and it moves the problem into the database-internals territory of the high-level key-value store.
"Two clients, one store. What isolation do you give them?"
As written, none: write-through means dirty reads. The concurrency section covers the three fixes: serialise transactions with a global lock, queue commands like Redis MULTI/EXEC, or keep per-client overlays with version-checked commit. Name the isolation level you get from each. With a global lock it's serializable. Queued execution is serializable but can't read its own writes. The overlay gives per-key optimistic validation that prevents lost updates. Whether it prevents write skew depends on whether reads are validated too, and in the sketch they are.
"How does the sampling expiry behave when 90% of TTL keys are expired?" Each round finds that most of its sample is expired, so it keeps going, up to 16 rounds (320 reaps) per cycle. At ten cycles a second, that's 3,200 reaps per second. If keys expire faster than that, memory grows, and you either raise the cap or run cycles more often. Redis also runs extra short "fast" cycles when the regular ones fall behind. A test can pin the bound, as the demos do by asserting each cycle reaps at most 320.
"Where would you add metrics?"
apply already receives a cause. Counting by cause gives writes, expirations, evictions, undos and restores for free. expiredTotal in the listings is one such counter. Add hit and miss counts in live, plus the layer depth and the keys per layer for spotting runaway transactions.
"Is KvStore doing too much?"
It owns the data, two indexes, the layers, the lock and the expiry trigger. Each of those could be its own class, but they must change together on every write. Separate classes would need a coordinating method anyway, and that method is apply. A good split is the one the code already has: the store keeps the state that must stay consistent, while strategies, commands, the parser and the snapshot memento live outside it, because they vary independently. That's the cohesion argument from Cohesion, Coupling and the Law of Demeter.
Related
- Command, Strategy, Memento and Observer: the four patterns on this page, each in depth.
- Design an LRU / LFU Cache: the eviction structure behind extension A, and TTL from the cache side.
- Design a Rate Limiter (LLD): another case study built around an injected clock.
- Machine Coding Rounds: how to pace and structure a 90-minute build like this one.
- Thread-Safe Class Design and Concurrency Patterns in LLD: lock granularity and striping in more depth.
- Design a Key-Value Store: the distributed version, with partitioning, replication and consistency.