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

near the users. Replication may also increase scalability as the workload can be
distributed among multiple hosts. Unfortunately, transaction management on
replicated data is hard. Managing concurrent access on replicated data requires
coordination, and if copies are separated by slow network links, this may increase
transaction latency beyond acceptable bounds.
These challenges have made most cloud-based databases relax consistency.
Several applications use data stores , which abandon transaction support to re-
duce latency and increase availability. Notable examples of such data stores are
Amazon's Dynamo [1], Cassandra [2], and Google BigTable [3]. A recent trend
is data stores with transactional capabilities within partitions of the data set.
Examples include ElaStraS [4], Spinnaker [5] and Google's Megastore [6]. All of
these provide high availability, but the transaction support is limited as there
is no isolation among transactions accessing different partitions. This imposes
strict limits on how to partition the data, and reduce the general applicability.
Managing consistency in applications without transaction support is dicult
and expensive [7]. Furthermore, inconsistencies related to concurrent transac-
tions can potentially go undetected for a long time. Google's Spanner [8] com-
bines full consistency with scalability, availability, and low latency in a system
replicated across a large geographical area (both sides of the US). However, Span-
ner is deployed on a complex infrastructure based on GPS and atomic clocks,
which limits its applicability as a general-purpose solution.
In this paper, we propose a method for managing replicated data which pro-
vides low latency, transaction support, and scalability, without requiring specific
infrastructure. Our approach, FLACS (Flexible, Location-Aware Consistency),
is based on the observation that in cloud systems, transactions accessing the
same data often originate in the same area. In a world wide online bookstore,
the chance is high that most transactions from Spain access Spanish topics, while
German customers buy German book. For this, partitioning the database accord-
ing to language would work with traditional methods. However, since we also
need to support customers purchasing books both in Spanish and in German, a
more sophisticated solution is needed.
FLACS provides full consistency across partitions by organizing the sites in
a tree structure, and allow transactions to be validated and committed as near
their originating site as possible. To facilitate this, we propose an incremental
ordering protocol which allows validation without full view of concurrent trans-
actions. For many usage patterns, this allows the majority of transactions to
execute with minimal delay.
We have formally specified the FLACS protocol as a real-time rewrite the-
ory [9], and have used Real-Time Maude [9] simulations to compare the perfor-
mance of FLACS to a classical approach with a master-site for validation.
The rest of the paper is structured as follows. Section 2 defines our system
model. Section 3 gives an overview of the FLACS protocol. Section 4 explains
the protocol in more detail. Section 5 presents our simulation results. Finally,
Section 6 discusses related work and Section 7 gives some concluding remarks.