DSA & System Design
Full-stackHard50 min

Design Google Docs (Collaborative Editing)

Many people type in one document at once. Local echo keeps typing instant, a server orders the edits, and OT or a CRDT merges the concurrent ones.

Related:Polling, SSE and WebSocketsConsistency and CAP Explain it back
Say it in 30 seconds
  • 2M ops/sfrom 1M concurrent editors
  • ~100-200 msfor others to see an edit
  • ~500 opsworst-case replay after a crash
Show what to say

“I'd show each edit locally at once and send it, with the revision it was based on, to a session server that owns the document. The server transforms it past edits the sender missed (operational transformation), appends it to an operation log, assigns the next revision and broadcasts it. Snapshots every few hundred edits make recovery fast. A CRDT is the alternative for offline-first.”

Trade-offs

  • OT vs CRDT: OT is compact with a central server but subtle to get right; CRDTs work offline and peer-to-peer but carry ids and tombstones.
  • Local echo vs wait for ack: typing feels instant, but edits must be transformed and reconciled when the server answers.
  • One server per document vs sharing a document: a single order is simple, but one hot document is bounded by one machine.

Bring it up before they ask

Unacknowledged edits after a crash: clients resend by operation id, and the server ignores repeats, so nothing is lost or applied twice.

0 of 0 sections ticked
30-second answer

Show every edit locally at once, and send it to a session server that puts all edits in one order. Concurrent edits are fixed by (rewrite an edit to fit the ones it missed) or by a (give every character a permanent id). The operation log is the source of truth.

Functional

  • Many people edit one document at the same time
  • Everyone sees the same text in the end
  • See other people's cursors and names
  • Version history and restore
  • Keep working offline and merge on return

Non-functional

  • Your own typing appears instantly (local echo)
  • Others' edits arrive in about 100 to 200 ms
  • No accepted edit is ever lost
  • 1M concurrent editors at peak
  • A document survives a server crash

Out of scope

  • Rich-text formatting rules and tables
  • Comments, suggestions and permissions UI
  • Search across documents

Clarify and estimate

Ask first:

Read more · 180 words
  • How many editors per document? Three is typical; hundreds is a special case.
  • Plain text or rich text? Rich text adds attributes; the idea is the same.
  • Offline? Long offline edits favour .
  • Server in the loop? A central server makes ordering simple.

Capacity estimate

QuantityCalculationResult
Edit rate1M editors × 2 batched ops/s2M ops/s
Ingest2M/s × 50 B100 MB/s
Active documents1M editors ÷ 3 per document≈ 333K
Session servers333K ÷ 5,000 documents per server≈ 67
Operation log10M editors × 1 h × 2 ops/s × 50 B≈ 3.6 TB/day
Replay after a crashsnapshot every 500 opsat most 500 ops

The key insight: traffic is high overall but tiny per document. One server can own a document and order its edits. by document id.

API and data model

API. messages, one socket per open document.

Read more · 95 words
DirectionMessagePayload
Client to serverjoin{ docId, lastRev }
Client to serverop{ opId, baseRev, op }
Server to clientack{ opId, rev }
Server to clientremote{ rev, op, by }
Bothcursor{ pos, name, color }, not stored

REST: POST /docs, GET /docs/:id (latest snapshot and revision), GET /docs/:id/revisions.

Data model

Large snapshots live in ; the table keeps a pointer. Cursors and presence are never stored.

CREATE TABLE ops (
  doc_id    bigint,
  rev       int,                    -- 1, 2, 3 ... per document, assigned by the session server
  op_id     uuid,                   -- from the client, so a retry is recognised
  author    bigint,
  op        jsonb,
  PRIMARY KEY (doc_id, rev),
  UNIQUE (doc_id, op_id)
);
CREATE TABLE snapshots (
  doc_id bigint, rev int, content text,   -- the text after `rev` operations
  PRIMARY KEY (doc_id, rev)
);

Architecture

Edits take the path editor, gateway, session server, log.

Read more · 25 words

The router sends all editors of a document to one session server. Play Type a character, Concurrent edits, Reconnect after offline and Session server crashes.

Press Play to watch it run · 6 steps

Editors keep a WebSocket to a gateway. A document router sends every connection for one document to the same session server, which orders edits, transforms concurrent ones, appends them to an operation log and broadcasts the result. Snapshots keep loading fast; presence and cursors travel on a separate lightweight channel.

Collaborative editor architectureEditors keep a WebSocket to a gateway. A document router sends every connection for one document to the same session server, which orders edits, transforms concurrent ones, appends them to an operation log and broadcasts the result. Snapshots keep loading fast; presence and cursors travel on a separate lightweight channel.op, baseRevop, baseRevwho owns doc?opscursorsappendsnapshotEditor Aapplies edits at onceEditor Bsees A's editsWS gatewayholds socketsConsistent hashing on the document id. Every editor of one document lands on the same session server, so one process can put their edits in a single order.Doc routerdoc id to serverHolds the live document in memory. Gives each accepted operation the next revision number, transforms it against operations the sender had not seen, and broadcasts it.Doc sessionorders + transformsPresencecursors, namesEvery accepted operation, in order, per document. This is the source of truth and the version history.Operation logappend-onlySnapshotsevery ~500 ops

Tap any box to see what it is and what it talks to.

  • Client
  • API gateway
  • Service
  • Pub/Sub
  • Database
  • Object storage
Open in playground
Text description
  1. A types 's'. It shows on A's screen immediately. The editor also sends insert('s', pos 3) with baseRev 12.
  2. The gateway asks the router which session server owns this document.
  3. The edit reaches that server. Nothing else has been accepted since revision 12, so there is nothing to transform against.
  4. It becomes revision 13 and is appended to the operation log. Only now is it durable.
  5. The server acknowledges revision 13 to A, and broadcasts the operation to B.
  6. B applies the operation and sees the 's' appear, about 100 ms after A typed it.

Operational transform and CRDTs

Operational transform. Two people edit 'cat' at once: A appends 's', B deletes 'c'.

Read more · 218 words

Each edit is a position in the text, and positions go stale when something else changes. (OT) fixes this: the server rewrites the later edit so it means the same thing after the earlier one.

Each client sends an edit tagged with the revision it started from. The server transforms it past everything accepted since, assigns the next revision and broadcasts it. Each client keeps one edit in flight and transforms incoming edits past its own unacknowledged ones. Everyone converges, and typing never waits.

, the alternative. A CRDT avoids rewriting. Every character gets a permanent id. An insert says "after character X", and a delete only marks a character dead (a ). Edits merge in any order, so no central server is needed and offline editing is natural.

The price is memory: ids and tombstones stay until compaction. Compare both on the same example, then pick.

Press Play to watch it run · 4 steps

'cat' becomes 'ats' when A appends 's' and B deletes 'c' at the same moment. Operational transformation lets a server rewrite one operation so it still means the same thing after the other. A CRDT gives each character an id, so the operations merge without rewriting.

Two edits at once: OT and CRDT'cat' becomes 'ats' when A appends 's' and B deletes 'c' at the same moment. Operational transformation lets a server rewrite one operation so it still means the same thing after the other. A CRDT gives each character an id, so the operations merge without rewriting.Both start from 'cat' at revision 12insert('s', pos 3)delete(pos 0)alt [OT]Server accepts A first: revision 13B's delete is transformed past A's insert: position 0 is left of 3, unchanged: revision 14A's insert, shifted to pos 2B's delete(pos 0)Both show 'ats'. Position numbers changed on the way
  • Client
  • Service
Text description
  1. Editor A → Server: insert('s', pos 3)
  2. Editor B → Server: delete(pos 0)
  3. Server replies to Editor B: A's insert, shifted to pos 2
  4. Server replies to Editor A: B's delete(pos 0)

Presence, storage and history

Presence and cursors. A cursor changes ten times a second and is worthless a second later.

Read more · 101 words

Send it over the same socket but through a lightweight channel, never write it to the log, and drop it when the socket closes. Throttle to about 10 updates a second and fade idle cursors.

Storage and history. Append every accepted operation to the log. Every few hundred operations write a snapshot of the whole text. Loading a document means the latest snapshot plus the tail of the log, at most about 500 operations.

Version history is the log: pick a revision, replay up to it. Old operations can be merged into coarser "named versions" after a month to save space.

Step-by-step answer

Order: clarify, estimate, pick an owner per document, resolve conflicts, then durability and scale.

Read more · 228 words

  1. Start with the user experience

    Typing must feel instant, so apply edits locally first and reconcile later. That is the whole reason this is hard.

  2. Route a document to one server

    Hash the document id to a session server. All its editors connect there through gateways, so one process can order edits.

  3. Number every accepted edit

    Each edit carries the revision it was based on. The server transforms it past newer ones, appends it to the log, and assigns the next revision.

  4. Keep one edit in flight per client

    The client sends one edit, buffers the rest, and transforms incoming edits past its pending ones. This keeps the protocol simple and correct.

  5. Acknowledge after the log write

    An edit is durable only once the log append succeeds. Clients keep unacknowledged edits and resend them by operation id.

  6. Snapshot and recover

    Snapshot every few hundred edits. After a crash, the new server loads the snapshot and replays the log tail.

  7. Handle offline and reconnect

    On reconnect, send the last revision seen and the queued edits. The server transforms them past what was missed.

  8. Say when you would choose a CRDT

    For long offline work, peer-to-peer sync or no central server. Mention growth and compaction.

Implementation

Tabs: the transform function and its tests, the client and server protocol, and a sequence (RGA).

Read more · 105 words
  • The OT test checks convergence for 5,000 random pairs of operations, and for three clients with random message timing over 200 runs.
  • The CRDT test applies the same operations in shuffled order with duplicates and checks every ends equal.
  • rga.test.js also shows : an empty document that still remembers 100 characters.
// Operational transformation (OT) for plain text, one character at a time.
//   { type: 'insert', pos, ch, site }   put `ch` before the character at index `pos`
//   { type: 'delete', pos, site }       remove the character at index `pos`
//   { type: 'noop' }                    nothing (what a delete becomes when someone already deleted that character)
// `site` is the author's id; it breaks the tie when two people insert at the same position.
//
// transform(a, b) answers: "a was made on the same document as b, but b has already been applied.
// What should a become so it still means the same thing?"  Guarantee (TP1):
//   apply(apply(doc, a), transform(b, a))  ===  apply(apply(doc, b), transform(a, b))

export function apply(doc, op) {
  if (op.type === 'insert') return doc.slice(0, op.pos) + op.ch + doc.slice(op.pos);
  if (op.type === 'delete') return doc.slice(0, op.pos) + doc.slice(op.pos + 1);
  return doc;
}

export const insert = (pos, ch, site) => ({ type: 'insert', pos, ch, site });
export const del = (pos, site) => ({ type: 'delete', pos, site });

export function transform(a, b) {
  if (a.type === 'noop' || b.type === 'noop') return a;
  if (a.type === 'insert' && b.type === 'insert') {
    if (a.pos < b.pos || (a.pos === b.pos && a.site < b.site)) return a;      // a stays left of b
    return { ...a, pos: a.pos + 1 };                                            // b's character is now before a
  }
  if (a.type === 'insert' && b.type === 'delete') {
    return a.pos <= b.pos ? a : { ...a, pos: a.pos - 1 };
  }
  if (a.type === 'delete' && b.type === 'insert') {
    return a.pos < b.pos ? a : { ...a, pos: a.pos + 1 };
  }
  // delete vs delete
  if (a.pos < b.pos) return a;
  if (a.pos > b.pos) return { ...a, pos: a.pos - 1 };
  return { type: 'noop' };                                                      // both deleted the same character
}

// Transform one op past a whole list of ops that were applied before it.
export const transformAgainst = (op, others) => others.reduce((o, other) => transform(o, other), op);

Failure modes and trade-offs

Read more · 179 words
What breaksEffectMitigation
Session server crashesEditing pausesReassign the document; snapshot plus log replay
Duplicate deliveryAn edit applied twiceOperation ids; the server ignores repeats
Client offline for longLarge rebaseTransform queued edits past missed ones; cap the queue
Transform bugCopies divergeProperty tests; periodic checksum of the document
Hot document, 1,000 editorsOne server saturatedRead-only viewers on a fan-out tier; limit editors
Log grows foreverStorage costSnapshots; compact old operations

Trade-offs

ChoiceGainCost
OT with a central serverCompact, no tombstonesTransform functions are subtle; needs a server
CRDTWorks peer-to-peer and offlineIds and tombstones grow memory
Last-writer-wins on the whole docTrivialLoses people's edits
Lock the paragraphSimple conflict storyBlocks people; poor feel

Follow-up questions

How do you undo?

Undo is a new operation that reverses your last edit after transforming it past everyone else's later edits, not a rollback of the document.

How do you scale one very popular document?

Keep editing on one server, and read-only viewers through a separate tier that follows the log.

How do you test a transform function?

Property tests: random pairs of operations must converge in both orders, and random multi-client runs must end equal.

Check yourself

Question 1 of 3

Score 2 out of 3 or better to mark this page complete.

1. A and B both start from 'cat'. A inserts 's' at position 3; B deletes the character at position 0. With operational transformation, what does the server do with B's delete when it arrives second?