Introduction - Data Storage for Social Networks: A Socially Aware Approach - page 5

is unavailable, the system must present the user with an older version of the cart. If
the user makes a change to this old version, this change is still meaningful and must
not be discarded when the most recent state of the cart becomes available again. The
resolution for having multiple versions at the same time can be done either manually
or automatically. A new version of an object should replace an older version and the
system fixes itself, but when semantic contexts are involved the user must manually
resolve the conflict. Dynamo uses vector clock [ 22 ] to maintain the evolution of the
versions of an object.

1.1.4 Read and Write

Since there may be multiple versions for the same data, read and write in Dynamo
follows a quorum-like protocol to ensure correctness in the data returned. This
protocol has two configurable parameters: (1) R: the minimum number of nodes
that must participate in a read operation, and (2) W : the minimum number of nodes
that must participate in a write operation. The coordinator, which usually is the top
node of the reference list, should handle read and write operations for a key. If a
request is received at a random node that is not on the preference list, the request
will be routed towards the list's top. If the request is for a write, the coordinator
routes the request to the top N nodes in the preference list (N is the number of
copies for a data item). If at least W 1 nodes respond successfully, the write is
considered successful. Similarly for a read request, the coordinator asks N nodes
for the key and waits for at least R 1 nodes to return data. If there is inconsistency
in object versions, reconciliation is done manually or automatically depending on
the nature of the conflict.

1.1.5 Handling Dynamics

Adding a node is relatively straightforward. A new node is assigned a set of
tokens on the ring and, consequently, a set of key ranges it will be responsible
for. In the case of a node's outage, this could be a permanent departure or
happen due to a temporary failure or maintainance task. An outage is considered
temporary unless a command is explicitly executed to inform the system of its
permanent removal. Dynamo employs a gossip-based protocol to propagate changes
in node membership, in which each node exchanges membership information with
random neighbors once every second and thus can reconcile any inconsistency
automatically. This periodic exchange of information allows nodes to be aware of
the ranges managed by other nodes on the ring, so that a request arriving at any node
can be forwarded directly to the right set of nodes responsible for this key.