Module 7: Reliability and the Consistency Tradeoff

4. The CAP theorem, explained (without the myth)

Next →

Description

By the end of this lesson you will understand the CAP theorem in its correct form, and you will be able to dismantle the myth that accompanies it in almost every interview: the famous "pick 2 of 3". You will learn what the three letters really mean —C for consistency (which is linearizability, not the C of ACID), A for availability (that every request to a live node receives a response) and P for partition tolerance (that the system keeps operating even if the network loses messages between nodes)—, and why grouping them as "three knobs of which you turn one off" is wrong. The real statement is simpler and more useful: you do not choose P (network partitions happen whether you like it or not), so the real decision is what you do during a partition —keep responding with possibly stale data (AP) or refuse to respond so as not to lie (CP)—; and when there is no partition, you have C and A at the same time. You will see why Enlace, facing a partition, must choose AP: a slightly stale redirect is acceptable, but refusing to redirect is a bad experience.

This matters because CAP is at once the most cited and the worst understood concept in distributed systems, and repeating the myth gives you away as someone who memorized a phrase without understanding it. The "pick 2 of 3" version makes you believe you can build a "CA" system —consistent and available, sacrificing partition tolerance—, which is nonsense: you cannot "choose not to have partitions", partitions are a fact of the network, not a design option. Understanding CAP well gives you three things: the ability to make a real design decision (when the network partitions, does my system prefer to respond or to be exact?), immunity to the myth in an interview, and the conceptual basis for PACELC (lesson 5), which corrects the other great limitation of CAP —that it only talks about the rare case of the partition and is silent about the common case—.

Connection to the module: this lesson opens the consistency block and picks up the seed lesson 3 planted. There you saw that failover has an irreducible trap: the system cannot distinguish a dead node from a node isolated by the network. That isolation is the network partition, the P of CAP, and it is the scenario that forces the whole decision of this block. Lesson 4 formalizes the choice made under partition (C or A); lesson 5 completes it with what is chosen outside the partition (latency or consistency, via PACELC); and lesson 6 brings both down to the concrete case, choosing eventual consistency for Enlace and measuring it. The border: here we explain the conceptual tradeoff; how the guarantees of strong consistency are implemented (consensus, quorum) is the resilience guide and the distributed systems one; we choose, we do not implement.

The two branches that lose their phone line

Think of it this way. A store has two branches, North and South, that sell the same inventory and coordinate by phone: every time one sells the last unit of a product, it calls the other to say "there are none left, do not sell it". While the phone works, the two branches are perfectly coordinated (consistent) and both serve customers (available). All good: you have both things.

One day the phone line between the two branches goes down. Watch out: the two stores stay open, with lights and employees —what was cut is the communication between them—. That is a partition: the two parts of the system are alive but cannot talk to each other. And now, if a customer arrives at the North branch asking for the last unit of a product, North faces a decision it cannot dodge, because it cannot call South to confirm whether any is left:

  • Option CP (choose consistency): North says "I cannot confirm the inventory with the other branch, so I do not sell until the line comes back". It stays coherent —it never sells something South already sold— but it stops serving: it sacrifices availability so as not to risk an incoherence.
  • Option AP (choose availability): North says "I keep selling with the information I have, and when the line comes back we reconcile". It keeps serving everyone —but it runs the risk of selling a unit that South also sold—: it sacrifices consistency so as not to stop serving.

Notice three things about this story, because they are all of the CAP theorem. First: the dilemma only appears during the partition —while the phone worked, North had coordination and service—. Second: nobody chose for the line to go down; the partition was an imposed fact, not an option. Third: faced with that imposed fact, the store does choose —between continuing to serve (A) or continuing to be exact (C)—, but it cannot have both at the same time while the cut lasts. That is the correct form of CAP: when the network partitions, you choose between C and A; when it does not, you have both. There is no "pick 2 of 3"; there is a "when the inevitable happens, decide what you prefer".

What the three letters really mean

The myth feeds on vague definitions. Let us make them precise, because each letter means something stricter than the loose word suggests.

C — Consistency = linearizability. In CAP, "consistency" is not the C of ACID (which is "transactions respect the database invariants"). It is linearizability: the illusion that there is a single copy of the data and that every read sees the most recent write. If you write a value and, in the next instant, any node of the system, when asked for that datum, has to return the new value (never the old one), the system is linearizable. It is the strong consistency of lesson 6. When CAP says "C", it means this: as if there were only one copy, always up to date.

A — Availability = every request to a live node receives a response (not error, not timeout). In CAP, "availability" is stricter than the colloquial "uptime" of lessons 2 and 3. It means that every request that reaches a node that did not go down gets a useful response (not an "I am busy, retry later"). A node that, so as not to lie, responds "I do not know, I cannot serve you now" counts as unavailable in the CAP sense —even though the node is alive—. That is why the North branch that refuses to sell under the partition is "unavailable" in CAP: it is alive, but it does not serve.

P — Partition tolerance = the system keeps operating even if the network loses messages between nodes. A partition is when the network between two groups of nodes fails: messages are lost or delayed indefinitely, and the groups cannot communicate. "Partition tolerance" means that the system does not give up when that happens —it keeps working somehow—. And here is the key to the myth: P is not an optional feature, it is a fact of the world. In any system that runs on more than one machine connected by a network, partitions are going to happen —cables that get cut, switches that fail, latencies that spike—. You cannot "choose not to have partitions", just as the store cannot choose for its phone line to never fail. That is why every real distributed system has to be P; the only question is what it does when the partition arrives.

Why "pick 2 of 3" is a myth

Now you can see why the famous phrase is wrong. "Pick 2 of 3" treats C, A and P as three symmetric options of which you give one up. But P is not an option, it is a condition of the environment. A distributed system cannot give up "tolerating partitions" and keep "C and A" —the famous "CA" system— because that would mean "a system that only works if the network never fails", and the network always fails eventually. A "CA system" only exists if it runs on a single machine (no network between nodes, no possible partitions), and then CAP does not even apply.

The correct statement, then, is asymmetric:

  • You must always be P (partitions happen; your system has to survive them somehow).
  • The real choice is between C and A, and it only activates during a partition. Under partition: either you are CP (you sacrifice A: you refuse to respond so as not to give an incoherent datum) or you are AP (you sacrifice C: you respond with a possibly stale datum so as not to stop serving).
  • When there is NO partition, you have C and A at the same time. The tradeoff disappears while the network works. This is what the myth hides completely: it suggests that you give something up all the time, when in reality you only give it up during network cuts, which are rare.
                    is there a network partition now?
                              │
              ┌───────────────┴───────────────┐
             NO                               YES
              │                                │
   you have C and A at once         you must CHOOSE one:
   (no tradeoff)                     ┌──────────┴──────────┐
                                    CP                     AP
                              respond exact          respond available
                              or do not respond      even if stale data
                              (sacrifice A)           (sacrifice C)

That diagram is the entire CAP theorem, and the phrase "2 of 3" appears nowhere. The honest version you should be able to say in an interview is: "CAP says that, during a network partition, a distributed system must choose between consistency and availability; outside the partition it can have both. You do not choose P because partitions are inevitable; what you choose is how to behave when they happen: CP or AP."

Worked example: Enlace's choice under partition

Let us bring CAP down to the case. Enlace, already scaled, has its primary and its replicas, possibly in different datacenters (module 5). Imagine a partition: the network between the primary's datacenter and a replica's datacenter is cut for 5 seconds. The two remain alive, but they do not talk. Now a resolve arrives at the isolated replica —someone clicked on a short link—. The replica faces CAP's dilemma:

  • If Enlace were CP: the replica would reason "I cannot confirm with the primary that my copy is up to date, so, to avoid risking returning an old URL, I refuse to respond". The user who clicked sees an error or a wait. Enlace would be exact but useless during the partition.
  • If Enlace is AP: the replica reasons "I serve the URL I have, which is almost certainly correct, and if by chance the link was edited in the last seconds, the user sees a version from 5 seconds ago". The user is redirected, the partition goes unnoticed.

For Enlace, AP is the obvious and correct choice, and the reason is the nature of the data. A resolve returns which URL to redirect to; that datum is almost always immutable (a short link points to the same URL its whole life) and its staleness, when it occurs, is of seconds and of null consequence. Compare it with the cost of being CP: refusing to redirect a user who clicked —showing them an error— is a terrible experience to protect against a risk (a URL 5 seconds old) that almost never materializes and that almost never matters. Enlace prefers to always respond, even if very occasionally the datum is a bit stale. That is being AP, and it is what lesson 6 will formalize as eventual consistency.

Is there anything in Enlace that would want to be CP? Yes, one: the uniqueness of the short_code when creating it. If two shorten requests on opposite sides of a partition could generate the same short_code for different URLs, you would have a corrupt collision. But —and this is key— that is solved in the generation of the code (the id_generator of module 3, which hands out disjoint ranges so that two nodes never clash), not in the resolution. The read (resolve) is AP; the uniqueness guarantee of the write is designed separately so as not to depend on coordination under partition. Lesson 6 comes back to this nuance.

Common mistakes

Repeating "pick 2 of 3" (conceptual). What happens: someone says "it is a CA system" or "we sacrifice P". Why it happens: the phrase "pick two" is catchy and makes the three letters sound equal. How to spot it: if you believe there is a distributed "CA" system (one that gives up tolerating partitions), you did not understand CAP —a networked system cannot give up P, because partitions happen regardless—. How to fix it: remember that P is a condition of the environment, not an option; the choice is C-or-A and only under partition. "CA" only describes a single-machine system, where CAP does not apply.

Confusing the C of CAP with the C of ACID (of definition). What happens: someone says "my relational database is ACID, so consistent, so it is CP" mixing two different "consistencies". Why it happens: the same word means different things in the two contexts. How to spot it: if you use "consistency" without specifying which, you are probably mixing them. How to fix it: the C of CAP is linearizability (every read sees the last write, as if there were a single copy); the C of ACID is "transactions preserve the invariants". They are different axes; a system can be ACID and AP at the same time. When you talk about CAP, say "linearizable" or "strong consistency" so as not to confuse.

Believing that the tradeoff applies all the time (of scope). What happens: someone designs as if every read had to choose between exactness and availability always, and over-designs coordination for the common case. Why it happens: the myth suggests a permanent giving-up. How to spot it: if you are paying the cost of strong consistency (coordination, latency) even when the network is healthy, maybe you are doing it for a case —the partition— that is rare. How to fix it: understand that CAP only talks about the partition case; 99.99% of the time there is no partition and there is no C-vs-A tradeoff. What to do outside the partition is exactly what PACELC solves in lesson 5, and there the tradeoff is another (latency versus consistency).

Exercises

Exercise 1 — Translate the branch. Go back to the two-branch store without a phone. For each sentence, say which CAP letter it describes and why. (a) "While the line worked, both sold and were coordinated." (b) "The line went down; the two stores stay open but do not talk." (c) "North decides not to sell until the line comes back." (d) "South decides to keep selling and reconcile later."

See solution
  • (a) Describes having C and A at once, which is what happens without a partition. The line working = healthy network; without a partition, there is no tradeoff.
  • (b) It is a partition (P): nodes alive but incommunicado. Nobody chose it; it is an imposed fact that forces the decision.
  • (c) North chooses CP (consistency over availability): it refuses to serve so as not to risk an incoherence. It sacrifices A.
  • (d) South chooses AP (availability over consistency): it keeps serving with the risk of becoming uncoordinated. It sacrifices C.

Exercise 2 — Dismantle the myth. A colleague claims: "Enlace is a CA system: we designed it to be consistent and available, and we do not worry about partitions because our network is very good." Explain in two or three sentences why that claim is incorrect and how it should be rephrased.

See solution

The claim is incorrect because there is no distributed "CA" system: giving up partition tolerance (P) would be equivalent to assuming that the network will never fail, and in a system with nodes on several machines —like Enlace, with primary, replicas and possibly several datacenters— partitions are going to happen however good the network is (cables, switches, latency spikes). "Our network is very good" reduces the frequency of partitions, it does not eliminate them. The correct rephrasing: "Enlace is a P system (like every distributed system) and, faced with a partition, it chooses to be AP —it keeps resolving links even if the datum may be a few seconds stale, because refusing to redirect is worse than a slightly stale URL—; when there is no partition, which is almost always, Enlace is consistent and available at the same time."

Exercise 3 — CP or AP, with judgment. For each system, decide whether it should be CP or AP during a partition and justify with one sentence about the cost of getting it wrong in each direction. (a) Enlace's resolve (redirecting a short link). (b) The balance of a bank account when making a withdrawal at an ATM. (c) The "likes" counter of a post on a social network.

See solution
  • (a) Enlace's resolve: AP. Cost of being CP: refusing to redirect a user who clicked —error or wait—, terrible experience. Cost of being AP: returning a URL from a few seconds ago, almost always identical and harmless. AP clearly wins: the datum is benign and unavailability is expensive.
  • (b) Bank balance on a withdrawal: CP. Cost of being AP: allowing two simultaneous withdrawals at different ATMs that together exceed the balance (overdraft from lack of coordination) —real money lost—. Cost of being CP: the ATM says "service unavailable, try later" —annoying but safe—. CP wins: here incoherence costs money, so it is preferable not to operate rather than operate wrong.
  • (c) "Likes" counter: AP. Cost of being AP: the counter shows 1,024 on one node and 1,026 on another for a few seconds —nobody cares—. Cost of being CP: not being able to "like" during a partition —irritating and pointless for a trivial datum—. AP wins: it is the archetypal case of data tolerant to lag.

The rule that emerges: AP when the data tolerates being a bit behind (redirects, likes, feeds); CP when an incoherence costs a lot (money, inventory, uniqueness).

Summary and next step

In this lesson you dismantled the myth and kept the correct CAP. With the two branches that lose their phone you saw the theorem's three truths: the tradeoff only appears during a partition; the partition is not chosen (it is an imposed fact); and faced with it the system does choose, between continuing to serve (A) or continuing to be exact (C), unable to have both while it lasts. You made the three letters precise —C is linearizability (not ACID's), A is that every live node responds something useful, P is surviving the network losing messages— and you saw why "pick 2 of 3" is wrong: P is mandatory (partitions happen), so the real choice is CP versus AP, and only under partition; without a partition you have C and A. And you applied all of it to Enlace: its resolve must be AP —always respond, even if very occasionally the datum is a few seconds stale—, because refusing to redirect is worse than a slightly stale URL.

Before moving on you should be able to: state CAP in its correct form without saying "2 of 3"; define each letter precisely (C = linearizability); explain why there is no "CA" system; and classify systems as CP or AP according to the cost of getting it wrong in each direction.

What comes next is correcting the other great limitation of CAP. You will have noticed something uncomfortable: CAP only says what happens during a partition, which is the rare case. And 99.99% of the time, when the network is healthy? CAP is silent —it implies that there "you have C and A" and that is that—, but that hides a second tradeoff that does operate all the time. In lesson 5 you will see PACELC, Daniel Abadi's extension: if Partition, choose A or C; Else, choose Latency or Consistency. You will understand why strong consistency costs latency even without a partition, and why Enlace, which we already chose to be AP, is also EL (it prefers low latency to strong consistency when the network is healthy) —the PA/EL class, which is exactly the profile of a redirect at 4,000 reads per second—.

Resources

← Previous3. Failover basicsNext →5. PACELC: beyond CAP