CAP Theorem

CAP is not a slogan that says "pick two forever." It is a failure-mode theorem. It asks what a replicated system does when the network stops carrying messages between replicas.

The practical version:

In real networks, partitions are not optional. Links fail, packets drop, clocks drift, routers flap, cloud zones isolate, deploys wedge service discovery. So the choice under pressure is usually CP or AP.

Imagine a replicated profile service. Two regions hold the same user record. Clients can read from either region. Writes replicate across the network.

When the link is healthy, the system can often give you all three properties in ordinary operation: reads return, writes replicate, and both regions converge on the same value.

CAP becomes interesting only when the replication link breaks.

A partition is not necessarily a machine crash. Both machines may be healthy. The trouble is that they cannot talk to each other.

At this exact point, eu-west has a local copy that still says 100. If it answers 100, the system stays available but may violate consistency. If it refuses to answer until it can contact us-east, the system protects consistency but gives up availability for that request.

During a partition, a replicated system has two honest choices.

The sharp lesson: CAP is not about what your system says on a sunny day. It is about the behavior you choose when the replicas disagree or cannot communicate.

CP systems preserve a single agreed value during partitions. If they cannot prove a write or read is safe, they refuse it, wait, or redirect to a leader.

Common CP behavior:

Examples that lean CP: ZooKeeper, etcd, Consul, Spanner-style strongly consistent databases, many SQL systems configured for synchronous replication.

Use CP when the wrong answer is worse than no answer: bank transfers, inventory reservation, identity and permissions, distributed locks, schema migrations, leader election, billing mutations.

AP systems keep answering during partitions. They accept that replicas may temporarily disagree, then repair the disagreement later.

Common AP behavior:

Examples that lean AP: Dynamo-style key-value stores, Cassandra-style systems, shopping carts, feeds, counters with merge logic, telemetry ingestion, logs, recommendation events.

Use AP when no answer is worse than a temporarily imperfect answer: likes, analytics events, shopping carts, presence, recommendations, feeds, sensor data, non-critical user preferences.

The common triangle is useful as a doorway, then harmful as a map.

Modern systems are not one CAP point. A product may choose CP for account balances, AP for notification counters, and eventual consistency for profile search. The boundary is per workflow, per data type, and per failure mode.

Suppose an item has one unit left in stock, replicated across two regions.

If Region B confirms the second order, availability is high but the store oversells. If Region B blocks, consistency is protected but the customer sees an error or delay.

For checkout inventory, CP is often the safer default. For adding that item to a cart, AP is usually fine because conflicts can be resolved before payment.

Use this checklist when designing a feature:

Hold CAP in your head as one picture:

A strong explanation does not recite "C, A, P, pick two." It says:

1. Partitions are unavoidable in distributed systems.
2. During a partition, each operation must choose between answering locally and preserving a single agreed value.
3. If stale or conflicting data is dangerous, choose CP behavior.
4. If temporary divergence is acceptable and repairable, choose AP behavior.
5. Many real products mix both choices across different workflows.

The CAP tradeoff is not abstract. It shows up as a family of well-known bugs that appear the moment data lives on more than one machine. Each problem below has the same root: two copies of the truth that cannot coordinate instantly. The sections that follow each give the problem in plain terms, a concrete worked example with specific values, and the named techniques that fix it.

A useful frame before the list: most of these are not solved by "choosing CP" or "choosing AP" alone. They are solved by adding a small, targeted guarantee to one operation, such as a version check, a routing rule, or an idempotency key.

A stale read is when a client reads an old value because it hit a replica that has not yet received the latest write. This is the everyday face of AP behavior, and it happens even without a full partition, whenever replication is slower than the read that follows the write.

Worked example. A user has balance 100. They transfer money and the system writes balance = 80 to the leader. Replication to a follower is lagging by 400 ms. Two hundred milliseconds later the same user refreshes their balance, the read is routed to that lagging follower, and they see 100. The money looks like it came back. Nothing is corrupt; the follower is simply behind.

How it is fixed. A quorum is a required minimum number of replicas that must agree before an answer counts; a quorum read asks enough replicas that at least one is guaranteed to hold the latest write.

The cost is latency or load on the leader, which is why leader reads are reserved for data where a stale answer is genuinely harmful.

These are the client-centric consistency guarantees. They do not demand that the whole system agree at every instant; they only promise that a single client's view stays sensible. Read-your-writes means you always see your own latest write. Monotonic reads means time never appears to run backward for you: once you have seen a value, you will not later see an older one. Causal consistency means effects never appear before their causes: if write B depends on write A, no client sees B without A.

Worked example. A user posts a comment. The write lands on replica R1. The user's next request, a page refresh, is load-balanced to replica R2, which has not yet received the comment. The comment vanishes from their own screen, then reappears a second later. Worse, without monotonic reads, a following refresh could hit R1 again and show it, then R2 again and hide it, flickering.

How it is fixed. A version vector is a small map from each replica to the highest version it has produced; carrying it lets a replica tell whether it is new enough to answer.

Sticky routing is the cheapest fix and covers most user-facing cases; causal tokens are the general solution when a session can move between replicas.

A lost update happens when two clients read the same value, each computes a new value from it, and each writes back, so the second write silently erases the first. The database never errors. One person's change simply disappears.

Worked example. A page-view counter reads 10. Two servers handle two hits at the same moment. Both read 10, both compute 10 + 1 = 11, both write 11. Two views happened; the counter now says 11. One increment is gone.

How it is fixed. Optimistic concurrency means you do not lock; you write only if the value has not changed since you read it, using a version number and a compare-and-set. If the version moved, your write is rejected and you retry.

UPDATE counters
SET value = 11, version = 5
WHERE id = 42 AND version = 4;

If another writer already bumped the row to version 5, this UPDATE matches zero rows, the client sees it failed, re-reads, and retries with the fresh value.

When more than one node can accept writes for the same record, two writes to the same data can happen with neither aware of the other. This is common in multi-region active-active setups and in offline-capable apps that sync later. During a partition there is no way to order the two writes as they happen.

Worked example. A shared document has title "Draft". Region A, serving European users, renames it to "Q3 Plan". Region B, serving American users, renames it to "Third Quarter" at nearly the same second, while the inter-region link is down. When the link heals, the system holds two conflicting titles for one document and must decide which survives.

How it is fixed. Last-write-wins (LWW) keeps the write with the highest timestamp and discards the other; it is simple but silently loses one user's edit, and it depends on clocks that may disagree. A CRDT (conflict-free replicated data type) is a data structure whose merge rule is defined so concurrent updates always combine deterministically without loss, for example a set that keeps every added element.

Split-brain is when a partition cuts a cluster in two and each side elects its own leader, so both sides accept writes. When the network heals, there are two divergent histories and no clean way to reconcile authoritative state.

Worked example. A three-node cluster has leader N1 and followers N2, N3. The network isolates N1 on one side and N2, N3 on the other. N2 and N3 no longer hear N1's heartbeats, so they elect N2 as leader. N1 still believes it is leader. A client on N1's side writes x = "a"; a client on the other side writes x = "b". Both sides acknowledge. There are now two truths.

How it is fixed. A fencing token is a number that increases every time leadership changes; storage rejects any write carrying a token older than the newest it has seen, so a deposed leader cannot mutate state even if it still believes it leads.

The majority rule is the foundation: with three nodes, a partition can only ever give one side a majority, so at most one leader can exist.

The dual-write problem is trying to update two independent systems, such as a database and a message broker, and hoping both succeed. There is no shared transaction across them, so a crash between the two writes leaves them inconsistent.

Worked example. An order service saves an order row to its database, then publishes an "OrderPlaced" event to Kafka so shipping and email services react. The database commit succeeds. Before the publish returns, the process crashes. The order exists, but no event was ever sent, so shipping never learns about it and the customer is charged with nothing shipped.

How it is fixed. A transactional outbox writes the event into an "outbox" table in the same database transaction as the business row, so either both commit or neither does; a separate relay then reads the outbox and publishes. Change data capture (CDC) tails the database's commit log and turns each committed row change into an event, so the event is derived from the durable write itself.

Some operations must update several services and either all commit or none do. With each service owning its own database, there is no single transaction to wrap them, so a partial failure can leave the operation half-done.

Worked example. Placing an order must create an order, capture a payment, and reserve inventory, each in a different service. Payment succeeds, then the inventory service is down, so the reservation fails. Now the customer is charged but holds no reserved stock, an unacceptable half-state.

How it is fixed. Two-phase commit (2PC) is a protocol where a coordinator asks every participant to prepare, then tells them all to commit; it gives atomicity but blocks if the coordinator dies after prepare, holding locks indefinitely. A saga is a sequence of local transactions where each step has a compensating action that undoes it, so a later failure triggers compensations that roll the whole operation back logically.

For the order example, a saga would refund the payment as the compensation for the failed inventory step, leaving the customer whole. Prefer sagas over 2PC across service boundaries; reserve 2PC for tightly coupled resources that can afford its blocking risk.

Exactly-once delivery, meaning a message is processed one time and only one time end to end, is not achievable over an unreliable network. A sender that does not receive an acknowledgment cannot tell whether the message was lost or whether only the acknowledgment was lost, so it must retry, which can duplicate.

Worked example. A payment service sends "charge $50" and the network drops the response. The service retries. The card is charged twice, for $100 total, because the first charge actually went through.

How it is fixed. The practical pattern is at-least-once delivery combined with idempotency, so duplicates are harmless. An idempotency key is a unique identifier the client attaches to the operation; the server records processed keys and ignores a repeat. This is often called effectively-once.

With an idempotency key on the charge, the retried "charge $50" carries the same key, the server sees it already processed that key, and returns the original result without charging again.

A thundering herd is a stampede of clients all retrying at the same instant, overwhelming a resource just as it tries to recover. A metastable failure is when the retries themselves keep the system down: the load never drops enough for it to catch up, so it stays stuck even after the original trigger is gone.

Worked example. A partition isolates a service for 30 seconds. Ten thousand clients time out and queue retries. When the partition heals, all ten thousand retry in the same second. The recovered node, still cold, is flattened by the surge, times out again, and the clients retry once more, holding it down.

How it is fixed.

Jitter is the single most important fix: turning a synchronized spike into a spread-out trickle is often enough on its own.

Machine clocks never agree perfectly. Clock skew is the difference between two nodes' clocks. Any scheme that orders events by wall-clock time, such as last-write-wins, can pick the wrong winner when the clocks disagree by more than the gap between the two writes.

Worked example. Node A's clock is 500 ms ahead of node B's. At true time T, node B writes the correct newer value with timestamp T. Slightly earlier, at true time T minus 200 ms, node A writes an older value, but stamps it T plus 300 ms because its clock is fast. Last-write-wins compares 300 ms ahead against T, keeps node A's older value, and discards the write that actually happened later.

How it is fixed. A Lamport clock is a simple counter that increases on every event and every message, giving a consistent order without trusting wall clocks. A hybrid logical clock (HLC) combines a physical timestamp with a logical counter so order is preserved even when clocks drift. TrueTime is Google Spanner's approach: GPS and atomic clocks bound the uncertainty, and a commit waits out that bound so external order is guaranteed.

The FLP result (named for Fischer, Lynch, and Paterson) proves that in a purely asynchronous network, no deterministic algorithm can guarantee agreement if even one node may fail, because a slow node and a dead node are indistinguishable. A protocol waiting for certainty could wait forever.

Worked example. A Raft cluster starts a leader election, but two candidates split the votes evenly and neither reaches a majority. In a purely deterministic timing scheme they could keep colliding on every attempt, stuck forever.

The practical escape is to give up pure determinism and add timing and randomness. Raft has each node wait a randomized election timeout, so one candidate almost always wakes first, wins the majority, and the tie resolves. Timeouts let the system treat a silent node as failed and move on; randomness breaks the symmetry that FLP shows determinism cannot.

PACELC extends CAP to cover normal operation. It reads: if there is a Partition (P), trade Availability (A) versus Consistency (C); Else (E), when running normally, trade Latency (L) versus Consistency (C). CAP only describes the partition case; PACELC points out that the same tension exists on a healthy network, because staying strongly consistent still costs coordination latency.

Worked example. With no partition at all, a globally replicated write can either wait for remote replicas to acknowledge, which is slower but consistent, or return after a local write, which is faster but may serve stale reads elsewhere. The network is fine; the tradeoff is purely latency against consistency.

PACELC is the honest full picture: a system is described by two choices, one for partitions and one for the ordinary day.

• CAP is a partition-time theorem, not a general database ranking.
• Because partitions happen, the real choice is usually CP versus AP.
• CP sacrifices availability to protect one agreed value.
• AP sacrifices immediate consistency to keep serving requests.
• Design the tradeoff per operation, not per brand name or whole system.
• The famous distributed bugs (stale reads, lost updates, split-brain, dual-write, clock skew) all trace back to two copies of the truth that cannot coordinate instantly.
• Most are fixed by adding one targeted guarantee, not by picking CP or AP wholesale: a version check, a fencing token, an idempotency key, a causal token, or an outbox.
• PACELC completes the picture: even with no partition, strong consistency still costs latency, so every system carries two choices, one for partitions and one for the ordinary day.