Design a Key Value Store

You're asked to design a distributed key-value store: a service with an interface as simple as get(key) and put(key, value), backed by a cluster of machines rather than one. It should hold more data than any single node can store, stay available when individual nodes fail, and let callers choose how much consistency they need. Think DynamoDB or Cassandra rather than Redis on one box.

The API being two functions is what makes this question hard rather than easy. There's no product to scope, no features to negotiate, and no way to spend the interview on requirements. Every minute goes into the distributed systems mechanics.

Clarifying the requirements

• What consistency do callers need? This is the first question, because it determines everything downstream. Strong consistency on every read, eventual consistency, or tunable per request?
• 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, 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. Whichever node receives the request. There is no special master; any node can coordinate any request.
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 agrees on who is alive.

Deep dive 1: partitioning with consistent hashing

The naive approach, hash(key) mod N, works until N changes. Add one node to a nine-node cluster and nearly every key maps somewhere new, which means moving nearly all of your data at once.

Consistent hashing solves this by hashing both keys and nodes onto the same circular space. A key belongs to the first node found walking clockwise from its position. When a node joins, it takes over only the arc between itself and its predecessor, so roughly 1/N of the keys move rather than all of them.

Plain consistent hashing distributes unevenly, because randomly placed nodes create arcs of very different sizes. The fix is virtual nodes: each physical machine claims many positions on the ring, typically a few hundred, so the law of large numbers evens out the load. Virtual nodes also let you weight heterogeneous hardware, by giving a larger machine more positions.

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 set and write set are guaranteed to overlap by at least one node, so any read sees at least one replica holding the latest write. That inequality is the whole mechanism, and being able to state it is a large part of the signal in this question.

The interesting part is that these are per-request knobs, not one global 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 a replica is down, a write requiring W acknowledgements could simply fail. Availability-oriented systems don't do that.

Hinted handoff lets another node temporarily accept the write on behalf of the unavailable replica, storing it with a hint about where it really belongs. When the down node returns, the hint is delivered and the data lands where it should. Writes keep succeeding through short outages.

For longer outages and for drift that hints don't cover, replicas need to reconcile. Read repair compares the versions returned during a read and pushes the newest to whichever replica was behind, which fixes popular keys as a side effect of normal traffic. Anti-entropy handles the cold keys nobody reads, using Merkle trees, a hash tree over each replica's key range, so two replicas can find exactly which subranges differ by exchanging a small number of hashes rather than comparing every key.

Deep dive 4: conflicting writes

Once writes can succeed without every replica participating, two clients can write the same key concurrently and each write can land on a different subset. Both are "the latest," and you need a policy.

Last-write-wins picks by timestamp. It's simple and it silently discards one of the two writes, which is acceptable for a cache and dangerous for a shopping cart. It also requires reasonably synchronized clocks, which is its own hazard.

Vector clocks track causality instead of wall-clock time. Each replica maintains a counter, and the vector of counters attached to a value tells you whether one version descends from another or whether they truly diverged. When they've diverged, the system can't decide alone, so it returns both versions and lets the application merge them. Dynamo's canonical example is the shopping cart, where the correct merge is the union of the items.

State which one you're choosing and why, because it's a product decision as much as a technical one.

Deep dive 5: what's on disk

Values have to persist, and the storage engine choice follows the write pattern. An LSM tree buffers writes in memory, flushes sorted segments to disk, and merges them in the background. Writes are sequential and fast; reads may consult several segments, which is why a Bloom filter per segment is standard to skip the ones that definitely don't hold the key. A B-tree updates in place, giving faster reads at the cost of random writes.

For a write-heavy distributed store, LSM is the usual answer, and knowing why is worth a sentence: sequential writes beat random ones 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 the answer

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.