Storing data · Chapter 9

Consistency and CAP

What CAP really says (a choice made only during a network partition), PACELC, the consistency models from linearizable to eventual, and how N/R/W quorums work.

AdvancedInterview priority: High35 min
On this page
  1. The problem: two copies, and the cable between them breaks
  2. The idea: during a partition, choose correct or answering
  3. CAP, stated precisely
  4. PACELC: the trade-off you pay every day
  5. Consistency models: a ladder
  6. Quorums: tuning with N, W and R
  7. Choosing per operation, not per system
  8. When not to reach for CAP
  9. In the interview
  10. Quiz

The problem: two copies, and the cable between them breaks

You keep account balances on two database servers in different datacenters, so that one can serve if the other dies. Every write on one is copied to the other. Then the link between the datacenters fails for 90 seconds. Both servers are healthy, and users can still reach both, but the servers can't reach each other.

A user withdraws $20 on server A: the balance there is now $80. A moment later, a request to server B asks for the same balance. B still has $100. What should B do?

A network partition: the copies can't talk, and they now disagree

  1. Once your data lives on several machines, the network between them can fail. A cable is cut or a router dies, and the machines can no longer talk. That is a network partition.
  2. Now someone updates their balance on copy A. Copy B never hears about it. Then someone reads from copy B. What should B do?

This is a network partition: some nodes can't exchange messages with others, although each side keeps running. It is not hypothetical; switch failures, misconfigured firewalls, long garbage-collection pauses and cloud network faults all cause them.

The idea: during a partition, choose correct or answering

Refuse and stay correct, or answer and risk being stale

  1. Option one: refuse to answer until the network heals. Every answer it does give is correct, which is consistency. But some requests fail.
  2. Option two: answer anyway with what it has. Every request gets an answer, which is availability. But the answer may be out of date: 100 dollars instead of 80.

B has only two options:

  1. Refuse (or wait) until it can confirm the latest value with A. Every answer it gives is up to date, but some requests fail. This is choosing consistency.
  2. Answer with the $100 it has. Every request gets a reply, but the reply may be out of date. This is choosing availability.

There is no third option that is both, because B has no way to learn about A's write while the link is down.

CAP: during a partition, pick one; afterwards the copies converge

  1. The CAP theorem says: during a partition you must pick one, consistency or availability. When the network is healthy, you can have both.
  2. Systems that choose availability usually promise eventual consistency: once the network heals, the copies sync up and agree again.

CAP, stated precisely

The CAP theorem (proved by Gilbert and Lynch in 2002) says that a system replicating data over a network cannot provide all three of these at the same time:

  • Consistency, in a specific sense: linearizability. Every read returns the most recent completed write, as if there were one copy of the data.
  • Availability, also strict: every request to a node that hasn't crashed gets a non-error response, eventually.
  • Partition tolerance: the system keeps working when the network drops or delays messages between nodes.

Because partitions happen whether you like it or not, P is not really optional. CAP's practical meaning is narrow: when a partition happens, a node must either refuse some requests (CP) or risk returning stale data (AP). When the network is healthy, you can have both.

PACELC: the trade-off you pay every day

Partitions are rare. A more useful everyday question is the one in PACELC (Daniel Abadi): if there is a Partition, choose A or C; Else, choose Latency or Consistency.

Even with a healthy network, keeping replicas in step means waiting for them. A write confirmed only after a replica in another region has it costs a cross-region round trip (100+ ms). Confirming locally and copying in the background is fast but lets a read elsewhere see old data.

System (default settings)During a partitionNormallyNotes
Cassandra, DynamoDB (default reads)AvailableLow latencyTunable per request: stronger settings shift towards C
Google Spanner, CockroachDBConsistentConsistent (pays latency)Majority agreement on every write
etcd, ZooKeeperConsistentConsistentSmall coordination data: locks, leaders, config
PostgreSQL with async replicasPrimary stays consistent; replicas serve stale readsLow latencyReplica lag is usually milliseconds, can be seconds

Consistency models: a ladder

"Consistent" has many levels. From strongest to weakest:

ModelGuaranteeExample of what it rules out
Linearizable (strong)Behaves like a single copy: once a write completes, every later read sees itReading $100 after the $80 withdrawal was confirmed
CausalIf one event could have caused another, everyone sees them in that orderSeeing a reply before the comment it answers
Read-your-writesA user always sees their own updatesChanging your profile photo, refreshing, and seeing the old one
Monotonic readsOnce you've seen a value, you never see an older oneA like count that goes 10 → 12 → 10 as you refresh
EventualIf writes stop, all replicas converge eventuallyNothing in the short term; only that they agree in the end

The weaker guarantees between "eventual" and "linearizable" are often enough and far cheaper. Read-your-writes, for instance, can be had by routing a user's reads to the primary for a few seconds after they write, or by having them carry the version they last wrote and waiting until a replica has caught up to it.

Serializable is not linearizable

Two words that sound alike answer different questions. Linearizability is about a single object (one key, one register) and real time: once a write completes, every later read sees it. Serializability is an isolation level for transactions that touch many objects: the result equals some one-at-a-time order of the transactions, but that order need not match the clock. A serializable database may legally show you a snapshot from a few seconds ago, as long as the history still looks sequential.

Strict serializability combines both: transactions appear to run one at a time, in an order that respects real time. Google Spanner offers it (it calls it external consistency). A single Postgres primary gives it at its SERIALIZABLE level, because there is one copy; reads from its async replicas do not.

Snapshot isolation and write skew

Many databases default to something weaker. Snapshot isolation (SI) gives each transaction a frozen view of the database as of its start, and aborts one of two transactions only if they write the same row. Postgres's REPEATABLE READ is SI, and Oracle's level named SERIALIZABLE is in fact SI.

SI permits write skew: two transactions read overlapping data, each decides based on what it read, and each writes a different row, so no conflict is detected. The classic example: a hospital rule says at least one doctor must be on call. Alice and Bob are both on call and both feel ill.

StepAlice's transactionBob's transaction
1Counts doctors on call: 2Counts doctors on call: 2
2"2 ≥ 2, I can leave": sets her row on_call = falseSame reasoning: sets his row on_call = false
3CommitsCommits (different row, no conflict)

Nobody is on call, though each transaction was correct on its own snapshot. The same shape breaks meeting-room bookings, username claims and "balance across two accounts must stay positive" checks.

Three ways to prevent it:

  1. Use SERIALIZABLE. Postgres implements it as serializable snapshot isolation: it tracks read/write dependencies and aborts one transaction with a serialization failure (SQLSTATE 40001), so your code must retry. Cost: some extra aborts under contention.
  2. Lock what you read: SELECT ... FROM doctors WHERE shift_id = 42 AND on_call FOR UPDATE. Bob's query now waits for Alice's lock, then sees only one doctor on call and refuses.
  3. Materialise the conflict, for when the rows you would lock don't exist yet (no booking row for 10:00 to lock). Create a row that stands for the thing being contended, such as one row per room and time slot or one per shift, and have every transaction lock or update it. The conflict becomes an ordinary same-row conflict. It works but leaks concurrency control into the schema, so treat it as the last resort.

See Postgres for its isolation levels in practice.

Quorums: tuning with N, W and R

With W + R greater than N, every read overlaps the latest write

  1. A clever middle ground is a quorum. With 3 copies, write to at least 2 and read from at least 2. Because 2 plus 2 is more than 3, every read overlaps the latest write, and you can still lose one machine.

Leaderless databases such as Cassandra (and Amazon's original Dynamo design) let you set three numbers:

  • N: how many replicas hold each item (the replication factor), typically 3.
  • W: how many replicas must confirm a write before it counts as successful.
  • R: how many replicas a read asks, returning the newest version among the answers.

A quorum is a group of replicas big enough that any two such groups overlap. If W + R > N, every read set shares at least one replica with the most recent successful write set, so the read can see that write.

Worked example: N = 3

WRW + R > N?Survives one node down?Character
11NoYes, reads and writesFastest; reads can be stale
22YesYes, reads and writesThe usual "QUORUM" setting
31YesReads yes, writes noFast reads, fragile writes
13YesWrites yes, reads noFast writes, fragile reads

With N = 5, W = R = 3 tolerates two failed nodes. Latency follows the slowest replica you wait for: with W = 2 of 3, you wait for the second-fastest, which also hides one slow node.

Choosing per operation, not per system

Payments lean consistent; feeds lean available

  1. In practice, banks and payments lean towards consistency. Social feeds, likes and shopping carts usually lean towards availability: a slightly stale like count is fine, an error page is not.

Most real systems mix levels:

OperationWhat breaks if staleChoice
Debit an account, book the last seatMoney lost, double bookingLinearizable: single primary or consensus; refuse during partitions
Unique username at sign-upTwo users with one nameLinearizable check (unique index or consensus)
Your own profile editsUser thinks the save failedRead-your-writes
Comments and repliesReplies before their parent look brokenCausal, or sort on the client
Like counts, view counts, feedsA number slightly off for a few secondsEventual, highly available
Why a multi-region "always consistent and fast" database can't exist

A linearizable write must be acknowledged by a majority of replicas. With replicas in Virginia, Oregon and Ireland, any majority includes at least two regions, so every write pays at least one cross-region round trip (roughly 60–150 ms). Spanner reduces read cost with tightly synchronised clocks (TrueTime) so stale or bounded-staleness reads can be served locally at a safe timestamp; a strong read may still need to check with the leader that the replica is caught up, and writes pay the round trip plus a short TrueTime commit wait. This is the "EC" half of PACELC: physics, not engineering, sets the floor.

When not to reach for CAP

  • One database server: no replication, no partition between copies. Talk about ACID and isolation instead.
  • Async read replicas behind one primary: the precise words are replication lag and read-your-writes, not CAP. See replication.
  • As a label for a whole product. Say what each operation needs and what happens during a partition.

In the interview

Your turn: a global ticketing system

A concert ticketing site runs in three regions. During a sale, users must never be sold the same seat twice. They also browse the seat map, which shows which seats are taken. The link to one region fails. What does each region do, and which consistency level does each operation need?

Compare with our answer
  • Booking a seat must be linearizable: use a consensus-backed store or a single primary for the event's inventory (or shard by event, each shard with one leader). A region cut off from the majority (or from the event's primary) refuses bookings and tells users to retry; it must not guess.
  • Seat map can be eventual: serve it from local replicas or a cache, accept that a seat shown as free may already be held, and let the booking step be the source of truth (the "seat just taken" message).
  • Holds (a seat reserved for 10 minutes during checkout) are writes and need the same strong path, with an expiry.
  • Mention the PACELC cost: booking writes pay a cross-region round trip if the majority spans regions; keeping each event's leader in the region nearest its buyers reduces it.

A strong answer mentions: linearizable booking via consensus or a single primary · minority side refuses bookings during the partition · eventual consistency for the seat map · the booking step as the source of truth · latency cost of strong writes across regions.

Your turn: the requirement changes

Your Cassandra cluster uses N = 3, W = 1, R = 1 for user profiles. Product now complains that users sometimes save a new bio, refresh, and see the old one. What is happening, and what are two different fixes with their costs?

Compare with our answer

With W = 1 and R = 1, the write may land on replica A while the refresh reads replica B, which hasn't received it yet. W + R = 2 is not greater than 3, so reads and writes need not overlap. Fixes:

  • QUORUM for both (W = 2, R = 2): overlap guaranteed; each request waits for two replicas, so latency rises a little and requests fail if two of three replicas are down.
  • Read-your-writes only for the author: after a user edits, make the author's write QUORUM and read their own profile at QUORUM (or write at ALL and read at ONE), while other users keep reading at ONE. A QUORUM read after a ONE write is not enough: 1 + 2 = 3 is not greater than 3. Cheaper, since most reads stay fast.
  • Also note last-write-wins and clock skew if the user edits twice quickly from two devices.

A strong answer mentions: why W + R ≤ N allows stale reads · QUORUM reads and writes and their latency/availability cost · read-your-writes as a narrower fix · that W + R > N still isn't full linearizability.

Consistency and CAP on one page
  • Partition = nodes can't talk to each other but keep running. During one, a node must refuse (CP) or risk stale answers (AP).
  • CAP's C = linearizability; A = every non-failed node answers. "CA" isn't an option on a network.
  • PACELC: else (no partition), choose latency or consistency. Cross-region strong writes cost 100+ ms.
  • Ladder: linearizable > causal > read-your-writes / monotonic reads > eventual.
  • Quorum: N replicas, W write acks, R read replies; W + R > N → overlap. N = 3, W = R = 2 survives one node.
  • Quorums ≠ linearizable: last-write-wins with clock skew, partial writes, sloppy quorums. Read repair and anti-entropy fix divergence.
  • True linearizability: consensus (Raft/Paxos): etcd, ZooKeeper, Spanner, or a single primary.
  • Decide per operation: balances and seats strong; profiles read-your-writes; likes and feeds eventual.
  • Serializable (transactions, some order) ≠ linearizable (one object, real time); both = strict serializability. Snapshot isolation allows write skew: fix with SERIALIZABLE plus retries, SELECT ... FOR UPDATE, or a materialised conflict row.
Interactive labPractise it: the quorum labOpens in the ByteAtlas lab. Your progress is saved in this browser.
Check what stuck

1. A bank replicates balances across two datacenters. The link between them fails, but both sides still receive customer requests. What does choosing consistency mean here?

2. An engineer says, "Our database is CA: consistent and available, so we don't worry about partitions." What is the best reply?

3. A Cassandra table uses N = 3. Which setting guarantees a read overlaps the latest successful write and still serves reads and writes with one replica down?

4. Users of a social app sometimes post a comment, refresh, and don't see it, because reads go to async replicas. Which guarantee are they missing, and what is a cheap fix?

5. A team uses QUORUM reads and writes with last-write-wins. Two clients update the same key within a millisecond from servers with skewed clocks. What can happen?

6. A company wants a database spread across three continents where every write is linearizable. What does PACELC predict?

7. Which pairing of operation and consistency level is the best fit?

8. On Postgres REPEATABLE READ, two transactions each check that two doctors are on call, then each takes a different doctor off call. Both commit. Why?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.