CRDTs
Conflict-free replicated data types: data structures that every device can edit on its own, offline or online, and that always merge to the same result without a central server deciding the order.
The problem: edits that meet late
Picture a small team planning a trip in a shared notes app. Asha edits the packing list on a train with no signal. Ben edits the same list at home on his laptop.
Both keep typing for an hour. When Asha's phone finds a network again, two different versions of the same list meet. What should the app show?
The easy answers are all bad. "Last save wins" throws away an hour of somebody's work. "Show a conflict dialog" asks a person to merge text by hand, which nobody enjoys on a phone.
"Lock the list while someone edits" means Ben can't touch it while Asha is in a tunnel. Users expect what they get from Google Docs or Figma: both sets of edits, merged, with nothing lost.
The lesson on operational transformation (OT) showed one way to merge: a central server puts every operation in one order and transforms late operations so they keep their meaning. That works well when everyone is online and talks to one server. It gets hard when edits pile up offline for hours, or when there is no single server (peer-to-peer, or several regions).
What a CRDT is
A CRDT (conflict-free replicated data type) is a data structure built so that merging is always automatic and always gives the same answer. Each device (a replica) keeps its own full copy. Any replica can change its copy at any time, with no network and no permission.
Later, replicas swap what they know, in any order, any number of times. When every replica has seen the same set of changes, every replica holds the same value.
That last property has a name: strong eventual consistency. "Eventual" because replicas can differ for a while. "Strong" because the moment two replicas have received the same changes, they are equal, with no extra round of voting or fixing. Nobody has to win a race to the server.
- No central order. Two replicas never need to agree on which edit came first. The data structure is designed so that it doesn't matter.
- Offline by default. An edit is applied locally at once. Sending it to others is a separate, later step that can wait for hours.
The price you pay
Nothing is free. To merge without a referee, a CRDT has to keep extra information next to the data: who made each change, a unique id per inserted character, and markers for things that were deleted. A document of 10,000 characters is not stored as 10,000 bytes. The metadata, the memory it costs, and how modern libraries shrink it is a big part of this lesson.
CRDTs also don't decide what a good merge means for your product. They guarantee everyone ends up with the same result, not the one a person would have picked. If Asha and Ben both rename the trip at once, every device picks the same name; whether that is fine is a product choice.
Check your understanding · Exercise 1
Two replicas of a CRDT have both received exactly the same set of changes, but in a different order. What is true? Pick one.
The mental model: merge is a union
The simplest CRDT is one you already know: a set that only grows. Asha's phone holds the tags {beach, hike}. Ben's laptop holds {beach, museum}.
To merge, take the union: {beach, hike, museum}. It does not matter who merges into whom, how many times, or in what order. Every path ends at the same set.
Every CRDT is a cleverer version of this picture. Each replica's state is a point on a map of possible states. Edits only move a replica upward on that map, never back down. Merging two replicas moves them both to the lowest point that is above both of them, the way a union is the smallest set that contains both sets.
Three laws that make order not matter
For the result to be the same on every device, the merge function has to obey three laws. They sound like school algebra, and they are, but each one protects you from a real network problem.
| Law | In symbols | The network problem it absorbs |
|---|---|---|
| Commutative | merge(a, b) = merge(b, a) | Asha syncs with Ben, or Ben with Asha: same result. Nobody has to go first. |
| Associative | merge(merge(a, b), c) = merge(a, merge(b, c)) | Updates can be relayed through any path: phone to server to laptop, or laptop to phone directly. |
| Idempotent | merge(a, a) = a | A message delivered twice after a reconnect changes nothing the second time. |
Union obeys all three. So does taking the maximum of two numbers. Adding two numbers does not: it is commutative and associative, but 5 + 5 is not 5, so a duplicated message would count twice. That one failing law is why a naive counter breaks, and the next chapter fixes it.
The trick behind every CRDT: give each writer its own space
Conflicts happen when two writers change the same thing. CRDTs avoid them by making sure two writers never change the same thing. Each replica gets a unique id (Yjs gives every Y.Doc a random numeric client id, 32 bits in the current 13.x release; Automerge uses a random actor id). Every change is stamped with that id plus a counter, so every change in the whole system has a name nobody else can produce.
With unique names, "Asha typed h" and "Ben typed o" are two different facts, not two competing versions of one fact. Merging two replicas becomes collecting facts: a union of everything anyone has done. The hard part, which the rest of this lesson is about, is turning a set of facts into a value people can see: a number, a title, a paragraph of text.
- Facts are the changes, each with a unique id. Replicas exchange facts.
- The view is what the user sees, computed from the facts by a fixed rule. Same facts in, same view out, on every device.
- The rule is the design of the CRDT. A counter sums the facts. A register picks the newest one. A text CRDT sorts characters into one line.
Check your understanding · Exercise 2
Which merge functions are safe for a CRDT (commutative, associative, and idempotent)? Select all that apply.
Warm-ups: a counter and a register
Before text, two small CRDTs that show the whole idea in a few lines. You will meet both in real products: like counts and view counts are counters, and almost every field of a form or a design object (a title, a color, a due date) is a register.
G-Counter: a counter that only grows
Three devices count likes on a post. The obvious state is one number, say 5. Asha's phone adds a like and sends 6. Ben's laptop also adds a like and sends 6.
Each side takes the bigger number and gets 6. One like is lost. If they add instead, a resent message counts twice. A single number can't be merged safely.
The G-Counter (grow-only counter) gives each replica its own slot. The state is a map from replica id to that replica's count, like { A: 3, B: 2, C: 0 }. A replica only ever increases its own slot.
To merge, take the maximum of each slot. The value shown is the sum of all slots.
type GCounter = Record<string, number>;
function increment(c: GCounter, me: string): GCounter {
return { ...c, [me]: (c[me] ?? 0) + 1 };
}
function merge(a: GCounter, b: GCounter): GCounter {
const out: GCounter = { ...a };
for (const [id, n] of Object.entries(b)) out[id] = Math.max(out[id] ?? 0, n);
return out;
}
const value = (c: GCounter) => Object.values(c).reduce((s, n) => s + n, 0);
Why it works: each slot has exactly one writer, so two replicas never disagree about a slot, they are only behind or ahead. max picks whoever is ahead, and max is commutative, associative, and idempotent. Try it below: add likes on each replica, merge in any order, merge twice.
Add likes on each replica, then send states across in any order.
max too, loses likes as soon as both sides add one.To also allow decrements (a cart quantity, an unlike), keep two G-Counters, one for additions and one for removals, and show the difference. That is a PN-Counter. Notice the cost already: the state grows with the number of replicas that ever wrote, not with the size of the number. A counter touched by 10,000 devices carries 10,000 slots.
LWW-Register: one value, newest wins
A register holds one value, like a document title. When Asha sets it to Lisbon trip and Ben sets it to Portugal 2026 while both are offline, only one can survive. The LWW-Register (last writer wins) stores the value together with a timestamp and the writer's id. Merge keeps the pair with the larger timestamp; if timestamps are equal, the larger writer id wins, so every replica breaks the tie the same way.
The timestamp is the subtle part. Wall clocks on phones can be minutes off, so a device with a fast clock would win every conflict.
Most systems use a Lamport clock instead: a counter that each replica sets to one more than the largest counter it has seen. Some use a hybrid logical clock, which stays close to wall time but never goes backwards. Either way the rule is deterministic, which is all a CRDT needs.
- When LWW is right: independent fields where the newest value is what people expect, like a title, a color, a toggle, or a position on a canvas. Figma's multiplayer post describes last-writer-wins per property for design objects.
- When LWW is wrong: anything where both edits carry meaning. Two people typing into the same paragraph must not have one paragraph replace the other. That needs a sequence CRDT.
The rest of the family
| CRDT | State | Typical use |
|---|---|---|
| G-Counter / PN-Counter | A count per replica | Likes, views, quantities |
| LWW-Register | Value, timestamp, writer id | A single field: title, color, due date |
| Multi-value register | Every concurrent value | Fields where a person should resolve a clash |
| OR-Set (observed-remove set) | Elements with unique add tags | Tags, members, selected items; add wins over a concurrent remove |
| LWW-Map / JSON map | A register per key | Objects with fields, like a shape on a canvas |
| Sequence (RGA, YATA) | Items with ids and neighbor links | Text, lists, ordered layers |
Check your understanding · Exercise 3
Asha (id A) sets the title with Lamport time 7. Ben (id B) sets it with Lamport time 7 too, while offline. Using the rule "larger time wins, then larger id", what happens? Select all that apply.
State-based or op-based: what travels on the wire
So far we merged whole states: Asha sends her entire counter map, Ben takes the maximum of each slot. That is one of two ways to build a CRDT. The other sends only the change itself, like "A added one". Both give the same final value; they differ in what they send and what they demand from the network.
State-based (CvRDT): send everything you know
A state-based CRDT (also called convergent, CvRDT) ships its full state. The receiver merges it with a function that obeys the three laws from chapter 2. Because merge is idempotent and order-free, the network can lose, repeat, and reorder messages, and things still converge as long as each state eventually gets through once.
The weakness is size. Shipping a counter map of three slots is nothing; shipping a 2 MB document after every keystroke is not an option. Pure state-based sync suits small objects, rare syncs, and the first load of a document.
Op-based (CmRDT): send each change
An operation-based CRDT (also called commutative, CmRDT) sends each change as a small message: insert this character with this id after that id, delete the item with this id. The messages are tiny, often a few dozen bytes. The receiver applies them, and the CRDT is designed so that concurrent operations give the same result in either order.
The price moves to the network layer. Classic op-based CRDTs need exactly-once, causal delivery: every operation arrives once, and never before the operations it depends on. An insert that refers to an origin character the receiver hasn't seen yet can't be placed. In practice libraries add ids to operations so duplicates can be dropped, and they buffer operations whose dependencies are missing until those arrive.
Delta-state: the hybrid real libraries use
Modern libraries sit in between. A delta is a small piece of state: just the part that changed, but shaped so it can be merged with the same lattice merge as a full state. Deltas are as small as operations and as forgiving as states: they can be repeated, batched, and merged with each other before sending.
Yjs works this way. Its updates are binary blobs that the docs describe as commutative, associative, and idempotent. You can apply them in any order, apply one twice, or merge many into one with Y.mergeUpdates.
An update can hold one keystroke or an entire document. If an update refers to items the document hasn't seen, Yjs keeps it pending until the missing ones arrive.
Decision What should replicas send to each other?
What we pick: Use what Yjs and Automerge already do: live deltas while connected, and a state-vector or heads exchange on reconnect so each side sends only what the other lacks. Full state is for the first load and for snapshots on the server.
Check your understanding · Exercise 4
Your WebSocket layer sometimes delivers a message twice after a reconnect. Which designs stay correct without extra work? Select all that apply.
How a sequence CRDT orders characters
Text is where CRDTs matter most and where they get interesting. A counter has no order; a paragraph is nothing but order. The OT lesson showed why positions are the enemy: "insert ! at index 2" means something different once another person has inserted text before index 2.
OT fixes positions by transforming them. A sequence CRDT stops using positions on the wire at all.
Every character gets a name and a neighbor
In a sequence CRDT, each inserted character becomes an item with three things: a unique id, the character itself, and an origin, which is the id of the character it was typed right after (or the start of the document). The id is a pair: a Lamport counter and the replica id. We write 3A for Asha's item with counter 3.
An insert message is no longer "put ! at index 2". It is "item 3A holds ! and comes right after item 2A". Item 2A is the letter i forever, wherever it ends up and whatever others type around it, so the message means the same thing on every replica.
This is the design called RGA (replicated growable array). Automerge's text and lists are based on RGA; Yjs uses a close relative called YATA.
A worked example: two people type at the same spot
Asha types hi, creating 1A (h, origin start) and 2A (i, origin 1A). Ben receives both, so his Lamport clock is now 2.
Then both go offline. Asha types ! at the end: item 3A, origin 2A. Ben types ? at the end: item 3B, origin 2A. Two items now claim the same spot right after i.
- Asha receives
3B. She finds its origin2Aand looks at what already follows it: her own3A. - The rule: skip over items that follow the origin and have a larger id than the new item. Ids compare by counter first, then by replica id.
3Avs3B: counters tie, andBis larger thanA, so3Ais the smaller one.3Bdoes not skip it and goes right here, before3A. - Asha's text becomes
hi?!. - Ben receives
3A. Its origin is2A, followed by his3B.3Bis larger than3A, so3Askips past it and lands after it. Ben's text is alsohi?!.
Neither side asked anyone. Both used the same ids and the same rule, so both reached the same line. The rule "larger id sits closer to the origin" is arbitrary but fixed, and fixed is all that matters.
3B sits before 3A. Every replica builds the same tree, so every replica reads the same text.The whole algorithm in 20 lines
Here is a complete, if slow, RGA. We fuzz-tested this exact logic with three replicas, random inserts and deletes, and random sync order over 2,000 runs: every run converged.
type Id = [counter: number, replica: string];
type Item = { id: Id; ch: string; deleted: boolean };
type Insert = { id: Id; origin: Id | null; ch: string };
const bigger = (a: Id, b: Id) =>
a[0] !== b[0] ? a[0] > b[0] : a[1] > b[1];
const same = (a: Id, b: Id) => a[0] === b[0] && a[1] === b[1];
function integrate(items: Item[], op: Insert) {
if (items.some((it) => same(it.id, op.id))) return; // seen it already
let i = op.origin ? items.findIndex((it) => same(it.id, op.origin!)) + 1 : 0;
// Skip items at this spot that have a larger id than ours.
while (i < items.length && bigger(items[i].id, op.id)) i++;
items.splice(i, 0, { id: op.id, ch: op.ch, deleted: false });
}
function remove(items: Item[], id: Id) {
const it = items.find((x) => same(x.id, id));
if (it) it.deleted = true; // a tombstone, not a splice
}
const text = (items: Item[]) =>
items.filter((it) => !it.deleted).map((it) => it.ch).join("");
Two details make it work. First, the local replica bumps its Lamport counter past every id it has seen, so a character typed after reading 3B gets counter 4 or more. Second, an item's origin must already be present: real libraries hold back an insert until its origin arrives, which is the causal delivery from chapter 4.
Why typed words stay together, mostly
Suppose Asha types tea and Ben types jam, both right after I like . Each new letter's origin is the letter its author just typed, so each word forms a chain. The chains attach to the same origin, the rule orders the two first letters, and each chain follows its head. Our implementation gives I like jamtea on both sides: ugly without a space, but neither word is torn apart.
That is not true for every pattern. If both people type backwards (cursor fixed, each new letter inserted before the previous one), plain RGA interleaves. Asha enters xyz as z, then y, then x, and Ben enters 123 the same way: all six letters share one origin, so our code merges them into 1x2y3z.
Research such as the Fugue paper (Weidner and Kleppmann, 2023) catalogues these interleaving cases for RGA, YATA, and older designs, and proposes algorithms that avoid them. In practice they are rare and cosmetic, but they show that "converges" and "looks right" are different promises.
YATA: what Yjs does differently
Yjs's YATA algorithm stores two neighbors per item: the left origin (the item it was typed after) and the right origin (the item that was right after it at that moment). When several items compete for the same gap, YATA uses both origins plus the client id to decide the order.
The right origin acts as a fence: an item can only land between its two origins, which keeps concurrent inserts from drifting past text their author could see. The YATA paper (Nicolaescu, Jahns, and others, 2016) proves the rule converges.
A different family avoids neighbor links: give each item a position that is a fraction between its neighbors (Logoot, LSEQ, and the simpler fractional indexing many apps use for list order: a card between 0.5 and 0.75 gets 0.625, in practice as strings). It is easy to store in a database row, but identifiers grow when people keep inserting in the same gap and text interleaves more, which is why the leading text libraries use RGA or YATA.
larger id sits closer to the origin gives both the same line.Check your understanding · Exercise 5
Document ab has items 1A (a) and 2A (b). Offline, Asha inserts x right after a as 3A, and Ben inserts y right after a as 3B. After sync, what does the RGA rule (larger id closer to the origin) produce? Pick one.
Tombstones, garbage collection, and memory
Look again at remove in the code above: it doesn't take the item out of the array, it sets deleted: true. A deleted item that stays in the structure is called a tombstone. It is invisible to the user but still has its id and its place in the line. Every sequence CRDT has them, and they are the main reason CRDT documents grow.
Why a deleted character can't just vanish
Asha deletes the word hike while Ben, offline, types s right after its e to make hikes. Ben's insert says "after item 9A", and 9A is the e that Asha deleted. If Asha's replica had thrown 9A away, it could not place Ben's s when it arrives.
With a tombstone, it finds 9A, puts s after it, and shows s where the word used to be. Both replicas agree, and Ben's letter is not lost.
hike while Ben typed s after its e. The faded tombstones are invisible to the user but keep their place, so Ben's letter lands where he typed it.Deletes need no ordering rule at all. A tombstone flag only goes from false to true, so two replicas that both delete the same character simply agree, and "delete, then a concurrent insert next to it" always keeps the insert. That is why deletes in CRDTs feel so calm compared with OT, where delete against delete is one of the trickiest transform pairs.
When can a tombstone be removed?
A tombstone is safe to drop only when no replica will ever send an operation that refers to it. That needs every replica to have seen the delete, a condition called causal stability. In a closed system with three servers you can track that. In a product where any laptop may come back after a month offline, you never know for sure.
- Keep a slim tombstone. Yjs, with garbage collection on (the default,
doc.gc = true), throws away the content of deleted items and keeps only their ids and length, merged into compact ranges. The structure needed for merging survives; the text does not. - Keep everything. Automerge stores the full change history by default, so you can view or diff any past version. Its columnar binary format compresses that history well, but memory use is higher than a design that forgets.
- Compact at a checkpoint. A server can rewrite the document from its current visible content, starting a fresh history. Any client holding old offline edits can no longer merge them as CRDT updates, so the app needs a fallback, such as re-applying them as a diff or showing them as a conflict.
How much bigger is a CRDT document?
Do the naive math first, as a rough estimate. If every character is a JavaScript object with an id (a number and a string), an origin, the character, and a flag, each one costs on the order of 100 bytes in a JS engine once object headers and pointers are counted. The real editing trace described below inserts about 182,000 characters over its life, so one object per character, tombstones included, comes to around 18 MB. Early CRDT implementations really did look like that.
Modern libraries cut this down with one main trick: run-length merging. When one person types hello world in one go, the ids are consecutive (5A, 6A, 7A...) and each origin is the previous letter. Yjs stores that run as one item holding the string, with one id and one origin. Most real typing is long runs by one author, so the number of items is far smaller than the number of characters.
The public crdt-benchmarks repository by Yjs's author replays a real editing trace: the history of writing an academic paper, about 260,000 single-character inserts and deletes that end in about 105,000 characters. In the results published there (Yjs 13.6, Automerge 2.1), Yjs encodes the whole history in roughly 160 KB, about 1.5 times the final text, and Automerge in roughly 130 KB.
In memory the cost is higher: about 3 MB for Yjs. Treat these as orders of magnitude, since they change from version to version and depend on how the text was typed.
Check your understanding · Exercise 6
Why does a text CRDT keep a tombstone for a deleted character? Pick one.
Yjs and Automerge in practice
You will almost never write a sequence CRDT yourself. Two open-source libraries cover most frontend needs, and they make different bets. Knowing both, and why a product might pick one, is what interviewers look for when CRDTs come up.
Yjs: shared types and providers
Yjs is a JavaScript library built around a Y.Doc that holds named shared types: Y.Text for text, Y.Array for lists, Y.Map for objects, and Y.XmlFragment for rich-text trees. You read and change them like normal data, and Yjs records each change as a small binary update. It is small (about 20 KB gzipped) and fast, and it has a large ecosystem.
- Editor bindings connect a shared type to an editor so that typing creates updates and remote updates move the editor:
y-prosemirror(used by Tiptap),y-codemirror.next,y-monaco,y-quill, and Lexical's collaboration plugin. - Providers move updates:
y-websocketthrough a server,y-webrtcdirectly between browsers,y-indexeddbinto local storage so the document survives a reload offline. Several providers can run on one document at once. - Awareness is a separate, small protocol for presence: who is here, their name, color, and cursor. It is not stored in the document, and an entry disappears if a client goes quiet for about 30 seconds.
Y.UndoManagerundoes only your own changes, not your collaborator's, which is what users expect in a shared editor.
import * as Y from "yjs";
import { WebsocketProvider } from "y-websocket";
import { IndexeddbPersistence } from "y-indexeddb";
const doc = new Y.Doc();
// Local copy first: works offline, loads instantly on the next visit.
new IndexeddbPersistence("trip-42", doc);
// Live sync through a relay server when the network is there.
const ws = new WebsocketProvider("wss://sync.example.com", "trip-42", doc);
const notes = doc.getText("notes");
notes.observe(() => render(notes.toString()));
// A local edit: applied at once, synced whenever possible.
const addLine = (line: string) => notes.insert(notes.length, line + "\n");
addLine("Sunscreen");
ws.awareness.setLocalStateField("user", { name: "Asha", color: "#e91e63" });
Automerge: a JSON document with history
Automerge treats the whole document as one JSON-like object. You change it inside a function, and Automerge turns what you did into changes. It keeps the full history by default, which makes it natural to show past versions, diff two versions, or branch and merge like Git.
Its core is written in Rust and runs in the browser as WebAssembly. automerge-repo adds the parts an app needs around it: storage adapters (IndexedDB in the browser) and network adapters (WebSocket, BroadcastChannel between tabs).
import * as A from "@automerge/automerge";
let asha = A.from({ items: ["tent"] });
let ben = A.clone(asha);
asha = A.change(asha, (d) => { d.items.push("map"); });
ben = A.change(ben, (d) => { d.items.push("torch"); });
const merged = A.merge(asha, ben);
// merged.items has "tent" plus both "map" and "torch",
// in the same order on every replica.
| Question | Yjs | Automerge |
|---|---|---|
| Data model | Named shared types inside a doc | One JSON-like document |
| History | Forgets deleted content by default (GC) | Keeps full history by default |
| Core | JavaScript (ports exist in Rust and other languages) | Rust, compiled to WebAssembly for the web |
| Ecosystem | Many editor bindings and hosted backends | automerge-repo for storage and sync |
| Pick it when | Live rich-text or code editing with many editors to choose from | Local-first apps where history, branching, and JSON data matter |
The offline merge, step by step
This is the case CRDTs were built for. Ben edits on a train for two hours. Every keystroke is applied to his local Y.Doc and saved to IndexedDB, so a crash or a closed tab loses nothing. When the train reaches signal, the provider reconnects and runs a two-step sync.
- Each side sends its state vector: for each client id, how many of that client's changes it has, like
{ A: 120, B: 88 }. It is a few bytes per writer. - Each side compares the other's state vector with its own and sends back exactly the updates the other lacks (
Y.encodeStateAsUpdate(doc, theirVector)). Two hours of typing is usually tens of kilobytes, not the whole document. - Each side applies what it received. The CRDT merges it; no transform, no conflict screen. From now on, live updates flow one by one.
Y.encodeStateVector and Y.encodeStateAsUpdate(doc, theirVector).You still want a server
"No central order" does not mean "no server". Most CRDT products run one with easier jobs: relaying updates between people who are never online at the same time, storing a copy for new devices, checking who may read and write, and compacting history. Hocuspocus (from the Tiptap team) and the y-websocket server are common open-source choices for Yjs.
In real products
- JupyterLab's real-time collaboration extension (
jupyter-collaboration) uses Yjs for shared notebooks. - Tiptap and many ProseMirror-based editors use Yjs through
y-prosemirrorfor collaborative rich text. - Zed, the code editor, built its buffers on a CRDT so that multiplayer editing is part of the core.
- Figma describes its multiplayer system as inspired by CRDTs but with a central server as the authority: each property of each object is last-writer-wins, and list order uses fractional indexing.
- Google Docs uses OT, not CRDTs: a reminder that both work at huge scale.
Check your understanding · Exercise 7
Ben reconnects after two hours offline. His state vector is { A: 120, B: 300 }; the server's is { A: 150, B: 88 }. What is sent? Select all that apply.
What goes wrong in production
A CRDT guarantees one thing: replicas that saw the same changes hold the same state. Everything else is still your problem. These are the failures teams actually hit, roughly in the order they hit them.
Merges that are consistent but wrong
A task board allows at most one assignee. Offline, Asha assigns the task to Chen and Ben assigns it to Dana. If assignee is an LWW-Register, one name silently wins. If it is a set, the merged task has two assignees, breaking the rule.
Both outcomes are perfectly convergent. Neither is what the product wanted.
CRDTs merge data, not rules. Invariants that span values (a budget that must not go negative, a seat only one person can book, a unique username) need a server that may say no, a data design that can't break the rule, or a check after the merge that asks a person.
Moving things
Dragging a card to another column looks like one action, but a basic list CRDT only knows insert and delete. If two people move the same card at the same time, "delete here, insert there" twice gives two copies of the card.
In a tree (folders, layers, an outline), concurrent moves can even create a cycle: A moved into B while B moved into A. Libraries and papers offer dedicated move operations (Kleppmann and others published a move algorithm for replicated trees in 2021), but many apps sidestep the problem: they store the parent as an LWW field per item and the order as a fractional index, so a move is just two field writes.
Rich text formatting
Bold, links, and comments span ranges. When Asha bolds a sentence and Ben types at its edge, should his letters be bold? Usually yes for bold, no for a link.
Ink and Switch's Peritext research studies these rules, and Automerge's rich-text marks (added in Automerge 2.2) build on it with an expand setting per mark. With Yjs, the editor binding and schema decide, so test the edges your users will hit.
Reused client ids
Every scheme in this lesson assumes ids are unique. If two tabs share one id, for example because the app saved a fixed client or actor id in localStorage, both will create items like 57A with different content, and replicas can diverge or reject updates.
Let the library pick a fresh id for each document instance and load saved state into it, which is what the providers do. Yjs even switches to a new client id when it sees its own id in a remote update, but edits made before that can already clash.
Trust and security
- Any client can write anything. An update can delete the whole document or add a megabyte of junk. The server must check that the sender may write this document, and should cap update sizes and rates.
- Validation is hard after the fact. The server must apply an update to its own copy to inspect it, and undoing one later is awkward because others may build on it.
- End-to-end encryption fits well. The server only relays and stores updates, so clients can encrypt them; you lose server-side search and validation.
- Deleted is not erased. With history kept (Automerge, or Yjs with GC off), text a user deleted, such as a pasted password, is still in the document. Plan a way to purge it.
Changing the data shape
A CRDT document lives on many devices, some offline with old app versions, so you can't migrate it in one go. If version 2 renames title to name, an old client will keep writing title. Treat the document format like a public API: add fields rather than rename them, and store a schema version.
Check your understanding · Exercise 8
Two users drag the same card to different columns while offline. The board stores each column as a list CRDT, and a move is delete plus insert. What happens after sync? Select all that apply.
When to pick a CRDT over OT
Both approaches power real products at scale, and the honest answer in an interview is "it depends on these three or four things", followed by what they are. The differences come from one design choice: OT keeps a single authoritative order on a server; a CRDT makes order irrelevant.
Side by side
| Question | OT (central server) | CRDT |
|---|---|---|
| Who decides order? | The server, one document at a time | Nobody; the data structure makes order irrelevant |
| Offline for hours | Possible, but a long queue of ops must be transformed against everything that happened | Natural: merge is the same at any distance |
| Peer-to-peer, no server | Very hard (needs extra transform properties) | Works; any transport will do |
| Data on the wire | Small ops with positions | Small updates with ids, plus a state vector on reconnect |
| Memory and storage | Just the document plus a recent op log | Document plus ids and tombstones; modern libraries keep this to small multiples |
| Server-side rules | Easy: the server sees every op in order and can reject one | Harder: changes are accepted locally first |
| Build it yourself? | Hard to get right; transform functions for every op pair | Don't; use Yjs or Automerge |
| Known at scale | Google Docs | JupyterLab, Zed, many Yjs-based editors |
Decision Which sync model should a collaborative frontend use?
What we pick: For online-only text editing with an existing server, OT is a fine and proven choice. For offline-first, peer-to-peer, or multi-region editing, or when you want an off-the-shelf library, choose a CRDT, usually Yjs. For structured objects like shapes and cards, per-field LWW is often enough, with a CRDT only for the text inside them.
Most products mix them
Real systems rarely pick one model for everything. A whiteboard might keep shape positions as LWW registers, the text inside sticky notes as Y.Text, the list of comments in a normal database behind a REST API, and cursors in an ephemeral presence channel. Saying this in an interview shows you see the data, not just the buzzword.
Check your understanding · Exercise 9
Which requirements push you toward a CRDT rather than OT? Select all that apply.
Using CRDTs in a system design interview
CRDTs come up in any design with shared editing: a collaborative editor, a whiteboard, a shared to-do list, a notes app that works offline. They also come up as a follow-up: "what if the user is offline?" or "what if there's no single server?". You don't need to derive YATA on a whiteboard. You need to pick the right tool, explain why it converges, and know what it costs.
What to draw
- The replicas. Each browser tab holds a full
Y.Doc(or Automerge doc), backed by IndexedDB. Edits apply locally first, so typing never waits for the network. - The sync path. A WebSocket to a relay server that fans updates out to other clients in the same document room and persists them (snapshot plus recent updates) in storage.
- Reconnect. State vector exchange, then only the missing updates.
- Presence. A separate ephemeral channel (awareness) for cursors and who is online, never stored in the document.
- The data shape. Which parts are text (sequence CRDT), which are fields (registers or maps), and what stays in a normal database behind an API.
Then say what it costs, before the interviewer asks. Every character carries an id, deleted text leaves tombstones, and documents only grow, so you split the workspace into one document per page or board and compact on the server. Name one thing the CRDT will not decide for you, such as two people assigning the same task, and how the product handles it. That short paragraph is usually what separates a mid-level answer from a senior one.
How deep to go, by level
| Level | What a strong answer includes |
|---|---|
| Junior | Names CRDTs and OT as the two ways to merge concurrent edits; says local-first edits, sync later, and that a library like Yjs does the merging. |
| Mid-level | Explains unique ids and why merge order doesn't matter; describes state vectors on reconnect, IndexedDB persistence, and separate presence; mentions tombstones and document size. |
| Senior | Chooses between CRDT, OT, and per-field LWW per kind of data; plans document splitting, compaction, auth and validation on the relay, schema evolution for offline clients, and the invariants a CRDT can't keep. |
Check your understanding · Exercise 10
An interviewer asks how your Yjs-based editor handles a user who reloads the page while offline. What belongs in a good answer? Select all that apply.
Summary
- A CRDT lets every replica edit locally, offline, without coordination, and guarantees that replicas that saw the same changes hold the same state.
- The core trick is unique ids per change plus a merge that is commutative, associative, and idempotent, so delivery order and duplicates don't matter.
- G-Counters give each replica its own slot and merge with max; LWW-Registers keep the value with the largest logical timestamp and break ties by replica id.
- Sequence CRDTs (RGA, YATA) give each character an id and an origin and order concurrent inserts with a fixed tie-break; deletes leave tombstones.
- Real libraries send small mergeable updates live and exchange state vectors or heads on reconnect, so offline merges cost what changed, not the document size.
- Metadata is the price: modern libraries keep encoded size close to the text through run-length merging and garbage collection, but memory and history still need a plan.
- Pick a CRDT (usually Yjs or Automerge) for offline-first, peer-to-peer, or multi-region editing; OT for online editing around a central server; per-field LWW for simple structured objects.
- CRDTs merge data, not product rules: design fields by asking what should happen when two people change them at once.
In the interview
Questions interviewers ask about this. Answer each out loud first, then compare.
Question 1
How can two replicas merge without a server deciding the order?
Every change gets a globally unique id: a counter plus the replica's id. Replicas exchange sets of changes, and the visible value is computed from that set by a fixed rule.
The merge is commutative, associative, and idempotent, like set union, so order, grouping, and duplicate delivery don't change the result. Same changes in, same state out: strong eventual consistency.
Question 2
Walk me through how a sequence CRDT places two characters typed at the same spot.
Each character is an item with an id like 3A and an origin, the id of the character it was typed after. Inserts refer to origins, never to positions.
If two items share an origin, a fixed tie-break orders them, for example larger id closer to the origin, comparing the counter first and the replica id second. Every replica applies the same rule, so all end with the same text, such as hi?!.
Yjs's YATA also stores a right origin, which bounds where an item can land; Automerge's lists follow RGA.
Question 3
Why are deleted characters kept, and how do you stop documents growing forever?
A concurrent insert may use a deleted character as its origin, so the item stays as a tombstone to keep its place.
Yjs garbage-collects deleted content and keeps only compact id ranges; run-length merging stores a typed run as one item. Beyond that: split workspaces into small documents, keep high-frequency data out of the CRDT, and compact on the server at checkpoints, with a fallback for clients holding very old offline edits.
Question 4
Your team is choosing between OT and a CRDT for a notes app. What do you ask and what do you pick?
Ask: do users edit offline for long periods? Is there always one server, or peer-to-peer or multi-region sync? Do edits need server-side approval? How large and long-lived are documents?
Long offline sessions or peer-to-peer point to a CRDT library like Yjs, with a relay server for persistence and auth. Online-only editing with an existing central server and strict server rules fits OT. Structured fields often only need per-field LWW.
Question 5
What can a CRDT not guarantee?
It guarantees convergence, not intent. Invariants across values (one assignee, a non-negative balance, unique names) can break after a merge, and moves done as delete plus insert can duplicate items.
Handle these with data design (LWW fields for parent and order), server checks for rules that need a referee, or detection after merge with a human in the loop.
Practice it
These design problems lean on crdts.
References
- Yjs documentation Shared types, providers, awareness, and the document update format.
- crdt-benchmarks (Yjs, Automerge, and others) Size, memory, and speed on synthetic and real editing traces.
- Automerge documentation The JSON document model, history, and automerge-repo.
- crdt.tech A hub of papers, talks, and implementations maintained by CRDT researchers.
- How Figma's multiplayer technology works A CRDT-inspired, server-authoritative design for a canvas.
- Local-first software (Ink and Switch) Why apps should keep data on the device, and where CRDTs fit.
Read next
- Real-time collaborationHow several people edit one document at the same time: each person sees their own typing instantly, a server puts everyone's changes in one order, and every copy ends up the same.
- Operational transformation (OT)A way to merge edits made at the same time: each incoming edit is rewritten, or transformed, to account for the edits it missed, so every copy ends with the same text. Google Docs is built on it.
- Conflict resolution strategiesWhat to do when two people change the same data: from last write wins per field, to version checks with
If-Match, to three-way merges and merge screens, chosen separately for each kind of data. - Presence and live cursorsShowing who else is in a shared document and where they are pointing, in near real time: a stream of small, short-lived updates that must stay cheap, smooth, and honest about who has left.
- Offline-first designA way of building apps where the device's own copy of the data is what the UI reads and writes, and a sync engine reconciles it with the server in the background, so the app stays fast and usable on a bad connection or none at all.
- WebSocketsOne long-lived connection, opened by an HTTP handshake, on which browser and server can each send a message at any moment. The usual pick for chat, multiplayer, and collaboration, and the one where you own the protocol, reconnects, and scaling.