Consistency, CAP and replication in system design
The CAP theorem says that when a network partition splits a replicated system, it must choose between consistency (every read sees the latest write) and availability (every working node still answers). It is not "pick two of three": partitions are not optional, and when there is no partition you can have both. The everyday trade-off, captured by PACELC, is between consistency and latency.
By Evin JohnPublished 8 min read
1. What consistency and CAP mean
As soon as data is copied to more than one machine, for durability, read capacity or lower latency, the copies can disagree. A consistency model is the contract a system offers about what a read can return given the writes that came before it. CAP is the best-known result about the limits of that contract: Eric Brewer stated it as a conjecture in 2000, and Seth Gilbert and Nancy Lynch proved a formal version in 2002.
2. Why interviewers ask about it
Every distributed design makes a consistency choice, whether or not the candidate notices. Interviewers ask to see whether you can name it, tie it to a product requirement and explain its cost. CAP is also a reliable filter: it is often recited loosely ("Cassandra is AP, so it is fast"), and a precise statement of what it does and does not say stands out quickly.
3. CAP, stated precisely, and PACELC
| Property | Precise meaning | Common misreading |
|---|---|---|
| Consistency (C) | Linearizability: every read returns the most recent completed write, as if there were a single copy of the data | ACID's "C" (keeping invariants), which is a different idea |
| Availability (A) | Every request received by a non-failing node eventually gets a non-error response (the definition sets no deadline, but the node may not wait forever) | "The system is usually up" or "high uptime" |
| Partition tolerance (P) | The system keeps operating even if the network drops or delays any number of messages between nodes | An optional feature you can decline |
The theorem: in a system whose network can partition, you cannot guarantee both linearizability and availability during a partition. A node cut off from the others must either refuse or delay requests it cannot coordinate (keeping C) or answer from local data that may be stale or conflicting (keeping A).
- "CA" is not a real option for a system that spans a network, because you cannot choose to have no partitions. A single-node database is "CA" only in the trivial sense that it is not distributed.
- The choice can differ per operation. A store can refuse writes on the minority side of a partition but still serve possibly stale reads there.
- CAP's availability is strict. Systems labeled "CP" are often highly available in practice: with consensus replication, the majority side of a partition keeps serving and only the minority side stops. Google describes Spanner as technically CP but, because partitions are rare on its network, effectively highly available.
PACELC (Daniel Abadi) completes the picture: if there is a Partition, choose Availability or Consistency; Else, choose Latency or Consistency. The second half matters more day to day. Keeping replicas in step means waiting for other machines, sometimes in other regions, on every write or read, and that waiting is latency you pay even when nothing is broken. Dynamo-style stores in their default settings are usually classed PA/EL; systems built on synchronous consensus replication, such as Spanner, are PC/EC.
4. Consistency models, strongest to weakest
| Model | Guarantee | Typical use | Cost |
|---|---|---|---|
| Linearizable | Operations appear to happen one at a time, in an order that matches real time. Once a write completes, every later read sees it or something newer. | Locks, leader election, uniqueness, balances | Coordination on every operation; unavailable on the minority side of a partition; cross-region latency |
| Sequential | All clients see the same single order, consistent with each client's own order, but not necessarily with real time | Rarely chosen explicitly; a useful reference point | Still needs a global order |
| Causal | If one operation could have influenced another (a reply after the post it answers), everyone sees them in that order. Unrelated writes may appear in different orders. | Comments, chat, collaborative tools | Tracking dependencies; can stay available during partitions |
| Read-your-writes | A client always sees its own earlier writes; other clients may not yet | Profile edits, a user's own posts | Route that client's reads to an up-to-date copy, or track its last write |
| Monotonic reads | A client never sees data go backwards in time | Any feed or list a user refreshes | Pin a client to one replica, or track versions |
| Eventual | If writes stop, all replicas converge. No promise about what a read returns meanwhile | Like counts, view counts, timelines, DNS | Cheapest and most available; the application must tolerate stale reads and resolve conflicts |
Keep two terms apart. Serializability is about transactions: concurrent transactions behave as if they ran one after another. Linearizability is about single operations and real-time order. A database can offer one without the other; strict serializability is both.
5. Replication and quorums
| Style | How writes flow | Consistency | Failure behavior | Examples |
|---|---|---|---|---|
| Leader-follower | One leader accepts writes and streams them to followers, synchronously or asynchronously | Reads from the leader can be up to date; follower reads lag | Failover; with asynchronous replication, acknowledged writes not yet copied can be lost | PostgreSQL and MySQL replication, MongoDB replica sets; Raft and Paxos groups |
| Multi-leader | Several leaders (often one per region) accept writes and replicate to each other asynchronously | Concurrent writes to the same data conflict | Each region keeps accepting writes during a partition | Active-active multi-region setups, offline-capable apps |
| Leaderless | The client or a coordinator sends each write to several replicas and waits for some of them | Tunable with quorum sizes | No failover step; stale replicas are repaired on read or in the background | Dynamo-style stores such as Cassandra, Riak, ScyllaDB |
Conflicts from multi-leader and leaderless writes need a rule. Last write wins (by timestamp) is simple but silently drops one of the writes and depends on clocks. CRDTs, data types designed so concurrent updates always merge, keep both. Application-level merging asks the user or the code to decide.
- Client
- Write v2
- Later: read
- Coordinator
- Send write to A, B, C; ack after 2
- Ask 2 replicas; return the newest; repair the stale one
- Replicas (N = 3)
- A: v2
- B: v2
- C: v1 (lagging)
R + W > N => every read set overlaps every successful write set in at least one replica
N=3, W=2, R=2 4 > 3 overlap; reads and writes survive 1 replica down
N=3, W=3, R=1 4 > 3 fast reads; any replica down blocks writes
N=3, W=1, R=1 2 < 3 no overlap; fastest, eventually consistent
N=5, W=3, R=3 6 > 5 overlap; reads and writes survive 2 replicas down
Consensus (Raft, Paxos): 2f + 1 nodes tolerate f failures (3 tolerate 1, 5 tolerate 2)Overlap makes a stale read unlikely, not impossible. Concurrent writes resolved by timestamp, sloppy quorums that accept writes on stand-in nodes during failures, and a failed write that still reached one replica can all produce results that are not linearizable. When an operation truly needs linearizability, such as claiming a unique name, use a consensus-backed store or a conditional write the database guarantees.
6. Choosing per operation
Most products need strong consistency for a few operations and can relax it for the rest. The skill is finding those few. Ask of each operation: what is the harm if two users see different values for a few seconds, and what is the harm if the operation is refused during a failure?
- Harm from divergence is money, safety or a broken invariant (double spending, two owners of one username, two workers running a job meant to run once): choose linearizable operations and accept refusals during partitions.
- Harm is a brief oddity (a like count off by a few, a post appearing a second late): choose eventual consistency, plus read-your-writes so users see their own actions.
- Order matters but global agreement does not (messages in a conversation, replies under a comment): causal ordering, often within one partition key, is enough.
7. How it shows up in common prompts
| Prompt and operation | What it needs | Why |
|---|---|---|
| Payment system: debit an account | Serializable transactions on a linearizable store | A stale balance allows double spending |
| URL shortener: claim a custom alias | Linearizable conditional write on that key | Two users must not both own one alias; redirects themselves can read replicas |
| Job scheduler: claim a job | A lease from a linearizable store, with fencing tokens | A paused worker must not keep running a job someone else took |
| Uber: assign a driver | One winner per driver (conditional write); locations can be seconds stale | A driver cannot take two trips |
| WhatsApp: send a message | Order within a conversation; sender sees own message | Global order across conversations is unnecessary |
| Twitter: timelines and counts | Eventual, with read-your-writes for your own posts | A post arriving a second late harms nobody |
| Collaborative editor: concurrent edits | Convergence via CRDTs or operational transformation | Everyone must end with the same document without locking |
8. Mistakes to avoid
- "Pick two of three." Partitions happen whether you pick them or not. The choice is what to do while one lasts.
- Calling a distributed design "CA".
- Mixing up the C's. CAP's consistency is linearizability; ACID's consistency is about invariants.
- "It's eventually consistent" with nothing after it. Say how stale reads can be, how conflicts resolve and what users see.
- Assuming quorums are linearizable. R + W > N narrows the window for stale reads; it does not remove every anomaly.
- Forgetting replica lag. Reading from an asynchronous replica right after a write shows the user old data unless you route or track that read.
- Labeling a whole product CP or AP. Real systems choose per operation, and many stores let you choose per request.
9. How to talk about it in the interview
- Pick out the one or two operations that need strong consistency and say why, in product terms.
- For everything else, name the weaker model and what users might notice.
- Say what happens during a partition for the strong operations: refuse, queue, or degrade.
- If you use quorums, give N, W and R and the failures they tolerate.
Fictional example
- Interviewer
- What consistency do you need here?
- Candidate
- It depends on the operation. Reserving a seat must be linearizable: two people must never hold the same seat, so the reservation is a conditional write in a consensus-replicated store. If a region is cut off from the majority, it stops taking reservations rather than risk a double booking.
- Candidate
- The seat map that people browse can be eventually consistent, a few seconds stale, served from replicas and a cache. The worst case is that someone picks a seat that was just taken and gets a clear error at checkout.
- Interviewer
- Why not make the seat map consistent too?
- Candidate
- It is read far more often than seats are booked. Making every view coordinate would add latency to every page load to prevent an error that the checkout already catches.
Practicing with Natively
Consistency is easy to hand-wave and hard to state precisely under pressure, so practice saying it. In a mock interview, Natively transcribes the conversation live and can suggest talking points for each question as it comes in; comparing them with what you said is a quick way to spot gaps such as partition behavior or replica lag. It can explain a screenshot you capture of a replication diagram or a problem statement. The transcript and notes are kept for review afterwards, so you can check whether you named a model for each operation or just said "eventually consistent".
Questions people ask
What does the CAP theorem actually say?
When a network partition separates the nodes of a replicated system, the system cannot guarantee both linearizable consistency and availability, so it must refuse some requests or answer with possibly stale data. It is not a choice of any two of three properties, because partitions cannot be ruled out. When there is no partition, a system can be both consistent and available.
What does R + W > N mean in quorum replication?
N is the number of replicas of each item, W the number that must acknowledge a write and R the number consulted on a read. When R + W is greater than N, every read overlaps every successful write in at least one replica, so the latest value is normally seen. It makes stale reads unlikely but does not on its own guarantee linearizability.
What is the difference between CAP consistency and ACID consistency?
CAP's consistency means linearizability: every read reflects the most recent completed write, as if there were one copy of the data. ACID's consistency means a transaction moves the database from one valid state to another, keeping invariants such as constraints. They are separate ideas that happen to share a word.
Where to go next
Practice with the same assistant you would use on a call: it listens, transcribes and suggests answers from your own resume and the job description.
Facts on this page were last checked on . Product details come from the Natively app itself; if something here is out of date, tell us at hello@heynatively.com.
