Design a Distributed Key-Value Store (DynamoDB) — System Design

🔴 High-Level Design · Super-senior · the Dynamo/Cassandra deep dive

"Design a distributed key-value store like DynamoDB or Cassandra." This is one of the hardest, most rewarding design questions — it's essentially the famous Amazon Dynamo paper, and it weaves together almost every fundamental: consistent hashing, replication, CAP, consistency models, and LSM-trees. If you can walk this, you understand distributed systems. Let's go deep but stay clear.

Step 1 — Requirements

• Functional: get(key) and put(key, value) over a huge dataset; durable (data survives on disk, unlike a cache).
• Non-functional: massive scale (petabytes across thousands of nodes), always available (writes never rejected — Amazon's "add to cart must never fail"), low latency, and tunable consistency. Per CAP, this is a deliberate AP choice: favour availability, accept eventual consistency.

Step 2 — Partitioning: consistent hashing

🔴 The data won't fit on one node, so we partition with consistent hashing: nodes and keys sit on a ring, each key owned by the next node clockwise. Adding/removing a node only moves ~1/N of the data, and virtual nodes keep the load balanced and spread a failed node's load across many others. This is the partitioning backbone — say it first.

Step 3 — Replication

🔴 For durability and availability, each key is stored on N nodes — the node that owns it on the ring plus the next N−1 nodes clockwise (its "preference list"). If one node dies, N−1 copies remain, and reads/writes just use the others. N is typically 3.

Step 4 — Tunable consistency with quorums

🔴 This is the elegant heart of the design. Instead of always waiting for all N replicas (slow) or just one (unsafe), use a quorum:

• W = replicas that must acknowledge a write.
• R = replicas that must respond to a read.

If you ensure R + W > N, the read set and write set always overlap by at least one node — so a read is guaranteed to see the latest write (strong-ish consistency). And you can tune it: W=1 is fast writes but weaker reads; R=1 is fast reads; W=N is strongest but least available. Dynamo-style systems let you dial R and W per operation to trade consistency against latency and availability. Explaining R + W > N is the single most impressive thing you can say in this interview.

Step 5 — Handling failures gracefully

🔴 In an AP system, writes must succeed even during failures. Three classic mechanisms:

• Hinted handoff: if a replica node is temporarily down, another node accepts the write on its behalf and holds a "hint"; when the node recovers, the write is handed off to it. Writes never fail for a transient outage.
• Anti-entropy with Merkle trees: replicas periodically compare a tree of hashes to find which data has diverged and sync only the differences efficiently — repairing inconsistencies in the background.
• Gossip protocol: nodes share membership/health info peer-to-peer, so the cluster learns who's alive without a central coordinator.

Step 6 — Conflict resolution

🔴 Because writes can happen on different replicas during a partition, two versions of a key can conflict. Two approaches:

• Last-Write-Wins (LWW): keep the version with the latest timestamp. Simple, but can silently drop a write.
• Vector clocks: track causality so the system can detect concurrent conflicting writes and either merge them or return both versions to the client to resolve (Dynamo's shopping-cart approach — union the carts). More correct, more complex.

Step 7 — The storage engine

🟠 Each node needs to store its data on disk, write-heavily. That's exactly what an LSM-tree is for (memtable → SSTables → compaction), with a Bloom filter per SSTable to skip files on reads. This is why Cassandra and friends are built on LSM engines — high write throughput is a core requirement.

The interview-ready walkthrough

"I'd build an AP key-value store. Partition keys with consistent hashing + virtual nodes, and replicate each key to N nodes on its preference list. For consistency I'd use quorums with R + W > N so read and write sets overlap — tunable per operation for the latency/consistency trade. To stay available through failures I'd use hinted handoff, anti-entropy with Merkle trees, and a gossip protocol for membership. Conflicts resolve via vector clocks (or LWW), and each node stores data in an LSM-tree for write throughput." That single answer touches nearly every distributed-systems fundamental — which is exactly why it's the ultimate HLD question."

What to read next

• Consistent Hashing · CAP Theorem — the theory this rests on
• Database Replication — quorums and replica sync in depth
• LSM-Tree vs B-Tree — the per-node storage engine
• ← The complete System Design guide (hub)

← Design a distributed cache · Design YouTube →