What is CAP theorem?

The BASE acronym was defined by Eric Brewer, who is also known for formulating the CAP theorem. Distributed systems are prone to outages and not safe from network failures. As system are being scaled up designing a resilient system had to deal with comlpexity incurred in the system. One of the fallcy of the distributed system is that network are reliable. This is where the CAP theorem comes into picture.

The CAP theorem, also known as Brewer's theorem, states that it is impossible for a distributed computer system to simultaneously provide all three of the following guarantees:

  • Consistency: all nodes see the same data at the same time.
  • Availability: a guarantee that every request receives a response about whether it was successful or failed.
  • Partition tolerance: the system continues to operate despite arbitrary message loss or failure of part of the system)

    • According to the theorem, a distributed system cannot satisfy all three of these guarantees at the same time.

    CAP theorem

    Databases can be categorized as CP, AP or CA.

    As mentioned earlier that network cannot be reliable. When a network failure happens to tolerate partition one has to choose one between Consistency(CP) or Availability(AP).

    • CP - Consisteny/Parititon Tolerance - The most recent write is always visible to subsequent readers (single register linearizability). In the event of partitions, the system will block rather than return inconsistent data.
    • AP - Availability/Parititon Tolerance - Imagine having system running with multiple nodes. When parition occurs, the nodes will continue to server traffic and writes may not be replicated across all replicas and/or slaves. In such case during a read the system will return the most recent version of the data in presnt on a node, which could be stale. This system state will also accept writes that can be processed later when the partition is resolved.

    I would highly recommend for people having interest in distributed systems to read papers about Google Spanner and DynamoDB.

    For further reading:

    http://robertgreiner.com/2014/06/cap-theorem-explained/

    Google Spanner

    DynamoDB

    There are few school of thoughts who doesn't agree with CAP theorem completely. Please stop calling databases CP or AP