Conflict-Free Replicated Data Types (CRDTs) Internals: Building Real-Time Collaborative & Local-First Systems

For decades, cloud-based applications have adhered to a strict centralized client-server paradigm: client devices are treated as dumb terminals that send mutation requests (e.g., HTTP POST/PUT) to a central database, waiting synchronously for the server to validate, serialize, and persist state.

While this architecture simplifies transactional consistency, it fails miserably under modern application demands. When network connectivity drops, users are locked out of their work. High round-trip network latencies make collaborative interfaces feel sluggish, and offline mutations frequently collide, resulting in catastrophic data loss or clunky "conflict resolution" dialogs.

The Local-First Software movement flips this paradigm. In a local-first system (popularized by platforms like Figma, Notion, Linear, and Apple Notes), data lives primarily on the user's local device (IndexedDB, SQLite, or local memory), allowing instant zero-latency reads and writes with full offline capability. When network connectivity is present, devices synchronize in the background peer-to-peer or via lightweight relay servers.

At the mathematical heart of local-first architectures are Conflict-Free Replicated Data Types (CRDTs). CRDTs are specialized data structures that guarantee Strong Eventual Consistency (SEC): any two replicas that have received the same set of updates will converge to the exact same state, regardless of the order in which the updates arrived or whether nodes were temporarily partitioned.

In this technical deep dive, we explore the mathematical foundations of CRDTs (Join-Semilattices), analyze State-based vs. Operation-based models, dissect complex Sequence CRDTs (Yjs, Automerge, and Fugue), and build a production-grade Observed-Remove Set (OR-Set) in TypeScript.

The CAP Theorem & Strong Eventual Consistency (SEC)

In distributed systems, the classical CAP theorem states that under a network partition ($P$), a system must choose between Availability ($A$) and Linearizable Consistency ($C$). Distributed consensus algorithms (such as Raft or Multi-Paxos) prioritize linearizable consistency by blocking writes when a majority quorum cannot be reached.

Local-first applications make the opposite choice: writes must always succeed locally with zero network coordination ($A + P$). However, unlike standard "eventual consistency" (which may lose writes or require heuristic manual conflict resolution like "Last-Write-Wins"), CRDTs provide Strong Eventual Consistency (SEC):

Mathematical Foundations: Join-Semilattices

State-based CRDTs (CvRDTs) achieve deterministic convergence because their state space and merge operations form a Bounded Join-Semilattice $\langle S, \sqcup, \le, \bot \rangle$:

1. $S$ is the set of all possible states.
2. $\le$ is a partial order over $S$ that defines the progression of state (i.e., state moves monotonically forward in time).
3. $\sqcup$ is the Merge (Least Upper Bound / Join) binary operator: $S \times S \to S$.
4. $\bot$ is the bottom element representing the initial empty state.

For any merge function $\sqcup$ to guarantee conflict-free convergence, it must satisfy three fundamental algebraic properties:

The Two Flavors of CRDTs: State-Based vs. Operation-Based

CRDTs come in two distinct operational architectures, differing in network transport requirements and payload sizes:

The Modern Synthesis: Delta-State CRDTs ($\Delta$-CRDTs)

To eliminate the high bandwidth cost of sending full state without taking on the fragile transport requirements of operation-based systems, modern production implementations use Delta-State CRDTs. When a mutation occurs, only the incremental state delta ($\delta$) is generated and sent over the wire. If a packet is lost, standard gossip reconciliation exchanges version vectors to send missing delta ranges.

Core CRDT Primitives Explained

1. Grow-Only Counter (G-Counter)

In a distributed system with $n$ nodes, a naive counter cannot simply send counter++ because network retries cause over-counting. A G-Counter maintains an array of $n$ slots, where each node $i$ only ever increments its own index P[i].

• Value: $V = \sum_{i=1}^{n} P[i]$
• Merge: $\text{Merge}(P_A, P_B)[i] = \max(P_A[i], P_B[i])$

2. Positive-Negative Counter (PN-Counter)

To allow decrements as well as increments, a PN-Counter pairs two G-Counters: $P$ (positive increments) and $N$ (negative decrements). The current value is simply $\sum P[i] - \sum N[i]$.

3. Observed-Remove Set (OR-Set / Add-Wins Set)

Sets are more challenging: what happens if Node A adds "apple" concurrently while Node B deletes "apple"? In a Last-Write-Wins (LWW) set, clock skew can silently destroy data. In an Observed-Remove Set (OR-Set), additions are tagged with unique cryptographic UUIDs or Lamport timestamps.

When an element is deleted, the node observes and records the deletion of all currently visible tag IDs for that element. If another node concurrently added the same element with a new tag ID that the deleting node had not yet observed, the addition wins. This preserves concurrent user intent without silent data erasure.

Sequence CRDTs: The Engine of Collaborative Text (Yjs & Automerge)

Collaborative text editors (like Google Docs or Notion) are the hardest challenge in distributed data. Text cannot be modeled as a simple set because character order matters. If User A types "H" and User B types "i" at index 0, naive index updates (like insert(0, 'H')) will produce scrambled strings depending on network arrival order.

Text Sequence Divergence Challenge:
Initial State: "CAT"

User 1 (at position 0): inserts "B" -> Intent: "BCAT"
User 2 (at position 3): inserts "S" -> Intent: "CATS"

Naive Index Execution:
User 1 receives User 2's op: insert(3, "S") -> "BCATS" (Correct)
User 2 receives User 1's op: insert(0, "B") -> "BCATS" (Correct)

Concurrent Conflict Case:
User 1 (at position 1): inserts "O" -> "COAT" (after 'C')
User 2 (at position 1): inserts "H" -> "CHAT" (after 'C')

Divergence Risk: Will replicas converge to "COHAT" or "CHOAT"?
Must be deterministic and preserve semantic intent without interleaving characters!

The Breakthrough: Relative Identifier Linked Lists (RGA & Yjs)

Modern sequence CRDTs like Yjs (using the YATA algorithm) and Automerge (using RGA / B-tree structures) do not use integer offsets. Instead, every character or chunk is assigned a globally unique immutable ID: (ClientID, LamportClock).

Each character maintains explicit references to its Left Origin ID and Right Origin ID. When inserting a character between two existing characters, it permanently anchors itself to its neighbors. If two users insert characters at the exact same location, a deterministic total ordering tie-breaker (e.g. comparing ClientID) ensures every client renders the exact same sequence.

The Interleaving Bug & Fugue Algorithm

Earlier sequence CRDTs suffered from the infamous Interleaving Problem: when two users concurrently pasted multi-word sentences at the same location, individual characters would alternate (e.g., "HWEOLRLDO" instead of "HELLO WORLD"). Modern algorithms like Fugue and Yjs's struct-store tree hierarchies maintain maximal non-interleaving guarantees across arbitrary concurrent branches.

Hands-On Implementation: Building an Observed-Remove Set (OR-Set) in TypeScript

Let us construct a production-ready, mathematically sound Delta-State Observed-Remove Set (OR-Set) in TypeScript:

import { v4 as uuidv4 } from 'uuid';

export interface ElementTag {
  id: string;        // Globally unique tag (UUID or Lamport ID)
  value: T;          // The underlying payload
  timestamp: number; // Wall clock / Lamport timestamp
}

export interface ORSetState {
  addSet: Map>;     // TagID -> ElementTag
  removeSet: Set;                 // Set of removed TagIDs (Tombstones)
}

export class ORSet {
  private clientId: string;
  private state: ORSetState;

  constructor(clientId: string, initialState?: ORSetState) {
    this.clientId = clientId;
    this.state = initialState ?? {
      addSet: new Map>(),
      removeSet: new Set(),
    };
  }

  /**
   * Add an element to the set.
   * Generates a unique tag ID to ensure concurrent additions never collide.
   */
  public add(value: T): ElementTag {
    const tag: ElementTag = {
      id: `${this.clientId}-${uuidv4()}`,
      value,
      timestamp: Date.now(),
    };
    this.state.addSet.set(tag.id, tag);
    return tag;
  }

  /**
   * Remove an element from the set.
   * Finds all currently observed tags for this value and moves their IDs to removeSet.
   */
  public remove(value: T): string[] {
    const removedTagIds: string[] = [];

    for (const [tagId, tag] of this.state.addSet.entries()) {
      if (tag.value === value && !this.state.removeSet.has(tagId)) {
        this.state.removeSet.add(tagId);
        removedTagIds.push(tagId);
      }
    }

    return removedTagIds;
  }

  /**
   * Check if the set contains a value.
   * An element is present if it has at least one tag in addSet that is NOT in removeSet.
   */
  public has(value: T): boolean {
    for (const [tagId, tag] of this.state.addSet.entries()) {
      if (tag.value === value && !this.state.removeSet.has(tagId)) {
        return true;
      }
    }
    return false;
  }

  /**
   * Read the materialized set values.
   */
  public read(): Set {
    const result = new Set();
    for (const [tagId, tag] of this.state.addSet.entries()) {
      if (!this.state.removeSet.has(tagId)) {
        result.add(tag.value);
      }
    }
    return result;
  }

  /**
   * Merge another replica's state (Lattice Join Operator: ⊔).
   * Satisfies Commutativity, Associativity, and Idempotence!
   */
  public merge(remoteState: ORSetState): void {
    // 1. Union of Add Sets (A.addSet ∪ B.addSet)
    for (const [tagId, tag] of remoteState.addSet.entries()) {
      if (!this.state.addSet.has(tagId)) {
        this.state.addSet.set(tagId, tag);
      }
    }

    // 2. Union of Remove Sets (A.removeSet ∪ B.removeSet)
    for (const tagId of remoteState.removeSet) {
      this.state.removeSet.add(tagId);
    }
  }

  /**
   * Export the current state for serialization across WebSockets / WebRTC.
   */
  public getState(): ORSetState {
    return {
      addSet: new Map(this.state.addSet),
      removeSet: new Set(this.state.removeSet),
    };
  }
}

Simulating Concurrent Operations and Convergence

// Node A and Node B start from a synchronized state
const nodeA = new ORSet('client_A');
const nodeB = new ORSet('client_B');

// Initial setup: Node A adds 'item-1'
nodeA.add('item-1');
nodeB.merge(nodeA.getState());

console.log('Node B reads:', Array.from(nodeB.read())); // ['item-1']

// --- CONCURRENT MUTATIONS OCCUR DURING NETWORK PARTITION ---
// Node A removes 'item-1' (observes tag A-1)
nodeA.remove('item-1');

// Node B concurrently adds 'item-1' (generates fresh tag B-1)
nodeB.add('item-1');

// Replicas re-connect and merge states bidirectionally
nodeA.merge(nodeB.getState());
nodeB.merge(nodeA.getState());

// Both replicas converge to the EXACT same state without conflict!
console.log('Node A state:', Array.from(nodeA.read())); // ['item-1'] (Add-Wins!)
console.log('Node B state:', Array.from(nodeB.read())); // ['item-1'] (Add-Wins!)

CRDTs vs. Operational Transformation (OT): Why the Industry Switched

Before CRDTs gained dominance, real-time collaboration relied on Operational Transformation (OT) (the foundation of Google Docs in 2009):

Production Challenges: Garbage Collection & Tombstone Bloat

While CRDTs guarantee strong consistency, production local-first architectures face real engineering hurdles:

1. Tombstone Accumulation: When characters or set items are deleted, they cannot be immediately dropped from memory; their IDs (tombstones) must be retained to prevent older concurrent updates from resurrecting them. In long-running documents, tombstones can consume $80\%$ of memory.
2. Garbage Collection via Stable Version Vectors: Systems solve tombstone bloat by tracking the minimum acknowledged version vector across all connected replicas. Once an update is known to have been applied by all active peers, the tombstone is safely purged.
3. Compact Binary Encoding: Libraries like Yjs and Automerge use custom binary encodings with Run-Length Encoding (RLE) and variable-length integer compaction (LEB128), compressing sequence CRDT overhead to within $1.5\times$ to $2\times$ of raw text size.

Summary & Architecture Roadmap

Conflict-Free Replicated Data Types are the foundational primitive enabling the next generation of resilient, offline-first, collaborative web and mobile applications:

• Decouple State from Network Transport: Design your application state around join-semilattices so network flakiness, out-of-order delivery, and offline edits never corrupt data.
• Choose the Right CRDT Primitive: Use LWW-Registers for simple independent attributes (e.g. user presence/status), OR-Sets for collections/tags, and Sequence CRDTs (Yjs/Automerge) for rich text and canvas scene graphs.
• Implement Delta-State Sync: Avoid transmitting complete document state by generating incremental state deltas and maintaining causal version vectors.
• Plan for Tombstone Pruning: Implement stable version vector tracking or snapshot checkpoints to keep client-side SQLite/IndexedDB footprints lean.