Case: Amazon Dynamo, the paper

Case: Amazon Dynamo (The 2007 Paper)

Dynamo was Amazon's internal key-value store designed for services that absolutely needed to keep accepting useful work during failures. Its 2007 paper is a foundational text in distributed systems, heavily influencing the creation of Cassandra, Riak, and modern DynamoDB.

Amazon's shopping-cart service prioritized accepting add-to-cart operations through many node and network failures and reconciling divergent versions later. This was an availability goal within reachable-capacity limits, not a promise that every request can succeed under every partition.

Always Writable

A leader-based database may pause writes while establishing a new leader, depending on its replication and failover policy; this is not an inherent property of all relational databases. Dynamo instead chose a leaderless design that favors accepting operations during many partitions and resolving concurrent versions later.

Dynamo is a leaderless, multi-master system. Any node can accept a write. But what happens if two users (or one user on two different devices during a network split) update the same cart at the same time on different nodes?

Vector Clocks and Conflict Resolution

Because multiple nodes can accept writes independently, conflicting versions of the data will emerge. Dynamo does not try to resolve these conflicts at write time—that would block the write. Instead, it pushes the conflict resolution to read time.

To track versions, Dynamo uses Vector Clocks. A vector clock is a list of (node, counter) pairs. When a client reads a shopping cart, it might get back two conflicting versions along with their vector clocks. The client application (the shopping cart service) is responsible for merging them (e.g., combining the items from both versions) and writing the merged result back to Dynamo.

Consistent Hashing

To distribute data across nodes, Dynamo uses Consistent Hashing. The nodes are arranged in a logical ring. A key is hashed and placed on the ring, and it is stored on the first node it encounters moving clockwise.

This ensures that if a node is added or removed from the cluster, only the data belonging to its immediate neighbors needs to be remapped, rather than remapping the entire database (which would happen with simple modulo hashing).

Tunable Consistency (N, R, W)

Dynamo popularized configurable quorums in a production key-value store (quorum voting itself dates back to Gifford, 1979), using three variables:

• N: The number of nodes that store replicas of the data (e.g., 3).
• W: The number of nodes that must acknowledge a write for it to be considered successful (e.g., 2).
• R: The number of nodes that must respond to a read request (e.g., 2).

Under a fixed replica set, a successful write to W replicas and a read from R replicas with W + R > N forces at least one overlap. That does not by itself guarantee one unambiguous latest value under concurrent writes, node failures, or Dynamo's sloppy quorum, where fallback nodes may satisfy requests outside the original preference list. Reads must reconcile returned causal versions, and lower W generally increases the chance of stale or missing observations.

The paper's problem-technique table, restated

Worked example: vector clocks from the paper

1. Node Sx handles a write: D1 with clock [Sx:1].
2. Sx handles an update: D2 [Sx:2]. D2 descends from D1, so D1 can be discarded.
3. Two clients read D2 and update it on different nodes: Sy produces D3 [Sx:2, Sy:1], Sz produces D4 [Sx:2, Sz:1].
4. Neither D3 nor D4 descends from the other, so both are kept and returned together on read.
5. The client merges them and Sx writes D5 [Sx:3, Sy:1, Sz:1], which supersedes both.

Worked example: quorum settings

The common configuration in the paper is (N, R, W) = (3, 2, 2). With W = 2, a write succeeds while one of three replicas is down. Setting W = 1 maximizes write availability and lowers latency but increases the chance that a read misses the newest version; R = 1 does the same for reads. With a sloppy quorum, a write can be accepted by a fallback node outside the key's preference list and handed back later, so R + W greater than N no longer guarantees overlap with the latest write.

Dynamo versus DynamoDB