Design a key-value store like Redis or Dynamo
Design a distributed key-value store like Redis or Dynamo: partition with consistent hashing, replicate, and tune quorum reads and writes.
A distributed key-value store splits keys across many machines with consistent hashing, copies each key to N replicas, and uses quorums so reads and writes survive a dead node. Choose W and R per request: with R + W greater than N a read sees the latest write, and with smaller values you trade freshness for speed. This is the shape of Amazon's Dynamo, DynamoDB and Cassandra.
This question is in the System Design Primer's list of additional questions.
Requirements#
Functional:
put(key, value)andget(key), with values up to a few hundred KB.Optional delete and TTL.
Non-functional:
Single-digit millisecond reads and writes at the 99th percentile.
Highly available for writes: a node failure must not stop the store.
Scales horizontally by adding machines, with little data movement.
Eventually consistent by default, with stronger reads when a caller asks.
Estimate the load#
Assume 1 billion keys, 1 KB per value, 100,000 requests per second with 4 reads for every write.
Raw data: 1,000,000,000 x 1 KB is 1 TB. With N of 3 that is 3 TB on disk.
Machines: at 1 TB per node, 3 TB is 3 nodes by capacity. By throughput, if a node serves 10,000 operations per second, 100,000 / 10,000 is 10 nodes before replication cost.
Write cost: 20,000 writes per second x 3 replicas is 60,000 replica writes per second. Reads at R of 2 cost 80,000 x 2, or 160,000 replica reads.
So throughput, not storage, sets the cluster size. Plan about 25 nodes with headroom.
The design#
Partitioning#
Hash each key onto a ring and give it to the next node clockwise. Adding a node moves only its neighbour's slice, where hash(key) % n would remap almost everything. Each machine takes many virtual nodes so slices even out. See consistent hashing and sharding.
Replication#
Store each key on the next N distinct nodes around the ring, usually N of 3, ideally in different zones. Any node can coordinate a request, so there is no leader to lose. See replication strategies.
Quorum reads and writes#
A write succeeds when W replicas acknowledge it, and a read asks R replicas and returns the newest version.
| N, W, R | Behavior |
|---|---|
| 3, 2, 2 | Read sees latest write, survives one node down |
| 3, 1, 1 | Fastest, a read can be stale |
| 3, 3, 1 | Fast reads, but one dead node blocks writes |
Making this tunable per request is what DynamoDB's strongly consistent read flag and Cassandra's consistency levels do. Details are in quorum reads and writes.
Conflicts and repair#
Concurrent writes to one key need a rule: last write wins by timestamp, or vector clocks that keep both versions. Replicas that missed a write catch up through read repair and background anti-entropy. A node that is briefly down gets hinted handoff.
Where it breaks#
One key is hot. A popular key lives on N nodes, so more nodes do not help. Cache it in front, split it into several sub-keys, or spread reads over all replicas. See hot keys and hot shards and the Hot key incident.
A partition splits the ring. With W and R of 1 both sides accept writes and diverge. A quorum of 2 stops the minority side. This is the CAP choice: CAP and PACELC lays it out, and the Network partition incident shows it in play.
Stale reads surprise users. A user writes and reads back an old value. Route that user to the replica that took the write, or raise R. See read-your-writes and consistency models.
Build it in Quorum#
Research Leaderless replication and place a Wide-column Store, the game's Cassandra. Its card takes N, R and W, so set R + W above N and then below it, and watch stale reads appear and the cost per request change.
The first board is the quorum answer. One App Server talks to a Wide-column Store with three replicas per key and a read and write quorum of two, so R + W is above N. Look at how the store's capacity is spent, because a write costs N replica operations and a read costs R, which is why the cluster size follows throughput and not storage. It uses an App Server and a Wide-column Store, and the pattern is quorum reads and writes.
Drag to pan. Hold Ctrl or Cmd and scroll to zoom.
| Where | Setting | Value | Why |
|---|---|---|---|
| App Server | Instance size | small | Small is enough, because the store does the data work. |
| Wide-column Store | Read quorum (R) | 2 | A read asks two of the three replicas, so at least one holds the latest write. |
| Wide-column Store | Write quorum (W) | 2 | A write waits for two of three. With R at two, R plus W is above N, so every read sees the last write. |
| Wide-column Store | Instance size | small | A write costs N replica operations and a read costs R, so capacity is spent faster than the size suggests. |
Research this Design needs: Leaderless replication, Sharding, Leaderless replication.
The second board adds the rest of a real data tier. An API Gateway sends lookups to the App Server that talks to the quorum store, and sends searches and uploads, which a key-value store cannot answer, to a second App Server and a Database. One caller reads one Data Group, so each store gets its own App Server. Look at which requests go to which store. It shows the interview point that a key-value store only does lookups by key, and the Database covers everything else. Distributed SQL and leaderless stores puts the two kinds side by side.
Drag to pan. Hold Ctrl or Cmd and scroll to zoom.
| Where | Setting | Value | Why |
|---|---|---|---|
| App Server | Instance size | medium | Medium, so the store is the tier under test. |
| Wide-column Store | Replicas per key (N) | 3 | Three copies of each key survive the loss of one. |
| Wide-column Store | Replicas a read asks (R) | 2 | Two of three replies, so a read overlaps any write that waited for two. |
| Wide-column Store | Replicas a write waits for (W) | 2 | R plus W is above N, so every read sees the latest write. |
| App Server | Instance size | medium | Medium, so the Database tier is not the limit. |
| Database | Instance size | medium | Searches and uploads stay on a Database, because the store takes only reads, writes and transactions. |
| Link API Gateway → App Server | Request kinds | page,read,write,login,buy,rt,bot,media | Lookups by key go to the App Server that talks to the store. |
| Link API Gateway → App Server | Request kinds | search,upload,job,report,ai | A key-value store cannot answer these, so a second App Server sends them to the Database. |
Research this Design needs: Leaderless replication, API gateway, Read replicas, Sharding, Leaderless replication.
The third board is partitioning. One Database is given four shards on a hash key, so keys spread evenly and no shard runs hot, which is the point of hashing a key onto a ring. Look at the load on each shard. It uses a Database and not a store, and it hashes keys into fixed shards, which is simpler than a ring with virtual nodes. See sharding and consistent hashing.
Drag to pan. Hold Ctrl or Cmd and scroll to zoom.
| Where | Setting | Value | Why |
|---|---|---|---|
| App Server | Instance size | large | Large, so the App Server is not the limit and the shards are. |
| Database | Shards | 4 | Each shard is another copy of the Database, and writes divide across them. |
| Database | Shard key | hash | A hash of the user ID sends every user to one shard and spreads users evenly, so no shard runs hot. |
| Database | Instance size | small | Small for each shard, so a shard that takes too much of the load shows. |
Research this Design needs: Sharding.
The Hot key Sandbox shows one key overloading its replicas.
The game covers replication and quorum settings, plus placement of keys on replicas. It does not model conflict resolution, hinted handoff or read repair, so those stay interview theory. It also does not let you add a node and watch a ring rebalance.
Common questions#
What is the difference between a key-value store and a database?#
A key-value store only looks up by key, which lets it shard and replicate simply and answer in milliseconds. A relational database adds joins, secondary indexes and transactions, and pays for them in scalability.
How does consistent hashing work in a key-value store?#
Nodes and keys are hashed onto the same ring, and each key belongs to the next node clockwise. When a node joins or leaves, only the keys next to it move, about 1/n of the data.
What does R + W > N mean?#
It means every read set overlaps every write set in at least one replica, so a read reaches a node holding the latest acknowledged write. It improves freshness but is not full linearizability.
Should a key-value store be consistent or available?#
For most use cases, available: shopping carts and sessions tolerate a stale read. For balances and inventory, ask for quorum reads or use a consensus store instead.