Real-Time Collaborative Editing: Operational Transformation vs. CRDT Architecture

Real-time collaboration is the defining capability of modern productivity software. Applications like Google Docs, Figma, Notion, and Linear allow multiple geographically distributed users to type, edit, draw, and reorganize content simultaneously over public networks—without locking the document and without overwriting each other’s work.

Solving concurrent document editing is one of the classic problems of distributed systems engineering. When two users type concurrently without coordination, traditional string indices diverge, text scrambles, and data is lost.

This lesson explores the two primary architectures for real-time collaboration: Operational Transformation (OT) and Conflict-Free Replicated Data Types (CRDTs).

1. Problem and Motivation

Consider two users, Alice and Bob, collaborating on a shared document that currently contains the word: $$\text{Document State: }\text{"CAT"}$$

Alice and Bob perform concurrent edits before their devices exchange network packets:

• Alice inserts 'O' at index $1$ (intending to write "COAT"): $${\text{op}}_A=\text{Insert}(1,\text{’O’})$$
• Bob inserts 'S' at index $3$ (intending to write "CATS"): $${\text{op}}_B=\text{Insert}(3,\text{’S’})$$

The Naive Replication Failure

• Alice applies ${\text{op}}_A$ locally $\to \text{"COAT"}$. She receives Bob’s ${\text{op}}_B=\text{Insert}(3,\text{’S’})$. Alice applies it literally at index 3 $\to \text{"COAST"}$ (incorrect).
• Bob applies ${\text{op}}_B$ locally $\to \text{"CATS"}$. He receives Alice’s ${\text{op}}_A=\text{Insert}(1,\text{’O’})$. Bob applies it literally at index 1 $\to \text{"COATS"}$.

Alice’s document is "COAST", while Bob’s document is "COATS". The replicas have diverged permanently!

To ensure all replicas converge deterministically, systems must use either Operational Transformation or Conflict-Free Replicated Data Types.

2. Mental Model & Architectural Taxonomy

SYSTEM ARCHITECTURE BLUEPRINTAPPLICATION ARCHITECTURES

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 3

1. Initial Doc State: "CAT" (Length = 3) & Client A (Alice)

Establishes the ingress and structural boundary across Initial Doc State: "CAT" (Length = 3) & Client A (Alice): Insert 'O' at index 1; Local: "COAT"; op_A = ins(1, 'O').

Architectural Invariant: Insert 'S' at index 3.

ARCHITECTURAL FLOW · STEP 2 OF 3

2. Central Server: Transformation Function T(op_B, op_A) & Advantages: Minimal memory overhead (index strings)

Coordinates core data-plane execution and state transitions through Central Server: Transformation Function T(op_B, op_A) & Advantages: Minimal memory overhead (index strings): Because op_A inserted before op_B (1 < 3), op_B index MUST shift by +1 to compensate! Transformed op_B' = ins(4, 'S'); Result at all clients: "COATS" (Converged!); Critical Weakness: Central Single Point of Failure.

Architectural Invariant: Characters never move relative to array indexes; they link to parent IDs.

ARCHITECTURAL FLOW · STEP 3 OF 3

3. Mathematical Semilattice Properties (Merge ⊔) & Advantages: Flawless Offline Sync & Peer-to-Peer

Enforces durability, state convergence, and output verification across Mathematical Semilattice Properties (Merge ⊔) & Advantages: Flawless Offline Sync & Peer-to-Peer: Any two replicas merge deterministically via Least Upper Bound; Commutative: A ⊔ B = B ⊔ A (Arrival order doesn't matter); Associative: (A ⊔ B) ⊔ C = A ⊔ (B ⊔ C) (Batch grouping doesn't matter).

Architectural Invariant: Idempotent: A ⊔ A = A (Duplicate network packets have zero effect) Guarantees Strong Eventual Consistency (SEC) without a central server!.

Operational Transformation (OT) vs. CRDTs

3. Deep Dive: Operational Transformation (OT)

Operational Transformation was introduced in 1989 by Ellis and Gibbs. The core insight of OT is: Rather than altering the document directly, operations are mathematically transformed before execution to account for concurrent operations.

The Transformation Function $T({\text{op}}_1,{\text{op}}_2)$

Given two concurrent operations ${\text{op}}_A$ and ${\text{op}}_B$:

• $T({\text{op}}_A,{\text{op}}_B)$ produces ${\text{op}}_A^{\prime }$, representing the intention of ${\text{op}}_A$ after ${\text{op}}_B$ has already executed.
• $T({\text{op}}_B,{\text{op}}_A)$ produces ${\text{op}}_B^{\prime }$, representing the intention of ${\text{op}}_B$ after ${\text{op}}_A$ has executed.

For our "CAT" example:

• Alice: ${\text{op}}_A=\text{Insert}(1,\text{’O’})$
• Bob: ${\text{op}}_B=\text{Insert}(3,\text{’S’})$

Because Alice inserted at index $1$ (which is $<3$), Bob’s insertion target shifted right by one position! $$T({\text{op}}_B,{\text{op}}_A)⟶{\text{op}}_B^{\prime }=\text{Insert}(3+1,\text{’S’})=\text{Insert}(4,\text{’S’})$$

When Alice applies ${\text{op}}_B^{\prime }$: $$\text{"COAT"}+\text{Insert}(4,\text{’S’})⟶\text{"COATS"}$$ Both Alice and Bob converge to "COATS".

Why OT Requires a Central Sequencer

In a multi-user environment ($>2$ users), operations can arrive in arbitrary permutations. Proving the TP2 property (Transformation Property 2: transforming over two concurrent operations in either order yields the same result) across decentralized peers proved mathematically fraught and prone to edge-case desynchronization bugs. Google Docs solved this by channeling all operations through a central server, which assigns a strict monotonic revision number ($v_1,v_2,v_3$) and forces clients to rebase locally.

4. Deep Dive: Conflict-Free Replicated Data Types (CRDTs)

CRDTs (formalized by Marc Shapiro et al. in 2011) take a radically different approach: Avoid index rewrites entirely by assigning every element an immutable, globally unique identifier.

4.1 Replicated Growable Array (RGA)

In an RGA sequence CRDT:

• Every character is represented by a node containing: $$\text{Node}=\{\text{id}:(\text{client\_id},\text{lamport\_clock}),\text{char}:\text{’X’},\text{parent\_id}:\text{prev\_node\_id},\text{deleted}:\text{false}\}$$
• Characters are ordered in a causal tree. If two users insert after the same character concurrently, ties are broken deterministically using Lamport timestamps and unique client IDs: $$({\text{clock}}_A,{\text{client}}_A)>({\text{clock}}_B,{\text{client}}_B)⟺{\text{clock}}_A>{\text{clock}}_B\vee ({\text{clock}}_A={\text{clock}}_B\wedge {\text{client}}_A>{\text{client}}_B)$$

4.2 Mathematical Semilattice Properties

A state-based CRDT (CvRDT) forms a join-semilattice equipped with a partial order $\le$ and a merge operator $\bigsqcup$ (least upper bound) satisfying three axioms:

1. Commutativity: $A\bigsqcup B=B\bigsqcup A$
   (Packets arriving out of order produce the same result).
2. Associativity: $(A\bigsqcup B)\bigsqcup C=A\bigsqcup (B\bigsqcup C)$
   (Network messages batched into packets produce the same result).
3. Idempotency: $A\bigsqcup A=A$
   (Duplicate packet delivery causes zero side effects).

5. Production TypeScript Simulation: Replicated Growable Array (RGA) CRDT

Below is an executable sequence CRDT supporting concurrent character insertions, Lamport clock ordering, and tombstone deletions:

export interface CharNode {
  id: string; // e.g. "clientA:1"
  char: string;
  clock: number;
  clientId: string;
  deleted: boolean;
  next: CharNode | null;
}

export class RgaDocument {
  public head: CharNode = {
    id: "START",
    char: "",
    clock: 0,
    clientId: "",
    deleted: true,
    next: null,
  };
  private clock = 0;

  constructor(public readonly clientId: string) {}

  public insertAfter(targetId: string, char: string): CharNode {
    this.clock++;
    const newNode: CharNode = {
      id: `${this.clientId}:${this.clock}`,
      char,
      clock: this.clock,
      clientId: this.clientId,
      deleted: false,
      next: null,
    };

    this.integrate(newNode, targetId);
    return newNode;
  }

  public delete(id: string): void {
    let curr: CharNode | null = this.head;
    while (curr) {
      if (curr.id === id) {
        curr.deleted = true; // Mark tombstone
        return;
      }
      curr = curr.next;
    }
  }

  /**
   * Deterministically merges an incoming remote node into the local RGA sequence
   */
  public integrate(newNode: CharNode, targetId: string): void {
    // 1. Locate the parent node
    let prev: CharNode | null = this.head;
    while (prev && prev.id !== targetId) {
      prev = prev.next;
    }
    if (!prev) {
      prev = this.head; // Fallback to start
    }

    // Advance clock to maintain causality
    this.clock = Math.max(this.clock, newNode.clock);

    // 2. Scan past any concurrent sibling nodes with higher Lamport priority
    let curr = prev.next;
    while (curr) {
      if (curr.clock > newNode.clock) {
        prev = curr;
        curr = curr.next;
      } else if (curr.clock === newNode.clock && curr.clientId > newNode.clientId) {
        prev = curr;
        curr = curr.next;
      } else {
        break; // Found correct deterministic insertion slot
      }
    }

    newNode.next = curr;
    prev.next = newNode;
  }

  public toString(): string {
    let result = "";
    let curr = this.head.next;
    while (curr) {
      if (!curr.deleted) {
        result += curr.char;
      }
      curr = curr.next;
    }
    return result;
  }
}

function runDemo(): void {
  console.log('=== Collaborative Real-Time Text Editing: RGA CRDT ===');
  const docA = new RgaDocument('client-A');
  const docB = new RgaDocument('client-B');
  const n1 = docA.insertAfter('START', 'H');
  const n2 = docA.insertAfter(n1.id, 'i');
  console.log('Client A doc: ' + docA.toString());
  docB.integrate({ ...n1, next: null }, 'START');
  docB.integrate({ ...n2, next: null }, n1.id);
  console.log('Client B doc: ' + docB.toString());
  const nA = docA.insertAfter(n2.id, '!');
  const nB = docB.insertAfter(n2.id, '?');
  docB.integrate({ ...nA, next: null }, n2.id);
  docA.integrate({ ...nB, next: null }, n2.id);
  console.log('Doc A converged: ' + docA.toString());
  console.log('Doc B converged: ' + docB.toString());
  console.log('Bitwise convergence: ' + (docA.toString() === docB.toString()));
}
runDemo();

6. Open-Source Implementation Analysis

A. Yjs (High-Performance Modern CRDT)

Yjs is written by Kevin Jahns and powers collaborative editing in Jupyter, GitBook, and affine.pro:

• Struct Store Optimization: Traditional academic CRDTs store every character as an individual heap object (incurring a $20\times -50\times$ RAM expansion). Yjs consolidates sequential characters typed by the same user into contiguous string slices inside a flat binary array (Item structs), cutting RAM overhead by $90\%$.
• Binary Sync Protocol: Encodes document updates into compact byte buffers using variable-length integer encoding (lib0), streaming updates over WebSockets or WebRTC.

B. Figma: Scene Graph CRDT

Figma does not model documents as text characters. A design file is an acyclic scene graph of trees:

• Every canvas frame, rectangle, and vector has a globally unique 64-bit ID.
• Properties (e.g., width, fill_color, x_pos) are independent LWW (Last-Write-Wins) registers using Lamport clocks.
• Z-index layer order uses Fractional Indexing (e.g., placing an item between layer 0.5 and 0.75 assigns 0.625), enabling reordering without modifying neighboring nodes.

7. Failure Modes & Operational War Stories

War Story: The Infinite Tombstone Memory Leak

• Incident: A collaborative text platform using an early CRDT library crashed user browser tabs with JavaScript heap out of memory after two weeks of heavy editing.
• Root Cause: In sequence CRDTs, deleted characters are marked with tombstones (deleted: true) so concurrent operations can still resolve their relative positions. In this platform, an automated linter repeatedly re-formatted $50,000$ lines of code every 5 minutes. Within 14 days, the document accumulated $180\text{ million}$ invisible tombstone nodes in memory!
• Mitigation:
  1. Implemented Garbage Collection of Tombstones: When all active collaborating clients have acknowledged seeing a deletion (proven via state vectors), tombstones that have no dependent child nodes are pruned.
  2. Consolidated runs of adjacent deleted characters into single summary ranges.

8. Operational Decision Guide

9. Hands-on Operational Drills

1. Simulate Concurrent RGA Merging: Instantiate two RgaDocument instances: Doc A and Doc B. Starting from "CAT":
   • On Doc A, insert 'O' after 'C'.
   • On Doc B, insert 'S' after 'T'.
   • Exchange the generated nodes between Doc A and Doc B via integrate(). Verify that both documents converge to "COATS".
2. Verify Tombstone Deletion: Delete character 'O' on Doc A. Verify that toString() outputs "CATS", while the underlying node remains intact in memory to preserve causal linked ordering.

10. Trade-offs & Collaborative Engine Alternatives

11. Authoritative References & Foundational Research

• Marc Shapiro et al. (2011), “Conflict-Free Replicated Data Types”, SSS ‘11 — doi.org/10.1007/978-3-642-24550-3_29
• Martin Kleppmann and Alastair R. Beresford (2017), “A Conflict-Free Replicated JSON Datatype”, IEEE TPDS — doi.org/10.1109/TPDS.2017.2697382
• Kevin Jahns (2020), “Yjs: Shared Data Types for Building Collaborative Software Architecture” — github.com/yjs/yjs
• Version Context: Reference implementations align with Yjs 13.6+ and Automerge 2.0+.