Why CRDTs exist

Two people typing into the same document at the same time, possibly offline, possibly across the world. The merge has to come out the same on both screens with no central referee. CRDTs are the data structures that make that arithmetic instead of a fight.

The picture version

Six pictures for a reader who has never heard of a CRDT, following one instant: you and I typing into the same spot in the same sentence, at the same moment, with neither laptop having heard from the other.

Why it exists

Open a shared doc with a colleague. You’re both typing into the same paragraph. Sometimes one of you is on a flaky train. The cursors move, the text rearranges, and the final document looks the same on both laptops. Nobody fights, nobody loses a sentence, nobody has to click “resolve conflict.” Keep one specific instant of that in mind for the rest of this post — you and I both typing a character into the same spot in the same sentence, at the same moment, with neither laptop having heard from the other yet. Every design decision below is about that instant.

Now try to write the code that does this.

The naive plan — “send each keystroke to a server, the server picks an order, everyone replays” — falls over the moment one of you is offline, or the server is far away. The slightly-less-naive plan — “diff the two documents, three-way merge them like Git does” — works fine for source control where humans review the result, and works terribly for a live cursor where the merge has to be instant, automatic, and silent.

What you actually want is something stronger: a way to represent the document such that any two replicas that have seen the same set of edits end up identical, no matter what order the edits arrived in. No central authority, no locking, no asking permission before typing. Edits commute.

That property — concurrent edits always merge to the same answer — is the whole reason Conflict-free Replicated Data Types (CRDTs) were invented. They are the data structures that make collaborative editing arithmetic rather than negotiation.

Why it matters now

Real-time multiplayer is no longer a Google-only superpower. Multi-cursor canvases, notes apps that sync across devices, editors that keep working on a train and reconcile afterwards — all of them need some automatic merge, and whichever mechanism they picked, they were solving the problem CRDTs are designed for.

Being precise about who uses what is harder than the marketing suggests, and most public claims here are secondhand. Two that aren’t: Figma’s own engineering blog describes their multiplayer system as CRDT-inspired and explicitly says it isn’t using true CRDTs, and Google Docs is long and widely described as built on OT, the older approach. Yjs and Automerge are two of the most visible open CRDT implementations and underpin a long tail of local-first apps. Beyond that, what most named products run internally simply isn’t published — the honest summary is that the problem is universal while the mechanism is usually undisclosed.

The shape recurs beyond documents, too: any multi-writer replicated state with no referee — a multi-device to-do list, a shopping cart, a counter gossiped between regions — has the same problem. Whether a given team reaches for a CRDT library or hand-rolls something simpler is mostly anecdote; the problem is not.

The short answer

CRDT = data structure + a combine rule that ignores order, duplication, and timing

Picture to keep: two people separately adding coins to two piles, then pouring the piles together. It doesn’t matter who pours first, or whether someone pours the same pile twice — the heap on the table is the same. Like pouring coins, except a document has an order and coins don’t: the hard work in a text CRDT is making “where does this character go” survive the pour, and that’s the part the analogy can’t show you.

In English: every operation can be applied in any order, applied more than once, or applied alongside someone else’s operation, and the final state is the same. The merge is forced to be safe by the shape of the data, not by a coordinator deciding who wins. (The compression line is deliberately loose about where that rule lives: in the state-based flavor below it’s a merge function on values that is commutative, associative, and idempotent; in the operation-based flavor it’s the operations themselves that must commute. Same demand, two places to satisfy it.)

How it works

Two flavors exist, and it’s tempting to present them as a menu. Start from the failure instead: newer-wins loses edits, shipping whole state is too heavy for text, and raw positions don’t survive concurrent inserts. Each flavor answers one of those breakages — so build it that way, with you and me typing into the same sentence.

Naive attempt: send my whole document, you take the newer one. Simple, and it converges: last write wins. Why it breaks: one of us loses an entire paragraph. “Converges” and “correct” are different words, and this is the gap CRDTs live in.

Fix: don’t replace, combine — make the merge a function of both values. Now you need a merge that gives the same answer regardless of who merges what, in what order, how many times. That’s a real algebraic constraint, and it’s the first flavor.

State-based (CvRDT) — ship the whole value, take the join

Each replica holds a value drawn from a join-semilattice: the values can be combined by a merge operation that is commutative (merge(a, b) = merge(b, a)), associative (merge(a, merge(b, c)) = merge(merge(a, b), c)), and idempotent (merge(a, a) = a).

Those three properties are doing all the work. Together they mean: it doesn’t matter which replicas you merge, in what order, or how many times — the result is the same. You can ship full state around with a gossip protocol, drop messages, deliver them out of order, redeliver them, and the system still converges.

This is the clean algebraic version of the idea — and notice how far it already is from our shared sentence. The textbook example is a G-Counter (grow-only counter): each replica keeps its own slot in a vector of counts, only ever increments its own slot, and merge takes the elementwise maximum. Two replicas that have seen different increments will, after exchanging state, agree on every slot — and therefore agree on the sum.

Replica A: [3, 0, 1]   (A=3, B=0, C=1)
Replica B: [0, 2, 1]
merge:     [3, 2, 1]   (max in each slot)

A PN-Counter (supports decrements) is two G-Counters glued together. A G-Set (grow-only set) just unions. An OR-Set (observed-remove set) tags each insert with a unique ID so you can tell “I’m removing the banana I saw” from “I’m removing all bananas, including ones added later.” Once you start composing these, you can build registers, maps, and sequences.

Why it breaks: you are not editing a counter, you are editing a document. Shipping the whole state on every keystroke means shipping the whole document on every keystroke — fine for a three-slot vector, absurd for a novel.

Operation-based (CmRDT) — ship the operations

Fix: send only what changed. Replicas broadcast each operation (“insert ‘x’ at position p with ID k”) instead of the full value. For this to converge without a total order, every pair of concurrent operations must commute — the same algebra as before, relocated from the merge function into the operations themselves.

Why it breaks: “position p” is a lie. If I insert at index 5 and you insert at index 5, and my edit arrives first, your index 5 now points at a different character. Positions in a shared sequence are not stable, so operations defined against them do not commute. This is the moment collaborative text editing gets genuinely hard, and it’s the instant from the hook.

Fix: give every character an identity that never moves. Instead of “insert at index 5,” an operation says “insert this character here,” where here is an identifier that other people’s inserts cannot invalidate.

The general move: each character gets a globally unique identifier that places it in some well-defined order, and concurrent inserts at “the same spot” produce different identifiers that the data structure knows how to interleave deterministically. Different CRDTs do this differently, but they share one move: identify elements by stable identity instead of by mutable position, which is what lets the model transfer from text to any other ordered data. Logoot and Treedoc use dense fractional identifiers (a path in a tree, or a list of (replica-id, counter) pairs) so a new ID can always be found between two neighbors; RGA takes a different approach, treating the sequence as a growable linked structure where each insert names the element it sits after. Per their own documentation, Yjs adapts an algorithm called YATA, while Automerge’s list type is RGA-based and its rich-text type uses a newer scheme called Peritext. The family is less uniform than introductory writing usually implies.

Why it breaks: you can’t delete anything. If I remove a character while your concurrent insert names it as its anchor, your operation has nowhere to land. Fix: don’t actually remove it — mark it dead. Which brings us to the bill.

What CRDTs cost

This is the seams part. The math is beautiful; the engineering is real.

• Tombstones. To safely delete a character without breaking concurrent inserts that referenced it, most text CRDTs keep a marker for the deleted item rather than removing it. Over a long-lived doc the structure accumulates tombstones, and storage and merge cost grow with edit history, not just current document size. Collecting tombstones safely requires establishing that no live replica can still reference them — causal stability — and how expensive that is depends on the deployment. A system with a known, bounded set of replicas or a server that sees everything can often track it cheaply; an open peer-to-peer system generally can’t, and falls back to something coordination-shaped. Yjs and Automerge have spent years reducing this overhead; it isn’t gone.
• Metadata weight. Every character carrying a unique identifier isn’t free. CRDT documents carry per-element metadata that plain text doesn’t, and operation logs grow with edit count. In recent years the gap has narrowed considerably — Yjs in particular is impressively compact — but the constant factor is still nonzero and shows up in cold-load times. I’m not citing a specific size ratio here because it depends heavily on the algorithm, edit history, and encoding.
• CRDTs converge to a state, not necessarily the right state. Convergence is a weaker promise than human intent. If you and I both edit the same sentence concurrently, a CRDT will deterministically produce some merged sentence. There is no guarantee it makes sense. For text this is usually fine; for “shopping cart of unique items” or “list of approved transactions” it can be very wrong, which is why financial systems still use coordination instead.
• Causal delivery is usually assumed. Operation-based CRDTs generally assume operations are delivered in causal order — roughly, nobody processes a reply before the message it was replying to: if op B was created on a replica that had already seen op A, then no replica processes B before A. State-based CRDTs don’t need this; they merge full states. Causal delivery is weaker than total order, but it isn’t free; the network layer (often vector clocks plus a buffer) has to enforce it.
• OT is not dead. Operational Transformation, the older approach Google Docs is built on, has its own advantages — particularly that the document representation can stay closer to plain text, without CRDT-style per-character identity metadata. The OT-vs-CRDT debate isn’t fully settled in production; Martin Kleppmann’s writing is a good place to read both sides honestly.
• The OT-vs-CRDT split isn’t publicly measured. No survey covers what fraction of collaborative-editing products run CRDTs versus OT, because most teams never disclose the mechanism. Treat any confident breakdown you read — including a plausible-sounding one — as unsourced.

Back to the opening instant: you and I typing into the same spot in the same sentence, neither laptop having heard from the other. Both characters get globally unique identifiers, both operations name the character they sit after, and both replicas interleave them by the same deterministic rule — so both screens land on the same sentence, without either of us waiting for a referee. That’s the whole answer.

You started with CRDT = data structure + a combine rule that ignores order, duplication, and timing. What did this post add? — + per-element identity, and the tombstones that identity forces on you. The combine rule is what makes merging safe; stable per-character IDs are what make that rule achievable for a sequence; and not being able to promptly forget a deleted character is the bill for both. A CRDT isn’t magic, and it isn’t just “eventual consistency for documents” — it’s a deliberate restriction of what the data structure is allowed to be, paid for in metadata, in exchange for writing to any replica at any time without asking anyone.

Check yourself

Before you go — a teammate proposes using an OR-Set CRDT for a bank’s “pending transfers” list, reasoning that a set with automatic merge means they’ll never lose a transfer. What would you tell them?

And one more — if tombstones are the cost of deletion, why can’t a client just drop tombstones older than, say, a week?

Famous related terms

• Eventual consistency — eventual consistency = replicas may disagree now + guaranteed to converge later. CRDTs are the data-structure-level discipline that makes eventual consistency automatic for specific shapes.
• Operational Transformation (OT) — OT ≈ each incoming edit gets transformed against concurrent edits the sender hadn't seen. The pre-CRDT approach Google Docs is built on; same problem, different mechanism.
• Vector clock — vector clock ≈ per-replica counters that detect "happened before" vs. "concurrent". The plumbing most operation-based CRDTs use to deliver ops in causal order.
• Local-first software — local-first ≈ apps where the local copy is the source of truth and the network is an optimization. The architectural style CRDTs unlock; coined by Ink & Switch.
• Yjs / Automerge — Yjs / Automerge ≈ production CRDT libraries — the two you’ll actually meet. My impression from using them is that Yjs optimizes hard for size and speed while Automerge offers a richer JSON-like document model; that’s a judgment about their design emphasis, not a benchmark result.

Going deeper

• Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski, “Conflict-free Replicated Data Types” (2011). Answers “what exactly must be true for a structure to count as a CRDT?” — it laid out the convergence framework most implementations cite and standardized the “Conflict-free” reading of the acronym. (The acronym is older: Preguiça et al.’s 2009 Treedoc work used “Commutative Replicated Data Type.” 2011 is the formalization, not the naming.)
• Martin Kleppmann’s blog and talks on CRDTs, OT, and Automerge — the place to go for “which approach should I actually use, and what does each one cost me,” argued by someone who builds both and is unusually honest about the limits.
• Ink & Switch, “Local-first software: You own your data, in spite of the cloud” (2019, Kleppmann et al.). The rabbit hole: what product becomes possible once merge is automatic, which is a different question from how merge works.