Design a key-value store

Scope the requirements

The trap here is reaching for an off-the-shelf database — the question is the database. I want to establish early that this is an AP system in the Dynamo family, because that one decision drives partitioning, replication, conflict handling and the entire failure story.

Functional — what it must do

put(key, value) and get(key) — that is the whole user-facing surface.
Values are small (under 10 KB), but the total dataset is huge and must span many machines.
Consistency is tunable per operation — callers choose between fast and safe.
Nodes can be added or removed with automatic rebalancing, no downtime.
Explicitly cut: range queries, secondary indexes, transactions — this is a hash-addressed store, and saying that out loud keeps the design honest.

Non-functional — the numbers that shape the design

High availability: keep serving reads and writes through node failures and network partitions — we choose AP, eventual consistency.
Latency: single-digit milliseconds for both get and put at the median.
Scale: petabyte-class data, around 1M ops/s, growing without redesign.
Every key replicated to N=3 nodes, ideally across zones, so no single failure loses data.
Durability: an acknowledged write survives the crash of the node that took it.

Say this out loud

Partitions will happen, so I have to pick a side of CAP before I draw anything. I'm choosing availability — this is the Dynamo and Cassandra lineage — which means I owe you a conflict-resolution story and a repair story, and those will be my deep dives.

Back-of-envelope estimates

The numbers here are less about capacity planning and more about proving the shape of the design: no single machine holds the data or the traffic, so partitioning and replication are forced moves, not choices.

Quantity	Estimate	How you got there
Raw dataset	~1 TB	100M keys × 10 KB. Deliberately modest — the design must work the same at 1 PB.
With replication	~3 TB	N=3 copies of everything. Storage triples; that's the price of surviving node loss.
Throughput target	~1M ops/s	Mixed reads and writes; each op touches N=3 replicas, so internal traffic is ~3M ops/s.
Per-node capacity	~100k ops/s	An LSM-backed node saturates around here → ~10 nodes for traffic; run ~30 with vnodes for headroom and rebalancing.
Quorum config	N=3, W=2, R=2	W+R > N means read and write sets overlap on at least one node — reads see the latest acknowledged write.
Latency budget	<10 ms	A quorum op waits for the 2nd-fastest replica, not the slowest — quorums quietly improve tail latency too.

Say this out loud

One terabyte and a million ops a second means roughly ten serving nodes minimum, and every one of them will eventually fail. So the interesting 80% of this design is not the happy path — it's membership, failure detection and repair.

Sketch the API

The API is three verbs. The interesting decision hides in the get response: when replicas disagree, I return all conflicting versions and make the client part of the consistency protocol.

GET/v1/kv/{key}→ { value, context } — or multiple sibling versions plus a context when replicas conflict. Optional ?r= to override the read quorum.

PUT/v1/kv/{key}body: { value, context? }. The context carries the version the client last saw, so the store can order this write against it. Optional ?w= for the write quorum.

DELETE/v1/kv/{key}Writes a tombstone — a versioned marker, not a physical delete. Compaction removes it later.

GET/v1/admin/ringRing state: nodes, vnode token ranges, health as seen by gossip. Ops surface, not user-facing.

Returning sibling versions is the deliberate choice: an AP store cannot always pick a winner, so get can return two values and a context, and the next put with that context resolves the conflict. It pushes complexity onto clients — which is exactly why Cassandra chose last-write-wins instead, and I'll defend that trade-off in the deep dives.
Deletes must be tombstones, not removals — if you physically delete on 2 of 3 replicas, anti-entropy repair will helpfully resurrect the key from the third.

Data model

Two layers of data model: how keys map to nodes across the cluster, and how a single node stores its slice. Both are canonical structures the interviewer expects by name.

hash ring metadata

node → vnode tokens · health · version (gossip-replicated)

Each physical node owns ~100–200 virtual nodes scattered around the ring — even load, and rebalancing moves small slivers, not half the keyspace.

commit log + memtable

append-only WAL on disk · sorted in-memory map

Every write hits the log first (durability), then the memtable (speed). Sequential disk writes are why LSM stores take writes so fast.

SSTables

immutable sorted files · per-file Bloom filter · compaction merges

Memtable flushes become SSTables; reads check memtable, then Bloom filters skip files that definitely lack the key.

version metadata

key → vector clock [(node, counter)...]

Lets the store distinguish "newer" from "concurrent" — the difference between overwriting and conflicting.

The database call

There is no database to pick — this question is the database, and I'm building each node as an LSM tree because the workload is write-heavy point ops, exactly what log-structured storage is for. The escape hatch is the consistency requirement: if the interviewer flips it to "strongly consistent, no stale reads ever", I stop building Dynamo and run a consensus group — Raft per shard, the etcd and Spanner lineage — accepting lower availability under partition and higher write latency.

High-level design

Decentralised by design: every node is a peer, any node can coordinate any request, and there is no master to fail. The synchronous path is coordinator-to-replicas; everything that keeps the cluster healthy — gossip, hinted handoff, anti-entropy — runs in the background.

no master anywhere — the coordinator is whichever node the client hit. notice the async lane is entirely about failure: detection, temporary cover, permanent repair.

Write: the ring-aware client sends put to any node, which acts as coordinator — it hashes the key onto the ring and forwards to the N=3 replicas that own that range.
The coordinator acknowledges the client after W=2 replicas confirm — the write is durable on two machines before anyone hears "OK".
Read: coordinator queries the replicas, waits for R=2 responses, compares vector clocks — returns the newest version, or all siblings if the clocks say the versions are concurrent.
If a replica is down, the coordinator writes to the next healthy node with a hint attached (sloppy quorum); the hint replays to the real owner when it recovers.
In the background, gossip spreads membership and failure state peer-to-peer, and anti-entropy jobs compare Merkle trees between replicas to find and repair silent divergence.

Deep dives — where the interview is won

Phase 01

Quorums are a dial, not a setting: N, W and R per operation

With N=3 replicas, the caller picks W (writes acknowledged) and R (reads consulted). W+R > N guarantees the read set overlaps the write set on at least one node, so a read always sees the latest acknowledged write — that's the closest an AP store gets to strong consistency. W=2, R=2 is the balanced default. Drop to W=1 for fire-hose ingestion where losing an occasional write is acceptable; R=1 for latency-critical reads that tolerate staleness.

The point interviewers want to hear: this is a per-operation trade, not a cluster config. The same store serves a shopping cart at W=2 R=2 and a metrics firehose at W=1 R=1 simultaneously. And name the latency subtlety — a quorum op returns on the 2nd-fastest of 3 replicas, so it clips the tail that a wait-for-all scheme would suffer.

N replicas, W writes must ack, R reads must ack. R+W>N gives read-your-writes.

Trade-offW+R > N buys read-your-writes at the cost of every operation paying for the 2nd-fastest replica; W+R ≤ N buys speed and availability at the cost of reads that can be stale with no bound you can promise.

Phase 02

Vector clocks detect conflicts; last-write-wins quietly eats them

Under a partition, two clients can write the same key on different sides — both writes are acknowledged, and neither is "newer". A vector clock per key ([(node, counter)...]) makes this detectable: if one clock dominates the other, overwrite safely; if neither dominates, the writes were concurrent and the store keeps both siblings and returns them on the next read for the client to merge. That's how Dynamo kept every item anyone added to a shopping cart.

Last-write-wins is the pragmatic alternative Cassandra ships: timestamp every write, highest timestamp wins, conflicts silently resolved. It's simpler for clients and operators — and it destroys data under concurrency, because the "loser" write vanishes without a trace, and it trusts clock synchronisation across machines. I'd offer LWW as the default and vector clocks only where a lost write is a lost sale.

each write carries a vector clock. divergent clocks surface as siblings; client resolves.

Trade-offVector clocks preserve every concurrent write but push merge logic into every client; LWW keeps clients trivial and silently discards one of two concurrent writes — pick per key-space, not per cluster.

Phase 03

Failure handling is three mechanisms, one per failure duration

Detection first: no central health-checker — nodes gossip, exchanging heartbeat counters with random peers a few times a second, so "node C is down" propagates cluster-wide in seconds with no single point of failure. Temporary failure: a sloppy quorum writes to the next healthy node on the ring with a hint naming the real owner; when the owner returns, hints replay and the quorum was never blocked. A crashed node costs nothing but a short replay.

Permanent divergence — missed hints, dropped messages, a node restored from old disk — is caught by anti-entropy: each replica builds a Merkle tree over its key range, and two replicas compare root hashes downward, transferring only the subtrees that differ. Comparing terabytes costs kilobytes of hash exchange. This trio — gossip, hinted handoff, Merkle repair — is the part interviewers push hardest, and the part most candidates never reach.

hinted handoff (seconds), read repair (minutes), merkle-tree anti-entropy (hours).

Trade-offSloppy quorums keep writes available through node failure but weaken the overlap guarantee — during the failure window, W=2 might be two stand-ins, and a read can miss the write until hints replay.

Phase 04

The node itself: an LSM tree, because writes never wait for disk seeks

Per-node write path: append to the commit log (sequential I/O, durable), insert into the memtable (sorted, in memory), acknowledge. When the memtable fills, flush it to an immutable sorted SSTable. Writes never touch existing files, never seek — which is why this design takes 100k ops/s per node on ordinary hardware.

The read path pays for that: a key could live in the memtable or any SSTable, so each SSTable carries a Bloom filter that answers "definitely not here" in memory, and reads skip almost every file. Background compaction merges SSTables, drops overwritten versions and finally purges tombstones. Compaction is also the operational cost — it competes with foreground traffic for I/O, and unthrottled compaction is a classic production incident.

writes append to memtable + WAL. sstables flush; background compaction merges.

Trade-offLSM trees trade read amplification and background compaction I/O for near-optimal write throughput — the right trade here, and the opposite of a B-tree, which is what I'd want under a read-mostly, range-scan workload.

Follow-ups you should expect

Why virtual nodes instead of one ring position per machine?

Three reasons. Load evens out — with one token per node, random placement leaves some nodes owning big arcs of the ring. Rebalancing spreads — when a node dies, its 150 vnodes are inherited by 150 different owners instead of dumping its whole range on one neighbour. And heterogeneous hardware is easy — a box with twice the capacity takes twice the vnodes.

One key gets extremely hot — a celebrity's cart. What happens?

Consistent hashing spreads keys, not popularity — all traffic for that key lands on its N replicas. Mitigations in order: cache it in front of the store, raise R=1 reads served by all N replicas, and for write-hot keys salt the key into k sub-keys written randomly and merged on read. The honest answer is that key design is the real fix; the store can only soften it.

What changes if I need strong consistency?

The architecture, fundamentally — not a config flag. Replace leaderless quorum replication with a consensus group per shard, Raft or Paxos, where a leader orders all writes and a majority commit makes them visible. That's etcd or Spanner territory: you gain linearizability and lose availability on the minority side of a partition, plus a round-trip of write latency. Saying "I'd turn up W and R" is the wrong answer — sloppy quorums and failure windows mean quorum overlap never equals linearizability.

How does cross-datacenter replication work?

Place replicas topology-aware — for N=3, three zones or DCs, so no single site failure loses quorum. Then offer per-operation locality: LOCAL_QUORUM acknowledges within the caller's DC in milliseconds and replicates cross-DC asynchronously, accepting that a DC failover can lose the async tail. Global quorums make every write pay an inter-DC round trip — tens of milliseconds — which almost no workload accepts.

Why not consistent-hash with mod-N?

Because hash(key) mod N remaps nearly every key when N changes — adding one node to ten reshuffles ~90% of the data, a cluster-wide rebalance storm for a routine scaling event. The ring moves only the keys in the slivers the new node takes over — roughly 1/N of the data, from many donors in parallel.

Where candidates lose the room

Answering "I'd use DynamoDB" — the question asks you to build the database, and reaching for a managed product reads as not recognising what's being asked.
Designing partitioning and replication before positioning on CAP — every later decision depends on AP vs CP, and interviewers notice when it was never chosen, only implied.
Hashing with mod-N — the mass-remapping problem is the exact reason consistent hashing exists, and it's often the first probe.
No conflict story: acknowledging that two sides of a partition both accept writes, then never saying what a reader sees afterwards.
Stopping at the happy path — gossip, hinted handoff and Merkle repair are where senior candidates separate from the pack, and most run out of time before reaching them.