The Three Guarantees
Consistency (C): every read receives the most recent write or an error. All nodes see the same data at the same time. A system is consistent if reading from node A immediately after writing to node B returns the value just written.
Availability (A): every request receives a (non-error) response, though not necessarily the most recent write. The system stays operational even when some nodes are down.
Partition Tolerance (P): the system continues to operate even when network partitions (communication failures between nodes) occur. In a distributed system, network partitions are inevitable — hardware fails, cables are cut, switches malfunction.
CAP Theorem (Eric Brewer, 2000): in the presence of a network partition, a distributed system must choose between Consistency and Availability. You cannot have both.
Why Partition Tolerance is Not Optional
Network partitions happen in real distributed systems — no one can prevent them. Therefore, any distributed system must be partition tolerant. This means the real choice is not between C, A, and P — it's between C and A when a partition occurs.
CP systems: when a partition occurs, the system refuses reads/writes to nodes that cannot communicate with the majority (to avoid returning stale data). Example: HBase will stop serving a region if the RegionServer loses contact with the HMaster. MongoDB in default w=1 is CP — if the primary is unreachable, reads from secondaries may be stale (configurable).
AP systems: when a partition occurs, all nodes continue serving requests, accepting that their data may diverge temporarily. After the partition heals, the system reconciles (eventual consistency). Example: Cassandra always serves reads/writes even during a partition.
graph TD CAP["CAP Theorem"] --> CP["CP Systems (MongoDB, HBase, Zookeeper) Consistent but may refuse requests"] CAP --> AP["AP Systems (Cassandra, CouchDB, DynamoDB) Always available, eventually consistent"] CAP --> CA["CA Systems (MySQL, PostgreSQL) No partition tolerance — single node only"]
Consistency Models
Strong Consistency: every read reflects all previous writes. Equivalent to a single-server system. Implementation: all nodes confirm a write before it's acknowledged (synchronous replication). High latency but never stale.
Eventual Consistency: given enough time without new writes, all nodes will converge to the same value. No guarantee of when. Used by DNS, Cassandra (with low consistency level), and many web caches.
Causal Consistency: preserves cause-and-effect ordering. If you post a comment after reading a post, other users who see your comment will also see the post. Stronger than eventual, weaker than strong.
Read-Your-Writes Consistency: after writing, the same user always reads their own write (even if other users may see stale data). Easy to implement: route the user's reads to the node where they wrote.
PACELC — Beyond CAP
CAP only addresses partition scenarios. PACELC extends CAP: "if there is a Partition, trade-off between Availability and Consistency; Else (when running normally), trade-off between Latency and Consistency."
Even without partitions, you must choose: (1) Strong consistency (synchronous replication) → higher latency. (2) Lower latency (asynchronous replication, local writes) → stale reads possible.
PACELC classification: PA/EL (Cassandra): available during partition, low latency during normal operation. PC/EC (MySQL, Zookeeper): consistent during partition, consistent (low latency possible with single node) during normal operation. DynamoDB: PA/EL by default, configurable to PC/EC.
Practical Implications
In system design interviews, discuss CAP trade-offs when choosing your database: "I'll use Cassandra (AP) for the user timeline because I can tolerate eventual consistency — it's acceptable if a user sees a post a few seconds late. I'll use MySQL (CP) for the payment system because I cannot afford to show an incorrect balance."
Common AP examples: DNS resolution, CDN caching, shopping cart (add to cart always succeeds, inventory check happens later), social media feeds. Common CP examples: financial transactions, account balances, inventory management, ticketing (no double-booking).