CRDTs
A family keeps one shopping list on two phones. One person is in the metro with no signal and ticks off milk, because they just bought some. At home, the other notices the milk has run out again and adds it. Twenty minutes later both phones are online. What should the list say?
No server was there to decide, and no clock can be trusted to settle it. The two edits happened without either phone seeing the other's. Most systems would quietly pick one and lose the other. A CRDT is a way of designing the data so that the two phones merge on their own, always to the same answer, without losing either edit.
Mumbai and Singapore both count likes on the same post while the link between them is down. Mumbai counts 40, Singapore counts 25, starting from 100. When the link returns, how would you merge so the answer is 165, even if the merge message is delivered twice?
Replicas that merge on their own#
The chapters so far gave you two ways to keep copies of data in step. Consensus makes every write wait for a majority, so it is correct and stops working on the minority side of a split. Last write wins accepts every write everywhere and silently drops one of two concurrent ones.
CRDTs (conflict-free replicated data types, named in a 2011 paper by Marc Shapiro and colleagues) take a third path. Every replica accepts writes locally, with no coordination, and the data type comes with a merge that is guaranteed to bring replicas to the same state once they have seen the same updates, in any order. That guarantee is called strong eventual consistency: no conflicts to resolve by hand, no write thrown away, no waiting.
The catch is that you cannot do this with any data type. The merge must have three properties:
Commutative: merging A into B gives the same result as merging B into A. So the order updates arrive in does not matter, and you do not need clocks to order them.
Associative: merging A with B and then C is the same as A with the result of B and C. So it does not matter which replica gossips with which first.
Idempotent: merging the same state twice changes nothing. So duplicate delivery, the whole problem of the exactly-once chapter, simply stops mattering.
Those three properties make the two hardest problems of this path (ordering and duplicates) irrelevant. The rest of this chapter is about which data can be shaped to have them.