Design Google Docs (Collaborative Editor)

1. Problem & Real-World Context

Design a real-time collaborative document editor: multiple users typing in the same document simultaneously, with everyone converging on the same final content, without an explicit merge step. This is widely regarded as the hardest common HLD problem — the core challenge (concurrent edit conflict resolution) doesn't have an approximate or "good enough" answer the way caching or sharding often do; the document either ends up correct and consistent across all clients, or it's visibly broken (garbled text, lost characters), with no middle ground.

2. Requirements

Functional: multiple users edit the same document in real-time; all users see each other's changes near-instantly; cursor/selection positions visible to collaborators; persistent storage with no data loss; version history (restore to an earlier point).

Non-functional: concurrent edits must merge correctly and deterministically (every client must converge on the identical final document, regardless of the order operations happened to arrive in); low local-edit latency (<100ms felt latency — a user's own keystrokes must never wait on a server round trip); eventual consistency across clients is acceptable (a collaborator seeing your latest keystroke half a second late is fine; seeing a corrupted document is not).

3. The Core Problem, Concretely

Doc: "ab"
User A: Insert(pos=1, 'x') → intends "axb"
User B: Insert(pos=1, 'y') → intends "ayb"   (sent concurrently, before seeing A's edit)

Both operations reference position 1 in the original two-character document — but they can't both simply be applied at position 1 against the same evolving document, or one edit silently overwrites/misplaces the other. Two established approaches solve this: Operational Transformation (OT) — Google Docs' actual, real production approach — and CRDTs (Conflict-free Replicated Data Types) — the more modern alternative used by systems like Figma.

4. Operational Transformation (OT)

Core idea: transform an incoming operation against any operations that happened concurrently, so that applying the transformed operation produces the correct result regardless of arrival order.

from dataclasses import dataclass

@dataclass
class InsertOp:
    pos: int
    char: str

@dataclass
class DeleteOp:
    pos: int

def transform_insert_insert(op1: InsertOp, op2: InsertOp, op1_first: bool) -> InsertOp:
    """Transform op1 assuming op2 already happened. op1_first breaks position ties deterministically."""
    if op2.pos < op1.pos or (op2.pos == op1.pos and not op1_first):
        return InsertOp(pos=op1.pos + 1, char=op1.char)   # op2 inserted before op1's position — shift right
    return op1                                              # op2 doesn't affect op1's position

Walking the example from §3 with server-assigned arrival order (A arrives first): server applies A directly → "axb". Server then transforms B's Insert(1, 'y') against A's already-applied Insert(1, 'x'): since both target position 1, the tie-break rule (a consistent, agreed ordering — e.g., by a client/site ID) decides B shifts right → Insert(2, 'y'). Applying the transformed op gives "axyb" — and critically, every client reaches this same final string, regardless of which of A's or B's operation their local copy of the document processed first, because the transform function is defined to make transformation order-independent for correctness (this property is what the whole OT literature is built around getting right).

Why OT is hard in practice: the transform function must correctly handle every pair of operation types (insert-insert, insert-delete, delete-delete, delete-delete-of-overlapping-ranges) — each pairing has its own subtle edge cases. Multi-client OT (the Jupiter algorithm, Google Docs' actual lineage) additionally requires a central server to serialize operations into one total order before transforming — OT fundamentally depends on having an authoritative sequencing point, which is why it doesn't naturally extend to a fully peer-to-peer (no central server) setting.

5. CRDTs (Conflict-Free Replicated Data Types)

Core idea: instead of transforming operations relative to each other, give every character a globally unique, deterministically-ordered identity at insertion time — so two clients that insert concurrently, even without ever communicating, independently compute the same final ordering with zero coordination.

from dataclasses import dataclass

@dataclass
class RGAChar:
    value: str
    char_id: tuple[int, str]        # (logical_clock, site_id) — globally unique, totally ordered
    left_id: tuple[int, str] | None # the ID of the character immediately to its left at insertion time

def resolve_concurrent_inserts(chars: list[RGAChar]) -> list[RGAChar]:
    """Characters with the same left_id are concurrent inserts at the same position —
    break the tie deterministically (e.g., by char_id) so every replica agrees on order."""
    chars.sort(key=lambda c: c.char_id)   # deterministic across all replicas, no coordination needed
    return chars

This is a Replicated Growable Array (RGA) — each character's position is defined relative to its neighbor, not an absolute integer index (which would itself need constant adjustment as the document changes, the exact problem OT's transform functions solve for). Two concurrent inserts at the "same" position (same left_id) resolve their order purely by comparing char_id — a comparison every replica computes identically and independently, requiring no central server, no coordination, no transformation step at all.

Deletion via tombstones: a deleted character isn't physically removed — it's marked deleted but kept in the structure, because other characters' left_id references might still point to it; physically removing it would break the positional-reference chain for concurrent operations still in flight. This is the direct cause of CRDTs' main practical downside: tombstones accumulate over a long-lived document's life, growing memory usage — a real, named cost, not a hypothetical one.

6. OT vs. CRDT — the Trade-off Table

Why Google chose OT: largely a historical/timing reason (Google Docs' OT lineage predates CRDTs' maturity as a practical technique) — worth stating this plainly rather than implying OT is simply "better." Modern greenfield systems, especially ones wanting strong offline-first support (Figma is the standard example), more often reach for CRDTs specifically for the offline/peer-to-peer properties.

7. High-Level Architecture

flowchart LR
    A[Client A<br/>local doc + optimistic apply] -->|WebSocket| DS[Document Server]
    B[Client B<br/>local doc + optimistic apply] -->|WebSocket| DS
    DS -->|op log, ordered| Kafka[Kafka Op Log]
    DS -->|periodic snapshot| Blob[(Snapshot Store)]
    DS -->|cursor/presence,<br/>ephemeral| Redis[(Redis<br/>active sessions)]
    DS -->|transformed op,<br/>broadcast| A
    DS -->|transformed op,<br/>broadcast| B

Detailed flow (OT-based, matching Google's real design): (1) a user types — the character is applied immediately and optimistically to their own local in-memory document (this is what makes typing feel instant — it never waits on a network round trip), and the operation is queued to send. (2) The client sends the op to the server over a persistent WebSocket (see [[Communication Protocols]]), tagged with the client's last-known server version. (3) The server transforms the incoming op against any ops it has received and applied since that version, applies the transformed result to its authoritative document copy, and broadcasts the transformed op to every other connected client. (4) Other clients, on receiving a broadcast op, transform it against their own locally pending, not-yet-acknowledged edits before applying and rendering — this local transform step is what reconciles "I typed something the server doesn't know about yet" with "the server just told me about someone else's edit."

8. Cursor Presence

Cursor/selection position broadcasting is deliberately kept separate from the document-edit op stream — it's high-frequency, latency-sensitive, and (crucially) not part of the document's durable history. Each client broadcasts {user_id, cursor_pos, color}; the server relays it to other clients without persisting it to the op log at all — stored ephemerally in Redis (active-session state, the same pattern as [[WhatsApp Chat]]'s presence tracking) rather than Kafka's durable log. Cursor positions do still need position-transformation logic analogous to insert/delete transforms (if someone else inserts text before your cursor, your cursor's absolute position needs to shift) — but this is a lightweight derived computation, not something requiring the full OT/CRDT conflict-resolution machinery.

9. Persistence & Version History

• Op log: every operation, in server-serialized order, appended to an immutable, replayable log (Kafka or a similarly durable append-only store) — this is the document's true source of history, not a derived artifact.
• Snapshots: periodically (every N ops, or every fixed time interval), the current in-memory document state is serialized and saved to [[Blob & Object Storage]] — snapshots exist purely as a performance optimization for recovery and version history, not as the source of truth.
• Recovery: a server restart (or reassignment to a new server, §10) loads the most recent snapshot, then replays only the ops logged after that snapshot to reach the current state — far cheaper than replaying the entire document's history from the beginning every time.
• Version history as a feature: named snapshots (or any point reconstructed by replaying to a specific op) directly give "restore to an earlier version" — a natural byproduct of the append-only-op-log design, not a separately-built feature.

10. Scaling

• Single document → single coordinating server: OT's correctness depends on a total ordering of operations, which is far simpler to guarantee with one authoritative coordinator per document than with a distributed consensus process across multiple servers — this is a deliberate simplification, not a limitation to work around.
• Many documents → consistent hashing across servers: each document (identified by ID) is assigned to one server via [[Consistent Hashing]], and that server holds authoritative in-memory state for every document it owns — horizontal scale comes from spreading documents across many single-document-authoritative servers, not from distributing the coordination of one document across many servers.
• Server failure: the failed server's documents are reassigned (via the same consistent-hashing ring) to another server, which recovers each document's state via the snapshot-plus-replay mechanism from §9 — no data loss, since the op log is durable independent of any single server's in-memory state.

11. Interview Drill Questions

1. Why does a user's own typing feel instant even though the server needs to transform and broadcast the operation? — Optimistic local application: the client applies its own edit to its local document immediately, before the server round-trip even starts — the network exchange happens in the background for reconciliation with other clients' concurrent edits, not as a gate on the local user's perceived typing latency.
2. Why can't OT's transform function be applied independently by each client without a central server? — OT's correctness depends on operations being transformed relative to a single, agreed total order of "what happened before what" — without a central coordinator establishing that order, different clients could transform the same concurrent operations differently and diverge on the final document, which is exactly the failure mode OT is designed to prevent.
3. Why do CRDTs keep deleted characters as tombstones instead of removing them outright? — Other characters' position references (left_id in the RGA model) may still point at a deleted character; removing it outright would break those references for any concurrent operation still resolving against the old structure — tombstones preserve referential integrity at the cost of unbounded memory growth over a long document's lifetime.
4. A network partition splits collaborators into two groups, each continuing to edit offline. How does each approach handle reconciliation on reconnect? — CRDTs handle this naturally — each side's edits already carry globally-ordered identities, so merging on reconnect is just combining both structures and resolving ties deterministically, no special-casing required. OT handles this far more awkwardly — the offline side accumulated ops against a stale server version, and reconciling a whole batch of ops against everything that happened on the server side in the interim is a much harder transform problem than the single-concurrent-op case OT is built around.
5. Why is cursor position broadcast as a separate stream from document edits instead of being just another operation type in the same op log? — Cursor position is ephemeral, high-frequency, and has no long-term value (nobody needs "restore the cursor position from an hour ago" as a feature) — persisting it in the durable, replayable op log would bloat the document's real history with noise; keeping it in ephemeral Redis-backed presence state (like [[WhatsApp Chat]]'s online-status tracking) matches its actual lifecycle.

Cross-links

[[Message Queues & Kafka]] · [[Caching & Redis]] · [[WhatsApp Chat]] · [[Consistent Hashing]] · [[Blob & Object Storage]] · [[Communication Protocols]]