CAP Theorem and PACELC

easy

Scale: Consistency dictates per-op latency Storage: Replication factor × dataset Google, Meta, Amazon

FundamentalsDistributed SystemsConsistency

Imagine your data is stored on two servers, one in Mumbai and one in Singapore, and the network link between them breaks. A user writes to Mumbai. Another user reads from Singapore. Singapore has not heard about the write.

ScaleConsistency dictates per-op latency

StorageReplication factor × dataset

Key Concepts

You have two choices, and only two. Singapore can return the old value, which is wrong but fast. Or it can refuse to answer until the link is back, which is correct but looks like downtime.

That is the CAP theorem. When the network splits, you choose consistency (refuse to answer) or availability (answer with possibly stale data).

consistencyavailability

"Pick two of three" is wrong. People say you choose two of consistency, availability and partition tolerance. You do not. Networks break whether you like it or not, so partition tolerance is not optional. The real choice only appears during a break, and it is between the other two.

"Pick two of three" is wrong.

PACELC covers the rest of the time. Partitions are rare. The everyday trade-off is different: if Partitioned, choose A or C; Else, choose Latency or Consistency.

PACELC covers the rest of the time.if Partitioned, choose A or C; Else, choose Latency or Consistency.

Even with a healthy network, keeping servers in step costs time. If a write must reach Singapore before you confirm it, every write waits for that trip.

And the trip has a floor you cannot engineer away. Light through fibre covers roughly 200 km per millisecond, and cables do not run straight:

And the trip has a floor you cannot engineer away.

Mumbai to Mumbai (same building) under 1 ms Mumbai to Singapore about 60 ms Mumbai to Virginia about 200 ms

So a write confirmed by a server in Virginia takes at least 200 ms. No amount of clever code changes that. Quote these numbers and a vague argument becomes a budget.

You can tune it per request, with quorums. Keep N copies. Require W of them to confirm a write and R to answer a read. If R + W > N, a read always overlaps the newest write, so it cannot miss it.

You can tune it per request, with quorums.NWRR + W > N

With 3 copies, W=2 and R=2 survives one server being down and still reads correctly. W=1, R=1 is faster and may hand back stale data. The setting is per operation: a payment uses the strict one, a profile picture does not.

W=2R=2W=1, R=1

Real systems and what they chose. Spanner picks consistency and pays in write latency. DynamoDB and Cassandra default to availability with tunable quorums. etcd and ZooKeeper pick consistency, because a configuration store handing out stale data during a split causes worse problems than pausing.

Real systems and what they chose.

What the interviewer is probing.

What the interviewer is probing.

1. "What does CAP say?" Probing: whether you learned the slogan or the idea. Stalls: "You can only have two of the three." Moves up: partitions are not a choice, so the theorem is about what you do during one.

1. "What does CAP say?"

2. "Your system chooses consistency. A partition happens. What does the user see?" Probing: the consequence in plain terms. Stalls: "It stays consistent." Moves up: the smaller side returns errors or hangs — the user experiences downtime, and you must decide which side that is.

2. "Your system chooses consistency. A partition happens. What does the user see?"

3. "Why is a cross-region write slow even when nothing is broken?" Probing: the everyday half. Stalls: "The network is slow." Moves up: waiting for a distant confirmation costs one round trip, and Mumbai to Virginia is about 200 ms of physics.

3. "Why is a cross-region write slow even when nothing is broken?"

4. "How do you make it adjustable?" Probing: quorums. Stalls: "Use eventual consistency." *Moves up:* R + W > N, chosen per operation, with an example.

4. "How do you make it adjustable?"R + W > N

5. "Which would you pick for a shopping cart?" Probing: whether you can defend a choice. Stalls: "Consistency, obviously." Moves up: availability — a cart that refuses to accept items loses sales, and merging two versions of a cart is a solvable business rule.

5. "Which would you pick for a shopping cart?"

Components

Replication protocol — sync, semi-sync, async, quorum-based.
Replica placement — same AZ, cross-AZ, cross-region, with proximity rules.
Conflict resolution — Last-Write-Wins timestamps, vector clocks, CRDTs (G-counters, OR-sets), domain merge functions.
Failure detection — heartbeats, gossip (SWIM), phi-accrual.
Leader election or coordinator — Raft, Paxos, single-master with promotion.
Client-side routing knowledge — which replica owns this key, which is leader, fall-back order.
Anti-entropy — Merkle tree compare, read repair, periodic full sync.

Latency floor by distance

  Light in fibre ~200 km per millisecond, and real paths are not
  straight lines. Typical round trips:

  Mumbai      -> Mumbai (same AZ)                 <1 ms
  Mumbai      -> Mumbai (cross-AZ)                 1-2 ms
  Mumbai      -> Singapore                        ~60 ms
  Mumbai      -> Frankfurt                       ~110 ms
  Mumbai      -> Virginia                        ~200 ms
  Sydney      -> London                          ~250 ms

  What that means for a quorum write (N=3):
    All replicas in one region                    ~2-5 ms
    Two regions (Mumbai + Singapore)               ~60 ms
    Three continents                              ~200 ms+

  Consequences to state out loud:
    - A synchronous cross-continent quorum caps you at ~5 writes/second
      per sequential client. Batching and concurrency hide it; a single
      user's serial workflow cannot.
    - This is why "global strong consistency" products either restrict
      write regions or accept the latency openly.

Quorum arithmetic

  N replicas, W write acks, R read responses.
  R + W > N  =>  every read overlaps the latest write.

  N=3  W=3  R=1   reads fast, writes fragile (any replica down = no writes)
  N=3  W=2  R=2   the common default: tolerates 1 failure, consistent
  N=3  W=1  R=1   fastest, stale reads possible (R+W = 2, not > 3)
  N=5  W=3  R=3   tolerates 2 failures, consistent, more latency
  N=5  W=1  R=5   fast writes, expensive reads -- rare but valid

  Failure tolerance for strong consistency = N - W  (writes)
                                           = N - R  (reads)

  Per-operation, not per-system:
    payment write            N=3 W=2 R=2    correctness first
    profile photo read       N=3 W=2 R=1    latency first
    analytics event          N=3 W=1 R=1    loss is acceptable

  The mistake to avoid: choosing one setting for the whole database and
  then arguing about it. The knob exists per call.

What real systems chose

  Spanner            CP. Synchronised clocks (TrueTime) plus commit-wait
                     give externally consistent global transactions.
                     Cost: write latency bounded by clock uncertainty.

  DynamoDB           AP by default, CP available. Eventually consistent
                     reads are cheaper; strongly consistent reads cost
                     double and cannot cross regions.

  Cassandra          AP with per-query tuning (ONE / QUORUM / ALL).
                     LOCAL_QUORUM is the common production setting:
                     consistent within a region, async across regions.

  etcd / ZooKeeper   CP. A minority partition stops serving writes and
                     can be configured to stop serving reads. Correct for
                     configuration and leader election, where a stale
                     answer causes split brain.

  PostgreSQL + sync  CP within the replica set. synchronous_commit=on
  replication        means the primary waits for the standby; RPO is zero
                     and every commit pays the round trip.

  Kafka              Tunable via acks and min.insync.replicas.
                     acks=all with ISR >= 2 is the durable setting.