Scenario: Google Docs with 2 users editing simultaneously

User A types: "Hello"  (position 0)
User B types: "World"  (position 0)

Problem: How do we merge without losing data?

Naive merge: "World" (B overwrites A) ❌
Lock-based: B waits for A to finish (slow) ❌
CRDT: "HelloWorld" or "WorldHello" (both valid, deterministic) ✅

User A acquires lock → edits → releases lock
User B waits... waits... finally gets lock

Problem: Poor UX, doesn't work offline

User A: "Hello" (timestamp: 12:00:00)
User B: "World" (timestamp: 12:00:01)

Result: "World" (B wins)
Problem: A's work is lost! ❌

Used by Google Docs (historically)
Requires central server to transform operations
Complex edge cases

Example:
User A: Insert("x", position=5)
User B: Delete(position=3)
Server transforms: "A's insert now at position=4" (shifted by delete)

Problem: Requires server, complex implementation

No locking
No central coordination
Always converges to same state
Works offline
P2P friendly

// G-Set (Grow-only Set)
class GSet<T> {
  private elements: Set<T> = new Set();
  
  add(element: T): void {
    this.elements.add(element);
  }
  
  // Merge function (commutative, associative, idempotent)
  merge(other: GSet<T>): GSet<T> {
    const result = new GSet<T>();
    // Union of both sets
    for (const elem of this.elements) {
      result.elements.add(elem);
    }
    for (const elem of other.elements) {
      result.elements.add(elem);
    }
    return result;
  }
  
  has(element: T): boolean {
    return this.elements.has(element);
  }
  
  toArray(): T[] {
    return Array.from(this.elements);
  }
}

// Usage
const set1 = new GSet<string>();
set1.add("apple");
set1.add("banana");

const set2 = new GSet<string>();
set2.add("banana");
set2.add("cherry");

const merged = set1.merge(set2);
// Result: ["apple", "banana", "cherry"]
// Order doesn't matter: merge(set1, set2) === merge(set2, set1)

// OR-Set (Observed-Remove Set)
class ORSet<T> {
  private elements: Map<T, Set<string>> = new Map();  // element → unique tags
  
  add(element: T, uniqueTag: string = uuid()): void {
    if (!this.elements.has(element)) {
      this.elements.set(element, new Set());
    }
    this.elements.get(element)!.add(uniqueTag);
  }
  
  remove(element: T): void {
    // Remove all observed tags for this element
    this.elements.delete(element);
  }
  
  has(element: T): boolean {
    const tags = this.elements.get(element);
    return tags !== undefined && tags.size > 0;
  }
  
  merge(other: ORSet<T>): ORSet<T> {
    const result = new ORSet<T>();
    
    // Union of all elements with their tags
    for (const [elem, tags] of this.elements) {
      for (const tag of tags) {
        result.add(elem, tag);
      }
    }
    for (const [elem, tags] of other.elements) {
      for (const tag of tags) {
        result.add(elem, tag);
      }
    }
    
    return result;
  }
}

// Example: Concurrent add/remove
const set1 = new ORSet<string>();
set1.add("item", "tag1");

const set2 = new ORSet<string>();
set2.add("item", "tag1");  // Same item
set2.remove("item");       // But then removed

const merged = set1.merge(set2);
merged.has("item");  // false - remove wins (both observed it before removal)

Initial: "Hello"

User A inserts "Beautiful " at position 0:
Result: "Beautiful Hello"

User B (simultaneously) inserts "World" at position 6:
Result: "Hello World"

How to merge?

interface Character {
  id: string;           // Unique ID
  value: string;        // Actual character
  timestamp: number;    // For ordering
  left: string | null;  // ID of character to the left
  right: string | null; // ID of character to the right
  deleted: boolean;
}

class RGA {
  private chars: Map<string, Character> = new Map();
  private head: string | null = null;
  
  insert(value: string, afterId: string | null, id: string = uuid(), timestamp: number = Date.now()): void {
    const char: Character = {
      id,
      value,
      timestamp,
      left: afterId,
      right: null,
      deleted: false
    };
    
    if (afterId) {
      const leftChar = this.chars.get(afterId)!;
      char.right = leftChar.right;
      leftChar.right = id;
      
      if (char.right) {
        this.chars.get(char.right)!.left = id;
      }
    } else {
      // Insert at beginning
      char.right = this.head;
      if (this.head) {
        this.chars.get(this.head)!.left = id;
      }
      this.head = id;
    }
    
    this.chars.set(id, char);
  }
  
  delete(id: string): void {
    const char = this.chars.get(id);
    if (char) {
      char.deleted = true;  // Tombstone (don't actually remove)
    }
  }
  
  toString(): string {
    let result = '';
    let current = this.head;
    
    while (current) {
      const char = this.chars.get(current)!;
      if (!char.deleted) {
        result += char.value;
      }
      current = char.right;
    }
    
    return result;
  }
  
  merge(other: RGA): void {
    // Merge all characters from other
    for (const [id, char] of other.chars) {
      if (!this.chars.has(id)) {
        this.chars.set(id, { ...char });
      } else {
        // Conflict resolution: use timestamp
        const existing = this.chars.get(id)!;
        if (char.timestamp > existing.timestamp) {
          this.chars.set(id, { ...char });
        }
      }
    }
    
    // Rebuild ordering
    this.rebuildOrder();
  }
  
  private rebuildOrder(): void {
    // Rebuild linked list based on timestamps and IDs
    // (Simplified - real implementation more complex)
  }
}

// Example usage
const doc1 = new RGA();
doc1.insert('H', null, 'id1');
doc1.insert('e', 'id1', 'id2');
doc1.insert('l', 'id2', 'id3');
doc1.insert('l', 'id3', 'id4');
doc1.insert('o', 'id4', 'id5');

console.log(doc1.toString());  // "Hello"

// Concurrent edits
const doc2 = new RGA();
doc2.merge(doc1);

doc1.insert(' ', 'id5', 'id6');
doc1.insert('W', 'id6', 'id7');
doc1.insert('o', 'id7', 'id8');
doc1.insert('r', 'id8', 'id9');
doc1.insert('l', 'id9', 'id10');
doc1.insert('d', 'id10', 'id11');

doc2.insert('!', 'id5', 'id12');

doc1.merge(doc2);
console.log(doc1.toString());  // "Hello World!" (deterministic merge)

import * as Y from 'yjs';
import { WebrtcProvider } from 'y-webrtc';

// Create shared document
const ydoc = new Y.Doc();

// Create shared text type
const ytext = ydoc.getText('mytext');

// P2P sync via WebRTC
const provider = new WebrtcProvider('my-room-name', ydoc);

// Local edits
ytext.insert(0, 'Hello');
ytext.insert(5, ' World');

// Observ changes (from local and remote)
ytext.observe(event => {
  console.log('Text changed:', ytext.toString());
});

// Delete range
ytext.delete(0, 5);  // Remove "Hello"

// Collaborative cursors
const awareness = provider.awareness;
awareness.setLocalStateField('cursor', { position: 5, color: '#ff0000' });

awareness.on('change', () => {
  const states = awareness.getStates();
  states.forEach((state, clientId) => {
    console.log(`Client ${clientId} cursor at:`, state.cursor);
  });
});

import * as Automerge from '@automerge/automerge';

// Create document
let doc1 = Automerge.init();

// Make changes
doc1 = Automerge.change(doc1, doc => {
  doc.text = new Automerge.Text();
  doc.text.insertAt(0, ...'Hello'.split(''));
});

// Fork document (simulate 2 users)
let doc2 = Automerge.clone(doc1);

// Concurrent edits
doc1 = Automerge.change(doc1, doc => {
  doc.text.insertAt(5, ...' World'.split(''));
});

doc2 = Automerge.change(doc2, doc => {
  doc.text.insertAt(0, ...'Hi '.split(''));
});

// Merge
doc1 = Automerge.merge(doc1, doc2);

console.log(doc1.text.toString());  // "Hi Hello World"

// Time travel
const history = Automerge.getHistory(doc1);
history.forEach((state, index) => {
  console.log(`Version ${index}:`, state.snapshot.text.toString());
});

class GCounter {
  private counts: Map<string, number> = new Map();  // nodeId → count
  
  constructor(private nodeId: string) {
    this.counts.set(nodeId, 0);
  }
  
  increment(amount: number = 1): void {
    const current = this.counts.get(this.nodeId) || 0;
    this.counts.set(this.nodeId, current + amount);
  }
  
  value(): number {
    let total = 0;
    for (const count of this.counts.values()) {
      total += count;
    }
    return total;
  }
  
  merge(other: GCounter): GCounter {
    const result = new GCounter(this.nodeId);
    
    // Take max count for each node
    const allNodes = new Set([...this.counts.keys(), ...other.counts.keys()]);
    
    for (const nodeId of allNodes) {
      const thisCount = this.counts.get(nodeId) || 0;
      const otherCount = other.counts.get(nodeId) || 0;
      result.counts.set(nodeId, Math.max(thisCount, otherCount));
    }
    
    return result;
  }
}

// Example: Distributed counter
const counter1 = new GCounter('node1');
counter1.increment(5);

const counter2 = new GCounter('node2');
counter2.increment(3);

const merged = counter1.merge(counter2);
console.log(merged.value());  // 8

class LWWSet<T> {
  private adds: Map<T, number> = new Map();     // element → timestamp
  private removes: Map<T, number> = new Map();  // element → timestamp
  
  add(element: T, timestamp: number = Date.now()): void {
    this.adds.set(element, timestamp);
  }
  
  remove(element: T, timestamp: number = Date.now()): void {
    this.removes.set(element, timestamp);
  }
  
  has(element: T): boolean {
    const addTime = this.adds.get(element) || 0;
    const removeTime = this.removes.get(element) || 0;
    
    // Element exists if added after last removal (or never removed)
    return addTime > removeTime;
  }
  
  merge(other: LWWSet<T>): LWWSet<T> {
    const result = new LWWSet<T>();
    
    // Merge adds (take latest timestamp)
    for (const [elem, time] of this.adds) {
      result.adds.set(elem, time);
    }
    for (const [elem, time] of other.adds) {
      const existing = result.adds.get(elem) || 0;
      result.adds.set(elem, Math.max(existing, time));
    }
    
    // Merge removes (take latest timestamp)
    for (const [elem, time] of this.removes) {
      result.removes.set(elem, time);
    }
    for (const [elem, time] of other.removes) {
      const existing = result.removes.get(elem) || 0;
      result.removes.set(elem, Math.max(existing, time));
    }
    
    return result;
  }
}

CRDTs used for:
- Object properties (position, color, size)
- Layer ordering
- Selection state
- Comments

Benefits:
- Real-time collaboration
- Offline editing
- No central bottleneck
- 60 FPS performance

Redis CRDTs:
- Counters (page views across regions)
- Sets (unique visitors)
- Registers (configuration values)

Multi-region setup:
Region 1: counter.increment(5)
Region 2: counter.increment(3)
Merge: 8 (consistent everywhere)

CRDT-based sync:
- Edit on iPhone (offline)
- Edit on Mac (simultaneously)
- Both sync to iCloud
- Changes merge automatically
- No conflicts, no data loss