Database Reference
In-Depth Information
The CAP theorem
In 2000, Eric Brewer (
http://en.wikipedia.org/wiki/Eric_Brewer_%28scientist%29
)
, in his
keynote speech at the ACM Symposium, said, "A distributed system requiring always-on,
highly-available operations cannot guarantee the illusion of coherent, consistent single-sys-
tem operation in the presence of network partitions, which cut communication between act-
ive servers". This was his conjecture based on his experience with distributed systems. This
conjecture was later formally proved by Nancy Lynch and Seth Gilbert in 2002 (
Brewer's
Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services
,
published in ACMSIGACT News, Volume 33 Issue 2 (2002), page 51 to 59 available at
ht-
Let's try to understand this. Let's say we have a distributed system where data is replicated
at two distinct locations and two conflicting requests arrive, one at each location, at the
time of communication link failure between the two servers. If the system (the cluster) has
obligations to be highly available (a mandatory response, even when some components of
the system are failing), one of the two responses will be inconsistent with what a system
with no replication (no partitioning, single copy) would have returned. To understand it
better, let's take an example to learn the terminologies. These terms will be used frequently
throughout this topic.
Let's say you are planning to read George Orwell's topic
Nineteen Eighty-Four
over the
Christmas vacation. A day before the holidays start, you logged into your favorite online
bookstore to find out there is only one copy left. You add it to your cart, but then you real-
ize that you need to buy something else to be eligible for free shipping. You start to browse
the website for any other item that you might buy. To make the situation interesting, let's
say there is another customer who is trying to buy
Nineteen Eighty-Four
at the same time.
Consistency
A consistent system is defined as one that responds with the same output for the same re-
quest at the same time, across all the replicas. Loosely, one can say a consistent system is
one where each server returns the right response to each request.
In our topic buying example, we have only one copy of
Nineteen Eighty-Four
. So, only one
of the two customers is going to get the topic delivered from this store. In a consistent sys-
tem, only one can check out the topic from the payment page. As soon as one customer
makes the payment, the number of
Nineteen Eighty-Four
topics in stock will get decremen-
ted by one, and one quantity of
Nineteen Eighty-Four
will be added to the order of that cus-
