Design Google Docs: Real-Time Collaborative Editing (OT vs CRDT)

"Design Google Docs" separates candidates quickly. Most can draw WebSockets and a database. Far fewer can explain what happens when two people edit the same sentence at the same moment, which is the entire reason the question exists. This guide starts with that problem, works through operational transformation and CRDTs with small runnable examples, and then builds the system around them.

Scope note: file storage, sharing and sync of whole files belong to Google Drive / Dropbox design. Here we design the real-time editing engine.

Requirements

Functional

• Multiple users edit the same rich-text document simultaneously; everyone sees others' changes within a fraction of a second.
• Show collaborators' presence: avatars, cursors and selections.
• Version history: view and restore earlier versions; see who changed what.
• Comments and suggestions (mention, do not deep dive unless asked).
• Offline editing that merges when connectivity returns.

Non-functional

• Convergence: all replicas end with identical content once all edits are delivered. Non-negotiable.
• Intention preservation: an edit should do what its author meant, even after concurrent edits.
• Low latency: local typing is instant (optimistic); remote edits appear in roughly 100–300 ms.
• Durability: no acknowledged edit is ever lost.
• Most documents have 1–3 concurrent editors; a few have dozens. Google's help pages describe a cap of around 100 people editing at once, with others viewing.

Capacity Estimation

The shape: millions of long-lived connections, millions of tiny messages per second, but each document's traffic is small and local. That points to partitioning by document: route all of a document's participants to one session owner, which can hold the document in memory and order its operations without distributed coordination. 10M documents across, say, 2,000 session servers is ~5,000 documents each, mostly idle.

Why Naive Sync Fails

Represent edits as operations: Insert(pos, char) and Delete(pos). The document is "CAT". At the same moment:

• Asha types "H" after "C": Insert(1, 'H') → her screen shows "CHAT".
• Bilal deletes "T": Delete(2) → his screen shows "CA".

Each sends their op to the other. Asha applies Delete(2) to "CHAT" and deletes "A", leaving "CHT". Bilal applies Insert(1,'H') to "CA" and gets "CHA". The replicas have diverged, and Asha's copy lost the wrong letter. Locks (only one editor at a time) would avoid this but destroy the product. Sending the whole document on every keystroke loses concurrent edits. We need operations that survive reordering: that is what OT and CRDTs provide.

Operational Transformation Explained with Code

OT defines a function transform(a, b) that rewrites operation a so it can be applied after concurrent operation b with the same intent. In the example, Bilal's Delete(2) transformed against Asha's Insert(1) becomes Delete(3), because an insert before position 2 pushed "T" right by one.

The convergence property we need (called TP1): apply(apply(doc, a), transform(b, a)) == apply(apply(doc, b), transform(a, b)).

from dataclasses import dataclass, replace

@dataclass(frozen=True)
class Ins:
    pos: int
    ch: str
    site: int          # tie-breaker for inserts at the same position

@dataclass(frozen=True)
class Del:
    pos: int

NOOP = None

def apply(doc, op):
    if op is NOOP:
        return doc
    if isinstance(op, Ins):
        return doc[:op.pos] + op.ch + doc[op.pos:]
    return doc[:op.pos] + doc[op.pos + 1:]

def transform(a, b):
    """Rewrite op `a` so it can be applied after concurrent op `b`."""
    if a is NOOP or b is NOOP:
        return a
    if isinstance(a, Ins) and isinstance(b, Ins):
        if a.pos < b.pos or (a.pos == b.pos and a.site < b.site):
            return a
        return replace(a, pos=a.pos + 1)
    if isinstance(a, Ins) and isinstance(b, Del):
        return a if a.pos <= b.pos else replace(a, pos=a.pos - 1)
    if isinstance(a, Del) and isinstance(b, Ins):
        return a if a.pos < b.pos else replace(a, pos=a.pos + 1)
    # both deletes
    if a.pos < b.pos:
        return a
    if a.pos > b.pos:
        return replace(a, pos=a.pos - 1)
    return NOOP                      # same character already deleted

doc = "CAT"
op_a = Ins(1, "H", site=1)           # Asha: "CAT" -> "CHAT"
op_b = Del(2)                        # Bilal: "CAT" -> "CA"

at_asha  = apply(apply(doc, op_a), transform(op_b, op_a))
at_bilal = apply(apply(doc, op_b), transform(op_a, op_b))
print(at_asha, at_bilal)             # CHA CHA
print(apply(apply(doc, op_a), op_b)) # CHT  <- what happens without OT

public final class TextOT {
    interface Op {}
    record Ins(int pos, char ch, int site) implements Op {}
    record Del(int pos) implements Op {}

    static String apply(String doc, Op op) {
        if (op == null) return doc;                       // null == no-op
        if (op instanceof Ins ins) {
            return doc.substring(0, ins.pos()) + ins.ch() + doc.substring(ins.pos());
        }
        Del del = (Del) op;
        return doc.substring(0, del.pos()) + doc.substring(del.pos() + 1);
    }

    /** Rewrite a so that it applies after concurrent op b. */
    static Op transform(Op a, Op b) {
        if (a == null || b == null) return a;
        if (a instanceof Ins ia && b instanceof Ins ib) {
            boolean stays = ia.pos() < ib.pos() || (ia.pos() == ib.pos() && ia.site() < ib.site());
            return stays ? ia : new Ins(ia.pos() + 1, ia.ch(), ia.site());
        }
        if (a instanceof Ins ia && b instanceof Del db) {
            return ia.pos() <= db.pos() ? ia : new Ins(ia.pos() - 1, ia.ch(), ia.site());
        }
        if (a instanceof Del da && b instanceof Ins ib) {
            return da.pos() < ib.pos() ? da : new Del(da.pos() + 1);
        }
        Del d1 = (Del) a, d2 = (Del) b;
        if (d1.pos() < d2.pos()) return d1;
        if (d1.pos() > d2.pos()) return new Del(d1.pos() - 1);
        return null;                                      // both deleted the same char
    }

    public static void main(String[] args) {
        Op a = new Ins(1, 'H', 1), b = new Del(2);
        String asha  = apply(apply("CAT", a), transform(b, a));
        String bilal = apply(apply("CAT", b), transform(a, b));
        System.out.println(asha + " " + bilal);           // CHA CHA
    }
}

Dry run

1. At Asha: she has applied Ins(1,'H') → "CHAT". Bilal's Del(2) arrives; transform(Del 2, Ins 1): delete position 2 is not before insert position 1, so it shifts to Del(3). Deleting index 3 ("T") gives "CHA".
2. At Bilal: he has "CA". Asha's Ins(1) arrives; transform(Ins 1, Del 2): 1 ≤ 2 so it is unchanged. Inserting "H" at 1 gives "CHA".
3. Converged, and both intents survived: "H" after "C", "T" deleted.

The site tie-breaker matters when both insert at the same position: without it, both replicas might put their own character first and diverge. Real editors transform richer ops (retain/insert/delete runs with formatting attributes, as in the ot.js and Quill Delta formats), but the logic is the same pattern scaled up.

The OT Client-Server Protocol (Jupiter-style)

With a central server, every document has a linear history: revision 0, 1, 2… The protocol (descended from the Jupiter system and used by Google Wave and Docs):

1. Client applies edits locally immediately (optimistic UI), and sends an op tagged with the server revision it was based on: {op, base_rev: 41}.
2. Client keeps at most one op in flight. Further local edits accumulate in a buffer, composed into one op, until the server acknowledges. This bounds the transform work.
3. Server receives {op, base_rev: 41} while it is at revision 44. It transforms the op against ops 42, 43 and 44 from its log, applies it, assigns revision 45, appends it to the durable log, then acknowledges the sender and broadcasts the transformed op to others.
4. Other clients receive op 45. Each transforms it against its own in-flight and buffered ops (and transforms those against op 45) before applying, so local unacknowledged typing is preserved.
5. Acknowledged: the sender moves its buffer into flight and repeats.

The server is the single source of order, which makes it the natural place for durability: an op is acknowledged only after it is in the log. That also means a document must have exactly one active server owner at a time, which shapes the architecture below.

CRDTs: Conflict-Free Replicated Data Types

CRDTs avoid transforming positions altogether. Instead of "insert at index 1", an insert says "insert 'H' after the character with ID (1, site 1), and my new character's ID is (4, site 1)". IDs never change, so operations are valid regardless of what else happened. Deletes mark characters as tombstones instead of removing them, because later operations might reference them.

The RGA (Replicated Growable Array) algorithm orders concurrent inserts after the same character by ID: higher IDs come first. IDs are (Lamport counter, site), so they are unique and totally ordered.

class RGA:
    """Replicated Growable Array: a sequence CRDT for collaborative text."""
    def __init__(self, site):
        self.site = site
        self.clock = 0
        self.items = []            # list of [id, ch, deleted]; id = (counter, site)

    def _index_of(self, elem_id):
        for i, item in enumerate(self.items):
            if item[0] == elem_id:
                return i
        raise KeyError(elem_id)

    def text(self):
        return "".join(ch for _, ch, deleted in self.items if not deleted)

    def local_insert(self, after_id, ch):
        self.clock += 1
        op = ("ins", (self.clock, self.site), after_id, ch)
        self.apply(op)
        return op                  # broadcast this to other replicas

    def local_delete(self, elem_id):
        op = ("del", elem_id)
        self.apply(op)
        return op

    def apply(self, op):           # works for local and remote ops, in any order*
        if op[0] == "ins":
            _, new_id, after_id, ch = op
            self.clock = max(self.clock, new_id[0])        # Lamport clock
            i = 0 if after_id is None else self._index_of(after_id) + 1
            # skip concurrent inserts at the same spot that have a higher id
            while i < len(self.items) and self.items[i][0] > new_id:
                i += 1
            self.items.insert(i, [new_id, ch, False])
        else:
            self.items[self._index_of(op[1])][2] = True    # tombstone

    def id_at(self, visible_index):
        seen = -1
        for item in self.items:
            if not item[2]:
                seen += 1
                if seen == visible_index:
                    return item[0]
        raise IndexError(visible_index)

a, b = RGA(site=1), RGA(site=2)
o1 = a.local_insert(None, "C")
o2 = a.local_insert(o1[1], "A")
o3 = a.local_insert(o2[1], "T")
for op in (o1, o2, o3):
    b.apply(op)                              # both replicas: "CAT"

x = a.local_insert(a.id_at(0), "H")          # a: "CHAT"
y = b.local_insert(b.id_at(0), "R")          # b: "CRAT"   (concurrent, same spot)
z = b.local_delete(b.id_at(3))               # b: "CRA"

a.apply(y); a.apply(z)                       # deliver in different orders
b.apply(x)
print(a.text(), b.text())                    # CRHA CRHA

Dry run: "H" gets ID (4, 1) and "R" gets ID (4, 2); both reference "C". On each replica, the insert scans right from "C" past any item with a larger ID. (4, 2) > (4, 1), so "R" always ends up before "H", on both replicas, regardless of arrival order. The delete of "T" references T's ID, unaffected by the inserts. Both converge to "CRHA". (*The one ordering requirement: an insert must be delivered after the insert it references, which causal delivery or a small pending buffer provides.)

Production CRDT libraries such as Yjs and Automerge use smarter variants (YATA, run-length encoded items, compact binary encodings, tombstone garbage collection when all replicas have seen a delete), bringing overhead down to practical levels for real documents.

OT vs CRDT: Which Should You Choose?

Interview answer: "Since we have a central server anyway and documents are mostly online, I'll use server-ordered OT, like Google Docs. If offline-first or peer-to-peer collaboration were a core requirement, I'd choose a CRDT like Yjs." Either choice is acceptable if you justify it; not knowing either is not.

High-Level Architecture

Deep Dive: WebSocket Sessions and Document Ownership

Each open document tab holds a WebSocket to a gateway. Gateways are stateless connection terminators: they authenticate, check the user's access to the document, and forward messages to the document's session owner.

• Single owner per document. Ownership is assigned by consistent hashing on doc_id plus a lease in a coordination service (etcd/ZooKeeper/Chubby-style). The owner loads the latest snapshot and subsequent ops into memory when the first user opens the document.
• Failover. If the owner dies, its lease expires (seconds); a new owner rebuilds state from snapshot + log. Clients reconnect, resend unacknowledged ops with their base revision, and the new owner transforms them normally. No acknowledged op is lost because acks happen after the log append.
• Split-brain protection. Log appends are conditional on the expected next revision (or carry a fencing token from the lease), so a stale owner that wakes up cannot write.
• Batching. Clients batch keystrokes into an op every ~100–200 ms; the owner broadcasts in small batches too. This cuts message counts by an order of magnitude with no perceptible lag.
• Hot documents. A company all-hands doc opened by 20,000 viewers: limit active editors, and fan out to viewers through a broadcast tier (pub/sub) instead of directly from the owner.

Why WebSockets rather than SSE or long polling? Editing is bidirectional and chatty; see WebSockets vs SSE vs long polling. The same stateful-session pattern appears in Zoom-style conferencing and multiplayer games.

Deep Dive: Presence and Live Cursors

• Ephemeral channel. Join/leave, cursor position and selection range travel over the same WebSocket as a separate message type. They are never written to the op log.
• Throttle. Send at most every 50–100 ms and only on change; drop intermediate positions.
• Keep cursors correct. A remote cursor at index 120 must move when someone inserts text before it. Either transform cursor positions through incoming ops with the same transform function (treating a cursor like a zero-width insert), or, with CRDTs, anchor the cursor to a character ID.
• Liveness. Heartbeats every ~15–30 s; a user whose connection drops disappears after a timeout. Idle users get a dimmed avatar.
• Cost. Presence can generate more messages than edits. Since it is disposable, the owner can coalesce and shed it under load before ever delaying real ops.

Deep Dive: Version History and Storage

Storage is an event-sourced design:

• Op log: (doc_id, revision) → op, author, timestamp. Append-only, written before acknowledging. A wide-column store or a sharded SQL table keyed by (doc_id, revision) handles this well; see key-value store design.
• Snapshots: every N ops (say 500) or on session close, the owner writes the full document state at that revision. Loading a document = latest snapshot + ops after it.
• History view: to show the document at revision r, load the nearest snapshot ≤ r and replay. The UI groups consecutive ops by author and time window into readable versions ("Asha, 10:42 – 10:57"); named versions are just labelled revisions.
• Restore is a new forward op that transforms the current document into the old content, so history stays linear and collaborators are not disrupted.
• Compaction: old fine-grained ops can be squashed into coarser ones after some retention period, keeping snapshots at the grouped-version boundaries.

Deep Dive: Offline Edits

A user edits on a train without connectivity for 40 minutes.

1. Queue locally. Ops are stored in IndexedDB with their base revision, so a closed laptop or refreshed tab loses nothing.
2. Reconnect. The client sends its composed pending ops with the last server revision it saw.
3. Server merges. With OT, the server transforms the pending op against every op since that revision, potentially thousands. This works but is costly and can produce surprising merges after long divergence. With a CRDT, the client and server exchange missing ops (state vectors tell each side what the other lacks) and merge directly.
4. Guardrails. If divergence is extreme (days, or the document was heavily restructured), it can be safer to present the offline changes as a suggestion or separate version for the user to review rather than silently auto-merging.

How to Present This in an Interview

1. Lead with the concurrency example ("CAT" with an insert and a delete) and show divergence. It proves you understand the core problem in 60 seconds.
2. Choose OT or CRDT and justify; show a transform rule or the ID-based insert.
3. Draw the session architecture: gateways, single owner per doc with lease, op log, snapshots.
4. Cover the protocol: optimistic local apply, one op in flight, base revision, ack after durable append.
5. Finish with presence, history, offline and failure handling.

Follow-up questions to expect

• "How do you handle formatting (bold) and rich structure?" Ops carry attributes over ranges; transforms must handle attribute ops; tree-structured documents need tree-aware transforms or CRDTs.
• "How do comments stay attached to text?" Anchor them to ranges that are transformed like cursors (or to CRDT IDs).
• "How do you scale to 10M open documents?" Partition by doc, keep idle documents unloaded, evict session state after inactivity.
• "What if the owner crashes after appending but before acking?" Client resends with an op ID; the owner deduplicates by (client_id, op_seq) and acks the existing revision.

Event streams from the op log (for search indexing or activity notifications) are a natural fit for Kafka; see distributed message queue design if the interviewer heads in that direction.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.