Courses › System Design › Question Breakdowns

Design Google Docs

Operational transformation vs. CRDTs, one server per document, op log plus snapshots, presence and offline edits.

Google Docs lets many people edit the same document at once and see each other's changes and cursors within a fraction of a second. It looks like a CRUD app with a text field, but it's a question about concurrent edits to shared state: how two people typing in the same sentence end up with the same document, how edits reach every collaborator in real time, and how you store a document that is really a stream of millions of tiny operations.

Requirements

Functional

  • Users can create, open and edit a document
  • Multiple users can edit the same document concurrently and see each other's changes in real time
  • Users can see collaborators' cursors and selections (presence)
  • Users can view version history and restore an earlier version

Out of scope: comments and suggestions, rich embedded objects (tables, drawings), search across documents, sharing UI (assume a permission check exists).

Non-functional

  • Convergence: all collaborators must end up with exactly the same document, whatever order edits arrive in
  • Latency: local edits apply instantly; remote edits appear in < 200 ms
  • Durability: an acknowledged edit is never lost
  • Scale: ~100M documents edited per day; most have 1–3 editors, a few have 100+ concurrent viewers
  • Offline: a user who loses connection keeps typing and syncs later

[!TIP] Separate the two problems Say early that there are two distinct problems: merging concurrent edits (an algorithm question — OT or CRDT) and delivering edits to everyone editing the same document (a routing question — send all editors of a document to the same server). Solving them separately keeps the design clear.

Capacity estimates

The op log grows quickly, so it must be compacted into snapshots.

Core Entities

  • Document — id, title, owner, current version, latest snapshot pointer
  • Operation — document id, version number, author, the change (insert "abc" at 120, delete 5 at 300, format bold 10–20)
  • Snapshot — document id, version, full content at that version
  • Session / presence — user, document, cursor position, color

API

GET  /v1/docs/{docId}                          → { snapshot, version }
GET  /v1/docs/{docId}/ops?since={version}      → ops[]   (catch up)
GET  /v1/docs/{docId}/history                  → versions[]

WS   /v1/docs/{docId}/live
  client → server  { type: "op", baseVersion: 41, op: {...}, clientOpId }
  server → client  { type: "ack", clientOpId, version: 42 }
  server → client  { type: "op", version: 43, op: {...}, author }
  both directions  { type: "cursor", userId, position }

High-Level Design

user = client "Editors" @0,1
gw = service "WebSocket Gateway" @1,1
router = service "Doc Router\n(consistent hashing)" @1,0
docsvc = service "Document Server\n(owns doc 812)" @2,1
oplog = store "Op Log\n(per-doc, ordered)" @3,0.5
snap = blob "Snapshots" @3,1.5
meta = store "Doc Metadata" @2,0
presence = cache "Presence\n(in memory)" @2,2
user <-> gw
gw -> router : which server owns doc?
gw <-> docsvc
docsvc -> oplog : append
docsvc --> snap : periodic snapshot
docsvc -> presence
router -> meta
  • Open: the client loads the latest snapshot plus any later operations, then opens a WebSocket.
  • Route: the gateway sends every connection for a document to the one document server that owns it, chosen by consistent hashing on the document ID.
  • Edit: the client applies the edit locally right away and sends it with the version it was based on.
  • Order and merge: the document server transforms the operation against anything newer, assigns the next version number, appends it to the op log, acks the author and broadcasts to other editors.
  • Snapshot: every few hundred operations the server writes a full snapshot so loading never replays the whole history.

Deep Dives

1. Merging concurrent edits: OT vs CRDT

Alice inserts "big " at position 4 while Bob deletes the character at position 10. If Bob's delete is applied unchanged after Alice's insert, it deletes the wrong character. Positions must be adjusted for concurrent edits.

With a server that owns each document, OT is the classic answer (it's what Google Docs uses): the server is the single source of order, so transformations only happen against the server's history. CRDTs are an equally strong answer, especially if you emphasize offline editing or peer-to-peer.

Server is at version 41. Bob sends op B based on version 40.
Op 41 (Alice: insert "big " at 4) happened after Bob's base.
B' = transform(B, op41)   → delete at 10 becomes delete at 14
Apply B' as version 42, broadcast B' to everyone, ack Bob with version 42.

The client does the mirror image: it keeps its unacknowledged ops in a pending buffer and transforms incoming server ops against them, so its local view stays correct.

[!WARNING] Don't let clients send whole documents Sending the full document on every keystroke wastes bandwidth and turns every concurrent edit into a conflict. Always send small operations relative to a known version.

2. Getting every editor to the same place

OT needs one ordering point per document. Route by document ID:

  • A document router maps docId → document server with consistent hashing (membership in ZooKeeper/etcd). Gateways look it up and forward the connection.
  • Each document server holds the live state of its documents in memory: current text, version, and recent ops for transforming late-arriving edits.
  • Load is naturally spread because there are millions of documents and each needs little CPU.

If a document server dies, its documents are reassigned; the new owner loads the latest snapshot plus the op log tail and clients reconnect and resend their pending ops (deduplicated by clientOpId). See Consistent Hashing.

3. Storing the document: op log + snapshots

  • The op log is the source of truth: an append-only, per-document ordered list of operations. A store keyed by (docId, version) — Bigtable, Cassandra or a sharded PostgreSQL table — works well.
  • The server acknowledges an edit only after it's durably appended, so no acknowledged edit is lost.
  • Snapshots every N operations (or every few minutes of activity) go to blob storage. Loading = latest snapshot + ops after it.
  • Compaction: after snapshotting, old ops can be merged into coarser history entries ("Alice edited 2:00–2:15").

This is event sourcing applied to a document.

4. Version history

Version history falls out of the op log and snapshots:

  • Show named or periodic checkpoints, grouped by author and time.
  • To view version 3,000, load the nearest earlier snapshot and replay ops up to 3,000.
  • Restore is a new forward edit that sets the content back — never a rewrite of history — so collaborators converge on it like any other change.

5. Cursors and presence

  • Cursor positions change constantly and don't need durability. Send them over the same WebSocket but keep them only in memory on the document server, and throttle updates to ~10 per second per user.
  • Cursor positions must also be transformed when text is inserted before them, exactly like operations.
  • Drop presence for a user when their connection closes or heartbeats stop.

6. Offline editing and reconnects

  • The client keeps editing locally and queues operations with their base version.
  • On reconnect, it fetches missed ops (GET /ops?since=), transforms its queued ops against them, and sends them. With OT, long offline sessions mean a lot of transforming; this is where CRDTs shine.
  • clientOpId makes resends idempotent.

7. Very popular documents

A document with 1,000 viewers and a few editors (a company-wide announcement):

  • Separate editors from viewers. Viewers receive a broadcast stream from fan-out servers subscribed to the document's updates, rather than connecting to the document server directly.
  • Batch ops into one update every 100 ms for viewers.
  • Cap concurrent editors (Google Docs limits real-time editors per document) and degrade beyond that.

What's expected at each level

  • Mid-level: WebSocket-based real-time sync, sending operations instead of whole documents, and a reasonable storage model for documents.
  • Senior: explains OT or CRDTs and why positions must be transformed, routes all editors of a document to one server, uses an op log with snapshots, and handles reconnects idempotently.
  • Staff: compares OT and CRDTs with their operational trade-offs, handles document server failover without losing edits, designs version history and compaction, offline editing, and very large audiences.