Design a distributed key value store

A key value store is the simplest database there is. You give it a name (the key, like cart:7) and some data (the value, like the items in that cart), and later you ask for the data back by name. That is the whole interface: put and get.

Building one on a single machine is a weekend project. Building one that spreads billions of keys across hundreds of machines, keeps working while some of them are down, and never quietly loses a write is this question. Every HLD building block shows up in it: consistent hashing decides where a key lives, quorums decide what a read returns, replication decides what survives a crash. Watch one write go through.

Three words come up all through this page, so here they are in plain terms:

• A node is one machine in the cluster.
• A replica is one copy of a key. With three replicas, three different nodes hold the same key, so losing one machine loses nothing.
• Quorum means "enough of them". Instead of waiting for every replica, a write waits for a set number of them to say yes.

If you can do this one, most of the other design questions become assembly.

Step 1: Understand the problem#

Half of this question is deciding what you are not going to support. Every "no" below buys you something in the design, so say them out loud and early.

What you are building#

"p99" means the 99th percentile: 99 out of every 100 reads must be at least this fast.

Back of the envelope#

Three inputs. The last two rows are the ones that shape the design. (New to this kind of estimate? The back of the envelope chapter shows the method.)

The 60 bytes added to each value is a rough allowance for the key and the bookkeeping stored next to it.

Step 2: Propose the high level design#

The API#

Three calls. The interesting part is what travels with them.

{
  "value": "...",
  "version": "n1:4,n3:2"
}

A tombstone is a small record that says "this key was deleted at this version". It sounds wasteful to store a note about nothing, and the third checkpoint question at the end shows why it is needed.

Where a key lives#

With hundreds of nodes, every node needs to answer "which machines hold cart:7?" on its own, in microseconds, and the answer must barely change when a machine joins or leaves.

Try it. Add and drop nodes and watch the counter of keys that move.

At a few hundred nodes, adding one moves a fraction of a percent of the data, and every node works out where a key lives locally, with no lookup service anywhere in the request path. The consistent hashing chapter covers the ring from scratch, and why virtual nodes are not optional shows how lopsided it gets without them.

The "skip a machine already chosen" rule matters more than it looks. Without it, three replicas can land on one machine, and the replication factor becomes a lie.

What a read returns#

Three numbers control everything here:

• N: how many copies of each key exist. Here, 3.
• W: how many replicas must confirm a write before the client hears "done".
• R: how many replicas a read asks before answering.

A small worked example. N = 3, W = 2, R = 2. A write reaches replicas A and B and is confirmed. Replica C has not got it yet. A read now asks any two replicas. If it asks A and C, A has the new value. If it asks B and C, B has it. If it asks A and B, both do. There is no way to pick two out of three that misses both A and B, so when R + W is greater than N, every read overlaps the latest completed write. The read compares versions and returns the newest.

Play with the dials above. The store does not decide consistency, the caller does, per operation, and that is the feature. The common settings say something real:

• W=1, R=1 behaves like a cache: fast, always writable, often stale.
• W=N, R=1 makes reads cheap and writes fragile, since one slow replica stalls every write.
• W=2, R=2 with N=3 is the workhorse. It survives one node being down on either side and still overlaps.

"Stale" here is the difference between strong and eventual consistency, which strong vs eventual consistency shows live. The quorums section of the replication chapter goes deeper, and the CAP theorem chapter explains why staying writable during a network split means giving up some consistency.

The whole system on one whiteboard#

Figure 1 is the entire store. The picture at the top showed one write through the middle of it. There is no leader in it, no config service in the request path, and no box every request has to pass through. That is the design goal, not minimalism: at a few hundred nodes something is always restarting, so nothing is allowed to be special.

Walking Figure 1:

1. The client connects to whichever node it likes. There is no routing tier to keep alive and no leader to find.
2. That node becomes the coordinator for this request. It hashes the key against its own copy of the ring. Each node keeps that copy up to date through gossip: every second or so, nodes swap "who is alive" news with a few random peers, and the news spreads through the cluster like a rumour. (Failure detection and gossip explains how.) So placement costs a hash and no network call.
3. It sends the operation to the N nodes that own the key.
4. It waits for W acknowledgements on a write, or R responses on a read, and answers the client. It does not wait for the slowest replica, which keeps the slow tail of response times down.
5. Each replica appends the write to its own commit log and memtable. Nothing is updated in place. (The third deep dive explains why.)
6. Repair runs beside all of this: hints for nodes that were absent, read repair on values a read already fetched, and Merkle trees for the keys nobody reads. The second deep dive explains all three.

Step 3: Design deep dive#

Two writers, one key#

Two people share a shopping cart. At almost the same moment, one adds milk on their phone and the other adds eggs on a laptop. Both writes reach the store, through different coordinators. Which one is the cart now?

Here is the third rung, one message at a time.

Say out loud which one you are choosing and what it costs. Last write wins is defensible for a value that is simply overwritten, like a user's profile photo. It is not defensible silently.

Clocks are the root of this whole problem. Time and clocks shows how far apart machine clocks drift, and its section on vector clocks walks through the comparison step by step. If you want the merge to happen without application code, CRDTs are data types built so that any two copies can always be merged automatically.

Nodes are always missing#

At a few hundred nodes, some node is always restarting, upgrading, or briefly unreachable. The question is what happens to writes meant for it, and how it catches up afterwards.

Switch between the three repair paths below.

Anti entropy just means "background work that stops copies drifting apart". The tool it uses is a Merkle tree. Start with a hash: a short fingerprint of some data, where the same input always gives the same fingerprint and any change gives a different one (the hashing article shows one live). Hash every key and value. Then hash those hashes in pairs, then hash the pairs in pairs, until one hash is left at the top: the root. If any key changes, its fingerprint changes, and so does every hash on the way up to the root.

Two replicas compare roots. Same root, same data, finished. Different root, compare the two hashes one level down, and only follow the side that differs. Try it: make a key stale and watch which boxes get compared.

This is the answer to the question at the top of the page. A node returning after an hour does not compare every key it owns. It compares a root hash with its peers and goes down only into the parts of the tree that disagree.

The storage engine#

Now inside one replica. A node may hold 8TB of keys, takes a steady stream of writes, and can lose power at any moment. How does it store them?

LSM tree stands for log structured merge tree. The reason to pick it over a B-tree (the structure most relational databases use, which updates pages in place) is that every write is an append. There are no random disk writes and no page splits on the write path, and immutable files are trivially safe to copy for repair or to stream to a new node. Storage engines compares the two families in depth.

A Bloom filter answers "is this key in that file?" with either "definitely not" or "maybe", using only a few bits per key. Most files say "definitely not", so a read opens only one or two. The web crawler page has a 16 bit Bloom filter you can play with.

Break it#

Push the dial and watch what the cluster does at each level of damage.

Trade-offs#

The level bar#

One moment from this round, answered three ways. Pick the one you think is staff level before the labels appear. (What changes at senior and staff explains the gap.)

Then run the question cold, with a 45 minute timer and no notes, and score the run on the five things this question is really testing.

Interview replay#

Checkpoint#