CAP Theorem Explained — A Practical Guide to Distributed System Trade-offs

What is the CAP theorem?#

The CAP theorem, proposed by Eric Brewer in 2000 and proven by Gilbert and Lynch in 2002, states that a distributed system can provide at most two out of three guarantees simultaneously:

• Consistency — every read receives the most recent write or an error
• Availability — every request receives a non-error response (though it may not contain the most recent write)
• Partition tolerance — the system continues to operate despite network partitions between nodes

Since network partitions are inevitable in any distributed system, the real choice is between consistency and availability when a partition occurs.

Why partitions are unavoidable#

A network partition happens when communication between nodes is disrupted — a cable fails, a switch dies, a cloud availability zone becomes unreachable. In any system that spans multiple machines, partitions will happen.

This means the CAP theorem is not really a three-way choice. It is a two-way choice: CP or AP — what does your system do when a partition occurs?

CP systems — choosing consistency#

A CP system refuses to serve requests that might return stale data during a partition. It sacrifices availability to guarantee consistency.

ZooKeeper#

ZooKeeper uses ZAB (ZooKeeper Atomic Broadcast) to maintain a consistent view across all nodes. During a partition:

• The side with the majority (quorum) continues to operate
• The minority side stops accepting writes
• Reads on the minority side may also be rejected depending on configuration

ZooKeeper prioritizes consistency because it is used for coordination — lock management, leader election, and configuration that must be correct.

HBase#

HBase relies on ZooKeeper for region assignment and uses a single RegionServer per data region. If a RegionServer fails or becomes partitioned:

• The region becomes unavailable until reassignment
• No stale reads are possible because only one server owns each region
• Recovery involves detecting the failure and assigning the region to another server

etcd#

etcd uses the Raft consensus protocol. During a partition, only the side with the leader and a majority of followers can process writes. The minority side returns errors. This makes etcd strongly consistent but unavailable during certain partition scenarios.

AP systems — choosing availability#

An AP system continues to serve requests during a partition, even if some nodes have stale data. It sacrifices consistency for availability.

Cassandra#

Cassandra allows tunable consistency, but its default behavior favors availability:

• During a partition, all nodes continue accepting reads and writes
• Writes go to whichever replicas are reachable
• After the partition heals, anti-entropy repair and read repair reconcile divergent data
• Conflict resolution uses last-writer-wins by default

DynamoDB#

DynamoDB is designed for high availability across AWS regions:

• Writes are acknowledged once a quorum of replicas responds
• During a partition, the system may serve stale reads from isolated replicas
• Eventual consistency is the default read mode
• Strongly consistent reads are available but route to the leader replica

Couchbase#

Couchbase replicates data across nodes and continues to serve requests during partitions. It uses automatic conflict resolution and can be configured with different consistency levels per operation.

Consistency models explained#

The "C" in CAP is specifically linearizability — the strongest consistency model. But distributed systems offer a spectrum of consistency levels.

Linearizability (strong consistency)#

Every operation appears to execute atomically at a single point in time between its invocation and response. All clients see the same order of operations. This is the gold standard but requires coordination, which adds latency.

Sequential consistency#

All operations appear in some sequential order, and operations from each individual process appear in the order they were issued. Different from linearizability because the global order does not need to respect real-time ordering.

Causal consistency#

Operations that are causally related are seen in the same order by all nodes. Concurrent operations (no causal relationship) may be seen in different orders by different nodes. Stronger than eventual consistency, achievable without coordination.

Eventual consistency#

If no new writes are made, all replicas will eventually converge to the same value. No guarantees about how long convergence takes or what clients see in the meantime. This is the weakest useful consistency model.

Read-your-writes consistency#

A client always sees the effects of its own writes. Other clients may see stale data. This is often implemented by routing a client's reads to the same replica that handled its writes.

PACELC — beyond CAP#

The CAP theorem only describes behavior during partitions. Daniel Abadi proposed PACELC to address normal operation too:

If there is a Partition (P), choose Availability (A) or Consistency (C). Else (E), choose Latency (L) or Consistency (C).

This captures a crucial insight: even when the network is healthy, there is a trade-off between consistency and latency. Synchronous replication gives consistency but adds round-trip latency.

PACELC classifications#

Systems like MongoDB are interesting — they default to AP behavior during partitions but prioritize consistency during normal operation.

Real-world trade-offs#

Banking and finance#

Financial systems typically choose CP. A bank cannot show different account balances to two ATMs simultaneously. Unavailability (declining a transaction) is preferable to inconsistency (allowing an overdraft).

Social media#

Social platforms typically choose AP. If a user posts a photo and a friend in another region does not see it for a few seconds, that is acceptable. Showing a slightly stale feed is better than showing an error page.

E-commerce#

E-commerce often uses a hybrid approach:

• Product catalog: AP — stale product descriptions are acceptable
• Inventory count: CP — overselling is costly
• Shopping cart: AP — availability matters more than perfect consistency (Dynamo was built for this)

DNS#

DNS is a classic AP system. Name servers return cached records that may be stale, but the system is always available. TTL values control how quickly changes propagate.

Choosing your consistency level#

Questions to guide your decision:

1. What happens if a user sees stale data? If the consequence is financial loss or safety risk, choose strong consistency. If the consequence is a minor UX issue, eventual consistency may suffice.

2. What is your latency budget? Strong consistency requires coordination round trips. If you need sub-millisecond responses, eventual consistency is likely necessary.

3. How often do conflicts occur? If writes to the same key are rare, eventual consistency with conflict resolution works well. If writes frequently collide, strong consistency avoids complex merge logic.

4. Can you use different levels for different operations? Most modern systems support per-operation consistency. Use strong consistency where it matters and eventual consistency everywhere else.

Common misconceptions#

"CAP means you can only have two of three." Technically true, but misleading. You always need partition tolerance, so the choice is CP or AP — and only during partitions.

"Eventual consistency means data loss." No. All replicas will converge. The question is what clients see during the convergence window.

"CP systems are always unavailable during partitions." Not entirely. The majority side of a partition typically remains available. Only the minority side loses availability.

"You must pick one model for your entire system." Modern databases support tunable consistency. You can use different levels for different tables, queries, or even individual operations.

Visualize CAP trade-offs#

On Codelit, generate a distributed database cluster and simulate network partitions to see how CP and AP systems behave differently. Toggle consistency levels to observe the impact on availability and latency.

---

This is article #239 in the Codelit engineering blog series.

Build and explore distributed system architectures visually at codelit.io.