Problem RestatementProblem
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.
RequirementsRequirements
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=
High-Level ArchitectureArchitecture
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
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
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 --> DSHow 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:
Operational Transformation (OT) (Google Docs):- 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.
Key FlowsFlows
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
- Apply the edit locally at once, so it feels instant.
- Send the op to the session server.
- The server appends it to the log (durable), assigns a version and broadcasts it to others.
- 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).
Deep Dive A — Recalculating a spreadsheetDeep dive
Someone types a number into A1. A sheet with 200,000 filled cells and formulas several layers deep has to decide what that number changed.
Recalculate the whole sheet
On every edit, evaluate every formula in the sheet from scratch.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
E["A1 = 42"] --> ALL["Evaluate all 200,000 formulas"]
ALL --> T["Hundreds of milliseconds to seconds"]
T --> TYPE["Every keystroke in a collaborative session triggers it"]
TYPE --> FREEZE["Sheet freezes while several people type"]The work is proportional to the size of the sheet rather than to the size of the change, and in a collaborative document the edits arrive continuously from several people at once.
Recalculate the cells that reference the edited one
Find formulas mentioning A1 and re-evaluate those. For C1 = A1 + B1, that is one cell instead of two hundred thousand.
Correct for one level and wrong beyond it. If D1 = C1 * 2 and E1 = SUM(D1:D50), those still hold stale values — the change stopped one hop from where it started. Re-running the direct dependents repeatedly until nothing changes fixes the result and can evaluate a cell many times over, in an order that depends on iteration luck.
A dependency graph, evaluated in topological order
When a formula is saved, record its edges: C1 = A1 + B1 stores A1 → C1 and B1 → C1. An edit walks the graph forward to collect everything transitively affected, sorts it topologically, and evaluates each cell exactly once, in an order where its inputs are already final.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
A1["A1 changed"] --> C1["C1 = A1 + B1"]
C1 --> D1["D1 = C1 * 2"]
D1 --> E1["E1 = SUM(D1:D50)"]
A1 --> DIRTY["Collect transitive dependents"]
DIRTY --> TOPO["Topological sort - each cell evaluated once"]
TOPO --> DONE["Everything else untouched"]The work is now proportional to what actually depends on the edit, which in a real sheet is usually a handful of cells.
Three things to raise before the interviewer does:
- Cycles.
A1 = B1andB1 = A1has no topological order. Detect it during the walk and surface a circular-reference error rather than looping. - Structural edits are not cell edits. Inserting a row or deleting a column shifts the references inside every formula that points past it. These are operations that have to be transformed against concurrent edits, exactly as text insertions are.
- Store cells sparsely — a map from
(sheet, row, col)to{ value, formula }. A million-row sheet is almost entirely empty, and a dense array of it is the other way to run out of memory.
For very large sheets, load only the visible range plus whatever the formulas in it need, and keep heavy recalculation on the server rather than shipping the whole dependency graph to a browser tab.
Deep Dive B — Scale and reliabilityScale
- 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).
Trade-offs & AlternativesTrade-offs
| Decision | Choice | Why | Alternative |
|---|---|---|---|
| Merge algorithm | CRDT (Yjs) | Order-independent, great offline | OT: less metadata, needs a central orderer |
| Session topology | One server owns each doc | Simple ordering and presence | Any server + shared DB locks: slow |
| Storage | Op log + periodic snapshots | Fast load, full history | Save whole doc on every keystroke: wasteful |
| Sheets recalculation | Dependency graph, recalc only affected cells | Fast on big sheets | Recalculate everything: slow |
Common Follow-up QuestionsFollow-ups
- "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.
Wrap-UpWrap-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.