CHAPTER 14
Design a Distributed Key-Value Store
A Dynamo-style store: partitioning, replication, quorums and the storage engine
Source: PDF pp. 50–51
| Functional requirements | Non-functional requirements and scale |
|---|---|
| - put(key, value) and get(key) (values up to ~1 MB) - Horizontal scale to hundreds of nodes and petabytes - Tunable consistency per request | - Always writable: highly available even during failures and partitions - Low latency (p99 < 10 ms), predictable under load - Incremental scalability: add nodes with minimal data movement - Automatic failure detection and recovery, no single point of failure |
| Problem | Technique | Chapter |
|---|---|---|
| Spread data and add nodes cheaply | Consistent hashing with virtual nodes | 4 |
| Survive node and AZ failures | Replicate each key to N nodes on distinct racks/AZs (preference list) | 6 |
| Tunable consistency | Quorums: W + R > N for strong-ish reads; W=1 for fastest writes | 7 |
| Stay writable during failures | Sloppy quorum + hinted handoff: another node accepts the write and forwards it later | 7 |
| Detect conflicts | Vector clocks (or last-write-wins by timestamp) with client-side or CRDT merge | 7 |
| Heal divergence | Read repair on reads; anti-entropy using Merkle trees in the background | 7, 12 |
| Know who is alive | Gossip protocol for membership and failure detection | 7 |
| Fast writes, durable data | WAL + memtable, flushed to SSTables, compacted in the background (LSM) | 6 |
Request flow p. 51
1. Client sends put(k, v) to any node (or a smart client library); that node (or a router) hashes the key and finds the coordinator: the first node clockwise on the ring. 2. Coordinator writes locally (WAL + memtable) and forwards to the other N-1 replicas in parallel; it returns success after W acknowledgements (e.g. W = 2 of 3). 3. get(k): the coordinator asks R replicas (R = 2), compares versions (vector clocks), returns the newest or all concurrent siblings, and triggers read repair for stale replicas. 4. If a replica is down, a healthy node outside the preference list stores the write with a hint and hands it over when the replica returns.
Review questions for this chapter have not been written and reviewed yet. The chapter text above is the full source content.
Try it
References
System Design & AI System Design: The Complete Guide — 2026 Edition, pp. 50–51; figures 35.
Tip: use ← and → keys to move between chapters.