A giant set of lockers where each key opens exactly one locker. The lockers are spread across many rooms, and every item is copied into three rooms, so losing a room loses nothing.
Problem Statement
Design a distributed key-value store like Amazon Dynamo, Cassandra or Riak: a simple put(key, value) / get(key) API that holds more data than any single machine, keeps working when machines fail, and scales by adding nodes. It is the problem that ties together partitioning, replication, consistency trade-offs and failure detection.
Functional Requirements
put(key, value) and get(key); delete(key).
Values up to ~1 MB; keys are opaque strings.
Tunable consistency per request (fast/eventual vs quorum).
Out of scope: range queries, secondary indexes, transactions.
Non-Functional Requirements
Scale: tens of TB and 100K+ ops/s; grow by adding nodes.
High availability: writes accepted even when some replicas are down ("always writable" in the Dynamo tradition).
Low latency: single-digit ms at p99 within a region.
Durability: data replicated (N = 3) across failure domains.
Core Entities
Key / Value / Version: each value carries a version (timestamp or vector clock).
Node: a storage server with positions (virtual nodes) on the hash ring.
Partition / preference list: the N nodes responsible for a key's range.
API Design
PUT /kv/{key} body: value ?w=1|quorum|all -> 200 { version }
GET /kv/{key} ?r=1|quorum|all -> 200 { value, version } | 404
DELETE /kv/{key} -> 200 (writes a tombstone)
High-Level Design (HLD)
The write succeeds after W = 2 acks; reads ask R = 2 nodes, and W + R > N guarantees overlap.
client -> any node (acts as COORDINATOR for this request)
|
| hash(key) on the consistent-hash ring
v
preference list for key k: [ node B, node C, node D ] (N = 3)
|
write: send to all 3, succeed after W acks
read: ask R replicas, return newest version, repair stale ones
Membership + failure detection: gossip protocol between all nodes
Each node's storage engine: commit log + memtable + SSTables (LSM tree)
Replication: each key stored on the next N distinct nodes clockwise.
Leaderless: any replica accepts reads/writes; quorums give the consistency knob.
Low-Level Design (LLD)
Writes are appends plus a memory insert; reads check the memtable then SSTables (Bloom filters skip files).
Quorums
N = replicas, W = acks needed for a write, R = replies needed for a read
W + R > N -> read set and write set overlap -> a read sees the latest acked write
N=3, W=2, R=2 balanced (typical "quorum")
N=3, W=1, R=3 fast writes, slow reads
N=3, W=3, R=1 fast reads, writes fail if any replica is down
W + R <= N -> faster and more available, but reads may be stale (eventual)
Versioning and conflicts
With leaderless writes, two clients can update the same key concurrently on different replicas. Options: last-write-wins by timestamp (simple; can silently drop a write; used by Cassandra) or vector clocks that detect concurrent versions and return both "siblings" for the application to merge (Dynamo's shopping cart). Deletes write a tombstone so a stale replica can't resurrect the value; tombstones are purged after a grace period.
Handling failures
Sloppy quorum + hinted handoff: if a preference-list node is down, the write goes to the next healthy node with a "hint"; when the owner returns, the hint is handed back. Writes stay available.
Read repair: when a read sees replicas with older versions, the coordinator writes the newest back to them.
Anti-entropy: replicas periodically compare data using Merkle trees (hash trees over key ranges) and sync only differing ranges.
Gossip: each node periodically exchanges membership/heartbeat info with random peers; a node not heard from for a while is suspected down.
Storage engine (per node): LSM tree
write: append to commit log (durability) -> insert into memtable (sorted, in memory)
memtable full -> flush to an immutable sorted file (SSTable) on disk
read: memtable -> SSTables newest to oldest (Bloom filter per SSTable skips
files that can't contain the key)
background compaction merges SSTables, dropping overwritten values and old tombstones
LSM trees turn random writes into sequential ones, which is why they suit write-heavy stores.
Follow-up Questions
How would you make this strongly consistent instead?
Use a leader per partition with consensus (Raft/Paxos) replicating a log to followers, as in etcd, Spanner or CockroachDB. You gain linearizable reads/writes and lose writes on partitions that can't reach a majority.
How do you add a node without downtime?
It takes ownership of some virtual-node ranges; the previous owners stream those ranges to it in the background while still serving, then the ring update is gossiped and routing switches.
Why are reads slower than writes in an LSM store?
A write is an append plus a memory insert; a read may have to check the memtable and several SSTables. Bloom filters, compaction and caches keep read amplification in check.