Implementing CRDTs (Conflict-free Replicated Data Types) in Browser Storage

The paradigm shift towards "local-first" software has fundamentally changed how we architect web applications. Instead of treating the server as the absolute source of truth and the client as a mere view layer, local-first applications treat the local device as the primary storage and execution environment. This approach yields applications that load instantly, work seamlessly offline, and provide a snappy, zero-latency user experience.

However, building local-first applications introduces a massive engineering challenge: distributed data synchronization. When multiple clients (or even multiple tabs within the same browser) modify local state concurrently while completely offline, how do you merge those changes when they eventually come back online without creating conflicts, overwriting data, or requiring manual user intervention to resolve conflicts?

Enter Conflict-free Replicated Data Types (CRDTs).

In this highly technical deep dive, we will explore the mathematical foundations of CRDTs, implement state-based CRDTs from scratch in TypeScript, and persist them robustly in the browser using IndexedDB. Finally, we'll look at how to synchronize these data structures across browser tabs in real-time, how to handle tombstone garbage collection, and how to utilize Hybrid Logical Clocks to preserve causality.

The Mathematical Foundation of CRDTs

CRDTs are a family of data structures designed to be replicated across multiple networked computers, updated independently and concurrently without coordination, and mathematically guaranteed to resolve inconsistencies automatically.

There are two primary flavors of CRDTs, both achieving the exact same eventual consistency guarantees but through different network payloads and mathematical rules:

1. State-based CRDTs (CvRDTs - Convergent Replicated Data Types): In this model, replicas send their full local state to other replicas. When a replica receives a state from another peer, it merges it with its own local state. For this to work, the merge operation (often denoted as join or ⊔) must be a join semilattice. Specifically, it must be:

   • Commutative: A ⊔ B = B ⊔ A (Order of merging doesn't matter)
   • Associative: (A ⊔ B) ⊔ C = A ⊔ (B ⊔ C) (Grouping doesn't matter)
   • Idempotent: A ⊔ A = A (Merging the same state multiple times has no additional effect)

   State-based CRDTs are highly resilient to network drops because if a message is lost, sending the state again later will encompass all previous changes.

2. Operation-based CRDTs (CmRDTs - Commutative Replicated Data Types): Instead of sending the full state, replicas only broadcast the specific operations (e.g., "insert 'a' at index 5", "delete character at index 10"). The mathematical requirement here is that all concurrent operations must commute. CmRDTs are typically more bandwidth-efficient than sending full states, but they require exactly-once causal delivery guarantees from the network layer. If an operation is dropped or delivered out of order, the CRDT can break.

For browser storage and offline-first web apps, state-based CRDTs (and their optimized variants like delta-state CRDTs) are often easier to implement natively, as we can simply serialize the entire deterministic state into IndexedDB and merge it when reading. We don't have to rely on a complex local message queue to guarantee exactly-once delivery.

Choosing the Right Browser Storage

Before writing the CRDT logic, we must choose where this data will live in the browser. Web APIs give us several options, but not all are suited for distributed data types.

1. LocalStorage / SessionStorage: These are synchronous, string-only APIs with a strict 5MB quota. Because they block the main JavaScript thread, they are entirely unsuitable for storing potentially large CRDT states or parsing massive JSON strings of operation logs.
2. Origin Private File System (OPFS): OPFS provides highly performant, file-based storage with direct synchronous access in Web Workers. It is excellent for heavy binary data (like SQLite databases compiled to WebAssembly), but the API is complex and overkill for basic JSON-serializable CRDT states.
3. IndexedDB: The gold standard for browser storage. It is asynchronous, supports storing complex JavaScript objects directly (via the structured clone algorithm), and offers generous storage quotas (often gigabytes). It also supports transactions, ensuring our CRDT state saves atomically.

We will use IndexedDB to store our CRDTs. Because the native IndexedDB API is notoriously verbose, heavily reliant on event listeners, and difficult to compose, we will conceptually rely on Promise-based wrappers (like Jake Archibald's idb library) for our implementation logic.

Implementing a Basic State-Based CRDT: The LWW-Register

Let's start with the simplest possible CRDT: the Last-Writer-Wins (LWW) Register. A register holds a single value. To resolve concurrent updates, we attach a logical timestamp to the value. The value with the highest timestamp wins.

Here is a robust implementation in TypeScript:

export class LWWRegister<T> {
  public id: string;
  public state: {
    peerId: string;
    timestamp: number; // For robust systems, this should be an HLC
    value: T | null;
  };

  constructor(id: string, peerId: string) {
    this.id = id;
    this.state = {
      peerId: peerId,
      timestamp: 0,
      value: null,
    };
  }

  // Update the value with a new timestamp
  public set(value: T): void {
    this.state = {
      peerId: this.state.peerId,
      timestamp: Date.now(),
      value: value,
    };
  }

  public get(): T | null {
    return this.state.value;
  }

  // The merge function (⊔) satisfying commutativity, associativity, idempotence
  public merge(remoteState: LWWRegister<T>['state']): void {
    const local = this.state;
    const remote = remoteState;

    // Last Writer Wins logic
    if (remote.timestamp > local.timestamp) {
      this.state = remote;
    } else if (remote.timestamp === local.timestamp && remote.peerId > local.peerId) {
      // Tie-breaker using peerId to ensure absolute determinism
      this.state = remote;
    }
    // If local.timestamp > remote.timestamp, we do nothing.
  }
}

Notice the tie-breaker logic: if two peers update the register at the exact same millisecond (which happens frequently in distributed systems), we compare their peerId strings to ensure both peers eventually converge on the exact same value. This determinism is the bedrock of CRDTs.

A Note on Time: Hybrid Logical Clocks (HLCs)

In the implementation above, we used Date.now(). In distributed systems, relying on physical wall clocks is incredibly dangerous. A user's device might have its clock skewed by minutes or years. To solve this, production CRDTs use Hybrid Logical Clocks (HLC). An HLC combines physical time with a logical counter. If a peer receives a timestamp from the future, it advances its own clock to match, ensuring causality is preserved regardless of NTP skew.

Scaling Up: The Observed-Remove Set (OR-Set)

A register is too simple for most applications. What if we want a collaborative list, a to-do list, or a tagging system? A standard mathematical Set doesn't work well. If Peer A removes an item while Peer B concurrently adds it offline, the system needs to know which operation happened first to resolve the state.

The Observed-Remove Set (OR-Set) solves this by attaching unique tags to every element when it is added. Removing an element means adding its specific tags to a "tombstone" set rather than deleting it from memory.

type Tag = string;

export class ORSet<T> {
  public peerId: string;
  // Map of value (stringified) to a set of active tags
  private elements: Map<string, Set<Tag>> = new Map();
  // Set of all tags that have been removed
  private tombstones: Set<Tag> = new Set();

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

  private generateTag(): Tag {
    return `${this.peerId}-${Date.now()}-${Math.random().toString(36).substring(2, 9)}`;
  }

  public add(value: T): void {
    const serialized = JSON.stringify(value);
    const tag = this.generateTag();
    
    if (!this.elements.has(serialized)) {
      this.elements.set(serialized, new Set());
    }
    this.elements.get(serialized)!.add(tag);
  }

  public remove(value: T): void {
    const serialized = JSON.stringify(value);
    const tags = this.elements.get(serialized);
    
    if (tags) {
      // Move all currently observed tags for this value into tombstones
      tags.forEach(tag => this.tombstones.add(tag));
      // We can optimize locally by clearing the active tags
      this.elements.delete(serialized);
    }
  }

  public get value(): T[] {
    const result: T[] = [];
    for (const [serialized, tags] of this.elements.entries()) {
      // Only include if there is at least one tag not in tombstones
      let isActive = false;
      for (const tag of tags) {
        if (!this.tombstones.has(tag)) {
          isActive = true;
          break;
        }
      }
      if (isActive) {
        result.push(JSON.parse(serialized));
      }
    }
    return result;
  }

  public merge(remoteSet: ORSet<T>): void {
    // 1. Merge tombstones (union of sets)
    remoteSet.tombstones.forEach(tag => this.tombstones.add(tag));

    // 2. Merge elements (union of tag sets for each value)
    for (const [serialized, remoteTags] of remoteSet.elements.entries()) {
      if (!this.elements.has(serialized)) {
        this.elements.set(serialized, new Set());
      }
      const localTags = this.elements.get(serialized)!;
      remoteTags.forEach(tag => localTags.add(tag));
    }
  }
}

Because elements are mapped to unique generated tags, adding the same semantic value twice results in two distinct tags. Deleting it deletes all currently observed tags at the time of deletion. If a remote peer concurrently adds the same value, it will have a different tag, which won't be caught in the local tombstone set. This means the concurrent add survives the delete. This elegantly satisfies the conflict resolution requirement for collaborative sets.

Integrating with IndexedDB for Persistence

Holding our CRDTs in JavaScript heap memory is great for runtime performance, but the browser tab will eventually be closed, or the browser might crash. We must persist the state to IndexedDB to survive reloads.

Because our CRDT states are deterministic, we can simply serialize the elements and tombstones maps to IndexedDB every time a mutation occurs, and reload them on boot.

Using a simplified wrapper around IndexedDB (like idb):

import { openDB, DBSchema, IDBPDatabase } from 'idb';

interface CRDTDB extends DBSchema {
  crdt_store: {
    key: string;
    value: {
      id: string;
      elements: Array<[string, Array<string>]>;
      tombstones: Array<string>;
      lastUpdated: number;
    };
  };
}

class CRDTStorage {
  private dbPromise: Promise<IDBPDatabase<CRDTDB>>;

  constructor() {
    this.dbPromise = openDB<CRDTDB>('local-first-db', 1, {
      upgrade(db) {
        db.createObjectStore('crdt_store', { keyPath: 'id' });
      },
    });
  }

  public async saveORSet(id: string, orSet: ORSet<any>): Promise<void> {
    const db = await this.dbPromise;
    
    // Convert Maps and Sets to serializable Arrays
    const elementsArray = Array.from(orSet['elements'].entries()).map(
      ([val, tags]) => [val, Array.from(tags)] as [string, Array<string>]
    );
    const tombstonesArray = Array.from(orSet['tombstones']);

    // IndexedDB put is an atomic transaction
    await db.put('crdt_store', {
      id,
      elements: elementsArray,
      tombstones: tombstonesArray,
      lastUpdated: Date.now()
    });
  }

  public async loadORSet(id: string, peerId: string): Promise<ORSet<any>> {
    const db = await this.dbPromise;
    const data = await db.get('crdt_store', id);
    
    const set = new ORSet(peerId);
    if (data) {
      // Rehydrate Maps and Sets
      data.elements.forEach(([val, tags]) => {
        set['elements'].set(val, new Set(tags));
      });
      set['tombstones'] = new Set(data.tombstones);
    }
    return set;
  }
}

The Tombstone Garbage Collection Problem

A critical issue in the OR-Set implementation above is that the tombstones set grows monotonically. Every deletion increases the size of the CRDT state. Over time, an active application will accumulate megabytes of tombstones, causing IndexedDB reads and writes to become dangerously slow, potentially causing jank on the main thread.

To mitigate this, production CRDT systems implement Tombstone Garbage Collection. If we can establish that all peers in a cluster have successfully synced up to a certain point in time, we can safely drop tombstones that are older than that threshold, because we mathematically guarantee no peer will ever try to resurrect them. This requires tracking vector clocks for the entire peer group, which introduces complexity but is essential for long-lived local-first applications.

Alternatively, implementing Delta-State CRDTs means you only persist the "delta" (the exact tags added or moved to tombstones in the last operation) into an append-only IndexedDB object store. You then lazily fold over these logs when initializing.

Syncing Across Tabs and Devices

A major benefit of local-first architectures is that different browser tabs can act as concurrent collaborators. If a user modifies data in Tab A, Tab B should instantly reflect that change without hitting a remote server.

To sync our CRDTs across tabs in the same browser efficiently, we use the BroadcastChannel API.

const channel = new BroadcastChannel('crdt_sync');

// When a local mutation occurs, we broadcast it:
channel.postMessage({
  type: 'SYNC',
  payload: {
    // In a real system, send a Delta instead of the full state to save CPU/Memory
    elements: Array.from(mySet['elements'].entries()).map(([k, v]) => [k, Array.from(v)]),
    tombstones: Array.from(mySet['tombstones'])
  }
});

// Listening for updates from other tabs
channel.onmessage = (event) => {
  if (event.data.type === 'SYNC') {
    const remoteSet = new ORSet('remote');
    // Rehydrate remoteSet from event.data.payload
    event.data.payload.elements.forEach(([val, tags]: [string, string[]]) => {
        remoteSet['elements'].set(val, new Set(tags));
    });
    remoteSet['tombstones'] = new Set(event.data.payload.tombstones);
    
    // Merge the state
    mySet.merge(remoteSet);
    
    // Trigger a UI re-render (e.g. React state update)
    updateUI();
  }
};

For syncing across physical devices over the internet, this exact same payload can be piped through WebSockets (to a relay server) or directly peer-to-peer using WebRTC (via libraries like simple-peer). Because CRDT merges are commutative and associative, the network transport does not need to guarantee order. It doesn't matter if messages arrive out of order, or if the user goes offline while on a subway and reconnects two hours later. The mathematical guarantees ensure that all nodes will seamlessly converge to the exact same state once the sync completes.

Real-World Libraries: Yjs and Automerge

While understanding the internals of CRDTs is crucial for systems engineering, you rarely need to write your own in production. The JavaScript ecosystem has two monolithic, battle-tested CRDT implementations that have solved these hard problems.

Yjs

Yjs is heavily optimized for text collaboration and relies on a highly efficient linked-list representation of operations. It uses binary encoding, making its state incredibly compact and fast to transmit. Yjs has a rich ecosystem of providers, including y-indexeddb for browser storage, y-webrtc for P2P sync, and y-websocket for centralized relaying. It powers complex applications like collaborative text editors (ProseMirror, Quill) and canvas apps.

Automerge

Automerge, spearheaded by Martin Kleppmann (author of Designing Data-Intensive Applications), treats CRDTs more like standard JSON documents. Its latest iterations (Automerge-Repo) have drastically improved performance using a Rust-based WebAssembly core, making it viable for massive document states. It provides an excellent Developer Experience (DX) for developers used to functional state updates, feeling very similar to modifying state with Immer.js.

Both libraries handle the complex edge cases that our naive implementations skipped: garbage collection of tombstones, highly compressed binary formats, array/sequence conflict resolution (which is notoriously harder than sets), and optimal delta-sync protocols that prevent sending unnecessary data over the wire.

Conclusion

Implementing CRDTs in browser storage bridges the gap between ephemeral web apps and robust, offline-capable local-first software. By anchoring our data structures in mathematical properties—commutativity, associativity, and idempotence—we free ourselves from the complexities of distributed locking, fragile conflict resolution modals, and centralized server consensus.

Coupling these robust structures with IndexedDB for persistent local storage, and BroadcastChannel/WebRTC for decentralized synchronization, results in an architecture that is incredibly resilient. The local device becomes the definitive source of truth, the network becomes an eventual enhancement rather than a hard dependency, and the user experience remains blazingly fast regardless of network conditions.

As the web continues to evolve towards edge computing, WebAssembly, and local-first architectures, mastering CRDTs is no longer just an academic exercise in computer science; it is a fundamental requirement for the next generation of web development.