Q68 — Design a real-time collaborative editing system (like Google Docs)

What makes collaborative editing hard

Two users are editing the same document simultaneously. User A inserts "Hello" at position 0. User B simultaneously inserts "World" at position 0. Both changes must be merged into the shared document so everyone sees the same final state — without losing either edit.

This is the concurrent modification problem. In a database, concurrent modifications are resolved by locking (one wins, the other waits or fails). In a collaborative editor, both changes must be accepted and merged — and the merge must converge to the same result regardless of the order in which the server receives the two operations.

This is fundamentally harder than any problem we've seen so far, because:

1. Multiple users are editing simultaneously without locks
2. Network latency means each user works on a slightly stale version
3. The final state must be consistent for all users

Why simple "last write wins" doesn't work

If user A and user B both have the document "cat" and simultaneously delete different characters:

• A deletes 'c' → "at"
• B deletes 'a' → "ct"

Last-write-wins: one of these is discarded. The other user's edit is silently lost. Users see their own edits disappear — the worst possible UX.

You need a conflict resolution algorithm that merges both edits correctly.

Operational Transformation (OT) — what Google Docs uses

Operational Transformation represents edits as operations (insert character X at position P, delete character at position P) and defines transformation functions that adjust operations for the operations that came before them concurrently.

Concretely:

• A inserts 'X' at position 5 (local version of document)
• B inserts 'Y' at position 3 (local version of document)

A's operation arrives at B's client after B has already inserted 'Y'. A's operation must be transformed relative to B's operation: since B inserted at position 3, which is before position 5, A's insert position becomes 5+1 = 6.

The transformation function: transform(A's insert at 5, B's insert at 3) → A's insert at 6.

After transformation, both clients apply both operations and arrive at the same state. This works for text operations but requires implementing transformation functions for every pair of operation types — insert+insert, insert+delete, delete+insert, delete+delete. The correctness requirement (convergence) is strict and easy to violate. OT systems require a central server to impose a total ordering on concurrent operations (the server's ordering is the canonical ordering all clients transform against).

Why OT is complex: transformation functions are subtle and error-prone. The permutation of operation types grows combinatorially with richer data models (tables, images, formatting). Google's Docs team has spent years refining their OT implementation.

CRDTs — the distributed-systems approach

Conflict-free Replicated Data Types (CRDTs) take a different approach: design the data structure so that all concurrent operations commute — applying them in any order produces the same result. No transformation functions, no central ordering required.

For text, the most practical CRDT is RGA (Replicated Growable Array) or its variant YATA (used in Y.js). Each character is assigned a globally unique identifier (node_id + logical_clock). The document is a linked list of characters sorted by their IDs. Insertions create a new character node; deletions tombstone the node (mark as deleted, keep in the list).

Since character nodes have unique stable identities, two concurrent insertions of 'X' at position 5 and 'Y' at position 5 create two distinct nodes. Their ordering in the final list is determined deterministically by their IDs. Both insertions are preserved, the list converges to the same order on all nodes regardless of operation receipt order.

CRDTs don't require a server for correctness — they work peer-to-peer. Each client applies operations locally and merges with other clients' operations when connected. They're the foundation of modern collaborative editors: Y.js (used in VS Code Live Share, Notion, many others) and Automerge implement text CRDTs.

Trade-off: CRDT documents grow over time (deleted characters are kept as tombstones). Garbage collection (pruning tombstones) is complex and requires coordination. The document representation is also larger than a simple string.

System architecture

Real-time synchronization: users need to see each other's changes in near-real-time. WebSockets (Q04) are the right transport — persistent bidirectional connections between each client and the server.

Server role:

• Relay operations between connected clients (broadcast)
• Persist the canonical document state and operation log
• Handle clients joining mid-session (send them the current document state)

Client A ──WebSocket──┐
                      │── Server ── Database (document + ops log)
Client B ──WebSocket──┘

Each connected client sends operations to the server. The server applies the operation (merging with concurrent operations via OT or CRDT), persists it, and broadcasts to all other connected clients. Clients apply received operations to their local state.

Presence and cursors: beyond text synchronization, users see each other's cursors (where they're currently editing) and names. Cursor positions are ephemeral state — stored in Redis (or in-memory on the server), broadcast on every cursor move, and not persisted to the database. Cursor updates are lossy (fire and forget) — it's fine if a cursor update is missed; the next one will correct it.

Persistence model

The document is stored in two forms:

Current document state (snapshot): the full document content at the current version. Used for new clients joining a session.

Operation log: every operation ever applied, in order. Used for version history, undo/redo, and reconstructing any historical version.

On each operation:

1. Apply to in-memory document state
2. Append to the operation log (durable write)
3. Update the snapshot periodically (e.g., every 100 operations) — snapshotting avoids replaying the full log on every server restart

This is event sourcing applied to collaborative editing (Q51) — the operation log is the event log, and the document state is the projection.

Scaling to many documents and users

A single document's WebSocket connections must all route to the same server (or the server must broadcast via a message broker). Two clients connected to different servers need their operations to be relayed.

Solution: use Redis Pub/Sub or Kafka topics per document. Server A receives an operation, publishes to Kafka topic doc:{document_id}. Server B (which has other clients for that document) subscribes to that topic and relays the operation to its clients. This decouples server instances while ensuring all clients receive all operations.

For very popular documents (live-edited by hundreds of users simultaneously — a shared conference notes doc), the server handling that document becomes a hotspot. Shard by document ID to dedicated server instances.

The mental model

Hard problem: concurrent edits from multiple users must all be preserved and merged
  Not last-write-wins — both edits must survive

Two approaches:
  OT (Operational Transformation):
    Represent edits as operations (insert/delete at position)
    Transform operations against concurrent operations before applying
    Requires central server to impose canonical ordering
    Google Docs uses this — complex but proven for rich documents

  CRDT (Conflict-free Replicated Data Type):
    Give each character a unique stable ID
    Operations commute — any order → same result
    Works peer-to-peer, no central server required
    Y.js, Automerge — used by VS Code, Notion
    Trade-off: tombstones grow the document over time

Architecture:
  WebSockets for real-time bidirectional comms (persistent connection per client)
  Server: receive operation → merge → persist to op log → broadcast to other clients
  Presence/cursors: ephemeral in Redis, lossy OK (missed update corrected by next)

Persistence: event sourcing pattern
  Op log: every operation in order (durable)
  Snapshot: current document state (periodic, fast load for new clients)
  Undo/redo: replay or reverse operations from log

Scaling:
  Redis Pub/Sub or Kafka topic per document → relay ops between servers
  Shard popular documents to dedicated server instances

The guarantee: all clients converge to the same document state
  regardless of operation order at the server
  regardless of network delays between clients

Collaborative editing is the hardest problem in this question bank because the consistency model is fundamentally different from anything else: you're not trying to serialize operations (that would require locking, killing concurrent edits) — you're trying to merge operations from a system where multiple writers make progress simultaneously, and you need the merger to be correct regardless of timing.