Home Distributed Computing What is CAP theorem and where is it used?

What is CAP theorem and where is it used?

CAP theorem stands for Consistency, Availability, and Partition tolerance.

CAP theorem also know as Brewer’s theorem states that it is impossible for any distributed database system to provide all three of the following properties together, that is to say, a distributed database can only provide almost any two of the following three characteristics: Consistency, Availability, and Partition-Tolerance. 

CAP Therom

With the advances in parallel processing and distributed systems, it is more common to expand horizontally or have more machines, and the CAP theorem is the backbone of such architecture. Let’s understand the characteristic of the CAP theorem in detail.

Consistency

A consistent system is one in which all nodes see the same data at the same time. In other words, if we perform read operations after multiple write operations then a consistent system should return the same value for all the read operations and that too the value of the most recent write operation.

Note that consistency, as defined in the CAP theorem, is quite different from the consistency guaranteed in ACID database transactions.

Availability

A highly available distributed system is one that remains operational 100% of the time. Hence, every request made should be accepted and receives a (non-error) response. Note it is not necessarly that the response will contain the most recent write value (i.e. the system needs not to be consistent but it should be available all the time).

Partition Tolerance

It states that a system should continue to run even if the connection between nodes delays or breaks. Note, this doesn’t mean a node/nodes goes down, nodes are up, but can’t communicate.

Partation Tolerance

Let’s say that we a two nodes N1 & N2 and both are connected. Now assume that the network connecting both the nodes goes down (network gets partitioned), but both nodes N1 and N2 are up and running fine but the updates happening at node N1 can no longer reach node N2 and vice-versa

Partition tolerance is more of a necessity than an option in modern distributed systems, hence we can’t we cannot avoid “P” of CAP. So. we have to choose one among consistency & availability either CP or AP systems.

Available Combination according to CAP Theorem

  1.  CP – Consistency & Partition Tolerance

    Data is consistent among all the nodes and the nodes maintain partition tolerance. hence the de-sync node will not accept any request i.e. some request will be dropped instead of returning inconsistent (most recent) information.
    Let’s say we have two nodes and one of the nodes (let’s say N2) stops servicing read/write requests on detecting that network connecting the system got partitioned. This means that system treats node N2 as not available anymore, and any request on this node will be rejected as it will end up returning the old/stale copy of the data. Hence, this kind of system provides consistency & Partition Tolerance.
    Example – Google BigTable, Hbase, MongoDB, MemcacheDB, Redis

  2. AP – Availability & Partition Tolerance

    The distributed system is highly available and the system is partition tolerant, hence every read request will not guarantee the most recent information, but every request will be processed.
    Example – Voldemort, SimpleDB, CouchDB

  3. CA – Consistency & Availability

    This is not possible in any distributed architecture. It can be found only in some non-scalable monolithic architecture.

Further Reading

Google Docs & GMail enforces consistency at the cost of availability hence the result you will see across the devices will be same/consistent.

Google Search, twitter & youtube focuses on availability and relaxes consistency hence, the results you see will depend on the state of the server that responds to your request, and different servers can have inconsistent states.
This is why, sometimes on youtube or twitter, you see inconsistent results in terms of likes or views.

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promise, we won't spam
Even we hate spam as much as you hate them

LEAVE A REPLY

Please enter your comment!
Please enter your name here