System Design (HLD)Real-Time Architecture Patterns

Real-Time Architecture Patterns

LevelAdvanced

Duration90 mins

TopicReal-Time Architecture Patterns

3 / 5

Real-Time Collaboration

When Everyone Edits at Once

Open a Google Doc with a colleague and start typing simultaneously. Watch as their cursor moves, their text appears character by character, and somehow—magically—your edits and theirs merge seamlessly without conflicts. This is real-time collaboration, and it's one of the most complex challenges in distributed systems.

The fundamental problem: multiple users modifying the same data structure concurrently, across an unreliable network, with the expectation that all participants' views converge to the same final state.

This isn't just about text editors. Real-time collaboration powers:

Document editing: Google Docs, Notion, Coda, Dropbox Paper
Design tools: Figma, Miro, FigJam, Canva
Code editors: VS Code Live Share, Replit, CodeSandbox
Spreadsheets: Google Sheets, Airtable, Coda
Whiteboards: Miro, Excalidraw, tldraw
Project management: Linear, Asana, Monday.com

This page dives deep into the algorithms, data structures, and architectural patterns that make real-time collaboration possible.

What You Will Learn

By the end of this page, you will understand: • Why concurrent editing is fundamentally hard • How Operational Transformation (OT) achieves consistency • How Conflict-free Replicated Data Types (CRDTs) offer an alternative approach • The tradeoffs between OT and CRDTs • How industry leaders architect their collaborative systems • Practical implementation patterns for common use cases

The Concurrency Problem

To understand why real-time collaboration is hard, consider a simple scenario:

Initial state: "Hello"

Alice inserts " World" at position 5 → "Hello World"
Bob inserts "!" at position 5 → "Hello!"

If both operations happen simultaneously and are applied naively:

If Alice's operation applies first, then Bob's "!" goes to position 5: "Hello! World"
If Bob's operation applies first, then Alice's " World" goes to position 5: "Hello World!"

Different outcomes depending on order! This is the convergence problem: how do we ensure all participants eventually see the same result?

Key challenges:

Real-Time Collaboration Challenges
Challenge	Description	Why It's Hard
Convergence	All replicas must reach the same final state	Network delays mean operations arrive in different orders
Intention Preservation	User's intended effect should be maintained	Position-based operations become invalid as document changes
Causality	Operations should respect happens-before relationships	Clock synchronization across distributed clients is imperfect
Performance	Sub-100ms latency for responsive editing	Coordination adds latency; going through server is slow
Offline Support	Users should be able to work disconnected	Merging divergent offline changes is complex
Undo/Redo	Users expect their undo to undo their action	In collaborative editing, what exactly should undo do?

Converting Mermaid diagram...

Naive Solutions That Don't Work:

Locking: Lock the document while someone edits. Destroys real-time experience.
Last-Write-Wins: Later operation overwrites earlier. Loses data, intention lost.
Manual Conflict Resolution: Show conflicts to users. Terrible UX for frequent operations.
Turn-Taking: Only one person can type at a time. Not really "collaboration."

We need algorithms that automatically merge concurrent operations while preserving user intent.

The CAP Theorem Implication

Real-time collaboration systems typically prioritize Availability and Partition Tolerance over strict Consistency (AP in CAP terms). Users can always edit locally, even if disconnected. The system eventually converges, but may show temporary inconsistency. This is acceptable because users see updates quickly and the final state is deterministic.

Operational Transformation (OT)

Operational Transformation (OT) is the classic solution, invented in 1989 and used by Google Docs, Google Sheets, and Microsoft Office Online.

Core Idea: When concurrent operations conflict, transform one operation so it can be applied after the other while preserving both users' intentions.

The Transform Function:

Given two concurrent operations a and b (neither happened-before the other), we need a transform function T such that:

apply(apply(state, a), T(b, a)) = apply(apply(state, b), T(a, b))

In other words: applying a then transformed-b should equal applying b then transformed-a.

Converting Mermaid diagram...

Text OT Transform Examples:

Scenario	Operation A	Operation B	T(B, A)	Explanation
Insert before insert	Insert "X" @3	Insert "Y" @5	Insert "Y" @6	A shifted B's position by 1
Insert after insert	Insert "X" @5	Insert "Y" @3	Insert "Y" @3	A didn't affect B's position
Insert vs delete	Insert "X" @3	Delete @5-6	Delete @6-7	Insertion shifted the delete range
Overlapping deletes	Delete @3-5	Delete @4-6	Delete @3-4	Merge overlapping deletes

The Transform Function for Text:

ot_transform.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
// Operational Transformation for text operations
 
type Operation = InsertOp | DeleteOp | RetainOp;
 
interface InsertOp {
  type: 'insert';
  position: number;
  text: string;
}
 
interface DeleteOp {
  type: 'delete';
  position: number;
  length: number;
}
 
interface RetainOp {
  type: 'retain';
  count: number;
}
 
/**
 * Transform operation B against operation A.
 * Returns a new operation B' that can be applied after A
 * and achieves the same result as if A and B had been applied
 * in the opposite order with A transformed.
 */
function transform(opB: Operation, opA: Operation): Operation {
  // Insert vs Insert
  if (opA.type === 'insert' && opB.type === 'insert') {
    if (opB.position <= opA.position) {
      // B is before or at A's position - no change needed
      return opB;
    } else {
      // B is after A's position - shift by A's length
      return {
        ...opB,
        position: opB.position + opA.text.length,
      };
    }
  }
 
  // Insert vs Delete
  if (opA.type === 'insert' && opB.type === 'delete') {
    if (opB.position >= opA.position) {
      // Delete is after insert - shift position
      return {
        ...opB,
        position: opB.position + opA.text.length,
      };
    } else if (opB.position + opB.length <= opA.position) {
      // Delete is entirely before insert - no change
      return opB;
    } else {
      // Delete spans the insert position - split the delete
      // This is where it gets complex...
      return {
        ...opB,
        position: opB.position,
        length: opB.length + opA.text.length,
      };
    }
  }
 
  // Delete vs Insert
  if (opA.type === 'delete' && opB.type === 'insert') {
    if (opB.position <= opA.position) {
      // Insert is before delete - no change
      return opB;
    } else if (opB.position >= opA.position + opA.length) {
      // Insert is after delete - shift back
      return {
        ...opB,
        position: opB.position - opA.length,
      };
    } else {
      // Insert is within deleted region - move to delete start
      return {
        ...opB,
        position: opA.position,
      };
    }
  }
 
  // Delete vs Delete
  if (opA.type === 'delete' && opB.type === 'delete') {
    // Handle overlapping deletes
    const aStart = opA.position;
    const aEnd = opA.position + opA.length;
    const bStart = opB.position;
    const bEnd = opB.position + opB.length;
 
    if (bEnd <= aStart) {
      // B entirely before A - no change
      return opB;
    } else if (bStart >= aEnd) {
      // B entirely after A - shift back
      return {
        ...opB,
        position: opB.position - opA.length,
      };
    } else {
      // Overlapping deletes - compute remaining delete
      const newStart = Math.min(bStart, aStart);
      const overlapStart = Math.max(bStart, aStart);
      const overlapEnd = Math.min(bEnd, aEnd);
      const overlapLength = overlapEnd - overlapStart;
      
      return {
        type: 'delete',
        position: bStart < aStart ? bStart : aStart,
        length: opB.length - overlapLength,
      };
    }
  }
 
  return opB; // Default: no transformation needed
}
 
/**
 * Compose two operations into a single operation
 * that has the same effect as applying both sequentially.
 */
function compose(opA: Operation, opB: Operation): Operation[] {
  // Returns a list because some compositions result in multiple operations
  // This is simplified - real implementations handle complex compositions
  return [opA, opB];
}

OT Architecture (Server-Centric):

Google Docs uses a central server to serialize operations:

Client applies operation locally (optimistic update)
Client sends operation to server with version number
Server transforms incoming operation against any concurrent operations
Server applies operation, increments version, broadcasts to other clients
Other clients transform their pending operations and apply

This approach ensures:

A single authoritative timeline of operations
All clients eventually converge
Server can persist operation log for history/undo

OT Complexity:

OT is notoriously difficult to implement correctly. The transform function must satisfy two properties:

TP1 (Transformation Property 1): apply(apply(s, a), T(b, a)) = apply(apply(s, b), T(a, b))
TP2 (Transformation Property 2): T(T(c, a), T(b, a)) = T(T(c, b), T(a, b))

TP2 is especially tricky and many published OT algorithms had bugs. Google spent years perfecting their implementation.

OT Is Hard to Get Right

Building OT from scratch is error-prone. The academic literature contains numerous 'correct' algorithms later found to have bugs. If you need OT, use a battle-tested library like ShareDB (Node.js), Yjs with y-websocket, or Google's own implementation via their APIs. Custom implementations require extensive formal verification.

Conflict-free Replicated Data Types (CRDTs)

CRDTs take a fundamentally different approach: instead of transforming operations, they design data structures that can be merged without conflicts by construction.

Core Insight: If operations are commutative (order doesn't matter) and idempotent (applying twice has same effect), then concurrent operations merge trivially.

Two Flavors of CRDTs:

State-based CRDTs (CvRDTs): Merge complete states using a merge function
Operation-based CRDTs (CmRDTs): Merge operations directly

Simple CRDT Examples:

Common CRDT Types
CRDT	Description	Merge Operation	Use Case
G-Counter	Grow-only counter	Max of each replica's count	View counts, likes
PN-Counter	Counter with increment/decrement	Separate G-Counters for pos/neg	Inventory, karma
G-Set	Grow-only set	Set union	Seen messages, tags
2P-Set	Set with add and remove	Separate add/remove sets	Simple collections
LWW-Register	Last-writer-wins register	Take value with highest timestamp	Simple properties
OR-Set	Observed-remove set	Track unique add operations	Collaborative lists
RGA	Replicated growable array	Unique IDs between elements	Text editing
YATA	Yet Another Transformation Approach	Optimized for text operations	Real-time text (Yjs)

crdt_examples.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
// CRDT Examples: G-Counter and G-Set
 
/**
 * G-Counter: Grow-only counter
 * Each replica maintains its own count; merge takes max of each.
 */
class GCounter {
  // Map of replica ID to that replica's count
  private counts: Map<string, number> = new Map();
  private replicaId: string;
 
  constructor(replicaId: string) {
    this.replicaId = replicaId;
    this.counts.set(replicaId, 0);
  }
 
  increment(): void {
    const current = this.counts.get(this.replicaId) || 0;
    this.counts.set(this.replicaId, current + 1);
  }
 
  value(): number {
    let sum = 0;
    for (const count of this.counts.values()) {
      sum += count;
    }
    return sum;
  }
 
  // Merge with another G-Counter (commutative, associative, idempotent)
  merge(other: GCounter): void {
    for (const [replicaId, count] of other.counts) {
      const current = this.counts.get(replicaId) || 0;
      this.counts.set(replicaId, Math.max(current, count));
    }
  }
 
  // Serialize for transmission
  toJSON(): Record<string, number> {
    return Object.fromEntries(this.counts);
  }
 
  static fromJSON(replicaId: string, data: Record<string, number>): GCounter {
    const counter = new GCounter(replicaId);
    counter.counts = new Map(Object.entries(data));
    return counter;
  }
}
 
/**
 * LWW-Element-Set: Last-Writer-Wins Set
 * Each element has an add timestamp and optional remove timestamp.
 * Element is in set if add timestamp > remove timestamp.
 */
class LWWSet<T> {
  private addSet: Map<T, number> = new Map();  // element -> add timestamp
  private removeSet: Map<T, number> = new Map();  // element -> remove timestamp
 
  add(element: T, timestamp: number = Date.now()): void {
    const currentAdd = this.addSet.get(element) || 0;
    this.addSet.set(element, Math.max(currentAdd, timestamp));
  }
 
  remove(element: T, timestamp: number = Date.now()): void {
    const currentRemove = this.removeSet.get(element) || 0;
    this.removeSet.set(element, Math.max(currentRemove, timestamp));
  }
 
  has(element: T): boolean {
    const addTime = this.addSet.get(element);
    if (addTime === undefined) return false;
    
    const removeTime = this.removeSet.get(element) || 0;
    return addTime > removeTime;  // Bias towards adds (add wins on tie)
  }
 
  values(): T[] {
    const result: T[] = [];
    for (const element of this.addSet.keys()) {
      if (this.has(element)) {
        result.push(element);
      }
    }
    return result;
  }
 
  merge(other: LWWSet<T>): void {
    // Merge add sets (take max timestamp for each element)
    for (const [element, timestamp] of other.addSet) {
      const current = this.addSet.get(element) || 0;
      this.addSet.set(element, Math.max(current, timestamp));
    }
    
    // Merge remove sets (take max timestamp for each element)
    for (const [element, timestamp] of other.removeSet) {
      const current = this.removeSet.get(element) || 0;
      this.removeSet.set(element, Math.max(current, timestamp));
    }
  }
}
 
/**
 * RGA (Replicated Growable Array) - simplified version for text
 * 
 * Key insight: Instead of positions, use unique IDs for each character.
 * Insert "between" two IDs, not at a position.
 * This makes inserts commutative.
 */
interface RGANode {
  id: string;           // Unique ID: "replicaId:sequenceNumber"
  char: string;         // The character (or tombstone marker)
  deleted: boolean;     // Tombstone for deleted characters
  afterId: string | null; // ID of the node this comes after
}
 
class RGAText {
  private nodes: Map<string, RGANode> = new Map();
  private replicaId: string;
  private sequenceNumber: number = 0;
 
  constructor(replicaId: string) {
    this.replicaId = replicaId;
    // Create sentinel node at start
    const sentinel: RGANode = {
      id: 'ROOT',
      char: '',
      deleted: false,
      afterId: null,
    };
    this.nodes.set('ROOT', sentinel);
  }
 
  generateId(): string {
    return `${this.replicaId}:${++this.sequenceNumber}`;
  }
 
  // Insert character after the node with the given ID
  insert(afterId: string, char: string): RGANode {
    const id = this.generateId();
    const node: RGANode = {
      id,
      char,
      deleted: false,
      afterId,
    };
    this.nodes.set(id, node);
    return node;
  }
 
  delete(id: string): void {
    const node = this.nodes.get(id);
    if (node) {
      node.deleted = true;  // Tombstone, don't actually remove
    }
  }
 
  // Merge incoming node (idempotent, commutative)
  mergeNode(node: RGANode): void {
    if (this.nodes.has(node.id)) {
      // Already have this node - merge tombstone status
      const existing = this.nodes.get(node.id)!;
      existing.deleted = existing.deleted || node.deleted;
    } else {
      this.nodes.set(node.id, { ...node });
    }
  }
 
  // Convert to string (traverse linked structure)
  toString(): string {
    const ordered = this.getOrderedNodes();
    return ordered
      .filter(n => !n.deleted && n.id !== 'ROOT')
      .map(n => n.char)
      .join('');
  }
 
  private getOrderedNodes(): RGANode[] {
    // Build ordered list by following afterId links
    // This is O(n²) for simplicity; real implementations optimize this
    const ordered: RGANode[] = [];
    const childrenOf = new Map<string, RGANode[]>();
    
    for (const node of this.nodes.values()) {
      const afterId = node.afterId || 'ROOT';
      if (!childrenOf.has(afterId)) {
        childrenOf.set(afterId, []);
      }
      childrenOf.get(afterId)!.push(node);
    }
 
    // Sort children by ID for deterministic ordering
    for (const children of childrenOf.values()) {
      children.sort((a, b) => a.id.localeCompare(b.id));
    }
 
    // DFS from ROOT
    const traverse = (id: string) => {
      const node = this.nodes.get(id);
      if (node) ordered.push(node);
      for (const child of childrenOf.get(id) || []) {
        traverse(child.id);
      }
    };
    traverse('ROOT');
    
    return ordered;
  }
}

CRDT Advantages:

No coordination needed: Replicas can work independently and merge later
Provably convergent: By construction, all replicas reach the same state
Better for P2P: No central server required for correctness
Natural offline support: Work offline, merge when reconnected

CRDT Disadvantages:

Space overhead: Tombstones and unique IDs consume memory
Complexity in rich data: Text CRDTs are complex; custom data structures are hard
No "undo" primitive: Undo must be modeled as a new operation
Garbage collection: Tombstones must be cleaned up carefully

Yjs: The Modern CRDT Library

Yjs (https://yjs.dev) is a high-performance CRDT library that implements the YATA algorithm for text. It powers Notion, JupyterLab, and many collaborative tools. Yjs handles the complexity of text CRDTs and provides bindings for popular editors like ProseMirror, Quill, and Monaco. If you're building collaborative editing, start with Yjs rather than implementing CRDTs from scratch.

OT vs CRDTs: Choosing Your Approach

Both OT and CRDTs solve the same problem but with different tradeoffs. Here's a detailed comparison:

OT vs CRDT Comparison
Aspect	Operational Transformation	CRDTs
Architecture	Requires central server to serialize ops	Fully decentralized possible
Offline Support	Complex; ops must be ordered later	Natural; merge when reconnected
Memory Overhead	Minimal; store current state + op log	Higher; tombstones, unique IDs
Implementation Complexity	Notoriously error-prone	Hard for custom data types
Mature Libraries	ShareDB, Google Apps	Yjs, Automerge
Text Editing	Google Docs (proven at scale)	Notion, many modern tools
Real-time Latency	Must round-trip through server	Can apply locally immediately
History / Undo	Natural op log enables history	Must model undo as operation
P2P Support	Poor (needs central coordinator)	Excellent (by design)
Conflict Semantics	Transform preserves intent	Last-writer-wins or causality-based

Choose OT When

•You have a reliable central server
•You need strong consistency guarantees
•You're building on existing OT infrastructure (Google Docs API)
•You need detailed operation history and audit logs
•You're working with simple text documents
•Your users are always online while editing

Choose CRDTs When

•Offline-first is a requirement
•You want P2P collaboration (no central server)
•You need local-first architecture
•You're building with modern CRDT libraries (Yjs)
•You want to avoid server as bottleneck
•You need predictable merge behavior

Hybrid Approaches:

Modern systems often combine approaches:

Figma: Uses CRDTs for the canvas (shapes, positions) but OT-like operations for specific features
Notion: Uses Yjs (CRDT) but with a central server for persistence and access control
Linear: CRDTs for rich text, traditional sync for structured data

The choice isn't always binary. You can use CRDTs for document content and traditional sync for metadata, permissions, and file references.

The Industry Trend

The industry has been shifting towards CRDTs, especially with the rise of local-first software. Libraries like Yjs and Automerge have made CRDTs accessible to application developers without deep distributed systems expertise. Google Docs still uses OT because they built it before CRDTs matured, but new collaborative tools often choose CRDTs.

Real-Time Collaboration Architecture Patterns

Beyond the core algorithm (OT or CRDT), collaborativetive systems require supporting infrastructure:

1. Document Session Architecture:

Converting Mermaid diagram...

2. Presence and Awareness:

Beyond document state, collaborative editors need awareness features:

Remote cursors: Where other users are editing
Remote selections: What text others have selected
User indicators: Who is viewing the document
Typing indicators: Who is actively typing

These are typically implemented on a separate, more ephemeral channel:

interface AwarenessState {
  userId: string;
  name: string;
  color: string;
  cursor?: { line: number; column: number };
  selection?: { start: Position; end: Position };
  isTyping: boolean;
  lastActivity: number;
}

3. Persistence Strategies:

Strategy	Description	Tradeoffs
Store Operations	Persist every operation	Complete history, expensive to load from scratch
Periodic Snapshots	Save full state periodically + recent ops	Balance of history and load time
Snapshot + Rollback	Save snapshots, store ops since snapshot	Efficient loading with full history
CRDT State Sync	Persist CRDT state directly	Natural for CRDTs, may lose op history

collaboration_server.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
import { Doc as YDoc, encodeStateAsUpdate, applyUpdate } from 'yjs';
import { WebSocket } from 'ws';
 
interface CollaborationRoom {
  docId: string;
  doc: YDoc;
  clients: Map<string, CollabClient>;
  lastSave: number;
}
 
interface CollabClient {
  socket: WebSocket;
  userId: string;
  awareness: AwarenessState;
}
 
interface AwarenessState {
  userId: string;
  name: string;
  color: string;
  cursor?: { line: number; column: number };
}
 
class CollaborationServer {
  private rooms: Map<string, CollaborationRoom> = new Map();
  private saveInterval = 5000; // Save every 5 seconds if changed
 
  async joinRoom(docId: string, client: CollabClient): Promise<void> {
    let room = this.rooms.get(docId);
    
    if (!room) {
      // Load document from storage or create new
      room = await this.loadOrCreateRoom(docId);
      this.rooms.set(docId, room);
    }
 
    room.clients.set(client.userId, client);
    
    // Send current document state to new client
    const state = encodeStateAsUpdate(room.doc);
    client.socket.send(JSON.stringify({
      type: 'sync',
      update: Array.from(state),
    }));
    
    // Send current awareness states
    const awareness = Array.from(room.clients.values()).map(c => c.awareness);
    client.socket.send(JSON.stringify({
      type: 'awareness',
      states: awareness,
    }));
    
    // Broadcast new user joined
    this.broadcastAwareness(room, client.awareness);
  }
 
  handleUpdate(docId: string, userId: string, update: Uint8Array): void {
    const room = this.rooms.get(docId);
    if (!room) return;
 
    // Apply update to server's copy
    applyUpdate(room.doc, update);
    
    // Broadcast to other clients
    for (const [clientId, client] of room.clients) {
      if (clientId !== userId) {
        client.socket.send(JSON.stringify({
          type: 'update',
          update: Array.from(update),
        }));
      }
    }
    
    // Schedule persistence
    this.scheduleSave(room);
  }
 
  handleAwareness(docId: string, userId: string, awareness: AwarenessState): void {
    const room = this.rooms.get(docId);
    if (!room) return;
 
    const client = room.clients.get(userId);
    if (client) {
      client.awareness = awareness;
      this.broadcastAwareness(room, awareness);
    }
  }
 
  private broadcastAwareness(room: CollaborationRoom, awareness: AwarenessState): void {
    const message = JSON.stringify({
      type: 'awareness',
      states: [awareness],
    });
    
    for (const client of room.clients.values()) {
      if (client.userId !== awareness.userId) {
        client.socket.send(message);
      }
    }
  }
 
  leaveRoom(docId: string, userId: string): void {
    const room = this.rooms.get(docId);
    if (!room) return;
 
    room.clients.delete(userId);
    
    // Broadcast user left
    for (const client of room.clients.values()) {
      client.socket.send(JSON.stringify({
        type: 'user-left',
        userId,
      }));
    }
    
    // Clean up empty rooms after delay
    if (room.clients.size === 0) {
      setTimeout(() => {
        if (room.clients.size === 0) {
          this.saveAndCloseRoom(room);
        }
      }, 30000); // Keep room alive for 30 seconds for quick rejoin
    }
  }
 
  private async loadOrCreateRoom(docId: string): Promise<CollaborationRoom> {
    const doc = new YDoc();
    
    // Try to load from storage
    const savedState = await this.storage.load(docId);
    if (savedState) {
      applyUpdate(doc, savedState);
    }
    
    return {
      docId,
      doc,
      clients: new Map(),
      lastSave: Date.now(),
    };
  }
 
  private scheduleSave(room: CollaborationRoom): void {
    const timeSinceLastSave = Date.now() - room.lastSave;
    
    if (timeSinceLastSave >= this.saveInterval) {
      this.saveRoom(room);
    }
  }
 
  private async saveRoom(room: CollaborationRoom): Promise<void> {
    const state = encodeStateAsUpdate(room.doc);
    await this.storage.save(room.docId, state);
    room.lastSave = Date.now();
  }
 
  private async saveAndCloseRoom(room: CollaborationRoom): Promise<void> {
    await this.saveRoom(room);
    this.rooms.delete(room.docId);
  }
 
  private storage = {
    async load(docId: string): Promise<Uint8Array | null> {
      // Load from PostgreSQL/S3/Redis
      return null;
    },
    async save(docId: string, state: Uint8Array): Promise<void> {
      // Save to PostgreSQL/S3
    },
  };
}

Room-Based Scaling

Collaborative documents naturally partition into 'rooms' (one document = one room). This enables horizontal scaling: route users to specific servers based on document ID. Users editing the same document must be on the same server (or use cross-server sync), but different documents can be on different servers.

Rich Content Collaboration

Text collaboration is the foundation, but modern tools need to handle rich content:

Challenges Beyond Plain Text:

Content Type	Additional Complexity
Rich text (bold, italic, links)	Formatting spans that can overlap, nested styles
Block structures (headings, lists)	Hierarchical document model, block identity
Embedded content (images, tables)	Binary data sync, position in document
Structured data (spreadsheets)	Cell references that must update, formulas
Canvas/graphics	2D positions, z-ordering, shape properties
Comments	Anchored to ranges that may change

Document Model Approaches:

rich_document_model.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
import * as Y from 'yjs';
 
/**
 * Rich document model using Yjs
 * 
 * Key insight: Model document as a tree of blocks,
 * not as flat text with formatting
 */
 
interface Block {
  id: string;
  type: 'paragraph' | 'heading' | 'list' | 'image' | 'table';
  content: Y.XmlFragment | Y.Map<any>;
  children?: Y.Array<Block>;
}
 
class RichDocument {
  private doc: Y.Doc;
  private blocks: Y.Array<any>;
  
  constructor() {
    this.doc = new Y.Doc();
    this.blocks = this.doc.getArray('blocks');
  }
 
  // Insert a new block
  insertBlock(index: number, type: string): Block {
    const block = new Y.Map();
    block.set('id', crypto.randomUUID());
    block.set('type', type);
    
    // Content depends on type
    if (type === 'paragraph' || type === 'heading') {
      // Text block: use XmlFragment for rich text
      const content = new Y.XmlFragment();
      block.set('content', content);
    } else if (type === 'image') {
      // Image block: use Map for properties
      const props = new Y.Map();
      props.set('src', '');
      props.set('alt', '');
      props.set('width', null);
      block.set('content', props);
    } else if (type === 'table') {
      // Table: nested arrays
      const rows = new Y.Array();
      block.set('content', rows);
    }
    
    this.blocks.insert(index, [block]);
    return block;
  }
 
  // Move block (drag and drop)
  moveBlock(fromIndex: number, toIndex: number): void {
    this.doc.transact(() => {
      const block = this.blocks.get(fromIndex);
      this.blocks.delete(fromIndex, 1);
      
      // Adjust target index if moving down
      const adjustedIndex = fromIndex < toIndex ? toIndex - 1 : toIndex;
      this.blocks.insert(adjustedIndex, [block]);
    });
  }
 
  // Delete block
  deleteBlock(index: number): void {
    this.blocks.delete(index, 1);
  }
 
  // Insert text at position in a text block
  insertTextInBlock(blockIndex: number, offset: number, text: string): void {
    const block = this.blocks.get(blockIndex);
    const content = block.get('content') as Y.XmlFragment;
    
    // Yjs handles concurrent text insertion
    content.insert(offset, [new Y.XmlText(text)]);
  }
 
  // Apply formatting to range
  formatRange(
    blockIndex: number, 
    start: number, 
    end: number, 
    format: { bold?: boolean; italic?: boolean; link?: string }
  ): void {
    const block = this.blocks.get(blockIndex);
    const content = block.get('content') as Y.XmlFragment;
    
    // XmlFragment supports attributes on ranges
    // This is simplified - real implementation uses marks/annotations
    this.doc.transact(() => {
      // Format handling depends on the text model
      // ProseMirror, Slate, etc. each have their own approach
    });
  }
 
  // Subscribe to changes
  observe(callback: (event: Y.YArrayEvent<any>) => void): void {
    this.blocks.observe(callback);
  }
 
  // Get state for persistence
  getState(): Uint8Array {
    return Y.encodeStateAsUpdate(this.doc);
  }
 
  // Load state
  loadState(state: Uint8Array): void {
    Y.applyUpdate(this.doc, state);
  }
}
 
/**
 * Comment model - comments anchored to document ranges
 * 
 * Challenge: Range may move as document is edited
 * Solution: Use relative position markers (Yjs provides this)
 */
interface Comment {
  id: string;
  userId: string;
  text: string;
  createdAt: number;
  // Instead of absolute positions, use Yjs relative positions
  anchorStart: Y.RelativePosition;
  anchorEnd: Y.RelativePosition;
  resolved: boolean;
}
 
class CommentManager {
  private comments: Y.Map<any>;
  private doc: Y.Doc;
 
  constructor(doc: Y.Doc) {
    this.doc = doc;
    this.comments = doc.getMap('comments');
  }
 
  addComment(
    text: string, 
    userId: string,
    range: { blockIndex: number; start: number; end: number }
  ): string {
    const block = this.doc.getArray('blocks').get(range.blockIndex);
    const content = block.get('content') as Y.XmlFragment;
    
    // Create relative positions (these update as document changes)
    const anchorStart = Y.createRelativePositionFromTypeIndex(content, range.start);
    const anchorEnd = Y.createRelativePositionFromTypeIndex(content, range.end);
    
    const comment: Comment = {
      id: crypto.randomUUID(),
      userId,
      text,
      createdAt: Date.now(),
      anchorStart,
      anchorEnd,
      resolved: false,
    };
    
    this.comments.set(comment.id, comment);
    return comment.id;
  }
 
  getCommentRange(commentId: string): { start: number; end: number } | null {
    const comment = this.comments.get(commentId);
    if (!comment) return null;
    
    // Convert relative positions back to absolute
    const startAbs = Y.createAbsolutePositionFromRelativePosition(
      comment.anchorStart, 
      this.doc
    );
    const endAbs = Y.createAbsolutePositionFromRelativePosition(
      comment.anchorEnd, 
      this.doc
    );
    
    if (!startAbs || !endAbs) return null;
    
    return { start: startAbs.index, end: endAbs.index };
  }
}

Block-Based Editing

Modern editors like Notion, Coda, and Roam use block-based models where documents are trees of blocks rather than flat text. This aligns well with CRDTs: each block has a unique ID, and operations reference blocks by ID rather than position. Block moves, deletions, and insertions become straightforward CRDT operations.

Industry Case Studies

Let's examine how major collaborative tools approach real-time editing:

Google Docs (OT Pioneer):

Custom OT implementation refined over 15+ years
Central server serializes all operations
Operations persisted for complete undo history
Revision history allows viewing any point in document history
Complex handling for tables, images, and formatting

Figma (Canvas CRDT):

Custom CRDT implementation for 2D canvas
Each object has unique ID with operations referencing IDs
Optimistic local application with server reconciliation
Real-time multiplayer cursors with <30ms latency target
Handles millions of objects in complex designs

Notion (Yjs-Based):

Block-based document model
Uses Yjs for core CRDT functionality
Blocks have types (paragraph, heading, list, table, etc.)
Databases are collaborative structured data
Offline support with sync on reconnection

Linear (Hybrid):

Rich text fields use CRDTs
Structured data (issues, projects) uses traditional sync
Real-time updates via WebSocket
Optimistic UI with conflict resolution
Offline mode with eventual sync

Collaborative Editing Architectures
Product	Algorithm	Architecture	Notable Features
Google Docs	OT	Server-centric	Revision history, 15+ years battle-tested
Figma	Custom CRDT	Server-backed P2P	Canvas editing, multiplayer cursors
Notion	Yjs (CRDT)	Server-synced	Block-based, databases
VS Code Live Share	Custom sync	Relay server	Code editing, terminals, debugging
Excalidraw	Custom CRDT	P2P capable	Canvas drawing, open source
Roam Research	Custom CRDT	Server-synced	Graph-based notes, bidirectional links
Coda	OT-like	Server-centric	Docs + spreadsheets + apps

Open Source Starting Points

For learning or building: Yjs (docs: crdt.tech) is production-ready with excellent documentation. Automerge offers a more data-structure-oriented API. ShareDB provides OT for those who prefer that model. tldraw is an open-source collaborative whiteboard you can study. Start with these rather than building from scratch.

Summary: Real-Time Collaboration

Real-time collaboration transforms how people work together, but it requires sophisticated algorithms and careful architectural decisions.

Key Takeaways

•Concurrent editing is fundamentally hard: Multiple users, unreliable networks, and the need for convergence create complex challenges.
•OT transforms operations for compatibility: Proven approach used by Google Docs, but complex to implement correctly.
•CRDTs ensure convergence by design: Data structures that merge without conflicts, enabling offline-first and P2P.
•Choose based on requirements: OT for server-centric with history; CRDTs for offline-first and decentralized.
•Awareness is essential UX: Cursors, selections, and presence make collaboration feel real and prevent conflicts.
•Rich content adds complexity: Block-based models, relative positions, and careful schema design are necessary.
•Use existing libraries: Yjs, Automerge, and ShareDB are battle-tested; building from scratch is error-prone.
•Industry is converging on CRDTs: Modern tools increasingly choose CRDTs for their flexibility and offline support.

Page Complete

You now understand the algorithms and architectures behind real-time collaboration. Next, we'll explore Gaming Applications—how to handle the extreme latency, consistency, and performance requirements of real-time multiplayer games, from casual mobile games to competitive esports.

3 / 5

Loading learning content...

System Design (HLD)Real-Time Architecture Patterns

Real-Time Architecture Patterns

LevelAdvanced

Duration90 mins

TopicReal-Time Architecture Patterns

3 / 5

Real-Time Collaboration

When Everyone Edits at Once

This isn't just about text editors. Real-time collaboration powers:

Document editing: Google Docs, Notion, Coda, Dropbox Paper
Design tools: Figma, Miro, FigJam, Canva
Code editors: VS Code Live Share, Replit, CodeSandbox
Spreadsheets: Google Sheets, Airtable, Coda
Whiteboards: Miro, Excalidraw, tldraw
Project management: Linear, Asana, Monday.com

This page dives deep into the algorithms, data structures, and architectural patterns that make real-time collaboration possible.

What You Will Learn

The Concurrency Problem

To understand why real-time collaboration is hard, consider a simple scenario:

Initial state: "Hello"

Alice inserts " World" at position 5 → "Hello World"
Bob inserts "!" at position 5 → "Hello!"

If both operations happen simultaneously and are applied naively:

If Alice's operation applies first, then Bob's "!" goes to position 5: "Hello! World"
If Bob's operation applies first, then Alice's " World" goes to position 5: "Hello World!"

Different outcomes depending on order! This is the convergence problem: how do we ensure all participants eventually see the same result?

Key challenges:

Real-Time Collaboration Challenges
Challenge	Description	Why It's Hard
Convergence	All replicas must reach the same final state	Network delays mean operations arrive in different orders
Intention Preservation	User's intended effect should be maintained	Position-based operations become invalid as document changes
Causality	Operations should respect happens-before relationships	Clock synchronization across distributed clients is imperfect
Performance	Sub-100ms latency for responsive editing	Coordination adds latency; going through server is slow
Offline Support	Users should be able to work disconnected	Merging divergent offline changes is complex
Undo/Redo	Users expect their undo to undo their action	In collaborative editing, what exactly should undo do?

Converting Mermaid diagram...

Naive Solutions That Don't Work:

Locking: Lock the document while someone edits. Destroys real-time experience.
Last-Write-Wins: Later operation overwrites earlier. Loses data, intention lost.
Manual Conflict Resolution: Show conflicts to users. Terrible UX for frequent operations.
Turn-Taking: Only one person can type at a time. Not really "collaboration."

We need algorithms that automatically merge concurrent operations while preserving user intent.

The CAP Theorem Implication

Operational Transformation (OT)

Operational Transformation (OT) is the classic solution, invented in 1989 and used by Google Docs, Google Sheets, and Microsoft Office Online.

Core Idea: When concurrent operations conflict, transform one operation so it can be applied after the other while preserving both users' intentions.

The Transform Function:

Given two concurrent operations a and b (neither happened-before the other), we need a transform function T such that:

apply(apply(state, a), T(b, a)) = apply(apply(state, b), T(a, b))

In other words: applying a then transformed-b should equal applying b then transformed-a.

Converting Mermaid diagram...

Text OT Transform Examples:

Scenario	Operation A	Operation B	T(B, A)	Explanation
Insert before insert	Insert "X" @3	Insert "Y" @5	Insert "Y" @6	A shifted B's position by 1
Insert after insert	Insert "X" @5	Insert "Y" @3	Insert "Y" @3	A didn't affect B's position
Insert vs delete	Insert "X" @3	Delete @5-6	Delete @6-7	Insertion shifted the delete range
Overlapping deletes	Delete @3-5	Delete @4-6	Delete @3-4	Merge overlapping deletes

The Transform Function for Text:

ot_transform.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
// Operational Transformation for text operations
 
type Operation = InsertOp | DeleteOp | RetainOp;
 
interface InsertOp {
  type: 'insert';
  position: number;
  text: string;
}
 
interface DeleteOp {
  type: 'delete';
  position: number;
  length: number;
}
 
interface RetainOp {
  type: 'retain';
  count: number;
}
 
/**
 * Transform operation B against operation A.
 * Returns a new operation B' that can be applied after A
 * and achieves the same result as if A and B had been applied
 * in the opposite order with A transformed.
 */
function transform(opB: Operation, opA: Operation): Operation {
  // Insert vs Insert
  if (opA.type === 'insert' && opB.type === 'insert') {
    if (opB.position <= opA.position) {
      // B is before or at A's position - no change needed
      return opB;
    } else {
      // B is after A's position - shift by A's length
      return {
        ...opB,
        position: opB.position + opA.text.length,
      };
    }
  }
 
  // Insert vs Delete
  if (opA.type === 'insert' && opB.type === 'delete') {
    if (opB.position >= opA.position) {
      // Delete is after insert - shift position
      return {
        ...opB,
        position: opB.position + opA.text.length,
      };
    } else if (opB.position + opB.length <= opA.position) {
      // Delete is entirely before insert - no change
      return opB;
    } else {
      // Delete spans the insert position - split the delete
      // This is where it gets complex...
      return {
        ...opB,
        position: opB.position,
        length: opB.length + opA.text.length,
      };
    }
  }
 
  // Delete vs Insert
  if (opA.type === 'delete' && opB.type === 'insert') {
    if (opB.position <= opA.position) {
      // Insert is before delete - no change
      return opB;
    } else if (opB.position >= opA.position + opA.length) {
      // Insert is after delete - shift back
      return {
        ...opB,
        position: opB.position - opA.length,
      };
    } else {
      // Insert is within deleted region - move to delete start
      return {
        ...opB,
        position: opA.position,
      };
    }
  }
 
  // Delete vs Delete
  if (opA.type === 'delete' && opB.type === 'delete') {
    // Handle overlapping deletes
    const aStart = opA.position;
    const aEnd = opA.position + opA.length;
    const bStart = opB.position;
    const bEnd = opB.position + opB.length;
 
    if (bEnd <= aStart) {
      // B entirely before A - no change
      return opB;
    } else if (bStart >= aEnd) {
      // B entirely after A - shift back
      return {
        ...opB,
        position: opB.position - opA.length,
      };
    } else {
      // Overlapping deletes - compute remaining delete
      const newStart = Math.min(bStart, aStart);
      const overlapStart = Math.max(bStart, aStart);
      const overlapEnd = Math.min(bEnd, aEnd);
      const overlapLength = overlapEnd - overlapStart;
      
      return {
        type: 'delete',
        position: bStart < aStart ? bStart : aStart,
        length: opB.length - overlapLength,
      };
    }
  }
 
  return opB; // Default: no transformation needed
}
 
/**
 * Compose two operations into a single operation
 * that has the same effect as applying both sequentially.
 */
function compose(opA: Operation, opB: Operation): Operation[] {
  // Returns a list because some compositions result in multiple operations
  // This is simplified - real implementations handle complex compositions
  return [opA, opB];
}

OT Architecture (Server-Centric):

Google Docs uses a central server to serialize operations:

Client applies operation locally (optimistic update)
Client sends operation to server with version number
Server transforms incoming operation against any concurrent operations
Server applies operation, increments version, broadcasts to other clients
Other clients transform their pending operations and apply

This approach ensures:

A single authoritative timeline of operations
All clients eventually converge
Server can persist operation log for history/undo

OT Complexity:

OT is notoriously difficult to implement correctly. The transform function must satisfy two properties:

TP1 (Transformation Property 1): apply(apply(s, a), T(b, a)) = apply(apply(s, b), T(a, b))
TP2 (Transformation Property 2): T(T(c, a), T(b, a)) = T(T(c, b), T(a, b))

TP2 is especially tricky and many published OT algorithms had bugs. Google spent years perfecting their implementation.

OT Is Hard to Get Right

Conflict-free Replicated Data Types (CRDTs)

CRDTs take a fundamentally different approach: instead of transforming operations, they design data structures that can be merged without conflicts by construction.

Core Insight: If operations are commutative (order doesn't matter) and idempotent (applying twice has same effect), then concurrent operations merge trivially.

Two Flavors of CRDTs:

State-based CRDTs (CvRDTs): Merge complete states using a merge function
Operation-based CRDTs (CmRDTs): Merge operations directly

Simple CRDT Examples:

Common CRDT Types
CRDT	Description	Merge Operation	Use Case
G-Counter	Grow-only counter	Max of each replica's count	View counts, likes
PN-Counter	Counter with increment/decrement	Separate G-Counters for pos/neg	Inventory, karma
G-Set	Grow-only set	Set union	Seen messages, tags
2P-Set	Set with add and remove	Separate add/remove sets	Simple collections
LWW-Register	Last-writer-wins register	Take value with highest timestamp	Simple properties
OR-Set	Observed-remove set	Track unique add operations	Collaborative lists
RGA	Replicated growable array	Unique IDs between elements	Text editing
YATA	Yet Another Transformation Approach	Optimized for text operations	Real-time text (Yjs)

crdt_examples.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
// CRDT Examples: G-Counter and G-Set
 
/**
 * G-Counter: Grow-only counter
 * Each replica maintains its own count; merge takes max of each.
 */
class GCounter {
  // Map of replica ID to that replica's count
  private counts: Map<string, number> = new Map();
  private replicaId: string;
 
  constructor(replicaId: string) {
    this.replicaId = replicaId;
    this.counts.set(replicaId, 0);
  }
 
  increment(): void {
    const current = this.counts.get(this.replicaId) || 0;
    this.counts.set(this.replicaId, current + 1);
  }
 
  value(): number {
    let sum = 0;
    for (const count of this.counts.values()) {
      sum += count;
    }
    return sum;
  }
 
  // Merge with another G-Counter (commutative, associative, idempotent)
  merge(other: GCounter): void {
    for (const [replicaId, count] of other.counts) {
      const current = this.counts.get(replicaId) || 0;
      this.counts.set(replicaId, Math.max(current, count));
    }
  }
 
  // Serialize for transmission
  toJSON(): Record<string, number> {
    return Object.fromEntries(this.counts);
  }
 
  static fromJSON(replicaId: string, data: Record<string, number>): GCounter {
    const counter = new GCounter(replicaId);
    counter.counts = new Map(Object.entries(data));
    return counter;
  }
}
 
/**
 * LWW-Element-Set: Last-Writer-Wins Set
 * Each element has an add timestamp and optional remove timestamp.
 * Element is in set if add timestamp > remove timestamp.
 */
class LWWSet<T> {
  private addSet: Map<T, number> = new Map();  // element -> add timestamp
  private removeSet: Map<T, number> = new Map();  // element -> remove timestamp
 
  add(element: T, timestamp: number = Date.now()): void {
    const currentAdd = this.addSet.get(element) || 0;
    this.addSet.set(element, Math.max(currentAdd, timestamp));
  }
 
  remove(element: T, timestamp: number = Date.now()): void {
    const currentRemove = this.removeSet.get(element) || 0;
    this.removeSet.set(element, Math.max(currentRemove, timestamp));
  }
 
  has(element: T): boolean {
    const addTime = this.addSet.get(element);
    if (addTime === undefined) return false;
    
    const removeTime = this.removeSet.get(element) || 0;
    return addTime > removeTime;  // Bias towards adds (add wins on tie)
  }
 
  values(): T[] {
    const result: T[] = [];
    for (const element of this.addSet.keys()) {
      if (this.has(element)) {
        result.push(element);
      }
    }
    return result;
  }
 
  merge(other: LWWSet<T>): void {
    // Merge add sets (take max timestamp for each element)
    for (const [element, timestamp] of other.addSet) {
      const current = this.addSet.get(element) || 0;
      this.addSet.set(element, Math.max(current, timestamp));
    }
    
    // Merge remove sets (take max timestamp for each element)
    for (const [element, timestamp] of other.removeSet) {
      const current = this.removeSet.get(element) || 0;
      this.removeSet.set(element, Math.max(current, timestamp));
    }
  }
}
 
/**
 * RGA (Replicated Growable Array) - simplified version for text
 * 
 * Key insight: Instead of positions, use unique IDs for each character.
 * Insert "between" two IDs, not at a position.
 * This makes inserts commutative.
 */
interface RGANode {
  id: string;           // Unique ID: "replicaId:sequenceNumber"
  char: string;         // The character (or tombstone marker)
  deleted: boolean;     // Tombstone for deleted characters
  afterId: string | null; // ID of the node this comes after
}
 
class RGAText {
  private nodes: Map<string, RGANode> = new Map();
  private replicaId: string;
  private sequenceNumber: number = 0;
 
  constructor(replicaId: string) {
    this.replicaId = replicaId;
    // Create sentinel node at start
    const sentinel: RGANode = {
      id: 'ROOT',
      char: '',
      deleted: false,
      afterId: null,
    };
    this.nodes.set('ROOT', sentinel);
  }
 
  generateId(): string {
    return `${this.replicaId}:${++this.sequenceNumber}`;
  }
 
  // Insert character after the node with the given ID
  insert(afterId: string, char: string): RGANode {
    const id = this.generateId();
    const node: RGANode = {
      id,
      char,
      deleted: false,
      afterId,
    };
    this.nodes.set(id, node);
    return node;
  }
 
  delete(id: string): void {
    const node = this.nodes.get(id);
    if (node) {
      node.deleted = true;  // Tombstone, don't actually remove
    }
  }
 
  // Merge incoming node (idempotent, commutative)
  mergeNode(node: RGANode): void {
    if (this.nodes.has(node.id)) {
      // Already have this node - merge tombstone status
      const existing = this.nodes.get(node.id)!;
      existing.deleted = existing.deleted || node.deleted;
    } else {
      this.nodes.set(node.id, { ...node });
    }
  }
 
  // Convert to string (traverse linked structure)
  toString(): string {
    const ordered = this.getOrderedNodes();
    return ordered
      .filter(n => !n.deleted && n.id !== 'ROOT')
      .map(n => n.char)
      .join('');
  }
 
  private getOrderedNodes(): RGANode[] {
    // Build ordered list by following afterId links
    // This is O(n²) for simplicity; real implementations optimize this
    const ordered: RGANode[] = [];
    const childrenOf = new Map<string, RGANode[]>();
    
    for (const node of this.nodes.values()) {
      const afterId = node.afterId || 'ROOT';
      if (!childrenOf.has(afterId)) {
        childrenOf.set(afterId, []);
      }
      childrenOf.get(afterId)!.push(node);
    }
 
    // Sort children by ID for deterministic ordering
    for (const children of childrenOf.values()) {
      children.sort((a, b) => a.id.localeCompare(b.id));
    }
 
    // DFS from ROOT
    const traverse = (id: string) => {
      const node = this.nodes.get(id);
      if (node) ordered.push(node);
      for (const child of childrenOf.get(id) || []) {
        traverse(child.id);
      }
    };
    traverse('ROOT');
    
    return ordered;
  }
}

CRDT Advantages:

No coordination needed: Replicas can work independently and merge later
Provably convergent: By construction, all replicas reach the same state
Better for P2P: No central server required for correctness
Natural offline support: Work offline, merge when reconnected

CRDT Disadvantages:

Space overhead: Tombstones and unique IDs consume memory
Complexity in rich data: Text CRDTs are complex; custom data structures are hard
No "undo" primitive: Undo must be modeled as a new operation
Garbage collection: Tombstones must be cleaned up carefully

Yjs: The Modern CRDT Library

OT vs CRDTs: Choosing Your Approach

Both OT and CRDTs solve the same problem but with different tradeoffs. Here's a detailed comparison:

OT vs CRDT Comparison
Aspect	Operational Transformation	CRDTs
Architecture	Requires central server to serialize ops	Fully decentralized possible
Offline Support	Complex; ops must be ordered later	Natural; merge when reconnected
Memory Overhead	Minimal; store current state + op log	Higher; tombstones, unique IDs
Implementation Complexity	Notoriously error-prone	Hard for custom data types
Mature Libraries	ShareDB, Google Apps	Yjs, Automerge
Text Editing	Google Docs (proven at scale)	Notion, many modern tools
Real-time Latency	Must round-trip through server	Can apply locally immediately
History / Undo	Natural op log enables history	Must model undo as operation
P2P Support	Poor (needs central coordinator)	Excellent (by design)
Conflict Semantics	Transform preserves intent	Last-writer-wins or causality-based

Choose OT When

•You have a reliable central server
•You need strong consistency guarantees
•You're building on existing OT infrastructure (Google Docs API)
•You need detailed operation history and audit logs
•You're working with simple text documents
•Your users are always online while editing

Choose CRDTs When

•Offline-first is a requirement
•You want P2P collaboration (no central server)
•You need local-first architecture
•You're building with modern CRDT libraries (Yjs)
•You want to avoid server as bottleneck
•You need predictable merge behavior

Hybrid Approaches:

Modern systems often combine approaches:

Figma: Uses CRDTs for the canvas (shapes, positions) but OT-like operations for specific features
Notion: Uses Yjs (CRDT) but with a central server for persistence and access control
Linear: CRDTs for rich text, traditional sync for structured data

The choice isn't always binary. You can use CRDTs for document content and traditional sync for metadata, permissions, and file references.

The Industry Trend

Real-Time Collaboration Architecture Patterns

Beyond the core algorithm (OT or CRDT), collaborativetive systems require supporting infrastructure:

1. Document Session Architecture:

Converting Mermaid diagram...

2. Presence and Awareness:

Beyond document state, collaborative editors need awareness features:

Remote cursors: Where other users are editing
Remote selections: What text others have selected
User indicators: Who is viewing the document
Typing indicators: Who is actively typing

These are typically implemented on a separate, more ephemeral channel:

interface AwarenessState {
  userId: string;
  name: string;
  color: string;
  cursor?: { line: number; column: number };
  selection?: { start: Position; end: Position };
  isTyping: boolean;
  lastActivity: number;
}

3. Persistence Strategies:

Strategy	Description	Tradeoffs
Store Operations	Persist every operation	Complete history, expensive to load from scratch
Periodic Snapshots	Save full state periodically + recent ops	Balance of history and load time
Snapshot + Rollback	Save snapshots, store ops since snapshot	Efficient loading with full history
CRDT State Sync	Persist CRDT state directly	Natural for CRDTs, may lose op history

collaboration_server.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
import { Doc as YDoc, encodeStateAsUpdate, applyUpdate } from 'yjs';
import { WebSocket } from 'ws';
 
interface CollaborationRoom {
  docId: string;
  doc: YDoc;
  clients: Map<string, CollabClient>;
  lastSave: number;
}
 
interface CollabClient {
  socket: WebSocket;
  userId: string;
  awareness: AwarenessState;
}
 
interface AwarenessState {
  userId: string;
  name: string;
  color: string;
  cursor?: { line: number; column: number };
}
 
class CollaborationServer {
  private rooms: Map<string, CollaborationRoom> = new Map();
  private saveInterval = 5000; // Save every 5 seconds if changed
 
  async joinRoom(docId: string, client: CollabClient): Promise<void> {
    let room = this.rooms.get(docId);
    
    if (!room) {
      // Load document from storage or create new
      room = await this.loadOrCreateRoom(docId);
      this.rooms.set(docId, room);
    }
 
    room.clients.set(client.userId, client);
    
    // Send current document state to new client
    const state = encodeStateAsUpdate(room.doc);
    client.socket.send(JSON.stringify({
      type: 'sync',
      update: Array.from(state),
    }));
    
    // Send current awareness states
    const awareness = Array.from(room.clients.values()).map(c => c.awareness);
    client.socket.send(JSON.stringify({
      type: 'awareness',
      states: awareness,
    }));
    
    // Broadcast new user joined
    this.broadcastAwareness(room, client.awareness);
  }
 
  handleUpdate(docId: string, userId: string, update: Uint8Array): void {
    const room = this.rooms.get(docId);
    if (!room) return;
 
    // Apply update to server's copy
    applyUpdate(room.doc, update);
    
    // Broadcast to other clients
    for (const [clientId, client] of room.clients) {
      if (clientId !== userId) {
        client.socket.send(JSON.stringify({
          type: 'update',
          update: Array.from(update),
        }));
      }
    }
    
    // Schedule persistence
    this.scheduleSave(room);
  }
 
  handleAwareness(docId: string, userId: string, awareness: AwarenessState): void {
    const room = this.rooms.get(docId);
    if (!room) return;
 
    const client = room.clients.get(userId);
    if (client) {
      client.awareness = awareness;
      this.broadcastAwareness(room, awareness);
    }
  }
 
  private broadcastAwareness(room: CollaborationRoom, awareness: AwarenessState): void {
    const message = JSON.stringify({
      type: 'awareness',
      states: [awareness],
    });
    
    for (const client of room.clients.values()) {
      if (client.userId !== awareness.userId) {
        client.socket.send(message);
      }
    }
  }
 
  leaveRoom(docId: string, userId: string): void {
    const room = this.rooms.get(docId);
    if (!room) return;
 
    room.clients.delete(userId);
    
    // Broadcast user left
    for (const client of room.clients.values()) {
      client.socket.send(JSON.stringify({
        type: 'user-left',
        userId,
      }));
    }
    
    // Clean up empty rooms after delay
    if (room.clients.size === 0) {
      setTimeout(() => {
        if (room.clients.size === 0) {
          this.saveAndCloseRoom(room);
        }
      }, 30000); // Keep room alive for 30 seconds for quick rejoin
    }
  }
 
  private async loadOrCreateRoom(docId: string): Promise<CollaborationRoom> {
    const doc = new YDoc();
    
    // Try to load from storage
    const savedState = await this.storage.load(docId);
    if (savedState) {
      applyUpdate(doc, savedState);
    }
    
    return {
      docId,
      doc,
      clients: new Map(),
      lastSave: Date.now(),
    };
  }
 
  private scheduleSave(room: CollaborationRoom): void {
    const timeSinceLastSave = Date.now() - room.lastSave;
    
    if (timeSinceLastSave >= this.saveInterval) {
      this.saveRoom(room);
    }
  }
 
  private async saveRoom(room: CollaborationRoom): Promise<void> {
    const state = encodeStateAsUpdate(room.doc);
    await this.storage.save(room.docId, state);
    room.lastSave = Date.now();
  }
 
  private async saveAndCloseRoom(room: CollaborationRoom): Promise<void> {
    await this.saveRoom(room);
    this.rooms.delete(room.docId);
  }
 
  private storage = {
    async load(docId: string): Promise<Uint8Array | null> {
      // Load from PostgreSQL/S3/Redis
      return null;
    },
    async save(docId: string, state: Uint8Array): Promise<void> {
      // Save to PostgreSQL/S3
    },
  };
}

Room-Based Scaling

Rich Content Collaboration

Text collaboration is the foundation, but modern tools need to handle rich content:

Challenges Beyond Plain Text:

Content Type	Additional Complexity
Rich text (bold, italic, links)	Formatting spans that can overlap, nested styles
Block structures (headings, lists)	Hierarchical document model, block identity
Embedded content (images, tables)	Binary data sync, position in document
Structured data (spreadsheets)	Cell references that must update, formulas
Canvas/graphics	2D positions, z-ordering, shape properties
Comments	Anchored to ranges that may change

Document Model Approaches:

rich_document_model.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
import * as Y from 'yjs';
 
/**
 * Rich document model using Yjs
 * 
 * Key insight: Model document as a tree of blocks,
 * not as flat text with formatting
 */
 
interface Block {
  id: string;
  type: 'paragraph' | 'heading' | 'list' | 'image' | 'table';
  content: Y.XmlFragment | Y.Map<any>;
  children?: Y.Array<Block>;
}
 
class RichDocument {
  private doc: Y.Doc;
  private blocks: Y.Array<any>;
  
  constructor() {
    this.doc = new Y.Doc();
    this.blocks = this.doc.getArray('blocks');
  }
 
  // Insert a new block
  insertBlock(index: number, type: string): Block {
    const block = new Y.Map();
    block.set('id', crypto.randomUUID());
    block.set('type', type);
    
    // Content depends on type
    if (type === 'paragraph' || type === 'heading') {
      // Text block: use XmlFragment for rich text
      const content = new Y.XmlFragment();
      block.set('content', content);
    } else if (type === 'image') {
      // Image block: use Map for properties
      const props = new Y.Map();
      props.set('src', '');
      props.set('alt', '');
      props.set('width', null);
      block.set('content', props);
    } else if (type === 'table') {
      // Table: nested arrays
      const rows = new Y.Array();
      block.set('content', rows);
    }
    
    this.blocks.insert(index, [block]);
    return block;
  }
 
  // Move block (drag and drop)
  moveBlock(fromIndex: number, toIndex: number): void {
    this.doc.transact(() => {
      const block = this.blocks.get(fromIndex);
      this.blocks.delete(fromIndex, 1);
      
      // Adjust target index if moving down
      const adjustedIndex = fromIndex < toIndex ? toIndex - 1 : toIndex;
      this.blocks.insert(adjustedIndex, [block]);
    });
  }
 
  // Delete block
  deleteBlock(index: number): void {
    this.blocks.delete(index, 1);
  }
 
  // Insert text at position in a text block
  insertTextInBlock(blockIndex: number, offset: number, text: string): void {
    const block = this.blocks.get(blockIndex);
    const content = block.get('content') as Y.XmlFragment;
    
    // Yjs handles concurrent text insertion
    content.insert(offset, [new Y.XmlText(text)]);
  }
 
  // Apply formatting to range
  formatRange(
    blockIndex: number, 
    start: number, 
    end: number, 
    format: { bold?: boolean; italic?: boolean; link?: string }
  ): void {
    const block = this.blocks.get(blockIndex);
    const content = block.get('content') as Y.XmlFragment;
    
    // XmlFragment supports attributes on ranges
    // This is simplified - real implementation uses marks/annotations
    this.doc.transact(() => {
      // Format handling depends on the text model
      // ProseMirror, Slate, etc. each have their own approach
    });
  }
 
  // Subscribe to changes
  observe(callback: (event: Y.YArrayEvent<any>) => void): void {
    this.blocks.observe(callback);
  }
 
  // Get state for persistence
  getState(): Uint8Array {
    return Y.encodeStateAsUpdate(this.doc);
  }
 
  // Load state
  loadState(state: Uint8Array): void {
    Y.applyUpdate(this.doc, state);
  }
}
 
/**
 * Comment model - comments anchored to document ranges
 * 
 * Challenge: Range may move as document is edited
 * Solution: Use relative position markers (Yjs provides this)
 */
interface Comment {
  id: string;
  userId: string;
  text: string;
  createdAt: number;
  // Instead of absolute positions, use Yjs relative positions
  anchorStart: Y.RelativePosition;
  anchorEnd: Y.RelativePosition;
  resolved: boolean;
}
 
class CommentManager {
  private comments: Y.Map<any>;
  private doc: Y.Doc;
 
  constructor(doc: Y.Doc) {
    this.doc = doc;
    this.comments = doc.getMap('comments');
  }
 
  addComment(
    text: string, 
    userId: string,
    range: { blockIndex: number; start: number; end: number }
  ): string {
    const block = this.doc.getArray('blocks').get(range.blockIndex);
    const content = block.get('content') as Y.XmlFragment;
    
    // Create relative positions (these update as document changes)
    const anchorStart = Y.createRelativePositionFromTypeIndex(content, range.start);
    const anchorEnd = Y.createRelativePositionFromTypeIndex(content, range.end);
    
    const comment: Comment = {
      id: crypto.randomUUID(),
      userId,
      text,
      createdAt: Date.now(),
      anchorStart,
      anchorEnd,
      resolved: false,
    };
    
    this.comments.set(comment.id, comment);
    return comment.id;
  }
 
  getCommentRange(commentId: string): { start: number; end: number } | null {
    const comment = this.comments.get(commentId);
    if (!comment) return null;
    
    // Convert relative positions back to absolute
    const startAbs = Y.createAbsolutePositionFromRelativePosition(
      comment.anchorStart, 
      this.doc
    );
    const endAbs = Y.createAbsolutePositionFromRelativePosition(
      comment.anchorEnd, 
      this.doc
    );
    
    if (!startAbs || !endAbs) return null;
    
    return { start: startAbs.index, end: endAbs.index };
  }
}

Block-Based Editing

Industry Case Studies

Let's examine how major collaborative tools approach real-time editing:

Google Docs (OT Pioneer):

Custom OT implementation refined over 15+ years
Central server serializes all operations
Operations persisted for complete undo history
Revision history allows viewing any point in document history
Complex handling for tables, images, and formatting

Figma (Canvas CRDT):

Custom CRDT implementation for 2D canvas
Each object has unique ID with operations referencing IDs
Optimistic local application with server reconciliation
Real-time multiplayer cursors with <30ms latency target
Handles millions of objects in complex designs

Notion (Yjs-Based):

Block-based document model
Uses Yjs for core CRDT functionality
Blocks have types (paragraph, heading, list, table, etc.)
Databases are collaborative structured data
Offline support with sync on reconnection

Linear (Hybrid):

Rich text fields use CRDTs
Structured data (issues, projects) uses traditional sync
Real-time updates via WebSocket
Optimistic UI with conflict resolution
Offline mode with eventual sync

Collaborative Editing Architectures
Product	Algorithm	Architecture	Notable Features
Google Docs	OT	Server-centric	Revision history, 15+ years battle-tested
Figma	Custom CRDT	Server-backed P2P	Canvas editing, multiplayer cursors
Notion	Yjs (CRDT)	Server-synced	Block-based, databases
VS Code Live Share	Custom sync	Relay server	Code editing, terminals, debugging
Excalidraw	Custom CRDT	P2P capable	Canvas drawing, open source
Roam Research	Custom CRDT	Server-synced	Graph-based notes, bidirectional links
Coda	OT-like	Server-centric	Docs + spreadsheets + apps

Open Source Starting Points

Summary: Real-Time Collaboration

Real-time collaboration transforms how people work together, but it requires sophisticated algorithms and careful architectural decisions.

Key Takeaways

•Concurrent editing is fundamentally hard: Multiple users, unreliable networks, and the need for convergence create complex challenges.
•OT transforms operations for compatibility: Proven approach used by Google Docs, but complex to implement correctly.
•CRDTs ensure convergence by design: Data structures that merge without conflicts, enabling offline-first and P2P.
•Choose based on requirements: OT for server-centric with history; CRDTs for offline-first and decentralized.
•Awareness is essential UX: Cursors, selections, and presence make collaboration feel real and prevent conflicts.
•Rich content adds complexity: Block-based models, relative positions, and careful schema design are necessary.
•Use existing libraries: Yjs, Automerge, and ShareDB are battle-tested; building from scratch is error-prone.
•Industry is converging on CRDTs: Modern tools increasingly choose CRDTs for their flexibility and offline support.

Page Complete

3 / 5