What are CRDTs and why they matter

Imagine a collaborative application where two users modify the same document offline. Alice adds "Hello " at the beginning of a line, Bob adds " World" at the end. When they reconnect, how do you integrate the two edits without losing data and without explicit conflicts?

This is the problem of conflict-free replication. Traditional solutions (three-way merge, CRDTs with vector clocks) are complex and require a central server. CRDTs offer an elegant alternative: every operation is independent and commutative, meaning the order of application doesn't matter — the result will always be the same across all replicas.

A CRDT is a data structure that guarantees:

• Convergence: all replicas reach the same state after receiving the same operations
• Conflict-free: no manual merge operation required
• Commutativity: the order of operation application doesn't influence the final result
• Delay tolerance: works on poor networks, offline, and with arbitrary latency

Last-Write-Wins (LWW) CRDT

The simplest strategy is Last-Write-Wins (LWW): every edit is tagged with a timestamp (or a unique user identifier if timestamps aren't synchronized), and the most recent value wins.

Consider an example of LWW Map:

interface ValueWithTimestamp {
  value: unknown;
  timestamp: number;
  replicaId: string;
}

class LWWMap {
  private map: Map = new Map();

  set(key: string, value: unknown, timestamp: number, replicaId: string) {
    const existing = this.map.get(key);

    // The new value wins if it has a higher timestamp
    // If timestamp is equal, use replica ID for deterministic tie-breaking
    if (!existing || timestamp > existing.timestamp ||
        (timestamp === existing.timestamp && replicaId > existing.replicaId)) {
      this.map.set(key, { value, timestamp, replicaId });
    }
  }

  get(key: string): unknown {
    return this.map.get(key)?.value;
  }

  // Merge receives a remote replica and applies changes
  merge(remote: Map) {
    for (const [key, remoteValue] of remote) {
      this.set(key, remoteValue.value, remoteValue.timestamp, remoteValue.replicaId);
    }
  }
}
    

The advantage of LWW is simplicity; the downside is that small data loss is possible. If two users modify the same field nearly simultaneously, the first user's change is silently overwritten.

Commutative operations: the foundation of CRDTs

The key to CRDTs is building commutative operations (order doesn't matter) and idempotent operations (applying twice causes no issues). A simple example is a Counter CRDT:

class CounterCRDT {
  // Each replica maintains its own counter
  // The global value is the sum of all local counters
  private increments: Map = new Map();

  increment(replicaId: string) {
    const current = this.increments.get(replicaId) || 0;
    this.increments.set(replicaId, current + 1);
  }

  decrement(replicaId: string) {
    const current = this.increments.get(replicaId) || 0;
    this.increments.set(replicaId, current - 1);
  }

  get value(): number {
    let sum = 0;
    for (const count of this.increments.values()) {
      sum += count;
    }
    return sum;
  }

  // Merge is simply: for each replica, take the maximum value
  merge(remote: Map) {
    for (const [replicaId, remoteCount] of remote) {
      const local = this.increments.get(replicaId) || 0;
      this.increments.set(replicaId, Math.max(local, remoteCount));
    }
  }
}
    

Notice that the order of operation application doesn't matter. If replica A does +1, +2, -1 and replica B only receives the final state (+2, -1), the result is identical: +1 overall.

Common CRDT types

Beyond Counter and Map, there are CRDTs for Set, List, Text, and more complex structures:

1. OR-Set (Observed-Remove Set)

A Set CRDT that allows add/remove without conflicts. Each element has a unique UUID for every add:

class ORSet {
  private elements: Map> = new Map(); // element -> set of UUIDs

  add(element: string): string {
    const id = crypto.randomUUID();
    if (!this.elements.has(element)) {
      this.elements.set(element, new Set());
    }
    this.elements.get(element)!.add(id);
    return id; // Return the ID so you can remove it later
  }

  remove(element: string, id: string) {
    this.elements.get(element)?.delete(id);
  }

  contains(element: string): boolean {
    return this.elements.has(element) && this.elements.get(element)!.size > 0;
  }

  toArray(): string[] {
    return Array.from(this.elements.entries())
      .filter(([_, ids]) => ids.size > 0)
      .map(([elem]) => elem);
  }
}
    

2. RGA (Replicated Growable Array) for Text CRDT

For collaborative editors, it's crucial to preserve character order. RGA (and the more modern YATA) assigns each character a unique identifier based on (replicaId, clock):

interface CharWithId {
  id: string; // "replicaId:clock"
  char: string;
  tombstone: boolean; // Marked as deleted, but not removed
}

class RGATextCRDT {
  private chars: CharWithId[] = [];
  private clock = 0;
  private replicaId: string;

  constructor(replicaId: string) {
    this.replicaId = replicaId;
  }

  insert(position: number, char: string): void {
    this.clock++;
    const id = `${this.replicaId}:${this.clock}`;
    this.chars.splice(position, 0, { id, char, tombstone: false });
  }

  delete(position: number): void {
    this.chars[position].tombstone = true; // Mark-and-sweep, don't remove yet
  }

  getText(): string {
    return this.chars
      .filter(c => !c.tombstone)
      .map(c => c.char)
      .join('');
  }
}
    

3. Map with nested CRDT

For complex structures, you can compose CRDTs: a Map where each value is a Counter, Set, or List CRDT:

class NestedCRDT {
  private map: Map = new Map();

  getOrCreateCounter(key: string): CounterCRDT {
    if (!this.map.has(key)) {
      this.map.set(key, new CounterCRDT());
    }
    return this.map.get(key) as CounterCRDT;
  }

  // Recursive merge: for each key, merge the nested CRDT
  merge(remote: Map) {
    for (const [key, remoteValue] of remote) {
      const local = this.map.get(key);
      if (local && typeof local.merge === 'function') {
        local.merge(remoteValue);
      } else {
        this.map.set(key, remoteValue);
      }
    }
  }
}
    

Recognized CRDT algorithms: Yjs, Automerge, OT

Three approaches dominate the conflict-free replication landscape:

Yjs

Yjs is a JavaScript library for CRDTs that uses an optimized version of the YATA algorithm (Yet Another Text Algorithm). It's extremely popular for collaborative editors (Figma-like, Google Docs-like).

import * as Y from 'yjs';
import { WebsocketProvider } from 'y-websocket';

// Create a Yjs document
const ydoc = new Y.Doc();
const ytext = ydoc.getText('shared-text');
const ymap = ydoc.getMap('shared-map');

// Observe local changes
ytext.observe(event => {
  console.log('Text changed:', event.changes);
});

// Sync with server via WebSocket
const provider = new WebsocketProvider(
  'ws://localhost:1234',
  'my-room',
  ydoc
);

// Modify the text
ytext.insert(0, 'Hello ');
ymap.set('name', 'Alice');

// Yjs automatically handles synchronization
// and replica convergence
    

Automerge

Automerge is a JSON-like CRDT library with a focus on immutability and history. Perfect for applications where you need to track changes and branching (like Git for data).

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

// Create a document
let doc1 = Automerge.from({ tasks: [] });

// Make an edit
doc1 = Automerge.change(doc1, d => {
  d.tasks.push({ text: 'Learn CRDT', done: false });
});

// Clone the document for a second replica
let doc2 = Automerge.clone(doc1);

// Divergent changes
doc1 = Automerge.change(doc1, d => {
  d.tasks[0].done = true;
});

doc2 = Automerge.change(doc2, d => {
  d.tasks.push({ text: 'Deploy', done: false });
});

// Merge: Automerge does it automatically without conflicts
const merged = Automerge.merge(doc1, doc2);
console.log(merged);
// { tasks: [{ text: 'Learn CRDT', done: true }, { text: 'Deploy', done: false }] }
    

Operational Transform (OT)

While CRDTs are commutative, Operational Transform uses a different approach: it records operations and transforms them so they maintain intent even when conflicting. It's used in Google Docs. OT requires a central server to linearize orders, while CRDTs don't.

Performance, memory, and trade-offs

CRDTs come with costs:

• Memory overhead: each element must have a unique identifier. Text CRDT with millions of characters can be bulky.
• Implementation complexity: some CRDTs (like YATA for Text) are intricate and require attention to detail.
• Garbage collection: deleted elements (tombstones) must be cleaned periodically, otherwise memory grows indefinitely.
• Serialization: transmitting an entire CRDT document can be larger than a JSON delta.

Libraries like Yjs mitigate these issues with:

• Efficient binary encoding
• State vector + deletion vector for incremental synchronization
• Automatic garbage collection

Practical applications and use cases

CRDTs enable:

• Offline-first collaborative editors: Google Docs-like without a mandatory server (Notion, Figma use similar architectures)
• Decentralized note-taking: apps like Obsidian Sync use CRDTs for synchronization across devices
• Whiteboard and diagramming: Excalidraw, Tldraw support CRDTs for real-time collaboration
• Replicated local databases: RxDB, Replicache use CRDT-like for their sync engine
• P2P and mesh systems: IPFS, Dat Protocol, and apps on Bluetooth mesh use CRDTs for distributed consensus
• Decentralized version control: systems like Pijul and Jujutsu use CRDT-like merging to avoid Git conflicts

Testing and Prototyping CRDTs

Testing CRDTs means verifying that convergence and commutativity work. This is where Ollama comes in for prototyping and generating random test cases:

// Pseudo-code: use a local AI model (via Ollama)
// to generate random operation sequences and verify convergence

import fetch from 'node-fetch';

async function generateTestScenario(): Promise {
  const response = await fetch('http://localhost:11434/api/generate', {
    method: 'POST',
    body: JSON.stringify({
      model: 'llama3.1:8b',
      prompt: 'Generate 5 random CRDT operations in JSON format for testing: add(x), remove(x), increment(x). Format: ["op1", "op2", ...]',
      stream: false
    })
  });
  const data = await response.json();
  return JSON.parse(data.response);
}

async function testCRDTConvergence() {
  const operations = await generateTestScenario();

  const replicaA = new CounterCRDT();
  const replicaB = new CounterCRDT();

  // Apply operations in different orders
  for (const op of operations) {
    if (op.includes('increment')) replicaA.increment('replicaA');
    if (op.includes('decrement')) replicaA.decrement('replicaA');
  }

  for (const op of operations.reverse()) {
    if (op.includes('increment')) replicaB.increment('replicaB');
    if (op.includes('decrement')) replicaB.decrement('replicaB');
  }

  console.assert(replicaA.value === replicaB.value, 'Convergence failed!');
}
    

Ollama provides a local AI model (default llama3.1:8b) for generating test fixtures, scenarios, and edge cases. It's not the site's AI provider, but a useful tool for local development and testing.

How to get started: Yjs step-by-step

If you want to add CRDTs to an Angular or React editor:

npm install yjs y-websocket y-protocols lib0

# For Monaco or CodeMirror editors:
npm install y-monaco  # or y-codemirror
    

// In an Angular component:
import { Component, OnInit, OnDestroy } from '@angular/core';
import * as Y from 'yjs';
import { WebsocketProvider } from 'y-websocket';

@Component({
  selector: 'app-collab-editor',
  template: '<div #editor></div>'
})
export class CollabEditorComponent implements OnInit, OnDestroy {
  private ydoc = new Y.Doc();
  private provider: WebsocketProvider;
  private ytext: Y.Text;

  ngOnInit() {
    this.ytext = this.ydoc.getText('shared-text');
    this.provider = new WebsocketProvider(
      'ws://your-sync-server.com',
      'editor-room',
      this.ydoc
    );

    // Observe changes
    this.ytext.observe(event => {
      this.updateLocalView(event);
    });
  }

  onUserEdit(text: string) {
    this.ytext.delete(0, this.ytext.length);
    this.ytext.insert(0, text);
  }

  ngOnDestroy() {
    this.provider.disconnect();
    this.ydoc.destroy();
  }

  private updateLocalView(event: any) {
    console.log('Remote changes:', event.changes);
  }
}
    

Frequently asked questions (FAQ)