CAP Theorem Visualization | CP vs AP During a Network Partition

The idea: one key, three copies, a cut in the network

A key x is stored on three nodes, N1, N2 and N3. Client C1 talks to N1, client C2 talks to N3. Then the network partitions: messages between two groups of nodes are lost. A node on one side can still hear its own client, but not the other side. It has two choices: answer, and risk giving an old value or accepting a write the other side never sees, or refuse (wait, time out, return an error) until it can talk to the others again. That choice is the CAP theorem.

Three nodes N1, N2, N3 all holding x = v0; client C1 talks to N1, client C2 talks to N3; a partition line separates N1 and N2 (the majority) from N3, and messages across it are lost — During a partition, N3 can hear its client C2 but not N1 or N2.

The page runs the same operations through two stores at once, on one clock. On the left, a CP store in the style of Raft (etcd, ZooKeeper, Consul). On the right, an AP store in the style of Dynamo (Cassandra, Riak). Every message takes one tick, a message across the partition is dropped (red, ✗), and a client gives up after 8 ticks. The table under each side checks every answer: a read is STALE if it returns something older than a write that was already acknowledged, and a write is LOST if it was acknowledged but later vanished.

What C, A and P mean exactly

letter	meaning in the theorem	not to be confused with
Consistency	Linearizability: the system behaves as if there were one copy; once a write is acknowledged, every later read sees it (or something newer).	the C in ACID (constraints hold)
Availability	Every request to a node that has not crashed gets a non-error answer, eventually.	"99.99% uptime"
Partition tolerance	The system keeps its promises even when the network loses any number of messages between nodes.	a choice you can skip: networks do partition

The proof (Gilbert and Lynch, 2002) fits in four sentences. Cut the network between N3 and the rest. C2 writes v1 to N3. If N3 answers OK (available), then C1 reading from N1 cannot see v1, because no message got through, so the read is stale (not consistent). If N3 refuses to answer until it can reach the others, it is not available. So during a partition you pick one: C or A.

Two panels. CP: C2's write of v1 to N3 times out because N3 cannot reach a majority, and C1 reads v0 from N1, which is correct since v1 was never acknowledged: consistent, not available. AP: N3 stores v1 alone and answers OK, and C1 reads v0 from N1, a stale read: available, not consistent — The same two requests during the partition: CP refuses C2's write and stays consistent; AP accepts it and C1 reads a stale value.

The CP choice: majorities, and the minority waits

The CP store has one leader. A write is appended to the leader's log, sent to the followers with AppendEntries, and committed once a majority (2 of 3) has it. Only then does the client hear OK. A follower forwards requests to the leader. Any two majorities overlap in at least one node, so a committed write can never be missed by a later leader.

During a partition, the side with a majority carries on. The side without one can't commit, so its clients time out (Demo 2: C2's write on N3 fails). If the leader itself ends up in the minority, it can't commit either. After the election timeout, the majority elects a new leader with a higher term. On heal, the old leader sees the higher term, steps down and throws away its uncommitted entries. Nobody was told those entries succeeded, so nothing acknowledged is lost (Demo 3). A lone follower uses pre-vote: it asks whether it could win before starting an election, so it does not bump its term and disrupt the cluster when it comes back. The full protocol is on the Raft page.

The AP choice: always answer, sort it out later

The AP store has no leader. The client's own node coordinates: it stores the write, sends PUT to the other replicas and answers once W of them (itself included) have it. A read asks R replicas and returns the newest version. With W = 1, R = 1, every node answers on its own, so every request succeeds during a partition. The price: C1 can read v0 after C2's v1 was acknowledged (Demo 2: STALE), and both sides can accept different writes to the same key (Demo 3).

When the partition heals, anti-entropy runs: replicas compare what they hold (real systems compare Merkle trees, so they only send the differences) and exchange the versions that are missing. The replicas converge: this is eventual consistency.

Resolving conflicts: last write wins vs vector clocks

	last write wins (LWW)	vector clocks, siblings
each version carries	a timestamp	a counter per node, e.g. `[1,0,0]`
two versions meet	higher timestamp wins, the other is dropped	if one clock is ≥ in every position it wins; otherwise they are concurrent and both are kept
concurrent writes	one acknowledged write is silently lost (Demo 3)	a read returns both siblings; the client merges them and writes back (Demo 4)
used by	Cassandra (per cell), DynamoDB global tables	Riak, the original Dynamo

LWW also depends on the clocks: with clock skew, an older write can carry a newer timestamp and win. CRDTs (counters, sets and maps with a built-in merge) avoid the client merge for data types that support it.

Quorums: R + W > N is a dial

With N = 3 copies, if every write waits for W acks and every read asks R replicas with R + W > N, then every read set overlaps every write set, so a read sees the latest acknowledged write. The cost is the same as for CP: a node that can't reach enough replicas must refuse (Demo 5: with W = 2, R = 2 the AP store gives the same results as the CP store). Even then it is not quite linearizable. A failed write can stay on the node that took it and show up later (at the end of Demo 5, N3 still holds v1 although C2 was told the write failed, and a read with R = 1 there would return it). Sloppy quorums with hinted handoff count "any N reachable nodes" instead of the key's real replicas. Concurrent reads can also race with read repair.

Reads matter too: ReadIndex and the deposed leader

A CP store is only consistent if its reads are. A leader that answers reads from its own state may no longer be the leader: a newer one may have been elected on the other side of a partition and may have committed new writes. With leader-local reads, Demo 6 returns v0 after v1 was committed. ReadIndex (etcd) makes the leader confirm, with one heartbeat round to a majority, that it is still the leader before answering. Leader leases skip that round but rely on bounded clock drift.

PACELC: without a partition, latency vs consistency

Partitions are rare; latency is every request. Abadi's PACELC: if there is a Partition, choose A or C; Else choose Latency or Consistency. In Demo 1, with no partition, the CP write takes 4 ticks from C1 and 6 from C2 (forward to the leader, majority round trip). The AP write with W = 1 takes 2.

system	partition	else
etcd, ZooKeeper, Consul, Spanner, CockroachDB	PC (minority refuses)	EC (majority round trip per write)
Cassandra, Riak, Dynamo (with small R, W)	PA	EL
MongoDB (majority write concern)	PC	EC; reads from secondaries trade toward EL
MySQL / PostgreSQL with async replicas	replicas stay readable (PA for reads)	EL: replica reads can lag

Common misreadings

"Pick two of three." P is not something you give up. Without a partition, you can have both C and A. The choice only arises while the network is broken. "CA system." A single-node database is "CA" only because it has no network to partition. "Cassandra is AP." Most real stores are tunable per request (W, R, write concern, QUORUM). Labels describe a configuration, not a product. "C in CAP = C in ACID." No. For isolation levels (a different kind of consistency) see MVCC and Isolation Levels.

See also Raft (elections and log repair in full), Primary–Replica Replication (replication lag, stale reads, failover), Redis Sentinel (split brain and min-replicas-to-write) and Consistent Hashing (preference lists and hinted handoff in Dynamo-style stores).

What the page leaves out

Heartbeats on every tick (only the ones that matter are drawn), randomized election timeouts, clock skew for LWW, the Merkle trees themselves, read repair, sloppy quorums and hinted handoff, CRDTs, more than one key, transactions across keys, and weaker consistency models between linearizable and eventual (causal, read-your-writes, monotonic reads; see Consistency Patterns).