“Dynamo: Amazon’s Highly Available Key-value Store” by Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels of Amazon.com was presented at the 21st ACM Symposium on Operating Systems Principles (SOSP) in 2007. It describes the design and implementation of a storage system that powers several core Amazon services.
The paper opens with the observation that reliability at massive scale is one of the biggest challenges Amazon faces, and that at the scale of tens of thousands of servers, components fail continuously. The authors argue that for many Amazon services, such as the shopping cart, availability is paramount: customers must always be able to add and view items even when disks fail, networks partition, or whole data centers are unreachable. To achieve this, Dynamo deliberately sacrifices strong consistency under certain failure scenarios in favor of being “always writeable.”
Dynamo is a key-value store: applications store and retrieve opaque blobs (values) identified by a key, with no relational schema and no complex queries. The paper combines several known distributed-systems techniques into one working system. It uses consistent hashing to partition and replicate data across nodes, object versioning with vector clocks to track conflicting updates, and a quorum-like protocol with configurable read and write counts (R, W, and N) to manage consistency and durability. When concurrent updates conflict, Dynamo pushes conflict resolution to the application rather than rejecting writes.
Dynamo became one of the most influential systems papers of its era. Its design directly shaped the open-source Apache Cassandra and Riak, and Amazon later named its managed DynamoDB service after it. The paper is widely cited as a founding document of the eventual-consistency branch of the NoSQL movement.