／var／logmarcus chiu

CAP Theorem (Consistency - Availability - Partition Tolerance)

Created on · Last Modified on

CAP Theorem (Consistency - Availability - Partition Tolerance)
  • states that a distributed system cannot simultaneously guarantee all three properties:
    • Consistency
    • Availability
    • Partition Tolerance
  • this means that when designing distributed systems, developers must make trade-offs, choosing which two properties are most important for their application

CAP - Introduction

CAP Properties & Trade-Offs

A distributed system can guarantee at most two of the following three properties at the same time:

Consistency
  • all nodes in the system see the same data at the same time
  • this means all reads receive the most recent write or an error
  • e.g. After writing x = 5, any read from any node must return 5

Availability
  • every request receives a (non-error) response, even if the data is not the most recent
  • this ensures that the system is always operational and can respond to requests, even if some nodes are unavailable

Partition Tolerance
  • the system continues to operate despite network partitions or communication failures between nodes
  • this means the system can handle situations where nodes are disconnected from each other due to network issues

Network partitions are unavoidable in distributed systems. So in practice, when a partition happens, you must choose between: Consistency or Availability

CP (Consistency and Partition Tolerance)
  • Sacrifices availability
  • The system prioritizes keeping data consistent even during network partitions, but may become unavailable or have limited availability if nodes are disconnected

AP (Availability and Partition Tolerance)
  • Sacrifices consistency
  • The system prioritizes being available and continuing to operate during network partitions, but may not guarantee data consistency across all nodes

CA (Consistency and Availability)
  • NOT POSSIBLE - Network partitions are unavoidable in distributed systems
  • In a distributed setting, this combination is theoretically impossible because network partitions are inevitable

Consistency Types

Strong Consistency
  • the strongest type of consistency (i.e. same as choosing C in CAP)
  • all reads reflect most recent write

Causal Consistency
  • related events appear in order (comments on a comment)

Read Your Own Writes Consistency
  • user sees their own updates

Eventual Consistency
  • the weakest type of consistency
  • updates will propagate eventually