Design a Key Value Store

You're asked to design a distributed key-value store like DynamoDB or Cassandra. It exposes a small API, get(key) and put(key, value), but stores data across a cluster. The system must hold more data than one node can fit, remain available through individual node failures, and let callers choose how much consistency they need.

The small API leaves little product scope to negotiate. Let's spend our time on partitioning, routing, replication, failure recovery, and consistency.

Clarify the requirements

• What consistency do callers need? Ask this first because it affects the rest of the design. Do callers need strong consistency, eventual consistency, or a per-request choice?
• What's the read/write mix? A write-heavy workload favors different storage engines than a read-heavy one.
• How large are values? Kilobytes is the normal assumption. Multi-megabyte values change the storage and replication story.
• Range queries, or point lookups only? Point lookups let you hash-partition freely. Range queries force ordered partitioning and a different set of trade-offs.
• Single region or global? Cross-region replication brings latency and conflict handling that a single-region design avoids entirely.

Assume point lookups, kilobyte values, tunable consistency, and a single region.

Back-of-envelope numbers

• Stored bytes: $100\text{ TB} \times 3 \text{ replicas} = 300\text{ TB}$
• Node count: $300\text{ TB} \div 10\text{ TB/node} \approx 30 \text{ nodes}$ minimum, and realistically more for headroom
• Per-node load: $120\text{k ops/sec} \div 30 \text{ nodes} \approx 4\text{k ops/sec}$, which is comfortable

High-level architecture

Components

1. Coordinator. Any node that receives a request can coordinate it; the cluster has no dedicated master for this role.
2. Partition ring. The consistent-hashing ring that maps a key to the nodes responsible for it.
3. Replicas. The N nodes holding copies of that key, typically three.
4. Gossip. Nodes exchange membership and health information peer to peer so the cluster can track which nodes are alive.

Deep dive 1: partitioning with consistent hashing

The simple approach, hash(key) mod N, works only while N remains fixed. Adding one node to a nine-node cluster changes the result for nearly every key and forces most of the data to move at once.

Consistent hashing places keys and nodes on the same circular space. A key belongs to the first node clockwise from its position. When a new node joins, it takes over only the arc between itself and its predecessor, so roughly 1/N of the keys move.

Plain consistent hashing can distribute data unevenly because random node positions create arcs of different sizes. Use virtual nodes so each physical machine claims many positions on the ring, typically a few hundred. The larger sample evens out the load and lets you give more positions to machines with greater capacity.

Deep dive 2: replication and tunable consistency

Each key is stored on N nodes, found by continuing clockwise around the ring past the first owner (replication strategies covers the general mechanics). Requests then use two more parameters:

• W, the number of replicas that must acknowledge a write before it's considered successful.
• R, the number of replicas that must respond to a read before it's returned.

When R + W > N, the read and write sets overlap by at least one node. A read will therefore contact at least one replica that acknowledged the latest write. State this inequality and connect it directly to the overlap guarantee.

Treat these as per-request parameters rather than one cluster-wide setting:

• W=N, R=1 makes reads fast and writes slow, suiting read-heavy data that rarely changes.
• W=1, R=N does the opposite, suiting write-heavy ingestion.
• W=2, R=2 with N=3 is the balanced default, tolerating one node failure on either path.
• W=1, R=1 abandons the overlap guarantee entirely for maximum speed, appropriate for data where staleness is harmless.

Deep dive 3: handling failures without blocking writes

If one replica is down, a write that requires W acknowledgements may fail. Hinted handoff lets an availability-oriented system continue through a short outage.

With hinted handoff, another node temporarily stores the write on behalf of the unavailable replica, along with a hint identifying its intended owner. When that node returns, the temporary holder delivers the hint and restores the missing copy.

Replicas still need reconciliation after longer outages or drift that hints do not cover. Read repair compares versions returned during a read and sends the newest version to any lagging replica. This repairs popular keys during normal traffic. Anti-entropy repairs cold keys using Merkle trees over each replica's key range. Replicas exchange a small number of hashes to locate differing subranges instead of comparing every key.

Deep dive 4: conflicting writes

When writes can succeed without every replica, two clients may update the same key concurrently and reach different subsets of replicas. Neither version clearly comes after the other, so the system needs a conflict policy.

Last-write-wins chooses a version by timestamp. It is simple but silently discards the other write, which may be acceptable for a cache and dangerous for a shopping cart. It also depends on reasonably synchronized clocks.

Vector clocks track causality instead of wall-clock time. Each replica maintains a counter, and the vector attached to a value shows whether one version descends from another or whether the two diverged. If they diverged, return both versions and let the application merge them. Dynamo's canonical example is a shopping cart, where the merge takes the union of the items.

Choose a conflict policy based on the data and explain why silent loss is or is not acceptable.

Deep dive 5: what's on disk

Choose the storage engine based on the workload. An LSM tree buffers writes in memory, flushes sorted segments to disk, and merges them in the background. Its writes are sequential and fast, but reads may consult several segments. A Bloom filter on each segment lets the reader skip segments that cannot contain the key. A B-tree updates data in place, improving reads at the cost of random writes.

For a write-heavy distributed store, choose an LSM tree because sequential writes outperform random writes on every storage medium.

Common pitfalls

• hash(key) mod N with no answer for adding a node. Capacity changes are certain, and this remaps everything.
• Consistent hashing without virtual nodes. Load ends up meaningfully uneven.
• One consistency setting for the whole cluster. Tunability is the feature.
• Last-write-wins with no discussion. Fine for some data, silent loss for the rest.
• No plan for a replica that was down. Hinted handoff and anti-entropy are what make availability real rather than aspirational.

Leveling signals

Related lessons

Design a Distributed Message QueueHard

Build the broker itself: topics, partitions, consumer offsets, and durability.

Design DropboxHard

Sync files across a user's devices, handling large files and version history.