The Life of Dynamo’s put() & get() Operations

So far we have covered how Dynamo stores and replicates data. Now let's follow a single get() or put() request through the system, end to end.

Strategies for choosing the coordinator node

Every get() and put() request has to reach a coordinator node. This is the node that owns the key and drives the request. Dynamo clients pick that node one of two ways:

• Route the request through a generic load balancer.
• Use a partition-aware client library that sends the request straight to the right coordinator node, for lower latency.

In the first case, the load balancer decides where the request goes. In the second, the client decides. Each approach has its own upside.

With a load balancer, the client never has to know anything about the Dynamo ring. That keeps Dynamo's architecture

The partition-aware client skips that cost, and gets

Consistency protocol

Dynamo's consistency protocol works like a quorum system. A quorum is the minimum number of nodes that must take part in an operation before it counts as done. Say R is the minimum number of nodes that must take part in a successful read. Say W is the minimum for a successful write. Whenever R+W > N, you get a quorum-like guarantee.

A common (N, R, W) configuration for Dynamo is (3, 2, 2). Push those numbers in either direction, and you trade one thing for another. A (3, 3, 1) setup gives you fast writes and slow reads. It is not very durable. A (3, 1, 3) setup gives you fast reads and slow writes. It is durable.

In this model, a get() or put() takes as long as its slowest replica. That is why R and W are usually set below N: it gives better latency. The trade runs the other way too. Low values of W and R raise the risk of inconsistency. Write requests can be marked successful, and returned to the client, even if most replicas have not processed them yet. That gap is also a durability risk. A write can be handed back to the client as done, while it has actually reached only a small number of nodes.

For both read and write operations, requests are forwarded to the first N healthy nodes.

'put()' process

A put() request runs through these steps:

1. The coordinator generates a new data version, tagged with a vector clock component.
2. It saves the new data locally.
3. It sends the write request to the N-1 highest-ranked healthy nodes on the preference list.
4. The put() operation is considered successful after receiving W-1 confirmations.

'get()' process

A get() request runs through these steps:

1. The coordinator requests the data version from the N-1 highest-ranked healthy nodes on the preference list.
2. It waits until R-1 replies come back.
3. The coordinator works out how the returned versions relate to each other, using their vector clocks.
4. It returns all relevant data versions to the caller.

Request handling through state machine

Every client request gets its own state machine, created on the node that received it. That state machine holds all the logic. It identifies the nodes responsible for a key, sends the requests, and waits for responses. It retries where needed, processes the replies, and packages the response for the client. One instance handles exactly one client request. A read operation's state machine looks like this:

1. Send read requests to the nodes.
2. Wait for the minimum number of required responses.
3. If too few replies arrive within the time limit, fail the request.
4. Otherwise, gather all the data versions and determine which ones to return.
5. If versioning is enabled, perform syntactic reconciliation, and generate an opaque write context. That context carries the vector clock covering all the remaining versions.

Once the read response has gone back to the caller, the state machine keeps waiting briefly for any responses still outstanding. If one of those turns out to be a stale version, the coordinator updates that node with the latest version. This process is called Read Repair. It repairs replicas that missed a recent update.

put() requests are coordinated the same way, by one of the top N nodes on the preference list. It would be simpler to always use the first of those N nodes, so every write for a key would serialize through one place. But request load is not spread evenly across objects. Always picking the same node led to uneven load distribution for Dynamo. So Dynamo lets any of the top N nodes coordinate a write. A write usually follows a read. So the coordinator for that write is chosen to be the node that replied fastest to the earlier read. That information is already stored in the request's context. That node is likely to hold the data the client just read, which raises the odds of "read-your-writes" consistency.