Design Google Docs (Collaborative Editing)

A collaborative editor (Google Docs, Notion, Figma) lets multiple people type into the same document at the same time and guarantees that, no matter the order edits arrive in, everyone ends up with the identical document. That guarantee — convergence — is deceptively hard, because two people editing the same sentence concurrently produce operations that don’t naturally compose. You can’t take a lock on the paragraph (that would make collaboration feel like waiting in line), so you need edits that can be applied in different orders on different machines and still land on the same text. This is the world of vector clocks and CRDTs; we’ll follow the framework.

1. Requirements

Functional

• Concurrent editing — many users edit one doc simultaneously.
• Real-time sync — each user sees others’ changes within a fraction of a second.
• Presence — live cursors, selections, “who’s here.”
• Offline + reconnect — edits made offline merge cleanly on reconnect.
• History, undo/redo.

Non-functional

• Convergence (strong eventual consistency) — replicas that have seen the same edits are identical.
• Intention preservation — an edit’s effect should survive concurrent edits (your inserted word shouldn’t land inside someone else’s word).
• Low latency — local edits apply instantly (optimistic), then reconcile.

The hard requirement isn’t speed — it’s convergence without a lock

The whole difficulty is letting everyone edit at once (no locks, instant local response) while guaranteeing every replica converges to the same final document. Throughput per doc is small; the correctness of merging concurrent edits is the entire game.

2. Back-of-envelope estimation

per active document:
  collaborators:   typically a handful, occasionally dozens-to-hundreds
  edit rate:       a fast typist ≈ 5–10 keystrokes/sec; each may be an operation
  fan-out:         every op broadcast to all other collaborators on that doc

at platform scale:
  millions of documents, but each is its own small, independent sync problem
  ⇒ shard by document_id — one doc's collaborators all connect to one coordinating server

The scaling insight: a document is a natural shard. All collaborators on doc X talk to one coordinating server holding that doc’s live session, so the hard concurrency problem stays local to a single document and small. You scale out by spreading millions of docs across many servers, not by making one doc’s merge logic distributed.

3. Why naive concurrent editing breaks

Take the document ABC. Two users act concurrently on their local copies:

start:        A B C
User 1:  insert 'X' at position 0   → X A B C
User 2:  delete the char at position 2 (C) → A B

Now exchange operations. User 1 applies User 2’s “delete position 2” to XABC — but position 2 in XABC is B, not C. The two replicas diverge: one reads XAB, the other XAC. The operations were each individually correct against the state they were authored on, but position indices shift when concurrent edits land first. Fixing this is the job of either transforming the operations or designing them so order doesn’t matter. Those are the two great families: OT and CRDTs.

4. Operational Transformation (OT)

OT keeps operations small (insert(pos, char), delete(pos)) and, before applying a remote op, transforms it against the concurrent local ops so its indices land correctly.

User 1's op:  insert('X', 0)
User 2's op:  delete(2)
transform delete(2) against insert('X',0):
   the insert added a char before position 2 → shift the delete right by one → delete(3)
both replicas now apply the adjusted ops and converge → X A B

A central collaboration server orders incoming ops (assigning a revision number), transforms each against the ops it missed, and rebroadcasts. Google Docs uses OT (descended from the Jupiter system, and famously the engine behind Google Wave). Buys: operations stay tiny (great for bandwidth), and a server-mediated total order keeps things tractable. Costs: the transformation functions are notoriously hard to get right — the number of op-pair cases explodes, and OT typically leans on a central server to mediate order, which makes pure peer-to-peer or fully offline merges awkward.

Under the hood — why OT earned its scary reputation

OT looks simple for two ops; correctness under many concurrent ops requires the transformation to satisfy convergence properties (the literature calls them TP1/TP2) that are subtle to prove. The field has a long history of published “correct” OT algorithms later shown to violate these properties on specific interleavings. The practical takeaway: OT works beautifully in production (Google Docs proves it), but it concentrates the difficulty into a transformation matrix that must be exhaustively correct — and it leans on a server to assign the canonical order.

5. CRDTs — convergence by construction

A Conflict-free Replicated Data Type sidesteps transformation by designing operations that commute: apply them in any order on any replica and you reach the same state, no transform needed. For text, the trick is to stop using fragile integer positions. Give every character a stable, unique identifier with a dense total order — so a character’s identity never shifts when neighbors are inserted or deleted.

instead of   insert('X', position 2)          ← position shifts under concurrent edits
use          insert('X', id between idA, idB)  ← a fractional/stable id; order is intrinsic
deletes leave a "tombstone" so a concurrent insert next to a deleted char still resolves

Sequence CRDTs (RGA, LSEQ, Logoot, and the libraries Yjs and Automerge) implement exactly this. Buys: no central transformation logic; edits merge peer-to-peer, offline-first, in any order — convergence is guaranteed by the data structure itself. Costs: metadata overhead — every character carries an id, and deletes leave tombstones that linger, so memory and document size grow with edit history unless garbage-collected. You trade CPU-heavy transform logic for memory-heavy bookkeeping.

By the numbers — the tombstone tax

Suppose a paragraph of 1,000 visible characters has been edited heavily over its life — 50,000 inserts and deletes total. A position-based OT document stores ~1,000 characters of state (the ops were transient). A naive sequence CRDT stores an identifier per character ever inserted, plus a tombstone for every deleted one:

visible chars:        1,000
tombstones (deleted): ~49,000   ← still tracked so concurrent edits resolve
id overhead:          each char/tombstone carries a unique id (several bytes)
⇒ in-memory structure can be 10–50× the visible text before garbage collection

That’s the consistency cost made concrete: CRDTs buy you transform-free, offline-capable convergence, and they pay for it in metadata that must be tracked and periodically reclaimed. Modern CRDT libraries spend much of their cleverness shrinking exactly this overhead. What does the guarantee buy us, and what does it cost? — here the cost is bytes.

6. High-level design and presence

   clients ══WebSocket══►  ┌─────────────────────────┐
   (optimistic local edit) │  Collaboration server    │  (one per document session)
                           │   - assigns revisions     │
                           │   - OT transform / CRDT   │
                           │   - broadcasts ops         │
                           └───────────┬──────────────┘
                                       │ append to durable OP LOG + periodic SNAPSHOT
                                       ▼
                                 document store (op log + snapshots)

   presence (cursors, selections): a separate EPHEMERAL channel — not persisted, lossy is fine

Edits apply optimistically on the client (instant feedback), then sync: the server assigns a revision/order, reconciles (transform under OT, or merge under CRDT), and broadcasts to every other collaborator over their persistent connection — see real-time: polling, WebSockets, SSE. Durability is an append-only operation log plus periodic snapshots, so the document can be reconstructed and history/undo works. Presence (live cursors, “who’s editing”) rides a separate, ephemeral channel: it changes constantly, nobody needs it durably stored, and a dropped cursor update is harmless — so don’t pay to persist it. Both OT and CRDT target strong eventual consistency: any two replicas that have applied the same set of operations are byte-for-byte identical. See consistency models.

It actually happened — Google Wave and the cost of OT (2009–2010)

Google Wave launched in 2009 as a real-time collaboration platform built on Operational Transformation — every keystroke synced live across participants. Despite the impressive engineering, Google announced in August 2010 that it would stop developing Wave (the code was later donated to Apache as Wave-in-a-Box and the project eventually retired). Wave’s OT engine, though, lived on: its ideas and people fed directly into the OT machinery that powers Google Docs today. The episode is a clean illustration of the page’s thread — OT buys tight, server-mediated real-time collaboration with tiny operations, but it costs enormous engineering effort to make the transforms provably correct, effort that pays off only at the scale of a Docs, not a niche product.

Key trade-offs

• OT vs CRDT: OT keeps ops tiny and leans on a central server for ordering, but transformation logic is hard to make provably correct; CRDTs converge by construction and support peer-to-peer/offline editing, but carry per-character ids and tombstone metadata overhead.
• Optimistic local apply vs wait-for-server: applying edits locally first buys instant responsiveness; it costs a reconciliation step when the server’s order differs from yours.
• Persist ops vs persist snapshots: an append-only op log gives perfect history/undo but grows unbounded; periodic snapshots bound reconstruction cost at the price of extra storage.
• Persist presence vs treat it as ephemeral: ephemeral presence is cheap and good enough; persisting cursors would cost storage for data that’s worthless a second later.

Check your understanding

1. Using the ABC example, explain why naively applying concurrent insert/delete operations makes two replicas diverge.
2. How does Operational Transformation fix that, and what does it rely on a central server for?
3. How do CRDTs achieve convergence without transformation, and what is the metadata cost?
4. What does “strong eventual consistency” mean here, and why do both OT and CRDTs target it?
5. Why is presence (live cursors) carried on a separate ephemeral channel instead of the durable op log?

Show answers

1. Starting from ABC, User 1 does insert('X', 0) (→ XABC) and User 2 concurrently does delete(2) (deleting C from ABC → AB). When User 1 applies User 2’s delete(2) to XABC, position 2 is now B, not C, so the replicas diverge (e.g. XAB vs XAC). Each op was correct against the state it was authored on, but concurrent edits shift the position indices.
2. OT transforms a remote op against the concurrent ops it didn’t account for — e.g. it shifts delete(2) to delete(3) because an insert added a character before it — so both replicas converge. It relies on a central collaboration server to assign a canonical order (revision numbers) and mediate the transforms; pure peer-to-peer/offline merging is awkward under OT.
3. CRDTs give every character a stable, unique identifier with a dense order (e.g. a fractional id between its neighbors) so operations commute — applying them in any order on any replica yields the same result, no transform needed; deletes leave tombstones so concurrent edits near them still resolve. The cost is metadata overhead: an id per character plus lingering tombstones, which can bloat the structure many times over the visible text until garbage-collected.
4. Strong eventual consistency means any two replicas that have applied the same set of operations are identical, regardless of the order they arrived. Both OT and CRDTs target it because the product requirement is convergence without a lock — everyone editing freely must still end up with the exact same document.
5. Presence changes constantly, nobody needs a cursor position durably stored, and a dropped update is harmless — so it rides a separate ephemeral channel. Persisting it to the op log would pay storage and ordering costs for data that is worthless a second later; the durable log is reserved for the edits that define the document.