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

Fig. 1.1 Dynamo ring: key
K is primarily stored at B, its
coordinator node, and
replicated at C and D,the
two successor nodes of B;
here, we assume three copies
per data item

1.1.2 Replication

Dynamo allows data replication for better data availability,. Given a data item, in
addition to storing its key locally, the coordinator node also replicates it on the
N 1 successor nodes clockwise on the ring, where N is a pre-specified number
representing the number of copies for the data item. For example, in Fig. 1.1 ,
assuming N D 3, node B, the coordinator node of key K, will replicate key K
on node C and D, the two successor nodes of B on the ring. Consequently, each
node is responsible for its range and the ranges of the N 1 predecessor nodes.
The list of nodes responsible for storing a key is called the key's preference list .
To account for failure during write operations, this preference list may contain more
than N nodes. Also, due to the presence of virtual nodes, it is possible that a key is
replicated on two virtual nodes on the ring which happen to be the same physical
node. Therefore, the preference list is constructed such that it includes only physical
nodes but not virtual nodes. The system is designed so that any node can determine
the preference list of a key based on exchanging membership and status information
between nodes.

1.1.3 Versioning

Because data is replicated, data versioning is needed to achieve consistency.
Dynamo provides eventual consistency in which write operations are applied to
replicas asynchronously. As one of the consistency models in parallel computing,
eventual consistency means that given a sufficiently long period of time over which
no changes are sent, all updates are expected to propagate eventually throughout the
system and so eventually all the replicas will be consistent.
Dynamo allows multiple versions of a data item to be available in the system
at the same time. For example, on amazon.com, an “add to cart” operation can
never be rejected nor forgotten. If for any reason, the most recent state of the cart