CAP and consistency levels: what you give up when the network breaks

Once data has copies, a question follows: "When a user reads, is the data the newest?" Interviewers also ask: "What does your system do when part of the network breaks?" Many candidates answer with the CAP theorem. Most use it badly.

A weak answer says "pick two of three, so I choose CP" and gives no reason. A strong answer goes through the operations one by one. It says which reads must show the newest data and which can show old data. It says what the user sees when the network breaks, and what the strong choice costs in milliseconds.

At SDE-1 level you should name the levels and explain why followers lag (lesson 40). At SDE-2 level you should choose a level for each operation. At SDE-3 level you should explain what CAP does not say, and the cost in normal times.

Go back to the school in lesson 39: one master register and copies in the classrooms. A consistency level is a promise about what a read may show when there are many copies of the data. A stronger promise means more waiting. We go from the strongest promise to the weakest.

The levels

1. Strong consistency. The system acts as if there is only one copy. When a write has finished, every read after that, by anyone, shows that write or a newer one. Its formal name is linearizability. You can build it by sending all reads and writes to the leader. You can also make each write wait until every follower that answers reads has applied it (lesson 40). The cost is time: a write waits for the far copy.

2. Causal consistency. One write causes another when the writer had seen the first one before making the second. A reply is caused by the question it answers. Causal consistency promises that everyone sees a cause before its effect. It does not order writes that are not related. Two people may see two unrelated posts in different orders.

Here is a case where it breaks. Questions are saved in one database and replies in another. Each has its own leader and followers. Asha saves a question. Ravi reads it and saves a reply. Assumption: a follower of the replies database is 0.4 seconds behind, and a follower of the questions database is 2 seconds behind. Meena reads from both. The reply is visible at 0.4 seconds. The question is visible only at 2 seconds. For 2 - 0.4 = 1.6 seconds, Meena sees a reply to a question that is not there. The fix is to save with the reply the log position of the question that Ravi saw. The app shows the reply only after a follower of the questions database has applied the log up to that position. This is the log position idea from lesson 40.

3. Promises for one user. Lesson 40 gave two of these. Read-your-writes means my own reads show my own changes. The other one is "do not go back in time". Its formal name is monotonic reads. After I see a new value, I never see an older one. They are cheap, and they say nothing about other users.

4. Eventual consistency. From lesson 40: if writes stop, all copies become the same after some time. It gives no promise about what a read shows before that, and no time limit. It is the weakest level, and the cheapest.

When the network breaks

A network partition is a break in the network that splits the servers into two groups. Both groups still run and can talk to users. They cannot talk to each other. A cut cable, a faulty switch (a box that joins cables) or an overloaded link between two cities can cause it.

During a partition, a request arrives at a server that cannot reach the leader, or the other copies. The server has two choices:

• Refuse or wait. It returns an error. No user sees wrong data, but some users get no service.
• Answer from what it has. Every working server answers. But an answer can be old, and a write can be accepted that the other group does not know about.

The CAP theorem says that during a partition a system cannot give both of these:

• Consistency (C): strong consistency, as above.
• Availability (A): every request to a working server gets a real answer, not an error.

The P in CAP is partition tolerance. It means that the system keeps running when a partition happens. You do not choose P. Networks break whether you like it or not. So "pick two of three" is the wrong picture. The real choice is only this: when a partition happens, do you keep C or keep A? When the network is fine, you can have both. Gilbert and Lynch proved this in 2002 for an idea that Eric Brewer presented in 2000.

What CAP leaves out

Most of the time the network works, and you still pay for strong consistency. To show the newest data, a read or write must reach the leader or wait for a far copy. PACELC (Abadi says "pass-elk") adds the normal case. If there is a Partition, choose A or C. Else, in normal times, choose Latency or Consistency. Abadi described this in 2012. The second choice matters more, because it applies every second of every day.

A Tatkal booking system. Tatkal is the way Indian Railways sells last-minute train tickets. It opens at 10 am, and many people try to book few seats at once.

Assumptions (made up to teach with, not real traffic):

• 1,000 seats open at 10 am. 200,000 booking attempts arrive in the first minute, which is 200,000 / 60 = 3,333 per second.
• The leader is in Mumbai. A follower is in Chennai. Chennai users send 40% of the attempts and Mumbai users send 60%.
• A round trip between the cities takes 30 ms. A disk write takes 1 ms, and a local read of one seat takes 2 ms.
• The search page is opened 20,000 times per second and shows "seats left". One search view costs 4 ms of CPU. The leader has 8 cores, which is 8,000 ms per second.
• The partition starts at 10 am, when all 1,000 seats are still free.

Step 1: pick a level for each operation. Ask: what does a wrong answer cost?

• Booking a seat: a seat sold twice is a real loss. It needs strong consistency. One place, the leader, decides each seat (lesson 22).
• Seats left on the search page: a number that is some seconds old does no harm. Eventual is enough.
• My bookings page: the user just booked and must see it. Read-your-writes (lesson 40).

Step 2: the 20-second partition. Chennai cannot reach the leader.

• Chennai attempts = 3,333 x 40% = 1,333 per second. In 20 seconds: 1,333 x 20 = 26,660 attempts (rounded; 3,333 is itself rounded).
• If we keep consistency, Chennai refuses them all. 26,660 attempts get an error. Mumbai goes on. No seat is sold twice.
• If we keep availability, Chennai sells from its own copy, which shows 1,000 free seats. Mumbai sells its 1,000 seats in 1,000 / 2,000 = 0.5 seconds. Chennai sells its 1,000 in 1,000 / 1,333 = 0.75 seconds. That is 2,000 tickets for 1,000 seats. 1,000 tickets are wrong, which is half of all sales. Each one needs a cancel and a refund.

So the answer to the predict box for the booking is: refuse on the side that cannot reach the leader. For the search number, the answer is the opposite. Chennai keeps showing its last number, which may be 20 seconds old. Nobody is hurt, and the page stays up.

Step 3: the normal time (the E in PACELC). No partition. What does strong consistency cost?

• A write that waits for the Chennai follower takes 1 + 30 + 1 = 32 ms. An asynchronous write takes 1 ms (lesson 39). That is 32 times slower.
• A strong read for a Chennai user goes to the leader: 2 + 30 = 32 ms. A local read from the Chennai follower takes 2 ms. That is 16 times slower.
• If all 20,000 search views per second were strong reads on the leader: 20,000 x 4 ms = 80,000 ms of CPU. The leader has 8,000 ms per second, so that is 80,000 / 8,000 = 10 times too much. The search page must be eventual. Eventual reads can go to many followers, so the leader keeps its CPU for bookings.

Step 4: the result. One system, two levels: strong for the seat, eventual for the count. This is not "a CP system" or "an AP system". The choice is made for each operation.

• Strong consistency solves double sales and wrong balances. It costs 32 ms instead of 1 ms for a write in the example, and refused requests during a partition (26,660 in 20 seconds). I would use it only for data where a wrong answer costs money or trust.
• Eventual consistency solves speed and service during a partition. It costs old reads, and extra work to hide them from the user who just wrote (lesson 40). I would use it for counts, feeds and search pages.
• Causal consistency solves a reply that appears before its question. It costs a position to carry and a short delay for the effect. I would use it for comments and chat.
• I would change the choice when the cost of a wrong answer changes, or when the cost of waiting changes. A seat count that people pay for is no longer a number that can be old.

"CAP says pick any two of three, so I chose CP." You cannot drop P, because networks break. CAP only says that during a partition you choose between C and A. In normal times you can have both, and the real cost is the delay in Step 3.

"Our database is CP" or "our database is AP." The label hides the settings and the operations. In the example, one system refuses seat bookings and also answers the seat count during the same partition. Say what each operation does.

"The C in CAP is the C in ACID." They are different. The C in ACID (lesson 21) means your own rules still hold after a transaction. The C in CAP means that every reader sees the newest write, as if there was one copy. Also, the A in CAP is not the "99.9% uptime" of lesson 4. It means that every working server gives a real answer.

1. In CAP, what do C and A mean? What must a system choose between during a partition? Name the four levels in this lesson.
2. A city sends 1,500 booking attempts per second. A partition cuts it from the leader for 30 seconds. (a) How many attempts get an error if the system keeps consistency? (b) A strong write waits for a follower, and the round trip to it takes 25 ms. Each disk write takes 1 ms. How long does the write take? (c) How many times slower is that than an asynchronous write of 1 ms?
3. A shop shows "only 3 left" on the product page and reduces the stock when someone pays. Which level do you choose for the number on the page, and which for the stock at payment? What does each do during a partition?