Design Google Docs

Google Docs is a browser-based collaborative document editor where multiple users can create, edit, and view rich text documents in real-time. The core challenge is enabling concurrent editing while maintaining consistency across all collaborators.

This walkthrough follows the Interview Framework. Use it as a guide, not a script—adapt based on interviewer cues.

Phase 1: Requirements

Functional Requirements

1. Create documents — Users can create new documents
2. Concurrent editing — Multiple users can edit the same document simultaneously
3. Real-time updates — Users see each other's changes as they happen
4. Presence awareness — Users can see cursor positions and who's currently editing

Out of Scope

• Sophisticated document structure (rich text formatting, tables, images)
• Permissions and access control
• Document version history and restoration
• Comments and suggestions
• Offline editing

Non-Functional Requirements

Capacity Estimation

Assumptions:

• 80M daily active users (DAU)
• Average document size: 100 KB (text only)
• 1 document created per user per day

Storage:

• Documents per day: 80M
• Text storage: 80M × 100 KB = 8 TB/day

Throughput:

• If each user makes ~10 edits/minute while active
• Peak concurrent users: ~10M
• Edit operations: 10M × 10 = ~100M ops/minute or ~1.7M ops/sec globally

Phase 2: Data Model

Core Entities

Document
├── id: UUID
├── title: string
├── created_at: timestamp
└── owner_id: UUID

Operation
├── id: UUID
├── document_id: UUID
├── revision: integer (server-assigned, sequential per document)
├── base_revision: integer (client's last-seen revision)
├── user_id: UUID
├── type: "insert" | "delete"
├── position: integer
├── content: string (for insert)
└── length: integer (for delete)

Editor (ephemeral)
├── user_id: UUID
├── document_id: UUID
├── cursor_position: integer
└── last_active: timestamp

Key Design Decisions

Why store operations, not document snapshots?

• Operations are small (bytes vs. kilobytes)
• Enables conflict resolution via transformation
• Supports efficient sync; history can be layered on later (out of scope)
• Documents reconstructed by snapshot + subsequent operations (or full replay if no snapshot)

Why revision numbers?

• Server-assigned revisions track operation ordering per document
• Client base_revision lets the server detect concurrent edits and transform ops
• Idempotency comes from unique operation IDs (reject duplicate op_id)

Why is Editor ephemeral?

• Cursor positions only matter while user is connected
• No need to persist—stored in memory on Document Service
• Cleaned up on disconnect

Phase 3: API Design

We need two types of communication:

1. REST APIs for document management (create, list, delete)
2. WebSocket for real-time collaborative editing

REST Endpoints

POST /docs
  Request:  { "title": "Untitled Document" }
  Response: { "doc_id": "abc123" }

GET /docs/{doc_id}
  Response: { "doc_id": "abc123", "title": "...", "created_at": "..." }

WebSocket Messages

WS /docs/{doc_id}

// Client → Server
SEND { type: "insert", op_id: "u1-123", position: 5, content: "hello", base_revision: 42 }
SEND { type: "delete", op_id: "u1-124", position: 5, length: 3, base_revision: 42 }
SEND { type: "cursor", position: 8 }

// Server → Client
RECV { type: "operation", user_id: "...", op: {...}, revision: 43 }
RECV { type: "cursor", user_id: "...", position: 12, name: "Alice" }
RECV { type: "presence", users: [...] }
RECV { type: "ack", op_id: "u1-123", revision: 43 }

Phase 4: High-Level Design

Architecture Overview

Note: WebSocket connections initially hit any Document Service instance; the server can return the target host so clients reconnect, or the LB can route by document hash. Many WS clients do not follow HTTP redirects automatically.

Component Walkthrough

1. Creating a Document

Simple CRUD operation. Generate UUID, store title and owner, return to client.

2. Opening a Document for Editing

When a user opens a document, they establish a WebSocket connection:

1. Client connects to any Document Service (via load balancer)
2. Document Service checks ZooKeeper for which server owns this document's hash range
3. If wrong server, redirect client to correct server
4. Load latest snapshot (if any) + subsequent operations from Operations DB
5. Send current document state + active editors to client
6. Add client to in-memory subscriber list

3. Making an Edit

This is where it gets interesting. The naive approach fails:

The solution is Operational Transformation (OT).

Operational Transformation Deep Dive

OT is a conflict resolution technique that transforms operations to account for concurrent edits. The key insight: operations are contextual—they assume a specific document state.

How OT Works

When concurrent operations conflict, OT transforms them so they can be applied in any order and produce the same result.

Example:

Document: Hello! (positions 0-5)

• User A: INSERT(5, ", world")
• User B: DELETE(5) (delete the "!")

Without OT: Result depends on arrival order—broken.

With OT:

• Server receives A's insert first, applies it: Hello, world!
• Server transforms B's DELETE(5): since A inserted 7 characters at position 5, B's target shifted from position 5 to position 12. Transform: DELETE(5) → DELETE(12)
• Apply transformed delete: Hello, world ✓

Both users converge to the same state regardless of network timing.

OT Properties

For correctness, OT must satisfy:

1. Causality preservation — If operation A happened before B, A executes first
2. Convergence — All replicas eventually reach identical state

Client-Side OT

Here's the subtle part: clients also run OT locally.

When you type, changes apply immediately to your local document (for responsiveness). But what if another user's edit lands on the server before yours?

Your local state: "Hello, world!" (you added ", world")
Server state: "Hello!" → "Hello" (Bob deleted "!")

When you receive Bob's operation:

1. Transform it against your pending local operations
2. Apply the transformed operation to your local document
3. Both clients converge to the same state

OT vs. CRDTs

Phase 5: Scaling & Deep Dives

Deep Dive 1: Scaling WebSocket Connections

Problem: A single Document Service server can't handle millions of connections.

Solution: Consistent hashing to route all editors of a document to the same server.

Connection flow:

1. Client connects to any server with document ID
2. Server computes hash, checks ring config in ZooKeeper
3. If wrong server, respond with redirect to correct server
4. Client reconnects directly to the correct server
5. All editors of same document connect to same server

Why this works:

• Co-located connections can broadcast updates in-memory
• No cross-server communication for real-time sync
• Adding/removing servers only moves ~1/N of documents

Challenges:

• Server failures require quick redistribution
• Adding servers requires connection migration
• Hot documents (many editors) could overload a single server

Deep Dive 2: Cursor and Presence

Cursor positions are ephemeral—they only matter while users are connected.

Design:

• Document Service maintains in-memory map: document_id → {user_id → cursor_position}
• On cursor update: broadcast to all connected editors (no persistence)
• On disconnect: remove from map, broadcast departure
• On connect: send current presence list to new editor

Why no database?

• Cursor position changes constantly (every keystroke)
• Data is meaningless after disconnect
• In-memory is fast enough (sub-millisecond broadcast)

Deep Dive 3: Storage Optimization

Problem: A document with millions of operations becomes expensive to:

• Store (unbounded growth)
• Load (replay all ops on open)
• Transfer (new editors wait too long)

Solution: Periodic snapshots with operation compaction.

Implementation:

• Background worker periodically creates snapshots
• Snapshot = full document state at a specific revision
• Delete operations older than snapshot
• On document load: fetch snapshot + subsequent operations

Trade-offs:

• Snapshots reduce load time; history can be added later if needed (out of scope)
• Compaction frequency balances storage vs. load time
• Must coordinate with active editors during compaction
• If full history is required, keep older ops in cold storage instead of deleting

Deep Dive 4: Handling Server Failures

Scenario: Document Service server crashes with 1000 active documents.

Recovery:

1. ZooKeeper detects failure (heartbeat timeout)
2. Update hash ring, assign ranges to other servers
3. Clients detect WebSocket disconnect
4. Clients reconnect, get redirected to new server
5. New server loads operations from Cassandra
6. Clients receive current state, resume editing

Data durability:

• Operations persisted to Cassandra before ACK to client
• Client retries unacknowledged operations on reconnect
• At-least-once delivery; op_id ensures idempotency (duplicate ops ignored)

Common Pitfalls

Interview Checklist

Before finishing, verify you've covered:

• Explained why WebSockets over HTTP
• Described OT (or CRDT) for conflict resolution
• Addressed how multiple editors connect to same server
• Explained operation storage vs. document snapshots
• Discussed cursor/presence handling
• Covered failure scenarios and recovery
• Mentioned storage optimization (snapshots/compaction)

Summary