CRDT & Conflict Resolution

Overview

AFFiNE uses Y.js (Yjs) - a high-performance CRDT (Conflict-free Replicated Data Type) implementation for collaborative editing. CRDTs enable multiple users to edit documents simultaneously without conflicts, even when working offline.

What is a CRDT?

CRDTs are data structures that automatically resolve conflicts when multiple users make concurrent changes:

Commutative: Order of operations doesn’t matter
Associative: Grouping of operations doesn’t matter
Idempotent: Applying same operation multiple times has same effect as once

Example: Text Editing

// User A and B both start with: "Hello"

// User A inserts " World" at position 5
UserA: "Hello" → "Hello World"

// User B inserts "!" at position 5 (simultaneously)
UserB: "Hello" → "Hello!"

// After sync, both converge to same state
Result: "Hello World!"

Y.js Document Structure

Creating a Y.Doc

import * as Y from 'yjs';

const ydoc = new Y.Doc({ guid: 'doc-123' });

guid

string

Document identifier. If not provided, a random GUID is generated.

Shared Types

Y.js provides collaborative data structures:

Y.Text - Collaborative Text

const ytext = ydoc.getText('content');

// Insert text
ytext.insert(0, 'Hello');
ytext.insert(5, ' World');

// Delete text
ytext.delete(5, 6); // Removes " World"

// Get current value
console.log(ytext.toString()); // "Hello"

// Observe changes
ytext.observe(event => {
  event.changes.delta.forEach(change => {
    if (change.insert) {
      console.log('Inserted:', change.insert);
    } else if (change.delete) {
      console.log('Deleted:', change.delete, 'chars');
    }
  });
});

Y.Map - Collaborative Key-Value Store

const ymap = ydoc.getMap('metadata');

// Set values
ymap.set('title', 'My Document');
ymap.set('author', 'Alice');
ymap.set('tags', ['work', 'draft']);

// Get values
console.log(ymap.get('title')); // "My Document"

// Delete keys
ymap.delete('tags');

// Observe changes
ymap.observe(event => {
  event.changes.keys.forEach((change, key) => {
    console.log(`${key}: ${change.action}`);
  });
});

Y.Array - Collaborative Array

const yarray = ydoc.getArray('blocks');

// Insert elements
yarray.insert(0, [{ type: 'paragraph', text: 'Hello' }]);
yarray.push([{ type: 'heading', text: 'Title' }]);

// Delete elements
yarray.delete(0, 1);

// Get element
console.log(yarray.get(0));

// Iterate
yarray.forEach(block => {
  console.log(block.type, block.text);
});

Y.XmlFragment - Collaborative XML/HTML

const yxml = ydoc.getXmlFragment('page');

// Create elements
const paragraph = new Y.XmlElement('p');
paragraph.setAttribute('class', 'content');
paragraph.insert(0, [new Y.XmlText('Hello World')]);

yxml.insert(0, [paragraph]);

Document Updates

Encoding Updates

Y.js updates are binary format for efficiency:

// Capture all changes in a transaction
const update = ydoc.transact(() => {
  const ytext = ydoc.getText('content');
  ytext.insert(0, 'Hello');
}, 'local');

// Encode update as Uint8Array
const encodedUpdate = Y.encodeStateAsUpdate(ydoc);

// Convert to base64 for transmission
const base64Update = Buffer.from(encodedUpdate).toString('base64');

Applying Updates

// Receive update from remote
const update = Buffer.from(base64Update, 'base64');

// Apply to local document
Y.applyUpdate(ydoc, update, 'remote');

Pass an origin parameter to distinguish between local and remote updates. This prevents infinite update loops.

State Vectors

State vectors represent which operations a document has seen:

// Encode current state
const stateVector = Y.encodeStateVector(ydoc);

// Get diff: what remoteDoc has that localDoc doesn't
const remoteUpdate = Y.encodeStateAsUpdate(remoteDoc);
const diff = Y.diffUpdate(remoteUpdate, stateVector);

// Apply only the missing changes
Y.applyUpdate(ydoc, diff);

Use Case: Efficiently sync with server by sending state vector and receiving only new updates.

Transactions

Group multiple changes into atomic operations:

ydoc.transact(() => {
  const ymap = ydoc.getMap('metadata');
  const ytext = ydoc.getText('content');
  
  ymap.set('title', 'My Doc');
  ytext.insert(0, 'Hello');
}, 'batch-edit');

// Only one 'update' event is emitted for entire transaction

Transaction Origins

ydoc.on('update', (update: Uint8Array, origin: any) => {
  if (origin === 'remote') {
    // Don't send back to server
    return;
  }
  
  if (origin === 'undo') {
    console.log('Undo operation');
  }
  
  // Send to server
  sendUpdate(update);
});

Update Merging

Client-Side Merging

import { mergeUpdates } from 'yjs';

// Multiple updates from same document
const updates = [
  update1,
  update2,
  update3
];

// Merge into single update
const merged = mergeUpdates(updates);

// Apply merged update
Y.applyUpdate(ydoc, merged);

Server-Side Merging

AFFiNE server uses native Rust bindings for performance:

import { mergeUpdatesInApplyWay } from '../../native';

// Faster than Y.js JavaScript implementation
const merged = mergeUpdatesInApplyWay(updates);

mergeUpdatesInApplyWay uses Yrs (Rust Y-CRDT) and is ~10x faster than JavaScript mergeUpdates for large update batches.

Document Storage

Snapshots and Updates Queue

AFFiNE optimizes storage using snapshot + updates pattern:

interface DocStorage {
  // Latest snapshot
  snapshot: {
    docId: string;
    bin: Uint8Array;
    timestamp: Date;
  };
  
  // Queued updates since snapshot
  updates: Array<{
    docId: string;
    bin: Uint8Array;
    timestamp: Date;
    editor?: string;
  }>;
}

Process:

New updates are appended to queue
When document is loaded, updates are merged into snapshot
Old updates are marked as merged and removed

async getDoc(docId: string) {
  const snapshot = await this.getDocSnapshot(docId);
  const updates = await this.getDocUpdates(docId);
  
  if (updates.length > 0) {
    // Merge updates into snapshot
    const allUpdates = snapshot ? [snapshot, ...updates] : updates;
    const merged = await this.squash(allUpdates);
    
    // Save new snapshot
    await this.setDocSnapshot(merged, snapshot);
    await this.markUpdatesMerged(docId, updates);
    
    return merged;
  }
  
  return snapshot;
}

Diff Calculation

import { diffUpdate, encodeStateVectorFromUpdate } from 'yjs';

async getDocDiff(docId: string, clientStateVector?: Uint8Array) {
  const doc = await this.getDoc(docId);
  
  if (!doc) return null;
  
  return {
    docId,
    // Only send what client doesn't have
    missing: clientStateVector 
      ? diffUpdate(doc.bin, clientStateVector) 
      : doc.bin,
    // Server's current state vector
    state: encodeStateVectorFromUpdate(doc.bin),
    timestamp: doc.timestamp
  };
}

Conflict Resolution

Text Conflicts

Y.js automatically resolves concurrent text edits:

// Initial: "Hello"

// Client A inserts " World" at position 5
const updateA = encodeUpdate(() => {
  ytext.insert(5, ' World');
});

// Client B inserts "!" at position 5 (simultaneously)
const updateB = encodeUpdate(() => {
  ytext.insert(5, '!');
});

// Both apply both updates (order doesn't matter)
Y.applyUpdate(docA, updateB);
Y.applyUpdate(docB, updateA);

// Both converge to: "Hello! World" or "Hello World!"
// Consistent across all clients

Resolution Strategy: Y.js uses Lamport timestamps and client IDs to determine consistent ordering.

Map Conflicts

Last-write-wins based on Lamport timestamps:

// Client A sets title at timestamp 100
ymap.set('title', 'Document A');

// Client B sets title at timestamp 101
ymap.set('title', 'Document B');

// Result: "Document B" (higher timestamp wins)

Array Conflicts

Array operations are position-based with conflict resolution:

// Initial: [A, B, C]

// Client 1 inserts X at position 1
yarray.insert(1, ['X']); // [A, X, B, C]

// Client 2 inserts Y at position 1 (concurrently)
yarray.insert(1, ['Y']); // [A, Y, B, C]

// After sync: [A, X, Y, B, C] or [A, Y, X, B, C]
// Consistent across clients

Sync Peers

AFFiNE implements sync between local and remote storage:

class DocSyncPeer {
  constructor(
    readonly peerId: string,
    readonly local: DocStorage,
    readonly remote: DocStorage,
    readonly syncMetadata: DocSyncStorage
  ) {}
  
  async pullAndPush(docId: string) {
    // Get local state
    const localDoc = await this.local.getDoc(docId);
    const stateVector = localDoc 
      ? encodeStateVectorFromUpdate(localDoc.bin)
      : new Uint8Array();
    
    // Get remote diff
    const remoteDiff = await this.remote.getDocDiff(docId, stateVector);
    
    if (remoteDiff) {
      // Apply remote changes locally
      await this.local.pushDocUpdate({
        docId,
        bin: remoteDiff.missing
      });
      
      // Calculate local changes to push
      const serverStateVector = remoteDiff.state;
      const localDiff = diffUpdate(localDoc.bin, serverStateVector);
      
      if (localDiff.length > 0) {
        // Push local changes to remote
        await this.remote.pushDocUpdate({
          docId,
          bin: localDiff
        });
      }
    }
  }
}

Empty Update Detection

Avoid sending/storing empty updates:

import { isEmptyUpdate } from '@affine/nbstore';

function shouldSendUpdate(update: Uint8Array): boolean {
  if (isEmptyUpdate(update)) {
    return false; // No actual changes
  }
  return true;
}

// Implementation
function isEmptyUpdate(update: Uint8Array): boolean {
  return update.length === 0 || 
         (update.length === 2 && update[0] === 0 && update[1] === 0);
}

Document Locks

Prevent race conditions during snapshot updates:

class DocStorage {
  private readonly locker = new SingletonLocker();
  
  async getDoc(docId: string) {
    // Lock document for atomic read-merge-write
    await using lock = await this.locker.lock(
      `workspace:${this.spaceId}:update`,
      docId
    );
    
    const snapshot = await this.getDocSnapshot(docId);
    const updates = await this.getDocUpdates(docId);
    
    // Merge and save atomically
    if (updates.length > 0) {
      const merged = await this.squash([snapshot, ...updates]);
      await this.setDocSnapshot(merged, snapshot);
      await this.markUpdatesMerged(docId, updates);
      return merged;
    }
    
    return snapshot;
  }
}

History and Undo

Undo Manager

import { UndoManager } from 'yjs';

const ytext = ydoc.getText('content');
const undoManager = new UndoManager(ytext, {
  trackedOrigins: new Set(['local']),
  captureTimeout: 500 // Merge changes within 500ms
});

// Perform change
ytext.insert(0, 'Hello', 'local');

// Undo
undoManager.undo();

// Redo  
undoManager.redo();

// Check state
console.log(undoManager.canUndo());
console.log(undoManager.canRedo());

Snapshots for History

import { snapshot, restoreSnapshot } from 'yjs';

// Create snapshot
const snap = snapshot(ydoc);

// Make changes
ytext.insert(0, 'Hello');

// Restore to snapshot
restoreSnapshot(ydoc, snap);

Best Practices

Use transactions for batch operations to reduce update overhead
Pass origin parameter to prevent infinite update loops
Check for empty updates before sending to reduce network traffic
Use state vectors for efficient sync instead of sending full document
Implement proper locking when merging updates into snapshots
Merge updates periodically to reduce storage size
Use native bindings (Yrs) for performance-critical operations
Track origins in undo manager to avoid undoing remote changes

Performance Optimization

Update Compression

// Instead of sending multiple small updates
const updates = [update1, update2, update3, ...];

// Merge before sending
const merged = mergeUpdatesInApplyWay(updates);
socket.emit('push-update', merged);

// Reduces bandwidth by ~60% on average

Debounce Updates

import { debounce } from 'lodash-es';

const sendUpdate = debounce((update: Uint8Array) => {
  socket.emit('push-update', update);
}, 100);

ydoc.on('update', (update, origin) => {
  if (origin !== 'remote') {
    sendUpdate(update);
  }
});

Lazy Loading

// Only load document when needed
const ydoc = new Y.Doc({ gc: false }); // Disable garbage collection

// Load on first access
const ytext = ydoc.getText('content');
ytext.observe(() => {
  // Document is now active
});

Advanced: Block-Level CRDTs

AFFiNE represents documents as blocks:

interface BlockInfo {
  blockId: string;
  flavour: string; // 'paragraph', 'heading', 'image', etc.
  content?: string[]; // Text content
  blob?: string[]; // Referenced blob IDs
  refDocId?: string[]; // Linked document IDs
  refInfo?: string[]; // Reference metadata
  parentFlavour?: string;
  parentBlockId?: string;
  additional?: string; // JSON metadata
}

Each block is stored in the Y.js document:

const yblocks = ydoc.getMap('blocks');
const block = yblocks.get(blockId) as Y.Map;

block.set('flavour', 'paragraph');
block.set('content', yarray);
block.set('props', ymap);

Getting Started

GraphQL API

Storage & Sync

Extensions

​Overview

​What is a CRDT?

​Example: Text Editing

​Y.js Document Structure

​Creating a Y.Doc

​Shared Types

​Y.Text - Collaborative Text

​Y.Map - Collaborative Key-Value Store

​Y.Array - Collaborative Array

​Y.XmlFragment - Collaborative XML/HTML

​Document Updates

​Encoding Updates

​Applying Updates

​State Vectors

​Transactions

​Transaction Origins

​Update Merging

​Client-Side Merging

​Server-Side Merging

​Document Storage

​Snapshots and Updates Queue

​Diff Calculation

​Conflict Resolution

​Text Conflicts

​Map Conflicts

​Array Conflicts

​Sync Peers

​Empty Update Detection

​Document Locks

​History and Undo

​Undo Manager

​Snapshots for History

​Best Practices

​Performance Optimization

​Update Compression

​Debounce Updates

​Lazy Loading

​Advanced: Block-Level CRDTs

​Resources

Overview

What is a CRDT?

Example: Text Editing

Y.js Document Structure

Creating a Y.Doc

Shared Types

Y.Text - Collaborative Text

Y.Map - Collaborative Key-Value Store

Y.Array - Collaborative Array

Y.XmlFragment - Collaborative XML/HTML

Document Updates

Encoding Updates

Applying Updates

State Vectors

Transactions

Transaction Origins

Update Merging

Client-Side Merging

Server-Side Merging

Document Storage

Snapshots and Updates Queue

Diff Calculation

Conflict Resolution

Text Conflicts

Map Conflicts

Array Conflicts

Sync Peers

Empty Update Detection

Document Locks

History and Undo

Undo Manager

Snapshots for History

Best Practices

Performance Optimization

Update Compression

Debounce Updates

Lazy Loading

Advanced: Block-Level CRDTs

Resources