dag-sync

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

Installation

``bash
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

$3

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

`typescript
import { FieldChange } from 'dag-sync';

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

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

$3

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

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

$3

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

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

class MyModule extends BaseCommutativityHelper
implements CommutativityHelperModule
{
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 {
const { id, name, value, _create } = commit.payload;
const isCreate = _create === true;
const valueChanges: Record = {};

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 {
if (commit.isMergeCommit) {
return commit.parent_hashes.map(() => ({}));
}
// Return unitary with reversed changes
const { id, name, value, _create } = commit.payload;
const valueChanges: Record = {};

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 }] }];
}
}
`

$3

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

const moduleRegistry = new CommutativityModuleRegistry();
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

$3

All field changes must use FieldChange structure:

`typescript
interface FieldChange {
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

$3

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)

$3

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

$3

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

`typescript
// 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)
`

$3

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

Testing

`bash
npm test
`

Building

`bash
npm run build
``

Documentation

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

License

MIT