Last updated on

CAP Theorem

🧐 The Misunderstood CAP Theorem

The CAP theorem is a fundamental concept in distributed database systems, particularly where data is replicated across multiple nodes (like a leader/follower setup or common in NoSQL databases). It does not apply to a single, non-replicated database node.

The acronym stands for:

  • Consistency
  • Availability
  • Partition Tolerance

🚫 The True Meaning of the Theorem

A major misconception is that one can choose β€œtwo out of three” (CA, CP, or AP).

The reality is that Partition Tolerance (P) is mandatory in any useful distributed system, as network failures are inevitable. Therefore, the choice is fundamentally between Consistency (C) or Availability (A) during a network partition.

$$\text{P is guaranteed, choose } (\text{C} \text{ or } \text{A})$$

Partition Tolerance (P)

  • Definition: The system continues to function despite a network partition, where communication between some nodes is broken (e.g., a leader and a follower can no longer communicate).
  • Why it’s guaranteed: In a real-world distributed system, you almost always want the system to keep operating even if a network split occurs, rather than just shutting down the entire system.

Consistency (C)

  • Definition: Every read request receives the most recent write (or an error). This is a stronger form of consistency than the ACID property.
  • Trade-off: To ensure this when partitioned, a node that cannot communicate with the primary to confirm it has the latest data must stop serving requests (giving up availability).

Availability (A)

  • Definition: Every non-crashing node in the system must respond to a valid request (read or write) in a timely manner, without guarantee that the data is the most up-to-date.
  • Trade-off: To ensure this when partitioned, a node that can’t reach the primary will continue serving requests, but it might be serving stale (inconsistent) data (giving up consistency).
Scenario (During Partition)Favors C (CP system)Favors A (AP system)
Out-of-sync node responseRefuses the request.Serves the request with potentially stale data.
ResultStrong Consistency but Lower Availability.High Availability but Weak Consistency.

πŸ’‘ PACELC: A Better Model

A more helpful extension that addresses another common source of confusion is the PACELC theorem. It extends CAP by considering the trade-offs even when there is no partition.

$$\text{PACELC}$$

PA/C (During Partition)

This is the original CAP theorem, where in the event of a Partition, you must choose between Availability or Consistency.

E/LC (No Partition)

If there is Else (no partition), you must choose between Latency or Consistency.

  • Low Latency (L): Data replication is often handled asynchronously to speed up writes (low write latency) or reads (low read latency), but this means replicas might briefly hold stale data, creating eventual consistency.
  • Strong Consistency (C): Replication must be synchronous, meaning the user must wait until all necessary replicas confirm the write before the operation is complete. This increases latency.

This extension better captures the real-world trade-offs in distributed system design, such as deciding whether to prioritize faster response times (low latency) over ensuring all nodes are instantly up-to-date (consistency) under normal operation.

πŸ”‘ Key Takeaway

The value of the CAP theorem (and PACELC) lies not in rigid categorization, but in forcing designers to acknowledge and explicitly choose the trade-offs they must make in a replicated, distributed system:

  1. When the network fails (P): Do you sacrifice C or A?
  2. When the network is healthy (E): Do you sacrifice L or C?

Would you like to explore an example of a database that is generally considered β€œAP” (prioritizes availability over consistency during a partition)?

Pasted image 20251110145937