Library
35 min read

Design Google Docs

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.

Editor AEditor BGatewayCoordinatorPresenceDocument serverTransformIn memory docOp logSnapshotsHistory

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.

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.

Step 1: Understand the problem#

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 askThey sayWhat 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.

What you are building, and what you cut#

Functional requirements
What the system does.
  • Several people editing one text document at once. Every editor converges to the same result, always.
  • Local edits apply instantly. Reconciliation happens behind the cursor, never in front of it.
  • Presence and cursors. Cheap, ephemeral, and the thing users notice first.
  • History, and offline edits that merge on reconnect. The operation log gives you both.
Non-functional requirements
How well it has to do it. The numbers you commit to.
  • A keystroke is visible locally in under 16ms and to others in under 200ms.
  • Every client converges to a byte identical document.
  • A document survives any server restarting mid edit.
  • Fifty concurrent editors on one document without degradation.
Out of scope
What you cut, and say so out loud.
  • Rich media, tables and embedded objects. Same machinery, much messier operations, and it triples the page.
  • Access control and sharing. Real and orthogonal, and it belongs one layer up.
  • Rendering and layout. That is a word processor, not a distributed system.
  • Spreadsheet formula recalculation, which is a dependency graph problem hiding behind the same UI.

Back of the envelope#

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.