Design a Distributed Key-Value Store (System Design Interview)

Consistent hashing, replication, N/W/R quorums with an interactive lab, conflict resolution with version vectors, gossip, hinted handoff, Merkle trees and…

Designing a key-value store: common questions

What does R + W > N mean?

With N replicas, a write waits for W acknowledgements and a read for R replies. If R + W > N, every read set overlaps every write set, so a read always reaches at least one replica with the latest acknowledged write.

How does a key-value store resolve conflicting writes?

Either last write wins by timestamp, which can silently drop writes when clocks drift, or version vectors that detect concurrent writes and keep both values for the client or a CRDT to merge.

Related chapters

Keep learning

Overview

The client gets an error. Lower W (or use a sloppy quorum with hinted handoff) to keep writes available, at the cost of weaker guarantees. Reads need R live replicas. A smaller R keeps reads up during failures. Lucky overlap. With R + W ≤ N some reads can miss the write. Stale read: every replica the read asked still has the old value. Lab · tune N, W and R, then knock out replicas Replicas: click to crash or restore cart v2 cart v1 system design · database-heavy designs · key-value store Design a distributed key-value store A key-value store answers two questions: “what is stored under this key?” and “store this under that key”. On one machine that is a hash map. Across a hundred machines that keep failing, it becomes a lesson in partitioning, replication, quorums and conflicts. This is the design behind DynamoDB, Cassandra and Riak.

1. Pin down what you are building

Ask before you draw. The answers change the design more than any box you add later. get(key), put(key, value), delete(key). No joins, no range scans, no multi-key transactions. Data shape Keys up to a few hundred bytes, values under ~100 KB. Big files go to object storage, with the key pointing at them. Billions of keys, hundreds of thousands of requests a second, data that does not fit on one disk. The key choice The example throughout: a shopping-cart service. Losing an “add to cart” costs money, so writes must keep working even when a data centre is struggling. Seeing a slightly old cart for a second is acceptable.

2. Start with one machine

A single node is an in-memory hash map plus a write-ahead log. Every put is appended to the log on disk before it is acknowledged, so a crash loses nothing: on restart, replay the log. A periodic snapshot keeps the replay short. simple ops a second on one good server practical data per node before rebuilds hurt failure that takes everything offline Three limits push us off one box: data size, request rate, and a single point of failure. Partitioning solves the first two. Replication solves the third.

3. Partition with consistent hashing

client request hash → 0x7a3… position on the ring walk clockwise next N−1 distinct nodes the other replicas The list of N nodes responsible for a key is its preference list. Skip virtual nodes that belong to a physical node already chosen. Place replicas in different racks or zones, not just different nodes. Three copies on one rack die together with one switch. Deeper: consistent hashing.

4. Replicate, and decide how many must agree

Good for Default: strong-ish reads and writes Both survive one replica down Medium latency on both Write-heavy logs, fast ingestion Writes never wait Reads fail if any replica is down Read-heavy config Fastest reads One down replica blocks writes Counters, presence, caches Fastest and most available Stale reads are normal Quorums give overlap, not full linearizability: concurrent writes and sloppy quorums can still surprise you.

5. Concurrent writes and conflicts

With W < N and writes accepted on both sides of a network split, two replicas can hold different values for the same key. Someone has to pick a winner. Last write wins (timestamps) Simple and what Cassandra does by default. But clocks drift: a write stamped 10:00:00.120 on a fast clock beats a later one at 10:00:00.090 on a slow clock, and the later write silently disappears. Safe only when values are replaced whole and losing one is acceptable. Version vectors (keep both)

6. Handle failures without a leader

Detect: gossip Every second each node swaps its membership list with a few random peers. A node whose heartbeat counter stops rising is suspected, then marked down. No central monitor to fail. Short outage: hinted handoff If a replica is down, the write goes to the next healthy node with a note: “this belongs to node C”. When C returns, the hint is delivered and deleted. Drift: read repair When a read sees replicas disagree, it returns the newest value and writes it back to the stale ones in the background. Long outage: anti-entropy A whole data centre going away is the same problem, bigger: put the replicas of each key in at least two regions and use a local quorum for latency, accepting that the remote region catches up asynchronously.

7. Inside one node: the storage engine

Write-heavy key-value stores usually use an LSM tree rather than a B-tree, because it turns random writes into sequential ones. Commit log append, fsync sorted, in memory when ~64 MB full SSTable files immutable, sorted merge, drop old versions A read checks the memtable, then each SSTable from newest to oldest. A Bloom filter per file answers “definitely not here” in memory, so most files are never touched. Compaction keeps the number of files small, at the cost of background disk I/O. LSM tree Fast, sequential Slower, in-place pages Point reads Several files, Bloom filters help One path down the tree Old versions until compaction Fragmented pages Used by Cassandra, RocksDB, ScyllaDB Postgres, MySQL InnoDB

8. What to say in the interview

Clarify value size, scale, and whether the system should favour availability or consistency during a partition. Explain N, W, R and the R + W > N overlap rule, then pick numbers for the use case. Choose a conflict strategy per data type: last write wins, version vectors with merge, or a CRDT. Name the failure tools: gossip, hinted handoff, read repair, Merkle-tree anti-entropy. Describe the LSM write and read path, with Bloom filters and compaction. Related: quorums in practice · CAP theorem · replication

More courses

Jobs, linked to lessons — Browse jobs where every requirement links to the chapter that teaches it. See how ready you are, how long the gap takes to close, and which listings look stale.
Match a job post to courses — Paste a job post. Each skill is matched to a track here and put in learning order, foundations first.
React from open source with patterns — Patterns extracted from Material UI, Radix, React Aria, React Hook Form, Redux Toolkit, TanStack, and Next.js — not slides about hooks.
Database in depth — How a query becomes work. Indexes, isolation, locks, and the plans that explain why a page is slow — not an ORM tour.
Build a real API with NestJS — One ticket-booking API, built in order: a plain Node server first, then NestJS modules, validation, a real database, and the features real clients lean on.
Microservices — Microservice patterns one diagram at a time: how to split a monolith, how services talk, and how data stays consistent without distributed transactions.
Kafka — A beginner-to-senior path through event logs, reliable delivery, production operations, and disaster recovery.
AI engineering for software engineers — Eight free reads, in order, for software engineers moving into AI: when to build an agent, how to build one, how to test it, and how the model works underneath.
Frontend system design — How a UI is sliced when it is a product, not a page: ownership of state, cache, routes, and what happens when the network lies.
TypeScript in depth — The type system as a design tool. Inference, narrowing, generics, and the errors that mean the model is wrong — not a catalog of utility types.
CSS in depth — See the box, then the page. Visual chapters from the box model through Flexbox surprises, Grid, selectors, and units, then backgrounds, shapes, and visual effects, each with a playground.
Accessibility — Foundations first (WCAG in plain words, semantic HTML, lists, alt text), then hands-on HTML labs, a full pass of WAI-ARIA 1.3, and a final fix-the-page challenge.
Docker — What an image is, why layers cache, and how containers find each other on a network.
Redis — Fifteen Redis patterns, one picture each: cache, session, lock, counter, rate limiter, queue, and when Redis is the wrong tool.
Kubernetes — Kubernetes from zero to operators: why it exists, Pods, Deployments and Services, then configuration, networking, storage, scheduling, scaling and security.