Design Google Docs (Collaborative Real-time Document Editing)

Google Docs enables multiple users across different continents to simultaneously edit the same document in real time, view collaborators' cursor positions, and resolve concurrent typing collisions without data loss or UI freezing.

1. System Requirements

Functional Requirements

1. Real-time Concurrent Editing: Multiple users can edit the same document simultaneously, seeing each other's changes in under 100ms.
2. Conflict Resolution & Convergence: If two users type at the exact same cursor position simultaneously, the final document state must converge identically for all participants.
3. Presence & Caret Tracking: Display collaborators' live cursor coordinates and selection highlights.
4. Version History & Restore: View point-in-time snapshots and roll back to previous revisions.
5. Offline Editing & Re-sync: Allow users to edit offline and merge modifications when internet connectivity returns.

Non-Functional Requirements

1. Low Sync Latency: End-to-end operation dissemination latency $< 100\text{ms}$ globally.
2. Consistency Guarantee: Eventual consistency with strict convergence guarantees (no lost keystrokes).
3. Availability & Scalability: 99.99% availability; support up to 100 concurrent active typers on a single document.
4. Durability: Zero data loss upon browser refresh, crash, or server failure.

2. Capacity & Scale Estimation

• Daily Active Users (DAU): $100\text{ Million}$
• Concurrently Open Documents: $5\text{ Million}$
• Average Keystrokes / Edits per Active Document: 5 operations per second.
• System Peak Ingress Operations: $5\text{ Million} \times 5 = 25\text{ Million ops/sec}$.
• Average Operation Payload: 64 bytes (character, index/ID, timestamp, user_id).
• Network Throughput: $25 \times 10^6 \times 64\text{ bytes} \approx 1.6\text{ GB/sec}$.

3. Architecture Blueprint

                                  +-----------------------+
                                  |   Collaborator A/B    |
                                  +-----------+-----------+
                                              |
                                              | WebSockets (WSS)
                                              v
                                  +-----------------------+
                                  |     Load Balancer     |
                                  | (Session Sticky Hash) |
                                  +-----------+-----------+
                                              |
                                              v
                                  +-----------------------+
                                  | Document Room Server  |
                                  |   (In-Memory Actor    |
                                  |  Engine & OT/CRDT Hub)|
                                  +-----+-----------+-----+
                                        |           |
             +--------------------------+           +--------------------------+
             |                                                                 |
             v Broadcast (Redis Pub/Sub)                                       v Async Snapshot (10s)
+------------------------+                                         +------------------------+
| Other Room Servers     |                                         | Document Storage Svc   |
| (Multi-region replicas)|                                         | (PostgreSQL + S3 Docs) |
+------------------------+                                         +------------------------+

4. Conflict Resolution: OT vs. CRDT

Operational Transformation (OT)

Used historically by Google Docs.

• Concept: When an operation arrives that was executed against an older document version, the server transforms the operation's position offset against concurrent operations.
• Pros: Compact payload size (only sends Insert('x', at: 14)); low memory overhead.
• Cons: Requires a centralized single-threaded server per document to establish global operation ordering; computationally complex transformation matrices.

Conflict-Free Replicated Data Types (CRDTs)

Used by Figma, Apple Notes, and modern collaborative platforms (Yjs, Automerge).

• Concept: Every character is assigned a unique, immutable fractional identifier (e.g. between position 1.0 and 2.0, insert 1.5).
• Pros: Peer-to-peer friendly, highly decentralized, mathematically guaranteed convergence without a single central sequencer.
• Cons: Memory overhead per character (stores metadata IDs and tombstones for deletions).

5. Staff-Level Deep Dives

Deep Dive 1: The Centralized Document Room Actor Pattern

To avoid distributed consensus overhead on every keystroke:

1. Each active document is hosted on a specific Document Room Server using consistent hashing on document_id.
2. The server holds the canonical document state in RAM.
3. Inbound user keystrokes are processed sequentially in a single event loop.
4. The server assigns an incrementing monotonic revision_number (e.g., rev 104) and broadcasts the acknowledged operation to all connected sockets.
5. Clients receive the transformed delta and adjust their local visual trees.

Deep Dive 2: Snapshotting & Compaction

• Typing thousands of characters generates millions of incremental operations.
• A background worker periodically creates a compressed snapshot of the full document state every 100 revisions or every 10 seconds.
• Older operational logs are archived to cold object storage (S3/GCS), keeping document load times sub-second for new joiners.

Deep Dive 3: Disconnected & Offline Sync

• While offline, the client logs operations in an IndexedDB append-only queue.
• When reconnected, the client transmits its local change vector.
• Using CRDTs or three-way merge algorithms, local offline edits are interleaved into the server state without overriding remote colleagues' work.

Key Architecture Trade-Offs & Decision Matrix