dag-sync

A TypeScript library for DAG-based git-like synchronization with automatic conflict detection through module-based commutativity analysis.

Installation

npm install dag-sync

Overview

dag-sync provides a framework for building distributed synchronization systems using Directed Acyclic Graphs (DAGs), similar to git's commit model. The library is agnostic to your commit payloads, storage backend, and state management.

Key features:

• DAG-based commit structure with cryptographic signing
• Module-based commutativity detection with schema support
• Bidirectional commit traversal with change counting
• 3-way text field merging using jsdiff (server wins on conflicts)
• Automatic sequence management based on commutativity
• Client-server synchronization with granular rollback
• Stateless client design via PersistentRW
• Full TypeScript support

Quick Start

1. Define Your Payload with FieldChange

Payloads must use FieldChange<T> for all mutable fields to enable bidirectional traversal:

import { FieldChange } from 'dag-sync';

interface MyPayload {
  type: 'item';
  id: string;
  name?: FieldChange<string>;
  value?: FieldChange<number>;
  _create?: boolean;
}

const COMMIT_TYPES = {
  ITEM_UPSERT: 'item-upsert',
} as const;

2. Implement CommitRegistry

import { CommitRegistry, Commit } from 'dag-sync';

class MyRegistry implements CommitRegistry<MyPayload> {
  async getCommit(hash: string): Promise<Commit<MyPayload> | null> { /* ... */ }
  async storeCommit(commit: Commit<MyPayload>): Promise<void> { /* ... */ }
  async hasCommit(hash: string): Promise<boolean> { /* ... */ }
  async updateServerSeq(hash: string, serverSeq: number): Promise<void> { /* ... */ }
  async updateNextHash(hash: string, nextHash: string): Promise<void> { /* ... */ }
  async getServerHead(): Promise<string | null> { /* ... */ }
}

3. Implement CommutativityHelperModule

Modules return CommutativityDictUnitary (single commit deltas). The library handles applying these to the main dictionary with change tracking.

import {
  BaseCommutativityHelper,
  CommutativityHelperModule,
  CommutativityDictUnitary,
  TextFieldValue,
  isFieldChange,
} from 'dag-sync';

class MyModule extends BaseCommutativityHelper<MyPayload>
  implements CommutativityHelperModule<MyPayload>
{
  readonly moduleId = 'my-module';
  readonly supportedCommitTypes = [COMMIT_TYPES.ITEM_UPSERT];
  readonly schema = {
    item: {
      id: { type: 'text' },
      name: { type: 'text' },  // prevent3WayMerges defaults to true
      description: { type: 'text', prevent3WayMerges: false },  // Enable 3-way merge
      value: { type: 'number' },
    },
  };
  readonly references = [];

  async forward(registry, commit): Promise<CommutativityDictUnitary> {
    const { id, name, value, _create } = commit.payload;
    const isCreate = _create === true;
    const valueChanges: Record<string, unknown> = {};

    if (isCreate) {
      valueChanges['id'] = { base: '', value: id } as TextFieldValue;
    }
    if (name && isFieldChange(name)) {
      valueChanges['name'] = { base: name.prev ?? '', value: name.next } as TextFieldValue;
    }
    if (value && isFieldChange(value)) {
      valueChanges['value'] = value.next;
    }

    return {
      item: [{ id, created: isCreate, valueChanges }],
    };
  }

  async backward(registry, commit): Promise<CommutativityDictUnitary[]> {
    if (commit.isMergeCommit) {
      return commit.parent_hashes.map(() => ({}));
    }
    // Return unitary with reversed changes
    const { id, name, value, _create } = commit.payload;
    const valueChanges: Record<string, unknown> = {};

    if (_create) {
      valueChanges['id'] = { base: '', value: id } as TextFieldValue;
    }
    if (name && isFieldChange(name)) {
      valueChanges['name'] = { base: name.next, value: name.prev ?? '' } as TextFieldValue;
    }
    if (value && isFieldChange(value)) {
      valueChanges['value'] = value.prev;
    }

    return [{ item: [{ id, created: _create, valueChanges }] }];
  }
}

4. Create DagClient

import { DagClient, CommutativityModuleRegistry } from 'dag-sync';

const moduleRegistry = new CommutativityModuleRegistry<MyPayload>();
moduleRegistry.registerModule(new MyModule());

// Server
const server = new DagClient({
  isServer: true,
  actorId: 'server',
  actorPrivateKey: serverPrivateKey,
  actorsPublicKeys: new Map([['server', serverPublicKey], ['client', clientPublicKey]]),
  registry: new MyRegistry(),
  moduleRegistry,
});

const rootCommit = await server.server_create_root();

// Client
const client = new DagClient({
  isServer: false,
  actorId: 'client',
  actorPrivateKey: clientPrivateKey,
  actorsPublicKeys: new Map([['server', serverPublicKey], ['client', clientPublicKey]]),
  registry: new MyRegistry(),
  moduleRegistry,
  persistentRW: new MyPersistence(),
});

await client.client_sync_root(rootCommit);

// Create commits using FieldChange structure
const commit = await client.client_create_commit({
  payload: {
    type: 'item',
    id: '1',
    name: { prev: null, next: 'Test' },  // Create: prev is null
    _create: true,
  },
  commitType: COMMIT_TYPES.ITEM_UPSERT,
});

// Update: prev is old value, next is new value
const updateCommit = await client.client_create_commit({
  payload: {
    type: 'item',
    id: '1',
    name: { prev: 'Test', next: 'Updated' },
  },
  commitType: COMMIT_TYPES.ITEM_UPSERT,
});

await server.server_process_commits([commit, updateCommit]);
await client.client_sync(await server.getLastSyncedHash());

Core Concepts

Bidirectional Commits with FieldChange

All field changes must use FieldChange<T> structure:

interface FieldChange<T> {
  prev: T | null;  // Previous value (null for creates)
  next: T;         // New value
}

// Create: prev is null
{ name: { prev: null, next: 'New Item' } }

// Update: prev is old value
{ name: { prev: 'Old Name', next: 'New Name' } }

This enables:

• Forward traversal: Apply changes using next values
• Backward traversal: Reverse changes using prev values
• Change counting: Track how many times each field was modified

Commutativity Detection

Operations that don't conflict can be reordered (commute). The library automatically:

• Groups non-commuting operations into sequences
• Detects conflicts when sequences don't commute
• Rolls back only conflicting local changes during sync (granular rollback)

Conflict Rules

1. Same non-text field modified → Conflict
2. Same text field modified →
   • If prevent3WayMerges: false: Attempts 3-way merge using jsdiff. Server wins on overlapping edits.
   • If prevent3WayMerges: true (default): Conflict
3. Update before creation → Conflict (update depends on create)
4. Reference to uncreated element → Conflict

Text Field 3-Way Merge

For text fields with prevent3WayMerges: false, the library performs automatic 3-way merging:

// In your schema
mergeableDescription: { type: 'text', prevent3WayMerges: false }

Merge behavior:

• Non-overlapping changes merge cleanly (e.g., editing different words)
• Overlapping changes → server's version wins
• Identical changes → no conflict

Example:

Base:   "The quick brown fox"
Server: "The quick red fox"     (brown → red)
Client: "The quick brown cat"   (fox → cat)
Result: "The quick red cat"     (both changes merged)

Server Sequence Numbers

• null - Not registered with server
• -1 - Registered but not yet processed
• -2 - Refused by server
• >= 0 - Accepted

Testing

npm test

Building

npm run build

Documentation

See CLAUDE.md for detailed API documentation, architecture, and examples.

License

MIT