Distributed systems
Part 4 of 6 · CRDTsSequences & Collaborative Text — RGA, LSEQ, Yjs/Automerge
Sequence CRDTs give each insert a stable identity so two people typing at the same place converge. RGA, LSEQ, Yjs, and Automerge are that idea with different identifiers. A last-writer-wins string is not.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
Why does a last-writer-wins string fail for collaborative editing?
Answer
The whole document is one value. One replica's string replaces the other. The loser's keystrokes are gone even though both users typed them.
L2
What problem do unique insert ids solve?
Answer
Two inserts after the same character need one total order that every replica computes locally. The ids are that order. The characters are not compared as text.
L3
What is a tombstone in RGA?
Answer
A deleted element kept so concurrent inserts still have a predecessor. The walk skips it when building the visible string. It stays until causal stability says nobody needs the anchor.
L4
How do fractional indexes fail?
Answer
Always inserting in the same gap lengthens the key. A naive midpoint that appends a hash is not even guaranteed to sort between its neighbors. LSEQ allocates to slow that growth, and a replica salt keeps keys unique.
L5
Yjs or Automerge?
Answer
Yjs is the usual choice for real-time editor bindings and a compact update format. Automerge is the usual choice for a local-first document API. Evaluate the runtime you have. Do not hand-roll either.
L6
How do you persist the document?
Answer
A snapshot of the CRDT state plus the update log after that snapshot. Reload the snapshot and apply the log. Store the binary encoding, not only the plain string, or you cannot merge a later update.
L7
When do you refuse a sequence CRDT?
Answer
One writer and a row version are enough. A legal signature wants a linearizable commit of one frozen version. A binary blob wants content-addressed chunks. A working OT server does not need a rewrite.
Failure modes
Last-writer-wins on the document body
Two offline paragraphs become one paragraph. The metrics show a successful save.
Deleting the anchor
A garbage collector drops a tombstone before every replica has seen it. A concurrent insert no longer has a predecessor and lands in the wrong place, or the replicas disagree.
Identifier growth in one gap
Every new character splits the same pair of neighbors. Fractional keys get longer on every insert. The document is short and the metadata is not.
Interleaving that converged and still looks wrong
Both replicas agree on Hi!?, or on a scrambled word, because the id order is not the order a human expected. Convergence is not editing quality.
Misconceptions
Operational transformation is obsolete.
OT is a valid design when you control a central server and already have a correct transformer. CRDTs are how you get offline merge without that server. Plenty of products still ship OT.
The plain text is the replicated state.
The ids, tombstones, and parent links are the state. The string is a view. Persisting only the string throws away the next merge.
A CRDT document is the business event log.
Edits converge. A publish or a charge is a separate fact, emitted once from a linearizable step, usually through an outbox.
Interviewer traps
I will implement RGA in the interview and also YATA.
Draw one insert, one concurrent sibling, and a tombstone. Name the library you would actually depend on.
We will put the document through Raft so it is correct.
A Raft log can freeze a published version. It is a poor home for every keystroke, and it does not replace ids if clients edit offline.
Design scenario
Same prompt for every reader.
Requirements
Concurrent keystrokes in the draft both survive. The published export is one immutable version. The support form must not gain CRDT metadata it does not need.
Traffic / scale
A draft is a few kilobytes and a handful of editors. Publishes are rare compared with keystrokes.
Latency
A local keystroke paints immediately. Remote carets can lag by a short sync interval.
Consistency
The draft is strongly eventually consistent. The published version is an immutable write in a linearizable store.
Availability
Editors keep typing through a partition. Publish waits until the chosen snapshot can be committed.
Failure assumptions
- Both editors insert at the end of the same sentence while disconnected.
- One editor deletes a character the other is inserting beside.
- A client reloads from storage that saved only the plain string.
Constraints
- Do not replicate the draft as one last-writer-wins string.
- Do not send every keystroke through a Raft quorum.
Prompt
A notes app lets two people edit the same draft online and offline. Publishing freezes a version customers can export. A support form is edited by one agent at a time.
API
Which call edits the draft, and which call publishes a snapshot?
Data
What is stored besides the visible characters?
Architecture
Where does the business event fire, relative to the CRDT sync stream?
Two people type at the end of Hi
Prefer
One id per insert
Alice inserts ! and Bob inserts ? after the same character. Both ids exist. Every replica sorts those siblings the same way.
- The visible string is a walk over the ids.
- Deleting a character keeps the id so a concurrent neighbor still has a parent.
- A library owns the interleaving rules you do not want to invent.
Alternative
One string, last writer wins
Whoever syncs last replaces Hi! with Hi? or the reverse. One person watches their character disappear.
- The timestamp can be perfect and the loser is still gone.
- Offline editing makes the collision the common case.
- A central OT server can also work, if you already have a correct one.
From a string to a walk
The replicated state is the nodes. The characters on screen are the nodes that are not tombstoned, in id order under each parent.
- 1
Reject the whole-string register
If the unit of merge is the document, one editor wins. Split the document into inserts with their own identities. - 2
Name the predecessor
Each insert records the id it was typed after. Two inserts with the same predecessor are siblings, not a conflict to delete. - 3
Sort siblings by id
A counter and an actor id are enough for a teaching order. Both replicas use the same comparison, so the strings match after both inserts arrive. - 4
Tombstone a delete
Skip the character in the walk. Keep the node until every replica has seen the delete, or a concurrent insert loses its anchor.
Why the string is the wrong state
Start from Hi. Alice inserts ! at the end. Bob inserts ? at the end. Both insertions name the same left neighbor. If the replicated value is the string, one of Hi! or Hi? replaces the other. If the replicated value is a set of inserts with ids, both characters exist, and a sort of those ids picks Hi!? or Hi?! everywhere. The interesting part is not which of those two strings you get. It is that you get one of them on every replica.
Flow
- 1
1 Insert after the same char
- next2 Each insert gets an id
- 2
2 Each insert gets an id
- next3 Sort those ids the same way
- 3
3 Sort those ids the same way
- next4 Both replicas show one string
- 4
4 Both replicas show one string
Lesson map
Sequences & Collaborative Text — RGA, LSEQ, Yjs/Automerge
Sequence CRDTs give each insert a stable identity so two people typing at the same place converge. RGA, LSEQ, Yjs, and Automerge are that idea with different identifiers. A last-writer-wins string is not.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a["1 Insert after the same char"] b["2 Each insert gets an id"] c["3 Sort those ids the same way"] d["4 Both replicas show one string"] a -->|1 Insert after the same char| b b -->|2 Each insert gets an id| c c -->|3 Sort those ids the same way| d
That converged order can still look wrong. Identifiers do not know that a human wanted Hi!? rather than a scramble of two words typed in the same gap. Interleaving is the hard part Kleppmann's talk is about. Convergence is the guarantee. Editing quality is extra work inside the library: block ids, character ranges, and exclusion rules. Do not claim a ten-line sorter has solved it.
RGA
The replicated growable array (Roh and colleagues) is the teaching model. Each element has a unique id and a link to the predecessor it was inserted after. Delete marks the element and leaves the id in place. Concurrent inserts after one node sort by id. The visible string is a depth-first walk that skips tombstones.
The model is clear enough to implement badly in an afternoon and slow enough, with enough tombstones, to hurt a large document. Garbage collection waits on causal stability. In an open set of clients that may return months later, that proof is the product problem, not a DELETE in a table. The sandbox is this walk. It is not a document engine.
Fractional indexes
LSEQ and Logoot-style designs assign each position a key that sorts between its neighbors. Between a and c you want a key that compares greater than a and less than c. A careful allocator uses a base, a strategy that avoids always splitting the same gap, and a replica-specific salt so two clients do not pick the same key.
A one-line "append a digit and a hash" does not do that. It often fails to land between the neighbors, and the hash is not a stable order. The failure mode that survives a correct allocator is growth: if every insert splits one hot gap, the keys get longer. That is why production allocators jitter the depth instead of always taking the midpoint. Prefer the library. Use the idea to explain the metadata, not as the code you ship.
Yjs and Automerge
| Yjs | Automerge | |
|---|---|---|
| Algorithm | YATA, a tree-shaped sequence | A list CRDT in the RGA lineage, evolved in the library |
| Editors | Bindings for ProseMirror, Monaco, CodeMirror | A document API aimed at local-first apps |
| Network | Providers: WebSocket, WebRTC, and others | Sync over automerge-repo adapters |
| Encoding | Compact binary updates | Columnar document bytes |
| Other types | Map, array, text, XML | Maps, lists, text, counters |
| Typical fit | Real-time editing in the browser | Offline-first documents with a richer merge API |
Both exist so a team does not hand-roll the identifier math. Operational transformation remains reasonable when a central server already owns the session and the transformer is known to be correct. It is a painful offline story. For "design a collaborative editor," a strong answer is Yjs or Automerge, a provider, and snapshots. Mentioning that OT's correctness is the hard part is enough empathy. Do not derive inclusion transformation on the whiteboard.
Figma is the interview reminder that products mix techniques. A real editor can use a CRDT for some structures and a central authority for others. Hybrid is not a dodge.
What you store
Persist a snapshot of the CRDT and the update log after it. On load, apply the snapshot and then the log. If you store only the plain string, the next remote update has nothing to merge with. Binary encodings from the library are the snapshot format. The dissemination page covers how large those updates get and when you compact them.
A publish step is different from sync. Freeze one version into a linearizable store, then emit doc.published once. That event belongs on the event-driven architecture page. The CRDT stream is not the business log. Two replicas applying the same edit must not each send the email.
OT, CRDT, and a Raft buffer
| Approach | Who coordinates | How it converges | Offline |
|---|---|---|---|
| Classic OT | Usually a central server | Transform functions | Painful |
| Sequence CRDT | Peers or a relay that does not decide order | Ids and a deterministic sort | Natural |
| Server buffer plus Raft | A leader | One log order | Queue locally, then rebase on reconnect |
Use the third row when the product is "one ordered buffer and clients are online." Use the second when the product is "edit offline, merge later." Raft is the log in the third row. It is not a character merge.
When not to use one
- One writer. A ticket description edited by one agent is a row and a version. MVCC already covers that snapshot. CRDT metadata buys nothing.
- The signed version must be one commit. Collaborate in the CRDT. Commit the export through a database transaction. The draft converging is not the signature.
- An OT stack already works. Do not rewrite it to collect a CRDT.
- Bytes, not characters. Content-addressed chunks and a sync algorithm beat a CRDT per byte.
Sandbox
Both snippets are the RGA-flavored walk: nodes hang off a predecessor, siblings sort by (counter, actor), and a tombstone is skipped without dropping its children. They are the interview model. They are not Yjs.
ProblemThe document is H then i. Alice inserts ! after i and Bob inserts ? after i. Build the string from both arrival orders, then tombstone i and walk again.
ExpectedBoth orders produce Hi!?. After i is tombstoned the anchors remain, so the string is H!?.
Edge cases
- Sibling order does not depend on list order.
- A tombstone is not removed from the parent map.
- Test: arrival order does not matter
forward == reverse == 'Hi!?' - Test: tombstone keeps the anchor
deleted == 'H!?'
Press Run. Snippets must be self-contained — no network, files, or native modules.
ProblemSort siblings by counter, then actor. Confirm both append orders match, and that a deleted predecessor still hosts its children.
ExpectedHi!? both ways, and H!? when i is tombstoned.
- Test: both orders match
forward === reverse && forward === 'Hi!?' - Test: children of a tombstone remain
deleted === 'H!?'
Press Run. Snippets must be self-contained — no network, files, or native modules.
Actor A sorts before actor B at the same counter, so the teaching string is Hi!?. Swap the actor ids and the string changes. The point of the exercise is that both replicas change with it.
Interview Q&A
Why not store the document in a last-writer-wins register?
Answer
Because the value is the entire string. Two concurrent edits produce two strings, and the merge keeps one. The other user's characters are not a conflict you can present. They are gone. Sequence CRDTs merge at the insert, which is the granularity people actually type.
What are tombstones in RGA?
Answer
Deleted elements that stay in the structure so a concurrent insert still knows which id it followed. The visible walk skips them. You may drop a tombstone only after every replica that might still reference it has seen the delete. Until then the memory is the algorithm, not a leak you compact on a whim.
Yjs or Automerge, in one line?
Answer
Yjs if the problem is a real-time editor and you want the existing bindings and update format. Automerge if the problem is a local-first document and you want that data model. Measure your runtime. Do not pick from the logo.
How do you persist CRDT text?
Answer
Snapshot the internal state, append updates after the snapshot, and on load apply them in that order. Keep the library's binary form. A row that contains only the plain text cannot accept a later update without guessing.
How does this interact with events and CQRS?
Answer
Sync converges the draft. Publish, export, or charge is a decision you record once. Write that version to a linearizable store and emit the domain event through an outbox. The event-driven architecture page is the outbox. This page stops at "the CRDT stream is not that log."
What is wrong with a hand-rolled fractional index?
Answer
The key must sort strictly between its neighbors, stay unique across replicas, and not grow without a bound when inserts pile into one gap. Appending a constant digit or a hash fails the first requirement. LSEQ is an allocation strategy for the growth problem. It is still a bad weekend project compared with a maintained library.
When is operational transformation the better answer?
Answer
When a server already serializes the session, the transformer is known-good, and offline merge is not the requirement. CRDTs remove the central transform at the cost of identifiers and tombstones. Replacing a working OT server is a migration, not a design-review trophy.
When do you refuse a sequence CRDT entirely?
Answer
Single-writer forms, binary blobs, and any "submit" that must be one committed version. Collaborate in the CRDT if you need to. Sign, bill, or file the result through an ordinary transaction. Raft can order that commit. It should not order the keystrokes.
Pitfalls
- Replicating the plain string.
- Dropping tombstones because a document "looks small."
- Treating a converged interleaving as proof the algorithm feels right.
- Persisting text and throwing away ids.
- Emitting a business event from every replica that applied an edit.
- Writing a new sequence CRDT when Yjs or Automerge already fits.
Write Hi as two nodes. Add ! and ? after i with different actor ids. Sort by hand. Then mark i deleted and write the visible string again without removing the nodes that point at it.
Go Deeper
- Yjs for YATA, providers, and the update encoding you would actually store.
- Automerge and the local-first essay for the offline document model.
- Kleppmann, CRDTs: The Hard Parts (video), especially interleaving.
Next: State-based vs op-based vs delta-CRDTs and compaction.