Collaborative text editing: OT vs CRDTs

A position is not an address

Line 3 of tomorrow's release note reads Fixed a crash on login., and two people have it open in a shared editor. Noor, from support, types rare in front of crash. Felix, who fixed the bug, adds with SSO before the full stop. Each editor applies its own user's keystrokes at once, since waiting for a server on every key would feel broken, and sends the change as an operation: insert(8, "rare ") from Noor, insert(22, " with SSO") from Felix, positions counted from 0.

1. Noor's editor applies her insert: Fixed a rare crash on login. The full stop moves from position 22 to 27.
2. Felix's editor applies his: Fixed a crash on login with SSO.
3. Felix's editor receives insert(8, "rare "). Nothing before position 8 has changed on his screen, so the result is right: Fixed a rare crash on login with SSO.
4. Noor's editor receives insert(22, " with SSO") and applies it at position 22 of her text, now the l of login: Fixed a rare crash on with SSOlogin.

Both operations were correct when they were made. A position means something only in the text it was computed against: Felix's 22 meant "before the full stop" in a text without Noor's five characters. Conflict resolution for concurrent writes covers how replicas detect and merge concurrent writes to a value; a text adds a problem of its own, because every edit moves the positions the others are addressed by.

Rewriting an edit against the one it missed

Before applying Felix's insert, Noor's editor can ask what it would have been had Felix seen her five characters. Her insert landed at 8, before his 22, so his moves right by 5, to insert(27, " with SSO"), and her text matches his. On Felix's side, Noor's 8 needs no change. Rewriting an operation against a concurrent one it did not see is operational transformation (OT). With correct rules, both copies converge to the same text, and here each edit keeps its intent: rare stays before crash, with SSO stays at the end.

The shift is one case of a transformation function, which adjusts one of two concurrent operations so it can be applied after the other. Every pair of operation types needs one. Two deletes of the same word must remove it once, not the next word too. Two inserts at one position need a tie-breaker every editor applies alike, such as comparing user ids. Add formatting, a bold over a range someone else is deleting, and the pairs multiply. Each function is short, and several published OT algorithms were later shown to diverge in cases their authors had not checked.

One server, one order

Much of that difficulty comes from operations meeting in different orders. When three editors exchange operations directly, each may transform the same edits along a different path, and the functions must give the same text on every path, the condition the flawed algorithms broke. Most production OT systems avoid it with one server per document that picks a single order:

1. Noor's editor sends insert(8, "rare "), marked as written against revision 41, the latest it has.
2. Felix's editor sends insert(22, " with SSO"), also written against revision 41.
3. The server receives Noor's first and stores it as revision 42.
4. The server receives Felix's, sees it was written without revision 42, transforms it into insert(27, " with SSO") and stores that as revision 43.
5. The server sends each editor the revision the other one wrote, and confirms which revision its own edit became.
6. Felix's editor transforms revision 42 against his still unconfirmed insert, finds position 8 unaffected and applies it.

Noor's editor, its edit confirmed, applies revision 43 as sent. Every transformation now happens between one editor and the server, against one agreed history; Google Docs is the best-known editor built this way. The server merges edits rather than picking a winner, unlike an authoritative game server, which decides the world's state itself (Multiplayer game state: authoritative servers & tick rates). Getting every connection to a document onto its one owner is WebSockets at scale: gateways, routing & draining.

The price is the server. In this design, editors cannot sync with each other directly, and an editor that goes offline queues edits against an old revision, which the server transforms against everything stored since when it returns. That converges, but after a day apart the result can surprise both authors.

Name the neighbour, not the position

A sequence CRDT removes the server's job by taking positions out of operations. In the common design followed here, every character gets an identifier when it is typed, unique and never reused, typically the author's replica id plus a counter, and an insert names the character it goes after. Say Ines wrote the original sentence, so its characters are ines-1 to ines-23. Noor's rare becomes noor-1 to noor-5, placed after ines-8, the space before crash; Felix's with SSO becomes felix-1 to felix-9, placed after ines-22, the n that ends login; in each run, every later character names the one typed before it. Each replica places the other's characters next to the named neighbour, wherever it now sits, so the order of arrival stops mattering and nothing is transformed. Inserts after the same character are ordered by a fixed rule, the same on every replica; in the design followed here an insert made after seeing the other goes first, and concurrent ones are ordered by their identifiers, which puts rare before the c that already followed ines-8.

The identifiers are not free. A delete cannot drop a character, because a concurrent insert may name it as its neighbour, so the character stays, hidden, as a tombstone, and discarding it requires knowing that no operation naming it can still arrive, which for a sequence takes more than every replica having seen the delete. Each character also carries an identifier several times its own size. Convergence has the same condition as for the set CRDTs: two replicas agree once each has received every operation, and an insert after noor-3 waits until noor-3 has arrived. RGA (replicated growable array) is one well-studied sequence CRDT; Automerge's text grew out of it, and Yjs uses its own, YATA, and both libraries sync over any channel, peer to peer included. Some other algorithms, Logoot and LSEQ among them, give each character a sortable position instead, and can interleave two words typed at the same spot at the same moment, character by character.

With correct algorithms, both techniques make the copies agree, but agreement is not the text either author meant. In the CRDT described here, if Noor replaces crash with freeze while Felix, offline, deletes the whole sentence, both copies converge on freeze, the one word nobody deleted, because each delete removes only the characters its author had seen. In live editing people usually see such results as they happen and fix them; after a long offline session they are easier to miss. A collaborator's cursor is a position too, and drifts the same way; how cursors travel is Presence & ephemeral state.

Which one for your editor

If editors are online and you already run one server per document, OT is the established choice, and the stored document stays plain text plus a log of revisions. If edits must merge offline, or with no server in the path, a sequence CRDT fits, paid for in memory and metadata. Many CRDT deployments still put a server per document in front, to relay, persist and check permissions; the difference is whether the merge needs it to be correct.

The Collaborative Document Editor Challenge asks you to "Merge concurrent edits without losing changes using OT or CRDT", and that choice is the one to make visible. For OT, route every edit through the gateway to one service per document and write on that edge that it orders and transforms. For a CRDT, put the merge in the editor clients and write on the server's edge that it relays and persists. Then answer "Handle offline edits and reconcile on reconnect" in a note: what Noor's editor sends after an afternoon offline, and what happens to it. A canvas in Collaborative Whiteboard needs less, since separate shapes rarely fight over positions.