How to design a distributed key-value store
The first sections are free. The deep dives, level expectations and quiz are part of Pro.
On this page
- The problem
- Clarifying questions
- The requirements menu
- Non-functional requirements
- Estimates
- Core entities
- The API
- The high-level design
- What breaks first
- The deep dives
- Entity fields
- Tuning the quorum
- Resolving conflicting writes
- Adding, removing and repairing nodes
- Variants
- What each level is expected to show
- The 30-second answer
- Quiz
The problem
A distributed key-value store keeps small values under keys and spreads them across many machines, so that services can put and get by key without caring which machine holds what. A sound answer follows the Dynamo shape: a hash ring that places each key, N copies of it on the next distinct nodes around the ring, a coordinator that waits for W write acks or R read replies, gossip to track which machines are alive, and hinted writes plus Merkle-tree repair to bring copies back in step after failures. The answer turns on one decision made out loud: how many copies each key gets and how many of them must answer before a put or a get returns, because that choice sets the latency, the consistency the caller sees, and what the store does when the network splits.
Clarifying questions
| Ask | Why it matters | A typical answer |
|---|---|---|
What do callers store under a key, and how large is a value? | Value size decides whether a node can hold a whole value in memory-first storage and copy it whole to each replica, or whether you need chunking and streaming, which is a different system. | Opaque values under 10 KB each, billions of keys in total. The store doesn't look inside a value. |
When the network splits, should the store keep taking writes, or refuse them so that no two versions of a key can appear? | This is the CAP choice and it shapes the whole design: a store that keeps writing during a split needs versioning and conflict handling; one that refuses needs a leader or a strict majority. | Keep taking writes. Services such as a shopping cart would rather merge two versions later than reject a customer's update. |
Does one consistency setting fit all callers, or should each call choose? | If callers tune it, the API carries the write and read quorum sizes and the coordinator waits accordingly; if not, you pick one setting and defend it. | Callers choose. They pick how many replicas a write and a read wait for, as few as 1 each. |
How much traffic should I plan for, and what latency do callers expect? | Without a request rate you can't size the cluster, and the latency goal decides whether a put may wait for the slowest replica. | No rate is given, so state your own assumption aloud and keep it in view. Low latency on each put and get is a stated requirement, so plan for operations that wait on a few replicas, not all of them. |
Does the store need to survive the loss of a whole data center? | If yes, the copies of a key must be placed in more than one data center, and quorum settings must still be reachable with one center gone. | Yes. It's a stated requirement, so place replicas across data centers from the start rather than retrofitting it. |
Do we need range scans, secondary indexes, transactions across keys, or authentication? | Each of those pulls the design away from a hash ring: ranges want ordered partitioning, transactions want coordination across nodes, and auth wants a gateway. | None of them. Single-key put and get, plus cluster membership, is the whole surface. |
Non-functional requirements
| Requirement | What it forces |
|---|---|
Each key-value pair is small, under 10 KB | A value is copied whole to each replica and fits comfortably in an in-memory write buffer before it reaches disk, so there's no chunking and no streaming. The version metadata on each value must stay small next to a value this size. |
Stays available during a network partition, at the cost of consistency | No leader per key: any node can coordinate a write, a write can land on stand-in nodes when its home replicas are unreachable, and two versions of a key can exist at once. The store therefore needs a way to detect and settle conflicting versions after the split heals. |
Strong reads when W + R > N; faster, eventual reads below that | The write and read quorum sizes are inputs to each call, not fixed constants. The coordinator sends each write to the full set of N replicas but returns after W confirm, and on a read queries R of them and returns the newest version it gets back. Strong here means the read set overlaps the write set when the quorums are strict; it is not linearizability, since stand-in replicas and concurrent coordinators can break the overlap. |
Low latency on every put and get | One hop from the caller to a coordinator and one parallel round to the replicas. Keep W and R below N so the slowest replica doesn't set the latency, and make each node's local write an append to a log rather than an in-place update. |
Survives the loss of a whole data center | The N replicas of a key are placed in more than one data center, and the default quorum must still be reachable when one center is gone. Hints and repair have to work across centers as well as within one. |
Estimates
| Quantity | Working | Result | What it sizes |
|---|---|---|---|
Replication factor and quorum sizes | Pick N = 3 copies, the configuration the Dynamo paper reports as common in production with R = 2 and W = 2. For strong reads W + R > N means W + R must reach 4: W = 2, R = 2 is the balanced choice; W = 1 forces R = 3 (read all copies); W = 3 forces R = 1 (write all copies). W = 1, R = 1 sums to 2, below N, so it's the fast eventual setting. | N = 3 with W = 2, R = 2 as the default; W = 1, R = 1 when the caller wants speed over freshness | How many copies each key needs and how many must answer, which is the decision the whole round turns on. |
Storage for the key space | 1 billion keys × under 10 KB = under 10 TB for one copy; × 3 copies = under 30 TB. At 10 billion keys, under 300 TB across the cluster. The cap is an upper bound on each value, so these are ceilings. | Under 30 TB of value bytes for a billion keys, under 300 TB for ten billion, across all copies; keys, version metadata, logs and compaction headroom come on top | The disk the ring must hold in total, which with the disk per node gives the node count. |
Keys that move when one node joins | With consistent hashing and K keys on M nodes, the new node takes about K ÷ (M + 1) keys, its own share, from its neighbors on the ring. With hash-mod-M placement, almost all remainders change, so almost all keys move. | One node's share, against nearly the whole key space | The size of a rebalance, and why the ring beats a modulo for growing without downtime. |
Hint window against the outage in the scenario | Cassandra keeps hints for a down node for up to 3 hours by default. The node in the deep-dive scenario is back after 1 hour, a third of the window. | Hinted writes cover the one-hour outage; a node gone longer than 3 hours needs Merkle repair | Which recovery path the midnight outage takes, and where the hand-off to anti-entropy repair sits. |
Core entities
| Entity | What it holds |
|---|---|
Key-value pair | One stored value under one key, tagged with the version information that lets replicas compare copies. |
Node | One physical server, present at several positions on the ring so bigger servers can take more keys. |
Membership list | Each node's view of who is in the cluster and whether they're alive, spread by gossip. |
Hint | A write taken on behalf of a replica that was unreachable, kept until it can be handed back. |
The API
| Endpoint | Notes |
|---|---|
| Any node can take the call and act as coordinator. The optional context is the version information returned by an earlier get; a put that carries it is treated as an update that supersedes those versions, and a put without it is a fresh write. The call returns after W replicas confirm, where W comes from the caller's settings. |
| The coordinator asks R replicas and returns the newest version if the versions it gets back are ordered. If two of them are concurrent, it returns all of them with their clocks as a context, and the caller is expected to merge and put the result back with that context. |
| Operator actions, not something nodes do on their own, so a long network blip doesn't trigger a rebalance. A join gives the node its ring positions and starts moving the keys it now owns from the old owners; a leave does the reverse. Both spread through gossip rather than through a central registry. |
The high-level design
Step 1 of 4
Hash each key to a node on a ring
Start with placement. A client sends put or get to any node, which acts as the coordinator for that call. The coordinator hashes the key onto a ring of positions and the node that owns the next position clockwise stores the value. Each physical node holds several positions (virtual nodes), so a bigger server can take more of them, and when a node joins it takes about its own share of keys from its neighbors instead of reshuffling the whole key space, which is what hash-mod-N placement would do. The weakness is plain: each key lives on one node, so a dead node takes its keys with it, and nothing yet says how anyone learns that a node died.
What breaks first
The deep dives
Tuning the quorum. A client writes a key and reads it straight back through a different node. What does it see, and which settings of N, W and R decide that?
Resolving conflicting writes. Two clients write the same key at the same moment through different nodes while the network is split. When the split heals, how does the store decide what the key holds?
Adding, removing and repairing nodes. A node goes down at midnight and comes back an hour later, and next week several new nodes join. How does the rest of the cluster notice, keep writing, and catch the node up, and how many keys move when the new nodes arrive?
A concept that helps here: Anti-entropy repair with Merkle trees
Concepts this guide uses
Sources
- Design Babushkai: Dynamo paper analysis (evidence-first notes on the SOSP paper)
- Werner Vogels, All Things Distributed: Amazon's Dynamo (paper text, first four sections)
- Alex Xu, System Design Interview: Design a key-value store (ByteByteGo)
- Apache Cassandra documentation: Dynamo (gossip, failure detection, tunable consistency)
- Apache Cassandra documentation: Hints and hinted handoff
- Apache Cassandra documentation: Storage engine
- Riak KV documentation: Conflict resolution
- Riak KV documentation: Causal context
- AxonOps: Cassandra repair architecture (Merkle tree validation)