Design Collaborative Document Editing (Google Docs)

1
interface DocumentState {
2
  documentId: string
3
  revision: number // Monotonic operation counter
4
  content: DocumentContent // Current document state
5
  pendingOps: Map<ClientId, Operation[]> // Ops awaiting transform
6
  clients: Map<ClientId, ClientState> // Connected clients
7
}
8

9
interface ClientState {
10
  clientId: string
11
  lastAckedRevision: number
12
  cursor: CursorPosition | null
13
  color: string // For presence display
14
}

1
interface PresenceUpdate {
2
  clientId: string
3
  documentId: string
4
  cursor: {
5
    anchor: number // Selection start (character position)
6
    head: number // Selection end (cursor position)
7
  } | null
8
  user: {
9
    id: string
10
    name: string
11
    avatar: string
12
    color: string // Assigned per-document
13
  }
14
  timestamp: number
15
}

1
{
2
  "type": "operation",
3
  "documentId": "doc_abc123",
4
  "clientId": "client_xyz",
5
  "baseRevision": 142,
6
  "operation": {
7
    "ops": [{ "retain": 50 }, { "insert": "Hello, " }, { "retain": 100 }, { "delete": 5 }]
8
  },
9
  "timestamp": 1706886400000
10
}

1
{
2
  "type": "presence",
3
  "documentId": "doc_abc123",
4
  "cursor": { "anchor": 150, "head": 150 },
5
  "selection": null
6
}

1
{
2
  "type": "ack",
3
  "documentId": "doc_abc123",
4
  "revision": 143,
5
  "transformedOp": { ... }
6
}

1
{
2
  "type": "remote_operation",
3
  "documentId": "doc_abc123",
4
  "clientId": "client_other",
5
  "revision": 143,
6
  "operation": { ... },
7
  "user": {
8
    "id": "user_123",
9
    "name": "Alice"
10
  }
11
}

1
{
2
  "type": "remote_presence",
3
  "documentId": "doc_abc123",
4
  "presences": [
5
    {
6
      "clientId": "client_other",
7
      "cursor": { "anchor": 200, "head": 210 },
8
      "user": { "id": "user_123", "name": "Alice", "color": "#4285f4" }
9
    }
10
  ]
11
}

1
{
2
  "title": "Untitled Document",
3
  "content": "",
4
  "folderId": "folder_abc",
5
  "templateId": "template_xyz"
6
}

1
{
2
  "id": "doc_abc123",
3
  "title": "Untitled Document",
4
  "revision": 0,
5
  "createdAt": "2024-02-03T10:00:00Z",
6
  "createdBy": {
7
    "id": "user_123",
8
    "name": "Alice"
9
  },
10
  "permissions": {
11
    "owner": "user_123",
12
    "editors": [],
13
    "viewers": []
14
  },
15
  "wsEndpoint": "wss://collab.example.com/ws/doc_abc123"
16
}

1
{
2
  "id": "doc_abc123",
3
  "title": "Project Proposal",
4
  "revision": 1542,
5
  "content": {
6
    "type": "doc",
7
    "content": [
8
      {
9
        "type": "heading",
10
        "attrs": { "level": 1 },
11
        "content": [{ "type": "text", "text": "Introduction" }]
12
      },
13
      {
14
        "type": "paragraph",
15
        "content": [{ "type": "text", "text": "..." }]
16
      }
17
    ]
18
  },
19
  "snapshot": {
20
    "revision": 1500,
21
    "createdAt": "2024-02-03T09:00:00Z"
22
  },
23
  "pendingOperations": 42,
24
  "collaborators": [{ "id": "user_456", "name": "Bob", "online": true }]
25
}

1
{
2
  "revisions": [
3
    {
4
      "revision": 1542,
5
      "timestamp": "2024-02-03T10:30:00Z",
6
      "user": { "id": "user_123", "name": "Alice" },
7
      "summary": "Edited section 3",
8
      "operationCount": 15
9
    },
10
    {
11
      "revision": 1500,
12
      "timestamp": "2024-02-03T09:00:00Z",
13
      "user": { "id": "user_456", "name": "Bob" },
14
      "summary": "Added introduction",
15
      "operationCount": 203,
16
      "isSnapshot": true
17
    }
18
  ],
19
  "hasMore": true,
20
  "nextCursor": "rev_1499"
21
}

1
{
2
  "error": "REVISION_CONFLICT",
3
  "message": "Base revision 100 is too old. Current: 150",
4
  "currentRevision": 150,
5
  "missingOperations": "/api/v1/documents/doc_abc/operations?from=100&to=150"
6
}

1
CREATE TABLE documents (
2
    id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
3
    title TEXT NOT NULL,
4
    owner_id UUID NOT NULL REFERENCES users(id),
5
    folder_id UUID REFERENCES folders(id),
6
    current_revision BIGINT DEFAULT 0,
7
    latest_snapshot_revision BIGINT,
8
    content_type VARCHAR(50) DEFAULT 'rich_text',
9
    created_at TIMESTAMPTZ DEFAULT NOW(),
10
    updated_at TIMESTAMPTZ DEFAULT NOW(),
11
    deleted_at TIMESTAMPTZ,
12

13
    -- Denormalized for read performance
14
    collaborator_count INT DEFAULT 0,
15
    word_count INT DEFAULT 0,
16
    last_edited_by UUID REFERENCES users(id),
17
    last_edited_at TIMESTAMPTZ
18
);
19

20
-- Access control
21
CREATE TABLE document_permissions (
22
    document_id UUID REFERENCES documents(id) ON DELETE CASCADE,
23
    user_id UUID REFERENCES users(id),
24
    role VARCHAR(20) NOT NULL, -- 'owner', 'editor', 'commenter', 'viewer'
25
    granted_at TIMESTAMPTZ DEFAULT NOW(),
26
    granted_by UUID REFERENCES users(id),
27
    PRIMARY KEY (document_id, user_id)
28
);
29

30
CREATE INDEX idx_documents_owner ON documents(owner_id, updated_at DESC);
31
CREATE INDEX idx_documents_folder ON documents(folder_id, updated_at DESC);
32
CREATE INDEX idx_permissions_user ON document_permissions(user_id);

1
{
2
  "document_id": "doc_abc123",
3
  "revision": 1542,
4
  "operation": {
5
    "ops": [{ "retain": 50 }, { "insert": "Hello" }]
6
  },
7
  "client_id": "client_xyz",
8
  "user_id": "user_123",
9
  "timestamp": 1706886400000,
10
  "checksum": "sha256:abc123...",
11
  "ttl": null
12
}

1
s3://doc-snapshots/{document_id}/{revision}.json.gz

1
{
2
  "documentId": "doc_abc123",
3
  "revision": 1500,
4
  "createdAt": "2024-02-03T09:00:00Z",
5
  "content": {
6
    "type": "doc",
7
    "content": [...]
8
  },
9
  "metadata": {
10
    "wordCount": 5420,
11
    "characterCount": 32150,
12
    "imageCount": 12
13
  },
14
  "checksum": "sha256:..."
15
}

1
# Document state (hash)
2
HSET doc:{id}:state
3
    revision 1542
4
    content "{serialized_content}"
5
    last_updated 1706886400000
6

7
# Connected clients (sorted set by last activity)
8
ZADD doc:{id}:clients {timestamp} {client_id}
9

10
# Pending operations queue (list)
11
RPUSH doc:{id}:pending "{operation_json}"
12

13
# Presence (hash with TTL per client)
14
HSET doc:{id}:presence:{client_id}
15
    cursor_anchor 150
16
    cursor_head 150
17
    user_name "Alice"
18
    user_color "#4285f4"
19
EXPIRE doc:{id}:presence:{client_id} 60

1
type Operation = {
2
  ops: (RetainOp | InsertOp | DeleteOp)[]
3
}
4

5
type RetainOp = {
6
  retain: number
7
  attributes?: Record<string, any> // For formatting changes
8
}
9

10
type InsertOp = {
11
  insert: string | { image: string } | { embed: any }
12
  attributes?: Record<string, any>
13
}
14

15
type DeleteOp = {
16
  delete: number
17
}

1
// Insert "Hello" at position 0
2
{
3
  ops: [{ insert: "Hello" }]
4
}
5

6
// Delete 3 characters at position 10
7
{
8
  ops: [{ retain: 10 }, { delete: 3 }]
9
}
10

11
// Bold characters 5-10
12
{
13
  ops: [{ retain: 5 }, { retain: 5, attributes: { bold: true } }]
14
}

10 collapsed lines
1
function transform(op1: Operation, op2: Operation, priority: "left" | "right"): [Operation, Operation] {
2
  // op1' = transform(op1, op2) - op1 transformed against op2
3
  // op2' = transform(op2, op1) - op2 transformed against op1
4
  // Guarantee: apply(apply(doc, op1), op2') === apply(apply(doc, op2), op1')
5

6
  const ops1 = [...op1.ops]
7
  const ops2 = [...op2.ops]
8
  const result1: Op[] = []
9
  const result2: Op[] = []
10

11
  let i1 = 0,
12
    i2 = 0
13

14
  while (i1 < ops1.length || i2 < ops2.length) {
15
    const o1 = ops1[i1]
16
    const o2 = ops2[i2]
17

18
    // Case: insert vs anything - inserts go first
19
    if (o1 && "insert" in o1) {
20
      if (priority === "left") {
21
        result2.push({ retain: insertLength(o1) })
22
        result1.push(o1)
23
        i1++
24
        continue
25
      }
26
    }
27
    if (o2 && "insert" in o2) {
28
      result1.push({ retain: insertLength(o2) })
29
      result2.push(o2)
30
      i2++
31
      continue
32
    }
33

34
    // Case: retain vs retain
35
    if (o1 && "retain" in o1 && o2 && "retain" in o2) {
36
      const len = Math.min(o1.retain, o2.retain)
37
      result1.push({ retain: len, attributes: o1.attributes })
38
      result2.push({ retain: len, attributes: o2.attributes })
39
      consumeLength(ops1, i1, len)
40
      consumeLength(ops2, i2, len)
41
      continue
42
    }
43

44
    // Case: delete vs retain
45
    if (o1 && "delete" in o1 && o2 && "retain" in o2) {
46
      const len = Math.min(o1.delete, o2.retain)
47
      result1.push({ delete: len })
48
      // o2 doesn't produce output - deleted content
49
      consumeLength(ops1, i1, len)
50
      consumeLength(ops2, i2, len)
51
      continue
52
    }
53

54
    // Case: retain vs delete
55
    if (o1 && "retain" in o1 && o2 && "delete" in o2) {
56
      const len = Math.min(o1.retain, o2.delete)
57
      // o1 doesn't produce output - deleted content
58
      result2.push({ delete: len })
59
      consumeLength(ops1, i1, len)
60
      consumeLength(ops2, i2, len)
61
      continue
62
    }
63

64
    // Case: delete vs delete - both delete same content
65
    if (o1 && "delete" in o1 && o2 && "delete" in o2) {
66
      const len = Math.min(o1.delete, o2.delete)
67
      // Neither produces output - already deleted
68
      consumeLength(ops1, i1, len)
69
      consumeLength(ops2, i2, len)
70
      continue
71
    }
72
  }
73

74
  return [{ ops: result1 }, { ops: result2 }]
75
}

15 collapsed lines
1
class DocumentProcessor {
2
  private state: DocumentState
3
  private opLog: OperationLog
4
  private broadcaster: Broadcaster
5

6
  async processOperation(clientId: string, baseRevision: number, operation: Operation): Promise<ProcessResult> {
7
    // 1. Validate base revision
8
    if (baseRevision < this.state.revision - MAX_REVISION_LAG) {
9
      throw new RevisionConflictError(this.state.revision)
10
    }
11

12
    // 2. Transform against all operations since base
13
    let transformedOp = operation
14
    for (let rev = baseRevision + 1; rev <= this.state.revision; rev++) {
15
      const serverOp = await this.opLog.getOperation(this.state.documentId, rev)
16
      ;[transformedOp] = transform(transformedOp, serverOp, "right")
17
    }
18

19
    // 3. Apply to document state
20
    const newContent = applyOperation(this.state.content, transformedOp)
21
    const newRevision = this.state.revision + 1
22

23
    // 4. Persist operation (async, but before ack)
24
    await this.opLog.append({
25
      documentId: this.state.documentId,
26
      revision: newRevision,
27
      operation: transformedOp,
28
      clientId,
29
      timestamp: Date.now(),
30
    })
31

32
    // 5. Update in-memory state
33
    this.state.content = newContent
34
    this.state.revision = newRevision
35

36
    // 6. Broadcast to other clients
37
    this.broadcaster.broadcastOperation(
38
      this.state.documentId,
39
      clientId, // Exclude sender
40
      newRevision,
41
      transformedOp,
42
    )
43

44
    // 7. Return acknowledgment
45
    return {
46
      revision: newRevision,
47
      transformedOp,
48
    }
49
  }
50
}

12 collapsed lines
1
type ClientOTState =
2
  | { type: "synchronized"; serverRevision: number }
3
  | { type: "awaitingAck"; serverRevision: number; pending: Operation }
4
  | { type: "awaitingWithBuffer"; serverRevision: number; pending: Operation; buffer: Operation }
5

6
class ClientOT {
7
  private state: ClientOTState = { type: "synchronized", serverRevision: 0 }
8
  private document: DocumentContent
9

10
  onLocalEdit(operation: Operation): void {
11
    switch (this.state.type) {
12
      case "synchronized":
13
        // Send immediately
14
        this.sendToServer(operation, this.state.serverRevision)
15
        this.state = {
16
          type: "awaitingAck",
17
          serverRevision: this.state.serverRevision,
18
          pending: operation,
19
        }
20
        break
21

22
      case "awaitingAck":
23
        // Buffer - compose with existing buffer or create new
24
        this.state = {
25
          type: "awaitingWithBuffer",
26
          serverRevision: this.state.serverRevision,
27
          pending: this.state.pending,
28
          buffer: operation,
29
        }
30
        break
31

32
      case "awaitingWithBuffer":
33
        // Compose into buffer
34
        this.state = {
35
          ...this.state,
36
          buffer: compose(this.state.buffer, operation),
37
        }
38
        break
39
    }
40

41
    // Apply locally immediately
42
    this.document = applyOperation(this.document, operation)
43
  }
44

45
  onServerAck(revision: number): void {
46
    switch (this.state.type) {
47
      case "awaitingAck":
48
        this.state = { type: "synchronized", serverRevision: revision }
49
        break
50

51
      case "awaitingWithBuffer":
52
        // Send buffered operations
53
        this.sendToServer(this.state.buffer, revision)
54
        this.state = {
55
          type: "awaitingAck",
56
          serverRevision: revision,
57
          pending: this.state.buffer,
58
        }
59
        break
60
    }
61
  }
62

63
  onRemoteOperation(revision: number, operation: Operation): void {
64
    // Transform remote op against pending/buffer
65
    let transformedRemote = operation
66

67
    if (this.state.type === "awaitingAck" || this.state.type === "awaitingWithBuffer") {
68
      ;[, transformedRemote] = transform(this.state.pending, operation, "left")
69

70
      // Also transform pending against remote
71
      const [newPending] = transform(this.state.pending, operation, "left")
72
      this.state = { ...this.state, pending: newPending }
73
    }
74

75
    if (this.state.type === "awaitingWithBuffer") {
76
      ;[, transformedRemote] = transform(this.state.buffer, transformedRemote, "left")
77

78
      const [newBuffer] = transform(this.state.buffer, operation, "left")
79
      this.state = { ...this.state, buffer: newBuffer }
80
    }
81

82
    // Apply transformed remote operation
83
    this.document = applyOperation(this.document, transformedRemote)
84
  }
85
}

8 collapsed lines
1
class SnapshotWorker {
2
  private readonly SNAPSHOT_THRESHOLD = 1000 // Operations since last snapshot
3
  private readonly SNAPSHOT_INTERVAL_MS = 3600000 // 1 hour
4

5
  async processDocument(documentId: string): Promise<void> {
6
    const doc = await this.documentStore.getMetadata(documentId)
7
    const latestSnapshot = await this.snapshotStore.getLatest(documentId)
8

9
    const opsSinceSnapshot = doc.currentRevision - (latestSnapshot?.revision ?? 0)
10
    const timeSinceSnapshot = Date.now() - (latestSnapshot?.createdAt ?? 0)
11

12
    if (opsSinceSnapshot < this.SNAPSHOT_THRESHOLD && timeSinceSnapshot < this.SNAPSHOT_INTERVAL_MS) {
13
      return // No snapshot needed
14
    }
15

16
    // Build document state
17
    let content = latestSnapshot?.content ?? emptyDocument()
18
    const operations = await this.opLog.getRange(documentId, (latestSnapshot?.revision ?? 0) + 1, doc.currentRevision)
19

20
    for (const op of operations) {
21
      content = applyOperation(content, op.operation)
22
    }
23

24
    // Store snapshot
25
    await this.snapshotStore.create({
26
      documentId,
27
      revision: doc.currentRevision,
28
      content,
29
      createdAt: Date.now(),
30
    })
31

32
    // Mark old operations for TTL expiry (keep last 100 for recent history)
33
    await this.opLog.setTTL(documentId, 0, doc.currentRevision - 100, TTL_30_DAYS)
34
  }
35
}

15 collapsed lines
1
class CollaborativeEditor {
2
  private view: EditorView
3
  private otClient: ClientOT
4
  private ws: WebSocket
5

6
  constructor(container: HTMLElement, documentId: string) {
7
    // Initialize OT client
8
    this.otClient = new ClientOT()
9

10
    // Connect WebSocket
11
    this.ws = new WebSocket(`wss://collab.example.com/ws/${documentId}`)
12
    this.ws.onmessage = this.handleServerMessage.bind(this)
13

14
    // Initialize editor with collaboration plugin
15
    this.view = new EditorView(container, {
16
      state: EditorState.create({
17
        plugins: [collab({ version: 0 }), this.cursorPlugin(), this.presencePlugin()],
18
      }),
19
      dispatchTransaction: this.handleLocalChange.bind(this),
20
    })
21
  }
22

23
  private handleLocalChange(tr: Transaction): void {
24
    const newState = this.view.state.apply(tr)
25
    this.view.updateState(newState)
26

27
    if (tr.docChanged) {
28
      // Convert ProseMirror steps to OT operations
29
      const steps = sendableSteps(newState)
30
      if (steps) {
31
        const operation = stepsToOperation(steps.steps)
32
        this.otClient.onLocalEdit(operation)
33
        this.ws.send(
34
          JSON.stringify({
35
            type: "operation",
36
            operation,
37
            baseRevision: this.otClient.serverRevision,
38
          }),
39
        )
40
      }
41
    }
42
  }
43
}

20 collapsed lines
1
interface RemoteCursor {
2
  clientId: string
3
  user: { name: string; color: string }
4
  anchor: number
5
  head: number
6
}
7

8
class CursorOverlay {
9
  private cursors: Map<string, RemoteCursor> = new Map()
10

11
  updateCursor(cursor: RemoteCursor): void {
12
    this.cursors.set(cursor.clientId, cursor)
13
    this.render()
14
  }
15

16
  removeCursor(clientId: string): void {
17
    this.cursors.delete(clientId)
18
    this.render()
19
  }
20

21
  private render(): void {
22
    // Convert character positions to screen coordinates
23
    for (const [clientId, cursor] of this.cursors) {
24
      const coords = this.positionToCoords(cursor.head)
25

26
      // Render cursor caret
27
      this.renderCaret(clientId, coords, cursor.user.color)
28

29
      // Render selection highlight if anchor !== head
30
      if (cursor.anchor !== cursor.head) {
31
        this.renderSelection(clientId, cursor.anchor, cursor.head, cursor.user.color)
32
      }
33

34
      // Render name label
35
      this.renderNameLabel(clientId, coords, cursor.user)
36
    }
37
  }
38
}

10 collapsed lines
1
class OfflineQueue {
2
  private db: IDBDatabase
3
  private queueName = "pendingOperations"
4

5
  async enqueue(documentId: string, operation: Operation): Promise<void> {
6
    const tx = this.db.transaction(this.queueName, "readwrite")
7
    const store = tx.objectStore(this.queueName)
8

9
    await store.add({
10
      documentId,
11
      operation,
12
      timestamp: Date.now(),
13
      id: crypto.randomUUID(),
14
    })
15
  }
16

17
  async syncPending(documentId: string): Promise<void> {
18
    const pending = await this.getPending(documentId)
19

20
    for (const item of pending) {
21
      try {
22
        await this.sendOperation(item)
23
        await this.remove(item.id)
24
      } catch (e) {
25
        if (e instanceof RevisionConflictError) {
26
          // Fetch missing ops, transform, retry
27
          await this.handleConflict(documentId, item)
28
        } else {
29
          throw e
30
        }
31
      }
32
    }
33
  }
34
}