Real-Time Collaborative Editor (Google Docs / Sheets)

0) Problem Restatement

Design a real-time collaborative editor like Google Docs, or a spreadsheet like Google Sheets. Several people open the same document, type at the same time, and see each other's changes and cursors almost instantly. Even when two people edit the same sentence at the same moment, everyone must end up with the same document. Users also need version history and offline editing. In a spreadsheet, formulas like =SUM(A1:A10) must recalculate when the cells they use change.

1) Requirements

1.1 Functional

• Open a document and edit it together in real time.
• See other users' cursors and selections (presence).
• Version history, with restore.
• Offline edits that sync later.
• Sheets: cells, formulas and recalculation.
• Sharing and permissions (view, comment, edit).

1.2 Non-Functional

• Low latency: your own typing appears instantly (applied locally), and others see it within ~100–300 ms.
• Convergence: all copies end up identical.
• Durability: no lost edits.
• Scale: millions of documents open. Most have 1–3 editors, a few have 100+.

1.3 Scale Estimates

• 10M documents open at peak, 20M connected users.
• Typing produces ~5 operations/sec per active editor → millions of ops/sec in total, but each document's stream is small.
• Storage: an operation log per document, compacted into snapshots.

1.4 API Design

• GET /v1/docs/{id} → latest snapshot + version
• WebSocket /v1/docs/{id}/session:
• client → server: { op, base_version, client_id, seq }
• server → clients: { op, version, author }, plus presence updates
• GET /v1/docs/{id}/history, POST /v1/docs/{id}/restore?version=

2) High-Level Architecture

2.1 Overview

• Document service: loads snapshots, checks permissions and saves versions.
• Collaboration (session) servers: every open document is owned by one session server at a time (chosen by consistent hashing on doc ID). All editors of that doc connect there. The server orders operations, transforms or merges them, and broadcasts.
• Operation log: a durable append-only log per document (e.g., a DB table or Kafka).
• Snapshotter: periodically folds the log into a full snapshot so loading is fast.
• Presence: cursor positions are in memory only (not saved).

2.2 Architecture Diagram

flowchart LR
    A["Editor A"] -->|"WebSocket ops"| SS["Session server - owns doc 123"]
    B["Editor B"] -->|"WebSocket ops"| SS
    SS -->|"ordered ops"| A
    SS -->|"ordered ops"| B
    SS --> LOG[("Operation log")]
    LOG --> SNAP["Snapshotter"]
    SNAP --> ST[("Snapshots + version history")]
    DS["Document Service - load, permissions"] --> ST
    A --> DS

3) How Concurrent Edits Converge

Say the text is "HELLO". At the same moment, A inserts "!" at position 5 ("HELLO!") and B deletes the character at position 0 ("ELLO"). If we apply A's op on B's copy unchanged, we insert at position 5 of "ELLO", which is past the end, so the copies diverge. Two families of solutions:

• The server gives every operation a version number and applies them in one order.
• When an operation was made against an older version, the server transforms it against the operations that came before it. Here, B's delete at 0 shifts A's insert from position 5 to position 4.
• Clients apply their own ops immediately, then transform incoming ones against their pending local ops.
• It needs a central server to order operations, which fits our "one session server per doc" design.

• Every character gets a unique, ordered ID (not a position). Inserts reference neighbor IDs, and deletes mark IDs as removed.
• Operations can be applied in any order and still converge. Good for offline and peer-to-peer.
• Costs: extra metadata per character, and garbage collection of deleted items.

4) Key Flows

4.1 Opening a document

Load the latest snapshot plus log entries after it, connect to the doc's session server (the router finds the owner), and receive current presence.

4.2 Typing

1. Apply the edit locally at once, so it feels instant.
2. Send the op to the session server.
3. The server appends it to the log (durable), assigns a version and broadcasts it to others.
4. Others merge it (CRDT) or transform it (OT) and update their view.

4.3 Offline

Edits queue locally. On reconnect, they're sent. The CRDT merges them automatically (with OT, the server transforms them against everything missed).

5) Deep Dive A — Spreadsheets

• Data model: store cells sparsely, as a map from (sheet, row, col) → { value, formula }. Most cells are empty.
• Dependency graph: when a formula like C1 = A1 + B1 is saved, record the edges A1 → C1 and B1 → C1. When A1 changes, find all dependent cells (in topological order) and recalculate only those. Detect cycles and show an error.
• Concurrent edits to the same cell: last write wins by server order. Structural edits (insert row, delete column) are operations that shift references, and they need transforms like text edits do.
• Huge sheets: load only the visible range plus what's needed for formulas, and recalculate heavy sheets on the server.

6) Deep Dive B — Scale and reliability

• One owner per doc: sticky routing by doc ID keeps ordering simple. If a session server dies, another takes ownership and rebuilds from snapshot + log. Clients reconnect and resend unacknowledged ops (deduplicated by client_id + seq).
• Popular docs (100+ editors, 1,000s of viewers): editors connect to the owner, while viewers can get updates through a fan-out layer.
• Snapshots every N ops (e.g., 500) or minutes keep load times short. History is kept as named versions plus the compacted log.
• Permissions are checked when the session opens and re-checked when sharing changes (disconnect users who lost access).

7) Trade-offs & Alternatives

8) Common Follow-up Questions

• "Comments and suggestions?" Anchor comments to CRDT character IDs (not positions), so they stay attached as text changes.
• "Why not lock paragraphs?" Locks feel slow and block people. Merge algorithms let everyone type freely.
• "How do you show cursors?" Presence messages (cursor position as a CRDT ID) are broadcast but never saved.

9) Wrap-Up

Route every open document to one session server, send edits over WebSockets, apply them locally at once, and converge copies with a CRDT (or OT with server ordering). Persist an append-only operation log compacted into snapshots for fast loading and history. For spreadsheets, store cells sparsely and recalculate only dependent cells using a formula dependency graph.