Google Docs

What the interviewer is asking

"Design Google Docs" asks for a collaborative editor: several people type in one document at once and see each other's typing as it happens. Storing text is easy. The hard part is merging: two people edit the same spot at the same moment, both edits must survive, and every screen must end with the same text.

The walkthrough below follows the 8 steps of the interview framework: scope, data, API, the busy path, numbers, services, scale and deep dives.

1. Scope: what version 1 must do

• Live co-editing: several people edit one document at once and see each other's typing within a second.
• Nothing lost, one result: nobody's edit disappears, and every screen ends with the same text.
• Cursors: a colored cursor with a name for each person in the document.
• Version history: every past version, with who changed what, and when.

Park the rest out loud: comments and suggested edits, rich formatting, editing offline for days, and sharing rules beyond view and edit. Plain text is enough to design the merging.

2. Data: a log of operations plus snapshots

Two tempting answers fail. Saving the whole text after every keystroke means that when two saves cross, the later one drops the other's letters (last-write-wins). Whole-file sync, as in Dropbox, turns a clash into a conflicted copy for someone to merge by hand. A live editor merges every keystroke.

So store the document as a sequence of operations, each numbered by the server with a revision:

rev   who   operation          text after it
1     Ana   insert "c" at 0    c
2     Ana   insert "a" at 1    ca
3     Ben   insert "t" at 2    cat
4     Ben   delete at 0        at
5     Ana   insert "r" at 1    art

Replaying the log gives the text at any revision, so version history comes almost free. To avoid replaying a long log from the start, the server saves a snapshot every 1,000 revisions: the text at any revision is the newest snapshot before it plus the operations after it. Restoring an old version writes new operations that turn today's text into the old one, so the log only ever grows.

3. The API: a WebSocket and plain HTTP

Edits arrive at any moment, in both directions, so each open editor keeps one WebSocket (the Real-Time Updates lesson compares it with polling). → is from the browser, ← from the server:

GET /docs/d42/live   Upgrade: websocket   → 101 Switching Protocols, and the connection stays open
→ {"type": "edit", "base": 3, "insert": "r", "at": 2}
← {"type": "edit", "rev": 4, "by": "ben", "delete": 0}
← {"type": "ack", "rev": 5}
← {"type": "cursor", "by": "ben", "at": 0}

Every edit a browser sends names its base, the last revision it had seen; the deep dive shows why. Whatever the browser asks for itself is plain HTTP:

GET  /docs/d42/history   → 200 OK  revisions with who and when
POST /docs               → 201 Created  {"id": "d43"}

4. The busy path: one keystroke to everyone

1. Ana's screen shows her letter at once, and her browser sends the edit on its WebSocket.
2. The server gives the edit the next revision number.
3. It appends the edit to the document's op log.
4. It sends the edit to every other editor of the document.
5. Ben's browser applies it, and the letter appears on his screen.

Ana never waits to see her own typing. Log first, then send: once an edit is in the log, nothing that fails later can lose it. Each hop inside the data center is a round trip of about 0.5 ms; the editors' own networks take most of the time, and the trip stays well under a second.

5. The numbers

From the interviewer: a busy document has 50 editors, each typing about 5 characters a second, and every character is one operation. Most documents being edited are much quieter, one or two people typing on and off: about 10 operations a second. Say one document server handles about 1,000 operations a second, like an app server.

what          how                                   result
busy doc      50 editors × 5 characters a second    250 operations a second
per server    1,000 ÷ 10                            about 100 documents being edited
busiest doc   250 of a server's 1,000               a quarter of one server

The busiest document fits on one server, so no document ever needs two. That shapes the design: each document lives on exactly one server, the one place where all its edits meet and get one order, and each operation is sent on to the other 49 editors through their gateways.

6. Services: gateways and a doc service

• Gateways hold the editors' WebSockets (up to 100,000 each, as in Real-Time Updates), pass each edit to its document's server and push other people's edits down. Nothing else.
• The doc service keeps each open document's text in memory, numbers its edits, appends them to the op log and saves a snapshot every 1,000 revisions.
• The op log (an append-only database, split by document id) and the snapshot store (object storage) keep the document for good.

Gateways grow with people connected, the doc service with edits a second. Restarting a gateway only makes browsers reconnect: the op log has every edit.

7. Scale: one server per document

The doc service runs on many document servers, about 100 active documents each. Ana's WebSocket landed on gateway 1 and Ben's on gateway 2, yet all of d42's edits must reach one server. If each gateway picked the least busy server, d42 would have two owners, each ordering half its edits.

The fix is a directory: document id → server, kept in memory like Chat's session store. When d42 has no entry yet, a gateway picks a server with room and writes "d42 → doc server 2" only if no one has (a conditional write, as in Concurrency and Locks). Hashing the document id onto the servers (Consistent Hashing) also works; a directory makes it easier to move a hot document.

When a document server crashes, only the text it held in memory is gone. The new owner loads the newest snapshot and replays the log since: at revision 5,240 with a snapshot at 5,000, that's 240 operations, and never more than 999 with a snapshot every 1,000 revisions. Browsers resend any edit that was never acknowledged, with an id, so one already logged isn't applied twice.

8. Deep dive: conflicts and operational transformation

Take d42 at revision 3, "cat". At the same moment Ana types "r" at position 2 ("cart") and Ben deletes the "c" at position 0 ("at"). If the server just passed each edit on as it was sent:

screen   own edit     the other's edit, as sent   result
Ana      cat → cart   delete at 0                 art
Ben      cat → at     insert "r" at 2             atr

Two texts, and no error: position 2 in "at" is after the t. Operational transformation (OT) fixes it with one order and a shift. Ben's delete reaches d42's server first and becomes revision 4. Ana's insert arrives with base 3, so the server knows it missed revision 4: the delete before her position moved every later letter one to the left, so insert at 2 becomes insert at 1. The server logs that as revision 5 and sends it to Ben: "at" becomes "art". Ana's browser shifts Ben's delete past her own pending r the same way; it stays at 0, and her "cart" becomes "art" too.

For plain text the rules are short:

your edit   the edit you missed            your position
insert      an insert at or before it      one to the right
insert      a delete before it             one to the left
delete      an insert at or before it      one to the right
delete      a delete before it             one to the left
delete      a delete of the same letter    nothing left to do
any         an edit after it               unchanged

Two inserts at one position need a tie-break every copy agrees on, such as "the edit already in the log goes first". Rich text adds more operations and rules.

The server is the one order: it shifts each edit past everything logged after its base, gives it the next revision and sends it out. It's the version check from Concurrency and Locks, except that an edit on an old revision is shifted, not rejected, since rejecting would throw away someone's typing. A common design keeps one batch of edits in flight per browser: while it waits for the ack, the browser holds new letters, then sends them on the newest base. Google Docs is widely described as using OT.

9. Deep dive: CRDTs

A CRDT (conflict-free replicated data type) merges without a central order. Each letter gets a place between its neighbors: c 1, a 2, t 3. Ana's "r" gets place 2.5, and Ben's delete names place 1, the c. Every copy applies both edits, in either order, and ends with "art": an edit names letters, not positions that move. Two inserts at the same place also carry the writer's id, so every copy sorts them the same way.

Pick a CRDT when no server sees every edit: devices that sync directly, or editing offline for days. It's the available side of CAP and Consistency: every copy keeps taking edits, and they agree once they've swapped them. The price is size: every letter carries an id, and deleted letters often stay as hidden markers. With one server per document already, OT is the natural fit.

10. Deep dive: cursors and presence

Cursors, and the avatars of who's in the document, are ephemeral: a lost update is replaced by the next one a moment later. They travel on the same WebSocket, through the document's server, but are never written to the op log, so history and crash recovery never replay them. The server shifts them like edits: if Ben's cursor is at position 2 in "art" and Ana types "c" at position 0, his cursor moves to 3, still just before the t. When Ben's WebSocket closes, his cursor and avatar vanish from everyone's screen.

What breaks first

• A hot document: a busy one takes a quarter of a server, so the directory moves it to a server with room.
• A document server crashes: its documents pause until the new owner has replayed snapshot plus log.
• The op log grows forever: keep snapshots, and squash old history into fewer versions, one an hour, say.
• A gateway restarts: its browsers reconnect at once, so each waits a random second or two first.

Summary: the order to follow

1. Scope: live co-editing, nothing lost, one result, cursors, history.
2. Data: a log of numbered operations, plus snapshots.
3. API: a WebSocket per editor; GET /docs/{id}/history over HTTP.
4. Busy path: one keystroke, logged, then sent to the other editors.
5. Numbers: 250 operations a second for a busy document, about 100 documents per server.
6. Services: gateways, a doc service, the op log and snapshots.
7. Scale: a directory puts each document on one server; snapshot plus log after a crash.
8. Deep dives: OT orders and shifts edits; CRDTs merge without a server; cursors are ephemeral.

The same pieces carry over to whiteboards, spreadsheets and code editors: one place that orders each document's changes, a log of them, and live connections.