CAP, quorums and eventual consistency

Part of the free System Design course on LogicWiz, in the chapter: Consistency and coordination. The interactive whiteboard exercises and simulations run in the app.

Week 8: Two data centres that stopped talking

"Rohan topped up his SwiftKart wallet in Mumbai, then opened the app in Chennai and saw the old balance. He topped up again."

From a SwiftKart support ticket

A cut cable, and a choice you cannot avoid

SwiftKart keeps wallet balances in two data centres, Mumbai and Chennai, each holding a full copy. Normally every write in one is copied to the other in a few tens of milliseconds. Then a fibre cut separates them. Both are up and both can still reach their customers. But they cannot reach each other. That is a network partition.

A customer in Chennai tries to spend 300 rupees from a wallet showing 500. Meanwhile, in Mumbai, the same wallet is being spent for 400. Chennai has two options:

  • Refuse: "Wallet temporarily unavailable." Safe, because no copy diverges. But Chennai customers are stuck.
  • Serve anyway: allow the spend using the data it has. Everyone is served, but now the two copies disagree, and 700 may have been spent from 500.

There is no third option where both sides answer and both are certainly right, because neither side can learn what the other did. This is the CAP theorem in one scene.

CAP in plain words

When a partition happens, a system can keep only one of two promises:

  • Consistency: every read sees the latest successful write, as if there were one copy. This is not the "C" in ACID, the set of guarantees a database transaction gives. Here it means all copies agree from the user's point of view.
  • Availability: every request to a working node gets an answer.

A system that refuses to risk disagreement is CP: it may reject requests during a partition. One that keeps answering is AP: it may return stale data and reconcile later.

Many candidates learn CAP as "pick any two of Consistency, Availability, Partition tolerance." That reading is wrong. Partitions are not optional: cables get cut and machines pause, so you cannot pick "no partitions". The real choice is what to give up while a partition lasts. When everything is healthy, you keep availability, but consistency still costs you latency (next section).

PACELC: the cost when nothing is broken

CAP only talks about failures, but most of the time the network is fine. PACELC adds the everyday trade-off: if there is a Partition, choose Availability or Consistency; Else, choose Latency or Consistency.

Concretely: to guarantee that a Chennai read sees Mumbai's latest write, Mumbai must wait for Chennai to confirm before it replies. The round trip between those cities is roughly 30 milliseconds, depending on the path. Every write now pays 30 ms extra, even on a perfect day. Skip the wait and writes are fast, but a read in Chennai may be slightly behind. Consistency costs latency even without a failure.

Quorums: a vote that always overlaps

Many databases keep N copies (replicas) of each item. A quorum is the number of replicas that must answer. Writes go to W of them and wait for those to confirm. Reads ask R of them and take the newest version. The rule:

If R + W > N, every read set overlaps every write set in at least one replica.

This is the leaderless style of replication, where any replica can take a write, rather than the single-leader style of Week 5.

Take N = 3, with replicas A, B, C, and choose W = 2, R = 2 (since 2 + 2 = 4 > 3). A write of "balance = 200" is confirmed by A and B; C is slow and still says 500. A read asks, say, B and C. B returns version 2 (200), C returns version 1 (500). The reader picks the newest version, 200. Any two replicas you choose must include at least one of A or B. So the newest version is always among the replies. Real systems still need more than this rule:

  • Version numbers, so the reader can tell which copy is newest.
  • Read repair: when a read notices a stale copy, it writes the newer value back to it.
  • Care with two writes to the same item at the same moment.

R + W > N alone does not make the store behave exactly like one copy. Engineers call that stronger promise linearizability. Also, a write that failed partway can still leave mismatched copies behind.

The numbers show the trade-offs. W = 3, R = 1: reads are fast but a single dead replica blocks writes. W = 1, R = 1: very fast and available, but 1 + 1 is not greater than 3, so reads may be stale. With W = 2, R = 2 one replica can be down and both reads and writes still work.

Try the combinations below. Start at N = 3, W = 2, R = 2 and take one replica down, then a second. Then try W = 1, R = 1 and watch the overlap disappear. Last, try W = 3, R = 1 with a single replica down.

Eventual consistency and read-your-writes

Eventual consistency means: if no new writes arrive, all copies converge to the same value eventually, usually within milliseconds to seconds. It is not "inconsistent forever". For a like-count or a product description that is perfectly fine.

It does create the Rohan problem. He writes to one copy, then his next read lands on a lagging copy, and his own change seems missing. The fix is read-your-writes: a user always sees their own latest changes, even if others lag. Three simple ways to do it:

  • Route a user's reads to the primary for a few seconds after they write.
  • Send the version number of their last write with the next read. Accept only a replica that has that version or newer.
  • Pin the user to one region for a few seconds after they write.

💡 Tip: You rarely need strong consistency for the whole system. Often you need read-your-writes for one user and eventual for everyone else.

📌 Summary: During a partition, choose to refuse (consistent) or answer possibly stale (available). Consistency costs latency even when healthy. R + W > N makes reads overlap writes. Read-your-writes protects the writer.

What Meera learns next

Replicas need someone to decide the order of writes. Next: leaders, locks that can lie, and how a group of machines agrees on one answer.

Check your understanding

  1. A store keeps N = 3 copies of each wallet. Writes wait for W = 1 replica and reads ask R = 1. What do you get?
  2. N = 3, W = 2, R = 2. One replica crashes. What happens?
  3. In an interview a candidate says, "We will pick CA: consistency and availability." Why does the interviewer push back?
  4. Meera updates her delivery address. The checkout page, served by a lagging replica, still shows the old one. What is the targeted fix?