Collaborative editing

A community theater writes its new play in a browser-based editor. Ines, the director, and Kofi, a writer, both have the scene description The storm hits. open. At the same moment, Ines deletes the first 4 characters ("The ") and Kofi types "night " at position 4, just before "storm". Lena, the third writer, is revising Act 3 on a train with no signal.

Each editor applies its own change at once, so typing never waits for the network, and then sends the change to the others. If each copy simply replays the other person's change at the same position, the copies split:

The two copies now disagree, and nothing will bring them back together. The goal of collaborative editing is that all copies converge: once everyone has received every change, everyone sees the same document, and that document keeps what each person meant to do.

Two older fixes fall short. Comparing whole versions and guessing a merge can't tell what each person intended: if one person bolds "brown fox" while another replaces "fox" with "dog", several merges look equally valid. Locking a paragraph to one editor blocks the collaboration the product exists for, and two people can still start typing before either sees the other's lock. The working answers are operational transformation and sequence CRDTs.

Operational transformation (OT) rewrites an incoming change so that it applies to the document as the receiver has it. Ines's copy lost 4 characters before Kofi's insertion point, so Kofi's "insert at 4" becomes "insert at 0" there, and both copies read night storm hits. Google Docs' editor works this way: every edit is an insert, a delete or a style change, and the document is stored as the log of those changes.

A transform is only half the system; something must also decide the order. In Google Docs a central server plays that role, numbering every change it accepts as the next revision:

The client side has its own rules. Each Google Docs client tracks the last revision it has seen, the local changes not yet sent, and the changes sent but not yet acknowledged, and it never has more than one change in flight: new typing waits in the pending list until the acknowledgment arrives. Incoming changes are transformed against the pending ones, so the local view stays correct while the user keeps typing.

OT has a reputation for being hard, for a concrete reason. The transform must handle every pair of change types correctly, and with structured documents (tables, lists, nested blocks) a transform that always converges becomes very hard to define. A long list of published OT algorithms were later shown to be incorrect. Without a central server, OT generally also needs to keep records of deleted text, which brings it close to the next technique.

A sequence CRDT stops describing edits by position (CRDTs: data types that always merge covers the family). Every inserted character gets a permanent id made of the inserting client's id and a counter, and an insertion names the characters it goes between. Kofi's edit then means the same thing on every copy, however much the text around it has shifted:

Because the space Kofi anchored to still exists as a hidden character, Kofi's insertion lands in the right place on Ines's copy even though Ines deleted that space. Hidden deleted characters are called tombstones. When two people insert at exactly the same spot, every copy must order the insertions the same way; sorting by a logical timestamp and then by client id is one rule that does it (Time, clocks & ordering).

The result is that changes need no transform and no central order: they can arrive in any order, or twice, and copies still converge. Yjs, a widely used CRDT library, states that its document updates are commutative, associative and idempotent. The trade-offs against OT:

The extra data is smaller than it sounds. Yjs stores a run of characters typed in order by one client as a single item, and records deletions as ranges. On a real editing trace with about 182,000 inserted and 77,000 deleted characters, the record of deletions took 4.5 KB. With garbage collection on, deleted content is discarded and only its length is kept.

Most of a document isn't running text. The play editor also has scenes in an order, lighting cues with times, and formatting. Figma, a design tool, models its documents as objects with properties, and its server keeps the last value any client sent for each property of each object. Two people changing different properties, or the same property on different objects, never conflict at all.

Last write wins is cheap but blunt. Figma's own example: if a text value "B" is changed to "AB" by one person and to "BC" by another, the result is one of them and never "ABC". That is fine for a cue time and wrong for a speech, which is why the script text needs a real text merge.

Fractional indexing orders items without renumbering: each item has a position between 0 and 1, and an item placed between two others gets a value between theirs, such as (0.5 + 0.75) ÷ 2 = 0.625. Formatting is a range that must stretch: Google Docs transforms "bold 10 to 20" against "insert ABC at 15" into "bold 10 to 23", so text typed inside a bold span becomes bold.

Collaborators need to see who is where. Presence, meaning each person's cursor, selection, name and color, is shared live but not saved with the document. Yjs keeps it in a separate small structure: each user sets their own state, and when a user goes offline their state is removed and everyone else is told (Presence & push notifications).

A cursor can't be stored as a number. Kofi's cursor at position 10 points at the wrong letter once Ines deletes 4 characters before it. Positions are anchored to characters instead: Yjs's relative positions attach to the character after the cursor and stay with it as text changes around it, and all copies resolve them to the same place once synced. With plain offsets that guarantee isn't possible, even in an OT system whose documents converge. Comments on a range of text need the same anchoring.

Undo is per person. When Kofi presses undo, Kofi's own typing should disappear, not Ines's deletion, so each participant needs their own undo history. Yjs's undo manager tracks only local changes by default, and undoing an old change means first transforming it past everything that happened since:

Redo needs the same care. A useful test: if you undo several times, copy something, and redo back to the present, the document should be exactly as it was. A naive redo that "puts back what I did" can overwrite what others did in the meantime.

Most collaborative products route each document through a central server that orchestrates its changes. Figma runs a separate process for each open document, holds the document in memory, and connects everyone editing it to that process. If two processes each held the same document, people connected to each would see different versions: a split brain (Failure detection & split brain).

How the owner saves decides how much work a crash loses. Figma first wrote the whole file every 30 to 60 seconds, so a crash could lose up to 60 seconds of edits, and every deploy closed all files at once and caused a burst of writes. Adding a log of incremental changes, each with a sequence number, changed the numbers:

Recovery reads the latest snapshot, then every log entry with a higher sequence number. Clients send updates up to 30 times a second, so the owner batches them before writing. Ownership has to be enforced, not assumed: Figma records which process owns each file and makes every log write conditional on that record, so a second process can't append a conflicting history (Distributed locks).

Lena edits Act 3 for two hours on the train. When the connection returns, the editor must bring the copies together (Offline-first & optimistic UI). Figma's client downloads a fresh copy of the document, reapplies the offline edits on top of it, and resumes syncing. A CRDT client can instead send a state vector, how many changes it has from each client, and receive only the changes it lacks, while sending its own in return.

The merge always succeeds, but success isn't the same as sense. If Kofi rewrote the same speech while Lena was away, each deletion hides only the text its author could see, and both new versions survive side by side in one paragraph. Nothing is lost, which is the point, but the play now has two speeches. A useful habit is to flag long offline merges that touched the same paragraph so a person can review them.