Design Google Docs (Collaborative Document Editor)

#Problem Statement

Design a collaborative document editing system where multiple users can edit the same document simultaneously and see each other's changes in real-time, without conflicts.

📖

Real-world: This problem birthed two competing algorithm families with a genuine history. Operational Transformation (OT) — the approach Google Docs actually uses — dates back to a 1989 research system (GROVE) and works by transforming concurrent edits so they apply consistently (if you insert at position 5 while I delete at position 2, the system rewrites your operation to land correctly). OT is powerful but notoriously hard to implement right — Google engineers have said it took enormous effort to get correct. The challenger is CRDTs (Conflict-free Replicated Data Types), which structure the data so concurrent edits mathematically can't conflict and merge deterministically without a central server — the foundation of newer tools like Figma and local-first apps. The interview decision is OT (server-coordinated, compact) vs CRDT (peer-friendly, heavier metadata). Security angle: real-time collab means fine-grained access control and per-keystroke audit — who could see/edit which doc at which moment — plus the WebSocket layer is its own attack surface.

#Requirements

#Functional

• Real-time collaborative editing (multiple users, same document)
• Persistent storage of document state
• Edit history / version control
• User presence (who's currently viewing/editing)
• Comments and suggestions
• Offline editing with sync on reconnect

#Non-Functional

• 1B documents; 50M DAU
• Conflict resolution: users see consistent state within 100ms
• No data loss: every keystroke eventually persisted
• Highly available (offline mode works)

#Core Design

#The Central Challenge: Concurrent Edits

User A deletes character at position 5 while User B inserts at position 3. If applied in sequence, they corrupt each other's document state. How do you merge them correctly?

#Operational Transformation (OT)

The original collaborative editing approach (used by Google Docs).

Key ideatransform an operation against concurrent operations so it remains correct when applied after them.

Initial: "Hello World"
User A: delete position 6 (delete 'W') → "Hello orld"
User B: insert 'X' at position 6 → "Hello Xorld"

Without transformation:
  Apply A then B: "Hello Xorld" (correct)
  Apply B then A: User A deletes 'X' instead of 'W' (wrong!)

With OT:
  transform(delete_6, insert_6) → delete_7 (shift A's operation by 1)
  Apply B then transform(A): "Hello Xorld" → delete pos 7 → "Hello Xorld" ✓

OT works well for single-type documents (text) but becomes complex for rich documents with many operation types.

#CRDT (Conflict-free Replicated Data Type)

Modern approach (used by Figma, Notion, Linear).

Key ideadesign the data structure so concurrent operations can always be merged without conflict. Each character gets a globally unique ID; positions are logical (not integer indices).

Character IDs: A's insert gets ID (userA, seq1), B's gets (userB, seq1)
Order: determined by ID comparison, not position
→ Concurrent inserts at the same position have deterministic ordering by user ID
→ Merge is always possible, always correct

Popular CRDTs: Yjs, Automerge (both open-source, production-proven).

OT vs CRDT

#Architecture

Client (browser/mobile)
  - Local document state (CRDT or OT buffer)
  - WebSocket connection to Collaboration Server
          ↓
Collaboration Server (stateful, per document)
  - Maintains connected clients for each document
  - Receives operations, transforms/merges, broadcasts
  - Persists operations to Operation Log
          ↓
  ┌────────────────────────────────┐
  │ Operation Log (Kafka / DB)     │  ← append-only, every edit
  │ Document Snapshot Store (S3)   │  ← periodic full snapshots
  │ Session Store (Redis)          │  ← who's connected, cursor positions
  └────────────────────────────────┘

#Operation Log + Snapshots

Storing every operation is expensive to replay from scratch. Periodic snapshots:

snapshot at version 1000 + operations 1001-1050 = current state at version 1050

Compaction: after snapshot, old operations can be archived.

#Presence and Awareness

Redis (per document):
  doc:{doc_id}:users → set of { user_id: cursor_position, color, name }
  TTL: 30s (refresh on heartbeat)

WebSocket broadcast: when user moves cursor or selection changes,
broadcast to all other connected clients for the same document

#Key Design Decisions

#Security Considerations

#Interview Tips