0% completed
Replication
On This Page
What is optimistic replication?
Preference List
Sloppy quorum and handling of temporary failures
Hinted handoff
Let's see how Dynamo replicates data across nodes, and how it keeps working when some of those nodes fail.
What is optimistic replication?
Dynamo does not keep a key on one node. It replicates each data item across N nodes. N is the
, a number you set per instance of Dynamo. Spreading copies this way gives Dynamo high availability. It also gives Dynamo .Each key is assigned to a coordinator node. This is the node that falls first in the hash range for that key. The coordinator stores the data locally. Then it replicates the data to the N-1 nodes that follow it clockwise on the ring. Each node ends up owning the stretch of the ring between itself and its Nth predecessor.
This replication runs asynchronously, in the background. That is why Dynamo offers only an eventually consistent model. Replicas are not guaranteed to match at every moment, though they converge over time. Dynamo writes locally first, then copies the data out afterward without making the client wait. That is why this technique is called optimistic replication.
Each node in Dynamo replicates a different range of data. N copies of every item sit on different nodes. So if one node goes down, that does not stop reads or writes for its range. Another replica answers instead. If a client cannot reach the coordinator node, it sends the request elsewhere. Any node holding a replica can answer it.
Preference List
The list of nodes responsible for storing a given key is called the preference list. Every node in the system can work out this list on its own. It uses the same ring logic for any key (more on that later). The list holds more than N nodes, not exactly N. That margin does two things: it gives the system somewhere to fail over to, and it skips past virtual nodes on the ring. That way the list ends up with N distinct physical nodes.
Sloppy quorum and handling of temporary failures
A strict
approach makes a distributed system unavailable during failures. It keeps waiting on the same fixed set of nodes, even during a network partition. Dynamo trades that strictness for availability. Instead of a strict quorum, it uses a sloppy quorum. Every read or write runs against the first N healthy nodes on the preference list. Those are not always the first N nodes you would reach moving clockwise on the ring.Here is what that looks like with N=3. Say Server 1 is down, or just unreachable, during a write. Dynamo does not wait for it. It moves that replica to the next node on the ring that lacks a copy. Here, that node is Server 4. This keeps a short-term failure from blocking the write, and it preserves the availability and durability guarantees the design promises.
The replica handed to Server 4 carries a hint in its metadata. That hint names the node it was really meant for, Server 1. Server 4 keeps hinted replicas like this in a separate local store, and scans it periodically. Once it detects that Server 1 has recovered, it tries to deliver the replica there. When that delivery succeeds, Server 4 deletes its own copy. The total number of replicas in the system never drops.
Hinted handoff
The trick behind that recovery has a name: hinted handoff. When a node is unreachable, another node accepts writes on its behalf. It holds those writes in a local buffer, and sends them on once the destination node is reachable again. This is what makes Dynamo "always writeable." Even in the extreme case where only one node in the cluster is alive, it still accepts writes. Those writes get processed once the rest of the cluster returns.
That guarantee has a cost. A sloppy quorum is not a strict majority, so the data can and will diverge. Two concurrent writes to the same key can be accepted by two different, non-overlapping sets of nodes. Multiple conflicting values for the same key can then sit in the system at once. A later read can come back stale or conflicting. Dynamo accepts that trade, and uses vector clocks to detect these conflicts at read time.
Sudhanshu Bhatnagar
· 3 years ago
Coordinator Node in Optimistic Replication is Vnodes or Physical nodes?
Reading Progress
0%
On This Page
What is optimistic replication?
Preference List
Sloppy quorum and handling of temporary failures
Hinted handoff