Design: Collaborative Document Editor (Google Docs)¶

Difficulty: Senior → Staff | Time: 60–75 minutes

1. Problem Statement¶

Design a collaborative document editor like Google Docs: multiple users open the same document and type simultaneously, each seeing the others' keystrokes appear in near-real time, with visible cursors showing where everyone else is working.

Every other exercise on this site is either request/response (rate limiter, pastebin) or eventual convergence of independent writes made at different times (a CRDT counter that syncs on reconnect). This is neither. Two users can be typing in the same paragraph, at the same moment, and both edits must land, in an order every client agrees on, within about 100ms of being typed — with no central server holding a lock and no user ever seeing their keystroke silently vanish because someone else typed first. The problem is not "the data eventually agrees." It's "the data is being mutated by multiple writers right now, live, in front of both users' eyes, and it still has to converge."

Do not reach for "just use a database with row locking." A lock held for the duration of a keystroke destroys the product — nobody will type through 100ms locks contested by a stranger.

2. Clarifying Questions¶

3. Functional Requirements¶

• Multiple users open the same document and edit concurrently
• Every keystroke from any editor is visible to all other connected editors, in a consistent merged order
• Show live cursor position and selection range for each connected user
• Local edits appear instantly for the typist (no waiting on the network)
• Reconnect after a brief disconnect without losing local unsynced edits or duplicating them
• Persist the document so it survives server restarts and can be reopened later

4. Non-Functional Requirements¶

5. Capacity Estimation¶

Documents:
  5M documents opened/day
  Avg session length: 8 minutes → concurrent open docs (Little's law): 5M × 8 / 1,440 ≈ 28K
  Of those, most are single-editor (someone alone in a doc) — only a fraction are truly multi-editor

Concurrent editing sessions (the interesting number):
  Assume 5% of open documents have >=2 concurrent editors → ~1,400 actively co-edited docs
  Avg concurrent editors per actively co-edited doc: ~2.5 → ~3,500 presence users
  Viral tail: ~50 documents at any moment with 100-500 concurrent editors (all-hands doc, shared spec)

WebSocket connections:
  ~28K open docs × ~1.3 avg connections/doc (most solo, some multi) ≈ 36K concurrent WebSocket connections

Keystrokes:
  Average typist: ~5 keystrokes/second while actively typing, but only ~20% of connected time is active typing
  36K connections × 5 keys/s × 20% active ≈ 36K operations/second system-wide (before batching)
  Batched into ~50ms send windows client-side → ~20 op-batches/second/active typist, not 5 raw sends/s

Presence/cursor updates:
  ~3,500 co-editor users × 5 updates/s (200ms cadence) ≈ 18K presence msgs/s
  Presence is still high volume relative to text ops and must NOT compete with them for bandwidth/priority

Storage:
  Avg document: 20 KB of text, plus operation log
  5M new/edited docs/day × ~5 KB of new ops/day/doc ≈ 25 GB/day of raw op-log before compaction
  Snapshot-compacted storage: ~5M docs × 20 KB ≈ 100 GB total resident text

6. API Design¶

# Open a document / establish the real-time channel
WS  /v1/docs/{doc_id}/connect
    → on connect: server sends { "snapshot": "...", "version": 4821, "presence": [...] }
    Client then sends and receives operations over this socket for the session's duration.

# Client → server: an edit operation (batched, not one frame per keystroke)
{
  "type": "op",
  "doc_id": "abc123",
  "client_id": "u42-session9",
  "base_version": 4821,
  "ops": [ { "insert": "h", "pos_id": "<crdt-position-id>" }, ... ]
}

# Server → all connected clients (including a version for the sender's own reconciliation)
{
  "type": "op_broadcast",
  "doc_id": "abc123",
  "from": "u42-session9",
  "ops": [ ... ],
  "version": 4822
}

# Presence — separate, lower-guarantee channel, same socket
{ "type": "presence", "client_id": "u42-session9", "cursor_pos": 118, "selection": [118, 130], "color": "#3a7" }

# REST — document lifecycle, not the hot edit path
POST /v1/docs                          → create, returns doc_id
GET  /v1/docs/{doc_id}                 → latest snapshot (for non-realtime preview / SEO / export)
GET  /v1/docs/{doc_id}/history         → version snapshots for time-travel

7. Data Model¶

Same split instinct as Pastebin — separate the hot mutable object from its durable record — but here the "hot object" is actively being co-mutated, not just read.

-- Durable snapshot: the document as of the last compaction point. Not the hot path during active editing.
CREATE TABLE document_snapshots (
    doc_id        VARCHAR(32) PRIMARY KEY,
    content       TEXT NOT NULL,           -- or CRDT-serialized structure, not raw text, if compaction keeps CRDT metadata
    version       BIGINT NOT NULL,         -- monotonic, matches last applied op in the log
    updated_at    TIMESTAMPTZ NOT NULL
);

-- Operation log: append-only, replayable, source of truth between snapshots
CREATE TABLE doc_operations (
    doc_id        VARCHAR(32) NOT NULL,
    version       BIGINT NOT NULL,         -- monotonic per doc
    client_id     VARCHAR(64) NOT NULL,
    op_payload    JSONB NOT NULL,          -- CRDT op: {insert/delete, position_id, value}
    applied_at    TIMESTAMPTZ NOT NULL,
    PRIMARY KEY (doc_id, version)
);

Presence: ephemeral, never persisted to durable storage.
  presence:{doc_id} → Redis hash, one field per connected client_id
    { cursor_pos, selection_range, color, display_name, last_seen_ts }
  TTL'd aggressively (2-3s) — a disconnected client's cursor should vanish fast, not linger as a ghost.

The operation log is the CRDT's real substance — it's what lets a reconnecting or newly-joining client replay from a snapshot to current state, and what makes "two edits landed in the same region" resolvable instead of a last-writer-wins coin flip.

8. Version 1 — simplest thing that works¶

One server process holds the document in memory. Every connected client's WebSocket routes through it. Edits broadcast to everyone else. Conflicting edits: last-writer-wins by arrival order at the server.

graph LR
    A[Client A] <-->|WebSocket| S[Single editing server\nin-memory document]
    B[Client B] <-->|WebSocket| S
    C[Client C] <-->|WebSocket| S
    S -->|periodic flush| PG[(Postgres snapshot)]

# V1 — single process, last-writer-wins on overlapping edits
class DocSession:
    def __init__(self, doc_id, initial_text):
        self.text = initial_text
        self.clients = {}   # client_id -> websocket

    def apply_edit(self, client_id, pos: int, insert: str, delete_len: int):
        # last writer wins: whoever's edit reaches this line last simply
        # mutates self.text at `pos` as given, with no regard for what
        # another concurrent edit already did to the indices around it
        self.text = self.text[:pos] + insert + self.text[pos + delete_len:]
        self.broadcast(client_id, pos, insert, delete_len)

    def broadcast(self, from_client, pos, insert, delete_len):
        for cid, ws in self.clients.items():
            if cid != from_client:
                ws.send({"pos": pos, "insert": insert, "delete_len": delete_len})

This works for the demo: two people, low latency, edits in different parts of the document. Ship it behind a flag for small teams before adding any infrastructure.

9. Identify the bottleneck¶

10. Version 2 — OT or CRDT merge, and horizontal sharding¶

The core fix: replace "apply blindly, last write wins" with a merge function that makes concurrent edits at the same position both survive, deterministically, on every replica. This is a choice, not a single correct answer. Google Docs uses OT; many newer editors use CRDTs. Either is a complete interview answer if you can name the trade-off.

• Operational Transformation (OT): the original Google Docs approach (and still what Docs uses). Every operation is transformed against every concurrent operation it might have raced with, so it can be reapplied correctly regardless of arrival order. Requires a central server to establish a canonical operation order (or a carefully specified transform function per operation pair) — the transform functions are notoriously easy to get subtly wrong, and correctness has historically required extensive testing against adversarial interleavings.
• CRDT (specifically an RGA-family sequence CRDT): each character gets a unique (replica_id, logical_counter) identity plus a reference to its logical predecessor, as covered in CRDTs — RGA. Concurrent inserts at the same position are ordered by a deterministic tie-break rule every replica applies identically, so both A's and B's characters survive, in a consistent order, with no central server required to establish canonical order — merge is just "apply the op, compare IDs on ties."

This walkthrough uses CRDT (RGA) from here on so the rest of the page has one concrete merge engine to hang architecture on — not because CRDT is "what Google Docs does" (it isn't) and not because OT is invalid. OT is what Docs shipped; CRDT is the more common from-scratch pick today because merge is a local structural comparison, and the same function handles live typing and offline/reconnect. The costs: per-character metadata, and you still usually pin a document to an owning editing server for fan-out even if merge itself needs no sequencer. See CRDTs for the mechanics — this page won't re-derive (replica_id, counter) tie-breaking here.

Horizontal scaling: shard documents across editing server instances. One process can no longer hold every open document. Route each doc_id to an owning server via consistent hashing — adding or removing editing servers reshuffles only ~1/N of documents instead of every open session, which matters because a full reshuffle would disconnect every active editor simultaneously.

graph TD
    Client -->|WS connect doc_id| GW[WebSocket Gateway]
    GW -->|consistent hash doc_id| ES1[Editing Server 1\nCRDT merge engine]
    GW -->|consistent hash doc_id| ES2[Editing Server 2\nCRDT merge engine]
    ES1 -->|op log append| PG[(Postgres: ops + snapshots)]
    ES2 -->|op log append| PG

# V2 sketch — RGA insert, replica-tagged, deterministic tie-break
def apply_insert(doc: RGA, op: InsertOp):
    # op.id = (replica_id, logical_counter); op.after = predecessor element id
    # concurrent inserts with the same `after` are ordered by comparing
    # (replica_id, logical_counter) — every replica applies the same rule,
    # so A's and B's concurrent characters both land, in the same order everywhere
    doc.insert_after(op.after, op.id, op.value)

Two clients typing in the same spot at the same moment never blindly overwrite each other — both inserts land, and the tie-break rule is what guarantees every replica orders them identically without asking a server which one "won":

sequenceDiagram
    participant CA as Client A (replica_id=A)
    participant CB as Client B (replica_id=B)
    participant ES as Editing Server (CRDT merge)

    note over CA,CB: both start from the same base state,\ncursor at the same position (after element X)

    CA->>ES: InsertOp { id: (A, 7), after: X, value: "!" }
    CB->>ES: InsertOp { id: (B, 4), after: X, value: "?" }

    ES->>ES: apply (A,7) — no existing child of X yet, insert
    ES->>ES: apply (B,4) — X already has child (A,7); both are\nconcurrent inserts "after X" — tie-break by comparing\n(replica_id, counter): B < A, so (B,4) sorts before (A,7)
    note over ES: deterministic order: X -> (B,4) "?" -> (A,7) "!"

    ES-->>CA: broadcast (B,4) "?" (A already has its own op)
    ES-->>CB: broadcast (A,7) "!" (B already has its own op)

    note over CA,CB: both clients apply the same tie-break rule locally\nand converge to identical text: ...X?! — no coordinator involved,\nand no server-imposed "who typed first"

11. Identify the next bottleneck¶

12. Version 3 — production architecture¶

graph TD
    C1[Client A] -->|WS| GW[WebSocket Gateway layer\nstateless, horizontally scaled]
    C2[Client B] -->|WS| GW
    C3[Client C - 500 editors] -->|WS| GW

    GW -->|consistent hash doc_id| ES[Editing Server\nowns doc_id, holds live CRDT state]
    ES -->|fan-out via pub/sub, not direct socket loop| PS[(Pub/Sub: per-doc topic)]
    PS -->|subscribe| GW

    ES -->|append op| OL[(Operation log - append-only)]
    OL -->|periodic compaction| SNAP[(Snapshot store)]
    SNAP -->|cold load on doc open| ES

    PRES[Presence Service\nRedis, short TTL] <-->|cursor updates, separate channel| GW

    ES -->|ownership lease| COORD[Coordination service\nZooKeeper/etcd: which server owns doc_id]

Key production decisions:

• WebSocket gateway is stateless and separate from the editing server. Gateways terminate client connections and route to whichever editing server owns the doc's shard; they hold no document state, so they scale independently of document count and can restart without affecting document ownership.
• Fan-out via pub/sub, not a direct per-socket loop on the editing server. At 500 concurrent editors, having the editing server iterate 500 socket writes itself blocks it from processing new incoming ops. Publish merged ops to a per-document topic; gateways holding connections to that doc's clients subscribe and push to their own sockets. This decouples "how many editors" from "how much CPU the merge engine itself burns."
• Ownership lease via a coordination service, not just a hash ring lookup — a hash ring tells you which server should own a doc, but you still need a lease (ZooKeeper/etcd, similar to leader election) to guarantee exactly one server actually holds authoritative in-memory state for it at a time, so a network hiccup doesn't produce two servers both believing they own the same document and diverging.
• Periodic compaction of the operation log into snapshots (e.g., every 500 ops or every 60 seconds, whichever first) bounds replay cost for a client joining a long-lived document to "load the latest snapshot + a small tail of recent ops," not "replay six months of keystrokes." Old ops past the compaction point can be archived to cold storage for history/blame features, not kept in the hot replay path.
• Presence is a fully separate, lower-durability channel. It shares the WebSocket transport but never touches the operation log or the CRDT merge engine — losing a cursor update for 200ms is invisible; losing a text operation is not. Keeping them architecturally separate stops presence traffic (which, per the capacity estimate, is higher volume than text ops) from competing for priority with actual document mutations.

13. Failure analysis¶

14. Consistency considerations¶

Convergence guarantee: strong eventual consistency (SEC) via CRDT merge, exactly the property described in CRDTs — Mental Model. In plain terms for an interviewer: every client that has received the same set of operations — regardless of the order they arrived in, even with duplicates — ends up displaying the byte-identical document. This is stronger than "eventually all replicas agree on something" (which LWW also technically satisfies) — it specifically guarantees the merged result reflects every concurrent edit, not a coin-flip winner.

What this buys, concretely: - A user never sees their own confirmed keystroke silently disappear because someone else typed nearby at the same instant. - Reconnecting after a partition needs no special-cased conflict-resolution logic — it's the same merge function used for live, connected typing. - Presence/cursor state deliberately does not carry this guarantee — it's best-effort, TTL'd, and allowed to be stale or briefly wrong, because the cost of that relaxation (a ghost cursor for 200ms) is far cheaper than making cursor updates travel the same durable, ordered path as text.

What it does not buy: a global invariant that spans the whole document (e.g., "total word count must never exceed 10,000" enforced live across concurrent editors) is not expressible purely through CRDT merge, for the same reason a CRDT can't enforce "balance never goes negative" — that needs a check against global state before allowing a local write, which is exactly the coordination this architecture is built to avoid needing for the common case.

15. Observability¶

Metrics:
  editor_ws_connections_active (per gateway, per shard)
  crdt_merge_latency_ms p50/p99   (op received → merged → broadcast)
  op_broadcast_fanout_ms p99      (per-document, watch the 500-editor tail)
  presence_update_rate / dropped_presence_pct
  oplog_length{doc_id}            (top-K longest — compaction candidates)
  compaction_lag_seconds
  ownership_lease_churn           (editing servers losing/reacquiring shards)
  client_reconnect_rate, client_outbox_replay_count

Alerts:
  crdt_merge_latency_p99 > 100ms          (the core SLA)
  oplog_length > compaction_threshold × 3  (compactor falling behind)
  ownership_lease_churn spike              (coordination service instability, or a hot shard flapping)
  single_doc_fanout_ms p99 > 150ms         (a viral doc outgrowing its shard)

16. Cost analysis¶

WebSocket gateway fleet (~36K concurrent connections, stateless, horizontally scaled): ~$400/month
Editing server fleet (merge engine, sharded by doc_id, CPU-bound on fan-out): ~$800/month
Coordination service (etcd/ZooKeeper cluster, small, high-availability):    ~$300/month
Pub/sub for fan-out (per-doc topics, high message rate, low payload size):  ~$200/month
Operation log storage (append-only, ~25 GB/day pre-compaction):            ~$400/month
Snapshot storage (compacted, ~100 GB resident):                            ~$50/month
Presence store (Redis, short-TTL, ephemeral, moderate size):               ~$100/month
Total:                                                                     ~$2,250/month

Cost lever: presence update rate is still the highest-volume live traffic (~18K msgs/s)
but carries no durability requirement — batching/coalescing presence updates more aggressively
(e.g. 100ms instead of 200ms, or coalescing multiple cursor moves per window) cuts
pub/sub and gateway CPU cost with zero correctness risk, unlike text ops which cannot be
coalesced away without risking a lost keystroke.

17. Alternative architectures¶

18. Staff Engineer Extensions¶

19. Interview follow-ups¶

1. "Why not just use OT since that's what Google Docs actually shipped?" — OT is a valid, proven answer; the honest trade-off is that OT needs a correctly-specified transform function per operation-pair (hard to prove correct) and a central sequencing server, while CRDT trades some per-character metadata overhead for a coordination-free merge that also handles offline/reconnect for free. Either is defensible; the interview signal is whether you can name the trade-off, not which one you pick.
2. "How do you handle rich text formatting (bold, italic), not just plain characters?" — Character-level RGA handles insert/delete of text content; formatting needs its own CRDT (e.g., a range-based attribute CRDT, or treating each formatting toggle as its own OR-Set-like marker attached to a span) layered on top — naively modeling "bold" as an LWW field on a text run reintroduces the silent-conflict problem this whole design was built to avoid.
3. "How do you support undo/redo in a multi-user document?" — Naive undo ("revert my last op") is wrong once someone else has edited since, because reverting can conflict with their intervening edit. Real implementations track a causal history and compute an inverse operation relative to current state (not a blind revert to a prior snapshot), which is significantly more complex than single-user undo — worth flagging as a known-hard extension rather than hand-waving it.
4. "What's actually different about this versus the CRDT counter/task-list exercise?" — Here, convergence must happen within ~100ms while multiple people are simultaneously typing and watching the result live; the task-list CRDT exercise's users are typically not staring at the same field at the same literal instant. That live, sub-second, multi-writer-watching-each-other requirement is what forces the fan-out/pub-sub/gateway architecture on top of the CRDT — the CRDT alone solves correctness, not the real-time delivery problem.

Self-Assessment¶

• [ ] I can explain why this problem is neither request/response nor "eventual convergence of independent writes," and why that distinction changes the architecture
• [ ] I can name the specific correctness bug last-writer-wins introduces (silently dropped keystrokes) and reproduce the exact interleaving that triggers it
• [ ] I can justify CRDT over OT for a from-scratch design while stating OT's real trade-off, not dismissing it
• [ ] I can explain why presence/cursor state is architecturally separate from the operation log, with the volume numbers to justify it
• [ ] I can state the multi-region latency floor honestly (150-300ms cross-region) instead of claiming a global 100ms SLA