!This gives away every stage. For a clean attempt, practise it first, then come back.

Before we start

In every other interview question, you say “store it in a key-value store like DynamoDB” and move on. This time, you’re building the store.

The interface is tiny: put a value under a key, get it back, delete it. Everything interesting is underneath. The data is too big for one machine, so it must be spread out. Machines fail every day, so there must be copies. Copies can disagree, so you need rules for who wins. And all of it must answer in a few milliseconds.

This design follows Amazon’s Dynamo paper, the idea behind DynamoDB and Cassandra. You don’t need to have read it; we’ll build it step by step.

Same order as always: requirements, quick maths, data and API, a design that grows, then deep dives.

Minutes 0–5Requirements

Functional requirements

1. Put, get and delete values by key.
2. Let each request choose between faster and more up to date.
3. Add or remove machines without downtime, moving as little data as possible.

Nice to have: values that expire after a set time. Out of scope: range queries, secondary indexes and transactions.

Non-functional requirements

1. Fast: a few milliseconds per request, even at the 99th percentile.
2. Always writable: writes keep working when machines or network links fail.
3. Durable: three copies in three zones, so even losing a whole zone loses nothing.
4. Big: 100 TB of data and a million operations a second.
5. Copies catch up: after failures, all copies eventually agree again.

Minutes 5–10Back-of-the-envelope estimates

Two things follow. First, with 110 machines, one of them is failing or being updated almost every day. Failures aren’t rare edge cases here; they’re the normal state. Second, with 10 billion keys, we can’t keep a central list of where each one lives. The location has to be worked out from the key itself.

Minutes 10–15Core entities and the API

Core entities

• Key and value: the key is a string; the value is opaque bytes up to 1 MB.
• Version: a small record attached to each value, used to tell which of two copies is newer.
• Node: one machine, holding part of the data and part of the copies.
• Ring: how keys are assigned to nodes (explained below), shared by every node.

The API

The two small numbers, W and R, are how each request picks “faster” or “more up to date”. We’ll see exactly what they mean in stage 3.

Minutes 15–25The design, built up

Stage 1One machine: a hash map, a log, and snapshots

This is fast and simple, and plenty of real systems start here. But 100 TB won’t fit on one machine, and when it crashes or reboots, everything is unavailable. Both break our requirements.

Stage 2Spread keys across machines with consistent hashing

Lesson 5.2 shows how much data moves each way:

Stage 3Three copies and quorums

That overlap rule is easier to see than to explain. Lesson 5.3 has a demo:

Stage 4When machines fail: gossip, hinted handoff, repair

Here’s hinted handoff, compared with simply waiting for all three:

Checking the design against the requirements

Deep diveWhere does each key live?

Bad solutionHash mod N

hash(key) % 110. Simple, until machine 111 arrives and almost every key now maps somewhere else. Nearly all 300 TB would have to move, and while it does, reads land on the wrong machines.

Good solutionConsistent hashing

Keys and machines on a circle; each key goes to the next machine clockwise. A new machine only takes keys from its immediate neighbour, about 1/110th of the data.

Great solutionConsistent hashing with virtual nodes

Each machine appears at, say, 256 points around the circle. Data spreads evenly even with uneven luck in hashing, a new machine takes small slices from many machines at once (so no single machine is overloaded moving data), and more powerful machines can simply be given more points. Lesson 5.2 shows data moving gradually instead of all at once:

Deep diveWhen copies disagree

Bad solutionLast write wins, by the clock

Keep whichever value has the newest timestamp. Simple, but machine clocks drift, so the write that really happened second can lose, and the lost write disappears without anyone noticing. For a shopping cart, an item silently vanishes.

Good solutionVersion vectors

Each value carries a small record of which replicas have updated it and how many times. Comparing two records tells you whether one version came after the other (keep the newer one) or whether they happened at the same time without knowing about each other. In that case, keep both and let the application merge them. Amazon’s Dynamo did exactly this for carts: when two versions conflict, merge them by keeping the items from both.

Great solutionPick per use case

For some data, last write wins is genuinely fine, like “last known location”. For carts, use version vectors and merge. For counters and sets, use data types designed to merge automatically, called CRDTs. The strong answer is naming what each choice can lose. Lesson 5.3 shows last write wins losing data:

Deep diveCopies drifting apart

One subtle trap: deletes. If a replica missed a delete, it still has the old value, and read repair would copy it back. So a delete is stored as a marker (a “tombstone”), kept long enough for all copies to see it, and only then cleaned away.

Deep diveInside each node

Deep diveThe CAP choice, made concrete

Lesson 5.4 shows a network split playing out both ways:

The complete architecture

Here’s everything together: the full design from the last stage, with every part we added along the way. If you only remember one picture from this question, make it this one.

How one request travels through it:

1. The client library knows the ring, so it sends a request straight to a node responsible for the key. That node coordinates the request.
2. The coordinator hashes the key to find its three replicas: the next three distinct machines around the ring, placed in three different zones.
3. For a write, it sends the value to all three and replies once W of them (say 2) confirm. Each replica appends the write to its log first, then its in-memory table.
4. For a read, it asks R of them (say 2) and returns the newest version. If one replica had an older version, it quietly updates it (read repair).
5. If a replica is down, another node accepts the write with a note saying who it’s for, and hands it over when the replica comes back.
6. Nodes gossip to share who’s up and how the ring is laid out, and a background process compares copies to fix anything that drifted.

How this answer gets scored

Interviewers don’t tick boxes, but their notes on this question tend to land on the same few moments. Here’s what each one sounds like from the other side of the table.

What the left column has in common: every choice points back to a requirement or a number from earlier. If you can say where each box came from, the interviewer will notice.