Two people are working on a shopping list together on their phones. Both have lost their internet connection—one is in an elevator, and the other is on a plane. Lan adds "milk," and Minh adds "eggs." Half an hour later, both have their internet connection back.
The correct result should be a list containing both milk and eggs. But for the machine to do that on its own without asking anyone, it requires a data design approach that’s completely different from the usual one. That’s CRDT.
Why Does the Familiar Method Cause Data Loss?
The most common approach is to let the server decide: whichever version is submitted later wins. That sounds reasonable, but let’s see what happens with the shopping list.
Lan's file was uploaded first, and Minh's file was uploaded later. The server saved Minh's version and deleted Lan's. The "edit" option disappeared, and no one was notified.
The second approach is to ask the user, "There's a conflict—which version do you want to keep?" It's safer, but it shifts the burden to the user, and with items that are constantly being updated, like shared documents, you'd be asking this all the time.
CRDT takes a third approach: designing data structures so that aggregation always yields a single, correct answer that can be computed by a machine, without the need for a referee or consultation with anyone.
The Three Qualities That Make Magic Happen
To merge without arbitration, the merger must satisfy three conditions. It sounds very mathematical, but the practical implications are simple.
Swapping the order—that is, merging Lan’s version into Minh’s, or vice versa—yields the same result. This is important because on the network, you have no control over which packet arrives first.
Grouping means that with three or more machines, it doesn’t matter which pairs are grouped first. There’s no need for a global order—something that’s very difficult to achieve in a distributed system.
"Harmless duplication" means that receiving the same packet twice is not an error. This saves you from an entire class of errors, since real networks always send duplicate packets when retrying.
Given these three properties, the copies will certainly converge to the same state—regardless of who sent them first, which packets got lost, or which ones arrived twice.
The simplest example: counting likes
Suppose a post is liked on three different servers, and they synchronize slowly. If each server keeps its own count and then takes the largest number when merging them, you’ll lose likes. If you simply add them up without checking, you’ll count them twice.
The solution is that each machine may only write in its own cell.
Machine A counts 5, Machine B counts 3, and Machine C counts 2. To combine the results, we take the largest value from each cell and add them together: 5 + 3 + 2 = 10.
Why take the largest value instead of adding it? Because the cell for Machine A is written to only by Machine A, so the number there always increases. If an older version is received, ignore it; if a newer version is received, update it. It doesn’t matter if a duplicate is received—taking the largest value twice still yields the same number.
To count both increases and decreases, use two counters as described above—one for increases and one for decreases—and the result is the difference between the two totals.
Sets: Adding is easy; deleting is the hard part
Back to the shopping list. Adding an item is easy: union is the operation that combines two sets, and the union satisfies all three properties listed above.
The trouble started when something was deleted.
Lan deleted "milk" from the list. Minh's computer didn't know about that, so "milk" was still there. When they merged the lists using the union operation, "milk" reappeared—because to a computer, "I don't have milk" and "I deleted milk" look exactly the same.
The solution is to keep a record of changes: when an element is deleted, we don’t remove it but mark it as deleted. This mark is often called a “tombstone.” During a merge, the deletion mark takes precedence over the surviving element, so the result is what the user intends.
The cost is that the list of tombstones just keeps getting longer. A document that has been edited over many years may carry more traces than actual content. The system must be cleaned up periodically, and this can only be done once it is certain that all copies have received notification of the deletion.
Text: The Most Difficult Problem
Collaborative editing is the aspect of CRDT for which it is best known, and it is also the most challenging. The problem is that the position within the text is not fixed.
Suppose the text is currently "MEO." Lan inserts "C" at the beginning, and Minh inserts "O" at the end. If we describe the operation using a position number—"insert at position 3"—then after Lan’s operation is applied, position 3 now points to a different location. Minh’s character ends up in the wrong place.
The solution is to eliminate sequence numbers entirely. Each character is assigned a permanent identifier that never changes, and the insertion operation is described in terms of the relationship: "between the character with code X and the character with code Y."
The interesting detail here is that between any two codes, there is always a new code that lies between them—just as between any two real numbers, there is always another real number. Thanks to this, there is always room to insert a new code, no matter how many times you insert one at the same point.
When two people try to insert data into the exact same slot, a tie-breaking rule is needed—usually a comparison of the machine’s identifier. Any rule will do, as long as all machines use the same rule, because the goal is for everyone to arrive at the same result.
Result: All copies match
This is what CRDT promises and delivers: machines can receive changes in any order, as many times as necessary, as long as everyone eventually receives all the changes, everyone will end up with the same state. No central server is needed, no keys are required, and there’s no need to ask the user.
Two Approaches to Implementation
Send status. Each machine periodically sends its entire status, and the recipient aggregates it. This method is simple and tolerant of packet loss, but it consumes a lot of bandwidth if the data is large. Modern implementations send only the changes instead of the entire status.
Send the operation. Each machine sends only the operation it just performed. This is very efficient, but requires the transport layer to ensure that all operations arrive, are not lost, and are not applied more than once.
What CRDT Doesn't Promise
This is the most common source of misunderstanding. CRDTs ensure that all copies converge to the same result. They do not guarantee that the result will be to the user’s liking.
If two people edit the same sentence in different directions, the result could be a nonsensical hybrid sentence. CRDT only guarantees that everyone will see that very hybrid sentence—it doesn’t guarantee that it’s any good.
CRDTs cannot handle operations that require global consistency—such as "the balance must not be negative" or "only one person can hold this position." Those cases still require true consensus.
When to Use It
- Suitable for: notes, to-do lists, drawings, collaborative drafting, and multi-device sync—where internet outages are common and auto-merge is better than forcing users to choose
- Not suitable: financial transactions, reservations, inventory — where an incorrect result is truly wrong, not just unsightly
- Consider: very large datasets or data that’s continuously updated over many years, as the accompanying metadata can exceed the actual data
If you're planning to implement this yourself, use an existing library instead of writing it from scratch. The hard part isn't the idea—the idea is just like the one in this article—but rather compressing metadata, cleaning up orphaned entries, and maintaining performance as the document grows.
Thảo luận