Dynamo

Dynamo is the key value store described by Amazon for services such as the shopping cart. Its guiding requirement is unusual: the store must always accept writes. If a customer adds an item to a cart during a network failure, rejecting it costs a sale, while showing two versions of a cart that are later merged costs almost nothing. So Dynamo sits at the availability end of the CAP tradeoff. It prefers to accept a write and reconcile conflicts later than to refuse it.

The design goals follow from that.

• Always writable, even during failures and partitions.
• Incremental scalability: add one machine at a time and the system absorbs it.
• Symmetry and decentralization: no leader, every node has the same role, so no single point of failure.
• Heterogeneity: stronger machines can take more load.
• Tunable consistency: applications choose their own balance of consistency, availability and latency.

The interface is minimal: get(key) returns a value (or several conflicting versions), and put(key, context, value) stores one. Values are opaque blobs, typically small. There are no joins and no multi-key transactions. That simplicity is what makes the scale possible.

Dynamo spreads keys over nodes with consistent hashing. The hash space is a ring. Each key is hashed to a position, and the node that owns it is the first one found going clockwise. Adding or removing a node moves only the keys in its neighborhood, as covered in the sharding lesson.

Plain consistent hashing places each node at one point, which gives uneven load. Dynamo gives each physical node many virtual nodes, scattered around the ring. This gives three benefits: load evens out, a failed node's load is shared by many survivors instead of one neighbor, and a more powerful machine simply takes more virtual nodes.

To survive failures each key is stored on N nodes, commonly 3. The node that owns the key's position is the coordinator for it, and it replicates the key to the next N minus 1 distinct physical nodes clockwise. The ordered list of nodes responsible for a key is its preference list. Skipping virtual nodes that belong to a machine already chosen guarantees the replicas sit on different machines.

Dynamo uses two numbers. W is how many replicas must acknowledge a write before it succeeds. R is how many replicas must respond to a read. The rule is:

• If R + W > N, any read set overlaps any write set, so a read sees at least one replica with the latest write.

With N = 3, the common choice R = 2 and W = 2 gives 4 > 3. A shopping cart that must never lose a write might choose W = 3 on slow, safe writes, while a product catalog read often might choose R = 1 for speed. Lowering W makes writes faster and more available at the cost of weaker durability. Dynamo thus gives each application a dial between consistency and speed.

A strict quorum would stop accepting writes if some of the N preferred nodes are unreachable. Dynamo uses a sloppy quorum: the write goes to the first N healthy nodes found walking the ring, even if some of them are not in the preference list.

When a write intended for node C is accepted by node D instead, D stores it with a hint naming C as the intended owner, in a separate place. Once C returns, D delivers the data and deletes its copy. This is hinted handoff. It keeps writes succeeding through temporary failures, at the cost of weaker guarantees: until the handoff completes, a read quorum might not see the write.

Since writes are accepted during partitions, different replicas can hold different versions of the same key. Dynamo needs to know whether one version is a descendant of another or whether they are concurrent. It does this with vector clocks: each version carries a list of (node, counter) pairs recording which nodes have updated it and how many times.

Follow one cart:

1. Node X handles a write. Version D1 has clock [X:1].
2. X handles another update. D2 has [X:2], which descends from D1, so D1 can be discarded.
3. A network split happens. Node Y updates from D2, creating D3 with [X:2, Y:1]. Node Z, separately, updates from D2, creating D4 with [X:2, Z:1].
4. Neither D3 nor D4 descends from the other, since each has a counter the other lacks, so they are concurrent and both are kept.
5. A later read returns both. The client merges them, for a cart by taking the union of items, and writes D5 with clock [X:2, Y:1, Z:1] bumped by the coordinator to [X:3, Y:1, Z:1], which descends from both.

A clock A is an ancestor of B if every counter in A is less than or equal to the matching counter in B. If neither dominates, the versions conflict. To keep clocks from growing without bound, Dynamo drops the oldest entries once there are more than a set number of them, which can occasionally lose causality information, a rare and accepted risk.

Who merges conflicting versions? Dynamo offers two choices.

• Application-driven reconciliation: the read returns all conflicting versions, and the application merges them using business knowledge. The cart does this by union, accepting that a deleted item may reappear, which is a better failure than a lost item.
• Last write wins: the system keeps the version with the latest timestamp. It is simple and needs no client logic, but it silently discards the other write, and relies on clocks being roughly in step.

Pushing the merge to the application is honest about the fact that only the application knows what a correct merge is.

For a put, the request reaches a coordinator, either directly through a client that knows the ring or via a load balancer that forwards it. The coordinator creates the new vector clock, writes locally, sends the version to the other N minus 1 nodes in the preference list, and returns success once W have acknowledged.

For a get, the coordinator asks the N replicas, waits for R responses, and returns the version or versions it finds. If it sees stale replicas, it sends the newest version to them in the background. This is read repair.

Hinted handoff and read repair do not fix everything, for example a node that was down long enough to lose its hints. Dynamo also runs a background process that compares replicas and repairs differences. Comparing every key would be enormously expensive, so each node builds a Merkle tree over its key ranges: leaves are hashes of individual keys' data, and each parent is a hash of its children.

Two nodes compare their root hashes. If equal, the whole range is identical, and nothing more is needed. If different, they compare children and descend only into subtrees that differ, until they find the exact keys that disagree and exchange just those. The cost is proportional to the number of differences, not the size of the data.

There is no central registry. Each node periodically picks a random peer and exchanges its view of who is in the ring and what state they are in. This gossip protocol spreads information through the cluster in a logarithmic number of rounds, and needs no coordinator. A node considers a peer failed if it stops answering. Dynamo distinguishes temporary failures, handled by hinted handoff, from permanent departures, which are done explicitly by an administrator and trigger data movement and Merkle repair. A few seed nodes help new nodes join and avoid split views of the ring.

• Gains: very high availability, linear scalability, no single point of failure, and a tunable consistency dial.
• Costs: applications must handle conflicts, there are no transactions across keys, reads may return several versions, and vector clock and gossip behavior adds operational complexity.
• Best fit: workloads where availability and low latency matter more than strict consistency, such as carts, session stores and user preferences.
• Poor fit: anything needing strong invariants, such as account balances.

Dynamo's ideas, the ring, virtual nodes, quorums, hinted handoff, vector clocks, Merkle trees and gossip, reappear throughout modern distributed storage, including Cassandra, which we study next.