Design a Key-Value Store

This is the problem where nearly every Database Fundamentals and Distributed Systems lesson in this course gets applied at once — a distributed key-value store is the classic Dynamo/Cassandra-shaped design, and it's included as an "easy" problem here specifically because most of its hard sub-problems already have their own dedicated lessons to draw on directly. Following the framework from How to Answer a System Design Interview Question.

1. Requirements

Functional:

put(key, value) and get(key) — nothing more; no queries, no joins, no secondary indexes.
The store must survive individual node failures without losing data or becoming unavailable.

Non-functional:

Favor availability over strict consistency — a classic AP choice under the CAP Theorem: the store should keep answering get/put even during a network partition, accepting that different nodes might briefly disagree.
Must scale horizontally by adding nodes, with no single node holding the entire dataset.

Scale estimate: assume a dataset far too large for one machine — hundreds of millions of keys, terabytes of data — which is the entire premise that makes this a distributed-systems problem rather than "just run Redis on one box."

2. API Design

Deliberately minimal, matching the functional requirements exactly:

PUT /keys/{key}   body: { value: bytes }
GET /keys/{key}   returns: { value: bytes }

3. Data Model

There isn't a schema in the traditional sense — every value is an opaque blob addressed by its key, which is exactly what makes this store horizontally partitionable with no cross-key relationships to preserve: unlike a relational schema, no key's value depends on any other key's value, so keys can be split across machines with no join ever needed to reconstruct an answer.

4. High-Level Design

System Design Lab

Every major piece of this design is a direct application of an existing lesson rather than something to invent from scratch:

Partitioning — Consistent Hashing assigns each key to a node, so adding or removing a node only remaps a small fraction of keys instead of the whole dataset.
Replication — each key is stored on N nodes (not just one), the same Data Replication idea applied per-key across the ring instead of per-shard.
Membership — nodes learn about each other joining or leaving via Gossip Protocol, with no central coordinator tracking cluster state.

5. Deep Dive: quorum reads/writes and conflict resolution

Because each key is replicated to N nodes, a write doesn't need to reach all N before being acknowledged — it needs to reach W of them, and a read needs to hear from R of them, chosen so that W + R > N. That inequality guarantees any read quorum and any write quorum share at least one common node, so a read is mathematically guaranteed to see the most recent acknowledged write somewhere in the nodes it queries — the same overlapping-majority idea Consensus Algorithms uses for leader election, applied here to reads and writes directly instead of to electing one leader.

This tunable quorum is exactly what makes the AP choice from the requirements concrete rather than abstract: a smaller W (say, W=1) makes writes fast and available even if most replicas are unreachable, at the cost of a real chance that two concurrent writes to the same key, accepted by different nodes, now conflict. Resolving that conflict — deciding which of two concurrent values for the same key "wins," or keeping both and letting the application decide — is the one genuinely hard problem this design can't just borrow from an existing lesson; real systems use either last-write-wins (simple, but can silently drop a legitimate concurrent write) or vector clocks (correctly detects concurrent writes as conflicting, at the cost of more bookkeeping and needing the application to resolve ambiguous cases).

6. Tradeoffs

Every knob in this design — replication factor N, and the quorum sizes W and R — is a direct dial on the same CAP tradeoff: larger W and R push toward stronger consistency at the cost of latency and availability during a partition (more nodes must respond); smaller values push toward availability at the cost of a real chance of reading stale or conflicting data.

The conflict-resolution choice from the deep dive above is a smaller version of the same tradeoff, applied to correctness instead of latency: last-write-wins needs no extra bookkeeping and always resolves a conflict automatically, but does so by silently discarding one of two genuinely concurrent writes — the client that "lost" gets no signal anything was dropped. Vector clocks fix that by correctly detecting two writes as concurrent rather than picking one arbitrarily, but push the harder question — which value should this key actually hold — up to the application, which now has to know how to merge or choose between conflicting versions instead of the store deciding silently on its behalf.

Small write quorum (fast, AP-leaning) vs. large write quorum (safer, more CP-leaning): pros and cons

Small W

Writes succeed and stay fast even when several replicas are unreachable
Higher write availability during a partition
Lower write latency — fewer nodes need to acknowledge before returning

Large W

Writes fail or stall if too many replicas are briefly unreachable
Higher write latency, waiting on more nodes to acknowledge
Less write availability during a partition, since more nodes must be reachable to succeed

1. Requirements​

2. API Design​

3. Data Model​

4. High-Level Design​

5. Deep Dive: quorum reads/writes and conflict resolution​

6. Tradeoffs​

Small write quorum (fast, AP-leaning) vs. large write quorum (safer, more CP-leaning): pros and cons​

Further Reading​