CSE Roadmap

Core tier · about 3 hours · 6 parts

Part 4 of 6 · 3 min read

The cost when nothing is broken: PACELC

Even on a good day, stronger consistency means slower operations.

Think of a team that must get a "yes" from every office before closing a deal. Even when the phone lines are fine, the deal waits for the slowest office. Asking fewer offices is quicker, but then some offices lag.

The DDIA book makes the point that dropping linearizability is mostly about speed, not fault tolerance. Its example: RAM on a modern multi-core processor is not linearizable. Each core has its own cache and store buffer, and changes reach main memory later. A thread on one core may read an old value after another core wrote a new one, unless a memory fence is used. This has nothing to do with network faults, since one computer assumes reliable internal communication. The reason is performance. Many distributed databases skip linearizability for the same reason: it is slow, all the time, not only during a fault.

The book cites a proof (Attiya and Welch): to get linearizability, the response time of reads and writes must be at least proportional to the uncertainty of network delays. In a network with highly variable delays, linearizable operations are inevitably slow. There is no cheaper way.

The UDS book names this in the theorem PACELC: if there is a Partition (P), choose between Availability (A) and Consistency (C); Else (E), when the system runs normally, choose between Latency (L) and Consistency (C).

PACELC

PACELC extends CAP: during a partition, choose availability or consistency; otherwise, choose latency or consistency.

Example: a store replicated across continents can wait for far replicas to confirm each write (consistent, slow) or confirm after the nearest replica (fast, replicas lag).

A worked example for the "else" part. A write is copied to replicas in the same city (2 ms away), another country (40 ms away) and another continent (150 ms away). Round trips: 4 ms, 80 ms, 300 ms (made up to show the idea).

Strategy Time before the write is confirmed Reader at far replica sees the new value
Wait for all replicas About 300 ms Always, once confirmed
Wait for a majority (2 of 3) About 80 ms Maybe not at once
Wait for the nearest only About 4 ms Stale for a while

Each step to the right gives speed and takes consistency. Nothing is broken, yet the choice remains.

Practical use. The UDS book notes that some off-the-shelf data stores offer settings for this trade-off, so you can pick better performance or stronger guarantees. It names Azure's Cosmos DB and Cassandra as examples. Know the trade-off before choosing a setting.

Question Answer
Choice when the network splits Consistency or availability
Choice when the network is fine Consistency or latency
Who pays for strong consistency Users, as slower or refused requests

Interview angle

Answer in your head first, then open it.

State the CAP theorem.

When a partition occurs, choose consistency or availability. Add that partitions are not optional.

CP or AP for this feature?

Answer per feature: payments and seat counts lean CP, feeds and counters lean AP.

Is CAP the whole story?

No. Mention latency (PACELC) and that consistency has levels (module 6).

Why do some databases skip linearizability even without partitions?

It is slow: response time grows with network delay uncertainty.

Does w + r > n mean you are CP?

Not necessarily (module 6).

Check yourself:

  • What does the E in PACELC stand for, and what is the choice there?
  • Why is multi-core RAM a useful example for the cost of linearizability?