Design a Key-Value Store

1Clarifying the requirements#

Agree on what you are building before drawing a single box. The most common way to fail this one is to build DynamoDB when the interviewer wanted Redis, or the reverse. Here is how I pin it down.

Candidate: When you say key-value store, do you mean something single-node like an embedded cache, or a distributed service that other teams call over the network?

Interviewer: Distributed. Assume it spans many machines and multiple datacenters eventually.

Candidate: Got it. What is the shape of the values? Small opaque blobs, or do we need rich types and queries?

Interviewer: Opaque blobs. No secondary indexes, no range scans across keys. Pure point lookups by key.

Candidate: And on consistency: if I write a key and immediately read it, do I have to see my write? Or can we tolerate reading a slightly stale value for a moment?

Interviewer: Good question. We want high availability above all. Eventual consistency is acceptable, but I want you to make the trade-off explicit and tunable.

Candidate: Last one. What is the value size ceiling, and is there a TTL concept?

Interviewer: Values up to about 1 MB. TTL is optional but nice to have.

What those answers just told me:

• "High availability above all" plus "make it tunable" is the interviewer handing me the thesis: this is a Dynamo-style AP system, not a Spanner-style CP one.
• "Opaque blobs, point lookups only" means no query engine, no secondary indexes, so I can keep the storage layer simple and spend my time on replication and consistency.
• The interview is about quorums and conflict resolution, not about CRUD plumbing.

Functional requirements

• get(key) returns the value or a not-found.
• put(key, value) writes or overwrites a value, with optional TTL.
• delete(key) removes a key.
• Values are opaque blobs up to 1 MB.
• No range queries, no joins, no secondary indexes.

Non-functional requirements

• Highly available. The store answers even during node and datacenter failures.
• Low latency. Single-digit millisecond reads and writes at p99.
• Horizontally scalable. Add nodes, get more capacity, no downtime.
• Tunable consistency. Callers choose how strict they want to be, per request.
• Durable. An acknowledged write is not silently lost.

2Back-of-the-envelope estimation#

Size it so the decisions have numbers behind them, not vibes. Two numbers decide the whole architecture, and I will flag them when I reach them.

Users and traffic.

• 200 million daily active users, each touching the store about 50 times a day (sessions, preferences, flags, cached objects).
• That is 10 billion operations a day.

10,000,000,000 ops / 86,400 sec ≈ 115,000 ops/sec average

• Traffic is spiky, so plan for 3x peak: roughly 350,000 ops/sec.
• Read-heavy like most stores, call it a 9:1 split.

Reads:  ~315,000 QPS
Writes:  ~35,000 QPS

Storage.

• Say 50 billion keys. Average value about 10 KB (most small, a few near 1 MB), plus ~100 bytes of key and metadata.

50,000,000,000 keys × ~10.1 KB ≈ 500 TB of logical data

• Replicate 3x for durability and availability: 1.5 PB raw before compression.
• With a 2:1 compression ratio on real blobs, about 750 TB on disk.

Bandwidth (where the network actually gets hot).

35,000 writes/sec × 10 KB ≈ 350 MB/sec ingest

• Multiply by replication factor 3 for cross-node traffic, and you are pushing north of 1 GB/sec on the internal network at peak.
• That tells me the replication path, not the client path, is where the network burns. I come back to it in the trade-offs.

The two numbers that drive the design.

• 315,000 read QPS at single-digit-millisecond p99. This forbids spinning disk on the read path (a seek is ~10 ms and blows the whole budget alone) and forbids a cold cross-datacenter hop on a normal read (tens of milliseconds by itself). Every normal read serves from memory or local SSD, in the local datacenter.
• 500 TB. It does not fit on one machine, not close, so partitioning is mandatory, not a nice-to-have.

3Core APIs#

Keep the surface tiny. A small API is a feature here, not laziness: fewer operations means fewer consistency corner cases to reason about.

GET /v1/keys/{key}?consistency=one
200 OK
{ "key": "user:42:prefs", "value": "<base64 blob>", "version": "v17-node3" }

PUT /v1/keys/{key}
{ "value": "<base64 blob>", "ttl_seconds": 3600, "consistency": "quorum" }
200 OK
{ "version": "v18-node3" }

DELETE /v1/keys/{key}?consistency=quorum
204 No Content

The consistency param is the knob the interviewer asked for.

• one acks after a single replica responds (fastest, weakest).
• quorum needs a majority to agree (slower, stronger).
• all waits for every replica.
• Same store, same code path, caller's call: a session cache sends one and eats the odd stale read for latency, a billing flag sends quorum and pays for correctness.

The version field is not cosmetic.

• It is how clients and the server detect conflicting writes.
• It carries the vector clock the server uses to decide which value is newer. More on that in the deep dive.

4High-level design#

The spine is simple, so draw it fast:

• Clients hit a stateless coordinator layer.
• The coordinator figures out which nodes own the key and talks to them.
• Storage nodes hold the data, replicate among themselves, and gossip about who is alive.

No central master.

• No single node owns metadata and becomes a bottleneck or a single point of failure.
• Every node knows the ring topology through gossip, so any node can coordinate any request.
• The moment you add a master that must be consulted on every write, you have handed a partition the power to freeze the whole cluster. That is the opposite of what the interviewer asked for.

The coordinator is stateless.

• It is just routing logic: read the ring, forward to the right replicas, collect responses, apply the consistency rule, answer.
• Run hundreds behind the load balancer and lose any of them with no data loss.
• At 350K ops/sec this layer scales by adding boxes, nothing clever.

Storage nodes own ranges of the keyspace via consistent hashing.

• Each node owns a slice of the ring plus replicas of its neighbors' slices.
• When a node joins or leaves, only the keys near it on the ring move. That is the whole point: adding a node does not reshuffle the dataset.

Under the hood, each node runs an LSM-tree engine.

• Writes go to an in-memory memtable plus an append-only commit log, then flush to sorted immutable files on SSD.
• Fast writes and good point-lookup reads, which is exactly our workload.
• The append-only write path is what lets one node absorb its share of 35K writes/sec without random-write disk thrash.

5Data model#

No schema in the relational sense, but each node tracks structure per key. Here is a stored record internally.

And the ring metadata every node carries, synced via gossip.

Two fields decide interviews, so call them out before you are asked.

• tombstone. In an eventually consistent system you cannot just erase on delete. If node C was offline during the delete and you physically removed the key on A and B, then C comes back, gossips the old value, and resurrects the dead key. The tombstone is a gravestone that outlives the downtime, then gets garbage-collected during compaction after a grace window.
• vector_clock. The real workhorse for consistency, so it gets its own deep dive below.

Name both of these before I ask and I know you have actually operated one of these systems.

6Deep dives#

6.1 Partitioning with consistent hashing and virtual nodes#

Naive hashing is a trap.

• node = hash(key) % N remaps nearly every key when N changes by one.
• At our scale, adding one machine would move hundreds of TB. Unacceptable.

Consistent hashing fixes it.

• Picture the hash output as a ring from 0 to 2^128. Each node gets a position.
• A key hashes to a point, then you walk clockwise to the first node: that node owns it.
• Add a node and only the keys between it and its predecessor move. One slice, not everything.

Plain consistent hashing has two problems: uneven load, and a hot neighbor inheriting everything when a node dies. Virtual nodes fix both.

• Each physical machine takes many positions on the ring, say 256.
• Load now spreads evenly across the cluster.
• When a machine dies, its 256 slices get absorbed by 256 different neighbors instead of dumping onto one.
• That last part is the operational win people miss: without vnodes, losing one box doubles the load on exactly one other box and your outage cascades. With 256 vnodes, the dead box's load fans out and nobody notices.

Replica placement has one rule you must say out loud.

• Replicas are the next N distinct physical nodes walking clockwise.
• Skip vnodes that land on a physical machine already chosen, and prefer spreading across datacenters.
• So a replica set never ends up as three vnodes on the same box or the same rack. Lose a rack, you still have copies.
• Skipping that rule is the quiet bug that turns a rack-power event into a data-loss event.

6.2 Tunable consistency with quorums#

This is the heart of the Hard version and the single deep dive I most want to hear nailed. We promised eventual consistency but a tunable knob. Quorum math delivers it.

The rule. Let N be the replication factor (3 for us), W the write quorum, R the read quorum.

W + R > N

Strong reads: W=2, R=2, N=3.

• A write is not acked until 2 of 3 replicas confirm. A read collects answers from 2 of 3.
• Because 2 + 2 is greater than 3, any read quorum and any write quorum must overlap on at least one node.
• So a read is guaranteed to touch at least one replica holding the newest value. Its higher version wins.
• Strong consistency, and we still survive one dead replica.

Raw speed: W=1, R=1.

• Writes ack instantly, reads return the first answer.
• Now W+R is not greater than N, so a read can miss a fresh write.
• That is the consistency=one path, chosen by the caller with eyes open.

D catches up through two mechanisms.

• Read repair. A read that notices D is stale pushes the fresh value to it inline, so the system self-heals on the hot path at essentially no extra cost.
• Anti-entropy. A background process where nodes compare Merkle trees of their key ranges and sync only the differing branches.
• Merkle trees matter because you cannot compare billions of keys one by one. You compare tree-root hashes and only descend into subtrees whose hashes disagree.
• A full range with one divergent key costs a logarithmic walk, not a full scan. That is what makes repair affordable at 50 billion keys.

6.3 Conflict resolution and the resurrection problem#

The setup. With W=1, two clients write the same key to different replicas during a partition. Two divergent values, no global order. Who wins?

Wall-clock timestamps alone lie.

• Clocks drift across machines.
• Last-write-wins by timestamp silently drops data when two writes race: the one with the slightly slower clock just vanishes.

So each value carries a vector clock: a map of node-id to a counter.

• Node A's write makes it {A:1}. A later causally-dependent write becomes {A:2}.
• Two concurrent writes on a partition become {A:1} and {B:1}, which are not comparable, because neither map is element-wise greater than the other.
• The system sees that neither clock descends from the other and knows it has a genuine conflict, not a stale copy.

What then? Two honest options.

• Last-write-wins by timestamp. Simple but lossy, fine for caches and preferences where losing one racing write costs nothing.
• Siblings. Hand both versions back to the client and let application logic merge them, the way a shopping cart unions items so nothing a user added disappears.
• I default to last-write-wins for a general store and offer sibling mode for callers who opt in, because most teams do not want to write merge logic and take the simpler contract every time.

The resurrection problem closes here, cleanly, thanks to vector clocks.

• A delete produces a tombstone with its own vector clock.
• When a recovering node gossips its stale live value, that value's clock is an ancestor of the tombstone's clock, so the tombstone correctly wins and the key stays dead.
• Garbage-collect the tombstone only after a grace window longer than the maximum expected node downtime. Collecting it early is exactly how a deleted key crawls back out of the grave.

7Bottlenecks and trade-offs#

Hot keys are the one thing consistent hashing does nothing for.

• A viral post's view counter, a global feature flag read by every request: all its traffic lands on the same 3 replicas and melts them.
• Adding nodes does not help, because the hash still points those reads at the same three boxes.
• My defenses, in the order I would reach for them:
• Cache hot keys in the coordinator with a short TTL, so repeated reads never reach storage. Cheapest, so first.
• Detect hotness by tracking per-key request rates and add extra ephemeral replicas for that single key, so its read load fans out.
• For write-hot counters, shard the key into key#0 through key#9 across different ring positions and sum on read, turning one melting-hot key into ten warm ones.
• Each defense trades a little consistency or complexity for survival.

The CAP trade-off, stated plainly.

• During a partition we chose availability. A partitioned minority still serves reads and writes, and those diverge from the majority.
• We accept temporary inconsistency and repair it with read repair and anti-entropy.
• If the interviewer flips the requirement to strong consistency during partitions, I move to a consensus protocol like Raft per partition. That buys linearizable reads and writes but costs availability: a partition with no quorum refuses writes rather than risk divergence.
• You cannot have both at once. I let the caller choose at the keyspace level, so the session cache stays AP and the billing ledger goes CP.

Tail latency from the slowest replica.

• With R=2 we wait for the second-fastest of three, fine on a healthy day.
• But a single slow node drags p99 everywhere it is a replica, and one sick machine out of thousands can wreck a latency SLA.
• Send the read to all N replicas, answer as soon as R respond, cancel the laggard, and run speculative retries to a different replica past a threshold of a few milliseconds.
• Cheap insurance, and it is the difference between a clean p99 and a bimodal one.

Compaction and write amplification.

• LSM-trees rewrite data during compaction. At 35K writes/sec that is real disk and CPU, and a badly timed compaction spikes latency for every read sharing that node.
• Rate-limit compaction, run it off-peak where possible, and watch the classic failure where deletes and overwrites bloat storage until compaction catches up and the disk fills faster than you expected.

Cross-datacenter replication (where the estimation warned the network gets hot).

• Synchronous cross-DC writes add tens of milliseconds and kill the single-digit-millisecond target.
• So cross-DC replication is asynchronous: ack from the local DC quorum, ship to remote DCs in the background.
• The trade-off: a remote DC can lag, and a full-DC failure right after a write can lose the last few seconds of data.
• For most workloads that is acceptable. For the few keys that cannot tolerate it, offer a synchronous all-dc level and let the caller pay the latency they are asking for.

Always route the consistency choice to the caller, not to your own taste.

8Summary#

The decisions that matter:

• Consistent hashing plus virtual nodes. Adding capacity moves one slice, not the world, and a dead node's load spreads across many neighbors instead of crushing one.
• Masterless, gossip-synced. Any node can coordinate and no single failure takes us down, which is the entire availability story.
• LSM-trees on SSD. Fast writes and point reads, which is what keeps us inside the 315K-read-QPS-at-millisecond-p99 budget.
• Tunable consistency backed by quorum math. W + R greater than N gives strong reads, W=R=1 gives raw speed, caller chooses per request.
• Vector clocks, not naked timestamps, to detect real conflicts, plus tombstones so deleted keys stay dead.
• Repair in two places: read repair inline on the hot path, Merkle-tree anti-entropy in the background.
• Honest about CAP: we chose availability, we repair after partitions, and we offer a stricter per-keyspace mode for the keys that need it.

For role-specific angles on this problem, see our company-specific system design guides.