Saturday, December 3, 2016

CAP Theorem

This theorem describes the behavior of a distributed system. A distributed system is a collection of interconnected nodes that all share data.

The CAP Theorem was first postulated by Dr. Eric Brewer back in the year 2000.  As per this theorem, you can get any two at any given time, but you cannot have all the below three attributes. You have to give up the third one for that particular pair of requests.


  1. Consistency: Consistency means that the system guarantees to read data that is at least as fresh as what you just wrote.
  2. Availability: availability means that a non-failing node will give the client a reasonable response within a reasonable amount of time. Now, all that's relative, but what that really means is that it won't hang indefinitely, and it won't return an error.
  3. Partition tolerance: Partition tolerance guarantees that a distributed system will continue to function in the face of network partitions. A network partition is a breaking connectivity. It means that nodes within the system cannot communicate with one another. A partition could be isolated to just the connection between two specific nodes or it could run through the entire network.


Explanation with an example... Write a new version of data to node X, and then we read that data from node Y.  Initially node Y has an older version of that data. So, there could three scenarios. 
  
  • Scenario #1:  Node Y could get the new version from node X. That could be node X sending it to node Y and waiting until it has confirmation from node Y before it sends confirmation back to the client or it could be that node Y goes and fetches it from node X, and it can only return to the client after it has fetched the data. In either case, the network must be functional for the new version to make it to node Y.  If the network is partitioned between nodes A and B, then node Y won't get the latest version. So, in this first scenario, this system is not being partition tolerant. So, let's suppose we want to guarantee partition tolerance.
  • Scenario #2: In the scenario node Y tolerates the partition and simply returns the best version that it has. So, in this case the client would get the older version of the data. This violates the consistency guarantee.
  •  Scenario #3:  In this scenario, we have to wait for messages to get from node X to node Y. So, either node Y will wait indefinitely while the network is partitioned or it'll time out and return an error. In either case, it's not being available.