gold standard of ACID isolation—
se-rializability, or SSI—it turns out many
ACID databases provide a weaker form
of isolation, such as read committed,
often by default and, in some cases,
as the maximum offered. Some of our
recent results show many of these
weaker models can be implemented in
a distributed environment while providing high availability. 5 Current databases providing these weak isolation
models are unavailable, but this is only
because they have been implemented
with unavailable algorithms.
We—and several others—are developing transactional algorithms
that show this need not be the case.
By rethinking the concurrency-control
mechanisms and re-architecting distributed databases from the ground
up, we can provide safety guarantees
in the form of transactional atomicity,
ANSI SQL Read Committed and Repeatable Read, and causality between
transactions—matching many existing ACID databases—without violating high availability. This is somewhat
surprising, as many in the past have
assumed that, in a highly available
system, arbitrary multi-object transactions are out of the question.
Recognizing the limits. While these
results push the limits of what is
achievable with high availability, there
are several properties that a weakly
consistent system will never be able to
provide; there is a fundamental cost
to remaining highly available (and
providing guaranteed low latency).
The CAP theorem states that making
staleness guarantees is impossible in
a highly available system. Reads that
specify a constraint on data recency
(for example, “give me the latest val-
ue,” “give me the latest value as of 10
minutes ago”) are not generally avail-
able in the presence of long-lasting
network partitions. Similarly, we can-
not maintain arbitrary global correct-
ness constraints over sets of data items
such as uniqueness requirements (for
example, “create bank account with ID
50 if the account does not exist”) and,
in certain cases (for example, arbitrary
reads and writes), even correctness
constraints on individual data items
are not achievable (for example, “the
bank account balance should be non-
negative”). These challenges are an
inherent cost of choosing weak consis-
tency—whether eventual or a stronger
but still “weak” model.
By simplifying the design and operation of distributed services, eventual
consistency improves availability and
performance at the cost of semantic guarantees to applications. While
eventual consistency is a particularly
weak property, eventually consistent
stores often deliver consistent data,
and new techniques for measurement
and prediction grant us insight into
the behavior of eventually consistent
stores. Concurrently, new research
and prototypes for building eventually
consistent data types and programs are
easing the burden of reasoning about
disorder in distributed systems. These
techniques, coupled with new results
pushing the boundaries of highly available systems—including causality and
transactions—make a strong case for
the continued adoption of weakly consistent systems. While eventual consistency and its weakly consistent cousins
are not perfect for every task, their performance and availability implications
will likely continue to accrue admirers
and advocates in the future.
The authors would like to thank Peter
Alvaro, Carlos Baquero, Neil Conway,
Alan Fekete, Joe Hellerstein, Marc Shapiro, and Ion Stoica for feedback on
earlier drafts of this article.
BASE: An Acid Alternative
1. abadi, D. consistency tradeoffs in modern distributed
database system design: caP is only part of the story.
IEEE Computer (feb. 2012).
2. alpern, b. and schneider, f.b. Defining liveness.
Information Processing Letters 21 (oct. 1985).
3. alvaro, P., conway, n., hellerstein, j. and marczak,
W. 2011. consistency analysis in bloom: a calm and
collected approach. Proceedings of the Conference on
Innovative Data Systems Research (2011).
4. bailis, P., venkataraman, s., franklin, m., hellerstein,
j. and stoica, I. Probabilistically bounded staleness
for practical partial quorums. In Proceedings of Very
Large Databases (2012). (Demo from text: http://pbs.
Peter Bailis is a graduate student of computer science in
the amPlab and boom projects at uc berkeley, where
he works closely with ali ghodsi, joe hellerstein, and
Ion stoica. he currently studies distributed systems
and databases, with a particular focus on distributed
consistency models. he blogs at http://bailis.org/blog and
tweets as @pbailis.
Ali Ghodsi ( firstname.lastname@example.org ) is an assistant
professor at kth/royal Institute of technology in sweden
and a visiting researcher at uc berkeley since 2009. his
general interests are in the broader areas of distributed
systems, and networking. he received his Ph. D. in 2006
from kth/royal Institute of technology in the area of