CAP Theorem

Behzad

— 2 min read
Share

The CAP Theorem (Consistency, Availability, Partition Tolerance) is a fundamental principle in distributed systems, introduced by Eric Brewer in 2000 and later formalized. It states that in a distributed database (one that runs across multiple nodes/servers), it is impossible to simultaneously guarantee all three properties perfectly, especially during network partitions (when nodes can't communicate reliably). A system can only prioritize two out of the three.

Core Definitions

  • Consistency (C): Every read receives the most recent write (or an error). All nodes see the same data at the same time (strong consistency).
  • Availability (A): Every request (read or write) receives a non-error response, without guarantee of the most recent write.
  • Partition Tolerance (P): The system continues to operate despite network partitions (some messages between nodes are lost or delayed). This is often non-negotiable in real distributed systems, as networks are unreliable.

In practice, during a network partition, the database must choose between Consistency (CP) or Availability (AP). Many systems also offer tunable consistency levels or operate in a "CA" mode in non-partitioned scenarios (but partitions are the key test).

How Different Databases Handle CAP

Databases make explicit or configurable trade-offs. Here's how popular ones align:

CP Systems (Consistency + Partition Tolerance)

These prioritize strong consistency. During partitions, they may become unavailable (or delay responses) on some nodes to avoid serving stale or conflicting data. Ideal for finance, transactions, or accuracy-critical apps.

  • MongoDB: Typically CP. Uses a primary node for writes; secondaries replicate. During partitions, it may elect a new primary or block writes to maintain consistency, sacrificing availability temporarily. It offers tunable read concerns (e.g., majority reads for stronger consistency).
  • PostgreSQL / MySQL (in distributed/replicated setups): Traditional relational DBs lean CP. They emphasize strong consistency (ACID transactions) and can handle partitions by failing over or becoming unavailable on isolated nodes. Horizontal scaling is harder without add-ons.
  • HBase: CP-oriented, often used where strong consistency is needed.
  • Redis (in certain clustered modes): Can prioritize consistency.

AP Systems (Availability + Partition Tolerance)

These keep responding to requests even during partitions, accepting eventual consistency (data converges over time once the partition heals). Great for high-traffic, globally distributed apps like social media, e-commerce catalogs, or IoT where immediate availability matters more than perfect freshness.

  • Apache Cassandra: Strongly AP. Peer-to-peer design; any node can handle reads/writes. Uses tunable consistency (e.g., QUORUM) but defaults to high availability with eventual consistency via anti-entropy repairs and hinted handoffs.
  • Amazon DynamoDB: AP by design (inspired Dynamo). High availability and partition tolerance; offers eventual consistency by default, with optional strong consistency reads. Excellent for scalable, always-on workloads.
  • Others: Riak, CouchDB (configurable), Cosmos DB (tunable).

CA Systems (Consistency + Availability)

These provide strong consistency and availability when there are no partitions. In true distributed systems with partitions, they often fall back to CP (sacrificing availability). Many traditional single-node or tightly-coupled systems fit here.

  • Oracle, traditional MySQL/PostgreSQL (non-sharded): Prioritize CA in normal operation but may sacrifice A during partitions for C.
  • Note: Pure CA is rare in highly distributed setups because partitions are inevitable.

Flexible / Tunable Systems

  • MongoDB: Can behave more AP with certain configurations (e.g., relaxed read/write concerns).
  • DynamoDB / Cassandra: Knobs for consistency levels (e.g., read/write to majority of replicas vs. one).
  • CockroachDB / Spanner (Google): Aim for strong consistency with high availability using advanced techniques like consensus protocols (e.g., Raft/Paxos), but still make trade-offs under extreme partitions.

Key Takeaways and Nuances

  • "2 of 3" is a simplification: Real systems operate in a spectrum. Many use quorum-based replication, eventual consistency, or conflict resolution (e.g., last-write-wins, CRDTs) to soften trade-offs. PACELC theorem extends CAP to include latency/ consistency choices even without partitions.
  • Use case drives choice:
    • Banking/transactions → CP (strong consistency).
    • Social feeds, recommendations → AP (high availability).
  • Modern improvements: Multi-master replication, consensus algorithms, and hybrid models blur lines. No database is "perfect"—evaluate based on your tolerance for stale reads vs. downtime.

Read more