Primitives

@robonen/crdt is a small set of independent data structures, each convergent on its own. You can use a single primitive in isolation — a last-writer-wins setting, an ordered list, a collaborative string — or compose them into something bigger. This page walks through each one with a construction example and a small converging scenario.

Every primitive leans on one shared idea: compareOpId — a deterministic total order over operation ids (higher Lamport clock wins; site id breaks ties). Because all primitives resolve conflicts the same way, two replicas that have seen the same operations always agree, no matter the order or duplicates in which those operations arrived. If op ids are new to you, start with Concepts.

Registers

LwwRegister and LwwMap — single values and keyed maps where the write with the highest op id wins.

Ordering

keyBetween / keysBetween — fractional indexing to place or move an item with a single string key.

Sequence

Rga — a replicated growable array: an ordered sequence CRDT with tombstones and a deterministic insert tie-break.

Marks

MarkStore — lightweight Peritext formatting spans anchored to character op ids, resolved per character by highest op id.

LWW registers

A LwwRegister is the smallest CRDT: a single value with a timestamp. Every write carries an OpId, and a write only takes effect if its id is strictly later than the current one by compareOpId. That single rule gives you the three convergence properties for free — applying writes is commutative (a later write always beats an earlier one regardless of arrival order), idempotent (re-applying a write is a no-op), and convergent (every replica ends on the same winning write).

set(value, id) returns true when the write won and false when it was superseded, which is handy for skipping downstream work.

import { LwwRegister, opId } from '@robonen/crdt';

// Two replicas hold the same register, start from the same value.
const a = new LwwRegister('draft');
const b = new LwwRegister('draft');

// They write concurrently — A at clock 4, B at clock 5.
a.set('A wins?', opId('a', 4));
b.set('B wins!', opId('b', 5));

// Exchange the writes (order and duplicates don't matter):
a.set('B wins!', opId('b', 5)); // 5 > 4 → accepted, returns true
b.set('A wins?', opId('a', 4)); // 4 < 5 → rejected, returns false

a.get(); // 'B wins!'
a.get() === b.get(); // true — converged on the higher op id

LwwMap

LwwMap is a register per key. Each entry tracks its own timestamp and a tombstone flag, so concurrent set and delete on the same key converge to whichever has the higher op id — deleting is just another timestamped write that happens to hide the value. get, has, keys, and toEntries all skip tombstoned entries, so the map reads like a plain map even though deletions are retained internally for convergence.

import { LwwMap, opId } from '@robonen/crdt';

const a = new LwwMap<string, string>();
const b = new LwwMap<string, string>();

// Concurrent edits to the same key, plus a concurrent delete.
a.set('color', 'red', opId('a', 7));
b.set('color', 'blue', opId('b', 7)); // same clock — site id breaks the tie

a.delete('color', opId('a', 7));        // tie too: delete vs set at the same id

// After both replicas see all three ops…
b.set('color', 'red', opId('a', 7));    // already covered by b's clock-7 write
a.set('color', 'blue', opId('b', 7));   // 'b' > 'a' at clock 7 → blue wins

a.get('color'); // 'blue'
a.has('color'); // true
a.toEntries();  // [['color', 'blue']]

Why keep tombstones? If a delete simply dropped the entry, a concurrent set arriving afterward would resurrect the key — the two replicas would disagree on whether it exists. Retaining the delete as a timestamped tombstone lets compareOpId decide the winner deterministically, the same way it does for live values.

Fractional indexing

Ordering a collaborative list with integer indices is a trap: insert at position 2 and every index after it shifts, so two replicas inserting concurrently clobber each other's positions. keyBetween sidesteps this by giving each item a string key that lives strictly between its neighbors. Order is recovered by sorting keys with plain string comparison — the digit alphabet is ASCII-ascending, so lexical order matches digit order.

Pass null for an open bound: keyBetween(null, x) is "before x", keyBetween(x, null) is "after x", and keyBetween(null, null) seeds an empty list. The result is always strictly between the bounds, so there is unlimited room to keep subdividing — you never run out of space to insert between two adjacent items.

import { keyBetween } from '@robonen/crdt';

// Open bounds (null) ask for "before everything" / "after everything".
const first = keyBetween(null, null);  // e.g. 'V'
const second = keyBetween(first, null); // a key after 'first'
const zeroth = keyBetween(null, first); // a key before 'first'

// Insert strictly between two existing neighbors — no renumbering, ever.
const mid = keyBetween(zeroth, first);
zeroth < mid && mid < first; // true

// Sorting items by key reproduces their order:
const items = [
  { text: 'b', key: first },
  { text: 'a', key: zeroth },
  { text: 'ab', key: mid },
];
items.sort((x, y) => (x.key < y.key ? -1 : x.key > y.key ? 1 : 0));
items.map(i => i.text); // ['a', 'ab', 'b']

Batches and moves

keysBetween generates n keys at once, all strictly between the bounds and in ascending order — useful for seeding a list or bulk-inserting a run of items. Because a key is just a value on the item, moving an item is a single-field write: compute a new key between its new neighbors and re-sort. Nothing else in the list is touched, which is exactly what makes concurrent reorders converge cleanly (they reduce to independent LwwRegister writes on each item's key).

import { keysBetween } from '@robonen/crdt';

// Pre-allocate N keys at once — ascending, all strictly between the bounds.
const keys = keysBetween(null, null, 5);
// each keys[i] < keys[i + 1]

// Moving an item is a single-field write: give it a new key between its
// new neighbors and re-sort. Nothing else in the list changes.
function move(list, fromKeyLeft, fromKeyRight) {
  return keyBetween(fromKeyLeft, fromKeyRight);
}

Heads up:keyBetween requires lower < upper and throws otherwise. Two replicas independently generating a key between the same neighbors can produce identical keys; pair the key with the item's op id as a secondary sort to keep ordering deterministic, or let Rga handle character-level ordering for you.

The RGA sequence

Rga (Replicated Growable Array) is the heart of the package — the CRDT behind collaborative text. Each element is a node with a unique OpId, a value, and an originLeft: the id of the element it was inserted after (null means the start of the sequence). Deletion never removes a node; it sets a tombstone flag, so the node lives on as a stable anchor that later inserts and marks can still reference.

integrateInsert(id, value, originLeft) and integrateDelete(id) are both idempotent — re-integrating an op you've already seen is a no-op that safely returns true. Read the visible state with toArray(); use visible() to get the surviving nodes (and their ids) for cursor anchoring, and length for the visible count.

import { Rga, opId } from '@robonen/crdt';

const rga = new Rga<string>();

// integrateInsert(id, value, originLeft) — originLeft = null means "at the start".
rga.integrateInsert(opId('a', 1), 'H', null);
rga.integrateInsert(opId('a', 2), 'i', opId('a', 1)); // after 'H'

rga.toArray().join(''); // 'Hi'

// Delete = tombstone. The node stays as an anchor; it just stops being visible.
rga.integrateDelete(opId('a', 2));
rga.toArray().join(''); // 'H'
rga.length;             // 1  (visible count, tombstones excluded)

Concurrent inserts and the tie-break

The interesting case is two replicas inserting at the same origin at the same time. Both new elements claim the slot right after the same left neighbor — so which goes first? RGA resolves this deterministically: among elements sharing an origin, the one with the higher op id is placed first (compareOpId > 0 scans past it). Because every replica applies the identical comparison, they all settle on the same order without any coordination.

import { Rga, opId } from '@robonen/crdt';

// Two replicas both start from "AC" and concurrently insert after 'A'.
function seed() {
  const rga = new Rga<string>();
  rga.integrateInsert(opId('seed', 1), 'A', null);
  rga.integrateInsert(opId('seed', 2), 'C', opId('seed', 1));
  return rga;
}

const left = seed();
const right = seed();

// left inserts 'x' after 'A'; right inserts 'y' after 'A' — same origin.
const xOp = { id: opId('left', 5), value: 'x', origin: opId('seed', 1) };
const yOp = { id: opId('right', 5), value: 'y', origin: opId('seed', 1) };

// Apply locally, then exchange. Order and duplicates don't matter.
left.integrateInsert(xOp.id, xOp.value, xOp.origin);
left.integrateInsert(yOp.id, yOp.value, yOp.origin);

right.integrateInsert(yOp.id, yOp.value, yOp.origin);
right.integrateInsert(xOp.id, xOp.value, xOp.origin);

// Tie-break: higher op id first. opId('right', 5) > opId('left', 5)
// (same clock, 'right' > 'left'), so 'y' lands before 'x'.
left.toArray().join('');  // 'AyxC'
right.toArray().join(''); // 'AyxC' — converged

Causal buffering

RGA requires inserts to be integrated in causal order: an element's originLeft must already be present, or there's no anchor to insert after. Rather than guess, integrateInsert returns false when the origin is missing and integrateDelete returns false for an unknown target — the signal to buffer the op and retry once its dependency lands. (At a higher level, Replica does this bookkeeping for you, holding and replaying ops automatically.)

import { Rga, opId } from '@robonen/crdt';

const rga = new Rga<string>();
rga.integrateInsert(opId('a', 1), 'H', null);

// An op arrives BEFORE its origin (causal violation). integrateInsert
// returns false instead of corrupting order — the caller buffers it.
const pending = { id: opId('a', 3), value: '!', origin: opId('a', 2) };
const ok = rga.integrateInsert(pending.id, pending.value, pending.origin);
// ok === false — origin opId('a', 2) isn't present yet

// Once the missing origin lands, retry the buffered op:
rga.integrateInsert(opId('a', 2), 'i', opId('a', 1));
rga.integrateInsert(pending.id, pending.value, pending.origin); // now true

rga.toArray().join(''); // 'Hi!'

Garbage collection. Tombstones accumulate. When every replica has fully synced and nothing is in flight, gc(stable, keep?) drops deleted nodes whose insert is covered by a stable VersionVector, returning how many it removed. Run it only at quiescence — a late op that uses a dropped node as its origin could no longer integrate — and pass keep to protect ids still referenced elsewhere, such as mark span endpoints.

Marks (lightweight Peritext)

Formatting in a collaborative editor can't be stored by offset — insert a character and every offset after it shifts, so a "bold from 3 to 7" range would drift onto the wrong text. MarkStore follows the Peritext model: a MarkSpan anchors to the OpId of its first and last characters (an inclusive range), so the span moves with the text it covers as the sequence grows and shrinks around it.

A span's value is a JSON-serializable MarkValue — pass true (or attributes like a color string) to apply the mark, and null or false to clear it.

import { Rga, MarkStore, opId } from '@robonen/crdt';

// Build a sequence and grab the op ids of its characters.
const rga = new Rga<string>();
const ids: ReturnType<typeof opId>[] = [];
let left: ReturnType<typeof opId> | null = null;
for (let i = 0; i < 'bold'.length; i++) {
  const id = opId('a', i + 1);
  rga.integrateInsert(id, 'bold'[i]!, left);
  ids.push(id);
  left = id;
}

const marks = new MarkStore();

// A span anchors to the FIRST and LAST character op ids (inclusive), not to
// integer offsets — so it survives concurrent inserts/deletes around it.
marks.add({
  id: opId('a', 10),
  type: 'strong',
  value: true,
  start: ids[0]!, // 'b'
  end: ids[3]!,   // 'd'
});

// resolve() returns one active type→value map per character, in document order.
const active = marks.resolve(rga.visible().map(n => n.id));
active.map(m => m.get('strong')); // [true, true, true, true]

Resolving and converging

add(span) just records a span (idempotent by span id). The real work is resolve(order): given the character op ids in document order — typically rga.visible().map(n => n.id) — it returns one Map<type, value> of active marks per character. For each character and mark type, the covering span with the highest op id wins, so concurrent formatting converges by the same compareOpId rule as everything else; a winning null/false span clears the mark.

import { MarkStore, opId } from '@robonen/crdt';

const store = new MarkStore();
const start = opId('a', 1);
const end = opId('a', 4);

// Concurrent formatting on the same range: B turns it bold, A clears it.
store.add({ id: opId('a', 9), type: 'strong', value: false, start, end });
store.add({ id: opId('b', 9), type: 'strong', value: true, start, end });

// Highest op id wins per (character, type). opId('b', 9) > opId('a', 9),
// so 'strong' resolves to true — a null/false value would have cleared it.
const order = [opId('a', 1), opId('a', 2), opId('a', 3), opId('a', 4)];
store.resolve(order).map(m => m.get('strong')); // [true, true, true, true]

Where to next

Concepts — op ids, Lamport clocks, version vectors, and why convergence holds across all of these primitives.
Replication & Sync — wire the primitives to a Replica for delta sync and automatic causal buffering.
Playground — watch two replicas diverge and reconcile, live in the browser.