Consistency Management in Cloud Storage Systems - Large Scale and Big Data: Processing and Management - page 334

concurrently do not share a causality relation. Therefore, causal consistency does
not order concurrent operations. In [27,28], two operations, a and b, have a potential
causality if one of the two following conditions are met: a and b are executed in a
single thread and one operation execution precedes the other in time, or if b reads a
value that is written by a. Moreover, a causality relation is transitive. If a and b have
a causal relation, b and c have a causal relation as well, then a and c have a causal
relation.
10.3.4.2 Updates Conflict Handling
In [28], a model that combines causal consistency and convergent conflict handling
is presented and called causal+. Since concurrent operations are not ordered by
causal consistency, two writes to the same key or data object would lead to con-
current updates conflict where different data changes are performed at the level of
at least two different replicas. The main challenge for such situations is to ensure
replicas convergence to the same state. In contrast to eventual consistency, the
updates conflict is a direct result of performing updates concurrently. With even-
tual consistency, however, a conflict may occur with two updates to the same data
but not at the same time. The convergent conflict handling aims at handling all
the replicas in the same manner using a handler function to ensure that all rep-
licas will be in the same state at a latter time. To reach handling convergence,
all conflicting replicas should consent to an agreement. Various conflict handling
methods were proposed such as last-writer-wins rule [29], through user interven-
tion, or using versioning mechanisms that allow merging of different versions in
one as in Amazon's eventually consistent Dynamo storage system. In this context,
it has been shown that implementing causal consistency with last-writer-wins rule
to handle updates conflicts at wide scales provides performance comparable to that
of eventually consistent systems [30].
10.3.5 t imeline C onsistenCy
The timeline consistency model was proposed specifically for the design of Yahoo!
PNUTS [31], the storage system designed for Yahoo! web applications. This consis-
tency model was proposed to overcome the inefficiency of serializability of transac-
tions at massive scales and georeplication. Moreover, it aims to limit the weakness
of eventual consistency.
10.3.5.1 System-Side Guarantees
Transaction serializability was avoided as a design choice within Yahoo! PNUTS.
This was mainly due to the observation that web applications typically manipulate
one record at a time. Therefore, a per-record timeline consistency was introduced.
Unlike eventual consistency, where operations order can vary from one replica to
another, all replicas of a record perform the operations in the same “correct” order.
For instance, if two concurrent updates are performed, all replicas will execute them
in the same order and thereby avoid inconsistencies. Nevertheless, data propaga-
tion to replicas is done lazily, which makes the convergence of all replicas eventual.
This allows clients to read data from local replicas that may be in a stale version. To