PAPERS-05-005 · Paper — Dynamo

The paper

The paper “Dynamo: Amazon’s Highly Available Key-value Store” by G. DeCandia et al., published in 2007 at SOSP, is a landmark because it introduced a practical design for a highly available, always‑writable storage system that reshaped how large‑scale services handle failures.

Before this paper

Before Dynamo, Amazon’s shopping cart needed to remain writable even during failures, but traditional strongly‑consistent databases would become unavailable when nodes or networks failed. This created a tension between consistency and availability, forcing services to sacrifice one for the other. Engineers struggled to keep critical services online during spikes or outages. The field lacked a proven approach that could keep data writable while tolerating failures.

The key idea

The core insight of Dynamo is to deliberately trade strong consistency for high availability. By allowing the store to accept writes at any time and reconciling conflicts later, the system achieves eventual consistency. This shift lets the service stay online even when parts of the system fail. The idea embraces the AP side of the CAP theorem.

How it works

Dynamo partitions data across a ring using consistent hashing, so each node owns a range of keys. Each piece of data is replicated on N nodes, and reads and writes use quorum parameters R and W to balance consistency and availability. Vector clocks are attached to versions to detect and later resolve conflicting updates. When a write arrives, it is stored on enough replicas to satisfy W, even if some replicas are down. Reads query enough replicas to satisfy R and merge any divergent versions using the vector clocks. There is no single master; any replica can accept writes, and conflict resolution is performed by the application or automatically when possible.

See it — always-on with eventual consistency

flowchart LR
  A["Write"] --> B["Consistent hashing<br/>ring"]
  B --> C["Replicate to<br/>N nodes"]
  C --> D["Quorum read/write<br/>(R + W)"]
  D --> E["Always available"]

What they showed

The authors demonstrated that Dynamo kept Amazon’s critical services available and writable through failures and traffic spikes, at the cost of occasional conflict reconciliation. This real‑world deployment proved that an eventually consistent design could meet Amazon’s reliability requirements.

What it changed

Dynamo popularized eventual consistency and highlighted the AP side of the CAP trade‑off, influencing the design of many later systems. It directly inspired the creation of Apache Cassandra, Riak, and Amazon DynamoDB, spreading its principles across the industry. The paper showed that sacrificing strict consistency could be a practical, scalable solution for large‑scale services. Next: Apache Kafka.

The one-line takeaway

Availability can be prioritized over strict consistency by using quorum‑based replication and later conflict resolution.

Read it / meet it

Reading the Dynamo paper gives insight into the practical engineering choices behind highly available storage. Its legacy lives on in modern NoSQL databases like Cassandra, Riak, and DynamoDB, where you can see the same design patterns in action.