Two people have the same document open. One types a character at position 4. At the same
instant, the other deletes the word at position 2. Both edits are valid, both were made
against the same version, and neither person did anything wrong. Now both screens have to
end up showing exactly the same text. Watch one edit make the trip.
Type. A types a letter and sees it at once. The edit goes out tagged with the version A was looking at: insert "h" at position 4, made against version 41207.
There is no correct way to merge those two edits by sorting them or by timestamping them,
because the second edit's position number stopped being true the moment the first one was
applied. That is the whole question, and everything else here is plumbing around it.
after A's insert: "Xhello world"X0h1e2l3l4o5_6w7o8r9l10d11B's delete at 5: the otransformed to 6: the spacean insert in front of you moves you one to the right
A few words come up on every line of this page:
An operation (op for short) is one small edit: insert "h" at position 4, or delete one
character at position 6. Editors send operations, never the whole document.
A version is a counter on the document. Every applied operation bumps it by one, so
two people at version 41207 are looking at exactly the same text.
Converge means every screen ends up with exactly the same text, byte for byte.
To transform an operation is to rewrite its position so it still points at the spot its
author meant, after other edits have landed in front of it. This is operational
transformation, or OT, and it is the heart of the page.
The real Google Docs
This page builds a live collaborative editor like Google Docs: several people typing in one document and seeing each other's changes as they happen. The numbers below are interview assumptions, not Google's own. The core choice does match the real product: Google Docs merges edits made at the same time with operational transformation, the technique this page picks.
The scope question that matters is how strong the convergence guarantee has to be, and
almost nobody asks it. Each answer below settles a line in the design.
You ask
They say
What it settles
How many people edit one document at once?
Usually two or three. Occasionally fifty in a meeting.
A server per document is affordable. Fifty editors on one document is a small fan out (each edit copied out to 49 other people), which is a relief, because the hard part here is correctness and not scale.
Must every editor end up with an identical document?
Always, no exceptions.
The convergence requirement. Last write wins is off the table immediately, because two concurrent edits at different positions must both survive.
Does intent have to be preserved, or just the characters?
Intent. If I bold a word while you move it, the word stays bold and moves.
Operations described relative to the text rather than to positions in it. This is the answer that rules out the naive "send the whole document" design.
How fast does a keystroke have to appear locally?
Instantly. Nobody tolerates latency on their own typing.
Optimistic local application: assume the edit will be fine, show it now, and fix things up afterwards. The client edits its own copy first and finds out later whether the server agreed.
Can someone edit offline?
Yes, and it must merge when they reconnect.
Operations have to compose after an arbitrary delay, not just a few hundred milliseconds. This makes the merge algorithm the centre of the design rather than an edge case.
Do we need history and undo?
Full version history, and undo that only undoes my own edits.
An append only operation log as the source of truth, with the document as a materialised view of it. Per user undo is much harder than it sounds and is worth flagging as such.
A worked number first. A word is about five characters, so someone typing 60 words a minute
produces 300 characters a minute, which is 5 keystrokes, and so 5 operations, a second. Move
the sliders to see what that means for one document and for the whole fleet. (The method is in
back of the envelope.)
Traffic per document
5
60 wpm
500 thousand
Operations per editor60 wpm x 5 chars / 60 = 5.0 per second
Operations per document5.0 x 5 = 25 per second
Messages fanned out per document25 x 4 = 100 per second
Total operations across the fleet12,500,000 per second
Open connections500k docs x 5 = 2,500,000
25 ops/sec
per document, which is nothing, and that is the point
Per document this is a trivial workload. 25 operations a second means one process can comfortably own a document and serialise every edit to it (put them in one line, one at a time), which removes the entire distributed consensus problem. The scale challenge is 2,500,000 open connections, and connections are a known problem with known answers. The hard problem is that two of those 25 operations conflict.
The trap in these numbers
The low per document rate tempts people into batching keystrokes to reduce traffic.
Resist it, or at least be careful: batching changes what an operation means, and two
batched operations conflict in ways two single character operations do not. Debounce
the network send (wait a few tens of milliseconds, then send the small operations that built up in one message) if you must, but keep operations small
and let the transform handle them. Cleverness in the merge algorithm is where bugs live
forever.