Case Study: Building a Real-Time Collaborative Editor — OT vs CRDT

Two people type into the same document at the same moment. Alice inserts "X" at position 5; Bob deletes the character at position 3. Their edits cross on the wire. When Alice's edit arrives at Bob's machine, position 5 no longer means what Alice meant — Bob's delete shifted everything after position 3 left by one. Apply Alice's edit naively and the "X" lands in the wrong place; do this a few thousand times a second across dozens of collaborators and the documents diverge into garbage. This is the central problem of real-time collaboration: concurrent edits to shared mutable state, applied in different orders on different machines, must converge to the same result. There are two families of solutions — Operational Transformation (OT), which powers Google Docs, and Conflict-free Replicated Data Types (CRDTs), which power newer tools like Figma and editors built on Yjs/Automerge. This case study builds a collaborative editor conceptually, derives why naive synchronization fails, contrasts OT and CRDT in depth, and lays out the architecture and operational realities of each.

The Scale and the Constraints

Collaborative editing is latency-, consistency-, and concurrency-bound all at once:

GIF via GIPHY

The two non-negotiables: local-first responsiveness (you cannot wait for a server round-trip per keystroke — edits apply to the local copy instantly and synchronize asynchronously), and convergence (every replica, regardless of the order it received concurrent operations, must end in the same state). These two requirements together rule out the naive "send positions to a server" approach, because positions are relative to a document state that's different on every machine.

Why Naive Synchronization Fails

  Initial document on all replicas:   "HELLO"  (positions 0-4)

  Alice (concurrently):  insert "X" at pos 5    →  "HELLOX"
  Bob   (concurrently):  delete char at pos 0   →  "ELLO"

  Bob receives Alice's op "insert X at pos 5" and applies it to "ELLO"
  (length 4): pos 5 is out of range / wrong location → "ELLOX" or error.
  Alice receives Bob's "delete pos 0" applied to "HELLOX" → "ELLOX".

  Both happen to land on "ELLOX" here, but flip the example (two inserts
  near each other) and they diverge: "HEXLLOY" vs "HEYLLOX".  ✗

GIF via GIPHY

The problem is that an operation's position is meaningful only relative to the exact document state it was created against. Once a concurrent operation changes that state, the position is stale. Naive last-write-wins on the whole document loses one user's edit entirely. You need a principled way to make concurrent operations commute — to produce the same result regardless of arrival order. OT and CRDT are two different answers to that.

Approach 1: Operational Transformation (OT)

OT keeps operations as position-based edits (insert(pos, char), delete(pos)) but transforms an incoming operation against any concurrent operations that the receiver has already applied, adjusting its position to account for them. The core is the transform function: given two concurrent operations, produce versions of each that, applied after the other, yield convergence.

type Op =
  | { type: 'insert'; pos: number; char: string }
  | { type: 'delete'; pos: number };

// transform(a, b): adjust op `a` to apply AFTER op `b` was already applied.
function transform(a: Op, b: Op): Op {
  if (a.type === 'insert' && b.type === 'insert') {
    // b inserted before or at a's position → shift a right by 1
    if (b.pos < a.pos || (b.pos === a.pos && tieBreak(b, a))) {
      return { ...a, pos: a.pos + 1 };
    }
    return a;
  }
  if (a.type === 'insert' && b.type === 'delete') {
    return b.pos < a.pos ? { ...a, pos: a.pos - 1 } : a;  // b removed a char before a
  }
  if (a.type === 'delete' && b.type === 'insert') {
    return b.pos <= a.pos ? { ...a, pos: a.pos + 1 } : a;
  }
  // delete vs delete
  if (b.pos < a.pos) return { ...a, pos: a.pos - 1 };
  if (b.pos === a.pos) return { type: 'noop' } as any;     // both deleted same char
  return a;
}

GIF via GIPHY

The tieBreak (using a site/user ID) is essential: when two inserts target the same position, some deterministic rule must decide ordering, or the two replicas would order them differently and diverge. OT systems use a total order over sites to break ties consistently everywhere.

The hard part isn't the two-operation transform — it's that OT must transform an incoming op against the entire sequence of concurrent ops the receiver applied since the common ancestor, in the right order. This requires a central server to assign a canonical order to operations (Google Docs uses one). The server sequences ops; each client transforms incoming ops against the ops it has that the server hadn't seen when it sent theirs. Getting the transform property correct for all op-pair combinations (the "TP1/TP2" convergence properties) is notoriously subtle — many published OT algorithms had convergence bugs for years.

Approach 2: CRDTs (Conflict-free Replicated Data Types)

CRDTs sidestep transformation entirely by changing the data model. Instead of positions (which are unstable), every character gets a globally unique, immutable identifier that encodes its position as a value in a dense, totally-ordered space. Inserting "between" two characters means generating an ID that sorts between their IDs. Because IDs are unique and the order is total, concurrent operations commute by construction — applying them in any order yields the same set of characters in the same order. No transform, no central sequencer required for correctness.

// A sequence CRDT (RGA-style): each char has a unique, ordered id.
// id = fractional position + site id (for uniqueness + deterministic tie-break)
interface Char {
  id: string;          // e.g. "0.5#siteA" — sorts deterministically
  value: string;
  deleted: boolean;    // tombstone: deletes mark, don't remove (for convergence)
}

// Insert between left and right by generating an id strictly between them.
function insertBetween(left: Char, right: Char, value: string, site: string): Char {
  const newPos = midpoint(left.id, right.id);   // dense ordering: always room between
  return { id: `${newPos}#${site}`, value, deleted: false };
}

// Merge is just union + sort by id. Commutative, associative, idempotent.
function merge(a: Char[], b: Char[]): Char[] {
  const byId = new Map<string, Char>();
  for (const c of [...a, ...b]) {
    const existing = byId.get(c.id);
    // tombstone wins (a delete anywhere means deleted everywhere)
    byId.set(c.id, existing?.deleted ? existing : c);
  }
  return [...byId.values()].sort((x, y) => (x.id < y.id ? -1 : 1));
}

Two CRDT properties make this work:

1. Stable, dense identifiers. Each character's ID never changes (unlike a position), and you can always generate an ID between any two existing IDs (a dense order, like rationals). So "insert X between H and E" is unambiguous on every replica forever.
2. Tombstones for deletion. Deleting marks a character deleted rather than removing it, because a concurrent insert might reference it as a neighbor. Removing it outright could break convergence. The visible text filters out tombstones.

Merging is a commutative, associative, idempotent set union — the mathematical definition of a CRDT. Replicas can sync peer-to-peer, in any order, even after long offline periods, and provably converge.

OT vs CRDT: The Core Tradeoff

                    OT                          CRDT
  Data model        positions + transform       unique ids, dense order
  Convergence       via transform + server seq  by construction (commutative)
  Central server    required (for op ordering)   optional (P2P possible)
  Metadata overhead low (ops are small)          per-char id + tombstones (high)
  Offline/P2P       hard                         natural
  Algorithm risk    transform correctness subtle merge is simple/provable
  Memory growth     bounded                      tombstones accumulate

GIF via GIPHY

The honest summary: OT is metadata-cheap but algorithm-expensive and server-bound; CRDT is algorithm-simple and decentralization-friendly but metadata-expensive. OT shines when you already have a central server and document size/memory matters (Google Docs). CRDTs shine for offline-first, peer-to-peer, and local-first apps where the merge simplicity and no-server property outweigh the per-character overhead (Yjs, Automerge, Figma's model). Modern CRDT implementations (Yjs) have aggressively optimized the overhead — run-length encoding of IDs, tombstone GC — narrowing the gap that historically favored OT.

System Architecture (CRDT-based, with a Sync Server)

┌──────────────┐   local edit applies instantly (CRDT op)   ┌──────────────┐
│  Client A    │───────────────────────────────────────────►│  Local doc A │
│  (editor)    │                                             └──────────────┘
└──────┬───────┘  CRDT update (binary, encoded ops)
       │
       ▼  WebSocket
┌──────────────────────────────────────────────────────────────────────┐
│  SYNC SERVER (relay + persistence — NOT a sequencer for correctness)  │
│   • broadcast updates to other clients in the room                    │
│   • persist the CRDT doc (snapshot + update log)                      │
│   • awareness channel: cursors, selections, presence (ephemeral)      │
└──────┬───────────────────────────────────────────────────┬───────────┘
       ▼                                                    ▼
┌──────────────┐                                     ┌──────────────┐
│  Client B    │  merges incoming update (commutes)  │  Client C    │
└──────────────┘                                     └──────────────┘

Even with CRDTs, a server is useful — but as a relay and persistence layer, not a correctness-critical sequencer. It broadcasts updates and stores the document, but convergence doesn't depend on it ordering anything. A separate awareness/presence channel carries ephemeral state (cursor positions, selections, who's online) that doesn't need to be part of the convergent document — losing a cursor update is harmless, so it's sent unreliably and not persisted.

Production Realities and Incidents

Incident 1: Tombstone Bloat

A long-lived CRDT document edited heavily for months grew to many times its visible size because every deleted character left a tombstone. Load times and memory ballooned. Root cause: tombstones never collected. Fix: periodic garbage collection of tombstones once all replicas have acknowledged the deletes (a version-vector watermark proves no replica still needs them as neighbors), plus run-length encoding of contiguous IDs. CRDT overhead is manageable but must be actively managed.

Incident 2: The Cursor That Jumped

GIF via GIPHY

After a remote edit inserted text before the user's cursor, the cursor stayed at its numeric offset and visually jumped to the wrong place. Root cause: cursor stored as a numeric position, which is unstable under concurrent edits — the same instability that breaks naive sync. Fix: store the cursor as a relative position anchored to a character ID (CRDT) or transformed alongside operations (OT), so it tracks its logical location as the document changes around it. Cursors have the same position-stability problem as edits.

Incident 3: Intention Violation in OT

An OT system's transform for a specific insert/delete overlap had a subtle bug: under a particular concurrent sequence, a user's pasted block was split and interleaved with another's text — converged (both replicas agreed) but wrong (intention violated). Root cause: the transform satisfied convergence but not intention preservation for that case. Fix: corrected transform logic and extensive property-based testing of transform pairs. OT correctness is not just "do replicas agree" — it's "do they agree on the right thing," which is far harder to verify.

Tradeoffs and Engineering Decisions

• OT vs CRDT. Choose OT when you have a reliable central server, need minimal per-character overhead, and can invest in getting transforms provably correct (Google Docs' bet). Choose CRDT when you want offline-first/peer-to-peer, simpler convergence guarantees, and can pay the metadata cost (now much reduced by libraries like Yjs). For most new applications, mature CRDT libraries are the pragmatic default — you get convergence for free instead of implementing and verifying transforms.
• Local-first vs server-authoritative. Applying edits locally first is mandatory for responsiveness but means the local state is temporarily ahead of the server and other clients — you must handle the reconciliation. A server-authoritative model (wait for server ack) is simpler but adds a round-trip per edit, which is unacceptable for typing.
• Tombstone GC timing. Collecting tombstones too early risks breaking convergence for a replica that hasn't synced; too late wastes memory. Gating GC on a version-vector watermark (all known replicas have seen the delete) is correct but requires tracking replica state — complexity for memory.
• Reliable doc channel vs unreliable presence channel. Splitting convergent document state (reliable, persisted, ordered-merge) from ephemeral awareness (unreliable, dropped freely) keeps the hot presence updates (cursors moving constantly) from bloating the persistent document and lets each channel use the right delivery guarantees.
• Rich text complexity. Both OT and CRDT get substantially harder for rich text (formatting spans, nested structure) than plain text — formatting attributes are concurrent edits to ranges, not just characters. This is where many implementations have the most bugs; lean on a battle-tested library rather than rolling your own rich-text CRDT/OT.

GIF via GIPHY

Key Takeaways

• Real-time collaboration's core problem is concurrent edits applied in different orders on different replicas must converge — and naive position-based sync fails because a position is only meaningful relative to the exact state it was created against.
• The two non-negotiables are local-first responsiveness (apply edits instantly, sync async) and guaranteed convergence (all replicas reach identical state regardless of arrival order).
• OT keeps position-based ops and transforms incoming ops against concurrent ones; it's metadata-cheap but requires a central sequencer and notoriously subtle transform correctness (convergence and intention preservation).
• CRDTs give every character a stable, unique, densely-ordered ID so operations commute by construction — merge is a simple commutative/associative/idempotent union, enabling peer-to-peer and offline editing, at the cost of per-character metadata and tombstones.
• Choose OT for server-centric, memory-sensitive systems with the budget to verify transforms; choose CRDT (via a mature library like Yjs/Automerge) for offline-first/P2P and simpler convergence — the modern default for new apps.
• Even CRDT systems use a server as a relay + persistence layer, not a correctness sequencer, and split the reliable convergent document from an unreliable ephemeral presence channel (cursors, selections).
• Cursors suffer the same position-instability as edits — anchor them to character IDs/relative positions, and actively manage tombstone GC (version-vector watermarks) to bound document growth.

GIF via GIPHY