Collaborative Editing — Hundreds Typing One Doc, Still ConvergingOT vs CRDT, Conflict Resolution, Offline Sync

Problem & Requirements

Design a Google Docs / Figma-class real-time collaborative editor: up to hundreds of active editors typing into one document, each keystroke an operation, everyone seeing others' cursors and text within <100ms, editing offline for arbitrary durations and auto-merging on reconnect. The single hard problem: when two people insert at the same position simultaneously, every replica must converge to a byte-identical state — otherwise the document forks.

• Concurrency: active editors per doc are usually <100, but keystroke rate is high (5-10 ops/s/person); presence (cursors/selections) updates even more often.
• Latency SLO: local keystrokes must echo with zero delay (optimistic local-first); remote propagation <100ms.
• Consistency: Strong Eventual Consistency — replicas that have received the same set of ops must reach identical state, regardless of arrival order.
• Offline: edit for arbitrary durations while disconnected; merge on reconnect without lost edits or manual conflict resolution.

High-Level Architecture

The core is one dedicated server process per document acting as the authority: it serializes all ops into a total-order log, then broadcasts. Clients always render locally first, applying ops optimistically before sending them; once the server acks, the local op is confirmed. Presence (cursors/selections) travels on a separate ephemeral channel and is never persisted. When a doc goes cold, it snapshots to storage and the process is reclaimed.

Key Techniques

1. OT (Operational Transformation) — trade central serialization for plain text, zero metadata

Core trade-off: the data structure is just plain text (no bloat), at the cost of transform functions that are brutally hard to get right and a hard dependency on a central serializer.

Principle. Each operation carries a positional index (e.g. "insert X at position 5"). When two concurrent ops derive from the same state, applying them naively by index diverges. OT defines a transform T(op_a, op_b): recompute op_a's position relative to a world where op_b has already been applied. If A inserts at position 2 and B at position 5, when B reaches A its position must shift +1 (A already lengthened the prefix). Replicas transform along different paths yet converge to the same state.

# insert vs insert position transform (simplified)
def transform(op_a, op_b):
    # return op_a's position assuming op_b already applied
    if op_a.pos < op_b.pos:
        return op_a                      # unaffected
    elif op_a.pos > op_b.pos:
        return op_a.shift(+len(op_b))    # pushed back by b
    else:  # concurrent insert at same position -- need tie-break
        if op_a.site_id < op_b.site_id:  # order by site id for symmetry
            return op_a
        return op_a.shift(+len(op_b))

The hard part is the TP1/TP2 correctness properties: TP1 requires two ops applied in either order to converge; TP2 requires that three-plus concurrent ops converge regardless of transform order. TP2 is extremely hard to satisfy without a total order — several published OT algorithms were later proven to have counterexamples. Industry's escape hatch: use a central server to enforce a total order, so you only need TP1 (the key insight of the Jupiter algorithm).

2. Sequence CRDT — trade dense position IDs for "no central coordination needed"

Core trade-off: operations are inherently commutative and mergeable offline/P2P, at the cost of per-character metadata plus tombstones that never disappear.

Principle. A CRDT does no transform; instead it gives each character a globally unique, densely comparable position identifier (a fractional index / tree path). Between any two characters you can always mint another id (density). Insert = generate an id wedged between the left and right neighbors; delete = plant a tombstone rather than physically remove (else concurrent references dangle). Because each op depends only on immutable ids, not the current index, applying the same batch of ops in any order yields the same result — that is Strong Eventual Consistency with no central ordering.

# RGA-style insert: id = (logical clock, site_id), positioned after a predecessor
def insert_after(pred_id, char, site_id, clock):
    new_id = (clock, site_id)           # globally unique
    node = Node(id=new_id, char=char, after=pred_id, deleted=False)
    # concurrent inserts under the same pred sort by id descending (deterministic tie-break)
    insert_sorted(node, key=lambda n: n.id, desc=True)
    return new_id

def delete(target_id):
    nodes[target_id].deleted = True     # tombstone, not physical delete

Two famous pitfalls: (1) metadata bloat — one id per character; a naive implementation can hit 100:1 overhead; (2) interleaving anomaly — when two people each insert a whole run of text concurrently, some CRDT algorithms interleave the characters into garbage (Kleppmann et al. have a dedicated 2019 paper on this).

3. Offline-first & causal merge — where CRDTs really pull ahead

Core trade-off: OT on reconnect must transform your stale baseline against the server's missing ops one by one (the server must retain an op log); a CRDT just exchanges the ops each side is missing and merges directly — the longer the offline window, the bigger the advantage.

Principle. A client uses a version vector (max logical clock per site) to describe "which ops I've seen." On reconnect both sides exchange version vectors and backfill only the delta the other lacks. Causal order is guaranteed by dependencies each op carries (predecessor id / logical clock) — an insert op may only apply once its predecessor is visible. A CRDT's commutativity lets even out-of-order backfilled ops merge correctly — the killer feature for offline.

4. Server architecture — per-document single-writer authority + snapshot truncation

Core trade-off: one process per document serializes cleanly, isolates well, is simple to reason about, and yields a natural total order; the cost is a per-doc single-point throughput ceiling and the need to handle process routing and migration.

Principle. The routing layer uses consistent hash(doc_id) to pin all connections for a document to the same process. That process processes ops single-threaded → guaranteeing total order (which lets OT need only TP1) → broadcasts to subscribers → appends to the op log. The op log grows unbounded, so periodically it snapshots (materializes the current document + version vector) and truncates old log, GC'ing tombstones with no remaining concurrent references at the same time. A new client joining just pulls the latest snapshot + a small delta instead of replaying all history.

Scaling & Optimization

• Large-doc chunking: split a huge document into multiple sub-CRDTs / segments, load on demand, so opening a doc doesn't pour millions of nodes into memory.
• Rich text: a plain sequence CRDT handles "bold spanning a concurrent insert" poorly; you need Peritext-style interval-marker CRDTs.
• Tombstone GC: physically reclaim a tombstone only once every replica has acknowledged the deletion (version vectors have passed it), else you break concurrent references.
• Undo/Redo: collaborative undo means undo your own operation, not "rewind time" — it needs per-user selective-undo semantics.
• Multi-region: give each document a home region (where its authority lives); cross-region edits route to the home region, avoiding the round-trips of global strong consistency.

Pitfalls & Interview Follow-ups

• Buggy OT transform: insert/delete/delete combinations + tie-breaks are bug-prone, and a bug means silent divergence — two documents disagree with no error. In interviews, articulate TP1/TP2 and "dodge TP2 via a central server."
• CRDT interleaving: expect "two people each paste a paragraph — why might they interleave?" Answer: concurrent inserts landing between the same anchor; tie-break guarantees convergence, not semantic coherence.
• Unbounded tombstones: a long-lived doc deleted and re-deleted drowns in tombstones without GC; the GC condition is a deep-dive point.
• LWW lost updates: Figma uses LWW for properties — two people changing color simultaneously lose one; be able to say "when a loss is acceptable vs not" (text: never; design property: fine).
• Persisting presence: storing cursor position as durable data is classic over-engineering — it's ephemeral and droppable.
• OT or CRDT? "Stable central server, want plain text without bloat, team can hold the transform" → OT (Google Docs); "want offline-first / P2P / local-first, can accept metadata overhead" → CRDT (Yjs/Automerge).

Deep Resources

• How Figma's multiplayer technology works — Evan Wallace on server-per-document, offline reconnect, LWW properties; the most readable industry writeup.
• CRDTs: The Hard Parts — Martin Kleppmann on metadata bloat, columnar encoding, interleaving, and other real pain points.
• Interleaving anomalies in collaborative text editors (PaPoC 2019) — a formal dissection of the interleaving problem.
• Yjs (Kevin Jahns, YATA) and Automerge — the two mainstream production-grade CRDT implementations; the source is the textbook.
• The Jupiter algorithm (Nichols et al., AT&T, 1995) and the Google Wave OT whitepaper — the origin of central-order OT.

Going Deeper