Dev Learning
Building the storage itself

Distributed key-value store

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.

hardReplicationPartitioning (sharding)Write-ahead logsCAP and PACELC as real tradeoffsBloom filtersConsensus, at concept levelConsistent hashingBackups, disaster recovery, RPO and RTOMulti-region and data residency

Where’s the slack?

Reads: milliseconds. Writes: milliseconds. Repair and rebalancing: hours.

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.

Work it through

Five stages, gated. You write your answer for each stage before its model answer unlocks. That is the core of the method.

Loading your progress…

Reference material for this problem. The diagrams below are here to check your own against once you have drawn it, not to read first.

The lifecycle

Received by coordinatorany nodeRouted to N ownersringLogged + fsyncedeach replicaAcknowledged at WcoordinatorFlushed to sorted filebackgroundCompactedbackgroundStale ring, wrong nodenode forwards and tells the client to refresh its viewReplica unreachablehinted handoff — a peer holds the write and delivers it on returnOnly W-1 respondednot confirmed to the client, but partially applied — say so rather than hide itTwo concurrent writesversion vectors detect concurrency; siblings returned for the app to resolveCrash with data in memoryreplay the write-ahead log on restart — nothing confirmed is lostNode gone for a dayhints expired, so full stream from peers — 18 hours, throttled
A write's life inside the store. The log entry before the acknowledgement is what makes this a database rather than a cache.

The numbers

Per-node load~10,000 ops / sec — modest
Quorum write, one datacenter~2 ms
Quorum write, cross-region~80 ms — 40x worse
Rebuilding one 8 TB node~18 hours at two copies

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.

The rebuild window, not the throughput, is what sets your replication factor.

The architecture

who owns?flushsnapshotClientcaches the ringCoordinatorany nodeReplica 1Replica 2Replica 3down — hints heldMembershipRaft, 5 nodesWAL + memtableSorted filesbloom per fileBackupsobject storage
Membership lives in a tiny Raft group that data traffic never touches. Inside a node: a log for durability, sorted files for reads, bloom filters so reads skip files.

The decision this turns on

A
Last-write-wins by timestamp
  • —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.
B
Version vectors with siblings
  • —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.
Which one: Version vectors by default for anything a user created, with last-write-wins available as an opt-in for callers who do not care. The sentence worth saying: last-write-wins is not conflict resolution, it is a decision to lose one side, and it should be made on purpose rather than inherited from a default.
What to do when two writes to one key conflict.

Follow-ups you should expect

Many interviews are decided in the follow-ups, not the first diagram.

Half your servers vanish instantly. What is the user impact?Two users click at the same millisecond. What happens?Writes double every month. When do you shard, and how do you know?Two halves of your cluster can see clients but not each other. What now?Why not just one big machine?How do you know when you are about to run out of capacity?Multi-region doubles your bill. Justify it.Now make it multi-region.

Same shape, other products

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.

Others with this shape: Distributed key-value store · Distributed cache · Object storage · Message broker

Before you leave
Try this problem again in a week without reading anything. Comparing what you write then with what you wrote today shows you what stuck.
Stuck, or new to this?Read the full worked solutionAll five stages end to end, with the diagrams and the costs, written out the way you would say it. Best read after you have had a go.Read it →

How it is really built

Write your own answer first. Then read how teams who run this at scale describe it. Their constraints were real, and the write-ups often say what their choices cost.