Design Google Docs: Real-Time Collaborative Editing at Scale

// io.thecodeforge — System Design tutorial

// Simplified OT for insert operations
// Assume document is a string, operations are {type, position, text}

function transform(op1, op2) {
  // op1 and op2 are concurrent operations
  // Return transformed op1' such that applying op2 then op1' is equivalent to op1 then op2'
  if (op1.type === 'insert' && op2.type === 'insert') {
    if (op1.position < op2.position) {
      // op1 stays, op2 shifts right by length of op1.text
      return { ...op1 };
    } else if (op1.position > op2.position) {
      // op1 shifts right by length of op2.text
      return { ...op1, position: op1.position + op2.text.length };
    } else {
      // Same position: use tie-breaker (e.g., user ID)
      if (op1.userId < op2.userId) {
        return { ...op1 };
      } else {
        return { ...op1, position: op1.position + op2.text.length };
      }
    }
  }
  // ... handle delete, replace etc.
}

// Example:
let doc = "hello";
let opA = { type: 'insert', position: 0, text: 'x', userId: 'A' };
let opB = { type: 'insert', position: 0, text: 'y', userId: 'B' };

// Server receives opA then opB (order arbitrary, but we need to apply both)
// Transform opB against opA:
let opBPrime = transform(opB, opA); // position becomes 1 (since opA inserted 'x' at 0)
// Apply opA then opBPrime:
doc = apply(doc, opA); // "xhello"
doc = apply(doc, opBPrime); // "xyhello"
// If we had applied opB then opAPrime, result would be "yxhello" — different! 
// OT ensures convergence only if transformation functions satisfy TP1 and TP2 properties.
console.log(doc); // "xyhello" — but this is not necessarily what users intended; real OT is more complex.

// io.thecodeforge — System Design tutorial

// Server-side operation handler (pseudocode)

class DocumentServer {
  constructor() {
    this.version = 0;
    this.operations = []; // persisted to DB
    this.document = "";
  }

  handleOperation(clientOp, clientVersion) {
    // Client sends its last known version
    // Transform clientOp against all operations after clientVersion
    let transformedOp = clientOp;
    for (let i = clientVersion; i < this.version; i++) {
      transformedOp = transform(transformedOp, this.operations[i]);
    }
    // Apply to server document
    this.document = apply(this.document, transformedOp);
    // Assign new version
    const newVersion = this.version++;
    this.operations.push(transformedOp);
    // Persist operation to DB (async, but critical for recovery)
    persistOperation(newVersion, transformedOp);
    // Broadcast to all clients
    broadcast({ op: transformedOp, version: newVersion });
  }
}

// Client-side: send operation with last known version
// On receiving broadcast, apply op and update local version
// If broadcast version > expected, request missing ops from server

// io.thecodeforge — System Design tutorial

// Using character IDs to avoid position shifts
// Each character gets a unique ID (e.g., UUID)
// Operations reference character IDs

class Char {
  constructor(id, value) {
    this.id = id;
    this.value = value;
  }
}

class Document {
  constructor() {
    this.chars = []; // ordered list of Char objects
  }

  applyInsert(afterCharId, newChar) {
    const idx = this.chars.findIndex(c => c.id === afterCharId);
    this.chars.splice(idx + 1, 0, newChar);
  }

  applyDelete(charId) {
    const idx = this.chars.findIndex(c => c.id === charId);
    this.chars.splice(idx, 1);
  }
}

// Transformation becomes simpler: no position shifting
// But you need to handle the case where the referenced character was deleted
// Solution: if charId not found, the operation is a no-op (or transformed to insert at end)

function transformInsert(op1, op2) {
  // op1 and op2 are inserts with afterCharId
  // If they reference the same afterCharId, use tie-breaker
  if (op1.afterCharId === op2.afterCharId) {
    // Insert op2's char before op1's char (or vice versa based on user ID)
    return { ...op1, afterCharId: op2.newChar.id }; // op1 now inserts after op2's char
  }
  // Otherwise, no transformation needed
  return op1;
}

// io.thecodeforge — System Design tutorial

// Cursor representation: { anchorCharId: string, focusCharId: string }
// anchorCharId is the character before the cursor (or null if at start)
// focusCharId is for selection (same as anchor for cursor)

function transformCursor(cursor, operation) {
  // If operation deletes the anchor character, move cursor to next valid
  if (operation.type === 'delete' && operation.charId === cursor.anchorCharId) {
    // Find next character in document after deleted one
    const nextChar = getNextChar(cursor.anchorCharId);
    cursor.anchorCharId = nextChar ? nextChar.id : null;
  }
  // If operation inserts before the anchor, anchor stays same (insert is after anchor)
  // If operation inserts after the anchor, no change
  // If operation inserts at the same position as anchor, anchor stays (insert is after)
  return cursor;
}

// Broadcast cursor updates at most every 50ms to avoid flooding
// Use a separate WebSocket channel for cursor updates (lower priority)

// io.thecodeforge — System Design tutorial

// Write-Ahead Log (WAL) for operation persistence

class WAL {
  constructor() {
    this.buffer = [];
    this.flushInterval = setInterval(() => this.flush(), 10); // flush every 10ms
  }

  append(operation) {
    this.buffer.push(operation);
    if (this.buffer.length >= 100) {
      this.flush();
    }
  }

  flush() {
    if (this.buffer.length === 0) return;
    // Write buffer to disk (e.g., append to file or DB)
    db.insertOperations(this.buffer);
    this.buffer = [];
  }

  recover(documentId) {
    // Load all operations from DB and replay
    const ops = db.getOperations(documentId);
    let doc = "";
    for (const op of ops) {
      doc = apply(doc, op);
    }
    return doc;
  }
}

// On server start:
// 1. Recover document state from WAL
// 2. Connect to clients
// 3. For each client, compare last acknowledged version with server version
// 4. Request missing operations from clients if server is behind

// io.thecodeforge — System Design tutorial

// Shard assignment: hash(documentId) % numShards
// Each shard is a separate process or container

class DocumentShard {
  constructor(shardId) {
    this.shardId = shardId;
    this.documents = new Map(); // documentId -> { state, version, operationLog }
    this.cache = new LRUCache({ max: 10000 }); // cache compiled state
  }

  getDocumentState(documentId) {
    if (this.cache.has(documentId)) {
      return this.cache.get(documentId);
    }
    // Rebuild from operation log
    const log = this.getOperationLog(documentId);
    let state = "";
    for (const op of log) {
      state = apply(state, op);
    }
    this.cache.set(documentId, state);
    return state;
  }

  handleOperation(documentId, operation) {
    // Apply operation, update log, increment version
    // Invalidate cache for this document
    this.cache.delete(documentId);
    // Persist operation
    // Broadcast to clients
  }
}

// Load balancer routes requests based on document ID hash

// io.thecodeforge — System Design tutorial

// Client-side offline operation queue
class OfflineQueue {
  constructor() {
    this.queue = [];
    this.lastSyncedVersion = 0;
  }

  addOperation(op) {
    this.queue.push(op);
  }

  async sync(server) {
    // Send all queued operations with lastSyncedVersion
    const response = await server.syncOperations({
      operations: this.queue,
      lastVersion: this.lastSyncedVersion
    });
    // Server returns transformed operations that the client must apply
    for (const op of response.transformedOps) {
      applyLocal(op);
    }
    this.queue = [];
    this.lastSyncedVersion = response.newVersion;
  }
}

// Server-side sync handler
function handleSync(clientOps, clientVersion) {
  let transformedOps = [];
  for (const op of clientOps) {
    // Transform against server operations after clientVersion
    let transformed = op;
    for (let i = clientVersion; i < serverVersion; i++) {
      transformed = transform(transformed, serverOps[i]);
    }
    // Apply to server
    applyServer(transformed);
    transformedOps.push(transformed);
    clientVersion++;
  }
  // Also send any server operations that happened after client's last version
  // that were not transformed (i.e., concurrent ops that client hasn't seen)
  const serverOpsSince = serverOps.slice(clientVersion);
  return { transformedOps, serverOpsSince, newVersion: serverVersion };
}

// io.thecodeforge — System Design tutorial

// CRDT approach: each character has a unique ID and a list of 'causally ready' parents
// Insert operation: { charId, value, afterId: [list of IDs that this char should follow] }
// Delete operation: { charId, tombstone: true }

// Convergence: all clients apply operations in any order, result is the same
// because inserts are commutative (they specify explicit ordering via afterId)

// Example: two clients insert 'x' and 'y' after the same character 'a'
// Client A: insert { charId: 'x', afterId: ['a'] }
// Client B: insert { charId: 'y', afterId: ['a'] }
// Both clients will have 'axy' or 'ayx' depending on tie-breaker (e.g., charId comparison)
// But both will converge to the same order because tie-breaker is deterministic

// OT would require a server to order these operations; CRDT doesn't.