CRDTs: how collaborative editing works

11:02:14  PUT /notes/8812  body="Agenda: ... (first user's edits)"   200
11:02:15  PUT /notes/8812  body="Agenda: ... (second user's edits)"  200

That’s from our logs, trimmed down, behind a customer complaint in May. Two people at the same customer had a shared meeting-notes page in our product open during a video call, both typed into it, and when the call ended one of them had lost a paragraph. Our notes feature saves the whole note on every change, and the server keeps whichever save arrived last. Last write wins, which is a polite name for “somebody’s work disappears”.

That was fine for years, because people rarely edited the same note at the same moment. Then everyone went remote, and now half our customers’ meetings involve a shared doc that several people type into while they talk. Google Docs has trained everybody to expect that to just work. So I spent a good part of June and July reading about how it does, and this is the write-up I wish I’d had at the start.

There are two families of answers. Google Docs uses the older one, operational transformation. The newer one is CRDTs, and it’s the one I find more interesting, so most of this post is about that.

The problem

Alice and Bob both have a copy of the document “ac”. Alice inserts “b” at position 1, between the a and the c. At the same moment Bob inserts “x” at position 1. Each of them sends their edit to the other.

Alice applies Bob’s “insert x at 1” to her “abc” and gets “axbc”. Bob applies Alice’s “insert b at 1” to his “axc” and gets “abxc”. They’ve both done something reasonable and they now have different documents, and nothing will ever bring them back together.

Positions are the problem. “Position 1” meant something specific when the edit was made, and by the time it arrives somewhere else, the document has changed under it.

Operational transformation fixes this by rewriting incoming operations against the ones that happened concurrently. When Bob receives “insert b at 1” and knows he’s already inserted something at or before position 1, he transforms it into “insert b at 2”. You need a transform function for every pair of operation types, and getting them all correct in every interleaving turns out to be really hard. Most working OT systems lean on a central server that decides a single order for everything, which Google’s does. The approach goes back to the Jupiter system from Xerox PARC in the ’90s, and Google Wave was built on it too. It works, at a lot of engineering cost.

The CRDT idea

A CRDT, a conflict-free replicated data type, takes a different approach. Instead of fixing up operations after the fact, you design the data structure so that conflicts can’t happen. Each replica can be changed locally with no coordination at all, replicas swap their states (or their operations) whenever they can, in any order, as many times as they like, and they’re mathematically guaranteed to end up identical once they’ve seen the same updates. The name and the formal treatment are from a 2011 paper by Marc Shapiro, Nuno Preguiça, Carlos Baquero and Marek Zawirski, though some of the ideas are older.

For the state-based kind, the whole guarantee comes down to the merge function. If merging two states is

• commutative, so merge(a, b) = merge(b, a),
• associative, so it doesn’t matter how you group a chain of merges,
• and idempotent, so merge(a, a) = a,

then it doesn’t matter what order updates arrive in, how they’re batched, or whether the same one shows up twice. Everyone converges. (This is the one place this year my math degree gets to come out and play. A set with an operation like that is a join-semilattice, and the merge is the least upper bound. I last thought about lattices for an exam a very long time ago, and assumed that was the end of it.)

The easiest way to see it is a counter.

A counter that can’t double count

Say you want to count page views on three servers that can’t always talk to each other. The naive approach, each server keeps a number and you add them up when they sync, breaks the first time a sync message gets delivered twice, or a server merges in a state it’s already merged. You count things twice and you can’t tell.

The CRDT version is called a G-Counter (G for grow-only). Each replica keeps a vector with one slot per replica, and only ever increments its own slot. The merge takes the maximum of each slot. The value is the sum of the slots.

B’s view of A is stale, it saw A when A’s count was 1. That doesn’t matter, since max(3, 1) is 3. Merge the same state in a second time and nothing changes. The trick is that each slot has exactly one writer, so the maximum is always the latest value for that slot, and “latest” doesn’t depend on who heard about it first.

If you want to decrement too, you keep two G-Counters, one for increments and one for decrements, and the value is the difference. That’s a PN-Counter, and Riak has offered counters like these, plus sets and maps, as built-in data types for a few years now.

Sets, and the add-wins choice

Sets are where you first have to make a decision. Alice adds “milk” to a shared shopping list. Bob, who hasn’t seen that yet, removes “milk” because he bought some yesterday. When their changes merge, is milk on the list or not?

There’s no right answer, only a policy. The common choice is add wins, and the way to get it is the Observed-Remove Set. Every add gets a unique tag, so Alice’s add is really “milk, tag a7”. A remove doesn’t remove “milk”, it removes the specific tags the remover had seen. Bob’s remove only covered the tags that were in his copy, the old milk from last week, so Alice’s new a7 survives the merge and milk stays on the list. If Bob had seen a7 and removed it, it’d be gone. Concurrent add and remove, add wins. Sequential ones do what you’d expect.

The other simple option, which plenty of systems use, is a last-writer-wins register: tag every value with a timestamp and keep the newest. It’s a valid CRDT (max by timestamp is commutative, associative and idempotent), and it’s exactly what our notes feature already did. It converges. It just converges by throwing one person’s work away, which is why “it’s a CRDT” isn’t the end of the conversation.

Text: give every character a name

So back to Alice and Bob. The root problem with text was that positions shift. The CRDT fix is to stop using positions at all.

Every character gets a unique, permanent ID when it’s typed, typically a pair of (counter, replica): the replica’s ID, plus a number that’s higher than any counter that replica has seen. And an insert doesn’t say “at position 1”, it says “after the character with ID such-and-such”. That reference never moves, no matter what else gets inserted around it.

The one remaining case is when two people insert right after the same character at the same time, which is exactly our example. That needs a tie-break that every replica will apply the same way, and the one in RGA, one of the classic sequence CRDTs, is to put the insert with the higher ID first, comparing counters and then replica IDs.

Alice and Bob both end up with “axbc”. Whether that’s the order either of them would have chosen doesn’t matter much, what matters is that they agree, and they agree without ever having talked to a server.

Deletes are the other half. You can’t actually remove a deleted character, because someone else’s concurrent insert might refer to it (“after 5@B”) and would have nothing to attach to. So a delete just marks the character as a tombstone. It stays in the structure, invisible, forever, or until you can prove every replica has seen the delete and nobody can still refer to it, which in a system where clients go offline for weeks is hard to prove.

The hard parts

This is where it stops being a neat whiteboard diagram, and it’s what Martin Kleppmann’s talk CRDTs: The Hard Parts from last month is about. It’s an hour, it’s very clear, and if you watch one thing on this, watch that. The problems I’d single out:

Metadata size. Every character carries an ID, and every deleted character stays around as a tombstone. A naive implementation of a long-lived document can be many times bigger than the text itself, in memory and on disk. Most of the recent work, like the Automerge project Kleppmann works on and Kevin Jahns’s Yjs, is about compressing this, for example by storing runs of characters typed in sequence as a single item.

Interleaving. If Alice types “Hello “ and Bob concurrently types “Hi “ at the same spot, you’d want “Hello Hi “ or “Hi Hello “. Some published sequence CRDTs can give you the characters of the two words interleaved, something like “HHeil lo”, which converges perfectly and is useless. Kleppmann and his co-authors wrote a paper on this last year. RGA mostly avoids the worst of it because each person’s run of characters chains off their own previous character.

Moves. Moving an item in a list (dragging a to-do to the top) is usually modeled as a delete plus an insert, and if two people move the same item concurrently, you end up with two copies. Moving subtrees in a tree, like folders, is harder still, because two concurrent moves can create a cycle.

And the general one. A CRDT guarantees everyone sees the same document. It doesn’t guarantee the document makes sense. If Alice fixes a typo in a sentence that Bob concurrently deletes, the merged result is defined, but one of them is going to be surprised.

Who’s actually using this

Not as many people as the amount of reading I did would suggest. Figma wrote about its multiplayer system last October and said, “Figma isn’t using true CRDTs though”. They took the ideas, but because they have a central server anyway, they could drop a lot of the overhead that you only need when there isn’t one. And Raph Levien’s retrospective on the xi editor from late June, which was built around a CRDT from early on, has a line I’ve thought about a lot since, that he “had no idea how deep the rabbithole would be of OT and then CRDT”. He’s one of the smartest people writing about text editors, and he decided the complexity hadn’t paid for itself in that project.

My reading is that CRDTs are the right tool when you really need to edit without a server: offline-first apps, peer-to-peer, devices that sync whenever they happen to be near each other. If every edit goes through your server anyway, you can have that server put edits in order and get away with something much simpler, and that’s what most production systems seem to do.

Which is roughly where we landed for our notes. We’re not shipping a CRDT. Our first step, already live, is that the client sends edits as small operations against a version number instead of whole-note saves, the server applies them in order, and if your edit was based on an old version and touches text someone else changed, you get a merge prompt instead of silently losing a paragraph. It’s a long way from Google Docs. It does fix the complaint from May, and I understand every line of it, which wasn’t true of the Yjs prototype one of our engineers built in July. That prototype worked, it was a bit magical to watch, and he’s now quietly lobbying for it. I haven’t said no.