Databases
Intermediate 15 min read Databases

The CAP Theorem

The triangle that explains every distributed database's trade-off

CAP says a distributed store can guarantee at most two of consistency, availability, and partition tolerance during a partition. Under network failure you choose consistent or available behavior, and PACELC adds what happens the rest of the time.

CAPPACELCconsistencyavailabilitypartitionquorum
Prerequisites: Transactions and Isolation
Before we start

What you will learn

  • State CAP and what is actually being decided under a partition
  • Map popular systems to CAP/PACELC choices
  • Translate a product requirement into a consistency and availability regime
Introduction

What is this?

CAP states that in a distributed system, when the network splits, you must choose between consistency (every node answers the same value) and availability (every request gets a response). Partition tolerance — continuing to serve during the split — is not optional; it is the physical reality you design around.

Motivation

Why do you need it?

  • Every distributed store sells itself on a CAP compromise; you must know which one you bought.
  • REQUIRED slug: de-foundations links here as the canonical reference for distributed database trade-offs.
  • The same idea reappears in quorums, replication, streaming offsets, and warehouse ELT decisions.
Think about it

Mental model

Imagine

Two tellers on a phone line that just dropped

Think of

A system under partition

Teller A is happy to accept a withdrawal and teller B is happy to serve too, but unless they can talk, one of them may hand out money that is already spent. You decide who suffers: the balance check (consistency) or the queue (availability).

Mechanics

How it works

  • A 'partition' means some nodes cannot exchange messages; there is no way for both sides to stay synchronized.
  • Choosing availability: both sides serve possibly-stale or conflicting data; conflicts get merged or lost later.
  • Choosing consistency: one side refuses writes or waits; requests may time out, but reads agree.
  • PACELC extends CAP: else-when (no partition, E) you pick Latency or Consistency.
  • Most systems are CP (Postgres with synchronous replicas), AP (Cassandra, DynamoDB), or CP-with-async (Postgres async replicas: strong on primary, eventual on replica).

How the trade-off plays out during a partition.

Node A & B
Link fails
CP path
AP path
Heal + reconcile
Reference

Key commands

cqlsh> CONSISTENCY LOCAL_QUORUM;

Raise Cassandra read/write consistency to minority-tolerant quorum.

aws dynamodb get-item --consistent-read

Force strongly-consistent DynamoDB reads (2x RCU cost).

kubectl exec svc/postgres -- psql -c 'SELECT * FROM pg_stat_replication'

See how many synchronous replicas ack a commit in a CP setup.

Hands-on

Examples

Reading the same record from two products

Reading the same record from two products
-- Strongly consistent read (CP flavor):
--   MySQL: SELECT ... FOR UPDATE after committing on the primary
--   Postgres sync replica: SELECT from primary, replica never observable-stale
 
-- Eventually consistent read (AP flavor):
--   Cassandra: SELECT ...   <consistency> QUORUM vs ONE
--   DynamoDB: read with ConsistentRead: false (default) vs TRUE

The same logical read is answered differently depending on which guarantee you require at query time.

Real world

In production

  • Payment ledger writes use CP: fail the write if a quorum cannot ack, rather than double-spend.
  • Recommendation counters use AP: a stale like-count is acceptable, a queue rejecting traffic is not.
  • A warehouse load balancer reads analytics from replicas tolerant of minutes-old data (E: latency > consistency).
Guidelines

Best practices

  • Write the guarantee into the SLO: 'at-most 5 seconds staleness on read replicas' is concrete; 'eventual' is not.
  • Test partition behavior on purpose (network-level chaos) before an accident does it for you.
  • Track which nodes hold conflicting data during a partition so the merge policy is decided in advance.
Watch out

Common mistakes

  • Believing a system is 'both': the theorem says at most two, and 'consistency during wearisome partitions' is usually availability renamed.
  • Skipping the E in PACELC and ignoring that normal-time latency is a real consistency trade-off.
  • Testing consistency only when the network is healthy; partitions are rare and that is exactly why they are un-modeled.
When things break

Debugging tips

  • When reads disagree after an outage, assume a partition happened, then replay the event log or merge policy to reconcile.
  • Check quorum thresholds on the write path; one reordered ack can flip the answer under minority writes.
  • Use a chaos experiment that partitions replicas from the primary and observe what the API returns, not the theory.
Interviews

Interview checkpoint

Test yourself

Quick quiz

0/2
1

During a network partition, how many of the three properties can a system guarantee?

2

A single-node relational database avoids CAP concerns because nothing is partitioned.

Go deeper

Official documentation

CAP theorem (Wikipedia)
docs
Jepsen consistency analyses
docs
MongoDB concurrency FAQ
docs