Databases Reference
In-Depth Information
The challenges of resource unavailability in long-running transactions also appear in high-
availability scenarios. The problem takes center stage especially when there is less tolerance for
resource unavailability and outage.
A congruent and logical way of assessing the problems involved in assuring ACID-like guarantees in
distributed systems is to understand how the following three factors get impacted in such systems:
Consistency
Availability
➤
➤
Partition Tolerance
Consistency, Availability, and Partition Tolerance (CAP) are the three pillars of Brewer's Theorem
that underlies much of the recent generation of thinking around transactional integrity in large
and scalable distributed systems. Succinctly put, Brewer's Theorem states that in systems that are
distributed or scaled out it's impossible to achieve all three (Consistency, Availability, and Partition
Tolerance) at the same time. You must make trade-offs and sacrifi ce at least one in favor of the other
two. However, before the trade-offs are discussed, it's important to explore some more on what these
three factors mean and imply.
➤
Consistency
Consistency is not a very well-defi ned term but in the context of CAP it alludes to atomicity and
isolation. Consistency means consistent reads and writes so that concurrent operations see the same
valid and consistent data state, which at minimum means no stale data.
In ACID, consistency means that data that does not satisfy predefi ned constraints is not persisted.
That's not the same as the consistency in CAP.
Brewer's Theorem was conjectured by Eric Brewer and presented by him (
www.cs.berkeley.edu/
~brewer/cs262b-2004/PODC-keynote.pdf
) as a keynote address at the ACM Symposium on the
Principles of Distributed Computing (PODC) in 2000. Brewer's ideas on CAP developed as a part of
his work at UC Berkeley and at Inktomi. In 2002, Seth Gilbert and Nancy Lynch proved Brewer's
conjecture and hence it's now referred to as Brewer's Theorem (and sometimes as Brewer's CAP
Theorem). In Gilbert and Lynch's proof, consistency is considered as atomicity. Gilbert and Lynch's
proof is available as a published paper titled “Brewer's Conjecture and the Feasibility of Consistent,
Available, Partition-Tolerant Web Services” and can be accessed online at
http://theory.lcs
.mit.edu/tds/papers/Gilbert/Brewer6.ps
.
In a single-node situation, consistency can be achieved using the database ACID semantics but
things get complicated as the system is scaled out and distributed.
Availability
Availability means the system is available to serve at the time when it's needed. As a corollary,
a system that is busy, uncommunicative, or unresponsive when accessed is not available. Some,
especially those who try to refute the CAP Theorem and its importance, argue that a system with
minor delays or minimal hold-up is still an available system. Nevertheless, in terms of CAP the
defi nition is not ambiguous; if a system is not available to serve a request at the very moment it's
needed, it's not available.
