CAP theorem

• CAP wiki 
• nice youtube talk 
• chapter 5 of System Design Interview – An insider’s guide 

Intro

Any distributed data store can provide only two of the following three guarantees:

• Consistency
  • Every read receives the most recent write or an error.
  • Once an operation is complete, it will be visible to all nodes - e.g. linearizable consistency
  • Simply put, all the databases see the same data at the same time.
  • Note that consistency as defined in the CAP theorem is quite different from the consistency guaranteed in ACID database transactions.
• Availability
  • Every request received by a non-failing node in the system must result in a response.
  • Simply put: the database is up to serve traffic.
• Partition tolerance
  • The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes.
  • Simply put: the system continues to work if there’s a network issue between databases.
  • When a network is “partitioned”, all messages sent from nodes in one component of the partition to nodes in another component are lost. For example, a simple master slave structure where master node can’t talk to slave node.

Explanation

• No distributed system is safe from network failures, thus network partitioning generally has to be tolerated.
• One therefore has to choose between consistency and availability.
  • Even in the same data center! network fail all the time. Network equipment failure, power cooling failure, network congestion, misconfiguration, software bugs …
  • AC can only achieve when you have single machine.
• e.g. it must be decided whether
  • (CP) to cancel the operation and thus decrease the availability but ensure consistency
    • e.g. the system will return an error or a time out if particular information cannot be guaranteed to be up to date due to network partitioning
  • (AP) to proceed with the operation and thus provide availability but risk inconsistency.
    • e.g. the system will always process the query and try to return the most recent available version of the information, even if it cannot guarantee it is up to date due to network partitioning.
• In the absence of a partition, both availability and consistency can be satisfied
• Database systems designed with traditional ACID guarantees in mind such as RDBMS choose consistency over availability, whereas systems designed around the BASE philosophy, common in the NoSQL movement for example, choose availability over consistency

CP - we normally don’t need it

• Linearizability is an extreme form of consistency and it’s extremely costly to provide. Possible to build useful system without it.

High availability has little to do with CAP-availability

• All nodes returning empty response is actually “CAP-available”.
• When we talk about a HA system, we expect the whole system (not nodes within the system or so) is available - and in such context, it should have a realistic response time. (Otherwise we don’t even considered as available…)
• CAP availability normally refers to “non-failing nodes” need to response, and not specify about the response time.

• Your goal is HA, and CAP-availability has little overlap with that.

AP to CP is a spectrum and the whole space is useful

• Trade-offs between consistency and availability is real.
• Most system are neither CP nor AP, don’t need CP or AP.
• Eventual consistency & high availability is usually good enough!
• Also, with more consistency requirement, there is also trade-offs for latency, operational consistency …etc.
• So you need to understand, CAP is an incomplete tool to analyzing real world system - hence the PACELC theorem