Distributed key-value store — a full worked answer
The whole thing, start to finish, in the order you would actually say it. Read it to learn the shape of a strong answer — then go and produce one yourself, because reading is not the same skill as producing.
The question
Design a distributed key-value store. Get and put by key, data larger than one machine, survives machines failing, and configurable durability. You are building the database, not choosing one.
Building the storage itself. You are not using a database. You are being asked to design one.
The vocabulary flips from "which store do I pick" to replication, quorums, partition assignment and durability. This is the group where every Tier 2 concept is the answer rather than the context.
Before anything: where is the slack?
How long the system has before a person notices. Ask this before you draw a single box — it decides more of the design than scale does.
The slack here is not in the request path at all: a caller is waiting on every get and every put. All the slack lives in the background work, and the design succeeds by moving as much as possible into it.
Gets and puts have no slack. This store is a dependency of other systems, so its p99 is inside their p99, and being slow makes it useless. That rules out anything requiring wide coordination on the request path.
Everything else has a lot of slack. Repairing a replica that has fallen behind, moving partitions when a machine joins, compacting on-disk files, taking backups, rebuilding a failed node: all of it can take hours, run at low priority, and be interrupted and resumed. The hard rule is that none of it may block a get.
The one place you get to sell slack is durability. "Confirmed when one node has it" is fast and can lose data. "Confirmed when a majority has it" is slower on every write, forever. That is not a failure-time decision. It is a latency cost paid on every write, the "else" half of PACELC, so the design lets the caller choose per operation.
So: Background work is aggressively deprioritised and never on the read path. Durability is a per-request knob rather than a system-wide property, so a session cache and a user record can use the same store with different promises.
Requirements
about 5 minWhy this stage exists: Because the question is deliberately vague, and every box you draw before this is a guess.
Assumptions: get, put and delete by key only. No range scans, no secondary indexes, no transactions across keys. Values up to about a megabyte. A few hundred terabytes total. Running in one region to start, with multi-region as a later question.
The question that changes everything: what is the consistency promise? Strong consistency means a read always sees the last confirmed write, which costs a majority round trip and makes the store unavailable on the minority side of a network split. Eventual consistency means fast local reads and writes, with the caller sometimes seeing stale data. These are two different products. I will assume tunable per request, defaulting to quorum, because that makes the store usable for both a session cache and a user profile.
Second question: do callers need range scans, such as "all keys with this prefix"? That decides partitioning. Hash partitioning spreads load evenly and destroys ranges. Range partitioning keeps neighbours together and invites hot spots. I will assume no range scans, which lets me hash and get even distribution, and I will name what I gave up.
Scope I propose: the data path, meaning partitioning, replication, the write path, the read path, failure handling and rebalancing. Out of scope: a query language, transactions across keys, and secondary indexes, all of which are separate systems built on top.
What an interviewer is ticking off in this stage
- Limited the operations to get, put and delete, and said so explicitly
- Asked about the consistency promise and named it as the biggest decision
- Chose tunable consistency and justified it with two different use cases
- Asked about range scans and tied the answer to hash versus range partitioning
- Named what hash partitioning gives up
Actors and lifecycle
about 6 minWhy this stage exists: Because the happy path is the easy half. The failure branches are where the design actually lives.
Actors: the client, the coordinator node that receives the request, the replica nodes that hold the data, and the system itself, which decides which nodes own a key, when a node is considered dead, when to start moving data, and when a replica has fallen far enough behind to need repair rather than catch-up.
A write's life: received by a coordinator → routed to the N nodes that own the key → appended to each node's write-ahead log and fsynced → applied to the in-memory table → acknowledged once W nodes have confirmed → later flushed to a sorted file on disk → later compacted with other files → eventually replicated to any node that missed it.
Failure branches. At routing: the coordinator's view of who owns the key is stale because membership just changed, so it writes to the wrong node. That is why ownership comes from a small consensus-backed membership service rather than from each node's guess. At acknowledgement: only W-1 nodes responded before the timeout, so the write is not confirmed. But the nodes that did accept it still have it, so a failed write may still be visible later. State that property rather than hide it. At flush: the node crashes with data only in memory. This is what the write-ahead log is for: replay it on restart and nothing confirmed is lost.
The branches the system owns. A node is unreachable for an hour: writes during that window went to the other replicas, so on return it is stale, and it must not serve reads as if it were current until it has caught up. A hinted handoff (another node temporarily holding writes destined for it) lets the write succeed during the outage and be delivered afterwards. The cost: a write held as a hint is not on its real replicas yet, so a quorum read can miss it even when W + R > N. And if it is away long enough that hints have expired, it needs a full repair from a peer rather than a catch-up, which is hours of background work.
The last one: two clients write the same key at the same moment to different coordinators. Both succeed. That is a real conflict. It cannot be prevented cheaply, so something has to decide between the versions, which is the Stage 5 question.
What an interviewer is ticking off in this stage
- Write-ahead log and fsync before acknowledgement: that is what "durable" means
- Ownership comes from a consensus-backed membership service, not from local guesses
- Named that a failed write can still be partially applied and visible
- Hinted handoff so a brief node outage does not fail writes
- A long-absent node needs full repair, not catch-up, and must not serve reads first
- Concurrent writes to one key named as a conflict needing a decision
The lifecycle, drawn
Numbers
about 6 minWhy this stage exists: Because one part of this is hard and the rest is easy, and they look identical until you do the arithmetic.
Assume 300 TB of unique data with a replication factor of 3, so 900 TB stored. At 8 TB usable per node that is about 115 nodes, and I would round up to 150 for headroom, because a cluster running at 90% full cannot absorb a node failure.
Throughput: assume 500,000 operations per second across the cluster. Spread over 150 nodes with a replication factor of 3, each node handles about 10,000 operations a second. That is well within what one machine does, so this is a capacity and coordination problem rather than a per-node performance one.
The latency arithmetic matters more. A local SSD write with fsync is under a millisecond with group commit. Waiting for two of three replicas inside one datacenter adds a round trip, about 0.5 ms, so a quorum write is maybe 2 ms. That is cheap. Across regions it is 80 ms or more, 40 times worse. That gap is why cross-region strong consistency is a product decision rather than a configuration one.
Rebuild time is the number candidates tend to skip, and it decides your replication factor. Restoring 8 TB from peers at 1 Gbit per second takes about 18 hours, and during those 18 hours that key range is down to two copies. If a second node fails in that window you are on one copy, and a third failure loses data. That arithmetic, not habit, is why the replication factor is 3 and not 2.
So the hard part here is failure recovery and membership, not throughput. Each node is barely working. What is hard is agreeing on who owns what while nodes come and go, and staying safe during the 18 hours it takes to rebuild one.
What an interviewer is ticking off in this stage
- Turned data size and replication factor into a node count with headroom
- Showed per-node load is modest, so this is not a throughput problem
- Quantified quorum latency locally and across regions, with the 40x gap
- Calculated rebuild time and used it to justify the replication factor
- Finished the sentence: failure recovery and membership, not throughput
The numbers, drawn
So the hard part is membership and recovery. Each node is barely working; agreeing who owns what while machines come and go, and staying safe for 18 hours at reduced replication, is the design.
High-level design
about 12 minWhy this stage exists: Because now — and only now — you have a reason for every box you are about to draw.
Placement. Consistent hashing with about 150 virtual nodes per physical node decides which N nodes own a key. Virtual nodes are required: with one position each, the arcs are uneven, and losing a machine dumps its entire load on a single neighbour. The N owners are the next N distinct physical nodes clockwise.
Membership lives in a small consensus group (three or five nodes running Raft) holding the ring, the node list and their states. This is what consensus is good for: small, critical, low-volume metadata that everyone must agree on. Application traffic never goes near it. If it is unreachable, existing routing keeps working from cached views; only membership changes stop.
Routing. Any node can act as coordinator. Clients cache the ring and go straight to an owner, and a node that receives a request for a key it does not own forwards it and tells the client to refresh. That saves a hop in the normal case and stays correct when the client is stale.
Inside one node, the part that separates a real answer from a hand-wave. Writes append to a write-ahead log and fsync; that is the durability promise. They also go into a sorted in-memory table. When that table is full it is flushed to disk as an immutable sorted file, and the log up to that point can be discarded. Reads check the memory table first, then the on-disk files newest to oldest. Because there can be many files, each carries a bloom filter so a read can skip a file the key is definitely not in, without touching the disk. That structure is what keeps reads affordable here. Background compaction merges files and drops superseded values; it is "hours of slack" work that must never block a read.
Quorum reads and writes. With N replicas, a write is confirmed when W accept it and a read consults R. If W plus R is greater than N, any read touches at least one node that saw the latest write. Defaults of N=3, W=2, R=2 keep that overlap with one node down. Callers can lower W or R per request when they want speed instead.
Repair. Read repair fixes divergence noticed during a read, cheaply and lazily. Background anti-entropy compares replicas using Merkle trees, so two nodes can find which key ranges differ by exchanging a few hashes rather than every key. That is what makes repairing terabytes practical.
What an interviewer is ticking off in this stage
- Consistent hashing with virtual nodes, and said why one position each fails
- Membership in a small consensus group; application traffic never touches it
- Clients cache the ring; any node can coordinate and forward
- Described the node internals: log, memory table, sorted files, compaction
- Bloom filter per on-disk file, and named what it saves
- Quorum formula stated, with W and R tunable per request
- Merkle trees for anti-entropy, and why hashes beat comparing keys
The architecture, drawn
Deep dive and tradeoffs
about 14 minWhy this stage exists: Because naming what a decision costs is the single clearest signal of seniority there is.
Hard part one: conflicting writes. Two clients write the same key through different coordinators. Both succeed under quorum, and now replicas disagree. The tempting answer is last-write-wins by timestamp, and I would name it as a decision to lose data rather than as conflict resolution. Server clocks drift apart, so the write that happened second can carry the earlier stamp and be discarded silently. That is acceptable for a session blob and unacceptable for anything a user typed. The better answer is version vectors: each replica tracks its own counter, so comparing two versions tells you not just which is newer but whether they are concurrent. Concurrent versions are returned to the client as siblings, and the application resolves them, because only the application knows whether two shopping carts should merge or one should win. Cost: clients must handle siblings, vectors grow with the number of writers and need pruning, and the API is harder to use. I would offer last-write-wins as an opt-in for callers who do not care.
Hard part two: a node fails, hour by hour. Within seconds, failure detection (gossip between nodes plus the membership service) marks it suspect rather than dead, because a brief network blip must not trigger a terabyte-scale data movement. After a grace period it is marked down. Its key ranges are now at two replicas, so reads and writes continue at quorum with no interruption. That is what N=3 buys. Writes destined for it are held as hints by peers. If it returns within the hint window, it replays them and catches up in minutes. If it does not, a replacement is brought in and streams 8 TB from its peers: 18 hours at a deliberately throttled speed, so the rebuild does not degrade live traffic. Throughout, that range is one failure from being down to a single copy, which is why I would prioritise rebuilding ranges that are already degraded and alert on time-spent-under-replicated rather than just on node count. Cost: the throttle trades a longer risk window for stable latency, and where to set it is an operational judgement.
Adding capacity. Adding 50 nodes means each new node takes over arcs of the ring, and the data for those arcs streams from the current owners. Consistent hashing means only about a quarter of the data moves rather than nearly all of it, and virtual nodes mean the source load is spread over every existing machine rather than a few. This runs for many hours at low priority. Ownership transfers only once the new node has the data and has caught up, so there is never a moment where reads go to a node that does not have the key. Cost: the cluster is doing background transfer for days, and its capacity is temporarily reduced.
Backups, separately from replication. Replication does not protect against a client writing garbage to a million keys, because it replicates the garbage too. So snapshots of the sorted files go to object storage. The files are immutable, so incremental backup only has to copy files it has not seen before. I would test restores regularly rather than assume they work.
What an interviewer is ticking off in this stage
- Named last-write-wins as data loss, not conflict resolution
- Version vectors with siblings returned to the application to resolve
- Failure detection with a grace period, so a blip does not move terabytes
- Hinted handoff for brief outages, full stream for long ones
- Rebuild throttled on purpose, and the risk window named
- Alerted on time-spent-under-replicated rather than node count
- Backups separate from replication, because replication copies mistakes
The decision this turns on
- —Trivial to implement, and every read returns one value.
- —Depends on clocks agreeing, and they never agree exactly.
- —The write that happened second can carry the earlier stamp and be discarded.
- —The loss is silent: no error, no log line, nothing to alert on.
- —Fine for disposable values like a session blob or a presence flag.
- —Tells you whether one version is newer, or whether they are concurrent.
- —Concurrent versions are handed to the application, which is the only layer that knows how to merge them.
- —No silent loss: a conflict becomes a decision somebody makes.
- —Vectors grow with the number of writers and need pruning.
- —Clients get a harder API: a read can return more than one value.
And then they push back
A complete answer is where the interview starts, not where it ends. These are the questions this design invites — the interview is decided here far more often than in the diagram.
Half your servers vanish instantly. What is the user impact?
"The load balancer routes around them." That handles routing; it does not handle the fact that the remaining half now takes double the load and may not have the headroom.
"Two separate problems. Routing: health checks remove them within a few seconds, so there is a short window of failed requests for anyone routed to a dead instance — retries with backoff cover that. Capacity: the survivors now take 2x traffic, so if I was running above 50% utilisation, they saturate and I have turned a partial failure into a total one. That is why capacity planning has to assume losing a chunk of the fleet, not just the peak load. Third, the subtle one: if servers held any local state — in-memory caches, sticky sessions, open connections — that is gone, so the survivors face a cold cache and a reconnection surge at the same time as double traffic. That combination is what takes systems down. I would rather run more, smaller instances so losing half is less likely to be correlated, and keep utilisation low enough to absorb it."
Two users click at the same millisecond. What happens?
"We would use a lock." Which lock, held where, and what happens if the holder pauses? A lock is a mechanism, and reaching for it before asking whether the resource is contested at all is a reflex rather than an answer.
"First I would ask whether the thing is contested. If it is a like button, both writes land, the count converges, and I would choose not to spend a transaction on it. If it is the last seat, exactly one must win, and I get that by making the decision at a single point of serialisation: a conditional update that only succeeds if the seat is still free, or a unique constraint so the second insert simply fails. I am not proposing to read and then write in application code, because that gap is the race itself. The loser gets a clear message and an alternative, not an error. Cost: that path is now strongly consistent, so it is slower and it becomes unavailable if the owning partition is unreachable, which I accept, because selling one seat twice is worse than an error message. I would specifically not add a distributed lock, because the database row is already a single point of serialisation and a lock adds a failure mode where a paused holder's lease expires and two processes both think they won."
Writes double every month. When do you shard, and how do you know?
"We would shard when it gets slow." By the time it is slow you are already in an incident, and sharding is a multi-week project you cannot do under pressure.
"I would pick the trigger in advance, from a measurement rather than a feeling: sustained write throughput above about 60% of what the primary can commit, or replication lag that stops recovering during peak. At 100% monthly growth, 60% gives me about three weeks before I hit the ceiling. That is not enough for a sharding project, so I start the work when I cross 25%, which leaves about two months. Cheaper options come first: batch writes to reduce operation count, move non-essential writes off the hot path, and check whether one table is the problem rather than the database, in which case I move that table out first. Sharding is the last resort because it is the only one that is hard to undo."
Two halves of your cluster can see clients but not each other. What now?
"The system would heal itself when the network came back." It might heal, or it might have accepted conflicting writes on both sides for ten minutes and now has two versions of the truth with no way to merge them.
"This is a partition, which is the case CAP is about. Both halves are up and serving, so the danger is not availability, it is divergence — if both sides accept writes, I get two conflicting histories. The defence is a majority rule: only the side that can reach more than half the nodes may accept writes, so the minority side refuses. That means some users get errors even though their servers are healthy, and I accept that on purpose for anything contested — inventory, balances, unique names. For non-contested data I would keep both sides available and reconcile afterwards, because the worst case is a merge rather than a double-sell. The failure to avoid is split brain: the old leader not knowing it lost, so I need fencing tokens so the storage layer rejects writes from a leader that has been superseded."
Why not just one big machine?
"It would not scale." At what number? A modern server has enormous capacity, and dismissing it without arithmetic is the reflex this question is designed to catch.
"For a lot of systems one big machine is the right answer and I would say so. My estimate said 500 GB and 2,000 writes a second, which one machine handles comfortably — so size is not the reason. The reasons to distribute are: availability, because one machine means downtime during any restart or hardware failure, and I need a replica regardless; blast radius, because one machine means every customer shares one failure; and eventually write throughput, which I am nowhere near. So my actual design is one primary with a replica for failover, and I would revisit when writes approach 60% of what the primary can commit. Choosing not to distribute, on purpose, with a stated trigger for changing my mind, is the answer. Distributing by reflex makes every future feature harder to build."
How do you know when you are about to run out of capacity?
"We would monitor utilisation." Of what resource, and against what threshold? Utilisation of the wrong resource is how people get surprised.
"I would identify the constraining resource per component, because it is different for each and rarely CPU. For the connection servers it is memory and file descriptors. For the database it is write throughput and connection count. For the queue it is consumer throughput against arrival rate. Then track headroom against those specific limits, and trend them, because the useful alert is not 'we are at 70%' but 'at the current growth rate we hit the ceiling in three weeks'. That gives time to act rather than a surprise. I would also load test to find the real ceiling rather than assuming a number, because the actual failure point is usually lower than the theoretical one and often in an unexpected place: a connection pool, a lock, a single-threaded component. And I would test the degraded case: what capacity do I have with a third of the fleet gone, because that is the number that matters during an incident."
Multi-region doubles your bill. Justify it.
"It gives us high availability." At what cost per hour of downtime avoided? Without that comparison this is an assertion, not a justification.
"I would justify it with the cost of the downtime it prevents, and if I cannot, I would not do it. For a system where an hour of outage costs a large amount of revenue or breaks a contractual commitment, doubling infrastructure spend is easily worth it. For an internal tool, it obviously is not. There is also a second justification, and it is often the stronger one: latency. If a large share of users are on another continent, they are paying 150 ms per round trip, and a regional presence improves their experience measurably. That is a product benefit, not just insurance. What I would push back on is doing it for availability alone when the actual outages have been caused by bad deploys and bugs rather than regional failures, because a second region does not protect you from your own code. The bad deploy reaches both regions. Cheaper alternatives I would consider first: multi-zone within one region, which covers most real failures at a fraction of the cost."
Now make it multi-region.
"We would replicate the database to another region." That covers reads. The question is what happens to writes, and that is where the design actually changes.
"Reads are the easy half: replicas in each region, users read locally, and they may be slightly stale — I would say how stale and which reads cannot tolerate it. Writes are the hard part, and there are three options. Single write region: simplest, no conflicts, and users far away pay 150 ms per write, which is fine if writes are rare and unacceptable if they are not. A home region per data partition, so each user's data lives near them: local writes without conflicts, but it needs a routing layer plus a plan for users who move. Multi-leader with conflict resolution: local writes everywhere, and now I own a conflict problem, which is only acceptable where merges are safe. I would pick the second for user-owned data and single-region for anything globally contested like inventory. What changes elsewhere: cross-region replication cost, a failover story per region, and data residency rules that may force certain data to stay in certain places. I would ask about that constraint rather than discover it later."
The topics this answer used
You have read a good answer. That is worth very little until you can produce one on a blank page — so go and write this problem without looking, and compare afterwards.