When many places accept writes: conflicts

Many products have users in two or more cities. The interviewer asks: "Can a user in Chennai save data in Chennai, or must the write travel to Mumbai? And what if two people change the same thing at the same moment?"

A weak answer says "use a database that handles conflicts" and stops. A strong answer says what a conflict is and how the system finds one. It picks a rule for each kind of data, and names the data that must never be written in two places.

At SDE-2 level you should know that two places can disagree. At SDE-3 level you should choose a rule for each kind of data and say what it loses.

Think of a tea chain with two shops, in Mumbai and in Chennai. Each manager may change the price on the board. They phone each other every night. One day both change the price of tea: Rs 12 in Mumbai and Rs 15 in Chennai. Each shop now has its own price and has heard a different one from the other. Someone must decide which price is right.

Why let more than one place accept writes?

In lesson 39, only one leader accepts writes. That is simple, but it has costs:

• Distance. In lesson 47 a round trip between Mumbai and Chennai takes 30 ms. A write from Chennai to a leader in Mumbai waits for that trip.
• A broken link. If the link between the cities is cut, the side without the leader cannot write (lesson 47).
• Offline devices. A notes app on a phone accepts changes when there is no network. The phone is then a place that accepts writes.

The price is the write conflict: two places change the same item, and neither knows about the other change yet.

Two ways to build it

Multi-leader. There is more than one leader, for example one in each region. A region is a part of the world where a cloud provider has data centres. Each leader takes the writes of nearby users and sends its changes to the other leaders. This copying is asynchronous (lesson 39). In this kind of copying, each server works alone. The servers compare changes from time to time, and users or rules settle the conflicts (Postgres manual).

Leaderless. There is no leader. A client sends each write to several of the N copies and waits for W of them to confirm. A read asks R copies (lesson 48). Any copy can take a write. Read repair helps the copies agree: when a read finds an older copy, it writes the newer version back to it.

Both ways have the same problem. The rule R + W > N makes a read meet the latest write. It does not stop two clients writing the same item at the same time. Then there is no single "latest".

What is a conflict?

From lesson 49: if neither of two events happened before the other, they are concurrent. A write conflict is two concurrent writes to the same item. These are not conflicts:

• Two writes to different items.
• Two writes to the same item where the second writer had already seen the first. The time between them does not matter.

To find a conflict, give each write a version list, as in the vector clock of lesson 49. With two leaders, Mumbai (M) and Chennai (C), a list has two numbers. Compare the lists entry by entry. Suppose every entry of one list is at most the same entry of the other, and one is smaller. Then the second write is newer and replaces the first. If neither list is below the other, the writes are concurrent: a conflict. A timestamp cannot do this job, because clocks differ (lesson 49). A conflict needs two writers to change one item inside the copy delay.

Four ways to settle a conflict

1. Avoid it. Give each item a home leader, chosen by a fixed rule on the item ID. All writes for that item go to its home leader, wherever the user is. There is no conflict. The cost is the trip to a far home leader, and the item cannot be written when its home is cut off.

2. Last write wins (LWW). Every write carries a timestamp. Every copy keeps the larger timestamp and drops the other write. All copies end with the same value, and nobody has to do anything. The costs:

• One write is thrown away, and nobody is told.
• The "last" write is a guess. With clock skew (lesson 49), the write that was later in real time can have the smaller timestamp. Even with perfect clocks, concurrent writes have no real order.
• It is wrong for numbers that add up, such as a count of likes.

It is fine where losing one write does no harm, such as "last seen at".

3. Keep both versions, then merge. The store keeps both versions, called siblings. The next reader gets both and merges them, which means it joins them into one value by the rules of the app. It then writes that value back. That write has a version list above both old ones, so it replaces them. For a shopping cart, the merge is "all dishes from both versions". The cost is merge code for each kind of data.

4. Merge by a rule that always works: the CRDT idea. A conflict-free replicated data type (CRDT) has a merge rule that cannot fail. Merging copies in any order, any number of times, gives the same result. In plain words, merge(a, b) equals merge(b, a), and merge(a, a) equals a.

• A counter. Keep one count for each leader. A leader adds only to its own count. The total is the sum. To merge, take the larger value for each leader. Nothing is lost, because each count only grows.
• A set of items. To merge, take all items from both sets. A remove is harder. A common rule is "the add wins". Each add gets a unique tag, and a remove deletes only the tags it has seen. A counter that must also go down uses two such counts, one for adds and one for removes.

A CRDT cannot enforce a rule that needs one answer for the whole world. Examples are "stock never goes below 0" and "a seat is sold once". For those, keep one leader for the item (lesson 22).

SwadKart, a food app, runs two leaders: one in Mumbai and one in Chennai.

Assumptions (made up to teach with, not measurements):

• A round trip between the cities takes 30 ms (lesson 47). A disk write takes 1 ms. A change reaches the other leader 200 ms after it is saved (slower than the 30 ms trip, because changes wait in a queue).
• Mumbai's clock is 150 ms ahead of real time. Chennai's is 50 ms behind.
• A "party cart" is one cart shared by 4 friends, 2 in each city. Each friend adds a dish about every 10 seconds, for 10 minutes.
• For Step 7, the whole app takes 1,000 writes per second, 500 in each city.

Step 1: why two leaders. A Chennai user who writes to the Mumbai leader waits 30 + 1 = 31 ms. A Chennai leader takes 1 ms. That is 31 times faster.

Step 2: the phone number. Asha writes at real time T. Her timestamp is T + 150 ms. Ravi writes at T + 100 ms. His timestamp is T + 100 - 50 = T + 50 ms. The gap (100 ms) is less than the copy delay (200 ms), so neither writer had seen the other write. The writes are concurrent.

Under last write wins, T + 150 is larger than T + 50. Asha's number wins in both leaders, and after 200 ms both hold it. Ravi's write was later in real time, but it lost, and nobody was told.

With version lists, Asha's write is [M=1, C=0] and Ravi's is [M=0, C=1]. Neither is below the other, so the system sees a conflict and can keep both as siblings.

Step 3: how often? Two writes from different cities conflict if they are within the copy delay of each other. The window is 2 x 200 ms = 0.4 seconds.

The 2 Chennai friends add 2 x 0.1 = 0.2 dishes per second. A Mumbai write meets one inside the window with chance about 0.2 x 0.4 = 0.08 (8%, a rough number). In 10 minutes there are 4 x 0.1 x 600 = 240 writes, and Mumbai makes 120. Conflicts: 120 x 0.08 = 9.6. A profile that one person edits twice a day almost never conflicts. A shared cart conflicts all the time.

Step 4: the cart under each rule. Suppose the whole cart is one value. With last write wins, each conflict drops one dish: 9.6 of 240 vanish, which is 9.6 / 240 = 4%. With siblings merged by union, no dish is lost, but the app must merge. With a set that merges by union (a CRDT), no dish is lost and no app code is needed.

Step 5: a counter. A dish has 10 likes: Mumbai's count is 6 and Chennai's is 4. Mumbai adds 3 (count 9, total 13). Chennai adds 2 (count 6, total 12). The true total is 15. Last write wins on the total keeps 13 or 12, so it loses 2 or 3 likes. The CRDT merge takes the larger value for each leader: 9 and 6. The total is 9 + 6 = 15, and merging again changes nothing.

Step 6: leaderless. N = 3 copies (A, B, C), W = 2, R = 2. Asha's write reaches A and B. Ravi's write reaches B and C. A read of A and C gets two different values. R + W = 4 is more than 3, so a read meets both writes, but the version lists show that neither is newer. The app merges the two values and writes one value back to the copies.

Step 7: the write limit. Each leader takes 500 writes per second and applies 500 more from the other leader. That is 500 + 500 = 1,000, the same as one leader. The gain is distance, not capacity.

Step 8: a rule that merging cannot keep. One seat is left. Mumbai sells it to Asha and Chennai sells it to Ravi, within 200 ms. After the copy, both sales exist. No merge rule fixes this. Keep the seat on one home leader (lesson 22). A Chennai buyer then waits 31 ms.

• Several places accepting writes solves distance (1 ms against 31 ms) and keeps users writing when the link is cut. It costs conflicts. I would keep one home leader where a lost write does harm.
• Last write wins solves simplicity. It costs a silent loss (4% of cart dishes) and a winner that depends on clocks. I would use it only where losing one write does no harm.
• Siblings and merge solve the loss. They cost merge code for each kind of data.
• A CRDT solves conflicts for counters and sets with no code. It costs a limit: it cannot keep a rule such as "stock never below 0". I would use it for counts and lists, and one leader for money and seats.

"More leaders means more writes per second." It does not. Each leader applies the writes of all the others, so in the example each still handles 1,000 per second.

"Last write wins keeps the newest write." It keeps the larger timestamp. Clocks differ (lesson 49), so in the example the later write lost. For concurrent writes there is no newest one.

"A CRDT can merge anything." It merges counters and sets well. It cannot keep a rule that needs one answer for the whole world. Two cities can both sell the last seat, and the merge keeps both sales.

1. What is a write conflict? Name the four ways in this lesson to settle one.
2. Mumbai's clock is 120 ms ahead and Chennai's is 80 ms behind. Asha writes in Mumbai at real time T. Ravi writes in Chennai at T + 90 ms. A change takes 150 ms to reach the other leader. (a) Is this a conflict? (b) Under last write wins, whose write wins, and is it the later write? (c) A like counter has Mumbai 4 and Chennai 7. Mumbai adds 5 and Chennai adds 1 while cut off. What is the total after a CRDT merge?
3. A team wants two leaders, Mumbai and Chennai, for a train-seat booking table. What do you say?