Fundamentals · Intermediate

Key-value store

Dynamo-style: consistent hashing, three replicas, quorums, hinted handoff and Merkle-tree repair.

Every part, and why it is there

Application servers

Callers doing get(key) and put(key, value). They want writes to always succeed, even during failures, which drives the whole design.

Load balancer

Sends each request to any node. Smart clients can skip this and go straight to the right node using the ring layout.

Coordinators (every node)

Whichever node receives a request becomes its coordinator. It hashes the key onto the ring, finds the 3 nodes responsible, and waits for enough of them to answer. There is no leader to fail.

Ring membership (gossip)

Which nodes exist and which key ranges each owns. Nodes gossip this to each other every second. Each server owns many small “virtual nodes”, so adding one moves only a small slice of data.

Replica A

One of three copies. Writes go to a commit log and an in-memory table that is later flushed to sorted files (an LSM tree), which keeps writes fast.

Replica B

Second copy, placed in a different rack or zone so one failure cannot take out two copies.

Replica C

Third copy. With N=3, W=2, R=2 every read overlaps at least one node that saw the latest write (because R + W > N).

Hinted handoff

If replica C is down, a write meant for it is kept by another node with a note “this belongs to C”. Writes keep succeeding during the outage.

Hint replayer

Delivers the held writes to C once it is back, so it catches up without a full copy.

Anti-entropy repair

In the background, replicas compare Merkle trees (hashes of key ranges) and copy over only the ranges that differ. This fixes whatever hints missed.

Asked in interviews at

  • linkedin
  • databricks
  • microsoft
  • airbnb

Concepts used here

  • Database indexes: Find one user among a million by reading 4 pages instead of 12,500. Build the index by hand, then see what it costs and why column order matters.
  • Replication: A copy of your database is not a live mirror. Copies run behind, so you can read old data, and a crash can lose a save you were told was safe.
  • CAP theorem: When the network between two copies of your data breaks, each side must either refuse some requests or risk a wrong answer. You choose which, ahead of time.
  • Sharding: Split one table across many database machines. It buys room and speed, and makes every query and transaction that crosses machines harder.
  • Bloom filter: Answer “have I seen this before?” for a hundred million names in about 10 bits each. It never wrongly says no.
  • Consistent hashing: Why adding one cache server can take a database down, and the ring that makes it move only about 1 key in 5 instead of 4 in 5.
  • Merkle tree: Two copies of a million rows find the few that differ by comparing about 41 short fingerprints, not a million rows.
  • LSM tree: Follow one write through Cassandra- or RocksDB-style storage: append it to a log, sort it in memory, write whole files, and clean up old copies later.
  • Raft consensus: Five servers hold copies of the same settings. Raft’s four rules stop them from ever disagreeing, even when the network splits them in two.
  • Skip list: Keep a million-player leaderboard in score order and find any score in about 40 steps, using a linked list, some extra lanes and a coin.

Learn more

All system design examples