Understanding Yjs: CRDT Data Structures, Conflict Resolution, and Real‑Time Synchronization

Yjs Overview

Yjs is a high‑performance operation‑based CRDT library that enables automatic synchronization of collaborative applications. It exposes its internal CRDT model as shared data types such as YMap , YArray , and YText , guaranteeing eventual consistency without central servers.

Modeling Data Structures

All Yjs data is stored in a bidirectional linked list . Each Item represents a single user operation and contains a unique ID (client, clock), origin references, parent information, and the actual content.

class Item {
  constructor(id, origin, rightOrigin, parent, parentSub, content) {
    this.id = id; // { client, clock }
    this.origin = origin;
    this.rightOrigin = rightOrigin;
    this.parent = parent;
    this.parentSub = parentSub;
    this.content = content;
    this.left = null;
    this.right = null;
  }
}

class ID {
  constructor (client, clock) {
    this.client = client;
    this.clock = clock;
  }
}

Items are also indexed in a StructStore , which keeps a per‑client array of items sorted by their logical clock, allowing fast binary‑search look‑ups.

Conflict Resolution – YATA Algorithm

When concurrent operations target the same position, Yjs runs the integrate(transaction, offset) routine. It walks left and right neighbours, builds conflictingItems and itemsBeforeOrigin sets, and uses ID comparison to decide the correct insertion point, ensuring a deterministic final order.

if (offset > 0) {
  this.id.clock += offset;
  this.left = getItemCleanEnd(transaction, transaction.doc.store, createID(this.id.client, this.id.clock - 1));
  this.origin = this.left.lastId;
  this.content = this.content.splice(offset);
  this.length -= offset;
}

The algorithm handles four typical cases: missing left neighbour, isolated items, mismatched right neighbours, and special handling for YMap entries.

Transaction and Update Flow

A Transaction groups all inserts and deletes for a single logical change. During integration Yjs calls:

addStruct(transaction.doc.store, this);
this.content.integrate(transaction, this);
addChangedTypeToTransaction(transaction, this.parent, this.parentSub);

These calls register the item in the struct store, merge its content, and record the parent modification for later synchronization.

Garbage Collection and Double‑Buffer Deletion

Deleted items are marked with item.deleted = true and managed by a GC object that integrates itself into the transaction. Yjs also maintains two buffers: DeleteSet (records what has been removed) and StateVector (represents each client’s latest clock), enabling efficient cleanup and consistency checks.

class GC {
  constructor (id, length) {
    this.id = id;
    this.length = length;
  }
  get deleted () { return true; }
  delete () {}
  integrate (transaction, offset) {
    if (offset > 0) {
      this.id.clock += offset;
      this.length -= offset;
    }
    addStruct(transaction.doc.store, this);
  }
}

Undo Management

Yjs provides an UndoManager that records each transaction. Undoing a transaction involves marking its inserted items as deleted and restoring any items that were removed in that transaction.

Network Synchronization

Synchronization uses a two‑phase protocol based on binary encoding, StateVector exchange, and delta updates. Clients first exchange state vectors to discover missing operations, then transmit only the required Item and DeleteSet deltas, achieving efficient real‑time sync.

Summary

Yjs combines a bidirectional linked‑list model, a per‑client struct store, and the YATA algorithm to resolve conflicts, while its transaction system, garbage collection, undo manager, and two‑phase binary sync make it a robust foundation for building collaborative editors.