What is optimistic replication in Dynamo?

Optimistic replication is a replication scheme used in DynamoDynamo is Amazon’s highly-available, key-value datastore. to ensure high availability and durability.Any system is considered durable if it does not lose the data that was successfully committed to it. In other words, durability guarantees against any data loss due to corruption or a permanent component failure, like that of a storage device or server. In this replication scheme, each data item is replicated on multiple N nodes, where N is known as the replication factor.A replication factor is the number of nodes that will receive a copy of the same data. For example, a replication factor of two means that there are two copies of each data item, whereby each copy is stored on a different node. Dynamo uses consistent hashing to direct user requests. The first node encountered while traversing the ring clockwise upon hashing a key is known as the coordinator node. The coordinator node serves the client requests and replicates the data on the next N-1 clockwise successor nodes.

This means that each data item is replicated on N nodes in the system. Dynamo uses the eventually consistent model, which means that the system eventually converges on a consensus, since replication is done asynchronously. This replication scheme is known as an optimistic replication, because the replicas are not guaranteed to be identical at all times.

Example

The following example shows how data is replicated on successor nodes in Dynamo:

Preference list

In Dynamo, every node has a list of nodes on which it replicates the data. This list is known as the node’s preference list. It contains more than the N successor nodes and skips similar virtual nodes. Similar virtual nodes are skipped to ensure that each data item is replicated on a unique physical node. The rationale behind choosing a value greater than N for the number of nodes in the preference list is that the engineers wanted to make the system highly available. Therefore, even in the case of N server failures, the node is able to replicate the data on the nodes ahead of the N successor nodes.