Scalable and Fully Consistent Transactions in the Cloud through Hierarchical Validation - Data Management in Cloud, Grid and P2P Systems - page 37

dynamic reconfiguration. The general rule is that observers for items commonly
accessed together should be close in the validation hierarchy.
6 Related Work
Most recent proposals for ecient data storage in cloud systems are based on
decentralization with partitioning. In ElasTraS [4], transactions spanning parti-
tions are only allowed as short transactions with predeclared read sets and write
sets. Megastore [6] assumes a relatively fine-grained partitioning of the data set,
and replicates each partition across a subset of servers. Consistency is achieved
by running Paxos within each partition. Spinnaker [5] coordinates updates in
the same way as Megastore, but executes consistent reads directly at the leader
of each partition. Although more fault-tolerant than FLACS, they do not pro-
vide consistency across partitions (Megastore provides two-phase commit, but
without serializability).
In a wide-area setting, approaches based on atomic multicast have been lim-
ited by the message delay required to order every update among all processes.
The protocols in [13,14] build upon atomic multicast, but they target a wide
area setting through partial replication, requiring message ordering only within
the group of replicas that together manage the read sets and write sets of the
transaction. This differs from FLACS since FLACS allows full replication, but
only requires coordination among a limited set of participants (the observers).
Many real-world systems are deployed on top of non-transactional data stores
such as Amazon's Dynamo [1] and Cassandra [2]. Both provide eventual con-
sistency by committing updates with synchronization among only a subset of
participating sites, and the new values are then propagated among other replicas
in the background. Updates are versioned using vector clocks, and in the case
of conflicts updates are reconciled by the application. Although ecient, lacking
transactions is a significant disadvantage for systems managing critical data such
as audit records, reservations, or financial data.
Microsoft's Azure [15] and Google's Spanner [8] also provide large-scale trans-
actions for cloud applications. Azure is known to give good performance [16]
through a master-slave approach, but publicly available details are scarce. Com-
pared to FLACS the transaction latency of any master-based approach will be
worse for clients far from the master site, since every update transaction needs
at least one message exchange with the master. Spanner provides both high
availability through Paxos, replication across wide area networks, and consis-
tency through Multi Version Concurrency Control (using global timestamps).
But Spanner is hard to deploy; one obstacle for widespread adoption is that to
provide global timestamps, Spanner depends on precisely synchronized clocks
and demands a relatively complex infrastructure involving GPS hardware and
atomic clocks. Our approach with logical ordering through the validation hier-
archy provides a simpler, more generic solution.