Back to System design
Design a Collaborative Editor (Google Docs)
hardTwo people type in the same document at the same time and both see the same result. That is the whole problem, and it is harder than it sounds.
ScaleSub-100ms keystroke echo; 100-1000s concurrent editors per doc max
StorageOp log + snapshot per doc; CRDT metadata can be large
Key Concepts
1
Why it is hard, with five letters. The document says
HELLO. Positions are numbered from 0.Why it is hard, with five letters.HELLO
2
Alice adds
! at position 5, so she sees HELLO!. At the same moment Bob deletes position 0, so he sees
ELLO.!HELLO!ELLO
3
Now the two edits cross on the network.
4
Bob's machine already shows ELLO
Alice's edit arrives: "insert ! at position 5"
But ELLO only has 4 letters. Position 5 does not exist.
5
Bob's machine either drops the
! or puts it somewhere wrong. Alice sees ELLO! and Bob sees ELLO. The
two documents have permanently disagreed, and neither edit was invalid.!ELLO!ELLO
6
This is not a stale cache that catches up later. Nothing will fix it on its own.
7
Fix one: change the edit as it arrives. A central server decides the order. It applies Bob's delete
first. Then, before applying Alice's insert, it adjusts the position: one character before position 5 was
removed, so position 5 becomes position 4.
Fix one: change the edit as it arrives.
8
Both machines end up with
ELLO!. This adjusting is called Operational Transformation, or OT. It sends
very little data — a position and a character — and it needs a server to decide the order, because working
out the adjustment against every possible sequence of other edits is where OT implementations go wrong.ELLO!
9
Fix two: stop using positions. Give every character a permanent identifier when it is typed. Alice's
! is not "at position 5"; it is "after the character with id A5".Fix two: stop using positions.!
10
Deleting the
H does not move that identifier, so Alice's insert still lands in exactly the right place
with no adjustment at all. Order of arrival stops mattering.H
11
This is a CRDT. It needs no central server, which is what makes offline editing and peer-to-peer work. The
cost is size: every character carries an identifier, and deleted characters must be kept as markers so
that edits referring to them still make sense. A heavily edited document accumulates those markers, so a
CRDT needs a plan for clearing them out.
12
Neither one decides what you meant. Alice makes a word bold while Bob deletes it. Both approaches will
agree on a final document. No algorithm knows whether "make the deleted word bold" should bring it back.
That is a product decision, and saying so is worth more than pretending otherwise.
Neither one decides what you meant.
13
Typing must feel instant, so apply changes locally first. The editor applies your keystroke
immediately and sends it afterwards. When the server's version comes back, the editor reconciles the two.
If it waited for the server, typing would lag by the round trip.
Typing must feel instant, so apply changes locally first.
14
Cursors are not edits. Showing where other people are clicking generates far more messages than the
typing does, and none of it is worth saving. Send it over the same connection, limit it to about ten
updates a second, and forget it when someone disconnects.
Cursors are not edits.
15
Opening a document quickly. Replaying a million edits from the beginning is too slow. Save a snapshot
of the whole document periodically and keep only the edits since. Opening means loading the snapshot and
replaying a short tail.
Opening a document quickly.
16
Undo is harder than it looks. Undoing your own edit is not "apply the opposite". Other people have
typed since. The opposite has to be adjusted against everything that happened in between, or your undo
deletes someone else's sentence.
Undo is harder than it looks.
17
What the interviewer is probing.
What the interviewer is probing.
18
1. "Two people type in the same place." Probing: whether you can state the failure exactly.
Stalls: "Last write wins." In a document that throws away someone's typing. Moves up: the
HELLO
example, then the two families of fix.1. "Two people type in the same place."HELLO
19
2. "OT or CRDT?" Probing: the real trade. Stalls: naming one as modern. Moves up: OT sends
little and needs a central server; CRDTs need no server and carry an identifier per character plus
markers for deleted ones.
2. "OT or CRDT?"
20
3. "Someone edits offline for an hour." Probing: reconnection. Stalls: "Sync when they come
back." Moves up: an hour of other people's edits must be merged; CRDTs handle it by construction, OT
needs the server to adjust a long queue.
3. "Someone edits offline for an hour."
21
4. "How do you show other people's cursors?" Probing: what is worth storing. Stalls: "Save the
cursor positions." Moves up: they are throwaway, far more frequent than edits, and should be rate
limited.
4. "How do you show other people's cursors?"
22
5. "How do you open a document with a million edits?" Probing: snapshots. Stalls: "Replay them."
Moves up: periodic snapshot plus the edits since, with the frequency chosen from how fast you need it to
open.
5. "How do you open a document with a million edits?"
High-level design
Client opens WebSocket to doc owner.
Client sends ops with revision number.
Owner orders ops (OT) or merges (CRDT), persists, broadcasts to others.
Snapshot + op log durable.
Presence on separate channel (Redis pub/sub).
Permission checked on join.
Reconnect: replay missed ops.
Components
- WebSocket gateway with doc → owner routing.
- Doc owner service (one per doc; sharded by doc_id).
- Op log + snapshot store (Postgres / KV).
- Presence service (Redis pub/sub).
- Permission service (ACL on doc).
- Export / print pipeline (PDF, Word).
- Search indexer (async).
The divergence, worked
Document state on both machines: H E L L O
0 1 2 3 4Alice: insert "!" at index 5 -> HELLO! Bob: delete index 0 -> ELLO
Both operations are created against the SAME original state and sent concurrently.
Naive application, Alice's machine
apply own insert -> HELLO!
apply Bob's delete(0)-> ELLO! (correct by luck) Naive application, Bob's machine
apply own delete -> ELLO
apply Alice's insert at 5 -> ELLO (index 5 no longer
exists; the "!" is
dropped or misplaced)Result: the two machines disagree. In a text editor this is not a stale read that resolves later -- it is permanent divergence.
With OT
The server orders the operations. Bob's delete(0) is applied,
then Alice's insert(5) is TRANSFORMED to insert(4) because one
character before it was removed.
Both machines converge on ELLO! With a CRDT
"!" is inserted after the character with identifier
id(O)=A:5, not at numeric index 5. Deleting id(H)=B:0 does not
move that reference, so both machines converge on ELLO! with
no transformation step.OT vs CRDT
OT CRDT
------------------------------------------------------------------
Merge mechanism transform ops commutative ops
against concurrent by construction
ops
Central server required (to impose not required
a total order)
Wire size small (index + char) larger (identifier
per character)
Memory document size document + tombstones
for deleted chars
Offline editing possible but the natural
transform queue
grows
Peer-to-peer no yes
Implementation risk high -- correctness moderate -- the
of transform
functions is subtle algorithm is the
hard part, not the
edge cases
Used by Google Docs (classic) Automerge, Yjs,
newer editors Tombstone growth, the CRDT cost to name
A document heavily edited over years accumulates identifiers
for deleted characters. Mitigations: periodic garbage
collection when all peers have acknowledged a version, or
compaction at a snapshot boundary. Saying "tombstones need a
GC story" shows you have thought past the demo.Session, presence, persistence
Connection
One WebSocket per client per open document.
Server holds: document state, a monotonic revision number, and
the set of connected clients. Edit path
1. Client applies the edit locally, immediately (no waiting).
2. Sends op + the revision it was based on.
3. Server transforms/merges against ops since that revision,
assigns the next revision, broadcasts.
4. Client reconciles its optimistic state with the
acknowledged order.
-- local-first application is what makes typing feel instant;
the reconciliation is invisible when it works. Presence (cursors, selections, avatars)
Volume: a cursor moves far more often than text changes.
Throttle to ~10 updates/second per client, broadcast without
persistence, and expire on disconnect. Persistence
Snapshot cadence every N operations (e.g. 1,000) or on
idle
Open cost load snapshot + replay ops since
Target < 500 ms to interactive
Version history snapshots plus the op log, which is also
what lets you show "who changed what" Undo, the detail people miss
Undo is not "apply the inverse of my last op". It is "apply
the inverse, transformed against everything that happened
since" -- otherwise undo deletes someone else's text.