Design a Distributed Key-Value Store

Advanced Storage & databases

The problem

Design a distributed key-value store like DynamoDB or Cassandra. Clients put and get values by key. The data is too big and too busy for one machine.

You are in a 45-minute interview. This is a classic deep-dive question about partitioning, replication and consistency.

The store is used by many teams for sessions, carts and profiles.

Latency should be a few milliseconds even at huge scale.

You are given

About 100 TB of data before replication.
Millions of operations per second across the cluster.
Machines fail every day. The service must not.
Values are small (a few KB), keys are strings.

What we expect from you

Drive the conversation. Ask questions before drawing anything. State your assumptions out loud so they can be corrected early.
Use numbers. Turn the givens into requests per second, storage and bandwidth. Every later choice should point back to one of them.
Start simple, then evolve. Get a working version on the board first. Add caches, sharding and queues only when a number or a requirement asks for them.
Go deep on the hard parts. For this problem the hard parts are partitioning with consistent hashing, replication with quorums, and handling failures and conflicts.
Name the trade-offs. Say what you chose, what you gave up, and what would make you change your mind.
Think about failure. Point out single points of failure and say what happens when a node, a cache or a whole zone goes down.

Scope

In scope

put, get and delete by key
Partitioning and replication
Failure handling and consistency options
The storage engine on each node

Not required

Secondary indexes and SQL
Multi-key transactions
Billing and multi-tenant quotas

Suggested time

Clarify requirements	4 min
Estimate scale	4 min
API and data model	5 min
High-level design	7 min
Deep dive	15 min
Reliability	5 min
Trade-offs and wrap-up	5 min

What makes an answer great

Uses consistent hashing with virtual nodes, not hash mod N.
Explains N, W, R and why R + W > N matters.
Describes hinted handoff, read repair and anti-entropy for repair.
Handles conflicting writes and names the CAP choice.

Key concepts

Consistent hashing

Place nodes and keys on a ring; a key belongs to the next node clockwise. Adding a node moves only a small share of keys.

Virtual node

One machine appears at many points on the ring so load is even.

Quorum

The number of replicas that must respond. Write quorum W and read quorum R with R + W > N give fresh reads.

Vector clock

A version counter per replica used to tell whether two writes are ordered or concurrent.

Gossip

Nodes exchange state with random peers so information spreads without a master.

LSM tree

Write to a log and memtable, flush sorted files, merge in the background. Very fast writes.

Bloom filter

A compact structure that says 'definitely not here' or 'maybe here'.

Numbers worth remembering

N=3, W=2, R=2 is the usual balanced setting
Replication multiplies storage: 100 TB x 3 = 300 TB
Consistent hashing moves only about 1/N of keys when a node joins

Locked in so far

Decisions you confirm will collect here as you go.

Your design so far