Collaborative Editing – Model & Schema

Overview

Collaborative editing allows multiple users to edit the same document simultaneously. The challenge is ensuring that all users see a consistent view of the document, even when operations happen concurrently.

Two main approaches exist: Operational Transformation (OT) and CRDTs (Conflict-free Replicated Data Types). Each has different trade-offs in terms of complexity, performance, and consistency guarantees.

Operational Transformation

Transform Algorithm

OT transforms operations to account for concurrent changes:

// Transform two operations: op1' = T(op1, op2)
function transform(op1, op2) {
  // If operations don't overlap, no transformation needed
  if (!operationsOverlap(op1, op2)) {
    return op1;
  }
  
  // Handle different operation pairs
  if (op1.type === 'insert' && op2.type === 'insert') {
    return transformInsertInsert(op1, op2);
  }
  
  if (op1.type === 'insert' && op2.type === 'delete') {
    return transformInsertDelete(op1, op2);
  }
  
  if (op1.type === 'delete' && op2.type === 'insert') {
    return transformDeleteInsert(op1, op2);
  }
  
  if (op1.type === 'delete' && op2.type === 'delete') {
    return transformDeleteDelete(op1, op2);
  }
  
  return op1;
}

function transformInsertInsert(op1, op2) {
  // Both inserting at same position
  if (pathsEqual(op1.path, op2.path) && op1.offset === op2.offset) {
    // Tie-breaking: op1 goes after op2
    return {
      ...op1,
      offset: op1.offset + (typeof op2.content === 'string' ? op2.content.length : 1)
    };
  }
  
  // op2 is before op1
  if (pathBefore(op2.path, op1.path) || 
      (pathsEqual(op2.path, op1.path) && op2.offset < op1.offset)) {
    return {
      ...op1,
      offset: op1.offset + (typeof op2.content === 'string' ? op2.content.length : 1)
    };
  }
  
  return op1;
}

function transformInsertDelete(op1, op2) {
  // op2 deletes content before op1's insert position
  if (pathBefore(op2.path, op1.path)) {
    // Adjust op1's path
    return {
      ...op1,
      path: adjustPathForDeletion(op1.path, op2.path)
    };
  }
  
  // op2 deletes at same position as op1 inserts
  if (pathsEqual(op1.path, op2.path) && op1.offset === op2.offset) {
    // Insert happens after deletion
    return op1;
  }
  
  return op1;
}

OT Editor Implementation

Apply operations with transformation:

// Apply operation with transformation
class OTEditor {
  #operations = [];
  #pendingRemoteOps = [];
  
  applyLocalOperation(op) {
    // Transform against all pending remote operations
    let transformedOp = op;
    for (const remoteOp of this.#pendingRemoteOps) {
      transformedOp = transform(transformedOp, remoteOp);
    }
    
    // Apply transformed operation
    this.#applyOperation(transformedOp);
    this.#operations.push(transformedOp);
  }
  
  applyRemoteOperation(op) {
    // Transform against all local operations that happened after this
    let transformedOp = op;
    const localOpsAfter = this.#getOperationsAfter(op.timestamp);
    
    for (const localOp of localOpsAfter) {
      transformedOp = transform(transformedOp, localOp);
    }
    
    // Apply transformed operation
    this.#applyOperation(transformedOp);
  }
}

CRDT Implementation

Logoot CRDT

CRDTs provide eventual consistency without transformation:

// Logoot-style CRDT for text editing
class LogootCRDT {
  #chars = [];
  #siteId = null;
  #clock = 0;
  
  constructor(siteId) {
    this.#siteId = siteId;
  }
  
  insert(position, content) {
    const newChars = [];
    
    // Generate positions for each character
    for (let i = 0; i < content.length; i++) {
      const charPosition = this.#generatePosition(position, i);
      const char = {
        position: charPosition,
        content: content[i],
        deleted: false
      };
      newChars.push(char);
    }
    
    // Insert in sorted order
    this.#chars.push(...newChars);
    this.#chars.sort(this.#comparePositions);
    
    return newChars;
  }
  
  #generatePosition(after, offset) {
    // Generate position between 'after' and next position
    const next = this.#findNextPosition(after);
    
    if (!next) {
      // Insert at end
      return {
        siteId: this.#siteId,
        clock: ++this.#clock,
        offset: 0
      };
    }
    
    // Generate position between after and next
    return this.#interpolatePosition(after, next);
  }
  
  delete(position) {
    const char = this.#findChar(position);
    if (char) {
      char.deleted = true;
    }
  }
  
  merge(remoteChars) {
    // Merge remote characters into local state
    for (const char of remoteChars) {
      const existing = this.#findChar(char.position);
      if (!existing) {
        this.#chars.push(char);
      }
    }
    
    // Re-sort
    this.#chars.sort(this.#comparePositions);
  }
  
  getDocument() {
    return this.#chars
      .filter(char => !char.deleted)
      .map(char => char.content)
      .join('');
  }
}

CRDT Merge

Merging CRDT states:

// Merge two CRDT states
function mergeCRDT(local, remote) {
  // Combine all characters
  const merged = new Set();
  
  // Add local characters
  local.#chars.forEach(char => {
    merged.add(char);
  });
  
  // Add remote characters
  remote.#chars.forEach(char => {
    merged.add(char);
  });
  
  // Sort by position
  const sorted = Array.from(merged).sort((a, b) => {
    return comparePositions(a.position, b.position);
  });
  
  return sorted;
}

Conflict Resolution

Resolution Strategies

Handle conflicts when operations cannot be automatically resolved:

class ConflictResolver {
  resolve(op1, op2) {
    // Check if operations conflict
    if (!this.#conflicts(op1, op2)) {
      return [op1, op2];
    }
    
    // Apply conflict resolution strategy
    switch (this.#strategy) {
      case 'last-write-wins':
        return this.#lastWriteWins(op1, op2);
      case 'first-write-wins':
        return this.#firstWriteWins(op1, op2);
      case 'merge':
        return this.#merge(op1, op2);
      case 'user-choice':
        return this.#requestUserChoice(op1, op2);
    }
  }
  
  #lastWriteWins(op1, op2) {
    // Operation with later timestamp wins
    if (op1.timestamp > op2.timestamp) {
      return [op1];
    }
    return [op2];
  }
  
  #merge(op1, op2) {
    // Try to merge operations
    if (op1.type === 'update' && op2.type === 'update') {
      // Merge attribute updates
      return [{
        ...op1,
        attrs: { ...op1.attrs, ...op2.attrs }
      }];
    }
    
    // Cannot merge, use last-write-wins
    return this.#lastWriteWins(op1, op2);
  }
}

Position Mapping

Map positions across different document versions:

// Map position across document versions
function mapPosition(position, operations) {
  let mappedPosition = position;
  operations.forEach(op => {
    mappedPosition = transformPosition(mappedPosition, op);
  });
  return mappedPosition;
}

function transformPosition(position, operation) {
  if (operation.type === 'insert') {
    // If insert is before position, adjust
    if (pathBefore(operation.path, position.path) ||
        (pathsEqual(operation.path, position.path) && 
         operation.offset <= position.offset)) {
      return {
        ...position,
        offset: position.offset + (typeof operation.content === 'string' 
          ? operation.content.length 
          : 1)
      };
    }
  }
  
  if (operation.type === 'delete') {
    // If delete is before position, adjust
    if (pathBefore(operation.path, position.path) ||
        (pathsEqual(operation.path, position.path) && 
         operation.offset < position.offset)) {
      return {
        ...position,
        offset: Math.max(0, position.offset - operation.length)
      };
    }
  }
  
  return position;
}