Architecture

Journal-based CRDT with edit buffering, snapshot compaction, and synced undo/redo.

State Model

typescript

interface ClientState {
  // 1. Current computed value (derived from snapshot + journal + edits)
  graph: SceneGraph;

  // 2. Committed edits (sent or pending acknowledgement)
  journal: JournalEntry[];

  // 3. Uncommitted operations (in-progress edits)
  edits: EditBuffer;

  // 4. Checkpoint for fast replay
  snapshot: Snapshot;

  // 5. Clocks
  lamportTime: number;
  vectorClock: VectorClock;
  sessionId: string;
}

interface JournalEntry {
  msg: CRDTMessage;
  ack: boolean;           // Has server acknowledged?
  deletedAt?: number;     // If set, message is "undone"
}

interface EditBuffer {
  ops: Operation[];       // Pending operations (merged)
  baseGraph: SceneGraph; // Graph state when edits started
}

interface Snapshot {
  graph: SceneGraph;
  vectorClock: VectorClock;
  journalIndex: number;   // How many entries are baked in
}

graph

Current computed state. Derived from snapshot + journal + edits. Updated on every change.

journal

Committed messages. Each entry tracks acknowledgement status and deletion (undo) state.

edits

Uncommitted operations. Accumulated during a gesture (e.g., drag), then committed as one message.

snapshot

Periodic checkpoint. Bakes in acknowledged journal entries for fast replay.

Actions

1. Edit (Uncommitted)

Add operation to edit buffer and update graph immediately:

typescript

function onEdit(state: ClientState, op: Operation): ClientState {
  // Save start graph for undo (first edit only)
  const baseGraph = state.edits.ops.length === 0
    ? state.graph
    : state.edits.baseGraph;

  // Merge into edit buffer
  const ops = mergeOp(state.edits.ops, op);

  // Clone graph + target node, then apply in place
  const graph: SceneGraph = { ...state.graph, nodes: { ...state.graph.nodes } };
  if (op.key && graph.nodes[op.key]) {
    graph.nodes[op.key] = { ...graph.nodes[op.key] };
  }
  applyOperation(graph, op);

  return { ...state, graph, edits: { ops, baseGraph } };
}

// Merge additive ops, replace LWW ops
function mergeOp(buffer: EditBuffer, op: Operation): void {
  const key = `${op.key}:${op.path}`;
  const existing = buffer.ops.find(o => `${o.key}:${o.path}` === key);

  if (existing && isAdditive(op.ot)) {
    // Merge: vector3.add [1,0,0] + [0,2,0] = [1,2,0]
    existing.value = addValues(existing.value, op.value);
  } else {
    buffer.ops.push(op);
  }
}

2. Commit Edits

Compact edit buffer into one message, add to journal, send to server:

Edit buffer: [add [1,0,0], add [0,2,0], set color]
                      │
                      ▼
              Compact into 1 message
                      │
                      ▼
┌─────────────────────────────────────────┐
│  msg: { ops: [add [1,2,0], set color] } │
│  ack: false                             │
│  deletedAt: undefined                   │
└─────────────────────────────────────────┘
                      │
                      ▼
              Send to server

typescript

function commitEdits(state: ClientState): { state: ClientState; msg: CRDTMessage | null } {
  if (state.edits.ops.length === 0) {
    return { state, msg: null };
  }

  const msg: CRDTMessage = {
    id: generateUUID(),
    sessionId: state.sessionId,
    clock: incrementClock(state.vectorClock, state.sessionId),
    lamportTime: state.lamportTime + 1,
    timestamp: Date.now(),
    ops: state.edits.ops,
  };

  return {
    state: {
      ...state,
      journal: [...state.journal, { msg, ack: false }],
      edits: { ops: [], baseGraph: state.graph },
      lamportTime: msg.lamportTime,
      vectorClock: msg.clock,
    },
    msg,
  };
}

3. Server Acknowledgement

When server confirms receipt:

typescript

function onServerAck(state: ClientState, msgId: string): ClientState {
  const idx = state.journal.findIndex(e => e.msg.id === msgId);
  if (idx < 0) return state;

  const journal = state.journal.map((e, i) =>
    i === idx ? { ...e, ack: true } : e
  );
  return { ...state, journal };
}

4. Remote Message

When receiving edits from other clients:

typescript

function onRemoteMessage(state: ClientState, msg: CRDTMessage): ClientState {
  // Skip duplicates
  if (state.journal.some(e => e.msg.id === msg.id)) {
    return state;
  }

  // Add to journal (already acked — came from server)
  let journal = [...state.journal, { msg, ack: true }];

  // Process meta ops (undo/redo) — clone only the affected entries
  for (const op of msg.ops) {
    if (op.ot === 'meta.undo') {
      journal = journal.map(e =>
        e.msg.id === op.targetMsgId ? { ...e, deletedAt: msg.timestamp } : e
      );
    } else if (op.ot === 'meta.redo') {
      journal = journal.map(e => {
        if (e.msg.id !== op.targetMsgId) return e;
        const { deletedAt, ...rest } = e;
        return rest;
      });
    }
  }

  // Merge clocks
  const vectorClock = mergeClock(state.vectorClock, msg.clock);
  const lamportTime = Math.max(state.lamportTime, msg.lamportTime);

  // Rebuild graph from snapshot + journal + pending edits
  const graph = rebuildGraph(state.snapshot, journal, state.edits.ops);

  return { ...state, journal, vectorClock, lamportTime, graph };
}

5. Compaction

Bake acknowledged entries into snapshot:

typescript

function compact(state: ClientState): ClientState {
  const lastAckedIdx = state.journal.findLastIndex(e => e.ack);
  if (lastAckedIdx < 0) return state;

  // Build new snapshot (skip deleted entries)
  let snapshotGraph = state.snapshot.graph;
  for (let i = 0; i <= lastAckedIdx; i++) {
    const entry = state.journal[i];
    if (entry.deletedAt) continue;
    snapshotGraph = applyMessage(snapshotGraph, entry.msg);
  }

  return {
    ...state,
    snapshot: {
      graph: snapshotGraph,
      vectorClock: state.journal[lastAckedIdx].msg.clock,
      journalIndex: state.snapshot.journalIndex + lastAckedIdx + 1,
    },
    journal: state.journal.slice(lastAckedIdx + 1),
  };
}

Rebuild Graph

Always derived from snapshot + journal + edits:

typescript

function rebuildGraph(
  snapshot: Snapshot,
  journal: JournalEntry[],
  pendingOps: Operation[]
): SceneGraph {
  let graph = snapshot.graph;

  // Apply journal (skip deleted entries and meta ops)
  for (const entry of journal) {
    if (entry.deletedAt) continue;

    const realOps = entry.msg.ops.filter(op => !op.ot.startsWith('meta.'));
    if (realOps.length > 0) {
      graph = applyMessage(graph, { ...entry.msg, ops: realOps });
    }
  }

  // Apply pending edits
  for (const op of pendingOps) {
    graph = applyOperation(graph, op);
  }

  return graph;
}

Undo / Redo

Undo and redo are synced messages using meta.undo and meta.redo operations. They set/clear deletedAt on target messages and sync across all clients.

Meta Operations

typescript

interface UndoOp {
  ot: 'meta.undo';
  key: '_meta';
  path: '_meta';
  targetMsgId: string;
}

interface RedoOp {
  ot: 'meta.redo';
  key: '_meta';
  path: '_meta';
  targetMsgId: string;
}

Undo

typescript

function undo(state: ClientState): { state: ClientState; msg: CRDTMessage | null } {
  let currentState = state;
  let targetMsgId: string;

  // If edit buffer not empty, commit first then mark as deleted
  if (state.edits.ops.length > 0) {
    const { state: committed, msg } = commitEdits(state);
    currentState = committed;
    targetMsgId = msg!.id;
  } else {
    // Find last non-deleted message from this session
    const lastActive = [...currentState.journal]
      .reverse()
      .find(e => !e.deletedAt && e.msg.sessionId === currentState.sessionId);

    if (!lastActive) return { state: currentState, msg: null };
    targetMsgId = lastActive.msg.id;
  }

  // Create undo message
  const undoMsg: CRDTMessage = {
    id: generateUUID(),
    sessionId: currentState.sessionId,
    clock: incrementClock(currentState.vectorClock, currentState.sessionId),
    lamportTime: currentState.lamportTime + 1,
    timestamp: Date.now(),
    ops: [{ ot: 'meta.undo', key: '_meta', path: '_meta', targetMsgId }],
  };

  // Apply locally and return message to send
  return {
    state: applyMetaMessage(currentState, undoMsg),
    msg: undoMsg
  };
}

Redo

typescript

function redo(state: ClientState): { state: ClientState; msg: CRDTMessage | null } {
  // Find last deleted message from this session
  const lastDeleted = [...state.journal]
    .reverse()
    .find(e => e.deletedAt && e.msg.sessionId === state.sessionId);

  if (!lastDeleted) return { state, msg: null };

  const redoMsg: CRDTMessage = {
    id: generateUUID(),
    sessionId: state.sessionId,
    clock: incrementClock(state.vectorClock, state.sessionId),
    lamportTime: state.lamportTime + 1,
    timestamp: Date.now(),
    ops: [{ ot: 'meta.redo', key: '_meta', path: '_meta', targetMsgId: lastDeleted.msg.id }],
  };

  return {
    state: applyMetaMessage(state, redoMsg),
    msg: redoMsg
  };
}

Synced Undo Flow

Key Insight: Undo/redo are regular messages that sync across all clients. Everyone sees the same undo state. No separate undo stack needed.

┌──────────────────────────────────────────────────────────────┐
│                    SYNCED UNDO FLOW                          │
├──────────────────────────────────────────────────────────────┤
│                                                              │
│  Alice ──▶ edit cube position                                │
│        ──▶ commit (msg-1)                                    │
│        ──▶ undo()                                            │
│              │                                               │
│              ▼                                               │
│        Create meta.undo message (target: msg-1)              │
│              │                                               │
│              ├──▶ Apply locally: msg-1.deletedAt = now       │
│              │    Rebuild graph (skips msg-1)                │
│              │                                               │
│              └──▶ Send to server                             │
│                        │                                     │
│                        ▼                                     │
│                   Server receives meta.undo                  │
│                   Marks msg-1.deletedAt                      │
│                   Broadcasts to all clients                  │
│                        │                                     │
│                        ▼                                     │
│  Bob receives meta.undo ──▶ msg-1.deletedAt = now            │
│                         ──▶ Rebuild graph                    │
│                         ──▶ Cube position reverts            │
│                                                              │
└──────────────────────────────────────────────────────────────┘

Idempotency

Deduplication by message ID prevents double-application:

Operation	Idempotent?	Reason
`*.set`	Yes	Compares lamportTime, same result on replay
`*.add`	With dedup	Requires message ID check to prevent double-add
`meta.undo`	Yes	Sets deletedAt, idempotent
`meta.redo`	Yes	Clears deletedAt, idempotent

Design Decisions

Why edit buffer?

Gestures like dragging generate many operations per second. The edit buffer merges them into one message on commit, reducing journal size and network traffic.

Why synced undo?

Local-only undo creates divergent state. By making undo a message, all clients see the same undo history and converge to the same state.

Why deletedAt instead of removal?

Soft delete allows redo. The message stays in journal until compaction, when deleted entries are garbage collected.

Why rebuild on remote message?

Remote messages may arrive out of order. Rebuilding from snapshot ensures consistent state regardless of arrival order.

References and Hydration

Nodes can reference other nodes using the $ref pattern. This is a data convention, not a CRDT operation—references are resolved during hydration in user space.

The `$ref` Pattern

typescript

// Store references as { $ref: 'node-key' }
{
  key: 'player',
  tag: 'Character',
  children: ['weapon-1'],           // Structural children (string[])
  equippedWeapon: { $ref: 'weapon-1' },  // Reference to another node
  material: { $ref: 'shared-material' }, // Reference to shared resource
}

Hydration

During hydration, resolve $ref objects to actual node references:

typescript

interface Ref {
  $ref: string;
}

function isRef(value: unknown): value is Ref {
  return (
    typeof value === 'object' &&
    value !== null &&
    '$ref' in value &&
    typeof (value as Ref).$ref === 'string'
  );
}

function hydrate(graph: SceneGraph, node: SceneNode): HydratedNode {
  const hydrated: any = { ...node };

  for (const [key, value] of Object.entries(node)) {
    if (isRef(value)) {
      // Resolve reference to actual node
      hydrated[key] = graph.nodes[value.$ref];
    }
  }

  return hydrated;
}

Children vs References

Aspect	`children: string[]`	`{ $ref: 'key' }`
Purpose	Structural hierarchy	Pointer/association
Ownership	Parent owns children	No ownership
Deletion	Cascade/tombstone children	Just removes pointer
Storage	Array of keys	Object with `$ref`
Usage	Scene graph traversal	Shared resources, links

Architecture

State Model

graph

journal

edits

snapshot

Actions

1. Edit (Uncommitted)

2. Commit Edits

3. Server Acknowledgement

4. Remote Message

5. Compaction

Rebuild Graph

Undo / Redo

Meta Operations

Undo

Redo

Synced Undo Flow

Idempotency

Design Decisions

Why edit buffer?

Why synced undo?

Why deletedAt instead of removal?

Why rebuild on remote message?

References and Hydration

The $ref Pattern

Hydration

Children vs References

The `$ref` Pattern