Case study: distributed key-value store

Amazon's 2007 Dynamo paper describes a key-value store that always accepts writes. Shopping carts had to take writes even when disks failed or networks split. The design favors availability, offers tunable consistency, and resolves conflicts when data is read. Cassandra and Riak carry the same ideas, even as managed products later added stronger options.

This case study rebuilds that design, so you can defend each setting in an interview.

Concepts in this section

Read the pages in this order.

Requirements

• get(key) and put(key, value) on opaque bytes, by primary key only.
• Scale to petabytes, and grow by adding nodes.
• Keep working through replica and network failures.
• Tunable consistency through quorum settings.
• Visible conflicts when concurrent writes diverge.

Non-goals are secondary indexes, multi-row SQL transactions and cross-item ACID.

The request path

put("user#42:cart", bytes):
  1. Coordinator hashes the key to a preference list, for example [n3, n7, n9]
  2. Coordinator advances its vector clock entry
  3. Send the write to n3, n7 and n9, or to stand-ins if one is down
  4. Wait for W = 2 acks, then return 200 to the client
  5. Remaining replicas catch up asynchronously

get("user#42:cart"):
  1. Same preference list
  2. Wait for R = 2 responses
  3. If versions conflict, return siblings for the application to merge
  4. Read repair: push the newest version to stale replicas

With N = 3, R = 2, W = 2, the overlap rule holds. Any node can coordinate, because the role is set per request.

Design choices at a glance

Pick based on whether losing a write or blocking a write hurts more during a partition.

Common mistakes

• Equating tunable quorums with linearizability. R + W > N still allows stale reads under races. See consistency.
• Thinking DynamoDB is the Dynamo paper. The managed product replicates each partition with consensus, and it offers strong reads.
• Deleting tombstones too early. A deleted key can come back when a lagging replica resends it.

Key takeaways

• Consistent hashing spreads keys, and minimizes movement when nodes join or leave.
• N replicas and quorums R and W set the trade-off between freshness and availability.
• Vector clocks detect concurrent writes, and the application merges siblings.
• Hinted handoff keeps writes going during failures, and anti-entropy repairs what hints miss.
• Local storage is usually an LSM tree, so compaction and tombstones need care.

Further learning

The Dynamo paper is the source for the design in this case study.

Sharding and partitioning

Replication