Requirements

Functional Requirements

• Multiple users can edit the same document simultaneously
• Changes appear in real-time (within 100ms)
• Cursor position visible for all collaborators
• Edit history with ability to undo/redo
• Comments and suggestions
• Offline editing with sync on reconnect
• Document sharing with permissions

Non-Functional Requirements

• Latency: Changes visible in < 100ms
• Consistency: All users see the same document state
• Scale: 100 concurrent editors per document
• Durability: Never lose edits
• Availability: 99.99%

Back-of-the-Envelope Estimation

Operational Transformation

OT Properties

Insert Operation Transformation

Delete Operation Transformation

High-Level Architecture

Detailed Design

Operation Model

Operation = {
  type: "insert" | "delete" | "retain",
  position: int,
  character: char (for insert),
  version: int,       // Base version this op was created from
  client_id: string,  // Who created this op
  timestamp: long
}

Server-side OT Flow

1. Client sends operation with base version V
2. Server receives operation
3. Server transforms operation against all operations after version V
4. Server applies transformed operation to document
5. Server increments version to V+1
6. Server broadcasts transformed operation to all other clients
7. Server persists operation to operation log

Client-side OT Flow

1. User makes local edit → create operation with current local version
2. Apply operation locally immediately (optimistic update)
3. Send operation to server
4. Receive transformed operation from server
5. Adjust local state based on server's transformed operation

Version Vector

Version Vector: {
  client_a: 15,  // Client A has applied 15 ops
  client_b: 12,  // Client B has applied 12 ops
  client_c: 18   // Client C has applied 18 ops
}

Persistence Strategy

Scaling OT Servers

Practice Exercises

1. Algorithm: Implement the OT transform function for insert-insert and delete-insert cases. Prove that TP1 and TP2 hold for your implementation.

2. Scale: If a document has 100 concurrent editors, each making 10 operations/second, the server processes 1000 ops/sec for one document. Estimate the server resources needed.

3. Offline: Design a system for offline editing that syncs changes when the user reconnects. How do you handle conflicts with the online version?

4. Comparison: Compare OT and CRDTs for collaborative editing. What are the trade-offs in terms of complexity, server requirements, and undo/redo support?

What to Learn Next