• Paul Butler
Conflict-free replicated datasets (CRDTs) are a family of replicated data structures.
CRDTs differ from simple leader/follower replication in that they do not designate an authoritative source-of-truth that all writes must pass through. Instead, all replicas are treated as equal peers. Each replica may be modified locally, and changes to any replica are propagated to the others.
In developer discourse, the term CRDT sometimes gets thrown around as a synecdoche for a broader set of techniques to enable Figma-like collaborative features. But when we started talking to dozens of companies building ambitious browser-based apps, we found it rare for apps to use true CRDTs to power multiplayer collaboration.
In this post, I’ll first give some high-level context on CRDTs, and then talk about why we often find other approaches used in practice.
Synchronizing State
The core problem that multiplayer apps need to solve is maintaining shared state. If you and I are both editing the same document, I should see your changes in real-time and vice versa.
At the code level, this means that there is some data structure (say, a tree or list) representing the document which exists in multiple locations: one for each user with the document open. Changes made on one copy need to be reflected by the others, as quickly as possible.
One way to accomplish this is to serialize each change and broadcast it over the network. If you and I are collaborating on a todo list, and I mark the fifth item as done, my replica emits some serialized event meaning “Mark item #5 as done”. If you then add an item ‘get groceries’ in the third position, your replica emits an event meaning “Insert ‘get groceries’ before item #3”.
This works fine as long as enough time passes for each of us to receive the others’ changes before making our own change. If not, things break down.
Suppose we start a collaboration session at time 0 with a list of two items, Get groceries and Do laundry.
At time 1, I mark Do laundry as done, and you simultaneously add a new item called Clean kitchen to the middle of the list. When my replica sees your edit at time 2, your change is appropriately applied on top of mine and I see the correct state. But when my change (“mark item 2 as done”) reaches your replica, “item 2” refers to the item you just added, not the one I actually checked. Our lists have diverged.
The problem comes down to the interplay of two facts:
- Operations on our data structure are not commutative: the result of applying them depends on the order in which they are applied.
- Our operations are unordered. Each replica might receive and apply the changes in a different order.
If we can design a system in which either one of these statements is no longer true, we can ensure that our data structure is eventually-consistent. Each of the two items represents a different path we can take.
Path #1 represents CRDTs. Broadly, you can think of CRDTs (specifically, operation-based CRDTs) a
