Skip to content

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
Asked at
Practice this question

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

AskWhy it mattersA 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.

The requirements menu

RequirementScopeWhy

put(key, value) stores a value under a key

Core

The write path: hash the key, find its replicas, send the value to all of them and return after enough have confirmed.

get(key) returns the value stored under a key

Core

The read path. It also has to cope with replicas that disagree, which is where versioning comes in.

The caller can tune consistency against latency

Core

The write and read quorum sizes are per-call settings, so one store serves a session cache and a config registry with different trade-offs.

Capacity grows by adding nodes, with no downtime

Core

Forces consistent hashing: a new node takes a share of the keys from its neighbors on the ring while the rest of the cluster keeps serving.

delete(key) removes a key

Optional

Worth taking if asked, because it tests whether you know a delete must be stored as a marker (a tombstone) that replicates like a write; a plain removal would be undone by a replica that still holds the old value.

A time to live on each key

Optional

Cheap to add on the storage engine, since expired entries can be dropped during compaction. Take it if the callers are caches or sessions; leave it otherwise.

Fetch several keys in one call

Optional

Convenient for callers, and the coordinator can fan the lookups out in parallel. Leave it unless asked: it adds nothing to the hard parts of the design.

Compare-and-set on a single key

Out of scope

A conditional write needs the replicas to agree on the current version first, which takes a consensus protocol for that key, with or without a stable leader. Name it as a different consistency model and park it.

Values larger than a few megabytes

Out of scope

Large values want chunking and a blob store. Say the design assumes small values, which is why a replica can copy a value whole.

Range scans and secondary indexes

Out of scope

A hash ring scatters neighboring keys on purpose, so a range scan would touch most nodes. Ordered partitioning is a different design.

Transactions across several keys

Out of scope

Keys live on different nodes, so a multi-key transaction needs cross-node coordination that a leaderless store doesn't have.

Authentication and multi-tenancy

Out of scope

The store sits behind trusted services inside one network. A gateway or per-namespace quotas can come later without changing the ring.

Non-functional requirements

RequirementWhat 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

QuantityWorkingResultWhat 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

EntityWhat 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

EndpointNotes

put(key, value, context?) → ok

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.

get(key) → value, or several versions with their vector clocks

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.

join(node) and leave(node) for cluster membership

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

callhashownerClientCoordinator nodeHash ringNode A

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.

callhashownercopygossiphintedreplaycompareappendspreadClientCoordinator nodeHash ringNode ANode BMembership listHints for BMerkle treesLog, memtable,SSTablesOther data center
The whole design

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?

A concept that helps here: Quorums and tunable consistencyA concept that helps here: Consistency modelsA concept that helps here: Replication and read replicas

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?

A concept that helps here: Conflict resolutionA concept that helps here: Clocks and orderingA concept that helps here: Consistency models

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: Heartbeats and presenceA concept that helps here: Consistent hashing

Concepts this guide uses

Sources

  1. Design Babushkai: Dynamo paper analysis (evidence-first notes on the SOSP paper)
  2. Werner Vogels, All Things Distributed: Amazon's Dynamo (paper text, first four sections)
  3. Alex Xu, System Design Interview: Design a key-value store (ByteByteGo)
  4. Apache Cassandra documentation: Dynamo (gossip, failure detection, tunable consistency)
  5. Apache Cassandra documentation: Hints and hinted handoff
  6. Apache Cassandra documentation: Storage engine
  7. Riak KV documentation: Conflict resolution
  8. Riak KV documentation: Causal context
  9. AxonOps: Cassandra repair architecture (Merkle tree validation)
Sign in to report a mistake