// Distributed Data Building Blocks

Design a distributed key-value store

System Design track · 25 min

By the end of this lesson you can
  • Explain how a key-value store spreads keys over many servers and keeps three copies of each.
  • Pick N, W and R for a product and say exactly what that choice costs.
  • Describe how the store keeps working when servers die or two clients write the same key at once.

Think of the cart on a shopping site. Every visitor has one, it changes every few seconds, and the site only ever asks two things of it: give me this user's cart, and save this new cart. That is a key-value store: get(key) to read a value, put(key, value) to save one. Nothing else.

Two operations sound easy. Yet Amazon built Dynamo for exactly this cart, and Cassandra and Riak grew from the same ideas. The hard part is not the operations. It is keeping them fast and correct when the data lives on hundreds of servers and some of those servers are always broken.

Version 1: one server

Start with the simplest thing that works. One server keeps a hash map in memory: key in, value out, in microseconds.

Memory is wiped when the server restarts. So every write first goes into a commit log on disk, a file you only ever add to at the end. After a crash, the server reads the log from the top and rebuilds the map.

Two limits kill this version. All the data must fit in one machine's RAM. And when that machine dies, the whole service dies with it.

Version 2: spread the keys with consistent hashing
  1. Bring back the ring from the consistent hashing lesson. Hash each server to a point on a circle, hash each key the same way, then walk clockwise. The first server you meet owns that key.
  2. Adding or removing a server moves only the keys right next to it, about 1/N of the total. With plain key % N, almost every key would move.
  3. Give each real server many virtual nodes spread around the ring. The load evens out, and a bigger machine simply takes more virtual nodes than a small one.
Version 3: three copies and the W + R > N rule

A single copy still dies with its server. So store every key on N = 3 servers: its owner plus the next two on the ring. This is replication, which you met in the data-at-scale lesson.

Now two numbers decide how the store behaves. W is how many of the 3 servers must confirm a write before you tell the client “saved”. R is how many must answer a read.

Take W = 2 and R = 2. Any 2 servers you wrote to and any 2 you read from must share at least one server, because 2 + 2 = 4 is more than 3. That shared server holds the newest value, so the read sees it. This is the rule W + R > N: when it holds, every read overlaps the last successful write.

Now try W = 1 and R = 1. Both operations get fast, because you wait for one server only. But a write confirmed by server A, followed by a read answered by server B, can return the old value. You bought speed and paid for it with correctness.

In the lab below, try W = 1, R = 1 first, then W = 2, R = 2. Then kill a node or two and see which settings stay available.

Try it yourself
When a server is down: the neighbour takes the parcel

With a strict quorum, if one of the three owners of a key is down and W = 3, the write is refused. The cart cannot be saved, and the customer leaves.

A sloppy quorum accepts the write anyway. It goes to the next healthy servers on the ring, even ones that do not own the key, with a note saying who the real owner is. When the owner comes back, the stand-in sends the write over and deletes its copy. This is called hinted handoff.

It works like a courier who finds you away and leaves the parcel with your neighbour. When you return, the neighbour hands it over. You stayed available through the outage. The price: a read during the outage may ask the real owners and miss the value that is sitting at the neighbour's.

Two writes at the same moment

Two clients update the same key at the same moment, on two different replicas. Which value wins?

Vector clocks give an exact answer. Each version carries a small list of (server, counter) pairs. Comparing two lists tells you whether one version came after the other, or whether they split apart. If they split, you keep both and let the application merge them. Dynamo's cart did exactly this: merge the two carts, so no item is lost.

Last-write-wins (LWW) is the lazy default: compare clock timestamps and silently drop the older one. It is one line of code, and it deletes data. Two people editing a shared cart lose one person's item. Server clocks also drift, so “older” may not even be true. Use LWW only where losing a write is genuinely fine.

Who is dead, and who has drifted

There is no master server here, so servers find failures by gossip. Every second, each server swaps heartbeat information with a few random peers. News of a dead server spreads through the whole cluster in O(log N) rounds, with no central watcher.

Gossip tells you who is alive. It does not tell you whose data is behind. Replicas drift quietly: a handoff that never arrived, a write that got lost. The repair tool is a Merkle tree. Each server builds a tree of hashes over its keys. Two servers compare the top hash first. Only if it differs do they walk down to the branches that differ and sync just those keys. One hash comparison can confirm that millions of keys match.

Inside one server: the write path

A write lands in the commit log first. That is a sequential append, the fastest thing a disk can do. Then it goes into the memtable, a sorted table in memory.

When the memtable fills up, the server writes it to disk as an SSTable: a sorted file that is never edited again. A read checks the memtable, then the SSTables from newest to oldest. A Bloom filter on each file says “this key is definitely not here”, so most files are skipped without being opened.

Nothing is ever updated in place. The disk only sees appends, plus a background job called compaction that merges old SSTables and throws away overwritten values. That is why writes stay fast even under heavy load.

WRITERequestCommit logappend on disk firstMemtablesorted, in RAMSSTablesorted, immutable file1 append2 write3 flush when fullREADMemtablenewest firstRecent SSTablesOlder SSTableson misson miss
Follow the write from left to right: commit log, then memtable, then a flush to immutable SSTables. Reads go memtable, Bloom filters, then SSTables, newest first.
The idea

Notice what you never did in this lesson: you never picked “the best” setting. N, W, R, strict or sloppy quorum, vector clocks or LWW: each one is a dial. The right position depends on what your product fears most: a slow answer, an old answer, or a lost write.

A distributed key-value store is less a data structure and more a set of trade-offs you chose on purpose. A shopping cart wants to stay writable even during failures. A bank balance wants every read to be correct, even if that means refusing some requests.

Common mistake

The classic mistake is to treat “distributed” as a free upgrade: add servers and you get scale and reliability. Every guarantee in this lesson has a price.

Reads that see the latest write cost latency, because you wait for W and R answers. Staying available during failures costs consistency (sloppy quorum). Safe conflict handling costs complexity and bigger values (vector clocks). Fast writes cost slower reads and compaction work. If a design claims all of these at once for free, it is hiding the bill.

Test yourself

With N = 3, W = 1 and R = 1, a client saves a value and the write is confirmed. It reads the key right away. What can it get back, and why?

Answer in your head first, then check.

Takeaway

You built it layer by layer: one server with a hash map and a commit log; consistent hashing to spread the keys; N = 3 copies with W = 2 and R = 2 so reads see writes; sloppy quorum and hinted handoff to survive outages; vector clocks to handle concurrent writes honestly; gossip and Merkle trees to keep the cluster healthy; and a commit log, memtable and SSTables to keep writes fast. That is the skeleton of Dynamo.

Do it this week

Take one datastore your team runs (Redis, Cassandra, even Postgres with replicas) and write down its real N, W and R: how many copies exist, when a write counts as saved, and what a read can return while one server is down. Then find one place where you rely on last-write-wins and ask what data it could silently drop. Ten minutes, and you will know your system's real promise for the first time.

What you can do now
  • Explain how a key-value store spreads keys over many servers and keeps three copies of each.
  • Pick N, W and R for a product and say exactly what that choice costs.
  • Describe how the store keeps working when servers die or two clients write the same key at once.

Distributed Data Building Blocks