CAP Theorem

The CAP Theorem, proved by Eric Brewer (2000) and formalized by Gilbert and Lynch (2002), states that a distributed data store can guarantee at most two of three properties: Consistency (every read returns the most recent write or an error), Availability (every request receives a non-error response, though it may be stale), and Partition Tolerance (the system continues operating despite network partitions). Since network partitions are a physical reality in any distributed system, the real choice is between CP and AP — CA systems exist only in single-node or non-distributed settings. MongoDB and HBase choose CP; Cassandra and DynamoDB choose AP; traditional RDBMS like PostgreSQL are CA (no partition tolerance, assume a reliable network).

Key Points

• Partition Tolerance is non-negotiable in any geographically distributed system — network links fail, packets are dropped, and you cannot prevent it, only choose how to respond.
• CP systems (MongoDB, HBase, Zookeeper) refuse to serve stale reads during a partition — they return errors or timeouts rather than risk inconsistency.
• AP systems (Cassandra, DynamoDB, CouchDB) continue serving reads and writes during a partition but may return stale data — they resolve conflicts after the partition heals.
• Eventual consistency (AP) is sufficient for most real-world use cases: shopping carts, social feeds, user profiles, recommendation engines — strong consistency is only critical for financial ledgers, inventory counts, and leader election.
• RDBMS (PostgreSQL, MySQL) are CA: they provide strong consistency and availability on a single reliable network, but a network partition causes them to stop accepting writes to preserve consistency.
• The CAP theorem applies per operation, not per system — a single system can be CP for writes and AP for reads by using read replicas with async replication.
• Linearizability is a stronger form of consistency than CAP's "C" — it guarantees real-time ordering, which requires consensus protocols like Raft or Paxos.
• CAP is a binary model; PACELC refines it by acknowledging that even without partitions, there is a latency vs. consistency trade-off in replica systems.