Information Technology Reference
In-Depth Information
An argument (called the “
CAP
theorem”) has been made that it is impossible
for a web service to provide all of the following three guarantees: consistency,
availability, and partition tolerance (i.e., tolerance to failures of communication
links between sites on the network) [Gilbert and Lynch,
2002
, Stonebraker,
2010a
].
It is the first of these, consistency, that is sacrificed with the key-value stores or
N
O
SQL
data stores. The solutions and performance arguments in favor of such
systems are criticized by Stonebraker [
2010a
,
b
], Stonebraker and Cattell [
2011
],
and Mohan [
2013
], among others. Stonebraker et al. [
2010
] compare the capabilities
offered by modern parallel database management systems with the map-reduce
parallel computation paradigm adopted by many
N
O
SQL
data stores.
Cattell [
2010
] and Stonebraker and Cattell [
2011
] survey a number of
N
O
SQL
data stores, also covering
SQL
database systems that scale to the huge workloads of
simple read and write actions typical in web applications. They group the systems
into key-value stores, document stores, extensible record stores, and scalable
relational systems. The systems in the first three groups have limited transactional
capabilities, if any. Some systems provide concurrency control for synchronizing
single actions, so that only one user at a time is allowed to update an entity (a
tuple, an object, or a document). Updates to local replicas may be propagated
synchronously, while update propagation to remote replicas is asynchronous in most
systems, so that at most eventual consistency among all replicas is achieved.
The idea of providing transactional consistency only within small entity groups
(or key groups) of a big key-value store appears in the design of Google's Megastore
[Baker et al.
2011
], a system implemented on top of BigTable [Chang et al.
2008
].
Megastore provides full replication across multiple datacenters, using the Paxos
consensus algorithm [Lamport,
1998
]. Patterson et al. [
2012
] describe an enhanced
version of Paxos for a similar environment. G-store [Das et al.
2010
]isanexample
of a system that provides transactions on single entity groups, but no replication
across datacenters.
Bernstein [
1990
], Bernstein and Newcomer [
1996
,
2009
], and Kifer et al. [
2006
]
discuss in detail various important aspects of distributed transaction processing we
have omitted, such as transactional middleware (or transaction-processing monitor),
which is a layer of software components between transaction-processing applica-
tions and the underlying database and operating systems. These authors also explain
the software mechanisms used for communications between application processes
and server-process threads and between processes running at different servers in
a distributed systems. These mechanisms include transactional remote procedure
calls and persistent queues. General texts on distributed database management,
with extensive treatments of transaction processing, have been written by Özsu
and Valduriez [
2011
] (the first edition published in 1991) and by Rahimi and Haug
[
2010
], among others.
