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.
On this page
- The problem: two copies, and the cable between them breaks
- The idea: during a partition, choose correct or answering
- CAP, stated precisely
- PACELC: the trade-off you pay every day
- Consistency models: a ladder
- Quorums: tuning with N, W and R
- Choosing per operation, not per system
- When not to reach for CAP
- In the interview
- 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
- 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.
- 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
- Option one: refuse to answer until the network heals. Every answer it does give is correct, which is consistency. But some requests fail.
- 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:
- 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.
- 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
- The CAP theorem says: during a partition you must pick one, consistency or availability. When the network is healthy, you can have both.
- 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 partition | Normally | Notes |
|---|---|---|---|
| Cassandra, DynamoDB (default reads) | Available | Low latency | Tunable per request: stronger settings shift towards C |
| Google Spanner, CockroachDB | Consistent | Consistent (pays latency) | Majority agreement on every write |
| etcd, ZooKeeper | Consistent | Consistent | Small coordination data: locks, leaders, config |
| PostgreSQL with async replicas | Primary stays consistent; replicas serve stale reads | Low latency | Replica lag is usually milliseconds, can be seconds |
Consistency models: a ladder
"Consistent" has many levels. From strongest to weakest:
| Model | Guarantee | Example of what it rules out |
|---|---|---|
| Linearizable (strong) | Behaves like a single copy: once a write completes, every later read sees it | Reading $100 after the $80 withdrawal was confirmed |
| Causal | If one event could have caused another, everyone sees them in that order | Seeing a reply before the comment it answers |
| Read-your-writes | A user always sees their own updates | Changing your profile photo, refreshing, and seeing the old one |
| Monotonic reads | Once you've seen a value, you never see an older one | A like count that goes 10 → 12 → 10 as you refresh |
| Eventual | If writes stop, all replicas converge eventually | Nothing 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.
| Step | Alice's transaction | Bob's transaction |
|---|---|---|
| 1 | Counts doctors on call: 2 | Counts doctors on call: 2 |
| 2 | "2 ≥ 2, I can leave": sets her row on_call = false | Same reasoning: sets his row on_call = false |
| 3 | Commits | Commits (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:
- 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.
- 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. - 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
- 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
| W | R | W + R > N? | Survives one node down? | Character |
|---|---|---|---|---|
| 1 | 1 | No | Yes, reads and writes | Fastest; reads can be stale |
| 2 | 2 | Yes | Yes, reads and writes | The usual "QUORUM" setting |
| 3 | 1 | Yes | Reads yes, writes no | Fast reads, fragile writes |
| 1 | 3 | Yes | Writes yes, reads no | Fast 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
- 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:
| Operation | What breaks if stale | Choice |
|---|---|---|
| Debit an account, book the last seat | Money lost, double booking | Linearizable: single primary or consensus; refuse during partitions |
| Unique username at sign-up | Two users with one name | Linearizable check (unique index or consensus) |
| Your own profile edits | User thinks the save failed | Read-your-writes |
| Comments and replies | Replies before their parent look broken | Causal, or sort on the client |
| Like counts, view counts, feeds | A number slightly off for a few seconds | Eventual, 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
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 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.
- 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.
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?
Consistency during a partition means refusing what you can't answer correctly. Accepting on both sides and reconciling later is the available choice, and can overdraw the account.
2. An engineer says, "Our database is CA: consistent and available, so we don't worry about partitions." What is the best reply?
Partitions aren't optional for a distributed system. CAP only describes the choice made during one: refuse some requests or risk stale answers.
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?
W + R must exceed N for overlap. W = 3 overlaps but blocks writes when any replica is down; W = 1, R = 2 sums to 3, which isn't enough.
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?
The user can't see their own write: a read-your-writes violation. Routing only recent writers to the primary fixes it without loading the primary with everyone's reads.
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?
Last-write-wins trusts timestamps. With clock skew, the real second write may carry an earlier timestamp and be silently discarded. Quorums don't fix concurrent writes.
6. A company wants a database spread across three continents where every write is linearizable. What does PACELC predict?
The "else" half of PACELC: with no partition, strong consistency still costs latency, because a majority of replicas spans regions.
7. Which pairing of operation and consistency level is the best fit?
Booking must never double-sell, so it needs a strong path. Likes and seat maps tolerate staleness; a username check served eventually could let two users take the same name.
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?
This is write skew. Each snapshot showed two doctors on call and the writes touched different rows, so snapshot isolation saw no conflict. SERIALIZABLE, FOR UPDATE on the rows read, or a materialised conflict row prevents it.
Score 60% or more and the lesson is marked complete.