Design Google Docs

Source: https://www.hack2hire.com/question-bank/questions/system-design/69ca9a17ff3ebde766ced8e7
Company: Meta, Microsoft
Difficulty: Hard

Problem statement

Many people edit the same document at once and see each other's changes and cursors live, with offline edits and full version history.

Requirements

We are building a collaborative rich-text editor in the style of Google Docs: many people edit one document at once, see each other's edits and cursors within a fraction of a second, keep editing while offline, and can browse and restore any past version.

Questions worth asking first: how many simultaneous editors per document (tens, or thousands like a company all-hands doc)? Rich text or plain text? Is offline a first-class requirement or a later extension? Do we need comments and suggestion mode? Assume rich text, up to ~100 active editors and many more viewers, and offline as a real requirement.

Functional requirements

• Create, open, and edit a document; every keystroke shows up for other editors in real time.
• Concurrent edits to the same region converge to the same result on every client, with no lost input.
• Presence: see who is in the document, their cursor and selection, in their color.
• Offline: keep editing with no connection; changes merge when the client reconnects.
• Version history: list named and automatic versions, view any one, restore it; undo/redo per user.
• Share with view/comment/edit roles; viewers see live updates but cannot edit.

Non-functional requirements

• Edit-to-remote-screen latency under 200 ms p99 in-region; local typing is never blocked on the network.
• Durability: an acknowledged operation is never lost (it is in a replicated log before the ack).
• Convergence is mandatory; availability of editing is preferred over strict global ordering (local echo always).
• Scale: 1B documents, 10M concurrently open, hot documents with hundreds of editors and 10K+ viewers.

Back-of-the-envelope estimation

• 10M open docs, ~20% actively edited → 2M docs; an active typist sends ~2 ops/s after 50 ms client batching → ~5M ops/s peak at the edge, ~2M ops/s after batching.
• One op ≈ 100 bytes with metadata → 2M × 100 B ≈ 200 MB/s into the op log, ~17 TB/day before compaction.
• Connections: ~15M WebSockets (editors + viewers); at ~50K per gateway box → ~300 gateway hosts.
• Average doc ≈ 50 KB of content; 1B docs ≈ 50 TB of snapshots, plus history kept as snapshots every N ops.
• Presence (cursor moves) is chattier than edits, ~5–10 msg/s per user, but is never persisted.

API design

Transport is a WebSocket per open document. Edits and presence are small, frequent, bidirectional messages; HTTP polling adds latency and header overhead, and SSE is one-way so edits would still need a separate POST path. REST handles everything that is not live.

POST /v1/docs                         {title, folder_id}        → {doc_id, revision: 0}
GET  /v1/docs/{id}                    → {title, acl, snapshot, revision}
GET  /v1/docs/{id}/ops?from=1200      → {ops: [...], revision: 1350}   # catch-up
GET  /v1/docs/{id}/versions           → [{version_id, revision, author, created_at, name}]
POST /v1/docs/{id}/versions/{vid}/restore → {revision}
WS   /v1/docs/{id}/live?token=...

WebSocket messages:

client → server  {type: "join", known_revision: 1300, client_id}
server → client  {type: "joined", revision: 1350, missing_ops: [...] | snapshot}
client → server  {type: "op", client_id, client_seq: 42, base_revision: 1350, ops: [{retain: 10}, {insert: "hi", attrs: {bold: true}}]}
server → client  {type: "ack", client_seq: 42, revision: 1351}
server → client  {type: "op", revision: 1352, author, ops: [...]}
both             {type: "presence", user_id, cursor: {anchor, head}, revision}

Recovery after a disconnect: the client reconnects with known_revision plus its unacked ops. The server sends ops after known_revision (or a fresh snapshot if that gap is past compaction), the client transforms its pending ops over them and resends. client_id + client_seq makes resends idempotent.

Data model

Key invariants:

• Revisions per document are dense and strictly increasing; the session server is the only writer, so (doc_id, revision) is a natural primary key and a conditional insert catches a double-writer.
• (doc_id, client_id, client_seq) is unique, so a retried op is applied once.
• Any document state = snapshot at revision R + ops (R, head]. Ops are deleted only after a newer snapshot covers them and the history retention policy allows it.

High-level design

flowchart LR
  C[Browser client] -->|WebSocket| GW[WS gateway]
  C -->|REST| API[Doc API]
  GW -->|route by doc id| SS[Doc session server]
  SS --> LOG[(Op log)]
  SS --> PUB[Pub sub fanout]
  PUB --> GW
  API --> META[(Docs metadata SQL)]
  API --> SNAP[(Snapshot blob store)]
  CMP[Compaction workers] --> LOG
  CMP --> SNAP
  DIR["Shard directory etcd"] -.-> GW

A baseline that just appends every client op to a log and broadcasts it fails on concurrency: if Alice inserts at index 5 while Bob deletes index 2, replaying Alice's op on Bob's copy hits the wrong position. So the session server runs Operational Transformation (OT) with one central order per document.

1. Create. POST /docs writes a documents row with revision 0 and an empty snapshot. No session server is involved until someone opens it.
2. Join and load. The client fetches the latest snapshot plus metadata over REST (cacheable at the CDN for viewers), opens the WebSocket, and the gateway looks up which session server owns the doc in the shard directory. The session server loads the doc if not already in memory (snapshot + tail ops), replies with ops since the client's revision, and adds the connection to the doc's room.
3. Edit. The client applies the op locally right away, then sends it with base_revision. The session server transforms it against any ops committed after that base, assigns the next revision, appends to the op log (quorum write), acks the sender, and broadcasts the transformed op to everyone else in the room.
4. Presence. Cursor updates go to the same session server, are kept in memory only, throttled to ~10/s per user, and broadcast. Each cursor carries the revision it refers to, so receivers transform the position through any ops they have that the sender lacked.
5. Background. Compaction workers read the op log and write a new snapshot every ~1,000 ops or 10 minutes of activity; history views read snapshots plus ops.

Deep dives

OT mechanics and convergence. Each client holds three states: the last server-acked revision, one in-flight op batch, and a buffer of local ops typed since. Only one batch is in flight at a time, which keeps the protocol simple (the Jupiter/Google Wave model). When a remote op arrives, the client transforms it against the in-flight and buffered ops and transforms those against it, so local text never jumps. The server transforms an incoming op against every op in (base_revision, head].

• Ops are retain/insert/delete runs over the document's linear sequence (rich text attributes ride on retains and inserts), so transforms are a few rules.
• Example: head "abc", Alice inserts "X" at 1 (base 7), Bob deletes index 0 committed as rev 8. Server transforms Alice's op: the delete was before position 1, so the insert shifts to 0. Result "Xbc" everywhere.
• Ties (two inserts at the same index) break by a deterministic rule such as lower client_id first, so every replica picks the same order.
• Because the server serializes all ops for a doc, we only need transform property TP1; the harder TP2 needed by peer-to-peer OT is avoided. That is the main reason to pick central OT over decentralized schemes.

Routing and scaling WebSockets. All editors of a document must reach the same session server, because ordering is per document and held in memory. Gateways terminate TLS and WebSockets (~50K connections each) and are stateless. A shard directory (etcd) maps doc_id → session server via consistent hashing with virtual nodes; adding a server moves only ~1/N of docs. Each session server holds a lease per doc; on failure the lease expires (~5 s), another server takes ownership, reloads snapshot + tail from the op log, and clients reconnect with known_revision and replay unacked ops. The conditional insert on (doc_id, revision) guarantees a stale owner that lost its lease cannot write. A session server holds ~20K active docs; 2M active docs → ~100–150 servers with headroom. Hot docs get their own server.

Snapshots and compaction. Loading a doc by replaying 2M ops from creation is too slow, so the latest snapshot is at most ~1,000 ops behind head and a load reads one blob plus ≤1,000 rows. Compaction also squashes old ops: consecutive single-character inserts by one author within a few seconds merge into one op, typically 10–50× fewer rows. Ops older than the retention window are dropped once a snapshot covers them, keeping only snapshots at version boundaries. Snapshots are content-addressed blobs, so identical states (a restore) are stored once.

Offline editing. The client persists the snapshot, the acked revision, and its pending ops in IndexedDB, and keeps editing locally. On reconnect it sends known_revision and the pending ops; the server sends the missed ops, and the client rebases its pending ops over them before submitting. Rebasing a long offline branch (thousands of ops against thousands of remote ops) is O(n × m) transforms, so the client batches and compresses pending ops first. Past a threshold (say 24 h or 10K remote ops), the merge still converges but intent can be poor; show a "your offline changes were merged" notice and create a version just before the merge so it is reversible. If offline becomes the dominant mode, this is the point to move to a CRDT.

Version history and undo. History is a list of versions rows pointing at revisions: automatic ones every ~30 minutes of activity or when the set of editors changes, plus named versions. Viewing version V = nearest snapshot ≤ V + replay ops to V. Restore does not rewrite history; it computes a diff from head to V and commits it as a new op, so collaborators converge normally and the restore itself is undoable. Undo is per user: the client keeps its own ops' inverses and transforms each inverse through later remote ops before applying, so Ctrl+Z never removes someone else's text.

Also worth covering briefly:

• Viewers at scale: A doc with 10K viewers should not put 10K sockets on one session server. The session server publishes committed ops once to a pub/sub topic; gateways subscribe and fan out locally. Viewers send no ops, so presence for viewers is a count, not cursors.
• Memory: Session servers keep only docs with an open connection, evict after ~10 minutes idle (after flushing a snapshot), and cap per-doc op buffers; a doc's in-memory size is roughly its content plus the uncompacted tail.
• Permissions: The gateway checks the ACL on join and caches it; ACL changes publish a revoke event that closes or downgrades open sockets within seconds.

Trade-offs

• Central OT gives simple, proven convergence and small ops, but makes each document depend on one session server; a failover pauses that doc's edits for a few seconds (local typing continues).
• Choosing OT over CRDT gives up cheap, unlimited offline merging and peer-to-peer sync in exchange for smaller memory and easier rich-text semantics.
• Persisting every op before ack costs a quorum write (~5–10 ms) per batch, but means no acknowledged keystroke is lost on a crash.
• Not persisting presence keeps the log small and fast; cursors are lost on failover and simply reappear on the next move.
• Snapshot every ~1,000 ops trades storage and compaction CPU for fast loads and cheap history views; a longer interval saves storage but slows cold opens.
• Client batching at ~50 ms cuts server load by ~2–3× at the cost of slightly later remote updates.

Interviewer expectations

Mid-level (L4)

• Names the core problem: concurrent edits to the same index, and why a plain op log or last-write-wins loses data.
• Uses WebSockets, local echo, and a per-document op log with revisions; describes join and catch-up.
• Separates ephemeral presence from durable edits.

Senior (L5)

• Explains OT with a worked transform example, in-flight vs buffered ops on the client, and idempotent resend after reconnect.
• Routes every editor of a document to one owner with consistent hashing, leases, and a fencing check on the revision write.
• Designs snapshots + op tail for loading and history, with numbers for compaction cadence and storage.

Staff (L6+)

• Compares OT and CRDT on offline merges, memory, and rich-text semantics, and states when the choice flips.
• Handles failover end to end: lease expiry, stale owner fencing, client replay, and what the user sees.
• Covers viewer fan-out via pub/sub, restore-as-new-op, per-user undo through transforms, and ACL revocation on live sockets.