Design a distributed key-value store (Dynamo-style)

Goal: a key-value store (put(key, value), get(key)) that scales out, stays available during failures, and has tunable consistency. This follows the ideas of Amazon's Dynamo paper, which influenced Cassandra and Riak.

Requirements

• Huge data and high throughput by adding nodes.
• Always writable and readable even with some nodes down (favour availability).
• Low latency.
• Tunable consistency.

Partitioning

Use consistent hashing with virtual nodes: keys and nodes are placed on a ring, and each key belongs to the next node clockwise. Adding or removing a node moves only a small share of keys.

Replication

Each key is stored on N consecutive nodes on the ring (for example N=3). Any node can act as the coordinator for a request.

Quorums: R, W and N

• W: how many replicas must confirm a write.
• R: how many replicas must answer a read.
• If R + W > N, reads and writes overlap on at least one replica, so a read sees the latest write.

Examples with N=3: W=2, R=2 gives consistency; W=1, R=1 gives speed and availability but possibly stale reads. You choose per use case.

Surviving failures

• Sloppy quorum and hinted handoff: if a replica is down, another node temporarily accepts the write along with a "hint" and forwards it when the replica returns. This keeps writes available.
• Failure detection by gossip: nodes exchange heartbeat info periodically, so the cluster learns who is alive without a central master.
• Read repair: when a read finds a stale replica, the coordinator updates it.
• Anti-entropy with Merkle trees: nodes compare tree hashes of their data to find and fix differences cheaply in the background.

Conflicts

With availability first, two clients can write different values to the same key on different replicas. Resolve by last-write-wins (simple, can lose data) or vector clocks that detect concurrent versions so the application (or a CRDT) can merge them.

Storage engine on each node

Most such stores use an LSM tree:

1. Write to a commit log (for durability) and an in-memory memtable.
2. When full, flush the memtable to an immutable sorted file (SSTable).
3. Reads check the memtable, then SSTables (a Bloom filter skips files that cannot contain the key).
4. Compaction merges files in the background.

This makes writes very fast because they are sequential.

Trade-offs

Availability and partition tolerance are chosen over strict consistency. Applications must handle stale reads and conflicts.

Takeaway: consistent hashing, N replicas, tunable R/W quorums, hinted handoff, gossip, repair, and an LSM-tree engine give a scalable, available key-value store.

---

System Design series, Part 4 (designing the infrastructure): 3 of 4. Previous: Design a distributed cache.